/**
 * Copyright (C) 2012 Ness Computing, Inc.
 *
 * 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 com.nesscomputing.sequencer;

import java.util.Collections;
import java.util.List;

import javax.annotation.concurrent.NotThreadSafe;

import com.google.common.collect.Lists;

import gnu.trove.map.TObjectIntMap;
import gnu.trove.map.hash.TObjectIntHashMap;

/**
 * Maps a sparse range of keys to a dense range (starting at 0).
 *
 * @param <K> the type of sparse keys to map
 */
@NotThreadSafe
public class HashSequencer<K> extends AbstractSequencer<K> {
    private static final long serialVersionUID = 1L;

    private final TObjectIntHashMap<K> keyToInt;
    private final List<K> intToKey;
    private int nextInt = 0;

    public HashSequencer() {
        keyToInt = new TObjectIntHashMap<K>();
        intToKey = Lists.newArrayList();
    }

    private HashSequencer(Sequencer<K> other) {
        keyToInt = new TObjectIntHashMap<K>(other.size());
        intToKey = Lists.newArrayListWithCapacity(other.size());

        this.nextInt = other.size();
        for (int i = 0; i < this.nextInt; i++) {
            K key = other.unsequence(i);
            this.intToKey.add(key);
            this.keyToInt.put(key, i);
        }
    }

    public static <K> HashSequencer<K> copyOf(Sequencer<K> other)
    {
        return new HashSequencer<K>(other);
    }

    @Override
    public List<K> getKeys() {
        return Collections.unmodifiableList(intToKey);
    }

    @Override
    public int sequenceOrAdd(K key) {
        int result = keyToInt.get(key);
        if (result == keyToInt.getNoEntryValue() && !keyToInt.containsKey(key)) {
            keyToInt.put(key, result = nextInt);
            intToKey.add(key);
            nextInt++;
        }

        return result;
    }

    @Override
    public boolean containsKey(Object key) {
        return keyToInt.containsKey(key);
    }

    @Override
    public int sequenceIfExists(K key) {
        int val = keyToInt.get(key);

        if (val == keyToInt.getNoEntryValue() && !keyToInt.containsKey(key))
            return -1;

        return val;
    }

    @Override
    public void sequenceExisting(Iterable<K> keys, TObjectIntMap<K> result)
    {
        for (K key : keys) {
            int val = keyToInt.get(key);
            if (val != keyToInt.getNoEntryValue() || keyToInt.containsKey(key)) {
                result.put(key, val);
            }
        }
    }

    @Override
    public K unsequence(int index) {
        return intToKey.get(index);
    }

    @Override
    public int size() {
        return nextInt;
    }
}

@@ -1113,16 +1113,67 @@
 ID = 1L;
+%0A    private static final float LOAD_FACTOR = 0.5f;
 %0A%0A    pr
@@ -1286,21 +1286,22 @@
 ;%0A%0A    p
-ublic
+rivate
  HashSeq
@@ -1307,16 +1307,32 @@
 quencer(
+int startingSize
 ) %7B%0A    
@@ -1371,16 +1371,45 @@
 hMap%3CK%3E(
+startingSize, LOAD_FACTOR, -1
 );%0A     
@@ -1440,17 +1440,41 @@
 rrayList
-(
+WithCapacity(startingSize
 );%0A    %7D
@@ -1519,24 +1519,136 @@
 K%3E other) %7B%0A
+        this(other.size(), other.getKeys());%0A    %7D%0A%0A    private HashSequencer(int size, Iterable%3CK%3E elements) %7B%0A
         keyT
@@ -1679,28 +1679,37 @@
 hMap%3CK%3E(
-other.size()
+size, LOAD_FACTOR, -1
 );%0A     
@@ -1753,28 +1753,20 @@
 apacity(
-other.
 size
-()
 );%0A%0A    
@@ -2254,32 +2254,113 @@
 eOrAdd(K key) %7B%0A
+        assert keyToInt.getNoEntryValue() == -1 : %22noEntryValue must be == -1%22;%0A%0A
         int resu
@@ -2435,38 +2435,8 @@
 ue()
- && !keyToInt.containsKey(key)
 ) %7B%0A
@@ -2754,138 +2754,79 @@
     
-int val = keyToInt.get(key);%0A%0A        if (val == keyToInt.getNoEntryValue() && !keyToInt.containsKey(key))%0A            return
+assert keyToInt.getNoEntryValue() == -1 : %22noEntryValue must be ==
  -1
+%22
 ;
-%0A
 %0A   
@@ -2837,19 +2837,33 @@
  return 
-val
+keyToInt.get(key)
 ;%0A    %7D%0A
@@ -2951,32 +2951,112 @@
 %3E result)%0A    %7B%0A
+        assert keyToInt.getNoEntryValue() == -1 : %22noEntryValue must be == -1%22;%0A
         for (K k
@@ -3162,37 +3162,8 @@
 ue()
- %7C%7C keyToInt.containsKey(key)
 ) %7B%0A

Improve HashSequencer performance by using -1 as the noEntryValue