Package com.macrofocus.utils

Class IndexedTreeSet<E>

  • Type Parameters:
    E - the type of elements maintained by this set
    All Implemented Interfaces:
    IndexedNavigableSet<E>, java.io.Serializable, java.lang.Cloneable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.NavigableSet<E>, java.util.Set<E>, java.util.SortedSet<E>
    public class IndexedTreeSet<E>
extends java.util.AbstractSet<E>
implements IndexedNavigableSet<E>, java.lang.Cloneable, java.io.Serializable
    A NavigableSet implementation based on a IndexedTreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

    This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

    Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a IndexedTreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

    Note that this implementation is not synchronized. If multiple threads access a tree set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the set. If no such object exists, the set should be "wrapped" using the Collections.synchronizedSortedSet method. This is best done at creation time, to prevent accidental unsynchronized access to the set: 

       SortedSet s = Collections.synchronizedSortedSet(new IndexedTreeSet(...));

    The iterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

    Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

    This class is a member of the Java Collections Framework.

    Since:
    1.2
    See Also:
    Collection, Set, HashSet, Comparable, Comparator, IndexedTreeMap, Serialized Form

    • Constructor Summary

      Constructors 
      Constructor Description
      IndexedTreeSet()
      Constructs a new, empty tree set, sorted according to the natural ordering of its elements.
      IndexedTreeSet​(java.util.Collection<? extends E> c)
      Constructs a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements.
      IndexedTreeSet​(java.util.Comparator<? super E> comparator)
      Constructs a new, empty tree set, sorted according to the specified comparator.
      IndexedTreeSet​(java.util.SortedSet<E> s)
      Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(E e)
      Adds the specified element to this set if it is not already present.
      boolean addAll​(java.util.Collection<? extends E> c)
      Adds all of the elements in the specified collection to this set.
      E ceiling​(E e)  
      void clear()
      Removes all of the elements from this set.
      java.util.Comparator<? super E> comparator()  
      boolean contains​(java.lang.Object o)
      Returns true if this set contains the specified element.
      void debug()  
      java.util.Iterator<E> descendingIterator()
      Returns an iterator over the elements in this set in descending order.
      java.util.NavigableSet<E> descendingSet()  
      int entryIndex​(E e)
      Searches the specified tree map for the specified entry using the put algorithm.
      E exact​(int index)
      Returns the entry located at the index offset from the beginning of the sorted set
      E first()  
      E floor​(E e)  
      java.util.SortedSet<E> headSet​(E toElement)  
      java.util.NavigableSet<E> headSet​(E toElement, boolean inclusive)  
      E higher​(E e)  
      boolean isEmpty()
      Returns true if this set contains no elements.
      java.util.Iterator<E> iterator()
      Returns an iterator over the elements in this set in ascending order.
      E last()  
      E lower​(E e)  
      E pollFirst()  
      E pollLast()  
      boolean remove​(java.lang.Object o)
      Removes the specified element from this set if it is present.
      int size()
      Returns the number of elements in this set (its cardinality).
      java.util.NavigableSet<E> subSet​(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)  
      java.util.SortedSet<E> subSet​(E fromElement, E toElement)  
      java.util.SortedSet<E> tailSet​(E fromElement)  
      java.util.NavigableSet<E> tailSet​(E fromElement, boolean inclusive)  

      • Methods inherited from class java.util.AbstractSet

        equals, hashCode, removeAll

      • Methods inherited from class java.util.AbstractCollection

        containsAll, retainAll, toArray, toArray, toString

      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait

      • Methods inherited from interface java.util.Collection

        parallelStream, removeIf, stream, toArray

      • Methods inherited from interface java.lang.Iterable

        forEach

      • Methods inherited from interface java.util.Set

        containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray

      • Methods inherited from interface java.util.SortedSet

        spliterator

    • Constructor Detail

      • IndexedTreeSet

        public IndexedTreeSet()
        Constructs a new, empty tree set, sorted according to the natural ordering of its elements. All elements inserted into the set must implement the Comparable interface. Furthermore, all such elements must be mutually comparable: e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the set. If the user attempts to add an element to the set that violates this constraint (for example, the user attempts to add a string element to a set whose elements are integers), the add call will throw a ClassCastException.

      • IndexedTreeSet

        public IndexedTreeSet​(java.util.Comparator<? super E> comparator)
        Constructs a new, empty tree set, sorted according to the specified comparator. All elements inserted into the set must be mutually comparable by the specified comparator: comparator.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the set. If the user attempts to add an element to the set that violates this constraint, the add call will throw a ClassCastException.
        Parameters:
        comparator - the comparator that will be used to order this set. If null, the natural ordering of the elements will be used.

      • IndexedTreeSet

        public IndexedTreeSet​(java.util.Collection<? extends E> c)
        Constructs a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements. All elements inserted into the set must implement the Comparable interface. Furthermore, all such elements must be mutually comparable: e1.compareTo(e2) must not throw a ClassCastException for any elements e1 and e2 in the set.
        Parameters:
        c - collection whose elements will comprise the new set
        Throws:
        java.lang.ClassCastException - if the elements in c are not Comparable, or are not mutually comparable
        java.lang.NullPointerException - if the specified collection is null

      • IndexedTreeSet

        public IndexedTreeSet​(java.util.SortedSet<E> s)
        Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set.
        Parameters:
        s - sorted set whose elements will comprise the new set
        Throws:
        java.lang.NullPointerException - if the specified sorted set is null

    • Method Detail

      • iterator

        public java.util.Iterator<E> iterator()
        Returns an iterator over the elements in this set in ascending order.
        Specified by:
        iterator in interface java.util.Collection<E>
        Specified by:
        iterator in interface java.lang.Iterable<E>
        Specified by:
        iterator in interface java.util.NavigableSet<E>
        Specified by:
        iterator in interface java.util.Set<E>
        Specified by:
        iterator in class java.util.AbstractCollection<E>
        Returns:
        an iterator over the elements in this set in ascending order

      • descendingIterator

        public java.util.Iterator<E> descendingIterator()
        Returns an iterator over the elements in this set in descending order.
        Specified by:
        descendingIterator in interface java.util.NavigableSet<E>
        Returns:
        an iterator over the elements in this set in descending order
        Since:
        1.6

      • descendingSet

        public java.util.NavigableSet<E> descendingSet()
        Specified by:
        descendingSet in interface java.util.NavigableSet<E>
        Since:
        1.6

      • size

        public int size()
        Returns the number of elements in this set (its cardinality).
        Specified by:
        size in interface java.util.Collection<E>
        Specified by:
        size in interface java.util.Set<E>
        Specified by:
        size in class java.util.AbstractCollection<E>
        Returns:
        the number of elements in this set (its cardinality)

      • isEmpty

        public boolean isEmpty()
        Returns true if this set contains no elements.
        Specified by:
        isEmpty in interface java.util.Collection<E>
        Specified by:
        isEmpty in interface java.util.Set<E>
        Overrides:
        isEmpty in class java.util.AbstractCollection<E>
        Returns:
        true if this set contains no elements

      • contains

        public boolean contains​(java.lang.Object o)
        Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).
        Specified by:
        contains in interface java.util.Collection<E>
        Specified by:
        contains in interface java.util.Set<E>
        Overrides:
        contains in class java.util.AbstractCollection<E>
        Parameters:
        o - object to be checked for containment in this set
        Returns:
        true if this set contains the specified element
        Throws:
        java.lang.ClassCastException - if the specified object cannot be compared with the elements currently in the set
        java.lang.NullPointerException - if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements

      • add

        public boolean add​(E e)
        Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if the set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.
        Specified by:
        add in interface java.util.Collection<E>
        Specified by:
        add in interface java.util.Set<E>
        Overrides:
        add in class java.util.AbstractCollection<E>
        Parameters:
        e - element to be added to this set
        Returns:
        true if this set did not already contain the specified element
        Throws:
        java.lang.ClassCastException - if the specified object cannot be compared with the elements currently in this set
        java.lang.NullPointerException - if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements

      • remove

        public boolean remove​(java.lang.Object o)
        Removes the specified element from this set if it is present. More formally, removes an element e such that (o==null ? e==null : o.equals(e)), if this set contains such an element. Returns true if this set contained the element (or equivalently, if this set changed as a result of the call). (This set will not contain the element once the call returns.)
        Specified by:
        remove in interface java.util.Collection<E>
        Specified by:
        remove in interface java.util.Set<E>
        Overrides:
        remove in class java.util.AbstractCollection<E>
        Parameters:
        o - object to be removed from this set, if present
        Returns:
        true if this set con tained the specified element
        Throws:
        java.lang.ClassCastException - if the specified object cannot be compared with the elements currently in this set
        java.lang.NullPointerException - if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements

      • clear

        public void clear()
        Removes all of the elements from this set. The set will be empty after this call returns.
        Specified by:
        clear in interface java.util.Collection<E>
        Specified by:
        clear in interface java.util.Set<E>
        Overrides:
        clear in class java.util.AbstractCollection<E>

      • addAll

        public boolean addAll​(java.util.Collection<? extends E> c)
        Adds all of the elements in the specified collection to this set.
        Specified by:
        addAll in interface java.util.Collection<E>
        Specified by:
        addAll in interface java.util.Set<E>
        Overrides:
        addAll in class java.util.AbstractCollection<E>
        Parameters:
        c - collection containing elements to be added to this set
        Returns:
        true if this set changed as a result of the call
        Throws:
        java.lang.ClassCastException - if the elements provided cannot be compared with the elements currently in the set
        java.lang.NullPointerException - if the specified collection is null or if any element is null and this set uses natural ordering, or its comparator does not permit null elements

      • subSet

        public java.util.NavigableSet<E> subSet​(E fromElement,
                                        boolean fromInclusive,
                                        E toElement,
                                        boolean toInclusive)
        Specified by:
        subSet in interface java.util.NavigableSet<E>
        Throws:
        java.lang.ClassCastException
        java.lang.NullPointerException - if fromElement or toElement is null and this set uses natural ordering, or its comparator does not permit null elements
        java.lang.IllegalArgumentException
        Since:
        1.6

      • headSet

        public java.util.NavigableSet<E> headSet​(E toElement,
                                         boolean inclusive)
        Specified by:
        headSet in interface java.util.NavigableSet<E>
        Throws:
        java.lang.ClassCastException
        java.lang.NullPointerException - if toElement is null and this set uses natural ordering, or its comparator does not permit null elements
        java.lang.IllegalArgumentException
        Since:
        1.6

      • tailSet

        public java.util.NavigableSet<E> tailSet​(E fromElement,
                                         boolean inclusive)
        Specified by:
        tailSet in interface java.util.NavigableSet<E>
        Throws:
        java.lang.ClassCastException
        java.lang.NullPointerException - if fromElement is null and this set uses natural ordering, or its comparator does not permit null elements
        java.lang.IllegalArgumentException
        Since:
        1.6

      • subSet

        public java.util.SortedSet<E> subSet​(E fromElement,
                                     E toElement)
        Specified by:
        subSet in interface java.util.NavigableSet<E>
        Specified by:
        subSet in interface java.util.SortedSet<E>
        Throws:
        java.lang.ClassCastException
        java.lang.NullPointerException - if fromElement or toElement is null and this set uses natural ordering, or its comparator does not permit null elements
        java.lang.IllegalArgumentException

      • headSet

        public java.util.SortedSet<E> headSet​(E toElement)
        Specified by:
        headSet in interface java.util.NavigableSet<E>
        Specified by:
        headSet in interface java.util.SortedSet<E>
        Throws:
        java.lang.ClassCastException
        java.lang.NullPointerException - if toElement is null and this set uses natural ordering, or its comparator does not permit null elements
        java.lang.IllegalArgumentException

      • tailSet

        public java.util.SortedSet<E> tailSet​(E fromElement)
        Specified by:
        tailSet in interface java.util.NavigableSet<E>
        Specified by:
        tailSet in interface java.util.SortedSet<E>
        Throws:
        java.lang.ClassCastException
        java.lang.NullPointerException - if fromElement is null and this set uses natural ordering, or its comparator does not permit null elements
        java.lang.IllegalArgumentException

      • comparator

        public java.util.Comparator<? super E> comparator()
        Specified by:
        comparator in interface java.util.SortedSet<E>

      • first

        public E first()
        Specified by:
        first in interface java.util.SortedSet<E>
        Throws:
        java.util.NoSuchElementException

      • last

        public E last()
        Specified by:
        last in interface java.util.SortedSet<E>
        Throws:
        java.util.NoSuchElementException

      • lower

        public E lower​(E e)
        Specified by:
        lower in interface java.util.NavigableSet<E>
        Throws:
        java.lang.ClassCastException
        java.lang.NullPointerException - if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements
        Since:
        1.6

      • floor

        public E floor​(E e)
        Specified by:
        floor in interface java.util.NavigableSet<E>
        Throws:
        java.lang.ClassCastException
        java.lang.NullPointerException - if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements
        Since:
        1.6

      • ceiling

        public E ceiling​(E e)
        Specified by:
        ceiling in interface java.util.NavigableSet<E>
        Throws:
        java.lang.ClassCastException
        java.lang.NullPointerException - if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements
        Since:
        1.6

      • higher

        public E higher​(E e)
        Specified by:
        higher in interface java.util.NavigableSet<E>
        Throws:
        java.lang.ClassCastException
        java.lang.NullPointerException - if the specified element is null and this set uses natural ordering, or its comparator does not permit null elements
        Since:
        1.6

      • pollFirst

        public E pollFirst()
        Specified by:
        pollFirst in interface java.util.NavigableSet<E>
        Since:
        1.6

      • pollLast

        public E pollLast()
        Specified by:
        pollLast in interface java.util.NavigableSet<E>
        Since:
        1.6

      • exact

        public E exact​(int index)
        Description copied from interface: IndexedNavigableSet
        Returns the entry located at the index offset from the beginning of the sorted set
        Specified by:
        exact in interface IndexedNavigableSet<E>
        Parameters:
        index - index of the entry
        Returns:
        the entry located at the index (@code index) offset from the beginning of the sorted set

      • entryIndex

        public int entryIndex​(E e)
        Description copied from interface: IndexedNavigableSet
        Searches the specified tree map for the specified entry using the put algorithm. Calculates its offset from the beginning of the sorted map using weights.
        Specified by:
        entryIndex in interface IndexedNavigableSet<E>
        Parameters:
        e - the entry
        Returns:
        index of the searched entry, if it is contained in the tree map; otherwise a NullPointerException is thrown

      • debug

        public void debug()
           throws java.lang.Exception
        Throws:
        java.lang.Exception