Package org.apache.calcite.util

Class EquivalenceSet<E extends Comparable<E>>

java.lang.Object
org.apache.calcite.util.EquivalenceSet<E>
Type Parameters:
E - Element type
public class EquivalenceSet<E extends Comparable<E>> extends Object
Set of elements organized into equivalence classes.

Elements are equivalent by the rules of a mathematical equivalence relation:

Reflexive
Every element e is equivalent to itself
Symmetric
If e is equivalent to f, then f is equivalent to e
Transitive
If e is equivalent to f, and f is equivalent to g, then e is equivalent to g

For any given pair of elements, answers in O(log N) (two hash-table lookups) whether they are equivalent to each other.

  • Constructor Summary

    Constructors
    Constructor
    Description
    EquivalenceSet()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    E
    add(E e)
    Adds an element, and returns the element (which is its own parent).
    boolean
    areEquivalent(E e, E f)
    Returns whether two elements are in the same equivalence class.
    int
    classCount()
    Returns the number of equivalence classes in this equivalence set.
    void
    clear()
    Removes all elements in this equivalence set.
    E
    equiv(E e, E f)
    Marks two elements as equivalent.
    NavigableMap<E,SortedSet<E>>
    map()
    Returns a map of the canonical element in each equivalence class to the set of elements in that class.
    int
    size()
    Returns the number of elements in this equivalence set.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • EquivalenceSet

      public EquivalenceSet()

  • Method Details

    • add

      public E add(E e)
      Adds an element, and returns the element (which is its own parent). If already present, returns the element's parent.

    • equiv

      public E equiv(E e, E f)
      Marks two elements as equivalent. They may or may not be registered, and they may or may not be equal.

    • areEquivalent

      public boolean areEquivalent(E e, E f)
      Returns whether two elements are in the same equivalence class. Returns false if either or both of the elements are not registered.

    • map

      public NavigableMap<E,SortedSet<E>> map()
      Returns a map of the canonical element in each equivalence class to the set of elements in that class. The keys are sorted in natural order, as are the elements within each key.

    • clear

      public void clear()
      Removes all elements in this equivalence set.

    • size

      public int size()
      Returns the number of elements in this equivalence set.

    • classCount

      public int classCount()
      Returns the number of equivalence classes in this equivalence set.