|
RuntimeSet.java
|
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ // PLEASE DO NOT EDIT WITHOUT THE EXPLICIT CONSENT OF THE AUTHOR! \\ //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\ package ilog.language.design.backend;
|
import ilog.language.util.ToIntMap; import ilog.language.tools.Misc; import java.util.Iterator;
|
This is the mother of all runtime representations for sets. There
are three subclasses:
which only differ in the instantiation of the element type of their
representation structures, which is common, modulo representation
variations as per of the type of elements. The common backbone
representation of a set is that of a two way bijection (i.e.,
a 1-to-1 onto map) between the elements of the set on one hand, and
the set of integers {1,...,n} of the other hand, where
n is the number of elements in the set. One way (from
elements to indices) is represented as an associative map from keys
of type instantiated for the element type to ints
(i.e. IntToIntMap, DoubleToIntMap, or
ObjectToIntMap). The inverse map (from ints to
Object, ints, or doubles) is simply a Java
array of the appropriate sort (i.e., int[],
double[], or Object[]). This "inverse map" is built
only if necessary as it is not always needed since it acts mostly as
a cache for iterations. Because sets may be dynamically altered in
situ, these two maps must be kept mutually consistent (lest gaps
in the index set appearing from deletions corrupt the 2-way
correspondence. It may also be needed to prevent a set from being
further modified. Control of such behavior is achieved through a
simple locking mechanism. Thus, an array (i.e., the map from
indices to elements) that has been built for an unlocked set prior to
the set is altered (by adding new elements or removing some - thus
possibly making "holes" in the index set) will be recomputed whenever
(and only if) this is necessary to prevent descrepancy between the
two sides of the element/index 2-way maps.
Thus our most basic representation of a Runtime Set is simply a table mapping elements to indices. These indices correspond to the order of insertion of each element into the set. Note that this representation makes sets implicitly totally ordered sets. Although this is true, this is only a programming convenience. Relying on the determinism of this feature is not a safe practice, even though the choice is predictable (since programmed using the implicit rules in the set operations defined herein). What matters, and is guaranteed, is that the pure set semantics of all set operations is always preserved. The only need for indices is to provide methods that a client class can use for iterating through a set - such as first(), next(), last(), previous(), etc., ... Such order could be any one as long as it is consistent and predictable - this is needed for debugging purposes. Indeed, even though the mathematical semantics of (unordered sets) is consistent with a non-deterministic choice of elements for performing an iteration over the set, for programming (and debugging) purposes, it is better to keep a consistent order whenever possible. In any case, the order must be predictable. Thus, whenever a predictable cosnsistent canonical order may be "naturally" derived it is used. The one we use is the order in which the set was built - i.e. order of temporal insertion of each element into the set. Such an order may not be maintained consistent through most set operations. Take, e.g., {3,4,2,1} U {1,2,4,5}. This, with explicit indices, may be written {3/1, 4/2, 2/3, 1/4} U {1/1, 2/2, 4/3, 5/4}, and thus which may the resulting set's indexing be? For the sake of predictable behavior, we remove such ambiguities adopting the following rule:
For example, the set order we get from the above union example is {3/1, 4/2, 2/3, 1/4, 5/5}. |
abstract public class RuntimeSet extends RuntimeCollection
{
| This flag is set whenever this set has "holes". A hole is a gap in the indexing sequence. |
protected boolean _hasHoles = false;
| This is the maximum index. When the set has no holes, it is equal to the size of the set. Otherwise, it is equal to the size of the set at the time the first hole appeared + the number of insertions that happened after that. |
protected int _maxIndex = 0;
| This flag is set whenever at least one hole has appeared in the indices. |
protected boolean _isLocked = false;
| Returns the underlying index map representing the set. |
abstract ToIntMap map ();
| Returns true when this set is equal (as a set) to the specified one, with a side-effect on the specified array of ints that will contain the index permutation when the sets are found to be equal. |
abstract public boolean equals (Object object, int[] permutation);
| Returns the first element of this set as an int. If there is no such element, throws a NoSuchElementException. |
abstract public int firstInt () throws NoSuchElementException;
| Returns the first element of this set as a double. If there is no such element, throws a NoSuchElementException. |
abstract public double firstReal () throws NoSuchElementException;
| Returns the first element of this set as an object. If there is no such element, throws a NoSuchElementException. |
abstract public Object firstObject () throws NoSuchElementException;
| Returns the last element of this set as an int. If there is no such element, throws a NoSuchElementException. |
abstract public int lastInt () throws NoSuchElementException;
| Returns the last element of this set as a double. If there is no such element, throws a NoSuchElementException. |
abstract public double lastReal () throws NoSuchElementException;
| Returns the last element of this set as an object. If there is no such element, throws a NoSuchElementException. |
abstract public Object lastObject () throws NoSuchElementException;
| Returns the position of given int if it is an element of this set. If there is no such element, throws a NoSuchElementException. |
abstract public int ord (int element) throws NoSuchElementException;
| Returns the position of given double if it is an element of this set. If there is no such element, throws a NoSuchElementException. |
abstract public int ord (double element) throws NoSuchElementException;
| Returns the position of given object if it is an element of this set. If there is no such element, throws a NoSuchElementException. |
abstract public int ord (Object element) throws NoSuchElementException;
| Returns the element following the given one in this set, as an int. If there is no such element, throws a NoSuchElementException. |
abstract public int next (int element) throws NoSuchElementException;
| Returns the element following the given one in this set, as a double. If there is no such element, throws a NoSuchElementException. |
abstract public double next (double element) throws NoSuchElementException;
| Returns the element following the given one in this set, as an object. If there is no such element, throws a NoSuchElementException. |
abstract public Object next (Object element) throws NoSuchElementException;
| Returns the element preceding the given one in this set, as an int. If there is no such element, throws a NoSuchElementException. |
abstract public int prev (int element) throws NoSuchElementException;
| Returns the element preceding the given one in this set, as a double. If there is no such element, throws a NoSuchElementException. |
abstract public double prev (double element) throws NoSuchElementException;
| Returns the element preceding the given one in this set, as an object. If there is no such element, throws a NoSuchElementException. |
abstract public Object prev (Object element) throws NoSuchElementException;
| Returns the element following the given one in this set, as an int, wrapping back to the beginning if necessary. If there is no such element, throws a NoSuchElementException. |
abstract public int nextc (int element) throws NoSuchElementException;
| Returns the element following the given one in this set, as a double, wrapping back to the beginning if necessary. If there is no such element, throws a NoSuchElementException. |
abstract public double nextc (double element) throws NoSuchElementException;
| Returns the element following the given one in this set, as an object, wrapping back to the beginning if necessary. If there is no such element, throws a NoSuchElementException. |
abstract public Object nextc (Object element) throws NoSuchElementException;
| Returns the element preceding the given one in this set, as an int, wrapping to last element if necessary. If there is no such element, throws a NoSuchElementException. |
abstract public int prevc (int element) throws NoSuchElementException;
| Returns the element preceding the given one in this set, as a double, wrapping to last element if necessary. If there is no such element, throws a NoSuchElementException. |
abstract public double prevc (double element) throws NoSuchElementException;
| Returns the element preceding the given one in this set, as an object, wrapping to last element if necessary. If there is no such element, throws a NoSuchElementException. |
abstract public Object prevc (Object element) throws NoSuchElementException;
| Returns true iff the specified set is a subset of this set. |
abstract public boolean contains (RuntimeSet set);
| Returns this set modified to contain the union of this and the specified set. If this set is locked, a LockViolationException is thrown. |
public final RuntimeSet union (RuntimeSet set) throws LockViolationException
{
if (_isLocked)
throw new LockViolationException();
return _union(set);
}
| Returns this set modified to contain the intersection of this and the specified set. If this set is locked, a LockViolationException is thrown. |
public final RuntimeSet intersection (RuntimeSet set) throws LockViolationException
{
if (_isLocked)
throw new LockViolationException();
return _intersection(set);
}
| Returns this set modified to contain the set difference of this and the specified set. If this set is locked, a LockViolationException is thrown. |
public final RuntimeSet minus (RuntimeSet set) throws LockViolationException
{
if (_isLocked)
throw new LockViolationException();
return _minus(set);
}
| Returns this set modified to contain the symmetric difference of this and the specified set. If this set is locked, a LockViolationException is thrown. |
public final RuntimeSet exclusion (RuntimeSet set) throws LockViolationException
{
if (_isLocked)
throw new LockViolationException();
return _exclusion(set);
}
| Returns a new set equal to the union of the two specified sets. |
public static final RuntimeSet union (RuntimeSet set1, RuntimeSet set2)
{
return set1.copy()._union(set2);
}
| Returns a new set equal to the intersection of the two specified sets. |
public static final RuntimeSet intersection (RuntimeSet set1, RuntimeSet set2)
{
return set1.copy()._intersection(set2);
}
| Returns a new set equal to the set difference of the two specified sets. |
public static final RuntimeSet minus (RuntimeSet set1, RuntimeSet set2)
{
return set1.copy()._minus(set2);
}
| Returns a new set equal to the symmetric difference of the two specified sets. |
public static final RuntimeSet exclusion (RuntimeSet set1, RuntimeSet set2)
{
return set1.copy()._exclusion(set2);
}
}
This file was generated on Tue Aug 03 09:20:39 PDT 2004 from file RuntimeSet.java
by the ilog.language.tools.Hilite Java tool written by Hassan Aït-Kaci