<commit_before>/*
 Copyright 2009 <NAME>, <NAME>
 
 Licensed 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. 
*/

package scalala.collection.sparse;

import scala.collection.generic._;
import scala.reflect.ClassManifest;
import scala.collection.mutable._;

/**
 * <p>Nearly-drop-in replacement for Array[T](length) that does not store
 * default array values.  Internally, the SparseArray data structure
 * stores an array of indexes in packed, sorted order, and a
 * corresponding packed array of values.  Updates are linear in
 * the number of non-zero array elements, while accesses are
 * logarithmic.  This class is not threadsafe for simultaneous
 * reads and writes, but more than one thread can read simultaneously
 * if no threads are writing.</p>
 *
 * <p>Note that the DefaultArrayValue must be a constant reference -- no
 * clever tricks like creating new instances of type T are supported
 * by the nature of the way this map works.  Otherwise, iterating
 * over the size of the array would cause the SparseArray to become
 * (inefficiently) dense.</p>
 *
 * @param length The virtual length of the array.
 * @param index The indices of the array, in packed sorted order.
 * @param data The data of the array, in corresponding positions to index.
 * @param used The number of used elements in index and data.
 * @param initialActiveLength The initial length of the sparse data structures
 *   when creating new instances.
 *
 * @author dlwh, dramage
 */
final class SparseArray[@specialized T]
(val length : Int, protected var index : Array[Int], protected var data : Array[T], protected var used : Int, initialActiveLength : Int)
(implicit m : ClassManifest[T], df : DefaultArrayValue[T]) {

  def this(length : Int, initialActiveLength : Int = 3)(implicit m : ClassManifest[T], d : DefaultArrayValue[T]) =
    this(length, new Array[Int](initialActiveLength), new Array[T](initialActiveLength), 0, initialActiveLength)(m, d);

  { // check rep invariants
    require(length >= 0, "Length must be non-negative");
    require(used >= 0 && used <= length, "Used must be <= length and >= 0");
    if (used > 0) {
      require(index(0) >= 0, "Indexes must be ordered and non-negative");
      var i = 1;
      while (i < used) {
        require(index(i-1) < index(i) && index(i) >= 0, "Indexes must be ordered and non-negative");
        i +=1;
      }
    }
  }

  /** Default value. */
  val default = df.value;

  /** Iterator over used indexes and values */
  def iterator = Iterator.range(0, used).map(i => (index(i),data(i)));

  /** Used indexes. */
  def indexIterator = index.iterator.take(used);

  /** Used values. */
  def valueIterator = data.iterator.take(used);

  /** Key value pairs of non-default entries. */
  def activeIterator = indexIterator zip valueIterator;

  /** A copy of the keys in this array. */
  def indexArray : Array[Int] = index.take(used);

  /** A copy of the values in this array. */
  def valueArray : Array[T] = data.take(used);

  /**
   * Returns the offset into index and data for the requested vector
   * index.  If the requested index is not found, the return value is
   * negative and can be converted into an insertion point with ~rv.
   */
  private def findOffset(i : Int) : Int = {
    if (i < 0 || i >= length)
      throw new IndexOutOfBoundsException("Index "+i+" out of bounds [0,"+used+")");

    if (used == 0) {
      // empty list; do nothing
      return -1;
    } else if (i > index(used-1)) {
      // special case for end of list - this is a big win for growing sparse arrays
      return ~used;
    } else {
      // regular binary search from begin to end (inclusive)
      var begin = 0;
      var end = used - 1;

      // Simple optimization: position i can't be after offset i.
      if(end > i)
        end = i;

      var mid = (end + begin) >> 1;
      while (begin <= end) {
        mid = (end + begin) >> 1;
        if (index(mid) < i)
          begin = mid + 1;
        else if (index(mid) > i)
          end = mid - 1;
        else
          return i;
      }

      // no match found, return insertion point
      if (i <= index(mid))
        return ~mid;       // Insert here (before mid)
      else
        return ~(mid + 1); // Insert after mid
    }
  }

  def apply(i : Int) : T = {
    val offset = findOffset(i);
    if (offset >= 0) data(offset) else default;
  }

  def get(i: Int) : Option[T] = {<commit_msg>fix bug introduced while removing lastOffset<commit_after>/*
 Copyright 2009 <NAME>, <NAME>
 
 Licensed 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. 
*/

package scalala.collection.sparse;

import scala.collection.generic._;
import scala.reflect.ClassManifest;
import scala.collection.mutable._;

/**
 * <p>Nearly-drop-in replacement for Array[T](length) that does not store
 * default array values.  Internally, the SparseArray data structure
 * stores an array of indexes in packed, sorted order, and a
 * corresponding packed array of values.  Updates are linear in
 * the number of non-zero array elements, while accesses are
 * logarithmic.  This class is not threadsafe for simultaneous
 * reads and writes, but more than one thread can read simultaneously
 * if no threads are writing.</p>
 *
 * <p>Note that the DefaultArrayValue must be a constant reference -- no
 * clever tricks like creating new instances of type T are supported
 * by the nature of the way this map works.  Otherwise, iterating
 * over the size of the array would cause the SparseArray to become
 * (inefficiently) dense.</p>
 *
 * @param length The virtual length of the array.
 * @param index The indices of the array, in packed sorted order.
 * @param data The data of the array, in corresponding positions to index.
 * @param used The number of used elements in index and data.
 * @param initialActiveLength The initial length of the sparse data structures
 *   when creating new instances.
 *
 * @author dlwh, dramage
 */
final class SparseArray[@specialized T]
(val length : Int, protected var index : Array[Int], protected var data : Array[T], protected var used : Int, initialActiveLength : Int)
(implicit m : ClassManifest[T], df : DefaultArrayValue[T]) {

  def this(length : Int, initialActiveLength : Int = 3)(implicit m : ClassManifest[T], d : DefaultArrayValue[T]) =
    this(length, new Array[Int](initialActiveLength), new Array[T](initialActiveLength), 0, initialActiveLength)(m, d);

  { // check rep invariants
    require(length >= 0, "Length must be non-negative");
    require(used >= 0 && used <= length, "Used must be <= length and >= 0");
    if (used > 0) {
      require(index(0) >= 0, "Indexes must be ordered and non-negative");
      var i = 1;
      while (i < used) {
        require(index(i-1) < index(i) && index(i) >= 0, "Indexes must be ordered and non-negative");
        i +=1;
      }
    }
  }

  /** Default value. */
  val default = df.value;

  /** Iterator over used indexes and values */
  def iterator = Iterator.range(0, used).map(i => (index(i),data(i)));

  /** Used indexes. */
  def indexIterator = index.iterator.take(used);

  /** Used values. */
  def valueIterator = data.iterator.take(used);

  /** Key value pairs of non-default entries. */
  def activeIterator = indexIterator zip valueIterator;

  /** A copy of the keys in this array. */
  def indexArray : Array[Int] = index.take(used);

  /** A copy of the values in this array. */
  def valueArray : Array[T] = data.take(used);

  /**
   * Returns the offset into index and data for the requested vector
   * index.  If the requested index is not found, the return value is
   * negative and can be converted into an insertion point with ~rv.
   */
  private def findOffset(i : Int) : Int = {
    if (i < 0 || i >= length)
      throw new IndexOutOfBoundsException("Index "+i+" out of bounds [0,"+used+")");

    if (used == 0) {
      // empty list; do nothing
      return -1;
    } else if (i > index(used-1)) {
      // special case for end of list - this is a big win for growing sparse arrays
      return ~used;
    } else {
      // regular binary search from begin to end (inclusive)
      var begin = 0;
      var end = used - 1;

      // Simple optimization: position i can't be after offset i.
      if(end > i)
        end = i;

      var mid = (end + begin) >> 1;
      while (begin <= end) {
        mid = (end + begin) >> 1;
        if (index(mid) < i)
          begin = mid + 1;
        else if (index(mid) > i)
          end = mid - 1;
        else
          return mid;
      }

      // no match found, return insertion point
      if (i <= index(mid))
        return ~mid;       // Insert here (before mid)
      else
        return ~(mid + 1); // Insert after mid
    }
  }

  def apply(i : Int) : T = {
    val offset = findOffset(i);
    if (offset >= 0) data(offset) else default;
  }

  def get(i: Int) : Option[T] = {
{'fraction_non_alphanumeric': 0.10737981014596305, 'fraction_numerical': 0.00694090027559457, 'mean_word_length': 2.9192, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 47, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '675457', 'n_tokens_mistral': 2857, 'n_tokens_neox': 2742, 'n_words': 1197}