Source code

001package com.hfg.math;
002
003import java.math.BigDecimal;
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.Collections;
007import java.util.List;
008
009import com.hfg.exception.ProgrammingException;
010import com.hfg.util.CompareUtil;
011import com.hfg.util.collection.CollectionUtil;
012
013//------------------------------------------------------------------------------
014/**
015 Generic range object.
016 <p></p>
017 @author J. Alex Taylor, hairyfatguy.com
018 */
019//------------------------------------------------------------------------------
020// com.hfg Library
021//
022// This library is free software; you can redistribute it and/or
023// modify it under the terms of the GNU Lesser General Public
024// License as published by the Free Software Foundation; either
025// version 2.1 of the License, or (at your option) any later version.
026//
027// This library is distributed in the hope that it will be useful,
028// but WITHOUT ANY WARRANTY; without even the implied warranty of
029// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
030// Lesser General Public License for more details.
031//
032// You should have received a copy of the GNU Lesser General Public
033// License along with this library; if not, write to the Free Software
034// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
035//
036// J. Alex Taylor, President, Founder, CEO, COO, CFO, OOPS hairyfatguy.com
037// jataylor@hairyfatguy.com
038//------------------------------------------------------------------------------
039public class Range<T extends Number> implements Cloneable, Comparable<Range<T>>
040{
041   private T mStart;
042   private T mEnd;
043
044   // Cached values
045   private Boolean mEndValueIsExclusive;
046
047   //###########################################################################
048   // CONSTRUCTORS
049   //###########################################################################
050
051   //--------------------------------------------------------------------------
052   public Range()
053   {
054   }
055
056   //--------------------------------------------------------------------------
057   public Range(T inStart, T inEnd)
058   {
059      mStart = inStart;
060      mEnd   = inEnd;
061   }
062
063   //###########################################################################
064   // PUBLIC METHODS
065   //###########################################################################
066
067   //--------------------------------------------------------------------------
068   public Range<T> setStart(T inValue)
069   {
070      mStart = inValue;
071      return this;
072   }
073
074   //--------------------------------------------------------------------------
075   public T getStart()
076   {
077      return mStart;
078   }
079
080
081   //--------------------------------------------------------------------------
082   public Range<T> setEnd(T inValue)
083   {
084      mEnd = inValue;
085      return this;
086   }
087
088   //--------------------------------------------------------------------------
089   public T getEnd()
090   {
091      return mEnd;
092   }
093
094
095   //--------------------------------------------------------------------------
096   @Override
097   public String toString()
098   {
099      return String.format("[%s, %s]",
100            getStart() != null ? getStart().toString() : null,
101            getEnd() != null ? getEnd().toString() : null);
102   }
103
104   //---------------------------------------------------------------------------
105   @Override
106   public Range<T> clone()
107   {
108      Range<T>  cloneObj;
109      try
110      {
111         cloneObj = (Range<T>) super.clone();
112      }
113      catch (CloneNotSupportedException e)
114      {
115         throw new ProgrammingException(e);
116      }
117
118      return cloneObj;
119   }
120
121   //--------------------------------------------------------------------------
122   @Override
123   public int hashCode()
124   {
125      int hashCode = (getStart() != null ? getStart().hashCode() : 0);
126      hashCode += 31 * (getEnd() != null ? getEnd().hashCode() : 0);
127
128      return hashCode;
129   }
130
131   //--------------------------------------------------------------------------
132   @Override
133   public boolean equals(Object inObj2)
134   {
135      boolean result = false;
136
137      if (inObj2 != null
138            && inObj2 instanceof Range)
139      {
140         result = (0 == compareTo((Range<T>)inObj2));
141      }
142
143      return result;
144   }
145
146   //--------------------------------------------------------------------------
147   @Override
148   public int compareTo(Range<T> inObj2)
149   {
150      int result = 0;
151
152      if (null == inObj2)
153      {
154         result = 1;
155      }
156      else
157      {
158         // Some custom work here to ensure that null starts sort first and
159         // null ends sort last
160         if (getStart() != null)
161         {
162            if (inObj2.getStart() != null)
163            {
164               result = CompareUtil.compare(getStart(), inObj2.getStart());
165            }
166         }
167         else if (inObj2.getStart() != null)
168         {
169            result = -1;
170         }
171
172         if (0 == result)
173         {
174            if (getEnd() != null)
175            {
176               if (inObj2.getEnd() != null)
177               {
178                  result = CompareUtil.compare(getEnd(), inObj2.getEnd());
179               }
180            }
181            else if (inObj2.getEnd() != null)
182            {
183               result = 1;
184            }
185         }
186      }
187
188      return result;
189   }
190
191   //--------------------------------------------------------------------------
192   public Double length()
193   {
194      Double length = null;
195      if (getStart() != null
196            && getEnd() != null)
197      {
198         length = getEnd().doubleValue() - getStart().doubleValue();
199
200         // Is the end value inclusive?
201         if (! endValueIsExclusive())
202         {
203            length += 1;
204         }
205      }
206
207      return length;
208   }
209
210   //--------------------------------------------------------------------------
211   public boolean contains(Number inValue)
212   {
213      return ((inValue != null
214               && ((getStart() != null
215                && inValue.doubleValue() >= getStart().doubleValue()
216                && getEnd() != null
217                && (inValue.doubleValue() < getEnd().doubleValue()
218                   || (! endValueIsExclusive()
219                       && inValue.doubleValue() == getEnd().doubleValue())))
220               || (null == getStart()
221                  && getEnd() != null
222                  && (inValue.doubleValue() < getEnd().doubleValue()
223                      || (! endValueIsExclusive()
224                          && inValue.doubleValue() == getEnd().doubleValue())))
225               || (null == getEnd()
226                  && getStart() != null
227                  && inValue.doubleValue() >= getStart().doubleValue()))
228               || (null == getStart()
229                   && null == getEnd()))
230              || (null == getStart()
231                  && null == getEnd()));
232   }
233
234   //--------------------------------------------------------------------------
235   public boolean contains(int inValue)
236   {
237      return ((getStart() != null
238               && inValue >= getStart().doubleValue()
239               && getEnd() != null
240               && (inValue < getEnd().doubleValue()
241                   || (! endValueIsExclusive()
242                       && inValue == getEnd().doubleValue())))
243              || (null == getStart()
244                  && getEnd() != null
245                  && (inValue < getEnd().doubleValue()
246                      || (! endValueIsExclusive()
247                          && inValue == getEnd().doubleValue())))
248              || (null == getEnd()
249                  && getStart() != null
250                  && inValue >= getStart().doubleValue())
251              || (null == getStart()
252                  && null == getEnd()));
253   }
254
255   //--------------------------------------------------------------------------
256   public boolean contains(float inValue)
257   {
258      return ((getStart() != null
259               && inValue >= getStart().doubleValue()
260               && getEnd() != null
261               && (inValue < getEnd().doubleValue()
262                   || (! endValueIsExclusive()
263                       && inValue == getEnd().doubleValue())))
264              || (null == getStart()
265                  && getEnd() != null
266                  && (inValue < getEnd().doubleValue()
267                      || (! endValueIsExclusive()
268                          && inValue == getEnd().doubleValue())))
269              || (null == getEnd()
270                  && getStart() != null
271                  && inValue >= getStart().doubleValue())
272              || (null == getStart()
273                  && null == getEnd()));
274   }
275
276   //--------------------------------------------------------------------------
277   public boolean contains(double inValue)
278   {
279      return ((getStart() != null
280               && inValue >= getStart().doubleValue()
281               && getEnd() != null
282               && (inValue < getEnd().doubleValue()
283                   || (! endValueIsExclusive()
284                       && inValue == getEnd().doubleValue())))
285              || (null == getStart()
286                  && getEnd() != null
287                  && (inValue < getEnd().doubleValue()
288                      || (! endValueIsExclusive()
289                          && inValue == getEnd().doubleValue())))
290              || (null == getEnd()
291                  && getStart() != null
292                  && inValue >= getStart().doubleValue())
293              || (null == getStart()
294                  && null == getEnd()));
295   }
296
297   //--------------------------------------------------------------------------
298   public boolean contains(Range<T> inRange2)
299   {
300      return (contains(inRange2.getStart().doubleValue())
301              && contains(inRange2.getEnd().doubleValue()));
302   }
303
304   //---------------------------------------------------------------------------
305   /**
306    Collapses a collection of specified ranges.
307    <p>
308    Ex: given three ranges: [1,4], [2,10], and [14,15] the result would be two ranges: [1,10] and [14,15].
309    </p>
310    @param inOrigList a collection of Ranges to be combined.
311    @return a list of Ranges that represents the union of the specified Ranges.
312    */
313   public static <T extends Number> List<Range<T>> union(Collection<Range<T>> inOrigList)
314   {
315      List<Range<T>> condensedRanges = new ArrayList<>(inOrigList);
316
317      boolean overlap = true;
318      while (overlap)
319      {
320         overlap = false;
321         for (int i = 0; i < condensedRanges.size() - 1; i++)
322         {
323            Range<T> range1 = condensedRanges.get(i);
324
325            for (int j = i + 1; j < condensedRanges.size(); j++)
326            {
327               Range<T> range2 = condensedRanges.get(j);
328
329               if (range1.intersects(range2)
330                     || (! range1.endValueIsExclusive()
331                         && ((range1.getStart() != null
332                              && range2.getEnd() != null
333                              && 1 == range1.getStart().longValue() - range2.getEnd().longValue())
334                             || (range1.getEnd() != null
335                                 && range2.getStart() != null
336                                 && 1 == range2.getStart().longValue() - range1.getEnd().longValue()))))
337               {
338                  T condensedStart = null;
339                  if (range1.getStart() != null
340                        && range2.getStart() != null)
341                  {
342                     int startComparison = CompareUtil.compare(range1.getStart(), range2.getStart());
343                     condensedStart = startComparison > 0 ? range2.getStart() : range1.getStart();
344                  }
345
346                  T condensedEnd = null;
347                  if (range1.getEnd() != null
348                        && range2.getEnd() != null)
349                  {
350                     int endComparison = CompareUtil.compare(range1.getEnd(), range2.getEnd());
351                     condensedEnd = endComparison > 0 ? range1.getEnd() : range2.getEnd();
352                  }
353
354                  Range<T> condensedRange = new Range<T>(condensedStart, condensedEnd);
355
356                  condensedRanges.remove(j);
357                  condensedRanges.remove(i);
358                  condensedRanges.add(condensedRange);
359                  overlap = true;
360                  break;
361               }
362            }
363
364            if (overlap)
365            {
366               break;
367            }
368         }
369      }
370
371      Collections.sort(condensedRanges);
372
373      return condensedRanges;
374   }
375
376   //---------------------------------------------------------------------------
377   /**
378    Returns a single Range that encompasses the collection of input ranges and ignores internal gaps.
379    @param inOrigList a collection of input ranges
380    @return a single Range that encompasses the input ranges and ignores internal gaps
381    */
382   public static <T extends Number> Range<T> superUnion(Collection<Range<T>> inOrigList)
383   {
384      Range<T> superUnion = null;
385
386      if (CollectionUtil.hasValues(inOrigList))
387      {
388         for (Range<T> range : inOrigList)
389         {
390            if (null == superUnion)
391            {
392               superUnion = range;
393            }
394            else
395            {
396               superUnion = superUnion.superUnion(range);
397            }
398         }
399      }
400
401      return superUnion;
402   }
403
404   //---------------------------------------------------------------------------
405   /**
406    Returns a single Range that encompasses both input ranges and ignores internal gaps.
407    @param inRange2 the second Range to union with the current range
408    @return a single Range that encompasses both input ranges and ignores internal gaps
409    */
410   public Range<T> superUnion(Range<T> inRange2)
411   {
412      T start = null;
413      T end = null;
414
415      if (inRange2 != null)
416      {
417         if (getStart() != null
418             && inRange2.getStart() != null)
419         {
420            start = (getStart().doubleValue() < inRange2.getStart().doubleValue() ? getStart() : inRange2.getStart());
421         }
422
423         if (getEnd() != null
424               && inRange2.getEnd() != null)
425         {
426            end = (getEnd().doubleValue() > inRange2.getEnd().doubleValue() ? getEnd() : inRange2.getEnd());
427         }
428      }
429
430      return new Range<>(start, end);
431   }
432
433   //---------------------------------------------------------------------------
434   public List<Range<T>> subtract(Range<T> inRange2)
435   {
436      List<Range<T>> resultRanges = new ArrayList<>(2);
437
438      Range<T> intersection = intersection(inRange2);
439      if (intersection != null)
440      {
441         // Right chunk?
442         Range<T> leftChunk;
443         if (null == getStart())
444         {
445            if (intersection.getStart() != null)
446            {
447               leftChunk = new Range<>();
448
449               if (endValueIsExclusive())
450               {
451                  leftChunk.setEnd(intersection.getStart());
452               }
453               else
454               {
455                  if (intersection.getStart() instanceof Long)
456                  {
457                     leftChunk.setEnd((T) new Long(intersection.getStart().longValue() - 1));
458                  }
459                  else if (intersection.getStart() instanceof Integer)
460                  {
461                     leftChunk.setEnd((T) new Integer(intersection.getStart().intValue() - 1));
462                  }
463               }
464
465               resultRanges.add(leftChunk);
466            }
467         }
468         else if (CompareUtil.compare(intersection.getStart(), getStart()) > 0)
469         {
470            leftChunk = new Range<>();
471            leftChunk.setStart(getStart());
472
473            if (endValueIsExclusive())
474            {
475               leftChunk.setEnd(intersection.getStart());
476            }
477            else
478            {
479               if (intersection.getStart() instanceof Long)
480               {
481                  leftChunk.setEnd((T) new Long(intersection.getStart().longValue() - 1));
482               }
483               else if (intersection.getStart() instanceof Integer)
484               {
485                  leftChunk.setEnd((T) new Integer(intersection.getStart().intValue() - 1));
486               }
487            }
488
489            resultRanges.add(leftChunk);
490         }
491
492         // Right chunk?
493         Range<T> rightChunk;
494         if (null == getEnd())
495         {
496            if (intersection.getEnd() != null)
497            {
498               rightChunk = new Range<>();
499
500               if (endValueIsExclusive())
501               {
502                  rightChunk.setStart(intersection.getEnd());
503               }
504               else
505               {
506                  if (intersection.getEnd() instanceof Long)
507                  {
508                     rightChunk.setStart((T) new Long(intersection.getEnd().longValue() + 1));
509                  }
510                  else if (intersection.getEnd() instanceof Integer)
511                  {
512                     rightChunk.setStart((T) new Integer(intersection.getEnd().intValue() + 1));
513                  }
514               }
515
516               resultRanges.add(rightChunk);
517            }
518         }
519         else if (CompareUtil.compare(intersection.getEnd(), getEnd()) < 0)
520         {
521            rightChunk = new Range<>();
522            rightChunk.setEnd(getEnd());
523
524            if (endValueIsExclusive())
525            {
526               rightChunk.setStart(intersection.getEnd());
527            }
528            else
529            {
530               if (intersection.getStart() instanceof Long)
531               {
532                  rightChunk.setStart((T) new Long(intersection.getEnd().longValue() + 1));
533               }
534               else if (intersection.getStart() instanceof Integer)
535               {
536                  rightChunk.setStart((T) new Integer(intersection.getEnd().intValue() + 1));
537               }
538            }
539
540            resultRanges.add(rightChunk);
541         }
542
543
544      }
545      else
546      {
547         // There was no intersection, hence return the orig.
548         resultRanges.add(this);
549      }
550
551      return resultRanges;
552   }
553
554   //---------------------------------------------------------------------------
555   public boolean endValueIsExclusive()
556   {
557      if (null == mEndValueIsExclusive)
558      {
559         // We can't interrogate T directly so we have to look at the values.
560         T end = getEnd();
561         if (end != null)
562         {
563            mEndValueIsExclusive = (end instanceof Double || end instanceof Float || end instanceof BigDecimal);
564         }
565         else
566         {
567            T start = getStart();
568            if (start != null)
569            {
570               mEndValueIsExclusive = (start instanceof Double || start instanceof Float || start instanceof BigDecimal);
571            }
572         }
573      }
574
575      return mEndValueIsExclusive;
576   }
577
578   //--------------------------------------------------------------------------
579   public Range<T> intersection(Range<T> inRange2)
580   {
581      Range<T> intersection = null;
582
583      if (inRange2 != null)
584      {
585         if (getStart() != null)
586         {
587            if (inRange2.getStart() != null)
588            {
589               if (getEnd() != null)
590               {
591                  if (inRange2.getEnd() != null)
592                  {
593                     if (getStart().doubleValue() <= inRange2.getEnd().doubleValue()
594                           && getEnd().doubleValue() >= inRange2.getStart().doubleValue())
595                     {
596                        //          -----
597                        //             -----
598
599                        intersection = new Range<T>()
600                              .setStart(getStart().doubleValue() < inRange2.getStart().doubleValue() ? inRange2.getStart() : getStart())
601                              .setEnd(getEnd().doubleValue() > inRange2.getEnd().doubleValue() ? inRange2.getEnd() : getEnd());
602                     }
603                  }
604                  else // Range 2 extends infinitely to the right
605                  {
606                     //          -----
607                     //             ----->
608                     if (inRange2.contains(getStart().doubleValue()))
609                     {
610                        intersection = new Range<T>()
611                              .setStart(getStart().doubleValue() < inRange2.getStart().doubleValue() ? inRange2.getStart() : getStart())
612                              .setEnd(getEnd());
613                     }
614                  }
615               }
616               else if (inRange2.getEnd() != null) // Range 1 extends infinitely to the right
617               {
618                  //             ----->
619                  //          -----
620
621                  if (getStart().doubleValue() <= inRange2.getEnd().doubleValue())
622                  {
623                     intersection = new Range<T>()
624                           .setStart(getStart().doubleValue() < inRange2.getStart().doubleValue() ? inRange2.getStart() : getStart())
625                           .setEnd(inRange2.getEnd());
626                  }
627               }
628               else
629               {
630                  // Both ranges extend infinitely to the right
631                  //               ----->
632                  //             ------->
633                  intersection = new Range<T>()
634                        .setStart(getStart().doubleValue() > inRange2.getStart().doubleValue() ? inRange2.getStart() : getStart())
635                        .setEnd(getStart().doubleValue() > inRange2.getStart().doubleValue() ? getStart() : inRange2.getStart());
636               }
637            }
638            else // Range 2 extends infinitely to the left
639            {
640               if (getEnd() != null)
641               {
642                  if (inRange2.getEnd() != null)
643                  {  //               -----
644                     //             <-------
645                     if (getStart().doubleValue() <= inRange2.getEnd().doubleValue())
646                     {
647                        intersection = new Range<T>()
648                              .setStart(getStart())
649                              .setEnd(getEnd().doubleValue() > inRange2.getEnd().doubleValue() ? inRange2.getEnd() : getEnd());
650                     }
651                  }
652                  else // Range 2 extends infinitely to the left & right
653                  {    //               -----
654                     //             <------->
655                     intersection = clone();
656                  }
657               }
658               else if (inRange2.getEnd() != null) // Range 1 extends infinitely to the right
659               {   //             ----->
660                  //          <---
661                  if (inRange2.contains(getStart().doubleValue()))
662                  {
663                     intersection = new Range<T>()
664                           .setStart(getStart())
665                           .setEnd(inRange2.getEnd());
666                  }
667               }
668               else
669               {
670                  // Both ranges extend infinitely to the right
671                  //             ----->
672                  //          <------->
673                  intersection = new Range<T>()
674                        .setStart(getStart());
675               }
676            }
677         }
678         else if (inRange2.getStart() != null)
679         {
680            if (getEnd() != null)
681            {
682               if (inRange2.getEnd() != null)
683               {
684                  //             <-----
685                  //               -------
686                  if (inRange2.getStart().doubleValue() <= getEnd().doubleValue())
687                  {
688                     intersection = new Range<T>()
689                           .setStart(inRange2.getStart())
690                           .setEnd(getEnd().doubleValue() <= inRange2.getEnd().doubleValue() ? getEnd() : inRange2.getEnd());
691                  }
692               }
693               else
694               {
695                  //             <-----
696                  //               ------->
697                  if (inRange2.getStart().doubleValue() <= getEnd().doubleValue())
698                  {
699                     intersection = new Range<T>()
700                           .setStart(inRange2.getStart())
701                           .setEnd(getEnd());
702                  }
703               }
704            }
705            else
706            {
707               if (inRange2.getEnd() != null)
708               {
709                  //         <----->
710                  //            ---
711                  intersection = inRange2.clone();
712               }
713               else
714               {
715                  //         <----->
716                  //            --->
717                  intersection = new Range<T>()
718                        .setStart(inRange2.getStart());
719
720               }
721            }
722         }
723         else
724         {
725            if (getEnd() != null)
726            {
727               if (inRange2.getEnd() != null)
728               {
729                  //         <-----
730                  //         <---
731                  intersection = new Range<T>()
732                        .setEnd(getEnd().doubleValue() <= inRange2.getEnd().doubleValue() ? getEnd() : inRange2.getEnd());
733               }
734               else
735               {
736                  //         <-----
737                  //         <-------->
738                  intersection = clone();
739               }
740            }
741            else
742            {
743               if (inRange2.getEnd() != null)
744               {
745                  //         <----->
746                  //         <---
747                  intersection = inRange2.clone();
748               }
749               else
750               {
751                  //         <----->
752                  //         <----->
753                  intersection = clone();
754               }
755            }
756         }
757      }
758
759      return intersection;
760   }
761
762   //--------------------------------------------------------------------------
763   public boolean intersects(Range<T> inRange2)
764   {
765      boolean result = false;
766
767      if (getStart() != null)
768      {
769         if (inRange2.getStart() != null)
770         {
771            if (getEnd() != null)
772            {
773               if (inRange2.getEnd() != null)
774               {
775                  if (endValueIsExclusive())
776                  {
777                     result = getStart().doubleValue() < inRange2.getEnd().doubleValue()
778                              && getEnd().doubleValue() > inRange2.getStart().doubleValue();
779                  }
780                  else
781                  {
782                     result = getStart().doubleValue() <= inRange2.getEnd().doubleValue()
783                           && getEnd().doubleValue() >= inRange2.getStart().doubleValue();
784                  }
785               }
786               else // Range 2 extends infinitely to the right
787               {
788                  result = inRange2.getStart().doubleValue() <= getEnd().doubleValue();
789               }
790            }
791            else if (inRange2.getEnd() != null)
792            {  // Range 1 extends infinitely to the right
793               result = inRange2.getEnd().doubleValue() >= getStart().doubleValue();
794            }
795            else
796            {
797               // Both ranges extend infinitely to the right
798               result = true;
799            }
800         }
801         else // Range 2 extends infinitely to the left
802         {
803            if (inRange2.getEnd() != null)
804            {
805               if (endValueIsExclusive())
806               {
807                  result = getStart().doubleValue() < inRange2.getEnd().doubleValue();
808               }
809               else
810               {
811                  result = getStart().doubleValue() <= inRange2.getEnd().doubleValue();
812               }
813            }
814            else
815            {
816               // Range2 is infinite
817               result = true;
818            }
819         }
820      }
821      else if (inRange2.getStart() != null)
822      {
823         if (getEnd() != null)
824         {
825            if (endValueIsExclusive())
826            {
827               result = inRange2.getStart().doubleValue() < getEnd().doubleValue();
828            }
829            else
830            {
831               result = inRange2.getStart().doubleValue() <= getEnd().doubleValue();
832            }
833         }
834         else
835         {
836            result = true;
837         }
838      }
839      else
840      {
841         // Both ranges extend infinitely to the left
842         result = true;
843      }
844
845      return result;
846   }
847
848   //--------------------------------------------------------------------------
849   public void swapStartEndValues()
850   {
851      T tmp = getEnd();
852      setEnd(getStart());
853      setStart(tmp);
854   }
855}