RuntimeSet (API documentation of hlt.language packages)
Date: 2013-01-30

hlt.language.design.backend

## Class RuntimeSet

- java.lang.Object
- - hlt.language.design.backend.RuntimeSet

- All Implemented Interfaces:
    Container, Indexable, IndexableContainer, Iteratable, Lockable, RuntimeObject
  Direct Known Subclasses:
    IntSet, ObjectSet, RealSet

      public abstract class RuntimeSet
      extends java.lang.Object
      implements RuntimeObject, IndexableContainer

  This is the mother of all runtime representations for sets. There are three subclasses:
  - `IntSet`
  - `RealSet`
  - `ObjectSet`
  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 `int`s (i.e. `IntToIntMap`, `DoubleToIntMap`, or `ObjectToIntMap`). The inverse map (from `int`s to `Object`, `int`s, or `double`s) 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).

  There are situations when it may 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 user-controlled iteration through a set - such as `first()`, `next()`, `last()`, `previous()`, etc., ..., as opposed to implicit iteration provided by the built-in iterators. Such an order on the elements 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 consistent 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 it is not clear what the resulting set's indexing will be. For the sake of predictable behavior, we remove such ambiguities adopting the following rule:

  `all binary set operations will preserve the left operand's order and reassign an index to the elements from the right set operand in the left set operand as per whether it is added or removed from it.`

  For example, the set order we get from the above union example is `{3/1, 4/2, 2/3, 1/4, 5/5}`.

- - ### Constructor Summary

    Constructors
    Constructor and Description
    `RuntimeSet()`

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `RuntimeSet` | `add(double element)` If this set is not locked, adds the specified element to this set if it does not already belong to this set, and returns this set.
    `RuntimeSet` | `add(int element)` If this set is not locked, adds the specified element to this set if it does not already belong to this set, and returns this set.
    `RuntimeSet` | `add(java.lang.Object element)` If this set is not locked, adds the specified element to this set if it does not already belong to this set, and returns this set.
    `abstract boolean` | `contains(RuntimeSet set)` Returns `true` iff the specified set is a subset of this set.
    `abstract RuntimeSet` | `copy()` Returns a copy of this set.
    `abstract boolean` | `equals(java.lang.Object object, int[] permutation)` 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.
    `RuntimeSet` | `exclusion(RuntimeSet set)` Returns this set modified to contain the symmetric difference of this and the specified set.
    `static RuntimeSet` | `exclusion(RuntimeSet set1, RuntimeSet set2)` Returns a new set equal to the symmetric difference of the two specified sets.
    `abstract int` | `firstInt()` Returns the first element of this set as an int.
    `abstract java.lang.Object` | `firstObject()` Returns the first element of this set as an object.
    `abstract double` | `firstReal()` Returns the first element of this set as a double.
    `int` | `hashCode()` Returns a hash code for this set.
    `RuntimeSet` | `intersection(RuntimeSet set)` Returns this set modified to contain the intersection of this and the specified set.
    `static RuntimeSet` | `intersection(RuntimeSet set1, RuntimeSet set2)` Returns a new set equal to the intersection of the two specified sets.
    `boolean` | `isEmpty()` Returns `true` iff this set is empty.
    `boolean` | `isLocked()` Returns `true` iff this set is locked.
    `abstract int` | `lastInt()` Returns the last element of this set as an int.
    `abstract java.lang.Object` | `lastObject()` Returns the last element of this set as an object.
    `abstract double` | `lastReal()` Returns the last element of this set as a double.
    `void` | `lock()` Locks this set to prevent any further modification.
    `RuntimeSet` | `minus(RuntimeSet set)` Returns this set modified to contain the set difference of this and the specified set.
    `static RuntimeSet` | `minus(RuntimeSet set1, RuntimeSet set2)` Returns a new set equal to the set difference of the two specified sets.
    `abstract double` | `next(double element)` Returns the element following the given one in this set, as a double.
    `abstract int` | `next(int element)` Returns the element following the given one in this set, as an int.
    `abstract java.lang.Object` | `next(java.lang.Object element)` Returns the element following the given one in this set, as an object.
    `abstract double` | `nextc(double element)` Returns the element following the given one in this set, as a double, wrapping back to the beginning if necessary.
    `abstract int` | `nextc(int element)` Returns the element following the given one in this set, as an int, wrapping back to the beginning if necessary.
    `abstract java.lang.Object` | `nextc(java.lang.Object element)` Returns the element following the given one in this set, as an object, wrapping back to the beginning if necessary.
    `abstract int` | `ord(double element)` Returns the position of given double if it is an element of this set.
    `abstract int` | `ord(int element)` Returns the position of given int if it is an element of this set.
    `abstract int` | `ord(java.lang.Object element)` Returns the position of given object if it is an element of this set.
    `abstract double` | `prev(double element)` Returns the element preceding the given one in this set, as a double.
    `abstract int` | `prev(int element)` Returns the element preceding the given one in this set, as an int.
    `abstract java.lang.Object` | `prev(java.lang.Object element)` Returns the element preceding the given one in this set, as an object.
    `abstract double` | `prevc(double element)` Returns the element preceding the given one in this set, as a double, wrapping to last element if necessary.
    `abstract int` | `prevc(int element)` Returns the element preceding the given one in this set, as an int, wrapping to last element if necessary.
    `abstract java.lang.Object` | `prevc(java.lang.Object element)` Returns the element preceding the given one in this set, as an object, wrapping to last element if necessary.
    `RuntimeSet` | `remove(double element)` If this set is not locked, removes the specified element from this set and returns this set.
    `RuntimeSet` | `remove(int element)` If this set is not locked, removes the specified element from this set and returns this set.
    `RuntimeSet` | `remove(java.lang.Object element)` If this set is not locked, removes the specified element from this set and returns this set.
    `int` | `size()` Returns the number of elements in this set.
    `RuntimeSet` | `union(RuntimeSet set)` Returns this set modified to contain the union of this and the specified set.
    `static RuntimeSet` | `union(RuntimeSet set1, RuntimeSet set2)` Returns a new set equal to the union of the two specified sets.
    `void` | `unlock()` Unlocks this set to enable further modification.

    - ### Methods inherited from class java.lang.Object

      `equals, getClass, notify, notifyAll, toString, wait, wait, wait`

    - ### Methods inherited from interface hlt.language.design.backend.Indexable

      `getIndex, getIndex, getIndex, indexIterator`

    - ### Methods inherited from interface hlt.language.design.backend.Iteratable

      `backwardIntIterator, backwardIterator, backwardRealIterator, intIterator, intIterator, iterator, iterator, realIterator, realIterator`

    - ### Methods inherited from interface hlt.language.design.backend.Container

      `contains, contains, contains`

- - ### Constructor Detail

    - #### RuntimeSet

          public RuntimeSet()

  - ### Method Detail

    - #### lock

          public final void lock()

      Locks this set to prevent any further modification.
      Specified by:
        `lock` in interface `Lockable`

    - #### unlock

          public final void unlock()

      Unlocks this set to enable further modification.
      Specified by:
        `unlock` in interface `Lockable`

    - #### isLocked

          public final boolean isLocked()

      Returns `true` iff this set is locked.
      Specified by:
        `isLocked` in interface `Lockable`

    - #### size

          public final int size()

      Returns the number of elements in this set.
      Specified by:
        `size` in interface `Indexable`

    - #### isEmpty

          public final boolean isEmpty()

      Returns `true` iff this set is empty.
      Specified by:
        `isEmpty` in interface `Container`

    - #### hashCode

          public final int hashCode()

      Returns a hash code for this set.
      Overrides:
        `hashCode` in class `java.lang.Object`

    - #### equals

          public abstract boolean equals(java.lang.Object object,
                       int[] permutation)

      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.
      Specified by:
        `equals` in interface `Indexable`

    - #### firstInt

          public abstract int firstInt()
                                throws NoSuchElementException

      Returns the first element of this set as an int. If there is no such element, throws a `NoSuchElementException`.
      Throws:
        `NoSuchElementException`

    - #### firstReal

          public abstract double firstReal()
                                    throws NoSuchElementException

      Returns the first element of this set as a double. If there is no such element, throws a `NoSuchElementException`.
      Throws:
        `NoSuchElementException`

    - #### firstObject

          public abstract java.lang.Object firstObject()
                                                throws NoSuchElementException

      Returns the first element of this set as an object. If there is no such element, throws a `NoSuchElementException`.
      Throws:
        `NoSuchElementException`

    - #### lastInt

          public abstract int lastInt()
                               throws NoSuchElementException

      Returns the last element of this set as an int. If there is no such element, throws a `NoSuchElementException`.
      Throws:
        `NoSuchElementException`

    - #### lastReal

          public abstract double lastReal()
                                   throws NoSuchElementException

      Returns the last element of this set as a double. If there is no such element, throws a `NoSuchElementException`.
      Throws:
        `NoSuchElementException`

    - #### lastObject

          public abstract java.lang.Object lastObject()
                                               throws NoSuchElementException

      Returns the last element of this set as an object. If there is no such element, throws a `NoSuchElementException`.
      Throws:
        `NoSuchElementException`

    - #### ord

          public abstract int ord(int element)
                           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`.
      Throws:
        `NoSuchElementException`

    - #### ord

          public abstract int ord(double 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`.
      Throws:
        `NoSuchElementException`

    - #### ord

          public abstract int ord(java.lang.Object 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`.
      Throws:
        `NoSuchElementException`

    - #### next

          public abstract int next(int 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`.
      Throws:
        `NoSuchElementException`

    - #### next

          public abstract double next(double 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`.
      Throws:
        `NoSuchElementException`

    - #### next

          public abstract java.lang.Object next(java.lang.Object 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`.
      Throws:
        `NoSuchElementException`

    - #### prev

          public abstract int prev(int 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`.
      Throws:
        `NoSuchElementException`

    - #### prev

          public abstract double prev(double 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`.
      Throws:
        `NoSuchElementException`

    - #### prev

          public abstract java.lang.Object prev(java.lang.Object 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`.
      Throws:
        `NoSuchElementException`

    - #### nextc

          public abstract int nextc(int 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`.
      Throws:
        `NoSuchElementException`

    - #### nextc

          public abstract double nextc(double 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`.
      Throws:
        `NoSuchElementException`

    - #### nextc

          public abstract java.lang.Object nextc(java.lang.Object 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`.
      Throws:
        `NoSuchElementException`

    - #### prevc

          public abstract int prevc(int 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`.
      Throws:
        `NoSuchElementException`

    - #### prevc

          public abstract double prevc(double 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`.
      Throws:
        `NoSuchElementException`

    - #### prevc

          public abstract java.lang.Object prevc(java.lang.Object 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`.
      Throws:
        `NoSuchElementException`

    - #### union

          public final RuntimeSet union(RuntimeSet set)
                                 throws LockViolationException

      Returns this set modified to contain the union of this and the specified set. If this set is locked, a `LockViolationException` is thrown.
      Throws:
        `LockViolationException`

    - #### intersection

          public final RuntimeSet intersection(RuntimeSet set)
                                        throws LockViolationException

      Returns this set modified to contain the intersection of this and the specified set. If this set is locked, a `LockViolationException` is thrown.
      Throws:
        `LockViolationException`

    - #### minus

          public final RuntimeSet minus(RuntimeSet set)
                                 throws LockViolationException

      Returns this set modified to contain the set difference of this and the specified set. If this set is locked, a `LockViolationException` is thrown.
      Throws:
        `LockViolationException`

    - #### exclusion

          public final RuntimeSet exclusion(RuntimeSet set)
                                     throws LockViolationException

      Returns this set modified to contain the symmetric difference of this and the specified set. If this set is locked, a `LockViolationException` is thrown.
      Throws:
        `LockViolationException`

    - #### union

          public static final RuntimeSet union(RuntimeSet set1,
                         RuntimeSet set2)

      Returns a new set equal to the union of the two specified sets.

    - #### intersection

          public static final RuntimeSet intersection(RuntimeSet set1,
                                RuntimeSet set2)

      Returns a new set equal to the intersection of the two specified sets.

    - #### minus

          public static final RuntimeSet minus(RuntimeSet set1,
                         RuntimeSet set2)

      Returns a new set equal to the set difference of the two specified sets.

    - #### exclusion

          public static final RuntimeSet exclusion(RuntimeSet set1,
                             RuntimeSet set2)

      Returns a new set equal to the symmetric difference of the two specified sets.

    - #### copy

          public abstract RuntimeSet copy()

      Returns a copy of this set.

    - #### contains

          public abstract boolean contains(RuntimeSet set)

      Returns `true` iff the specified set is a subset of this set.

    - #### add

          public final RuntimeSet add(int element)
                               throws LockViolationException

      If this set is not locked, adds the specified element to this set if it does not already belong to this set, and returns this set. If this set is locked, a `LockViolationException` is thrown.
      Throws:
        `LockViolationException`

    - #### add

          public final RuntimeSet add(double element)
                               throws LockViolationException

      If this set is not locked, adds the specified element to this set if it does not already belong to this set, and returns this set. If this set is locked, a `LockViolationException` is thrown.
      Throws:
        `LockViolationException`

    - #### add

          public final RuntimeSet add(java.lang.Object element)
                               throws LockViolationException

      If this set is not locked, adds the specified element to this set if it does not already belong to this set, and returns this set. If this set is locked, a `LockViolationException` is thrown.
      Throws:
        `LockViolationException`

    - #### remove

          public final RuntimeSet remove(int element)
                                  throws LockViolationException

      If this set is not locked, removes the specified element from this set and returns this set. If this set is locked, a `LockViolationException` is thrown.
      Throws:
        `LockViolationException`

    - #### remove

          public final RuntimeSet remove(double element)
                                  throws LockViolationException

      If this set is not locked, removes the specified element from this set and returns this set. If this set is locked, a `LockViolationException` is thrown.
      Throws:
        `LockViolationException`

    - #### remove

          public final RuntimeSet remove(java.lang.Object element)
                                  throws LockViolationException

      If this set is not locked, removes the specified element from this set and returns this set. If this set is locked, a `LockViolationException` is thrown.
      Throws:
        `LockViolationException`