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   /*
   28   Copyright 1999 CERN - European Organization for Nuclear Research.
   29   Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose 
   30   is hereby granted without fee, provided that the above copyright notice appear in all copies and 
   31   that both that copyright notice and this permission notice appear in supporting documentation. 
   32   CERN makes no representations about the suitability of this software for any purpose. 
   33   It is provided "as is" without expressed or implied warranty.
   34   */
   35   package org.apache.mahout.math.list;
   36   
   37   import org.apache.mahout.math.PersistentObject;
   38   
   39   /**
   40    Abstract base class for resizable lists holding objects or primitive data types such as <code>int</code>, <code>float</code>, etc.
   41    First see the <a href="package-summary.html">package summary</a> and javadoc <a href="package-tree.html">tree view</a> to get the broad picture.
   42    <p>
   43    <b>Note that this implementation is not synchronized.</b>
   44   
   45    @author wolfgang.hoschek@cern.ch
   46    @version 1.0, 09/24/99
   47    @see     java.util.ArrayList
   48    @see      java.util.Vector
   49    @see      java.util.Arrays
   50    */
   51   public abstract class AbstractList extends PersistentObject {
   52     
   53     public abstract int size();
   54     
   55     public boolean isEmpty() {
   56       return size() == 0;
   57     }
   58   
   59     /**
   60      * Inserts <tt>length</tt> dummy elements before the specified position into the receiver. Shifts the element
   61      * currently at that position (if any) and any subsequent elements to the right. <b>This method must set the new size
   62      * to be <tt>size()+length</tt>.
   63      *
   64      * @param index  index before which to insert dummy elements (must be in [0,size])..
   65      * @param length number of dummy elements to be inserted.
   66      * @throws IndexOutOfBoundsException if <tt>index &lt; 0 || index &gt; size()</tt>.
   67      */
   68     protected abstract void beforeInsertDummies(int index, int length);
   69   
   70     /** Checks if the given index is in range. */
   71     protected static void checkRange(int index, int theSize) {
   72       if (index >= theSize || index < 0) {
   73         throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + theSize);
   74       }
   75     }
   76   
   77     /**
   78      * Checks if the given range is within the contained array's bounds.
   79      *
   80      * @throws IndexOutOfBoundsException if <tt>to!=from-1 || from&lt;0 || from&gt;to || to&gt;=size()</tt>.
   81      */
   82     protected static void checkRangeFromTo(int from, int to, int theSize) {
   83       if (to == from - 1) {
   84         return;
   85       }
   86       if (from < 0 || from > to || to >= theSize) {
   87         throw new IndexOutOfBoundsException("from: " + from + ", to: " + to + ", size=" + theSize);
   88       }
   89     }
   90   
   91     /**
   92      * Removes all elements from the receiver.  The receiver will be empty after this call returns, but keep its current
   93      * capacity.
   94      */
   95     public void clear() {
   96       removeFromTo(0, size() - 1);
   97     }
   98   
   99     /**
  100      * Sorts the receiver into ascending order. This sort is guaranteed to be <i>stable</i>:  equal elements will not be
  101      * reordered as a result of the sort.<p>
  102      *
  103      * The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low
  104      * sublist is less than the lowest element in the high sublist).  This algorithm offers guaranteed n*log(n)
  105      * performance, and can approach linear performance on nearly sorted lists.
  106      *
  107      * <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one
  108      * for your data set.</b> It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because
  109      * those methods automatically choose the best sorting algorithm.
  110      */
  111     public final void mergeSort() {
  112       mergeSortFromTo(0, size() - 1);
  113     }
  114   
  115     /**
  116      * Sorts the receiver into ascending order. This sort is guaranteed to be <i>stable</i>:  equal elements will not be
  117      * reordered as a result of the sort.<p>
  118      *
  119      * The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low
  120      * sublist is less than the lowest element in the high sublist).  This algorithm offers guaranteed n*log(n)
  121      * performance, and can approach linear performance on nearly sorted lists.
  122      *
  123      * <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one
  124      * for your data set.</b> It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because
  125      * those methods automatically choose the best sorting algorithm.
  126      *
  127      * @param from the index of the first element (inclusive) to be sorted.
  128      * @param to   the index of the last element (inclusive) to be sorted.
  129      * @throws IndexOutOfBoundsException if <tt>(from&lt;0 || from&gt;to || to&gt;=size()) && to!=from-1</tt>.
  130      */
  131     public abstract void mergeSortFromTo(int from, int to);
  132   
  133     /**
  134      * Sorts the receiver into ascending order.  The sorting algorithm is a tuned quicksort, adapted from Jon L. Bentley
  135      * and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265
  136      * (November 1993).  This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to
  137      * degrade to quadratic performance.
  138      *
  139      * <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one
  140      * for your data set.</b> It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because
  141      * those methods automatically choose the best sorting algorithm.
  142      */
  143     public final void quickSort() {
  144       quickSortFromTo(0, size() - 1);
  145     }
  146   
  147     /**
  148      * Sorts the specified range of the receiver into ascending order.  The sorting algorithm is a tuned quicksort,
  149      * adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and
  150      * Experience, Vol. 23(11) P. 1249-1265 (November 1993).  This algorithm offers n*log(n) performance on many data sets
  151      * that cause other quicksorts to degrade to quadratic performance.
  152      *
  153      * <p><b>You should never call this method unless you are sure that this particular sorting algorithm is the right one
  154      * for your data set.</b> It is generally better to call <tt>sort()</tt> or <tt>sortFromTo(...)</tt> instead, because
  155      * those methods automatically choose the best sorting algorithm.
  156      *
  157      * @param from the index of the first element (inclusive) to be sorted.
  158      * @param to   the index of the last element (inclusive) to be sorted.
  159      * @throws IndexOutOfBoundsException if <tt>(from&lt;0 || from&gt;to || to&gt;=size()) && to!=from-1</tt>.
  160      */
  161     public abstract void quickSortFromTo(int from, int to);
  162   
  163     /**
  164      * Removes the element at the specified position from the receiver. Shifts any subsequent elements to the left.
  165      *
  166      * @param index the index of the element to removed.
  167      * @throws IndexOutOfBoundsException if <tt>index &lt; 0 || index &gt;= size()</tt>.
  168      */
  169     public void remove(int index) {
  170       removeFromTo(index, index);
  171     }
  172   
  173     /**
  174      * Removes from the receiver all elements whose index is between <code>from</code>, inclusive and <code>to</code>,
  175      * inclusive.  Shifts any succeeding elements to the left (reduces their index). This call shortens the list by
  176      * <tt>(to - from + 1)</tt> elements.
  177      *
  178      * @param fromIndex index of first element to be removed.
  179      * @param toIndex   index of last element to be removed.
  180      * @throws IndexOutOfBoundsException if <tt>(from&lt;0 || from&gt;to || to&gt;=size()) && to!=from-1</tt>.
  181      */
  182     public abstract void removeFromTo(int fromIndex, int toIndex);
  183   
  184     /** Reverses the elements of the receiver. Last becomes first, second last becomes second first, and so on. */
  185     public abstract void reverse();
  186   
  187     /**
  188      * Sets the size of the receiver. If the new size is greater than the current size, new null or zero items are added
  189      * to the end of the receiver. If the new size is less than the current size, all components at index newSize and
  190      * greater are discarded. This method does not release any superfluos internal memory. Use method <tt>trimToSize</tt>
  191      * to release superfluos internal memory.
  192      *
  193      * @param newSize the new size of the receiver.
  194      * @throws IndexOutOfBoundsException if <tt>newSize &lt; 0</tt>.
  195      */
  196     public void setSize(int newSize) {
  197       if (newSize < 0) {
  198         throw new IndexOutOfBoundsException("newSize:" + newSize);
  199       }
  200   
  201       int currentSize = size();
  202       if (newSize != currentSize) {
  203         if (newSize > currentSize) {
  204           beforeInsertDummies(currentSize, newSize - currentSize);
  205         } else if (newSize < currentSize) {
  206           removeFromTo(newSize, currentSize - 1);
  207         }
  208       }
  209     }
  210   
  211     /**
  212      * Sorts the receiver into ascending order.
  213      *
  214      * The sorting algorithm is dynamically chosen according to the characteristics of the data set.
  215      *
  216      * This implementation simply calls <tt>sortFromTo(...)</tt>. Override <tt>sortFromTo(...)</tt> if you can determine
  217      * which sort is most appropriate for the given data set.
  218      */
  219     public final void sort() {
  220       sortFromTo(0, size() - 1);
  221     }
  222   
  223     /**
  224      * Sorts the specified range of the receiver into ascending order.
  225      *
  226      * The sorting algorithm is dynamically chosen according to the characteristics of the data set. This default
  227      * implementation simply calls quickSort. Override this method if you can determine which sort is most appropriate for
  228      * the given data set.
  229      *
  230      * @param from the index of the first element (inclusive) to be sorted.
  231      * @param to   the index of the last element (inclusive) to be sorted.
  232      * @throws IndexOutOfBoundsException if <tt>(from&lt;0 || from&gt;to || to&gt;=size()) && to!=from-1</tt>.
  233      */
  234     public void sortFromTo(int from, int to) {
  235       quickSortFromTo(from, to);
  236     }
  237   
  238     /**
  239      * Trims the capacity of the receiver to be the receiver's current size. Releases any superfluos internal memory. An
  240      * application can use this operation to minimize the storage of the receiver. <p> This default implementation does
  241      * nothing. Override this method in space efficient implementations.
  242      */
  243     public void trimToSize() {
  244     }
  245   }

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