Package eu.simuline.util

Class CyclicArrayList<E>

  • Type Parameters:
    E - the class of the elements in this list.
    All Implemented Interfaces:
    CyclicList<E>, Cloneable, Iterable<E>, Collection<E>
    public final class CyclicArrayList<E>
extends Object
implements CyclicList<E>, Cloneable
    Resizable-array implementation of the CyclicList interface. Implements all optional operations, and permits all elements, includingnull. In addition to implementing the CyclicList interface, this class provides methods to manipulate the size of the array that is used internally to store the list.

    The size, isEmpty, get, set, 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 CyclicArrayList 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 list size. As elements are added an ArrayList, 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.

    An application can increase the capacity of a CyclicArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.

    Note that this implementation is not synchronized. if Multiple threads access an CyclicArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list.

    The iterator returned by this class's iterator and iterator(int) methods are fail-fast: if list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, 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.

    Version:
    1.0
    Author:
    Ernst Reissner

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private List<E> list
      The array this implementation of CyclicList is based on.

    • Constructor Summary

      Constructors 
      Constructor Description
      CyclicArrayList()
      Creates a new empty CyclicArrayList.
      CyclicArrayList​(E[] list)
      Creates a new CyclicArrayList such that new CyclicArrayList(list).get(i) == list.get(i) for all indices i for which the right hand side is valid.
      CyclicArrayList​(CyclicList<? extends E> other)
      Copy constructor.
      CyclicArrayList​(List<? extends E> list)
      Creates a new CyclicArrayList such that new CyclicArrayList(list).get(i) == list.get(i) for all indices i for which the right hand side is valid.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void add​(int index, E element)
      Inserts the specified element at the specified position in this list.
      boolean add​(E element)  
      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> addList)
      Inserts the specified list at the given position in this cyclic list. ***** done for collections!
      boolean addAll​(Collection<? extends E> coll)  
      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).
      CyclicArrayList<E> clone()
      Returns a clone of this CyclicArrayList.
      boolean contains​(Object obj)
      Returns true if this list contains the specified element.
      boolean containsAll​(Collection<?> coll)  
      CyclicArrayList<E> cycle​(int index)
      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, provided this list is not empty.
      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).
      boolean remove​(Object obj)  
      boolean removeAll​(Collection<?> coll)  
      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).
      boolean retainAll​(Collection<?> coll)  
      E set​(int index, E element)
      Replaces the element at the specified position in this list with the specified element (optional operation), provided this list is not empty.
      int shiftIndex​(int index)
      Returns the number which equals index modulo this.size(), provided this list is not empty.
      int shiftIndex​(int index, int size)  
      int size()
      Returns the number of elements in this list.
      Object[] toArray()  
      Object[] toArray​(int index)
      Returns an array containing all of the elements in this list in proper sequence.
      <E> E[] toArray​(int index, E[] ret)
      Returns an array containing all of the elements in this list in proper sequence; the runtime type of the returned array is that of the specified array.
      <E> E[] toArray​(E[] ret)  
      String toString()  

    • Field Detail

      • list

        private final List<E> list
        The array this implementation of CyclicList is based on. it satisfies this.get(i) == list.get(i) for all indices i for which the right hand side is valid.

    • Constructor Detail

      • CyclicArrayList

        public CyclicArrayList()
        Creates a new empty CyclicArrayList.

      • CyclicArrayList

        public CyclicArrayList​(E[] list)
        Creates a new CyclicArrayList such that new CyclicArrayList(list).get(i) == list.get(i) for all indices i for which the right hand side is valid.
        Parameters:
        list - some array of objects.

      • CyclicArrayList

        public CyclicArrayList​(List<? extends E> list)
        Creates a new CyclicArrayList such that new CyclicArrayList(list).get(i) == list.get(i) for all indices i for which the right hand side is valid.
        Parameters:
        list - some list of objects.

      • CyclicArrayList

        public CyclicArrayList​(CyclicList<? extends E> other)
        Copy constructor.
        Parameters:
        other - some cyclic list of objects.

    • Method Detail

      • size

        public 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>
        Specified by:
        size in interface CyclicList<E>
        Returns:
        the number of elements in this list.

      • isEmpty

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

      • getInverse

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

      • contains

        public 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>
        Specified by:
        contains in interface CyclicList<E>
        Parameters:
        obj - element whose presence in this list is to be tested.
        Returns:
        true if this list contains the specified element.

      • cyclicIterator

        public 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).
        Specified by:
        cyclicIterator in interface CyclicList<E>
        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 a negative one) is valid.
        Returns:
        a cyclic iterator of the elements in this list (in proper sequence), starting at the specified position in this list.

      • toArray

        public <E> E[] toArray​(E[] ret)
        Specified by:
        toArray in interface Collection<E>

      • toArray

        public Object[] toArray​(int index)
        Returns an array containing all of the elements in this list in proper sequence. Modifying the return value does not modify this CyclicList.
        Specified by:
        toArray in interface CyclicList<E>
        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

        public <E> E[] toArray​(int index,
                       E[] ret)
        Returns an array containing all of the elements in this list in proper sequence; the runtime type of the returned array is that of the specified array. Modifying the return value does not modify this CyclicList.
        Specified by:
        toArray in interface CyclicList<E>
        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.
        ret - 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

        public List<E> asList​(int index)
        Description copied from interface: CyclicList
        Returns a List containing all of the elements in this cyclic list in proper sequence. Modifying the return value does not modify this CyclicList.
        Specified by:
        asList in interface CyclicList<E>
        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.

      • cycle

        public CyclicArrayList<E> cycle​(int index)
        Returns a cyclic permutation p of this cyclic list.
        Specified by:
        cycle in interface CyclicList<E>
        Parameters:
        index - index of the element in the cyclic list which comes first in the cyclic list returned. This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        Returns:
        a cyclic permutation p of this cyclic list. It satisfies p.size() == this.size() and p.get(i) == this.get(i+num).

      • clear

        public 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>
        Specified by:
        clear in interface CyclicList<E>

      • equals

        public 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>
        Specified by:
        equals in interface CyclicList<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

        public 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.
        Specified by:
        equalsCyclic in interface CyclicList<E>
        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

        public 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>
        Specified by:
        hashCode in interface CyclicList<E>
        Overrides:
        hashCode in class Object
        Returns:
        the hash code value for this list.
        See Also:
        List.hashCode(), Object.equals(Object), equals(Object)

      • hashCodeCyclic

        public int hashCodeCyclic()
        Description copied from interface: CyclicList
        Returns a hash code value for this cyclic list which is invariant under cyclic permutation. This kind of hash code is conform with CyclicList.equalsCyclic(Object) and with CyclicList.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.
        Specified by:
        hashCodeCyclic in interface CyclicList<E>
        Returns:
        the "cyclic hash code" value for this list.
        See Also:
        CyclicList.hashCode(), CyclicList.equalsCyclic(Object)

      • shiftIndex

        public int shiftIndex​(int index)
               throws EmptyCyclicListException
        Returns the number which equals index modulo this.size(), provided this list is not empty.
        Specified by:
        shiftIndex in interface CyclicList<E>
        Parameters:
        index - This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        Returns:
        the number which equals index modulo this.size(), provided this list is not empty.
        Throws:
        EmptyCyclicListException - if this list is empty.

      • get

        public E get​(int index)
      throws EmptyCyclicListException
        Returns the element at the specified position in this list, provided this list is not empty.
        Specified by:
        get in interface CyclicList<E>
        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.
        Throws:
        EmptyCyclicListException - if this list is empty.

      • set

        public E set​(int index,
             E element)
      throws EmptyCyclicListException
        Replaces the element at the specified position in this list with the specified element (optional operation), provided this list is not empty.
        Specified by:
        set in interface CyclicList<E>
        Parameters:
        index - index of the element to replace. This is interpreted modulo the length of this cyclic list. Any index (even negative ones) are valid.
        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:
        EmptyCyclicListException - if this list is empty.

      • replace

        public 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.
        Specified by:
        replace in interface CyclicList<E>
        Parameters:
        index - index index of element to replace.
        iter - a CyclicIterator which determines an index in a list which replaces this.get(i).
        Throws:
        EmptyCyclicListException - if this list is empty.
        IllegalArgumentException - if the specified iterator is empty.
        See Also:
        CyclicList.replace(int, List)

      • replace

        public void replace​(int index,
                    List<E> list)
        Description copied from interface: CyclicList
        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.
        Specified by:
        replace in interface CyclicList<E>
        Parameters:
        index - index of element to replace.
        list - a List which determines an index in a list which replaces this.get(i).
        See Also:
        CyclicList.replace(int, Iterator)

      • addAll

        public 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.
        Specified by:
        addAll in interface CyclicList<E>
        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 - iterator delivering the elements to be inserted.
        See Also:
        CyclicList.addAll(int, List)

      • addAll

        public void addAll​(int index,
                   List<? extends E> addList)
        Inserts the specified list at the given position in this cyclic list. ***** done for collections! Shifts the element currently at that position (if any) and any subsequent elements to the right (increases their indices). The new elements will appear in this list in the order that they are returned by the specified collection's iterator. The behavior of this operation is unspecified if the specified collection is modified while the operation is in progress. (Note that this will occur if the specified collection is this list, and it's nonempty.) Contract: list.addAll(i, l); return list.get(i+k) yields list.get(k), for all k in 0,..,l.size()-1.

        Note that for l containing a single element e, list.addAll(i, l) is equivalent with list.add(i, e).

        Specified by:
        addAll in interface CyclicList<E>
        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.
        addList - the list to be inserted. **** this is much more complicated! ****
        See Also:
        CyclicList.addAll(int, Iterator)

      • add

        public void add​(int index,
                E element)
        Inserts the specified element at the specified position in this list. 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. Also note that this operation is allowed for empty cyclic lists. In this case, index is irrelevant.
        Specified by:
        add in interface CyclicList<E>
        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.

      • add

        public boolean add​(E element)
        Specified by:
        add in interface Collection<E>

      • remove

        public 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, provided this list is not empty.
        Specified by:
        remove in interface CyclicList<E>
        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:
        EmptyCyclicListException - if this list is empty.

      • getIndexOf

        public 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).

        Specified by:
        getIndexOf in interface CyclicList<E>
        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

        public 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.
        Specified by:
        getCopy in interface CyclicList<E>
        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.