Package eu.simuline.util

Interface CyclicList<E>

  • Type Parameters:
    E - the class of the elements of this list.
    All Superinterfaces:
    Collection<E>, Iterable<E>
    All Known Implementing Classes:
    CollectionsExt.ImmutableCyclicList, CyclicArrayList
    public interface CyclicList<E>
extends Collection<E>
    An ordered cyclic list. The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list) which is modulo its length, and search for elements in the list.

    Unlike sets, lists typically allow duplicate elements. More formally, lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all. It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.

    The CyclicList interface places additional stipulations, beyond those specified in the Collection interface, on the contracts of the iterator, add, remove, equals, and hashCode methods. On the other hand, some methods do not make sense (such as add) and are hence not supported. This is the reason why CyclicList does not extend Collection.

    The CyclicList interface provides four methods for positional (indexed) access to list elements. CyclicLists (like Java arrays) are zero based. Note that these operations may execute in time proportional to the index value for some implementations (the LinkedCyclicList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the caller does not know the implementation.

    The CyclicList interface provides a special iterator, called a CyclicIterator, that allows element insertion and replacement, and bidirectional access similar to the normal operations that the ListIterator interface provides. A method is provided to obtain a CyclicIterator that starts at a specified position in the list.

    The CyclicList interface provides two methods to search for a specified object. From a performance standpoint, these methods should be used with caution. In many implementations they will perform costly linear searches.

    The CyclicList interface provides two methods to efficiently insert and remove multiple elements at an arbitrary point in the list.

    Note: While it is permissible for lists to contain themselves as elements, extreme caution is advised: the equals and hashCode methods are no longer well defined on a such a list.

    Version:
    1.0
    Author:
    Ernst Reissner

    • Method Summary

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method Description
      void add​(int index, E element)
      Inserts the specified element at the specified position in this list (optional operation).
      void addAll​(int index, Iterator<E> iter)
      Inserts the cyclic list of the specified iterator at the specified position in this list (optional operation).
      void addAll​(int index, List<? extends E> list)
      Inserts the specified list at the given position in this cyclic list (optional operation).
      List<E> asList()  
      List<E> asList​(int index)
      Returns a List containing all of the elements in this cyclic list in proper sequence.
      void clear()
      Removes all of the elements from this list (optional operation).
      boolean contains​(Object obj)
      Returns true if this list contains the specified element.
      CyclicList<E> cycle​(int num)
      Returns a cyclic permutation p of this cyclic list.
      CyclicIterator<E> cyclicIterator​(int index)
      Returns a CyclicIterator of the elements in this list (in proper sequence), starting at the specified position in this list.
      boolean equals​(Object obj)
      Compares the specified object with this cyclic list for equality.
      boolean equalsCyclic​(Object obj)
      Compares the specified object with this cyclic list for equality.
      E get​(int index)
      Returns the element at the specified position in this list.
      CyclicList<E> getCopy​(int len)
      Returns a CyclicList which is by copying this list step by step such that the length of the result is len.
      int getIndexOf​(int idx, Object obj)
      Returns the non-negative index in this cyclic list of the first occurrence of the specified element, or -1 if this cyclic list does not contain this element.
      CyclicList<E> getInverse()
      Returns the inverse of this cyclic list: the list with inverse order.
      int hashCode()
      Returns the hash code value for this cyclic list.
      int hashCodeCyclic()
      Returns a hash code value for this cyclic list which is invariant under cyclic permutation.
      boolean isEmpty()
      Returns true iff this list contains no elements.
      Iterator<E> iterator()
      Returns cyclicIterator(index) for some unspecified index.
      E remove​(int index)
      Removes the element at the specified position in this list (optional operation).
      void replace​(int index, Iterator<E> iter)
      Replaces the element at the specified position in this list with the cyclic list of the specified iterator (optional operation).
      void replace​(int index, List<E> list)
      Replaces the element at the specified position in this list with the specified list (optional operation).
      E set​(int index, E element)
      Replaces the element at the specified position in this list with the specified element (optional operation).
      int shiftIndex​(int index)  
      int size()
      Returns the number of elements in this list.
      Object[] toArray​(int index)
      Returns an array containing all of the elements in this cyclic list in proper sequence, i.e. in the ordering returned by the iterator given by cyclicIterator(int).
      <E> E[] toArray​(int index, E[] array)
      Returns an array containing all of the elements in this cyclic list in proper sequence, i.e. in the ordering returned by the iterator given by cyclicIterator(int); the runtime type of the returned array is that of the specified array.

    • Method Detail

      • shiftIndex

        int shiftIndex​(int index)

      • size

        int size()
        Returns the number of elements in this list. If this list contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.
        Specified by:
        size in interface Collection<E>
        Returns:
        the number of elements in this list.

      • isEmpty

        boolean isEmpty()
        Returns true iff this list contains no elements.
        Specified by:
        isEmpty in interface Collection<E>
        Returns:
        true iff this list contains no elements.

      • getInverse

        CyclicList<E> getInverse()
        Returns the inverse of this cyclic list: the list with inverse order.
        Returns:
        The list with the same entries but inverse order.

      • contains

        boolean contains​(Object obj)
        Returns true if this list contains the specified element. More formally, returns true if and only if this list contains at least one element e such that (o==null ? e==null : o.equals(e)).
        Specified by:
        contains in interface Collection<E>
        Parameters:
        obj - element whose presence in this list is to be tested.
        Returns:
        true if this list contains the specified element.

      • cyclicIterator

        CyclicIterator<E> cyclicIterator​(int index)
        Returns a CyclicIterator of the elements in this list (in proper sequence), starting at the specified position in this list. The specified index indicates the first element that would be returned by an initial call to the next method. An initial call to the previous method would return the element with the specified index minus one (modulo the length of this cyclic list).
        Parameters:
        index - index of first element to be returned from the list iterator (by a call to the next method). This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        Returns:
        a cyclic iterator of the elements in this list (in proper sequence), starting at the specified position in this list.

      • toArray

        Object[] toArray​(int index)
        Returns an array containing all of the elements in this cyclic list in proper sequence, i.e. in the ordering returned by the iterator given by cyclicIterator(int). Modifying the return value does not modify this CyclicList.
        Parameters:
        index - index of the element in the cyclic list which comes first in the array returned. This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        Returns:
        an array containing all of the elements in this list in proper sequence.

      • toArray

        <E> E[] toArray​(int index,
                E[] array)
        Returns an array containing all of the elements in this cyclic list in proper sequence, i.e. in the ordering returned by the iterator given by cyclicIterator(int); the runtime type of the returned array is that of the specified array. Modifying the return value does not modify this CyclicList.
        Parameters:
        index - index of the element in the cyclic list which comes first in the array returned. This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        array - the array into which the elements of this list 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 all of the elements in this list in proper sequence.
        Throws:
        ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type of every element in this list.

      • asList

        List<E> asList​(int index)
        Returns a List containing all of the elements in this cyclic list in proper sequence. Modifying the return value does not modify this CyclicList.
        Parameters:
        index - index of the element in the cyclic list which comes first in the List returned. This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        Returns:
        a list containing all of the elements in this cyclic list in proper sequence.
        Throws:
        ArrayStoreException - if the runtime type of the specified array is not a supertype of the runtime type of every element in this list.

      • asList

        List<E> asList()

      • cycle

        CyclicList<E> cycle​(int num)
        Returns a cyclic permutation p of this cyclic list.
        Parameters:
        num - an int value.
        Returns:
        a cyclic permutation p of this cyclic list. It satisfies p.size() == this.size() and p.get(i) == this.get(i+num).

      • clear

        void clear()
        Removes all of the elements from this list (optional operation). This list will be empty after this call returns (unless it throws an exception).
        Specified by:
        clear in interface Collection<E>
        Throws:
        UnsupportedOperationException - if the clear method is not supported by this cyclic list implementation.

      • equals

        boolean equals​(Object obj)
        Compares the specified object with this cyclic list for equality. Returns true if and only if the specified object is also a cyclic list, both lists have the same size and all corresponding pairs of elements the two lists are equal. (Two elements e1 and e2 are equal if (e1==null ? e2==null : e1.equals(e2)).) In other words, two cyclic lists are defined to be equal if they contain the same elements in the same order according to their iterators. This definition ensures that the equals method works properly across different implementations of the CyclicList interface.
        Specified by:
        equals in interface Collection<E>
        Overrides:
        equals in class Object
        Parameters:
        obj - the object to be compared for equality with this list.
        Returns:
        true if the specified object is equal to this list.
        See Also:
        equalsCyclic(Object)

      • equalsCyclic

        boolean equalsCyclic​(Object obj)
        Compares the specified object with this cyclic list for equality. Returns true if and only if the specified object is also a cyclic list, both lists have the same size, and, up to a cyclic permutation, all corresponding pairs of elements the two lists are equal. (Two elements e1 and e2 are equal if (e1==null ? e2==null : e1.equals(e2)).) In other words, two lists are defined to be equal if they contain the same elements in the same order up to a cyclic permutation. This definition ensures that the equals method works properly across different implementations of the CyclicList interface.
        Parameters:
        obj - the object to be compared for equality with this list.
        Returns:
        true if the specified object is equal to this list.
        See Also:
        equals(Object)

      • hashCode

        int hashCode()
        Returns the hash code value for this cyclic list. The hash code of a list is defined to be the result of the following calculation: 
          hashCode = 1;
  Iterator i = list.iterator();
  while (i.hasNext()) {
      Object obj = i.next();
      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
  }
        This ensures that list1.equals(list2) implies that list1.hashCode()==list2.hashCode() for any two lists, list1 and list2, as required by the general contract of Object.hashCode.
        Specified by:
        hashCode in interface Collection<E>
        Overrides:
        hashCode in class Object
        Returns:
        the hash code value for this list.
        See Also:
        equals(Object), hashCodeCyclic()

      • hashCodeCyclic

        int hashCodeCyclic()
        Returns a hash code value for this cyclic list which is invariant under cyclic permutation. This kind of hash code is conform with equalsCyclic(Object) and with equals(Object), i.e. equals objects have equal hash codes. The hash code of this cyclic list is the hash code of the underlying set. This ensures that list1.equalsCyclic(list2) implies that list1.hashCodeCyclic()==list2.hashCodeCyclic() for any two lists list1 and list2.
        Returns:
        the "cyclic hash code" value for this list.
        See Also:
        hashCode(), equalsCyclic(Object)

      • get

        E get​(int index)
        Returns the element at the specified position in this list.
        Parameters:
        index - index of element to return. This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        Returns:
        the element at the specified position in this list.

      • set

        E set​(int index,
      E element)
        Replaces the element at the specified position in this list with the specified element (optional operation).
        Parameters:
        index - index of element to replace.
        element - element to be stored at the specified position. This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        Returns:
        the element previously at the specified position.
        Throws:
        UnsupportedOperationException - if the set method is not supported by this list.
        ClassCastException - if the class of the specified element prevents it from being added to this list.
        IllegalArgumentException - if some aspect of the specified element prevents it from being added to this list.

      • replace

        void replace​(int index,
             Iterator<E> iter)
        Replaces the element at the specified position in this list with the cyclic list of the specified iterator (optional operation). Places the elements of that list as returned by iter.next in this list.
        Parameters:
        index - index of element to replace.
        iter - a CyclicIterator which determines an index in a list which replaces this.get(i).
        Throws:
        UnsupportedOperationException - if the replace method is not supported by this list.
        ClassCastException - if the class of some element returned by iter.next() prevents it from being added to this list.
        IllegalArgumentException - if some aspect of some element returned by iter.next() prevents it from being added to this list.
        EmptyCyclicListException - if this list is empty.
        IllegalArgumentException - if the specified iterator is empty.
        See Also:
        replace(int, List)

      • replace

        void replace​(int index,
             List<E> list)
        Replaces the element at the specified position in this list with the specified list (optional operation). Places the elements of that list as returned by iter.next in this list.
        Parameters:
        index - index of element to replace.
        list - a List which determines an index in a list which replaces this.get(i).
        Throws:
        UnsupportedOperationException - if the replace method is not supported by this list.
        ClassCastException - if the class of some element returned by iter.next() prevents it from being added to this list.
        IllegalArgumentException - if some aspect of some element returned by iter.next() prevents it from being added to this list.
        EmptyCyclicListException - if this list is empty.
        IllegalArgumentException - if the specified list is empty.
        See Also:
        replace(int, Iterator)

      • add

        void add​(int index,
         E element)
        Inserts the specified element at the specified position in this list (optional operation). Contract: list.add(i,o);return list.get(i) yields o. In contrast to set(int, E), the element currently at the specified position is not lost.
        Parameters:
        index - index at which the specified element is to be inserted. This is interpreted modulo the length of this cyclic list plus one (The list emerging after the insertion). In contrast to List.add(int,Object) any index (even a negative one) is valid.
        element - element to be inserted.
        Throws:
        UnsupportedOperationException - if the add method is not supported by this list.
        ClassCastException - if the class of the specified element prevents it from being added to this list.
        IllegalArgumentException - if some aspect of the specified element prevents it from being added to this list.

      • addAll

        void addAll​(int index,
            Iterator<E> iter)
        Inserts the cyclic list of the specified iterator at the specified position in this list (optional operation). In contrast to replace(int, Iterator), the element currently at the specified position is not lost.
        Parameters:
        index - index at which the specified list is to be inserted. This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        iter - element to be inserted. *****
        Throws:
        UnsupportedOperationException - if the add method is not supported by this list.
        ClassCastException - if the class of the specified element prevents it from being added to this list.
        IllegalArgumentException - if some aspect of the specified element prevents it from being added to this list.
        See Also:
        addAll(int, List)

      • addAll

        void addAll​(int index,
            List<? extends E> list)
        Inserts the specified list at the given position in this cyclic list (optional operation). In contrast to replace(int, Iterator), the element currently at the specified position is not lost.
        Parameters:
        index - index at which the specified list is to be inserted. This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        list - the list to be inserted.
        Throws:
        UnsupportedOperationException - if the add method is not supported by this list.
        ClassCastException - if the class of the specified element prevents it from being added to this list.
        IllegalArgumentException - if some aspect of the specified element prevents it from being added to this list.
        See Also:
        addAll(int, Iterator)

      • remove

        E remove​(int index)
  throws EmptyCyclicListException
        Removes the element at the specified position in this list (optional operation). Returns the element that was removed from the list.
        Parameters:
        index - the index of the element to removed. This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        Returns:
        the element previously at the specified position.
        Throws:
        UnsupportedOperationException - if the remove method is not supported by this list.
        EmptyCyclicListException - if this list is empty.

      • getIndexOf

        int getIndexOf​(int idx,
               Object obj)
        Returns the non-negative index in this cyclic list of the first occurrence of the specified element, or -1 if this cyclic list does not contain this element. More formally, returns the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), or some negative index if there is no such index.

        Note that this specification slightly differs from List.indexOf(Object).

        Parameters:
        idx - the index to start search with. Independently of this, the search comprises all entries of this cyclic list.
        obj - element to search for or null.
        Returns:
        the index in this cyclic list of the first occurrence of the specified element, or -1 if this list does not contain this element.

      • getCopy

        CyclicList<E> getCopy​(int len)
        Returns a CyclicList which is by copying this list step by step such that the length of the result is len. For example len == size()*n yields an n-fold copy of this cyclic list.
        Parameters:
        len - a non-negative int value.
        Returns:
        a CyclicList which is by copying this list step by step such that the length of the result is as specified.
        Throws:
        IllegalArgumentException - if len is negative.
        EmptyCyclicListException - if this list is empty and len > 0.