Package eu.simuline.util

Class ListSet<E>

  • Type Parameters:
    E - The type of the entries.
    All Implemented Interfaces:
    java.lang.Iterable<E>, java.util.Collection<E>, java.util.Set<E>, java.util.SortedSet<E>
    public final class ListSet<E>
extends java.util.AbstractSet<E>
implements java.util.SortedSet<E>
    This class implements the Set interface, backed by a java.util.ArrayList. The iteration order of the set is the iteration order of the underlying ArrayList. This class permits the null element.

    The size, isEmpty, and iterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).

    Each ListSet instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the set size. As elements are added an ListSet, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

    Note that this implementation is not synchronized. If multiple threads access a 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.synchronizedSet method. This is best done at creation time, to prevent accidental unsynchronized access to the ListSet instance: 

    Set s = Collections.synchronizedSet(new ListSet(...));

    The iterators returned by this class's iterator method are fail-fast: if the set ismodified at any time after the iterator is created, in any way except through the iterator's own remove method, the Iterator throws 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.

    Version:
    1.0
    Author:
    Ernst Reissner
    See Also:
    Collection, List, ArrayList.add(E, java.lang.Object[], int), SortedSet, HashSet, TreeSet, AbstractSet, Collections

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.Comparator<? super E> innerCmp
      If outerCmp is not null, the two comparators coincide.
      private java.util.List<E> list
      Contains the elements of this set.
      private java.util.Comparator<? super E> outerCmp
      The comparator initialized in the constructor and returned by comparator().

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
        ListSet()
      Constructs a new, empty set, sorted according to the natural ordering of its elements.
        ListSet​(java.util.Collection<? extends E> coll)
      Creates a new set containing the elements of the specified collection in the natural ordering.
        ListSet​(java.util.Comparator<? super E> cmp)
      Constructs a new, empty set, sorted according to the specified comparator cmp.
      private ListSet​(java.util.List<E> list, java.util.Comparator<? super E> cmp)
      Creates a new ListSet with elements given by list and ordering given by cmp.
        ListSet​(java.util.SortedSet<E> sortedSet)
      Constructs a new set containing the same elements and using the same ordering as the sortedSet.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(E obj)
      Adds the specified element to this set if it is not already present.
      boolean addAll​(java.util.Collection<? extends E> coll)
      Adds all of the elements in the specified collection to this set if they're not already present.
      private boolean addList​(java.util.List<E> list1, java.util.List<E> list2)
      Merges list2 into list1 and returns whether l1 had been modified.
      void clear()
      Removes all of the elements from this set.
      java.util.Comparator<? super E> comparator()  
      boolean contains​(java.lang.Object obj)
      Returns true if this set contains the specified element.
      boolean containsAll​(java.util.Collection<?> coll)
      Returns true if this set contains all of the elements of the specified collection.
      boolean equals​(java.lang.Object obj)
      **** ask at oracle whether for sorted sets equality should include ordering. **** Compares the specified object with this set for equality.
      E first()  
      java.util.List<E> getList()
      Returns a list backing this set, so changes in the returned list are reflected in this set, and vice-versa.
      int hashCode()
      Returns the hash code value for this set.
      java.util.SortedSet<E> headSet​(E toObj)  
      boolean isEmpty()
      Returns true if this set contains no elements.
      private boolean isSortedWithSameComparator​(java.util.Collection<?> coll)
      Returns whether this set has the same comparator as the collection given.
      java.util.Iterator<E> iterator()
      Returns an iterator over the elements in this set.
      E last()  
      java.util.ListIterator<E> listIterator()
      Returns an iterator over the elements in this set.
      static void main​(java.lang.String[] args)  
      (package private) int obj2idx​(E obj)  
      boolean remove​(java.lang.Object obj)
      Removes the specified element from this set if it is present.
      boolean removeAll​(java.util.Collection<?> coll)
      Removes from this set all of its elements that are contained in the specified collection.
      boolean retainAll​(java.util.Collection<?> coll)
      Retains only the elements in this set that are contained in the specified collection.
      int size()
      Returns the number of elements in this set (its cardinality).
      static <E> ListSet<E> sortedAsAdded()
      Creates a new ListSet with ordering as added in ascending ordering.
      static <E> ListSet<E> sortedAsListed​(java.util.List<E> list)
      Returns an ListSet with elements and ordering given by list as described in Comparators.getAsListed(List).
      ListSet<E> subSet​(E fromObj, E toObj)  
      (package private) ListSet<E> subSetIdx​(int fromIdx, int toIdx)  
      java.util.SortedSet<E> tailSet​(E fromObj)  
      java.lang.Object[] toArray()
      Returns an array containing all of the elements in this set; the order is as in the backing list list.
      <T> T[] toArray​(T[] arr)
      Returns an array containing all of the elements in this set whose runtime type is that of the specified array; the order is as in the backing list list.
      java.lang.String toString()
      Returns a string representation of this set.

      • 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.SortedSet

        spliterator

    • Field Detail

      • list

        private final java.util.List<E> list
        Contains the elements of this set. By contract, list.get(a).equals(list.get(b)) implies a == b.

      • outerCmp

        private final java.util.Comparator<? super E> outerCmp
        The comparator initialized in the constructor and returned by comparator(). This may well be null and is nowhere used directly.

      • innerCmp

        private final java.util.Comparator<? super E> innerCmp
        If outerCmp is not null, the two comparators coincide. Otherwise this comparator reflects the natural ordering and throws a ClassCastException if feeded with no appropriate Comparable.

    • Constructor Detail

      • ListSet

        private ListSet​(java.util.List<E> list,
                java.util.Comparator<? super E> cmp)
        Creates a new ListSet with elements given by list and ordering given by cmp. If the latter is null then the type parameter of list must be a Comparable. and list must This is inspired by a constructor of TreeSet.
        Parameters:
        list - the list wrapped by this set. It must be ordered ascending according to cmp if this is non-null, else as Comparables. It is desireable that list contains each element once only.
        cmp - A comparator or null.

      • ListSet

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

      • ListSet

        public ListSet​(java.util.Collection<? extends E> coll)
        Creates a new set containing the elements of the specified collection in the natural ordering. 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.

        The backing ArrayList instance list has an initial capacity of 110% the size of the specified collection.

        Parameters:
        coll - the collection whose elements are to be placed into this 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.

      • ListSet

        public ListSet​(java.util.Comparator<? super E> cmp)
        Constructs a new, empty set, sorted according to the specified comparator cmp. For cmp==null a comparator defining the natural ordering is assumed.

        All elements inserted into the set must be mutually comparable by the specified comparator: cmp.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.

        Implementational note: Whereas outerCmp is initialized with cmp whether it is null or not, innerCmp is initialized with cmp only if this is not null. Otherwise, it is initialized with a comparator defining the natural ordering.

        Parameters:
        cmp - the comparator that will be used to order this set. If null, the natural ordering of the elements will be used.

      • ListSet

        public ListSet()
        Constructs a new, empty 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. For a generalization to a given comparator see ListSet(Comparator).

    • Method Detail

      • sortedAsAdded

        public static <E> ListSet<E> sortedAsAdded()
        Creates a new ListSet with ordering as added in ascending ordering.

      • sortedAsListed

        public static <E> ListSet<E> sortedAsListed​(java.util.List<E> list)
        Returns an ListSet with elements and ordering given by list as described in Comparators.getAsListed(List). If an element is added to list, the ordering is as added at the end of list. CAUTION: The list backs this set: changes in the list affect this set and the other way round. Changing the list also changes the ordering.
        Throws:
        java.lang.NullPointerException - if list is null.

      • getList

        public java.util.List<E> getList()
        Returns a list backing this set, so changes in the returned list are reflected in this set, and vice-versa.

      • size

        public int size()
        Returns the number of elements in this set (its cardinality). If thisset contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.
        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 obj)
        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 (obj==null ? e==null : obj.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:
        obj - obj is some object that may be in this collection.
        Returns:
        true if this set contains the specified element.

      • iterator

        public java.util.Iterator<E> iterator()
        Returns an iterator over the elements in this set. The elements are returned in the particular order in which they are stored in list.
        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.Set<E>
        Specified by:
        iterator in class java.util.AbstractCollection<E>
        Returns:
        an iterator over the elements in this set.

      • listIterator

        public java.util.ListIterator<E> listIterator()
        Returns an iterator over the elements in this set. The elements are returned in the particular order in which they are stored in list.
        Returns:
        an iterator over the elements in this set.

      • toArray

        public java.lang.Object[] toArray()
        Returns an array containing all of the elements in this set; the order is as in the backing list list. Obeys the general contract of the Collection.toArray method.
        Specified by:
        toArray in interface java.util.Collection<E>
        Specified by:
        toArray in interface java.util.Set<E>
        Overrides:
        toArray in class java.util.AbstractCollection<E>
        Returns:
        an array containing all of the elements in this set.

      • toArray

        public <T> T[] toArray​(T[] arr)
        Returns an array containing all of the elements in this set whose runtime type is that of the specified array; the order is as in the backing list list. Obeys the general contract of the Collection.toArray(Object[]) method.
        Specified by:
        toArray in interface java.util.Collection<E>
        Specified by:
        toArray in interface java.util.Set<E>
        Overrides:
        toArray in class java.util.AbstractCollection<E>
        Parameters:
        arr - the array into which the elements of this set are to be stored, if it is big enough; otherwise, a new array of the same runtime type is allocated for this purpose.
        Returns:
        an array containing the elements of this set.
        Throws:
        java.lang.ArrayStoreException - the runtime type of a is not a supertype of the runtime type of every element in this set.

      • add

        public boolean add​(E obj)
        Adds the specified element to this set if it is not already present. More formally, adds the specified element, o, to this set if this set contains no element e such that (o==null ? e==null : o.equals(e)). If this set already contains the specified element, the call leaves this set unchanged and returns false. In combination with the restriction on constructors, this ensures that sets never contain duplicate elements.

        Note that also null may be added to this set, but only if it is not already present, this changes this set.

        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:
        obj - element to be added to this set.
        Returns:
        true if this set did not already contain the specified element.

      • remove

        public boolean remove​(java.lang.Object obj)
        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 the set contains such an element. Returns true if the set contained the specified element (or equivalently, if the set changed as a result of the call). (The set will not contain the specified 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:
        obj - object to be removed from this set, if present.
        Returns:
        true if the set contained the specified element.

      • containsAll

        public boolean containsAll​(java.util.Collection<?> coll)
        Returns true if this set contains all of the elements of the specified collection. If the specified collection is also a set, this method returns true if it is a subset of this set.
        Specified by:
        containsAll in interface java.util.Collection<E>
        Specified by:
        containsAll in interface java.util.Set<E>
        Overrides:
        containsAll in class java.util.AbstractCollection<E>
        Parameters:
        coll - collection to be checked for containment in this set.
        Returns:
        true if this set contains all of the elements of the specified collection.

      • isSortedWithSameComparator

        private boolean isSortedWithSameComparator​(java.util.Collection<?> coll)
        Returns whether this set has the same comparator as the collection given.
        Parameters:
        coll - a collection which may be a SortedSet or not.
        Returns:
        true if c is a sorted set and if c.comparator yields the same result:
        • Either they coincide as pointers, including the case that both are null
        • or at least this comparator is not null and equals the other one. This case implies that neither are null.

      • addAll

        public boolean addAll​(java.util.Collection<? extends E> coll)
        Adds all of the elements in the specified collection to this set if they're not already present. If the specified collection is also a set, the addAll operation effectively modifies this set so that its value is the union of the two sets. The behavior of this operation is unspecified if the specified collection is modified while the operation is in progress.
        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:
        coll - collection whose elements are to be added to this set.
        Returns:
        true if this set changed as a result of the call.
        See Also:
        add(E)

      • addList

        private boolean addList​(java.util.List<E> list1,
                        java.util.List<E> list2)
        Merges list2 into list1 and returns whether l1 had been modified. At the end, list2 is not modified and list1 is ordered again.
        Parameters:
        list1 - a list which is required to be sorted according to innerCmp without duplicates.
        list2 - a list which is required to be sorted according to innerCmp without duplicates.
        Returns:
        whether list1 had been modified.

      • retainAll

        public boolean retainAll​(java.util.Collection<?> coll)
        Retains only the elements in this set that are contained in the specified collection. In other words, removes from this set all of its elements that are not contained in the specified collection. If the specified collection is also a set, this operation effectively modifies this set so that its value is the intersection of the two sets.
        Specified by:
        retainAll in interface java.util.Collection<E>
        Specified by:
        retainAll in interface java.util.Set<E>
        Overrides:
        retainAll in class java.util.AbstractCollection<E>
        Parameters:
        coll - collection that defines which elements this set will retain.
        Returns:
        true if this collection changed as a result of the call.
        See Also:
        remove(java.lang.Object)

      • removeAll

        public boolean removeAll​(java.util.Collection<?> coll)
        Removes from this set all of its elements that are contained in the specified collection. If the specified collection is also a set, this operation effectively modifies this set so that its value is the asymmetric set difference of the two sets.
        Specified by:
        removeAll in interface java.util.Collection<E>
        Specified by:
        removeAll in interface java.util.Set<E>
        Overrides:
        removeAll in class java.util.AbstractSet<E>
        Parameters:
        coll - collection that defines which elements will be removed from this set.
        Returns:
        true if this set changed as a result of the call.
        See Also:
        remove(java.lang.Object)

      • clear

        public void clear()
        Removes all of the elements from this set. This 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>

      • comparator

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

      • obj2idx

        int obj2idx​(E obj)

      • subSetIdx

        ListSet<E> subSetIdx​(int fromIdx,
                     int toIdx)

      • subSet

        public ListSet<E> subSet​(E fromObj,
                         E toObj)
        Specified by:
        subSet in interface java.util.SortedSet<E>

      • headSet

        public java.util.SortedSet<E> headSet​(E toObj)
        Specified by:
        headSet in interface java.util.SortedSet<E>

      • tailSet

        public java.util.SortedSet<E> tailSet​(E fromObj)
        Specified by:
        tailSet in interface java.util.SortedSet<E>

      • first

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

      • last

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

      • equals

        public boolean equals​(java.lang.Object obj)
        **** ask at oracle whether for sorted sets equality should include ordering. **** Compares the specified object with this set for equality. Returns true if the specified object is also a set, the two sets have the same size, and every member of the specified set is contained in this set (or equivalently, every member of this set is contained in the specified set). This definition ensures that the equals method works properly across different implementations of the set interface.
        Specified by:
        equals in interface java.util.Collection<E>
        Specified by:
        equals in interface java.util.Set<E>
        Overrides:
        equals in class java.util.AbstractSet<E>
        Parameters:
        obj - Object to be compared for equality with this set.
        Returns:
        true if the specified Object is equal to this set.

      • toString

        public java.lang.String toString()
        Returns a string representation of this set.
        Overrides:
        toString in class java.util.AbstractCollection<E>
        Returns:
        a comma separated list of String-representations of the elements of this list enclosed in triangle brackets.

      • hashCode

        public int hashCode()
        Returns the hash code value for this set. The hash code of a set is defined to be the sum of the hash codes of the elements in the set, where the hashcode of a null element is defined to be zero. This ensures that s1.equals(s2) implies that s1.hashCode()==s2.hashCode() for any two sets s1 and s2, as required by the general contract of the Object.hashCode method.
        Specified by:
        hashCode in interface java.util.Collection<E>
        Specified by:
        hashCode in interface java.util.Set<E>
        Overrides:
        hashCode in class java.util.AbstractSet<E>
        Returns:
        the hash code value for this set.
        See Also:
        Object.hashCode(), Object.equals(Object), Set.equals(Object)

      • main

        public static void main​(java.lang.String[] args)