tikhomirov@276: /*
tikhomirov@551:  * Copyright (c) 2011-2013 TMate Software Ltd
tikhomirov@276:  *  
tikhomirov@276:  * This program is free software; you can redistribute it and/or modify
tikhomirov@276:  * it under the terms of the GNU General Public License as published by
tikhomirov@276:  * the Free Software Foundation; version 2 of the License.
tikhomirov@276:  *
tikhomirov@276:  * This program is distributed in the hope that it will be useful,
tikhomirov@276:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@276:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@276:  * GNU General Public License for more details.
tikhomirov@276:  *
tikhomirov@276:  * For information on how to redistribute this software under
tikhomirov@276:  * the terms of a license other than GNU General Public License
tikhomirov@276:  * contact TMate Software at support@hg4j.com
tikhomirov@276:  */
tikhomirov@276: package org.tmatesoft.hg.internal;
tikhomirov@276: 
tikhomirov@551: import java.util.Arrays;
tikhomirov@656: import java.util.Collection;
tikhomirov@415: import java.util.Iterator;
tikhomirov@415: import java.util.Map;
tikhomirov@415: import java.util.Map.Entry;
tikhomirov@276: import java.util.NoSuchElementException;
tikhomirov@276: 
tikhomirov@276: 
tikhomirov@276: /**
tikhomirov@276:  * Map implementation that uses plain int keys and performs with log n effectiveness.
tikhomirov@448:  * May contain null values
tikhomirov@276:  * 
tikhomirov@276:  * @author Artem Tikhomirov
tikhomirov@276:  * @author TMate Software Ltd.
tikhomirov@276:  */
tikhomirov@276: public class IntMap<V> {
tikhomirov@276: 
tikhomirov@276: 	private int[] keys;
tikhomirov@276: 	private Object[] values;
tikhomirov@276: 	private int size;
tikhomirov@276: 	
tikhomirov@276: 	public IntMap(int size) {
tikhomirov@276: 		keys = new int[size <= 0 ? 16 : size];
tikhomirov@276: 		values = new Object[keys.length];
tikhomirov@276: 	}
tikhomirov@276: 	
tikhomirov@276: 	public int size() {
tikhomirov@276: 		return size;
tikhomirov@276: 	}
tikhomirov@276: 	
tikhomirov@276: 	public int firstKey() {
tikhomirov@276: 		if (size == 0) {
tikhomirov@276: 			throw new NoSuchElementException();
tikhomirov@276: 		}
tikhomirov@276: 		return keys[0];
tikhomirov@276: 	}
tikhomirov@276: 
tikhomirov@276: 	public int lastKey() {
tikhomirov@276: 		if (size == 0) {
tikhomirov@276: 			throw new NoSuchElementException();
tikhomirov@276: 		}
tikhomirov@276: 		return keys[size-1];
tikhomirov@276: 	}
tikhomirov@276: 	
tikhomirov@276: 	public void trimToSize() {
tikhomirov@276: 		if (size < keys.length) {
tikhomirov@276: 			int[] newKeys = new int[size];
tikhomirov@276: 			Object[] newValues = new Object[size];
tikhomirov@276: 			System.arraycopy(keys, 0, newKeys, 0, size);
tikhomirov@276: 			System.arraycopy(values, 0, newValues, 0, size);
tikhomirov@276: 			keys = newKeys;
tikhomirov@276: 			values = newValues;
tikhomirov@276: 		}
tikhomirov@276: 	}
tikhomirov@276: 
tikhomirov@276: 	public void put(int key, V value) {
tikhomirov@276: 		int ix = binarySearch(keys, size, key);
tikhomirov@276: 		if (ix < 0) {
tikhomirov@276: 			final int insertPoint = -ix - 1;
tikhomirov@276: 			assert insertPoint <= size; // can't be greater, provided binarySearch didn't malfunction.
tikhomirov@276: 			if (size == keys.length) {
tikhomirov@278: 				int capInc = size >>> 2; // +25%
tikhomirov@278: 				int newCapacity = size + (capInc < 2 ? 2 : capInc) ;
tikhomirov@276: 				int[] newKeys = new int[newCapacity];
tikhomirov@276: 				Object[] newValues = new Object[newCapacity];
tikhomirov@276: 				System.arraycopy(keys, 0, newKeys, 0, insertPoint);
tikhomirov@276: 				System.arraycopy(keys, insertPoint, newKeys, insertPoint+1, keys.length - insertPoint);
tikhomirov@276: 				System.arraycopy(values, 0, newValues, 0, insertPoint);
tikhomirov@276: 				System.arraycopy(values, insertPoint, newValues, insertPoint+1, values.length - insertPoint);
tikhomirov@276: 				keys = newKeys;
tikhomirov@276: 				values = newValues;
tikhomirov@276: 			} else {
tikhomirov@276: 				// arrays got enough capacity
tikhomirov@276: 				if (insertPoint != size) {
tikhomirov@276: 					System.arraycopy(keys, insertPoint, keys, insertPoint+1, keys.length - insertPoint - 1);
tikhomirov@276: 					System.arraycopy(values, insertPoint, values, insertPoint+1, values.length - insertPoint - 1);
tikhomirov@276: 				}
tikhomirov@276: 				// else insertPoint is past known elements, no need to copy arrays
tikhomirov@276: 			}
tikhomirov@276: 			keys[insertPoint] = key;
tikhomirov@276: 			values[insertPoint] = value;
tikhomirov@276: 			size++;
tikhomirov@276: 		} else {
tikhomirov@276: 			values[ix] = value;
tikhomirov@276: 		}
tikhomirov@276: 	}
tikhomirov@276: 	
tikhomirov@276: 	public boolean containsKey(int key) {
tikhomirov@276: 		return binarySearch(keys, size, key) >= 0;
tikhomirov@276: 	}
tikhomirov@276: 
tikhomirov@276: 	@SuppressWarnings("unchecked")
tikhomirov@276: 	public V get(int key) {
tikhomirov@276: 		int ix = binarySearch(keys, size, key);
tikhomirov@276: 		if (ix >= 0) {
tikhomirov@276: 			return (V) values[ix];
tikhomirov@276: 		}
tikhomirov@276: 		return null;
tikhomirov@276: 	}
tikhomirov@281: 	
tikhomirov@281: 	public void remove(int key) {
tikhomirov@281: 		int ix = binarySearch(keys, size, key);
tikhomirov@281: 		if (ix >= 0) {
tikhomirov@281: 			if (ix <= size - 1) {
tikhomirov@281: 				System.arraycopy(keys, ix+1, keys, ix, size - ix - 1);
tikhomirov@281: 				System.arraycopy(values, ix+1, values, ix, size - ix - 1);
tikhomirov@281: 			} // if ix points to last element, no reason to attempt a copy
tikhomirov@281: 			size--;
tikhomirov@281: 			keys[size] = 0;
tikhomirov@281: 			values[size] = null;
tikhomirov@281: 		}
tikhomirov@281: 	}
tikhomirov@281: 	
tikhomirov@551: 	public void clear() {
tikhomirov@551: 		Arrays.fill(values, 0, size, null); // do not keep the references
tikhomirov@551: 		size = 0;
tikhomirov@551: 	}
tikhomirov@551: 	
tikhomirov@281: 	/**
tikhomirov@281: 	 * Forget first N entries (in natural order) in the map.
tikhomirov@281: 	 */
tikhomirov@281: 	public void removeFromStart(int count) {
tikhomirov@281: 		if (count > 0 && count <= size) {
tikhomirov@281: 			if (count < size) {
tikhomirov@281: 				System.arraycopy(keys, count, keys, 0, size - count);
tikhomirov@281: 				System.arraycopy(values, count, values, 0, size - count);
tikhomirov@281: 			}
tikhomirov@281: 			for (int i = size - count; i < size; i++) {
tikhomirov@281: 				keys[i] = 0;
tikhomirov@281: 				values[i] = null;
tikhomirov@281: 			}
tikhomirov@281: 			size -= count;
tikhomirov@281: 		} 
tikhomirov@281: 	}
tikhomirov@415: 
tikhomirov@415: 	// document iterator is non-modifying (neither remove() nor setValue() works)
tikhomirov@415: 	// perhaps, may also implement Iterable<Map.Entry> to use nice for()
tikhomirov@415: 	public Iterator<Map.Entry<Integer, V>> entryIterator() {
tikhomirov@415: 		class E implements Map.Entry<Integer, V> {
tikhomirov@415: 			private Integer key;
tikhomirov@415: 			private V value;
tikhomirov@415: 
tikhomirov@415: 			public Integer getKey() {
tikhomirov@415: 				return key;
tikhomirov@415: 			}
tikhomirov@415: 
tikhomirov@415: 			public V getValue() {
tikhomirov@415: 				return value;
tikhomirov@415: 			}
tikhomirov@415: 
tikhomirov@415: 			public V setValue(V value) {
tikhomirov@415: 				throw new UnsupportedOperationException();
tikhomirov@415: 			}
tikhomirov@415: 			
tikhomirov@415: 			void init(Integer k, V v) {
tikhomirov@415: 				key = k;
tikhomirov@415: 				value = v;
tikhomirov@415: 			}
tikhomirov@415: 		}
tikhomirov@415: 		
tikhomirov@415: 		return new Iterator<Map.Entry<Integer, V>>() {
tikhomirov@415: 			private int i = 0;
tikhomirov@415: 			private final E entry = new E();
tikhomirov@415: 			private final int _size;
tikhomirov@415: 			private final int[] _keys;
tikhomirov@415: 			private final Object[] _values;
tikhomirov@415: 			
tikhomirov@415: 			{
tikhomirov@415: 				_size = IntMap.this.size;
tikhomirov@415: 				_keys = IntMap.this.keys;
tikhomirov@415: 				_values = IntMap.this.values;
tikhomirov@415: 			}
tikhomirov@415: 
tikhomirov@415: 			public boolean hasNext() {
tikhomirov@415: 				return i < _size;
tikhomirov@415: 			}
tikhomirov@415: 
tikhomirov@415: 			public Entry<Integer, V> next() {
tikhomirov@415: 				if (i >= _size) {
tikhomirov@415: 					throw new NoSuchElementException();
tikhomirov@415: 				}
tikhomirov@415: 				@SuppressWarnings("unchecked")
tikhomirov@415: 				V val = (V) _values[i];
tikhomirov@415: 				entry.init(_keys[i], val);
tikhomirov@415: 				i++;
tikhomirov@415: 				return entry;
tikhomirov@415: 			}
tikhomirov@415: 
tikhomirov@415: 			public void remove() {
tikhomirov@415: 				throw new UnsupportedOperationException();
tikhomirov@415: 			}
tikhomirov@415: 		};
tikhomirov@415: 	}
tikhomirov@281: 	
tikhomirov@415: 	public Map<Integer, ? super V> fill(Map<Integer, ? super V> map) {
tikhomirov@415: 		for (Iterator<Map.Entry<Integer, V>> it = entryIterator(); it.hasNext(); ) {
tikhomirov@415: 			Map.Entry<Integer, V> next = it.next();
tikhomirov@415: 			map.put(next.getKey(), next.getValue());
tikhomirov@415: 		}
tikhomirov@415: 		return map;
tikhomirov@415: 	}
tikhomirov@656: 	
tikhomirov@656: 	public Collection<V> values() {
tikhomirov@656: 		@SuppressWarnings("unchecked")
tikhomirov@656: 		V[] rv = (V[]) new Object[size];
tikhomirov@656: 		System.arraycopy(values, 0, rv, 0, size);
tikhomirov@656: 		return Arrays.<V>asList(rv);
tikhomirov@656: 	}
tikhomirov@276: 
tikhomirov@276: 	// copy of Arrays.binarySearch, with upper search limit as argument
tikhomirov@276: 	private static int binarySearch(int[] a, int high, int key) {
tikhomirov@276: 		int low = 0;
tikhomirov@276: 		high--;
tikhomirov@276: 
tikhomirov@276: 		while (low <= high) {
tikhomirov@276: 			int mid = (low + high) >> 1;
tikhomirov@276: 			int midVal = a[mid];
tikhomirov@276: 
tikhomirov@276: 			if (midVal < key)
tikhomirov@276: 				low = mid + 1;
tikhomirov@276: 			else if (midVal > key)
tikhomirov@276: 				high = mid - 1;
tikhomirov@276: 			else
tikhomirov@276: 				return mid; // key found
tikhomirov@276: 		}
tikhomirov@276: 		return -(low + 1); // key not found.
tikhomirov@276: 	}
tikhomirov@276: }