public final class CustomWidthArray implements Serializable
{

	public int getKeyWidth() {
		return keyWidth;
	}

	private static final long serialVersionUID = 1L;

	private final static int LOG2_BITS_PER_WORD = 6;

	private final static int BITS_PER_WORD = 1 << LOG2_BITS_PER_WORD;

	private final static int WORD_MASK = BITS_PER_WORD - 1;

	private long size;

	private final int keyWidth;

	private final int fullWidth;

	final long widthDiff;

	private final LongArray data;

	private final static long numLongs(final long size) {
		return ((size + WORD_MASK) >>> LOG2_BITS_PER_WORD);
	}

	private final static long word(final long index) {
		return (index >>> LOG2_BITS_PER_WORD);
	}

	private final static long bit(final long index) {
		return (index & WORD_MASK);
	}

	private final static long mask(final long index) {
		return 1L << (index & WORD_MASK);
	}

	public CustomWidthArray(final long numWords, final int keyWidth) {
		this(numWords, keyWidth, keyWidth);
	}

	public CustomWidthArray(final long numWords, final int keyWidth, final int fullWidth) {
		assert keyWidth > 0;
		assert fullWidth > 0;
		this.keyWidth = keyWidth;
		this.fullWidth = fullWidth;
		this.widthDiff = Long.SIZE - keyWidth;
		final long numBits = numWords * fullWidth;
		data = new LongArray(numLongs(numBits));// new long[numLongs(numBits)];
		size = 0;
	}

	private long length() {
		return size;
	}

	public void ensureCapacity(final long numWords) {
		final long numBits = numWords * fullWidth;
		final long numLongs = numLongs(numBits);
		data.ensureCapacity(numLongs);
		if (numLongs > data.size()) data.setAndGrowIfNeeded(numLongs - 1, 0);
	}

	public void trim() {
		trimToSize(size);
	}

	/**
	 * @param sizeHere
	 */
	public void trimToSize(final long sizeHere) {
		final long numBits = sizeHere * fullWidth;
		data.trimToSize(numLongs(numBits));
	}

	private void rangeCheck(final long index) {
		if (index >= length()) { //
			throw new IndexOutOfBoundsException("Index (" + index + ") is greater than length (" + (length()) + ")");
		}
	}

	public boolean getBit(final long index) {
		rangeCheck(index);
		return (data.get(word(index)) & mask(index)) != 0;
	}

	public void clear(final long index) {
		rangeCheck(index);
		data.set(word(index), data.get(word(index)) & ~mask(index));
	}

	private long getLong(final long from, final long l) {
		if (l == Long.SIZE) return 0;
		final long startWord = word(from);
		final long startBit = bit(from);
		if (startBit <= l)
			return data.get(startWord) << l - startBit >>> l;
		else
			return data.get(startWord) >>> startBit | data.get(startWord + 1) << Long.SIZE + l - startBit >>> l;
	}

	public boolean add(final long value) {
		return addHelp(value, true);
	}

	public boolean addWithFixedCapacity(final long value) {
		return addHelp(value, false);
	}

	/**
	 * @param value
	 * @return
	 */
	private boolean addHelp(final long value, final boolean growCapacity) {
		assert fullWidth == keyWidth;
		final long length = this.size * fullWidth;
		final long startWord = word(length);
		final long startBit = bit(length);
		if (growCapacity) ensureCapacity(this.size + 1);

		if (startBit + keyWidth <= Long.SIZE)
			data.set(startWord, data.get(startWord) | (value << startBit));
		else {
			data.set(startWord, data.get(startWord) | (value << startBit));
			data.set(startWord + 1, value >>> BITS_PER_WORD - startBit);
		}

		this.size++;
		return true;
	}

	public long get(final long index) {
		return getHelp(index, 0, keyWidth);
	}

	public long get(final long index, int offset, int width) {
		return getHelp(index, offset, width);
	}

	/**
	 * @param index
	 * @return
	 */
	private long getHelp(final long index, int offset, int width) {
		final long start = index * fullWidth + offset;
		return getLong(start, Long.SIZE - width);
	}

	public static int numBitsNeeded(final long n) {
		if (n == 0) return 1;
		if (Long.bitCount(n) == 1)
			return Long.numberOfTrailingZeros(n) + 1;
		else
			return Long.SIZE - Long.numberOfLeadingZeros(n - 1);
	}

	public void set(final long index, final long value) {
		rangeCheck(index);
		final int offset = 0;
		final int width = keyWidth;
		setHelp(index, value, offset, width);
	}

	public void set(final long index, final long value, final int offset, final int width) {
		rangeCheck(index);
		setHelp(index, value, offset, width);
	}

	/**
	 * @param index
	 * @param value
	 * @param offset
	 */
	private void setHelp(final long index, final long value, final int offset, final int width) {

		assert numBitsNeeded(value) <= width : "Value " + value + " bits " + width;
		final long start = index * fullWidth + offset;
		final long startWord = word(start);
		final long endWord = word(start + width - 1);
		final long startBit = bit(start);
		final long fullMask = width == Long.SIZE ? -1L : ((1L << width) - 1);

		if (startWord == endWord) {
			long startWordLong = data.get(startWord);
			startWordLong &= ~(fullMask << startBit);
			startWordLong |= value << startBit;
			data.set(startWord, startWordLong);

			assert value == (startWordLong >>> startBit & fullMask) : startWord + " " + startBit + " " + value;
		} else {
			// Here startBit > 0.
			long startWordLong = data.get(startWord);
			startWordLong &= ((1L << startBit) - 1);
			startWordLong |= (value << startBit);
			data.set(startWord, startWordLong);
			long endWordLong = data.get(endWord);
			endWordLong &= (-(1L << width - BITS_PER_WORD + startBit));
			endWordLong |= (value >>> BITS_PER_WORD - startBit);
			data.set(endWord, endWordLong);

			assert value == (startWordLong >>> startBit | endWordLong << (BITS_PER_WORD - startBit) & fullMask);
		}
	}

	public void setAndGrowIfNeeded(final long pos, final long value) {
		if (pos >= size) {
			ensureCapacity(pos + 2);
			this.size = pos + 1;
		}
		set(pos, value);
	}

	public void setAndGrowIfNeeded(final long pos, final long value, final int offset, final int width) {
		if (pos >= size) {
			ensureCapacity(pos + 2);
			this.size = pos + 1;
		}
		set(pos, value, offset, width);
	}

	public long size() {
		return length();
	}

	public void fill(final long l, final long n) {
		final long numBits = n * fullWidth;
		final long numLongs = numLongs(numBits);
		data.fill(l, numLongs);
		size = Math.max(n, size);
	}

	public long linearSearch(final long key, final long rangeStart, final long rangeEnd, final long startIndex, final long emptyKey,
		final boolean returnFirstEmptyIndex) {
		for (long i = startIndex; i < rangeEnd; ++i) {
			final long searchKey = getHelp(i, 0, keyWidth);
			if (searchKey == key) return i;
			if (searchKey == emptyKey) return returnFirstEmptyIndex ? i : -1L;
		}
		for (long i = rangeStart; i < startIndex; ++i) {
			final long searchKey = getHelp(i, 0, keyWidth);
			if (searchKey == key) return i;
			if (searchKey == emptyKey) return returnFirstEmptyIndex ? i : -1L;
		}
		return -1L;
	}

	public void incrementCount(final long index, final long count) {
		if (index >= size()) {
			setAndGrowIfNeeded(index, count);
		} else {
			final long curr = get(index);
			set(index, curr + count);
		}
	}

	public int getFullWidth() {
		return fullWidth;
	}

} public final class LongArray implements Serializable
{

	/**
	 * 
	 */
	private static final long serialVersionUID = -9133624434714616987L;

	/**
	 * For some reason, some VMs will refuse to allocate long[] arrays of size
	 * Integer.MAX_VALUE, so we stick to at most MAX_VALUE / 2
	 */
	private static final int MAX_ARRAY_BITS = 30;

	private static final int MAX_ARRAY_SIZE = 1 << MAX_ARRAY_BITS;

	long size;

	long[][] data;

	// keep a reference to the lowest order array, since that will be used most often
	private long[] first;

	public LongArray(final long initialCapacity) {
		this.size = 0;
		allocFor(initialCapacity, null);
	}

	public static final class StaticMethods
	{
		public static LongArray newLongArray(final long maxKeySize, final long maxNumKeys) {
			return newLongArray(maxKeySize, maxNumKeys, 10);
		}

		public static LongArray newLongArray(@SuppressWarnings("unused") final long maxKeySize, @SuppressWarnings("unused") final long maxNumKeys,
			final long initCapacity) {
			return new LongArray(initCapacity);
		}
	}

	/**
	 * @param capacity
	 */
	private void allocFor(final long capacity, final long[][] old) {
		final int numOuter = o(capacity) + 1;
		final int numInner = i(capacity);
		this.data = new long[numOuter][];
		for (int i = 0; i < numOuter; ++i) {
			final int currSize = (i == numOuter - 1) ? numInner : MAX_ARRAY_SIZE;
			if (old == null || i >= old.length) {
				data[i] = new long[currSize];
			} else if (currSize == old[i].length) {
				data[i] = old[i];
			} else {
				data[i] = Arrays.copyOf(old[i], currSize);
			}
			if (i == 0) first = data[i];
		}
	}

	protected static final int o(final long l) {
		return (int) (l >>> MAX_ARRAY_BITS);
	}

	protected static final int i(final long l) {
		return (int) (l & (MAX_ARRAY_SIZE - 1));
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see edu.berkeley.nlp.mt.lm.util.collections.LongArray#set(long, long)
	 */
	public void set(final long pos, final long val) {
		if (pos >= size) throw new ArrayIndexOutOfBoundsException("" + pos);
		setHelp(pos, val);

	}

	/**
	 * @param pos
	 * @param val
	 */
	private void setHelp(final long pos, final long val) {
		data[o(pos)][i(pos)] = val;
	}

	private void incrementHelp(final long pos, final long val) {
		data[o(pos)][i(pos)] += val;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see
	 * edu.berkeley.nlp.mt.lm.util.collections.LongArray#setAndGrowIfNeeeded
	 * (long, long)
	 */
	public void setAndGrowIfNeeded(final long pos, final long val) {
		ensureCapacity(pos + 1);
		setGrowHelp(pos, val);
	}

	public void setAndGrowIfNeededFill(final long pos, final long val) {
		ensureCapacity(pos + 1);
		final long oldSize = size;
		size = Math.max(size, pos + 1);
		for (long i = oldSize; i < size; ++i)
			setHelp(i, val);
	}

	/**
	 * @param pos
	 * @param val
	 */
	private void setGrowHelp(final long pos, final long val) {
		size = Math.max(size, pos + 1);
		setHelp(pos, val);

	}

	public void ensureCapacity(final long minCapacity) {
		final long oldCapacity = sizeOf(data);
		if (minCapacity > oldCapacity) {
			final long[][] oldData = data;
			long newCapacity = (oldCapacity * 3) / 2 + 1;
			if (newCapacity < minCapacity) newCapacity = minCapacity;

			allocFor(newCapacity, oldData);
		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see edu.berkeley.nlp.mt.lm.util.collections.LongArray#get(long)
	 */
	public long get(final long pos) {
		assert (pos < size) : this.getClass().getName() + " array index out of bounds";
		return getHelp(pos);
	}

	private static long sizeOf(final long[][] a) {
		long ret = 0;
		for (int i = 0; i < a.length; ++i) {
			ret += a[i].length;
		}
		return ret;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see edu.berkeley.nlp.mt.lm.util.collections.LongArray#trim()
	 */
	public void trim() {
		allocFor(size, data);
	}

	/**
	 * @param pos
	 * @return
	 */
	private long getHelp(final long pos) {
		final int i = i(pos);
		final int o = o(pos);
		return o == 0 ? first[i] : data[o][i];
	}

	public static void main(final String[] argv) {

		long mem = Runtime.getRuntime().maxMemory();
		System.out.println("VM size is " + mem);
		long pos = -9L + Integer.MAX_VALUE / 2;//;4L + Integer.MAX_VALUE;
		final LongArray b = new LongArray(pos + 1);
		final long val = 10000000000000L;
		b.setAndGrowIfNeeded(pos, val);
		final long z = b.get(pos);
		assert z == val;
		System.out.println("Finished with value " + z + " for " + val);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see edu.berkeley.nlp.mt.lm.util.collections.LongArray#size()
	 */
	public long size() {
		return size;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see edu.berkeley.nlp.mt.lm.util.collections.LongArray#add(long)
	 */
	public boolean add(final long val) {
		setAndGrowIfNeeded(size, val);
		return true;
	}

	public boolean addWithFixedCapacity(final long val) {
		setGrowHelp(size, val);
		return true;
	}

	public void shift(final long src, final long dest, final int length) {
		if (length == 0) return;
		if (src == dest) return;
		assert dest >= src;

		final int oStart = o(src);
		final int oEnd = o(src + length);
		final int oDestStart = o(dest);
		final int oDestEnd = o(dest + length);
		if (dest + length >= size) {
			setAndGrowIfNeeded(dest + length, 0);
		}
		if (oStart != oEnd || oDestStart != oDestEnd) {
			for (long i = length - 1; i >= 0; --i) {
				set(dest + i, get(src + i));
			}
		} else {
			System.arraycopy(data[o(src)], i(src), data[o(dest)], i(dest), length);
		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see edu.berkeley.nlp.mt.lm.util.collections.LongArray#trimToSize(long)
	 */
	public void trimToSize(final long size_) {
		this.size = size_;
		allocFor(size_, data);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see edu.berkeley.nlp.mt.lm.util.collections.LongArray#fill(long, long)
	 */
	public void fill(final long l, final long n) {
		for (long i = 0; i < n; ++i)
			setAndGrowIfNeeded(i, l);
	}

	public long linearSearch(final long key, final long rangeStart, final long rangeEnd, final long startIndex, final long emptyKey,
		final boolean returnFirstEmptyIndex) {
		for (long i = startIndex; i < rangeEnd; ++i) {
			final long searchKey = getHelp(i);
			if (searchKey == key) return i;
			if (searchKey == emptyKey) return returnFirstEmptyIndex ? i : -1L;
		}
		for (long i = rangeStart; i < startIndex; ++i) {
			final long searchKey = getHelp(i);
			if (searchKey == key) return i;
			if (searchKey == emptyKey) return returnFirstEmptyIndex ? i : -1L;
		}
		return -1L;
	}

	public void incrementCount(final long index, final long count) {
		if (index >= size) {
			setAndGrowIfNeeded(index, count);
		} else {
			incrementHelp(index, count);
		}
	}

} public final class BitList
{

	private final BitSet data;

	private int numBits;

	public BitList() {
		data = new BitSet();
		numBits = 0;
	}

	public void add(final boolean b) {
		set(numBits, b);
	}

	public boolean get(final int i) {
		if (i >= size()) throw new IndexOutOfBoundsException();
		return data.get(i);
	}

	public int size() {
		return numBits;
	}

	private void set(final int index, final boolean b) {
		data.set(index, b);
		numBits = Math.max(numBits, index + 1);
	}

	@Override
	public String toString() {
		final StringBuilder s = new StringBuilder("");
		long l = 0L;
		String hex = "";
		for (int i = 0; i < numBits; ++i) {
			final boolean curr = data.get(i);
			if (i % Long.SIZE == 0 && i > 0) {
				hex += String.format("%x", l);
				l = 0;
			}
			l = (l << 1) | (curr ? 1 : 0);
			s.append(curr ? "1" : "0");
		}
		return s.toString() + "(" + hex + ")";
	}

	public void addAll(final BitList bits) {
		for (int i = 0; i < bits.size(); ++i)
			add(bits.get(i));
	}

	public void addLong(final long l) {
		final int size = Long.SIZE;
		addHelp(l, size);
	}

	/**
	 * @param l
	 * @param size
	 */
	private void addHelp(final long l, final int size) {
		for (int b = size - 1; b >= 0; --b) {
			add((l & (1L << b)) != 0);
		}
	}

	public void addShort(final short l) {
		addHelp(l, Short.SIZE);
	}

	public void clear() {
		numBits = 0;
	}

} public final class BitStream
{

	private static final long LOG_LONG_SIZE = Long.SIZE - Long.numberOfLeadingZeros(Long.SIZE - 1);

	private static final long LOG_LONG_MASK = (1L << LOG_LONG_SIZE) - 1;

	private static final long HIGH_BIT_MASK = (1L << (Long.SIZE - 1));

	private final LongArray data;

	private final long start;

	private long currLong = -1;

	private long currPos = -1;

	private int relBit;

	private long markedCurrPos = -1;

	private int markedRelBit = -1;

	private final int numBits;

	private final int startBit;

	public BitStream(final LongArray data, final long start, final int startBit, final int numBits) {
		this.data = data;
		this.start = start;
		this.currPos = 0;
		this.numBits = numBits;
		this.startBit = startBit;
		currLong = data.get(start) << startBit;
		this.relBit = startBit;
	}

	public boolean nextBit() {
		assert !finished();
		if (relBit == Long.SIZE) advanceToNextLong();
		final boolean ret = (currLong & HIGH_BIT_MASK) != 0;
		relBit++;
		currLong <<= 1;
		if (relBit == Long.SIZE) {
			advanceToNextLong();
		}
		return ret;
	}

	/**
	 * Reads a string of zeros followed by a 1.
	 * 
	 * @return the number of consecutive zeros (plus 1)
	 */
	public int nextConsecutiveZeros() {
		final int numberOfLeadingZerosOnThisWord = Long.numberOfLeadingZeros(currLong);
		final int numLeft = Long.SIZE - relBit;
		if (numberOfLeadingZerosOnThisWord >= numLeft) {
			advanceToNextLong();
			final int numberOfLeadingZerosOnNextWord = Long.numberOfLeadingZeros(currLong);
			advanceWithinCurrLong(numberOfLeadingZerosOnNextWord + 1);
			return numberOfLeadingZerosOnNextWord + 1 + numLeft;
		} else {
			final int headerLength = numberOfLeadingZerosOnThisWord + 1;
			advanceWithinCurrLong(headerLength);
			return headerLength;
		}
	}

	/**
	 * Read and return next n bits.
	 * 
	 * @param n
	 * @return
	 */
	public long next(final int n) {
		assert n <= Long.SIZE;
		assert !finished();
		final int leftOnThisWord = Math.min(n, Long.SIZE - relBit);
		final int onNextWord = n - leftOnThisWord;
		final int thisWordShift = Long.SIZE - leftOnThisWord;
		long ret = currLong >>> thisWordShift;
		if (onNextWord > 0) {
			advanceToNextLong();
			final int nextWordShift = Long.SIZE - onNextWord;
			ret <<= onNextWord;
			ret |= currLong >>> nextWordShift;
			advanceWithinCurrLong(onNextWord);
		} else {
			advanceWithinCurrLong(leftOnThisWord);
		}
		return ret;
	}

	/**
	 * 
	 */
	private void advanceWithinCurrLong(final int n) {
		assert relBit + n <= Long.SIZE;
		relBit += n;
		currLong <<= n;

	}

	private void advanceToNextLong() {
		currPos++;
		relBit = 0;
		currLong = data.get(start + currPos);
	}

	public boolean finished() {
		return numBitsLeft() <= 0;
	}

	public void rewind(final int i) {
		shiftAbsPosition(-i);
	}

	private void shiftAbsPosition(final int i) {
		final long absBit = (currPos << LOG_LONG_SIZE) + relBit;
		final long rewound = absBit + i;
		final int newRelBit = (int) (rewound & LOG_LONG_MASK);
		final long newPos = rewound >>> LOG_LONG_SIZE;
		reset(newRelBit, newPos);
	}

	private void reset(final int newRelBit, final long newPos) {
		relBit = newRelBit;
		currPos = newPos;
		currLong = data.get(start + currPos) << relBit;
	}

	public int numBitsLeft() {
		return (int) (numBits + startBit - ((currPos << LOG_LONG_SIZE) + relBit));
	}

	/**
	 * Advances without returning any bits.
	 * 
	 * @param n
	 */
	public void advance(final int n) {
		shiftAbsPosition(n);
	}

	/**
	 * Sets a mark at the current bit that can be returned to using
	 * rewindToMark.
	 */
	public void mark() {
		assert markedCurrPos < 0 : "Tried to double mark";
		markedCurrPos = currPos;
		markedRelBit = relBit;
	}

	public void rewindToMark() {
		reset(markedRelBit, markedCurrPos);
		markedCurrPos = -1;
		markedRelBit = -1;
	}

} public final class VariableLengthBitCompressor implements Serializable
{
	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;

	private final int radix;

	public VariableLengthBitCompressor(final int radix) {
		this.radix = radix;
	}

	public BitList compress(final long n) {
		return CompressionUtils.variableCompress(n, radix);
	}

	public long decompress(final BitStream bits) {
		return CompressionUtils.variableDecompress(bits, radix);
	}

} public class Indexer<E extends Comparable<E>> implements Serializable
{
	private static final long serialVersionUID = -8769544079136550516L;

	protected ArrayList<E> objects;

	protected TIntMap<E> indexes;

	protected boolean locked = false;

	private Semaphore sem;

	public void lock() {
		this.locked = true;
	}

	public E getObject(final int index) {
		return objects.get(index);
	}

	public boolean add(final E elem) {
		final int oldSize = size();
		return getIndex(elem) >= oldSize;
	}

	/**
	 * Returns the number of objects indexed.
	 */
	public int size() {
		return objects.size();
	}

	/**
	 * Returns the index of the given object, or -1 if the object is not present
	 * in the indexer.
	 * 
	 * @param o
	 * @return
	 */
	public int indexOf(final E o) {
		final int index = indexes.get(o, -1);

		return index;
	}

	/**
	 * Return the index of the element If doesn't exist, add it.
	 */
	public int getIndex(final E e) {
		if (e == null) return -1;

		if (sem != null) sem.acquireUninterruptibly();
		int index = indexes.get(e, -1);
		if (index < 0) {
			if (locked) throw new RuntimeException("Attempt to add to locked indexer");
			index = size();
			objects.add(e);
			assert size() >= 0 : "Too many objects in indexer";
			indexes.put(e, index);
		}
		if (sem != null) sem.release();
		return index;
	}

	public Indexer(final boolean sync) {
		objects = new ArrayList<E>();
		indexes = new TIntMap<E>();
		this.sem = sync ? new Semaphore(1) : null;
	}

	public Indexer() {
		this(false);
	}

	public Indexer(final Collection<? extends E> c) {
		this();
		for (final E a : c)
			getIndex(a);
	}

	/**
	 * Save some space my compacting underlying maps and lists.
	 */
	public void trim() {
		objects.trimToSize();
		//		indexes.switchToSortedList();
	}

	public Iterable<E> getObjects() {
		return Collections.unmodifiableList(objects);
	}

} public final class LongToIntHashMap
{

	private long[] keys;

	private int[] values;

	private int size = 0;

	private static final int EMPTY_VAL = -1;

	private double maxLoadFactor = 0.5;

	private boolean sorted = false;

	//	private int deflt = -1;

	public LongToIntHashMap() {
		this(5);
	}

	public void setLoadFactor(double loadFactor) {
		this.maxLoadFactor = loadFactor;
		ensureCapacity(values.length);
	}

	public LongToIntHashMap(int initCapacity_) {
		int initCapacity = toSize(initCapacity_);
		keys = new long[initCapacity];
		values = new int[initCapacity];
		Arrays.fill(values, EMPTY_VAL);
	}

	public String toString() {
		String s = "[";
		for (Entry entry : primitiveEntries()) {
			s += s.length() == 1 ? "" : " ";
			s += "(" + entry.key + "," + entry.value + ")";
		}
		s += "]";
		return s;
	}

	public void toSorted() {
		sorted = true;
		long[] newKeys = new long[size];
		int[] newValues = new int[size];
		List<Entry> sortedEntries = new ArrayList<Entry>(size);
		for (java.util.Map.Entry<Long, Integer> e : entries()) {
			sortedEntries.add((Entry) e);
		}
		Collections.sort(sortedEntries, new Comparator<Entry>()
		{

			public int compare(Entry o1, Entry o2) {
				return Double.compare(o1.key, o2.key);
			}
		});
		int k = 0;
		for (Entry e : sortedEntries) {
			newKeys[k] = e.getKey();
			newValues[k] = e.getValue();
			k++;
		}
		keys = newKeys;
		values = newValues;
	}

	/**
	 * @param initCapacity_
	 * @return
	 */
	private int toSize(int initCapacity_) {
		return Math.max(5, (int) (initCapacity_ / maxLoadFactor) + 1);
	}

	public void put(Long k, int v) {
		checkNotImmutable();
		if (size / (double) keys.length > maxLoadFactor) {
			rehash();
		}
		putHelp(k, v, keys, values);

	}

	public void incrementCount(long k, int d) {
		checkNotImmutable();
		if (d == 0) return;
		int pos = find(k, false);
		if (pos == EMPTY_VAL || pos == EMPTY_VAL)
			put(k, d);
		else
			values[pos] += d;

	}

	/**
	 * 
	 */
	private void checkNotImmutable() {
		if (keys == null) throw new RuntimeException("Cannot change wrapped IntCounter");
		if (sorted) throw new RuntimeException("Cannot change sorted IntCounter");
	}

	/**
	 * 
	 */
	private void rehash() {
		final int length = keys.length * 2 + 1;
		rehash(length);
	}

	/**
	 * @param length
	 */
	private void rehash(final int length) {
		checkNotImmutable();
		long[] newKeys = new long[length];
		int[] newValues = new int[length];
		Arrays.fill(newValues, EMPTY_VAL);
		size = 0;
		for (int i = 0; i < keys.length; ++i) {
			long curr = keys[i];
			int val = values[i];
			if (val != EMPTY_VAL) {
				putHelp(curr, val, newKeys, newValues);
			}
		}
		keys = newKeys;
		values = newValues;
	}

	/**
	 * @param k
	 * @param v
	 */
	private boolean putHelp(long k, int v, long[] keyArray, int[] valueArray) {
		checkNotImmutable();
		assert v >= 0;
		int pos = find(k, true, keyArray, valueArray);
		//		int pos = getInitialPos(k, keyArray);
		//		long currKey = keyArray[pos];
		//		while (currKey != EMPTY_KEY && currKey != k) {
		//			pos++;
		//			if (pos == keyArray.length) pos = 0;
		//			currKey = keyArray[pos];
		//		}
		//
		boolean wasEmpty = valueArray[pos] == EMPTY_VAL;
		valueArray[pos] = v;
		if (wasEmpty) {
			size++;
			keyArray[pos] = k;
			return true;
		}
		return false;
	}

	/**
	 * @param k
	 * @param keyArray
	 * @return
	 */
	private static int getInitialPos(final long k, final int length) {
		if (length < 0) return (int) k;
		long hash = MurmurHash.hashOneLong(k, 31);
		if (hash < 0) hash = -hash;
		int pos = (int) (hash % length);
		return pos;
	}

	public int get(long k, int def) {
		int pos = find(k, false);
		if (pos == EMPTY_VAL) return def;

		return values[pos];
	}

	private int find(long k, boolean returnLastEmpty) {
		return find(k, returnLastEmpty, keys, values);
	}

	/**
	 * @param k
	 * @return
	 */
	private int find(long k, boolean returnLastEmpty, long[] keyArray, int[] valueArray) {
		if (keyArray == null) {
			return (int) (k < valueArray.length ? k : EMPTY_VAL);
		} else if (sorted) {
			final int pos = Arrays.binarySearch(keyArray, k);
			return pos < 0 ? EMPTY_VAL : pos;

		} else {
			final int[] localValues = valueArray;
			final int length = localValues.length;
			int pos = getInitialPos(k, localValues.length);
			int currVal = localValues[pos];
			long curr = keyArray[pos];
			while (currVal != EMPTY_VAL && curr != k) {
				pos++;
				if (pos == length) pos = 0;
				currVal = localValues[pos];
				curr = keyArray[pos];
			}
			return returnLastEmpty ? pos : (currVal == EMPTY_VAL ? EMPTY_VAL : pos);
		}
	}

	//	public void setDefault(int d) {
	//		this.deflt = d;
	//	}

	public boolean isEmpty() {
		return size == 0;
	}

	public class Entry implements Map.Entry<Long, Integer>, Comparable<Entry>
	{
		private int index;

		public long key;

		public int value;

		public Entry(long key, int value, int index) {
			super();
			this.key = key;
			assert value >= 0;
			this.value = value;
			this.index = index;
		}

		public Long getKey() {
			return key;
		}

		public Integer getValue() {
			return value;
		}

		public Integer setValue(Integer value) {
			this.value = value;
			values[index] = value;
			return this.value;
		}

		@Override
		public int compareTo(Entry o) {
			// sortable by *value*
			return Double.compare(value, o.value);
		}
	}

	private class EntryIterator extends MapIterator<Map.Entry<Long, Integer>>
	{
		public Entry next() {
			final int nextIndex = nextIndex();
			return new Entry(keys == null ? nextIndex : keys[nextIndex], values[nextIndex], nextIndex);
		}
	}

	private class KeyIterator extends MapIterator<Long>
	{
		public Long next() {
			final int nextIndex = nextIndex();
			return keys == null ? nextIndex : keys[nextIndex];
		}
	}

	private class PrimitiveEntryIterator extends MapIterator<Entry>
	{
		public Entry next() {
			final int nextIndex = nextIndex();
			return new Entry(keys == null ? nextIndex : keys[nextIndex], values[nextIndex], nextIndex);
		}
	}

	private abstract class MapIterator<E> implements Iterator<E>
	{
		public MapIterator() {
			end = keys == null ? size : values.length;
			next = -1;
			nextIndex();
		}

		public boolean hasNext() {
			return end > 0 && next < end;
		}

		int nextIndex() {
			int curr = next;
			do {
				next++;
			} while (next < end && keys != null && values[next] == EMPTY_VAL);
			return curr;
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}

		private int next, end;
	}

	public Iterable<Map.Entry<Long, Integer>> entries() {
		return Iterators.able(new EntryIterator());
	}

	public void ensureCapacity(int capacity) {
		checkNotImmutable();
		int newSize = toSize(capacity);
		if (newSize > keys.length) {
			rehash(newSize);
		}
	}

	public int size() {
		return size;
	}

	public Iterable<Entry> primitiveEntries() {
		return new Iterable<Entry>()
		{
			public Iterator<Entry> iterator() {
				return (new PrimitiveEntryIterator());
			}
		};

	}

	public Iterable<Long> keySet() {
		return Iterators.able(new KeyIterator());
	}

	public void clear() {
		//		Arrays.fill(keys, EMPTY_KEY);
		Arrays.fill(values, EMPTY_VAL);
		size = 0;

	}

	public List<Entry> getObjectsSortedByValue(boolean descending) {
		List<edu.berkeley.nlp.lm.collections.LongToIntHashMap.Entry> l = new ArrayList<edu.berkeley.nlp.lm.collections.LongToIntHashMap.Entry>();
		for (final edu.berkeley.nlp.lm.collections.LongToIntHashMap.Entry entry : primitiveEntries()) {
			l.add(entry);
		}
		Collections.sort(l);
		if (descending) Collections.reverse(l);
		return l;
	}

	public LongToIntHashMap copy() {
		LongToIntHashMap ret = new LongToIntHashMap();
		//		ret.deflt = deflt;
		ret.keys = Arrays.copyOf(keys, keys.length);
		ret.values = Arrays.copyOf(values, values.length);
		ret.size = size;
		ret.sorted = sorted;
		ret.maxLoadFactor = maxLoadFactor;
		return ret;
	}

} public class Entry implements Map.Entry<Long, Integer>, Comparable<Entry>
{
	private int index;

	public long key;

	public int value;

	public Entry(long key, int value, int index) {
		super();
		this.key = key;
		assert value >= 0;
		this.value = value;
		this.index = index;
	}

	public Long getKey() {
		return key;
	}

	public Integer getValue() {
		return value;
	}

	public Integer setValue(Integer value) {
		this.value = value;
		values[index] = value;
		return this.value;
	}

	@Override
	public int compareTo(Entry o) {
		// sortable by *value*
		return Double.compare(value, o.value);
	}
} public interface LongRepresentable<T> extends Comparable<T>
{

	public long asLong();

} public interface NgramMap<V>
{

	public long put(int[] ngram, int startPos, int endPos, V val);

	public void handleNgramsFinished(int justFinishedOrder);

	public void trim();

	public void initWithLengths(List<Long> numNGrams);

	public ValueContainer<V> getValues();

	public long getValueAndOffset(final long contextOffset, final int contextOrder, int word, @OutputParameter V currProbVal);

	public int getMaxNgramOrder();

	public long getNumNgrams(int ngramOrder);

	public Iterable<Entry<V>> getNgramsForOrder(final int ngramOrder);

	public CustomWidthArray getValueStoringArray(final int ngramOrder);

	public static class Entry<T>
	{
		/**
		 * @param key
		 * @param value
		 */
		public Entry(final int[] key, final T value) {
			super();
			this.key = key;
			this.value = value;
		}

		public int[] key;

		public T value;

	}

	public boolean contains(int[] ngram, int startPos, int endPos);

	public V get(int[] ngram, int startPos, int endPos);

	public void clearStorage();

} @SuppressWarnings("ucd")
public class Logger
{

	/**
	 * Logging interface.
	 * 
	 * @author adampauls
	 * 
	 */
	public static interface LogInterface
	{
		/**
		 * Log a string, but only once in a while. This is useful when we are
		 * logging frequently and only wish to see lines every second or so. How
		 * often logging is done is up to the implementation.
		 * 
		 * @param s
		 *            printf style string
		 * @param args
		 *            printf args
		 */
		public void logs(String s, Object... args);

		/**
		 * Always log this string.
		 * 
		 * @param s
		 */
		public void logss(String s);

		public void logss(String string, Object... args);

		/**
		 * Start a track (a function, or some other logical unit of computation)
		 * with a name given by <code>s</code>.
		 * 
		 * @param s
		 */
		public void startTrack(String s);

		/**
		 * Ends a track, printing out how long the track took.
		 */
		public void endTrack();

		public void dbg(String s);

		public void err(String s);

		public void err(String s, Object... args);

		public void warn(String s);

		public void warn(String string, Object... args);

	}

	/**
	 * Logs to System.out and System.err
	 * 
	 * @author Aria Haghighi
	 * 
	 */
	@SuppressWarnings("ucd")
	public static class SystemLogger implements LogInterface
	{

		private final PrintStream out;

		private final PrintStream err;

		private int trackLevel = 0;

		private final boolean debug = true;

		public SystemLogger(final PrintStream out, final PrintStream err) {
			this.out = out;
			this.err = err;
		}

		public void close() {
			if (out != null) {
				out.close();
			}
			if (err != null) {
				err.close();
			}
		}

		public SystemLogger(final String outFile, final String errFile) throws FileNotFoundException {
			this(outFile != null ? new PrintStream(new FileOutputStream(outFile)) : null, errFile != null ? new PrintStream(new FileOutputStream(errFile))
				: null);
		}

		public SystemLogger() {
			this(System.out, System.err);
		}

		private final Stack<Long> trackStartTimes = new Stack<Long>();

		private String getIndentPrefix() {
			final StringBuilder builder = new StringBuilder();
			for (int i = 0; i < trackLevel; ++i) {
				builder.append("\t");
			}
			return builder.toString();
		}

		private void output(final PrintStream o, final String txt) {
			if (o == null) return;
			final String[] lines = txt.split("\n");
			final String prefix = getIndentPrefix();
			for (final String line : lines) {
				o.println(prefix + line);
			}
		}

		@Override
		public void dbg(final String s) {
			if (debug) output(out, "[dbg] " + s);
		}

		private String timeString(final double milliSecs_) {
			double milliSecs = milliSecs_;
			String timeStr = "";
			final int hours = (int) (milliSecs / (1000 * 60 * 60));
			if (hours > 0) {
				milliSecs -= hours * 1000 * 60 * 60;
				timeStr += hours + "h";
			}
			final int mins = (int) (milliSecs / (1000 * 60));
			if (mins > 0) {
				milliSecs -= mins * 1000.0 * 60.0;
				timeStr += mins + "m";
			}
			final int secs = (int) (milliSecs / 1000.0);
			//if (secs > 0) {
			//milliSecs -= secs * 1000.0;
			timeStr += secs + "s";
			//}

			return timeStr;
		}

		@Override
		public void endTrack() {
			String timeStr = null;
			synchronized (this) {
				trackLevel--;
				final double milliSecs = System.currentTimeMillis() - trackStartTimes.pop();
				timeStr = timeString(milliSecs);
			}
			output(out, "} " + (timeStr != null ? "[" + timeStr + "]" : ""));
		}

		@Override
		public void err(final String s) {
			err.println(s);
		}

		public void logs(final String s) {
			output(out, s);
		}

		@Override
		public void logss(final String s) {
			output(out, s);
		}

		@Override
		public void startTrack(final String s) {
			output(out, s + " {");
			synchronized (this) {
				trackLevel++;
				trackStartTimes.push(System.currentTimeMillis());
			}
		}

		@Override
		public void warn(final String s) {
			output(err, "[warn] " + s);
		}

		@Override
		public void logs(final String s, final Object... args) {
			logs(String.format(s, args));
		}

		@Override
		public void err(final String s, final Object... args) {
			output(err, "[err] " + String.format(s, args));
		}

		@Override
		public void warn(final String string, final Object... args) {
			warn(String.format(string, args));
		}

		@Override
		public void logss(final String string, final Object... args) {
			logss(String.format(string, args));
		}
	}

	/**
	 * Default logging goes nowhere.
	 * 
	 * @author adampauls
	 * 
	 */
	@SuppressWarnings("ucd")
	public static class NullLogger implements LogInterface
	{

		@Override
		public void logs(final String s, final Object... args) {
		}

		@Override
		public void logss(final String s) {
		}

		@Override
		public void startTrack(final String s) {
		}

		@Override
		public void endTrack() {
		}

		@Override
		public void dbg(final String s) {
		}

		@Override
		public void err(final String s) {
		}

		@Override
		public void err(final String s, final Object... args) {
		}

		@Override
		public void warn(final String s) {
		}

		@Override
		public void warn(final String string, final Object... args) {
		}

		@Override
		public void logss(final String string, final Object... args) {
		}

	}

	/**
	 * Convenience class for stringing together loggers.
	 * 
	 * @author adampauls
	 * 
	 * 
	 */
	@SuppressWarnings("ucd")
	public static class CompoundLogger implements LogInterface
	{
		private final LogInterface[] loggers;

		public CompoundLogger(final LogInterface... loggers) {
			this.loggers = loggers;
		}

		@Override
		public void logs(final String s, final Object... args) {
			for (final LogInterface logger : loggers) {
				logger.logs(s, args);
			}
		}

		@Override
		public void logss(final String s) {
			for (final LogInterface logger : loggers) {
				logger.logss(s);
			}
		}

		@Override
		public void startTrack(final String s) {
			for (final LogInterface logger : loggers) {
				logger.startTrack(s);
			}
		}

		@Override
		public void endTrack() {
			for (final LogInterface logger : loggers) {
				logger.endTrack();
			}
		}

		@Override
		public void dbg(final String s) {
			for (final LogInterface logger : loggers) {
				logger.dbg(s);
			}
		}

		@Override
		public void err(final String s) {
			for (final LogInterface logger : loggers) {
				logger.err(s);
			}
		}

		@Override
		public void err(final String s, final Object... args) {
			for (final LogInterface logger : loggers) {
				logger.err(s, args);
			}
		}

		@Override
		public void warn(final String s) {
			for (final LogInterface logger : loggers) {
				logger.warn(s);
			}
		}

		@Override
		public void warn(final String string, final Object... args) {
			for (final LogInterface logger : loggers) {
				logger.warn(string, args);
			}
		}

		@Override
		public void logss(final String string, final Object... args) {
			for (final LogInterface logger : loggers) {
				logger.logss(string, args);
			}
		}
	}

	public synchronized static void setGlobalLogger(final LogInterface logger) {
		instance = logger;
	}

	public synchronized static LogInterface getGlobalLogger() {
		return instance;
	}

	private static LogInterface instance = new NullLogger();

	public static LogInterface i() {
		return instance;
	}

	public static void setLogger(final LogInterface i) {
		instance = i;
	}

	public static void logs(final String s) {
		i().logs(s);
	}

	// Static Logger Methods
	public static void logs(final String s, final Object... args) {
		i().logs(s, args);
	}

	public static void logss(final String s) {
		i().logss(s);
	}

	public static void startTrack(final String s, final Object... args) {
		i().startTrack(String.format(s, args));
	}

	public static void endTrack() {
		i().endTrack();
	}

	public static void dbg(final String s) {
		i().dbg(s);
	}

	public static void err(final String s) {
		i().err(s);
	}

	public static void err(final String s, final Object... args) {
		i().err(s, args);
	}

	public static void warn(final String s) {
		i().warn(s);
	}

	public static void warn(final String string, final Object... args) {
		i().warn(string, args);
	}

	public static void logss(final String string, final Object... args) {
		i().logss(string, args);
	}

}
import java.io.Serializable;
import java.util.Arrays;
import java.util.List;
import edu.berkeley.nlp.lm.array.CustomWidthArray;
import edu.berkeley.nlp.lm.array.LongArray;
import edu.berkeley.nlp.lm.bits.BitList;
import edu.berkeley.nlp.lm.bits.BitStream;
import edu.berkeley.nlp.lm.bits.VariableLengthBitCompressor;
import edu.berkeley.nlp.lm.collections.Indexer;
import edu.berkeley.nlp.lm.collections.LongToIntHashMap;
import edu.berkeley.nlp.lm.collections.LongToIntHashMap.Entry;
import edu.berkeley.nlp.lm.collections.LongRepresentable;
import edu.berkeley.nlp.lm.map.NgramMap;
import edu.berkeley.nlp.lm.util.Annotations.OutputParameter;
import edu.berkeley.nlp.lm.util.Annotations.PrintMemoryCount;
import edu.berkeley.nlp.lm.util.Logger;
package edu.berkeley.nlp.lm.values;



abstract class RankedValueContainer<V extends LongRepresentable<V>> implements CompressibleValueContainer<V>, Serializable
{

	/**
	 * 
	 */
	private static final long serialVersionUID = 964277160049236607L;

	@PrintMemoryCount
	protected final CustomWidthArray[] valueRanks;

	protected final boolean storeSuffixIndexes;

	protected final VariableLengthBitCompressor valueCoder;

	protected final int valueRadix;

	protected int valueWidth;

	protected final int defaultValRank = 10;

	protected final long[] numNgramsForEachOrder;

	protected final int[] suffixBitsForOrder;

	protected boolean useMapValueArray = false;

	private NgramMap<V> ngramMap;

	public RankedValueContainer(final int valueRadix, final boolean storePrefixIndexes, long[] numNgramsForEachOrder) {
		this.valueRadix = valueRadix;
		suffixBitsForOrder = new int[numNgramsForEachOrder.length];

		this.numNgramsForEachOrder = numNgramsForEachOrder;
		valueCoder = new VariableLengthBitCompressor(valueRadix);
		this.storeSuffixIndexes = storePrefixIndexes;
		valueRanks = new CustomWidthArray[numNgramsForEachOrder.length];

	}

	@Override
	public void setMap(final NgramMap<V> map) {
		this.ngramMap = map;

	}

	protected boolean useValueStoringArray() {
		return false;
	}

	@Override
	public void swap(final long a, final long b, final int ngramOrder) {

		final long temp = valueRanks[ngramOrder].get(a);
		assert temp >= 0;
		final long val = valueRanks[ngramOrder].get(b);
		assert val >= 0;
		valueRanks[ngramOrder].set(a, val);
		valueRanks[ngramOrder].set(b, temp);
	}

	@Override
	public boolean add(final int[] ngram, final int startPos, final int endPos, final int ngramOrder, final long offset, final long prefixOffset,
		final int word, final V val_, final long suffixOffset, final boolean ngramIsNew) {
		if (suffixOffset < 0 && storeSuffixIndexes) return false;

		assert suffixOffset < 0 || ngramOrder == 0 || CustomWidthArray.numBitsNeeded(suffixOffset) <= suffixBitsForOrder[ngramOrder] : "Problem with suffix offset bits "
			+ suffixOffset + " " + numNgramsForEachOrder[ngramOrder - 1] + " " + Arrays.toString(ngram);
		V val = val_;
		if (val == null) val = getDefaultVal();

		setSizeAtLeast(10, ngramOrder);

		final long indexOfCounts = getCountRank(val.asLong());

		assert indexOfCounts >= 0;

		final CustomWidthArray valueRanksHere = valueRanks[ngramOrder];
		final int widthOffset = ngramOrder == 0 || !useMapValueArray ? 0 : valueRanksHere.getKeyWidth();
		valueRanksHere.setAndGrowIfNeeded(offset, indexOfCounts, widthOffset, valueWidth);
		if (storeSuffixIndexes && ngramOrder > 0) {
			assert suffixOffset >= 0;
			assert suffixOffset <= Integer.MAX_VALUE;
			valueRanksHere.setAndGrowIfNeeded(offset, suffixOffset, widthOffset + valueWidth, suffixBitsForOrder[ngramOrder]);
		}
		return true;

	}

	abstract protected long getCountRank(long val);

	@Override
	public BitList getCompressed(final long offset, final int ngramOrder) {