Save This Page
Home » mahout-collections-1.0-src » org.apache.mahout.math.list » [javadoc | source]
    1   /**
    2    * Licensed to the Apache Software Foundation (ASF) under one
    3    * or more contributor license agreements. See the NOTICE file
    4    * distributed with this work for additional information
    5    * regarding copyright ownership. The ASF licenses this file
    6    * to you under the Apache License, Version 2.0 (the
    7    * "License"); you may not use this file except in compliance
    8    * with the License. You may obtain a copy of the License at
    9    *
   10    * http://www.apache.org/licenses/LICENSE-2.0
   11    *
   12    * Unless required by applicable law or agreed to in writing,
   13    * software distributed under the License is distributed on an
   14    * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
   15    * KIND, either express or implied. See the License for the
   16    * specific language governing permissions and limitations
   17    * under the License.
   18    */
   19   /*
   20   Copyright ? 1999 CERN - European Organization for Nuclear Research.
   21   Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose 
   22   is hereby granted without fee, provided that the above copyright notice appear in all copies and 
   23   that both that copyright notice and this permission notice appear in supporting documentation. 
   24   CERN makes no representations about the suitability of this software for any purpose. 
   25   It is provided "as is" without expressed or implied warranty.
   26   */
   27   package org.apache.mahout.math.list;
   28   
   29   import org.apache.mahout.math.function.ObjectProcedure;
   30   
   31   import java.util.Collection;
   32   
   33   /**
   34    Resizable list holding <code>${valueType}</code> elements; implemented with arrays.
   35   */
   36   
   37   public class ObjectArrayList<T> extends AbstractObjectList<T> {
   38   
   39     /**
   40      * The array buffer into which the elements of the list are stored. The capacity of the list is the length of this
   41      * array buffer.
   42      */
   43     private Object[] elements;
   44     private int size;
   45   
   46     /** Constructs an empty list. */
   47     public ObjectArrayList() {
   48       this(10);
   49     }
   50   
   51     /**
   52      * Constructs a list containing the specified elements. The initial size and capacity of the list is the length of the
   53      * array.
   54      *
   55      * <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array is not copied</b>. So if
   56      * subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing.
   57      *
   58      * @param elements the array to be backed by the the constructed list
   59      */
   60     public ObjectArrayList(T[] elements) {
   61       elements(elements);
   62     }
   63   
   64     /**
   65      * Constructs an empty list with the specified initial capacity.
   66      *
   67      * @param initialCapacity the number of elements the receiver can hold without auto-expanding itself by allocating new
   68      *                        internal memory.
   69      */
   70     @SuppressWarnings("unchecked")
   71     public ObjectArrayList(int initialCapacity) {
   72       elements((T[])new Object[initialCapacity]);
   73     }
   74   
   75     /**
   76      * Appends the specified element to the end of this list.
   77      *
   78      * @param element element to be appended to this list.
   79      */
   80     public void add(T element) {
   81       // overridden for performance only.
   82       if (size == elements.length) {
   83         ensureCapacity(size + 1);
   84       }
   85       elements[size++] = element;
   86     }
   87   
   88     /**
   89      * Inserts the specified element before the specified position into the receiver. Shifts the element currently at that
   90      * position (if any) and any subsequent elements to the right.
   91      *
   92      * @param index   index before which the specified element is to be inserted (must be in [0,size]).
   93      * @param element element to be inserted.
   94      * @throws IndexOutOfBoundsException index is out of range (<tt>index &lt; 0 || index &gt; size()</tt>).
   95      */
   96     public void beforeInsert(int index, T element) {
   97       // overridden for performance only.
   98       if (size == index) {
   99         add(element);
  100         return;
  101       }
  102       if (index > size || index < 0) {
  103         throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  104       }
  105       ensureCapacity(size + 1);
  106       System.arraycopy(elements, index, elements, index + 1, size - index);
  107       elements[index] = element;
  108       size++;
  109     }
  110   
  111   
  112     /**
  113      * Returns a deep copy of the receiver.
  114      *
  115      * @return a deep copy of the receiver.
  116      */
  117     @SuppressWarnings("unchecked")
  118     @Override
  119     public Object clone() {
  120       // overridden for performance only.
  121       return new ObjectArrayList<T>((T[]) elements.clone());
  122     }
  123   
  124     /**
  125      * Returns a deep copy of the receiver; uses <code>clone()</code> and casts the result.
  126      *
  127      * @return a deep copy of the receiver.
  128      */
  129     @SuppressWarnings("unchecked")
  130     public ObjectArrayList<T> copy() {
  131       return (ObjectArrayList<T>) clone();
  132     }
  133   
  134     /**
  135      * Returns the elements currently stored, including invalid elements between size and capacity, if any.
  136      *
  137      * <b>WARNING:</b> For efficiency reasons and to keep memory usage low, <b>the array is not copied</b>. So if
  138      * subsequently you modify the returned array directly via the [] operator, be sure you know what you're doing.
  139      *
  140      * @return the elements currently stored.
  141      */
  142     @SuppressWarnings("unchecked")
  143     public<Q> Q[] elements() {
  144       return (Q[])elements;
  145     }
  146   
  147     /**
  148      * Sets the receiver's elements to be the specified array (not a copy of it).
  149      *
  150      * The size and capacity of the list is the length of the array. <b>WARNING:</b> For efficiency reasons and to keep
  151      * memory usage low, <b>the array is not copied</b>. So if subsequently you modify the specified array directly via
  152      * the [] operator, be sure you know what you're doing.
  153      *
  154      * @param elements the new elements to be stored.
  155      * @return the receiver itself.
  156      */
  157     public void elements(T[] elements) {
  158       this.elements = elements;
  159       this.size = elements.length;
  160     }
  161   
  162     /**
  163      * Ensures that the receiver can hold at least the specified number of elements without needing to allocate new
  164      * internal memory. If necessary, allocates new internal memory and increases the capacity of the receiver.
  165      *
  166      * @param minCapacity the desired minimum capacity.
  167      */
  168     public void ensureCapacity(int minCapacity) {
  169       elements = org.apache.mahout.math.Arrays.ensureCapacity(elements, minCapacity);
  170     }
  171   
  172     /**
  173      * Compares the specified Object with the receiver. Returns true if and only if the specified Object is also an
  174      * ArrayList of the same type, both Lists have the same size, and all corresponding pairs of elements in the two Lists
  175      * are identical. In other words, two Lists are defined to be equal if they contain the same elements in the same
  176      * order.
  177      *
  178      * @param otherObj the Object to be compared for equality with the receiver.
  179      * @return true if the specified Object is equal to the receiver.
  180      */
  181     @SuppressWarnings("unchecked")
  182     public boolean equals(Object otherObj) { //delta
  183       // overridden for performance only.
  184       if (!(otherObj instanceof ObjectArrayList)) {
  185         return super.equals(otherObj);
  186       }
  187       if (this == otherObj) {
  188         return true;
  189       }
  190       if (otherObj == null) {
  191         return false;
  192       }
  193       ObjectArrayList<?> other = (ObjectArrayList<?>) otherObj;
  194       if (size() != other.size()) {
  195         return false;
  196       }
  197   
  198       Object[] theElements = elements();
  199       Object[] otherElements = other.elements();
  200       for (int i = size(); --i >= 0;) {
  201         if (theElements[i] != otherElements[i]) {
  202           return false;
  203         }
  204       }
  205       return true;
  206     }
  207   
  208     /**
  209      * Applies a procedure to each element of the receiver, if any. Starts at index 0, moving rightwards.
  210      *
  211      * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise
  212      *                  continues.
  213      * @return <tt>false</tt> if the procedure stopped before all elements where iterated over, <tt>true</tt> otherwise.
  214      */
  215     @SuppressWarnings("unchecked")
  216     public boolean forEach(ObjectProcedure<T> procedure) {
  217       T[] theElements = (T[]) elements;
  218       int theSize = size;
  219   
  220       for (int i = 0; i < theSize;) {
  221         if (!procedure.apply(theElements[i++])) {
  222           return false;
  223         }
  224       }
  225       return true;
  226     }
  227   
  228     /**
  229      * Returns the element at the specified position in the receiver.
  230      *
  231      * @param index index of element to return.
  232      * @throws IndexOutOfBoundsException index is out of range (index &lt; 0 || index &gt;= size()).
  233      */
  234     @SuppressWarnings("unchecked")
  235     public T get(int index) {
  236       // overridden for performance only.
  237       if (index >= size || index < 0) {
  238         throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  239       }
  240       return (T) elements[index];
  241     }
  242   
  243     /**
  244      * Returns the element at the specified position in the receiver; <b>WARNING:</b> Does not check preconditions.
  245      * Provided with invalid parameters this method may return invalid elements without throwing any exception! <b>You
  246      * should only use this method when you are absolutely sure that the index is within bounds.</b> Precondition
  247      * (unchecked): <tt>index &gt;= 0 && index &lt; size()</tt>.
  248      *
  249      * @param index index of element to return.
  250      */
  251     @SuppressWarnings("unchecked")
  252     public T getQuick(int index) {
  253       return (T) elements[index];
  254     }
  255   
  256     /**
  257      * Returns the index of the first occurrence of the specified element. Returns <code>-1</code> if the receiver does
  258      * not contain this element. Searches between <code>from</code>, inclusive and <code>to</code>, inclusive. Tests for
  259      * identity.
  260      *
  261      * @param element element to search for.
  262      * @param from    the leftmost search position, inclusive.
  263      * @param to      the rightmost search position, inclusive.
  264      * @return the index of the first occurrence of the element in the receiver; returns <code>-1</code> if the element is
  265      *         not found.
  266      * @throws IndexOutOfBoundsException index is out of range (<tt>size()&gt;0 && (from&lt;0 || from&gt;to ||
  267      *                                   to&gt;=size())</tt>).
  268      */
  269     public int indexOfFromTo(T element, int from, int to) {
  270       // overridden for performance only.
  271       if (size == 0) {
  272         return -1;
  273       }
  274       checkRangeFromTo(from, to, size);
  275   
  276       Object[] theElements = elements;
  277       for (int i = from; i <= to; i++) {
  278         if (element == theElements[i]) {
  279           return i;
  280         } //found
  281       }
  282       return -1; //not found
  283     }
  284   
  285     /**
  286      * Returns the index of the last occurrence of the specified element. Returns <code>-1</code> if the receiver does not
  287      * contain this element. Searches beginning at <code>to</code>, inclusive until <code>from</code>, inclusive. Tests
  288      * for identity.
  289      *
  290      * @param element element to search for.
  291      * @param from    the leftmost search position, inclusive.
  292      * @param to      the rightmost search position, inclusive.
  293      * @return the index of the last occurrence of the element in the receiver; returns <code>-1</code> if the element is
  294      *         not found.
  295      * @throws IndexOutOfBoundsException index is out of range (<tt>size()&gt;0 && (from&lt;0 || from&gt;to ||
  296      *                                   to&gt;=size())</tt>).
  297      */
  298     public int lastIndexOfFromTo(T element, int from, int to) {
  299       // overridden for performance only.
  300       if (size == 0) {
  301         return -1;
  302       }
  303       checkRangeFromTo(from, to, size);
  304   
  305       Object[] theElements = elements;
  306       for (int i = to; i >= from; i--) {
  307         if (element == theElements[i]) {
  308           return i;
  309         } //found
  310       }
  311       return -1; //not found
  312     }
  313   
  314     /**
  315      * Returns a new list of the part of the receiver between <code>from</code>, inclusive, and <code>to</code>,
  316      * inclusive.
  317      *
  318      * @param from the index of the first element (inclusive).
  319      * @param to   the index of the last element (inclusive).
  320      * @return a new list
  321      * @throws IndexOutOfBoundsException index is out of range (<tt>size()&gt;0 && (from&lt;0 || from&gt;to ||
  322      *                                   to&gt;=size())</tt>).
  323      */
  324     @SuppressWarnings("unchecked")
  325     public AbstractObjectList<T> partFromTo(int from, int to) {
  326       if (size == 0) {
  327         return new ObjectArrayList<T>(0);
  328       }
  329   
  330       checkRangeFromTo(from, to, size);
  331   
  332       Object[] part = new Object[to - from + 1];
  333       System.arraycopy(elements, from, part, 0, to - from + 1);
  334       return new ObjectArrayList<T>((T[]) part);
  335     }
  336   
  337     /** Reverses the elements of the receiver. Last becomes first, second last becomes second first, and so on. */
  338     @Override
  339     public void reverse() {
  340       // overridden for performance only.
  341       int limit = size / 2;
  342       int j = size - 1;
  343   
  344       Object[] theElements = elements;
  345       for (int i = 0; i < limit;) { //swap
  346         Object tmp = theElements[i];
  347         theElements[i++] = theElements[j];
  348         theElements[j--] = tmp;
  349       }
  350     }
  351   
  352     /**
  353      * Replaces the element at the specified position in the receiver with the specified element.
  354      *
  355      * @param index   index of element to replace.
  356      * @param element element to be stored at the specified position.
  357      * @throws IndexOutOfBoundsException index is out of range (index &lt; 0 || index &gt;= size()).
  358      */
  359     public void set(int index, T element) {
  360       // overridden for performance only.
  361       if (index >= size || index < 0) {
  362         throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  363       }
  364       elements[index] = element;
  365     }
  366   
  367     /**
  368      * Replaces the element at the specified position in the receiver with the specified element; <b>WARNING:</b> Does not
  369      * check preconditions. Provided with invalid parameters this method may access invalid indexes without throwing any
  370      * exception! <b>You should only use this method when you are absolutely sure that the index is within bounds.</b>
  371      * Precondition (unchecked): <tt>index &gt;= 0 && index &lt; size()</tt>.
  372      *
  373      * @param index   index of element to replace.
  374      * @param element element to be stored at the specified position.
  375      */
  376     public void setQuick(int index, T element) {
  377       elements[index] = element;
  378     }
  379   
  380     /**
  381      * Trims the capacity of the receiver to be the receiver's current size. Releases any superfluous internal memory. An
  382      * application can use this operation to minimize the storage of the receiver.
  383      */
  384     @Override
  385     public void trimToSize() {
  386       elements = org.apache.mahout.math.Arrays.trimToCapacity(elements, size());
  387     }
  388   
  389     @Override
  390     public void removeFromTo(int fromIndex, int toIndex) {
  391       throw new UnsupportedOperationException();
  392     }
  393   
  394     @Override
  395     public void replaceFromWith(int from, Collection<T> other) {
  396       throw new UnsupportedOperationException();
  397     }
  398   
  399     @Override
  400     protected void beforeInsertDummies(int index, int length) {
  401       throw new UnsupportedOperationException();
  402     }
  403   
  404     @Override
  405     public void mergeSortFromTo(int from, int to) {
  406       throw new UnsupportedOperationException();
  407     }
  408   
  409     @Override
  410     public void quickSortFromTo(int from, int to) {
  411       throw new UnsupportedOperationException();
  412     }
  413   
  414     @Override
  415     public int size() {
  416       return size;
  417     }
  418   }

Save This Page
Home » mahout-collections-1.0-src » org.apache.mahout.math.list » [javadoc | source]