/*		 
 * Copyright (C) 2007-2014 Sebastiano Vigna 
 *
 * 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 PACKAGE;

import java.util.Map;
import java.util.NoSuchElementException;
import it.unimi.dsi.fastutil.objects.AbstractObjectIterator;
import it.unimi.dsi.fastutil.objects.AbstractObjectSet;
import it.unimi.dsi.fastutil.objects.ObjectIterator;

import VALUE_PACKAGE.VALUE_COLLECTION;
import VALUE_PACKAGE.VALUE_COLLECTIONS;
import VALUE_PACKAGE.VALUE_ARRAY_SET;
import VALUE_PACKAGE.VALUE_ARRAYS;

/** A simple, brute-force implementation of a map based on two parallel backing arrays. 
 * 
 * <p>The main purpose of this
 * implementation is that of wrapping cleanly the brute-force approach to the storage of a very 
 * small number of pairs: just put them into two parallel arrays and scan linearly to find an item.
 */

public class ARRAY_MAP KEY_VALUE_GENERIC extends ABSTRACT_MAP KEY_VALUE_GENERIC implements java.io.Serializable, Cloneable {

	private static final long serialVersionUID = 1L;
	/** The keys (valid up to {@link #size}, excluded). */
	private transient KEY_TYPE[] key;
	/** The values (parallel to {@link #key}). */
	private transient VALUE_TYPE[] value;
	/** The number of valid entries in {@link #key} and {@link #value}. */
	private int size;
	
	/** Creates a new empty array map with given key and value backing arrays. The resulting map will have as many entries as the given arrays.
	 * 
	 * <p>It is responsibility of the caller that the elements of <code>key</code> are distinct.
	 * 
	 * @param key the key array.
	 * @param value the value array (it <em>must</em> have the same length as <code>key</code>).
	 */
	public ARRAY_MAP( final KEY_TYPE[] key, final VALUE_TYPE[] value ) {
		this.key = key;
		this.value = value;
		size = key.length;
		if( key.length != value.length ) throw new IllegalArgumentException( "Keys and values have different lengths (" + key.length + ", " + value.length + ")" );
	}

	/** Creates a new empty array map.
	 */
	public ARRAY_MAP() {
		this.key = ARRAYS.EMPTY_ARRAY;
		this.value = VALUE_ARRAYS.EMPTY_ARRAY;
	}
	
	/** Creates a new empty array map of given capacity.
	 *
	 * @param capacity the initial capacity.
	 */ 
	public ARRAY_MAP( final int capacity ) {
		this.key = new KEY_TYPE[ capacity ];
		this.value = new VALUE_TYPE[ capacity ];
	}
	
	/** Creates a new empty array map copying the entries of a given map.
	 *
	 * @param m a map.
	 */ 
	public ARRAY_MAP( final MAP KEY_VALUE_GENERIC m ) {
		this( m.size() );
		putAll( m );
	}
	
	/** Creates a new empty array map copying the entries of a given map.
	 *
	 * @param m a map.
	 */ 
	public ARRAY_MAP( final Map<? extends KEY_GENERIC_CLASS, ? extends VALUE_GENERIC_CLASS> m ) {
		this( m.size() );
		putAll( m );
	}
	
	/** Creates a new array map with given key and value backing arrays, using the given number of elements.
	 * 
	 * <p>It is responsibility of the caller that the first <code>size</code> elements of <code>key</code> are distinct.
	 * 
	 * @param key the key array.
	 * @param value the value array (it <em>must</em> have the same length as <code>key</code>).
	 * @param size the number of valid elements in <code>key</code> and <code>value</code>.
	 */
	public ARRAY_MAP( final KEY_TYPE[] key, final VALUE_TYPE[] value, final int size ) {
		this.key = key;
		this.value = value;
		this.size = size;
		if( key.length != value.length ) throw new IllegalArgumentException( "Keys and values have different lengths (" + key.length + ", " + value.length + ")" );
		if ( size > key.length ) throw new IllegalArgumentException( "The provided size (" + size + ") is larger than or equal to the backing-arrays size (" + key.length + ")" );
	}

	private final class EntrySet extends AbstractObjectSet<MAP.Entry KEY_VALUE_GENERIC> implements FastEntrySet KEY_VALUE_GENERIC {

		@Override
		public ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> iterator() {
			return new AbstractObjectIterator<MAP.Entry KEY_VALUE_GENERIC>() {
				int next = 0;
				
				public boolean hasNext() {
					return next < size;
				}

				@SuppressWarnings("unchecked")
				public Entry KEY_VALUE_GENERIC next() {
					if ( ! hasNext() ) throw new NoSuchElementException();
					return new ABSTRACT_MAP.BasicEntry KEY_VALUE_GENERIC( KEY_GENERIC_CAST key[ next ], VALUE_GENERIC_CAST value[ next++ ] );
				}
				
			};
		}

		public ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> fastIterator() {
			return new AbstractObjectIterator<MAP.Entry KEY_VALUE_GENERIC>() {
				int next = 0;
				final BasicEntry KEY_VALUE_GENERIC entry = new BasicEntry KEY_VALUE_GENERIC ( KEY_NULL, VALUE_NULL );
				
				public boolean hasNext() {
					return next < size;
				}

				@SuppressWarnings("unchecked")
				public Entry KEY_VALUE_GENERIC next() {
					if ( ! hasNext() ) throw new NoSuchElementException();
					entry.key = KEY_GENERIC_CAST key[ next ];
					entry.value = VALUE_GENERIC_CAST value[ next++ ];
					return entry;
				}
				
			};
		}

		public int size() {
			return size;
		}

		@SuppressWarnings("unchecked")
		public boolean contains( Object o ) {
			if ( ! ( o instanceof Map.Entry ) ) return false;
			final Map.Entry<KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS> e = (Map.Entry<KEY_GENERIC_CLASS, VALUE_GENERIC_CLASS>)o;
			final KEY_GENERIC_TYPE k = KEY_CLASS2TYPE( e.getKey() );
			return ARRAY_MAP.this.containsKey( k ) && VALUE_EQUALS( ARRAY_MAP.this.GET_VALUE( k ), VALUE_CLASS2TYPE( e.getValue() ) );
		}
		
	}

	public FastEntrySet KEY_VALUE_GENERIC ENTRYSET() {
		return new EntrySet();
	}

	private int findKey( final KEY_TYPE k ) {
		final KEY_TYPE[] key = this.key;
		for( int i = size; i-- != 0; ) if ( KEY_EQUALS( key[ i ], k ) ) return i;
		return -1;
	}

	@SuppressWarnings("unchecked")
#if #keys(primitive) || #values(primitive)
	public VALUE_GENERIC_TYPE GET_VALUE( final KEY_TYPE k ) {
#else
	public VALUE_GENERIC_TYPE get( final Object k ) {
#endif
		final KEY_TYPE[] key = this.key;
		for( int i = size; i-- != 0; ) if ( KEY_EQUALS( key[ i ], k ) ) return VALUE_GENERIC_CAST value[ i ];
		return defRetValue;
	}

	public int size() {
		return size;
	}

	@Override
	public void clear() {
#if #keys(reference) || #values(reference)
		for( int i = size; i-- != 0; ) {
#if #keys(reference)
			key[ i ] = null;
#endif
#if #values(reference)
			value[ i ] = null;
#endif
		}
#endif
		size = 0;
	}

	@Override
	public boolean containsKey( final KEY_TYPE k ) {
		return findKey( k ) != -1;
	}

	@Override
	@SuppressWarnings("unchecked")
	public boolean containsValue( VALUE_TYPE v ) {
		for( int i = size; i-- != 0; ) if ( VALUE_EQUALS( value[ i ], v ) ) return true;
		return false;
	}

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

	@Override
	@SuppressWarnings("unchecked")
	public VALUE_GENERIC_TYPE put( KEY_GENERIC_TYPE k, VALUE_GENERIC_TYPE v ) {
		final int oldKey = findKey( k );
		if ( oldKey != -1 ) {
			final VALUE_GENERIC_TYPE oldValue = VALUE_GENERIC_CAST value[ oldKey ];
			value[ oldKey ] = v;
			return oldValue;
		}
		if ( size == key.length ) {
			final KEY_TYPE[] newKey = new KEY_TYPE[ size == 0 ? 2 : size * 2 ];
			final VALUE_TYPE[] newValue = new VALUE_TYPE[ size == 0 ? 2 : size * 2 ];
			for( int i = size; i-- != 0; ) {
				newKey[ i ] = key[ i ];
				newValue[ i ] = value[ i ];
			}
			key = newKey;
			value = newValue;
		}
		key[ size ] = k;
		value[ size ] = v;
		size++;
		return defRetValue;
	}

	@Override
	@SuppressWarnings("unchecked")

#if #keys(primitive) || #values(primitive)
	public VALUE_GENERIC_TYPE REMOVE_VALUE( final KEY_TYPE k ) {
#else
	public VALUE_GENERIC_TYPE remove( final Object k ) {
#endif
		final int oldPos = findKey( k );
		if ( oldPos == -1 ) return defRetValue;
		final VALUE_GENERIC_TYPE oldValue = VALUE_GENERIC_CAST value[ oldPos ];
		final int tail = size - oldPos - 1;
		for( int i = 0; i < tail; i++ ) {
			key[ oldPos + i ] = key[ oldPos + i + 1 ];
			value[ oldPos + i ] = value[ oldPos + i + 1 ];
		}
		size--;
#if #keys(reference)
		key[ size ] = null;
#endif
#if #values(reference)
		value[ size ] = null;
#endif
		return oldValue;
	}

	@Override

	@SuppressWarnings("unchecked")
	public SET KEY_GENERIC keySet() {
		return new ARRAY_SET KEY_GENERIC( key, size );
	}

	@Override
	public VALUE_COLLECTION VALUE_GENERIC values() {
		return VALUE_COLLECTIONS.unmodifiable( new VALUE_ARRAY_SET VALUE_GENERIC( value, size ) );
	}

	/** Returns a deep copy of this map. 
	 *
	 * <P>This method performs a deep copy of this hash map; the data stored in the
	 * map, however, is not cloned. Note that this makes a difference only for object keys.
	 *
	 *  @return a deep copy of this map.
	 */

	@SuppressWarnings("unchecked")
	public ARRAY_MAP KEY_VALUE_GENERIC clone() {
		ARRAY_MAP KEY_VALUE_GENERIC c;
		try {
			c = (ARRAY_MAP KEY_VALUE_GENERIC)super.clone();
		}
		catch(CloneNotSupportedException cantHappen) {
			throw new InternalError();
		}
		c.key = key.clone();
		c.value = value.clone();
		return c;
	}
	
	private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
		s.defaultWriteObject();
		for( int i = 0; i < size; i++ ) {
			s.WRITE_KEY( key[ i ] );
			s.WRITE_VALUE( value[ i ] );
		}
	}

	@SuppressWarnings("unchecked")
	private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
		s.defaultReadObject();
		key = new KEY_TYPE[ size ];
		value = new VALUE_TYPE[ size ];
		for( int i = 0; i < size; i++ ) {
			key[ i ] = s.READ_KEY();
			value[ i ] = s.READ_VALUE();
		}
	}
}