com.tivoli.twg.libs
Class IntValueSet

java.lang.Object
  extended bycom.tivoli.twg.libs.IntValueSet
All Implemented Interfaces:
java.io.Serializable

public class IntValueSet
extends java.lang.Object
implements java.io.Serializable

Container for a set of integer values. This set is optimized for searches and various set operations, including intersection, union, difference, etc. The set is also internally sorted, and allows access to this sorted array. The class also supports optimized bulk insertion of values (which should be used instead of large numbers of single inserts).

See Also:
Serialized Form

Field Summary
static long serialVersionUID
           
 
Constructor Summary
IntValueSet()
          Construtor for creating an initially empty set.
IntValueSet(int init_size)
          Constructor for creating an empty set with a given initial space allocation.
IntValueSet(int[] init_values, int start_index, int length)
          Constructor for creating a set initialized with a given range within an array of integers.
IntValueSet(IntValueSet init_set)
          Constructor for creating a set initialized by another set
IntValueSet(LongValueSet init_set)
          Constructor for creating a set initialized by a LongValueSet
 
Method Summary
 int[] AccessValues()
          Access internal array containing values in set (read-only)
 boolean contains(IntValueSet s1)
          Test if all members of a given set are contained in this set.
 boolean containsValue(int val)
          Test if value is contained in this set.
static IntValueSet Difference(IntValueSet s1, IntValueSet s2)
          Return IntValueSet equal to difference of set s1 from s2.
static int DifferenceOfArrayFromArray(int[] a1, int a1_start, int a1_len, int[] a2, int a2_start, int a2_len)
          Produce difference of two sorted integer arrays (a1-a2), and save in a1
static int[] DifferenceOfArrays(int[] a1, int a1_len, int[] a2, int a2_len)
          Produce difference of two sorted integer arrays (a1-a2)
static int[] DifferenceOfArrays(int[] a1, int a1_start, int a1_len, int[] a2, int a2_start, int a2_len)
          Produce difference of two sorted integer arrays (a1-a2)
 boolean DifferenceSet(IntValueSet s1)
          Subtract given set from set, and save result as new value for set.
static int DropDuplicates(int[] valset, int start, int length)
          Drop duplicate values in a sorted array
 boolean equals(java.lang.Object obj)
          Compare the value of the IntValueSet with another IntValueSet
 int Find(int val)
          Return index of given value in set, or -1 if not in set
static int Find(int val, int[] valset, int valset_begin, int valset_len)
          Return index of given value in sorted range of array, or -1 if not in range
 int GetValue(int n)
          Return nth element of set
 int[] GetValues()
          Return array containing copy of all values in set.
 int hashCode()
          Returns a hash code value for the object
 boolean InsertArray(int[] val, int start, int length)
          Insert an array of values into set.
 boolean InsertSet(IntValueSet insset)
          Insert IntValueSet into set.
 boolean InsertValue(int val)
          Insert a single value into the set.
static IntValueSet Intersect(IntValueSet s1, IntValueSet s2)
          Return IntValueSet equal to intersection of set s1 and s2.
static int IntersectArrayIntoArray(int[] a1, int a1_start, int a1_len, int[] a2, int a2_start, int a2_len)
          Intersect two sorted arrays, and store result in first array
static int[] IntersectArrays(int[] a1, int a1_len, int[] a2, int a2_len)
          Produce intersection of two sorted integer arrays.
static int[] IntersectArrays(int[] a1, int a1_start, int a1_len, int[] a2, int a2_start, int a2_len)
          Produce intersection of two sorted integer arrays.
 boolean IntersectSet(IntValueSet s1)
          Intersect set with given set, and save result as new value for set.
 int Length()
          Return length of set
 boolean RemoveArray(int[] val, int start, int length)
          Remove an array of values from set.
 boolean RemoveValue(int val)
          Remove value from set, if present.
 void reset()
          Empty the contents of the set.
 void setEqual(IntValueSet s1)
          Set set contents equal to given set
static void Sort(int[] valset, int start, int length)
          Sort a given array of integers, using quicksort
 void sortValues()
          Sort values, if needed.
static boolean TestIfSorted(int[] valset, int start, int length)
          Test if a range in an array is already sorted
static boolean TestIfSortedAndUnique(int[] valset, int start, int length)
          Test if a range in an array is sorted with no duplicates
 java.lang.String toString()
          String representation method (for debug)
static IntValueSet Union(IntValueSet s1, IntValueSet s2)
          Return IntValueSet equal to union of two IntValueSets
static int[] UnionArrays(int[] a1, int a1_len, int[] a2, int a2_len)
          Produce union of two sorted integer arrays.
static int[] UnionArrays(int[] a1, int a1_start, int a1_len, int[] a2, int a2_start, int a2_len)
          Produce union of two sorted integer arrays.
 void unsortedInsertValue(int val)
          Unsorted insert : quick way to add value without causing incremental sort.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

serialVersionUID

public static final long serialVersionUID
See Also:
Constant Field Values
Constructor Detail

IntValueSet

public IntValueSet()
Construtor for creating an initially empty set.


IntValueSet

public IntValueSet(int init_size)
Constructor for creating an empty set with a given initial space allocation.

Parameters:
init_size - - initial set space allocation (array size)

IntValueSet

public IntValueSet(int[] init_values,
                   int start_index,
                   int length)
Constructor for creating a set initialized with a given range within an array of integers.

Parameters:
init_values - - array containing initial values
start_index - - index of start of values in array
length - - number of values

IntValueSet

public IntValueSet(IntValueSet init_set)
Constructor for creating a set initialized by another set

Parameters:
init_set - - set to use for initialization

IntValueSet

public IntValueSet(LongValueSet init_set)
Constructor for creating a set initialized by a LongValueSet

Parameters:
init_set - - set to use for initialization
Method Detail

InsertValue

public boolean InsertValue(int val)
Insert a single value into the set. Use InsertArray() for inserting multiple values.

Parameters:
val - - value to be inserted
Returns:
true if set modified, false if not changed

unsortedInsertValue

public void unsortedInsertValue(int val)
Unsorted insert : quick way to add value without causing incremental sort. No other method calls should be made (other than additional unsortedInsertValue() calls) until sortValues() is called.

Parameters:
val - - value to be inserted

sortValues

public void sortValues()
Sort values, if needed. Only necessary if values inserted using unsortedInsertValue().


InsertArray

public boolean InsertArray(int[] val,
                           int start,
                           int length)
Insert an array of values into set.

Parameters:
val - - array of values
start - - index of start of range of values
length - - length of range of values to be inserted
Returns:
true if set modified, false if not changed

InsertSet

public boolean InsertSet(IntValueSet insset)
Insert IntValueSet into set.

Parameters:
insset - - IntValueSet to be inserted
Returns:
true if set modified, false if not changed

RemoveValue

public boolean RemoveValue(int val)
Remove value from set, if present. Use RemoveArray() for removing multiple values.

Parameters:
val - - value to be removed
Returns:
true if set modified, false if not changed

RemoveArray

public boolean RemoveArray(int[] val,
                           int start,
                           int length)
Remove an array of values from set.

Parameters:
val - - array of values
start - - index of start of range of values
length - - length of range of values to be removed
Returns:
true if set modified, false if not changed

Union

public static IntValueSet Union(IntValueSet s1,
                                IntValueSet s2)
Return IntValueSet equal to union of two IntValueSets

Parameters:
s1 - - first IntValueSet
s2 - - second IntValueSet
Returns:
IntValueSet equal to union(s1, s2)

IntersectSet

public boolean IntersectSet(IntValueSet s1)
Intersect set with given set, and save result as new value for set. (this = intersect(this, s1))

Parameters:
s1 - - set to be intersected with
Returns:
true if set modified, false if not changed

Intersect

public static IntValueSet Intersect(IntValueSet s1,
                                    IntValueSet s2)
Return IntValueSet equal to intersection of set s1 and s2.

Parameters:
s1 - - first IntValueSet
s2 - - second IntValueSet
Returns:
IntValueSet equal to intersect(s1, s2)

DifferenceSet

public boolean DifferenceSet(IntValueSet s1)
Subtract given set from set, and save result as new value for set. (this = difference(this, s1))

Parameters:
s1 - - set to be subtracted
Returns:
true if set modified, false if not changed

Difference

public static IntValueSet Difference(IntValueSet s1,
                                     IntValueSet s2)
Return IntValueSet equal to difference of set s1 from s2.

Parameters:
s1 - - first IntValueSet
s2 - - second IntValueSet
Returns:
IntValueSet equal to difference(s1, s2)

Find

public final int Find(int val)
Return index of given value in set, or -1 if not in set

Parameters:
val - - value to be found in set

Find

public static final int Find(int val,
                             int[] valset,
                             int valset_begin,
                             int valset_len)
Return index of given value in sorted range of array, or -1 if not in range

Parameters:
val - - value to be found in set
valset - - array containing sorted values to be searched
valset_begin - - beginning of range in valset
valset_len - - length of range in valset

Length

public final int Length()
Return length of set

Returns:
number of elements in set

GetValue

public final int GetValue(int n)
                   throws java.lang.ArrayIndexOutOfBoundsException
Return nth element of set

Parameters:
n - - index (base 0) of element to be returned
Throws:
java.lang.ArrayIndexOutOfBoundsException - if invalid index

GetValues

public final int[] GetValues()
Return array containing copy of all values in set.

Returns:
allocated array containing all values in set

AccessValues

public final int[] AccessValues()
Access internal array containing values in set (read-only)

Returns:
reference to internal array for set (may be longer than actual amount of data : use Length() to find actual length

Sort

public static final void Sort(int[] valset,
                              int start,
                              int length)
Sort a given array of integers, using quicksort

Parameters:
valset - - Array to be sorted
start - - index of start of data to be sorted
length - - length of data to be sorted

TestIfSorted

public static final boolean TestIfSorted(int[] valset,
                                         int start,
                                         int length)
Test if a range in an array is already sorted

Parameters:
valset - - array containing values
start - - start of range to test
length - - length of range to test
Returns:
true if already sorted, false if not

TestIfSortedAndUnique

public static final boolean TestIfSortedAndUnique(int[] valset,
                                                  int start,
                                                  int length)
Test if a range in an array is sorted with no duplicates

Parameters:
valset - - array containing values
start - - start of range to test
length - - length of range to test
Returns:
true if sorted and contains no duplicates, false if not

UnionArrays

public static final int[] UnionArrays(int[] a1,
                                      int a1_len,
                                      int[] a2,
                                      int a2_len)
Produce union of two sorted integer arrays.

Parameters:
a1 - - first sorted array
a1_len - - length of valid elements in first array
a2 - - second sorted array
a2_len - - length of valid elements in second array
Returns:
array containing union of two arrays

UnionArrays

public static final int[] UnionArrays(int[] a1,
                                      int a1_start,
                                      int a1_len,
                                      int[] a2,
                                      int a2_start,
                                      int a2_len)
Produce union of two sorted integer arrays.

Parameters:
a1 - - first sorted array
a1_start - - index of start of sorted array
a1_len - - length of valid elements in first array
a2 - - second sorted array
a2_start - - index of start of sorted array
a2_len - - length of valid elements in second array
Returns:
array containing union of two arrays

IntersectArrays

public static final int[] IntersectArrays(int[] a1,
                                          int a1_len,
                                          int[] a2,
                                          int a2_len)
Produce intersection of two sorted integer arrays.

Parameters:
a1 - - first sorted array
a1_len - - length of valid elements in first array
a2 - - second sorted array
a2_len - - length of valid elements in second array
Returns:
array containing intersection of two arrays

IntersectArrays

public static final int[] IntersectArrays(int[] a1,
                                          int a1_start,
                                          int a1_len,
                                          int[] a2,
                                          int a2_start,
                                          int a2_len)
Produce intersection of two sorted integer arrays.

Parameters:
a1 - - first sorted array
a1_start - - index of start of first sorted array
a1_len - - length of valid elements in first array
a2 - - second sorted array
a2_len - - length of valid elements in second array
Returns:
array containing intersection of two arrays

IntersectArrayIntoArray

public static final int IntersectArrayIntoArray(int[] a1,
                                                int a1_start,
                                                int a1_len,
                                                int[] a2,
                                                int a2_start,
                                                int a2_len)
Intersect two sorted arrays, and store result in first array

Parameters:
a1 - - first sorted array
a1_start - - index of start of sorted data
a1_len - - length of valid elements in first array
a2 - - second sorted array
a2_start - - index of start of sorted data
a2_len - - length of valid elements in second array
Returns:
number of valid elements in intersection in a1

DifferenceOfArrays

public static final int[] DifferenceOfArrays(int[] a1,
                                             int a1_len,
                                             int[] a2,
                                             int a2_len)
Produce difference of two sorted integer arrays (a1-a2)

Parameters:
a1 - - first sorted array
a1_len - - length of valid elements in first array
a2 - - second sorted array
a2_len - - length of valid elements in second array
Returns:
array containing difference of two arrays

DifferenceOfArrays

public static final int[] DifferenceOfArrays(int[] a1,
                                             int a1_start,
                                             int a1_len,
                                             int[] a2,
                                             int a2_start,
                                             int a2_len)
Produce difference of two sorted integer arrays (a1-a2)

Parameters:
a1 - - first sorted array
a1_start - - start of valid elements in first array
a1_len - - length of valid elements in first array
a2 - - second sorted array
a2_start - - start of valid elements in second array
a2_len - - length of valid elements in second array
Returns:
array containing difference of two arrays

DifferenceOfArrayFromArray

public static final int DifferenceOfArrayFromArray(int[] a1,
                                                   int a1_start,
                                                   int a1_len,
                                                   int[] a2,
                                                   int a2_start,
                                                   int a2_len)
Produce difference of two sorted integer arrays (a1-a2), and save in a1

Parameters:
a1 - - first sorted array
a1_start - - start of valid elements in first array
a1_len - - length of valid elements in first array
a2 - - second sorted array
a2_start - - start of valid elements in second array
a2_len - - length of valid elements in second array
Returns:
number of valid elements in a1

DropDuplicates

public static final int DropDuplicates(int[] valset,
                                       int start,
                                       int length)
Drop duplicate values in a sorted array

Parameters:
valset - - array containing sorted values
start - - index of start of sorted values
length - - length of range of sorted values
Returns:
length of range of sorted values without duplicates

hashCode

public int hashCode()
Returns a hash code value for the object

Returns:
hash code value for this object

equals

public boolean equals(java.lang.Object obj)
Compare the value of the IntValueSet with another IntValueSet

Parameters:
obj - - object to be compared with
Returns:
true if sets are equal, false if not

contains

public boolean contains(IntValueSet s1)
Test if all members of a given set are contained in this set.

Parameters:
s1 - - set to be checked
Returns:
true if this set contains all members of s1

containsValue

public boolean containsValue(int val)
Test if value is contained in this set.

Parameters:
val - - value to be checked
Returns:
true if this set contains value

reset

public void reset()
Empty the contents of the set.


setEqual

public void setEqual(IntValueSet s1)
Set set contents equal to given set

Parameters:
s1 - - set to be copied

toString

public java.lang.String toString()
String representation method (for debug)

Returns:
string representation