dart sparseintvector new (still 50x slower than java)

sparseintvector2.dart

#import('dart:math');

class SparseIntVector {

  static int collision = 0;
  static final int INITIAL_SIZE = 8;
  static final double DEFAULT_LOAD_FACTOR = 0.7;
  int modulo = INITIAL_SIZE - 1;
  List<int> keys;
  List<int> values;
  int keyCount = 0;
  int threshold = (INITIAL_SIZE * DEFAULT_LOAD_FACTOR).toInt();

  _initializeForSize(int size) {
    keys = new List<int>(size);
    values = new List<int>(size);
    for (int i=0; i<keys.length; i++) {
     keys[i] = 0;
     values[i] = 0;
    }
  }

  SparseIntVector() {
    _initializeForSize(INITIAL_SIZE);
  }

  SparseIntVector.forSize(int size) {
    if (size < 2)
      size = 2;
    if ((size & (size - 1)) != 0) {
      int power = (log(size) / log(2)).toInt();
      size = 1 << (power + 1);
    }
    _initializeForSize(size);
    threshold = (size * DEFAULT_LOAD_FACTOR).toInt();
    modulo = size - 1;
  }

  int hash(int key) {
    return key & modulo;
  }

  int locate(int key) {
    int slot = hash(key);
    while (true) {
      if (values[slot] == 0)
        return -slot - 1;
      if (keys[slot] == key)
        return slot;
      collision++;
      slot = (slot + 1) & modulo;
    }
  }

  int increment(int key) {
    return incrementByAmount(key, 1);
  }

  int operator [](int key) {
    int l = locate(key);
    return l < 0 ? 0 : values[l];
  }

  int decrement(int key) {
    return incrementByAmount(key, -1);
  }

  int incrementByAmount(int key, int amount) {
    int k = locate(key);
    if (k < 0) {
      k = -k - 1;
      if (keyCount == threshold) {
        expand();
      }
      values[k] = amount;
      keys[k] = key;
      keyCount++;
      return values[k];
    } else {
      values[k] += amount;
      if (values[k] == 0)
        keyCount--;
      return values[k];
    }
 }

  void remove(int key) {
    int k = locate(key);
    if (k < 0)
      return;
    values[k] = 0;
    keyCount--;
  }

  void expand() {
    List<int> oldKeys = keys;
    List<int> oldValues = values;
    int oldSize = oldKeys.length;
    int newSize = oldSize * 2;
    keys = new List<int>(newSize);
    values = new List<int>(newSize);
    _initializeForSize(newSize);
    keyCount = 0;
    threshold = (newSize * DEFAULT_LOAD_FACTOR).toInt();
    modulo = newSize - 1;
    for (int i = 0; i < oldSize; i++) {
      if (oldKeys[i] != 0) {
        this[oldKeys[i]] = oldValues[i];
      }
    }
  }

  void operator []=(int key, int value) {
    int loc = locate(key);
    if (loc >= 0) {
      values[loc] = value;
      return;
    }
    if (keyCount == threshold) {
      expand();
    }
    loc = -loc - 1;
    keys[loc] = key;
    values[loc] = value;
    keyCount++;
  }

  int size() {
    return keyCount;
  }

  int capacity() {
    return keys.length;
  }

}

void main() {
  var siv = new SparseIntVector.forSize(8);
  List<int> randoms = new List<int>(10000);

  int iters = 500;
  Random r = new Random(0xCAFEBABE);
  for (int i=0; i<randoms.length; i++) {
    randoms[i] = r.nextInt(1000000);
  }

  Stopwatch sw = new Stopwatch();
  sw.start();
  for (int i=0; i<iters; i++) {
    siv = new SparseIntVector();
    for (int j=0; j<randoms.length; j++) {
      siv[randoms[j]] = randoms[j];
      siv.increment(randoms[j]);
      siv.decrement(randoms[j]);
    }
  }
  print("time: ${sw.elapsedInMs()}ms. Collisions:${SparseIntVector.collision}");
}