Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements. See the NOTICE file distributed with this work for additional information regarding copyright ownership. The ASF licenses this file to you under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
 
 /*
 Copyright ï¿½ 1999 CERN - European Organization for Nuclear Research.
 Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose 
 is hereby granted without fee, provided that the above copyright notice appear in all copies and 
 that both that copyright notice and this permission notice appear in supporting documentation. 
 CERN makes no representations about the suitability of this software for any purpose. 
 It is provided "as is" without expressed or implied warranty.
 */
 package org.apache.mahout.math.list;
 
Resizable list holding long elements; implemented with arrays.
 
 
 public class LongArrayList extends AbstractLongList implements Cloneable {

  
The array buffer into which the elements of the list are stored. The capacity of the list is the length of this array buffer.
 
   private long[] elements;

  
Constructs an empty list.
 
   public LongArrayList() {
     this(10);
   }

  
Constructs a list containing the specified elements. The initial size and capacity of the list is the length of the array. WARNING: For efficiency reasons and to keep memory usage low, the array is not copied. So if subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing.

Parameters:
elements the array to be backed by the the constructed list
 
   public LongArrayList(long[] elements) {
     elements(elements);
   }

  
Constructs an empty list with the specified initial capacity.

Parameters:
initialCapacity the number of elements the receiver can hold without auto-expanding itself by allocating new internal memory.
 
   public LongArrayList(int initialCapacity) {
     this(new long[initialCapacity]);
     setSizeRaw(0);
   }

  
Appends the specified element to the end of this list.

Parameters:
element element to be appended to this list.
 
   public void add(long element) {
     // overridden for performance only.
     if ( == .) {
       ensureCapacity( + 1);
     }
     [++] = element;
   }

  
Inserts the specified element before the specified position into the receiver. Shifts the element currently at that position (if any) and any subsequent elements to the right.

Parameters:
index index before which the specified element is to be inserted (must be in [0,size]).
element element to be inserted.
Throws:
java.lang.IndexOutOfBoundsException index is out of range (index < 0 || index > size()).
 
   public void beforeInsert(int indexlong element) {
     // overridden for performance only.
     if ( == index) {
       add(element);
       return;
     }
     if (index >  || index < 0) {
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + );
    }
    ensureCapacity( + 1);
    System.arraycopy(indexindex + 1,  - index);
    [index] = element;
    ++;
  }

  
Searches the receiver for the specified value using the binary search algorithm. The receiver must must be sorted (as by the sort method) prior to making this call. If it is not sorted, the results are undefined: in particular, the call may enter an infinite loop. If the receiver contains multiple elements equal to the specified object, there is no guarantee which instance will be found.

Parameters:
key the value to be searched for.
from the leftmost search position, inclusive.
to the rightmost search position, inclusive.
Returns:
index of the search key, if it is contained in the receiver; otherwise, (-(insertion point) - 1). The insertion point is defined as the the point at which the value would be inserted into the receiver: the index of the first element greater than the key, or receiver.size(), if all elements in the receiver are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.
See also:
org.apache.mahout.math.BinarySearch
java.util.Arrays
  public int binarySearchFromTo(long keyint fromint to) {
    return org.apache.mahout.math.BinarySearch.binarySearchFromTo(keyfromto);
  }

  
Returns a deep copy of the receiver.

Returns:
a deep copy of the receiver.
  public Object clone() {
    // overridden for performance only.
    LongArrayList clone = new LongArrayList(.clone());
    clone.setSizeRaw();
    return clone;
  }

  
Returns a deep copy of the receiver; uses clone() and casts the result.

Returns:
a deep copy of the receiver.
  public LongArrayList copy() {
    return (LongArrayListclone();
  }

  
  
Returns the elements currently stored, including invalid elements between size and capacity, if any. WARNING: For efficiency reasons and to keep memory usage low, the array is not copied. So if subsequently you modify the returned array directly via the [] operator, be sure you know what you're doing.

Returns:
the elements currently stored.
  public long[] elements() {
    return ;
  }

  
Sets the receiver's elements to be the specified array (not a copy of it). The size and capacity of the list is the length of the array. WARNING: For efficiency reasons and to keep memory usage low, the array is not copied. So if subsequently you modify the specified array directly via the [] operator, be sure you know what you're doing.

Parameters:
elements the new elements to be stored.
Returns:
the receiver itself.
  public AbstractLongList elements(long[] elements) {
    this. = elements;
    this. = elements.length;
    return this;
  }

  
Ensures that the receiver can hold at least the specified number of elements without needing to allocate new internal memory. If necessary, allocates new internal memory and increases the capacity of the receiver.

Parameters:
minCapacity the desired minimum capacity.
  public void ensureCapacity(int minCapacity) {
     = org.apache.mahout.math.Arrays.ensureCapacity(minCapacity);
  }

  
Compares the specified Object with the receiver. Returns true if and only if the specified Object is also an ArrayList of the same type, both Lists have the same size, and all corresponding pairs of elements in the two Lists are identical. In other words, two Lists are defined to be equal if they contain the same elements in the same order.

Parameters:
otherObj the Object to be compared for equality with the receiver.
Returns:
true if the specified Object is equal to the receiver.
  public boolean equals(Object otherObj) { //delta
    if (otherObj == null) {
      return false;
    }
    // overridden for performance only.
    if (!(otherObj instanceof LongArrayList)) {
      return super.equals(otherObj);
    }
    if (this == otherObj) {
      return true;
    }
    LongArrayList other = (LongArrayListotherObj;
    if (size() != other.size()) {
      return false;
    }
    long[] theElements = elements();
    long[] otherElements = other.elements();
    for (int i = size(); --i >= 0;) {
      if (theElements[i] != otherElements[i]) {
        return false;
      }
    }
    return true;
  }

  
Applies a procedure to each element of the receiver, if any. Starts at index 0, moving rightwards.

Parameters:
procedure the procedure to be applied. Stops iteration if the procedure returns false, otherwise continues.
Returns:
false if the procedure stopped before all elements where iterated over, true otherwise.
  public boolean forEach(LongProcedure procedure) {
    // overridden for performance only.
    long[] theElements = ;
    int theSize = ;
    for (int i = 0; i < theSize;) {
      if (!procedure.apply(theElements[i++])) {
        return false;
      }
    }
    return true;
  }

  
Returns the element at the specified position in the receiver.

Parameters:
index index of element to return.
Throws:
java.lang.IndexOutOfBoundsException index is out of range (index < 0 || index >= size()).
  public long get(int index) {
    // overridden for performance only.
    if (index >=  || index < 0) {
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + );
    }
    return [index];
  }

  
Returns the element at the specified position in the receiver; WARNING: Does not check preconditions. Provided with invalid parameters this method may return invalid elements without throwing any exception! You should only use this method when you are absolutely sure that the index is within bounds. Precondition (unchecked): index >= 0 && index < size().

Parameters:
index index of element to return.
  public long getQuick(int index) {
    return [index];
  }

  
Returns the index of the first occurrence of the specified element. Returns -1 if the receiver does not contain this element. Searches between from, inclusive and to, inclusive. Tests for identity.

Parameters:
element element to search for.
from the leftmost search position, inclusive.
to the rightmost search position, inclusive.
Returns:
the index of the first occurrence of the element in the receiver; returns -1 if the element is not found.
Throws:
java.lang.IndexOutOfBoundsException index is out of range (size()>0 && (from<0 || from>to || to>=size())).
  public int indexOfFromTo(long elementint fromint to) {
    // overridden for performance only.
    if ( == 0) {
      return -1;
    }
    checkRangeFromTo(fromto);
    long[] theElements = ;
    for (int i = fromi <= toi++) {
      if (element == theElements[i]) {
        return i;
      } //found
    }
    return -1; //not found
  }

  
Returns the index of the last occurrence of the specified element. Returns -1 if the receiver does not contain this element. Searches beginning at to, inclusive until from, inclusive. Tests for identity.

Parameters:
element element to search for.
from the leftmost search position, inclusive.
to the rightmost search position, inclusive.
Returns:
the index of the last occurrence of the element in the receiver; returns -1 if the element is not found.
Throws:
java.lang.IndexOutOfBoundsException index is out of range (size()>0 && (from<0 || from>to || to>=size())).
  public int lastIndexOfFromTo(long elementint fromint to) {
    // overridden for performance only.
    if ( == 0) {
      return -1;
    }
    checkRangeFromTo(fromto);
    long[] theElements = ;
    for (int i = toi >= fromi--) {
      if (element == theElements[i]) {
        return i;
      } //found
    }
    return -1; //not found
  }

  
Returns a new list of the part of the receiver between from, inclusive, and to, inclusive.

Parameters:
from the index of the first element (inclusive).
to the index of the last element (inclusive).
Returns:
a new list
Throws:
java.lang.IndexOutOfBoundsException index is out of range (size()>0 && (from<0 || from>to || to>=size())).
  public AbstractLongList partFromTo(int fromint to) {
    if ( == 0) {
      return new LongArrayList(0);
    }
    checkRangeFromTo(fromto);
    long[] part = new long[to - from + 1];
    System.arraycopy(frompart, 0, to - from + 1);
    return new LongArrayList(part);
  }

  
Removes from the receiver all elements that are contained in the specified list. Tests for identity.

Parameters:
other the other list.
Returns:
true if the receiver changed as a result of the call.
  public boolean removeAll(AbstractLongList other) {
    // overridden for performance only.
    if (!(other instanceof LongArrayList)) {
      return super.removeAll(other);
    }
    /* There are two possibilities to do the thing
       a) use other.indexOf(...)
       b) sort other, then use other.binarySearch(...)
       Let's try to figure out which one is faster. Let M=size, N=other.size, then
       a) takes O(M*N) steps
       b) takes O(N*logN + M*logN) steps (sorting is O(N*logN) and binarySearch is O(logN))
       Hence, if N*logN + M*logN < M*N, we use b) otherwise we use a).
    */
    if (other.isEmpty()) {
      return false;
    } //nothing to do
    int limit = other.size() - 1;
    int j = 0;
    long[] theElements = ;
    int mySize = size();
    double N = (doubleother.size();
    double M = (doublemySize;
    if ((N + M) * org.apache.mahout.collections.Arithmetic.log2(N) < M * N) {
      // it is faster to sort other before searching in it
      LongArrayList sortedList = (LongArrayListother.clone();
      sortedList.quickSort();
      for (int i = 0; i < mySizei++) {
        if (sortedList.binarySearchFromTo(theElements[i], 0, limit) < 0) {
          theElements[j++] = theElements[i];
        }
      }
    } else {
      // it is faster to search in other without sorting
      for (int i = 0; i < mySizei++) {
        if (other.indexOfFromTo(theElements[i], 0, limit) < 0) {
          theElements[j++] = theElements[i];
        }
      }
    }
    boolean modified = (j != mySize);
    setSize(j);
    return modified;
  }

  
Replaces a number of elements in the receiver with the same number of elements of another list. Replaces elements in the receiver, between from (inclusive) and to (inclusive), with elements of other, starting from otherFrom (inclusive).

Parameters:
from the position of the first element to be replaced in the receiver
to the position of the last element to be replaced in the receiver
other list holding elements to be copied into the receiver.
otherFrom position of first element within other list to be copied.
  public void replaceFromToWithFrom(int fromint toAbstractLongList otherint otherFrom) {
    // overridden for performance only.
    if (!(other instanceof LongArrayList)) {
      // slower
      super.replaceFromToWithFrom(fromtootherotherFrom);
      return;
    }
    int length = to - from + 1;
    if (length > 0) {
      checkRangeFromTo(fromtosize());
      checkRangeFromTo(otherFromotherFrom + length - 1, other.size());
      System.arraycopy(((LongArrayListother).otherFromfromlength);
    }
  }

  
Retains (keeps) only the elements in the receiver that are contained in the specified other list. In other words, removes from the receiver all of its elements that are not contained in the specified other list.

Parameters:
other the other list to test against.
Returns:
true if the receiver changed as a result of the call.
  public boolean retainAll(AbstractLongList other) {
    // overridden for performance only.
    if (!(other instanceof LongArrayList)) {
      return super.retainAll(other);
    }
    /* There are two possibilities to do the thing
       a) use other.indexOf(...)
       b) sort other, then use other.binarySearch(...)
       Let's try to figure out which one is faster. Let M=size, N=other.size, then
       a) takes O(M*N) steps
       b) takes O(N*logN + M*logN) steps (sorting is O(N*logN) and binarySearch is O(logN))
       Hence, if N*logN + M*logN < M*N, we use b) otherwise we use a).
    */
    int limit = other.size() - 1;
    int j = 0;
    long[] theElements = ;
    int mySize = size();
    double N = (doubleother.size();
    double M = (doublemySize;
    if ((N + M) * org.apache.mahout.collections.Arithmetic.log2(N) < M * N) {
      // it is faster to sort other before searching in it
      LongArrayList sortedList = (LongArrayListother.clone();
      sortedList.quickSort();
      for (int i = 0; i < mySizei++) {
        if (sortedList.binarySearchFromTo(theElements[i], 0, limit) >= 0) {
          theElements[j++] = theElements[i];
        }
      }
    } else {
      // it is faster to search in other without sorting
      for (int i = 0; i < mySizei++) {
        if (other.indexOfFromTo(theElements[i], 0, limit) >= 0) {
          theElements[j++] = theElements[i];
        }
      }
    }
    boolean modified = (j != mySize);
    setSize(j);
    return modified;
  }

  
Reverses the elements of the receiver. Last becomes first, second last becomes second first, and so on.
  public void reverse() {
    // overridden for performance only.
    int limit =  / 2;
    int j =  - 1;
    long[] theElements = ;
    for (int i = 0; i < limit;) { //swap
      long tmp = theElements[i];
      theElements[i++] = theElements[j];
      theElements[j--] = tmp;
    }
  }

  
Replaces the element at the specified position in the receiver with the specified element.

Parameters:
index index of element to replace.
element element to be stored at the specified position.
Throws:
java.lang.IndexOutOfBoundsException index is out of range (index < 0 || index >= size()).
  public void set(int indexlong element) {
    // overridden for performance only.
    if (index >=  || index < 0) {
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + );
    }
    [index] = element;
  }

  
Replaces the element at the specified position in the receiver with the specified element; WARNING: Does not check preconditions. Provided with invalid parameters this method may access invalid indexes without throwing any exception! You should only use this method when you are absolutely sure that the index is within bounds. Precondition (unchecked): index >= 0 && index < size().

Parameters:
index index of element to replace.
element element to be stored at the specified position.
  public void setQuick(int indexlong element) {
    [index] = element;
  }

  
Randomly permutes the part of the receiver between from (inclusive) and to (inclusive).

Parameters:
from the index of the first element (inclusive) to be permuted.
to the index of the last element (inclusive) to be permuted.
Throws:
IndexOutOfBoundsException index is out of range (size()>0 && (from<0 || from>to || to>=size())).


  
Sorts the specified range of the receiver into ascending order. The sorting algorithm is dynamically chosen according to the characteristics of the data set. Currently quicksort and countsort are considered. Countsort is not always applicable, but if applicable, it usually outperforms quicksort by a factor of 3-4.

Best case performance: O(N).

Worst case performance: O(N^2) (a degenerated quicksort).
Best case space requirements: 0 KB.
Worst case space requirements: 40 KB.

Parameters:
from the index of the first element (inclusive) to be sorted.
to the index of the last element (inclusive) to be sorted.
Throws:
java.lang.IndexOutOfBoundsException index is out of range (size()>0 && (from<0 || from>to || to>=size())).

  public void sortFromTo(int fromint to) {
    /*
    * Computes min and max and decides on this basis.
    * In practice the additional overhead is very small compared to the potential gains.
    */
    if ( == 0) {
      return;
    }
    checkRangeFromTo(fromto);
    // determine minimum and maximum.
    long min = [from];
    long max = [from];
    long[] theElements = ;
    for (int i = from + 1; i <= to;) {
      long elem = theElements[i++];
      if (elem > max) {
        max = elem;
      } else if (elem < min) {
        min = elem;
      }
    }
        quickSortFromTo(fromto);
      }

  
Trims the capacity of the receiver to be the receiver's current size. Releases any superfluous internal memory. An application can use this operation to minimize the storage of the receiver.
  public void trimToSize() {
     = org.apache.mahout.math.Arrays.trimToCapacity(size());
  }
New to GrepCode? Check out our FAQ X