# Range.java

    /*
    ** Module   : Range.java
    ** Abstract : Range of Long numbers.
    **
    ** Copyright (c) 2004-2017, Golden Code Development Corporation.
    **
    ** -#- -I- --Date-- -T- --JPRM-- ----------------Description-----------------
    ** 001 SVL 20080901 ADD   @39781 Created initial version. Basic functions
    *                                for working with ranges were implemented.
    */
    /*
    ** This program is free software: you can redistribute it and/or modify
    ** it under the terms of the GNU Affero General Public License as
    ** published by the Free Software Foundation, either version 3 of the
    ** License, or (at your option) any later version.
    **
    ** This program is distributed in the hope that it will be useful,
    ** but WITHOUT ANY WARRANTY; without even the implied warranty of
    ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    ** GNU Affero General Public License for more details.
    **
    ** You may find a copy of the GNU Affero GPL version 3 at the following
    ** location: https://www.gnu.org/licenses/agpl-3.0.en.html
    **
    ** Additional terms under GNU Affero GPL version 3 section 7:
    **
    **   Under Section 7 of the GNU Affero GPL version 3, the following additional
    **   terms apply to the works covered under the License.  These additional terms
    **   are non-permissive additional terms allowed under Section 7 of the GNU
    **   Affero GPL version 3 and may not be removed by you.
    **
    **   0. Attribution Requirement.
    **
    **     You must preserve all legal notices or author attributions in the covered
    **     work or Appropriate Legal Notices displayed by works containing the covered
    **     work.  You may not remove from the covered work any author or developer
    **     credit already included within the covered work.
    **
    **   1. No License To Use Trademarks.
    **
    **     This license does not grant any license or rights to use the trademarks
    **     Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
    **     of Golden Code Development Corporation. You are not authorized to use the
    **     name Golden Code, FWD, or the names of any author or contributor, for
    **     publicity purposes without written authorization.
    **
    **   2. No Misrepresentation of Affiliation.
    **
    **     You may not represent yourself as Golden Code Development Corporation or FWD.
    **
    **     You may not represent yourself for publicity purposes as associated with
    **     Golden Code Development Corporation, FWD, or any author or contributor to
    **     the covered work, without written authorization.
    **
    **   3. No Misrepresentation of Source or Origin.
    **
    **     You may not represent the covered work as solely your work.  All modified
    **     versions of the covered work must be marked in a reasonable way to make it
    **     clear that the modified work is not originating from Golden Code Development
    **     Corporation or FWD.  All modified versions must contain the notices of
    **     attribution required in this license.
    */

    package com.goldencode.p2j.persist.id;

    import java.util.*;

    /**
     * Represents a range of <code>Long</code> numbers between a lower bound
     * and an upper bound (inclusive).
     */
    public class Range
    implements Comparable
    {
       /** Lower bound of range. null if the range is empty. */
       private Long lowerBound;

       /** Upper bound of range. May be the same as lower bound. */
       private Long upperBound;

       /**
        * Creates an empty range.
        */
       public Range()
       {
          this.lowerBound = null;
          this.upperBound = null;
       }

       /**
        * Creates a new range object.
        *
        * @param lowerBound
        *        Lower bound of range.
        * @param upperBound
        *        Upper bound of range.
        */
       public Range(long lowerBound, long upperBound)
       {
          setBounds(lowerBound, upperBound);
       }

       /**
        * Creates a new range representing a single number.
        *
        * @param number
        *        Number to represent.
        */
       public Range(long number)
       {
          setBounds(number, number);
       }

       /**
        * Get the lower bound.
        *
        * @return Lower bound.
        */
       public Long getLowerBound()
       {
          return lowerBound;
       }

       /**
        * Get the upper bound.
        *
        * @return Upper bound.
        */
       public Long getUpperBound()
       {
          return upperBound;
       }

       /**
        * Return the quantity of numbers in range. More formally,
        * upper bound - lower bound + 1.
        *
        * @return The quantity of numbers in range.
        */
       public Long getRangeSize()
       {
          if (lowerBound == null)
          {
             return 0L;
          }
          else
          {
             return upperBound - lowerBound + 1;
          }
       }

       /**
        * Sets lower and upper bound of range.
        *
        * @param lowerBound
        *        Lower bound of range.
        * @param upperBound
        *        Upper bound of range.
        */
       public void setBounds(long lowerBound, long upperBound)
       {
          if (upperBound < lowerBound)
          {
             throw new IllegalArgumentException(
                "Upper bound should be more or equal lower bound");
          }

          this.lowerBound = lowerBound;
          this.upperBound = upperBound;
       }

       /**
        * Determines whether this range is empty (contains no numbers).
        *
        * @return <code>true</code> if this range contain an least one number.
        *         <code>false</code> otherwise.
        */
       public boolean isEmpty()
       {
          return lowerBound == null;
       }

       /**
        * Makes this range empty.
        */
       public void makeEmpty()
       {
          lowerBound = null;
          upperBound = null;
       }

       /**
        * Returns <code>true</code> if the specified number is contained in the
        * range.
        *
        * @param  number
        *         Number to be checked for containment in this range.
        * @return <code>true</code> if the specified number is contained in the
        *         range.
        */
       public boolean contains(long number)
       {
          return !isEmpty() && lowerBound <= number && number <= upperBound;
       }

       /**
        * Returns the fisrt number in range AND removes it from range.
        *
        * @return The first number in range, or <code>null</code> if the range
        *         contatins no numbers.
        */
       public Long extractFirstNumber()
       {
          if (lowerBound == null)
          {
             return null;
          }

          long num = lowerBound;
          if (lowerBound + 1 > upperBound)
          {
             lowerBound = null;
          }
          else
          {
             lowerBound++;
          }

          return num;
       }

       /**
        * Splits the range into several ranges using the given numbers as break
        * points. The numbers itself are excluded from resulting ranges. E.g
        * [1, 10] using {2,3,6,10} would be splitted into [1], [4,5], [7,9]
        *
        * @param  numbers
        *         Break points for splitting.
        * @return List of subranges.
        */
       public List<Range> splitRange(SortedSet<Long> numbers)
       {
          List<Long> list = new ArrayList<Long>(numbers);
          return splitRange(list);
       }

       /**
        * Splits the range into several ranges using the given numbers as break
        * points. The numbers itself are excluded from resulting ranges. E.g
        * [1, 10] using {2,3,6,10} would be splitted into [1], [4,5], [7,9]
        *
        * @param  numbers
        *         Break points for splitting. Should be sorted in ascending order.
        * @return List of subranges.
        */
       public List<Range> splitRange(List<Long> numbers)
       {
          if (isEmpty())
          {
             return null;
          }

          List<Range> res = new ArrayList<Range>();
          if (numbers == null || numbers.isEmpty())
          {
             res.add(new Range(lowerBound, upperBound));
             return res;
          }

          Long firstId = numbers.get(0);
          if (lowerBound < firstId)
          {
             res.add(new Range(lowerBound, firstId - 1));
          }

          Long id1 = firstId;
          Long id2;

          for (int i = 1; i < numbers.size(); i++)
          {
             id2 = id1;
             id1 = numbers.get(i);

             if (id1 - id2 > 1)
             {
                res.add(new Range(id2 + 1, id1 - 1));
             }
          }

          Long lastId = numbers.get(numbers.size() - 1);
          if (lastId < upperBound)
          {
             res.add(new Range(lastId + 1, upperBound));
          }

          return res;
       }

       /**
        * Return string representation of the range.
        *
        * @return String representation of the range.
        */
       public String toString()
       {
          if (lowerBound == null)
          {
             return "<empty>";
          }
          else if (lowerBound.equals(upperBound))
          {
             return Long.toString(lowerBound);
          }
          else
          {
             StringBuilder buf = new StringBuilder();
             buf.append("[");
             buf.append(lowerBound);
             buf.append(", ");
             buf.append(upperBound);
             buf.append("]");
             return buf.toString();
          }
       }

       /**
        * Compares this object with the specified object for order.  Returns a
        * negative integer, zero, or a positive integer as this object is less
        * than, equal to, or greater than the specified object.
        *
        * @param   o
        *          The object to be compared.
        * @return  A negative integer, zero, or a positive integer as this object
        *		      is less than, equal to, or greater than the specified object.
        */
       public int compareTo(Object o)
       {
          if (o instanceof Range)
          {
             Range r = (Range) o;

             if (r.isEmpty())
             {
                return isEmpty() ? 0 : 1;
             }
             else if (isEmpty())
             {
                return -1;
             }
             else
             {
                if (getLowerBound().equals(r.getLowerBound()))
                {
                   return getRangeSize().compareTo(r.getRangeSize());
                }
                else
                {
                   return getLowerBound().compareTo(r.getLowerBound());
                }
             }
          }
          else
          {
             return 1;
          }
       }

       /**
        * Main function for testing purposes.
        *
        * @param args
        *        Not used.
        */
       public static void main(String[] args)
       {
          Range r1;
          Range r2;

          r1 = new Range(1,2);
          r2 = new Range(3,4);
          System.out.println(r1.compareTo(r2));
          System.out.println(r2.compareTo(r1));

          r1 = new Range(1,2);
          r2 = new Range(2,4);
          System.out.println(r1.compareTo(r2));
          System.out.println(r2.compareTo(r1));

          r1 = new Range(1,2);
          r2 = new Range(2);
          System.out.println(r1.compareTo(r2));
          System.out.println(r2.compareTo(r1));

          r1 = new Range(1,2);
          r2 = new Range(1);
          System.out.println(r1.compareTo(r2));
          System.out.println(r2.compareTo(r1));

          r1 = new Range(1,2);
          r2 = new Range(1,2);
          System.out.println(r1.compareTo(r2));
          System.out.println(r2.compareTo(r1));

          r1 = new Range(1);
          r1.extractFirstNumber();
          r2 = new Range(1);
          System.out.println(r1.compareTo(r2));
          System.out.println(r2.compareTo(r1));

          r1 = new Range(1);
          r1.extractFirstNumber();
          r2 = new Range(1);
          r2.extractFirstNumber();
          System.out.println(r1.compareTo(r2));
          System.out.println(r2.compareTo(r1));

          Long l = 10L;

          r1 = new Range(10, 12);
          System.out.println(r1.compareTo(l));

          r1 = new Range(8, 9);
          System.out.println(r1.compareTo(l));

          r1 = new Range(11, 12);
          System.out.println(r1.compareTo(l));

          List<Range> deque = new ArrayList<Range>();
          deque.add(new Range(3,4));
          deque.add(new Range(1,2));
          deque.add(new Range(5));
          deque.add(new Range(10,12));
          deque.add(new Range(8));
          deque.add(new Range(13,67));

          System.out.println("before");
          for(Range r: deque)
          {
             System.out.println(r);
          }

          Collections.sort(deque);

          System.out.println("after");
          for(Range r: deque)
          {
             System.out.println(r);
          }

          System.out.println("");

          SortedSet<Long> set = new TreeSet<Long>();
          set.add(2L);
          set.add(3L);
          set.add(6L);
          set.add(10L);

          List<Range> ranges = new Range(1,10).splitRange(set);
          System.out.println("splitting");
          for(Range r: ranges)
          {
             System.out.println(r);
          }
       }
    }