Class AbstractList

All Implemented Interfaces:
Serializable, Cloneable
Direct Known Subclasses:
AbstractBooleanList, AbstractByteList, AbstractCharList, AbstractDoubleList, AbstractFloatList, AbstractIntList, AbstractLongList, AbstractShortList, ObjectArrayList

public abstract class AbstractList extends AbstractCollection
Abstract base class for resizable lists holding objects or primitive data types such as int, float, etc. First see the package summary and javadoc tree view to get the broad picture.

Note that this implementation is not synchronized.

Version:
1.0, 09/24/99
See Also:
  • Field Summary

    Fields inherited from class cern.colt.PersistentObject

    serialVersionUID
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Makes this class non instantiable, but still let's others inherit from it.
  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addAllOf(Collection collection)
    Appends all of the elements of the specified Collection to the receiver.
    void
    beforeInsertAllOf(int index, Collection collection)
    Inserts all elements of the specified collection before the specified position into the receiver.
    protected abstract void
    beforeInsertDummies(int index, int length)
    Inserts length dummy elements before the specified position into the receiver.
    protected static void
    checkRange(int index, int theSize)
    Checks if the given index is in range.
    protected static void
    checkRangeFromTo(int from, int to, int theSize)
    Checks if the given range is within the contained array's bounds.
    void
    Removes all elements from the receiver.
    final void
    Sorts the receiver into ascending order.
    abstract void
    mergeSortFromTo(int from, int to)
    Sorts the receiver into ascending order.
    final void
    Sorts the receiver into ascending order.
    abstract void
    quickSortFromTo(int from, int to)
    Sorts the specified range of the receiver into ascending order.
    void
    remove(int index)
    Removes the element at the specified position from the receiver.
    abstract void
    removeFromTo(int fromIndex, int toIndex)
    Removes from the receiver all elements whose index is between from, inclusive and to, inclusive.
    abstract void
    replaceFromWith(int from, Collection other)
    Replaces the part of the receiver starting at from (inclusive) with all the elements of the specified collection.
    abstract void
    Reverses the elements of the receiver.
    void
    setSize(int newSize)
    Sets the size of the receiver.
    final void
    Randomly permutes the receiver.
    abstract void
    shuffleFromTo(int from, int to)
    Randomly permutes the receiver between from (inclusive) and to (inclusive).
    final void
    Sorts the receiver into ascending order.
    void
    sortFromTo(int from, int to)
    Sorts the specified range of the receiver into ascending order.
    void
    Trims the capacity of the receiver to be the receiver's current size.

    Methods inherited from class cern.colt.list.AbstractCollection

    isEmpty, size, toList, toString

    Methods inherited from class cern.colt.PersistentObject

    clone

    Methods inherited from class java.lang.Object

    equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
  • Constructor Details

    • AbstractList

      protected AbstractList()
      Makes this class non instantiable, but still let's others inherit from it.
  • Method Details

    • addAllOf

      public void addAllOf(Collection collection)
      Appends all of the elements of the specified Collection to the receiver.
      Throws:
      ClassCastException - if an element in the collection is not of the same parameter type of the receiver.
    • beforeInsertAllOf

      public void beforeInsertAllOf(int index, Collection collection)
      Inserts all elements of the specified collection before the specified position into the receiver. Shifts the element currently at that position (if any) and any subsequent elements to the right (increases their indices).
      Parameters:
      index - index before which to insert first element from the specified collection.
      collection - the collection to be inserted
      Throws:
      ClassCastException - if an element in the collection is not of the same parameter type of the receiver.
      IndexOutOfBoundsException - if index < 0 || index > size().
    • beforeInsertDummies

      protected abstract void beforeInsertDummies(int index, int length)
      Inserts length dummy elements before the specified position into the receiver. Shifts the element currently at that position (if any) and any subsequent elements to the right. This method must set the new size to be size()+length.
      Parameters:
      index - index before which to insert dummy elements (must be in [0,size])..
      length - number of dummy elements to be inserted.
      Throws:
      IndexOutOfBoundsException - if index < 0 || index > size().
    • checkRange

      protected static void checkRange(int index, int theSize)
      Checks if the given index is in range.
    • checkRangeFromTo

      protected static void checkRangeFromTo(int from, int to, int theSize)
      Checks if the given range is within the contained array's bounds.
      Throws:
      IndexOutOfBoundsException - if to!=from-1 || from<0 || from>to || to>=size().
    • clear

      public void clear()
      Removes all elements from the receiver. The receiver will be empty after this call returns, but keep its current capacity.
      Specified by:
      clear in class AbstractCollection
    • mergeSort

      public final void mergeSort()
      Sorts the receiver into ascending order. This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

      The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

      You should never call this method unless you are sure that this particular sorting algorithm is the right one for your data set. It is generally better to call sort() or sortFromTo(...) instead, because those methods automatically choose the best sorting algorithm.

    • mergeSortFromTo

      public abstract void mergeSortFromTo(int from, int to)
      Sorts the receiver into ascending order. This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

      The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n*log(n) performance, and can approach linear performance on nearly sorted lists.

      You should never call this method unless you are sure that this particular sorting algorithm is the right one for your data set. It is generally better to call sort() or sortFromTo(...) instead, because those methods automatically choose the best sorting algorithm.

      Parameters:
      from - the index of the first element (inclusive) to be sorted.
      to - the index of the last element (inclusive) to be sorted.
      Throws:
      IndexOutOfBoundsException - if (from<0 || from>to || to>=size()) invalid input: '&'invalid input: '&' to!=from-1.
    • quickSort

      public final void quickSort()
      Sorts the receiver into ascending order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

      You should never call this method unless you are sure that this particular sorting algorithm is the right one for your data set. It is generally better to call sort() or sortFromTo(...) instead, because those methods automatically choose the best sorting algorithm.

    • quickSortFromTo

      public abstract void quickSortFromTo(int from, int to)
      Sorts the specified range of the receiver into ascending order. The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

      You should never call this method unless you are sure that this particular sorting algorithm is the right one for your data set. It is generally better to call sort() or sortFromTo(...) instead, because those methods automatically choose the best sorting algorithm.

      Parameters:
      from - the index of the first element (inclusive) to be sorted.
      to - the index of the last element (inclusive) to be sorted.
      Throws:
      IndexOutOfBoundsException - if (from<0 || from>to || to>=size()) invalid input: '&'invalid input: '&' to!=from-1.
    • remove

      public void remove(int index)
      Removes the element at the specified position from the receiver. Shifts any subsequent elements to the left.
      Parameters:
      index - the index of the element to removed.
      Throws:
      IndexOutOfBoundsException - if index < 0 || index >= size().
    • removeFromTo

      public abstract void removeFromTo(int fromIndex, int toIndex)
      Removes from the receiver all elements whose index is between from, inclusive and to, inclusive. Shifts any succeeding elements to the left (reduces their index). This call shortens the list by (to - from + 1) elements.
      Parameters:
      from - index of first element to be removed.
      to - index of last element to be removed.
      Throws:
      IndexOutOfBoundsException - if (from<0 || from>to || to>=size()) invalid input: '&'invalid input: '&' to!=from-1.
    • replaceFromWith

      public abstract void replaceFromWith(int from, Collection other)
      Replaces the part of the receiver starting at from (inclusive) with all the elements of the specified collection. Does not alter the size of the receiver. Replaces exactly Math.max(0,Math.min(size()-from, other.size())) elements.
      Parameters:
      from - the index at which to copy the first element from the specified collection.
      other - Collection to replace part of the receiver
      Throws:
      IndexOutOfBoundsException - if index < 0 || index >= size().
    • reverse

      public abstract void reverse()
      Reverses the elements of the receiver. Last becomes first, second last becomes second first, and so on.
    • setSize

      public void setSize(int newSize)
      Sets the size of the receiver. If the new size is greater than the current size, new null or zero items are added to the end of the receiver. If the new size is less than the current size, all components at index newSize and greater are discarded. This method does not release any superfluos internal memory. Use method trimToSize to release superfluos internal memory.
      Parameters:
      newSize - the new size of the receiver.
      Throws:
      IndexOutOfBoundsException - if newSize < 0.
    • shuffle

      public final void shuffle()
      Randomly permutes the receiver. After invocation, all elements will be at random positions.
    • shuffleFromTo

      public abstract void shuffleFromTo(int from, int to)
      Randomly permutes the receiver between from (inclusive) and to (inclusive).
      Parameters:
      from - the start position (inclusive)
      to - the end position (inclusive)
      Throws:
      IndexOutOfBoundsException - if (from<0 || from>to || to>=size()) invalid input: '&'invalid input: '&' to!=from-1.
    • sort

      public final void sort()
      Sorts the receiver into ascending order. The sorting algorithm is dynamically chosen according to the characteristics of the data set. This implementation simply calls sortFromTo(...). Override sortFromTo(...) if you can determine which sort is most appropriate for the given data set.
    • sortFromTo

      public void sortFromTo(int from, int to)
      Sorts the specified range of the receiver into ascending order. The sorting algorithm is dynamically chosen according to the characteristics of the data set. This default implementation simply calls quickSort. Override this method if you can determine which sort is most appropriate for the given data set.
      Parameters:
      from - the index of the first element (inclusive) to be sorted.
      to - the index of the last element (inclusive) to be sorted.
      Throws:
      IndexOutOfBoundsException - if (from<0 || from>to || to>=size()) invalid input: '&'invalid input: '&' to!=from-1.
    • trimToSize

      public void trimToSize()
      Trims the capacity of the receiver to be the receiver's current size. Releases any superfluos internal memory. An application can use this operation to minimize the storage of the receiver.

      This default implementation does nothing. Override this method in space efficient implementations.