/*
 * Copyright (C) 2007-2022 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 java.util.function.Consumer;


#if ! KEYS_REFERENCE
import it.unimi.dsi.fastutil.objects.AbstractObjectSet;
import it.unimi.dsi.fastutil.objects.ObjectIterator;
import it.unimi.dsi.fastutil.objects.ObjectSpliterator;
import it.unimi.dsi.fastutil.objects.ObjectSpliterators;
#endif

#if KEY_INDEX != VALUE_INDEX && !(KEYS_REFERENCE && VALUES_REFERENCE)
import VALUE_PACKAGE.VALUE_COLLECTION;
import VALUE_PACKAGE.VALUE_ABSTRACT_COLLECTION;
import VALUE_PACKAGE.VALUE_ARRAYS;
#endif
#if VALUES_PRIMITIVE && ! VALUES_INT_LONG_DOUBLE && KEY_INDEX != VALUE_INDEX
import VALUE_PACKAGE.METHOD_ARG_VALUE_CONSUMER;
#endif

/** 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;

	/** Cached set of entries. */
	private transient FastEntrySet KEY_VALUE_GENERIC entries;

	/** Cached set of keys. */
	private transient SET KEY_GENERIC keys;

	/** Cached collection of values. */
	private transient VALUE_COLLECTION VALUE_GENERIC values;

	/** 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} are distinct.
	 *
	 * @param key the key array.
	 * @param value the value array (it <em>must</em> have the same length as {@code key}).
	 */
	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());
		int i = 0;
		for(MAP.Entry KEY_VALUE_GENERIC e : m.ENTRYSET()) {
			key[i] = e.ENTRY_GET_KEY();
			value[i] = e.ENTRY_GET_VALUE();
			i++;
		}
		size = i;
	}

	/** 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());
		int i = 0;
		for(Map.Entry<? extends KEY_GENERIC_CLASS, ? extends VALUE_GENERIC_CLASS> e : m.entrySet()) {
			key[i] = KEY_CLASS2TYPE(e.getKey());
			value[i] = VALUE_CLASS2TYPE(e.getValue());
			i++;
		}
		size = i;
	}

	/** 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} elements of {@code key} are distinct.
	 *
	 * @param key the key array.
	 * @param value the value array (it <em>must</em> have the same length as {@code key}).
	 * @param size the number of valid elements in {@code key} and {@code value}.
	 */
	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 {

		// TODO Maybe make this return a list-iterator like the LinkedXHashMaps do? (same for other collection view types)

		@Override
		public ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> iterator() {
			return new ObjectIterator<MAP.Entry KEY_VALUE_GENERIC>() {
				int curr = -1, next = 0;

				@Override
				public boolean hasNext() { return next < size; }

				@Override
				SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
				public Entry KEY_VALUE_GENERIC next() {
					if (! hasNext()) throw new NoSuchElementException();
					return new ABSTRACT_MAP.BasicEntry KEY_VALUE_GENERIC_DIAMOND(KEY_GENERIC_CAST key[curr = next], VALUE_GENERIC_CAST value[next++]);
				}

				@Override
				public void remove() {
					if (curr == -1) throw new IllegalStateException();
					curr = -1;
					final int tail = size-- - next--;
					System.arraycopy(key, next + 1, key, next, tail);
					System.arraycopy(value, next + 1, value, next, tail);
#if KEYS_REFERENCE
					key[size] = null;
#endif
#if VALUES_REFERENCE
					value[size] = null;
#endif
				}

				@Override
				SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
				public void forEachRemaining(final Consumer<? super MAP.Entry KEY_VALUE_GENERIC> action) {
					// Hoist containing class field ref into local
					final int max = size;
					while (next < max) {
						action.accept(new ABSTRACT_MAP.BasicEntry KEY_VALUE_GENERIC_DIAMOND(KEY_GENERIC_CAST key[curr = next], VALUE_GENERIC_CAST value[next++]));
					}
				}
			};
		}

		@Override
		public ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> fastIterator() {
			return new ObjectIterator<MAP.Entry KEY_VALUE_GENERIC>() {
				int next = 0, curr = -1;
				final BasicEntry KEY_VALUE_GENERIC entry = new BasicEntry KEY_VALUE_GENERIC_DIAMOND ();

				@Override
				public boolean hasNext() { return next < size; }

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

				@Override
				public void remove() {
					if (curr == -1) throw new IllegalStateException();
					curr = -1;
					final int tail = size-- - next--;
					System.arraycopy(key, next + 1, key, next, tail);
					System.arraycopy(value, next + 1, value, next, tail);
#if KEYS_REFERENCE
					key[size] = null;
#endif
#if VALUES_REFERENCE
					value[size] = null;
#endif
				}

				@Override
				SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
				public void forEachRemaining(final Consumer<? super MAP.Entry KEY_VALUE_GENERIC> action) {
					// Hoist containing class field ref into local
					final int max = size;
					while (next < max) {
						entry.key = KEY_GENERIC_CAST key[curr = next];
						entry.value = VALUE_GENERIC_CAST value[next++];
						action.accept(entry);
					}
				}
			};
		}

		// We already have to create an Entry object for each iteration, so the overhead from having
		// skeletal implementations isn't significant.
		final class EntrySetSpliterator extends ObjectSpliterators.EarlyBindingSizeIndexBasedSpliterator<MAP.Entry KEY_VALUE_GENERIC>
				implements ObjectSpliterator<MAP.Entry KEY_VALUE_GENERIC> {

			EntrySetSpliterator(int pos, int maxPos) {
				super(pos, maxPos);
			}

			@Override
			public int characteristics() {
				return ObjectSpliterators.SET_SPLITERATOR_CHARACTERISTICS | java.util.Spliterator.SUBSIZED | java.util.Spliterator.ORDERED;
			}

			@Override
			SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
			protected final MAP.Entry KEY_VALUE_GENERIC get(int location) {
				return new ABSTRACT_MAP.BasicEntry KEY_VALUE_GENERIC_DIAMOND(KEY_GENERIC_CAST key[location], VALUE_GENERIC_CAST value[location]);
			}

			@Override
			protected final EntrySetSpliterator makeForSplit(int pos, int maxPos) {
				return new EntrySetSpliterator(pos, maxPos);
			}
		}

		@Override
		public ObjectSpliterator<MAP.Entry KEY_VALUE_GENERIC> spliterator() {
			return new EntrySetSpliterator(0, size);
		}

		/** {@inheritDoc} */
		@Override
		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		public void forEach(final Consumer<? super MAP.Entry KEY_VALUE_GENERIC> action) {
			// Hoist containing class field ref into local
			for (int i = 0, max = size; i < max; ++i) {
				action.accept(new ABSTRACT_MAP.BasicEntry KEY_VALUE_GENERIC_DIAMOND(KEY_GENERIC_CAST key[i], VALUE_GENERIC_CAST value[i]));
			}
		}

		/** {@inheritDoc} */
		@Override
		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		public void fastForEach(final Consumer<? super MAP.Entry KEY_VALUE_GENERIC> action) {
			final BasicEntry KEY_VALUE_GENERIC entry = new BasicEntry KEY_VALUE_GENERIC_DIAMOND ();
			// Hoist containing class field ref into local
			for (int i = 0, max = size; i < max; ++i) {
				entry.key = KEY_GENERIC_CAST key[i];
				entry.value = VALUE_GENERIC_CAST value[i];
				action.accept(entry);
			}
		}

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

		@Override
		SUPPRESS_WARNINGS_KEY_UNCHECKED
		public boolean contains(Object o) {
			if (! (o instanceof Map.Entry)) return false;
			final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
#if KEYS_PRIMITIVE
			if (e.getKey() == null || ! (e.getKey() instanceof KEY_CLASS)) return false;
#endif
#if VALUES_PRIMITIVE
			if (e.getValue() == null || ! (e.getValue() instanceof VALUE_CLASS)) return false;
#endif
			final KEY_GENERIC_TYPE k = KEY_OBJ2TYPE(KEY_GENERIC_CAST e.getKey());
			return ARRAY_MAP.this.containsKey(k) && VALUE_EQUALS(ARRAY_MAP.this.GET_VALUE(k), VALUE_OBJ2TYPE(e.getValue()));
		}

		@Override
		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		public boolean remove(final Object o) {
			if (!(o instanceof Map.Entry)) return false;
			final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
#if KEYS_PRIMITIVE
			if (e.getKey() == null || ! (e.getKey() instanceof KEY_CLASS)) return false;
#endif
#if VALUES_PRIMITIVE
			if (e.getValue() == null || ! (e.getValue() instanceof VALUE_CLASS)) return false;
#endif
			final KEY_GENERIC_TYPE k = KEY_OBJ2TYPE(KEY_GENERIC_CAST e.getKey());
			final VALUE_GENERIC_TYPE v = VALUE_OBJ2TYPE(VALUE_GENERIC_CAST e.getValue());

			final int oldPos = ARRAY_MAP.this.findKey(k);
			if (oldPos == -1 || ! VALUE_EQUALS(v, ARRAY_MAP.this.value[oldPos])) return false;
			final int tail = size - oldPos - 1;
			System.arraycopy(ARRAY_MAP.this.key, oldPos + 1, ARRAY_MAP.this.key, oldPos, tail);
			System.arraycopy(ARRAY_MAP.this.value, oldPos + 1, ARRAY_MAP.this.value, oldPos, tail);
			ARRAY_MAP.this.size--;
#if KEYS_REFERENCE
			ARRAY_MAP.this.key[size] = null;
#endif
#if VALUES_REFERENCE
			ARRAY_MAP.this.value[size] = null;
#endif
			return true;
		}
	}

	@Override
	public FastEntrySet KEY_VALUE_GENERIC ENTRYSET() {
		if (entries == null) entries = new EntrySet();
		return entries;
	}

	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;
	}

	@Override
	SUPPRESS_WARNINGS_VALUE_UNCHECKED
	public VALUE_GENERIC_TYPE GET_VALUE(final KEY_TYPE k) {
		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;
	}

	@Override
	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
	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
	SUPPRESS_WARNINGS_VALUE_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
	SUPPRESS_WARNINGS_VALUE_UNCHECKED
	public VALUE_GENERIC_TYPE REMOVE_VALUE(final KEY_TYPE k) {
		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;
		System.arraycopy(key, oldPos + 1, key, oldPos, tail);
		System.arraycopy(value, oldPos + 1, value, oldPos, tail);
		size--;
#if KEYS_REFERENCE
		key[size] = null;
#endif
#if VALUES_REFERENCE
		value[size] = null;
#endif
		return oldValue;
	}

	private final class KeySet extends ABSTRACT_SET KEY_GENERIC {
		@Override
		public boolean contains(final KEY_TYPE k) {
			return findKey(k) != -1;
		}

		@Override
		public boolean remove(final KEY_TYPE k) {
			 final int oldPos = findKey(k);
			 if (oldPos == -1) return false;
			 final int tail = size - oldPos - 1;
			 System.arraycopy(key, oldPos + 1, key, oldPos, tail);
			 System.arraycopy(value, oldPos + 1, value, oldPos, tail);
			 size--;
#if KEYS_REFERENCE
			ARRAY_MAP.this.key[size] = null;
#endif
#if VALUES_REFERENCE
			ARRAY_MAP.this.value[size] = null;
#endif
			 return true;
		}

		@Override
		public KEY_ITERATOR KEY_GENERIC iterator() {
			return new KEY_ITERATOR KEY_GENERIC() {
				int pos = 0;
				@Override
				public boolean hasNext() {
					return pos < size;
				}

				@Override
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				public KEY_GENERIC_TYPE NEXT_KEY() {
					if (! hasNext()) throw new NoSuchElementException();
					return KEY_GENERIC_CAST key[pos++];
				}

				@Override
				public void remove() {
					if (pos == 0) throw new IllegalStateException();
					final int tail = size - pos;
					System.arraycopy(key, pos, key, pos - 1, tail);
					System.arraycopy(value, pos, value, pos - 1, tail);
					size--;
					pos--;
#if KEYS_REFERENCE
					ARRAY_MAP.this.key[size] = null;
#endif
#if VALUES_REFERENCE
					ARRAY_MAP.this.value[size] = null;
#endif
				}

				@Override
				SUPPRESS_WARNINGS_KEY_UNCHECKED
				public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
					// Hoist containing class field ref into local
					final int max = size;
					while (pos < max) {
						action.accept(KEY_GENERIC_CAST key[pos++]);
					}
				}

				// TODO either override skip or extend from AbstractIndexBasedIterator.
			};
		}

		final class KeySetSpliterator extends SPLITERATORS.EarlyBindingSizeIndexBasedSpliterator KEY_GENERIC
				implements KEY_SPLITERATOR KEY_GENERIC {

			KeySetSpliterator(int pos, int maxPos) {
				super(pos, maxPos);
			}

			@Override
			public int characteristics() {
				return SPLITERATORS.SET_SPLITERATOR_CHARACTERISTICS | java.util.Spliterator.SUBSIZED | java.util.Spliterator.ORDERED;
			}

			@Override
			SUPPRESS_WARNINGS_KEY_UNCHECKED
			protected final KEY_GENERIC_TYPE get(int location) { return KEY_GENERIC_CAST key[location]; }

			@Override
			protected final KeySetSpliterator makeForSplit(int pos, int maxPos) {
				return new KeySetSpliterator(pos, maxPos);
			}

			@Override
			SUPPRESS_WARNINGS_KEY_UNCHECKED
			public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
				// Hoist containing class field ref into local
				final int max = size;
				while (pos < max) {
					action.accept(KEY_GENERIC_CAST key[pos++]);
				}
			}
		}

		@Override
		public KEY_SPLITERATOR KEY_GENERIC spliterator() {
			return new KeySetSpliterator(0, size);
		}

		@Override
		SUPPRESS_WARNINGS_KEY_UNCHECKED
		public void forEach(METHOD_ARG_KEY_CONSUMER action) {
			// Hoist containing class field ref into local
			for (int i = 0, max = size; i < max; ++i) {
				action.accept(KEY_GENERIC_CAST key[i]);
			}
		}

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

		@Override
		public void clear() {
			ARRAY_MAP.this.clear();
		}
	}

	@Override
	public SET KEY_GENERIC keySet() {
		if (keys == null) keys = new KeySet();
		return keys;
	}

	private final class ValuesCollection extends VALUE_ABSTRACT_COLLECTION VALUE_GENERIC {
		@Override
		public boolean contains(final VALUE_TYPE v) {
			return containsValue(v);
		}

		@Override
		public VALUE_PACKAGE.VALUE_ITERATOR VALUE_GENERIC iterator() {
			return new VALUE_PACKAGE.VALUE_ITERATOR VALUE_GENERIC() {
				int pos = 0;
				@Override
				public boolean hasNext() {
					return pos < size;
				}

				@Override
				SUPPRESS_WARNINGS_VALUE_UNCHECKED
				public VALUE_GENERIC_TYPE NEXT_VALUE() {
					if (! hasNext()) throw new NoSuchElementException();
					return VALUE_GENERIC_CAST value[pos++];
				}

				@Override
				public void remove() {
					if (pos == 0) throw new IllegalStateException();
					final int tail = size - pos;
					System.arraycopy(key, pos, key, pos - 1, tail);
					System.arraycopy(value, pos, value, pos - 1, tail);
					size--;
					pos--;
#if KEYS_REFERENCE
					ARRAY_MAP.this.key[size] = null;
#endif
#if VALUES_REFERENCE
					ARRAY_MAP.this.value[size] = null;
#endif
				}

				@Override
				SUPPRESS_WARNINGS_VALUE_UNCHECKED
				public void forEachRemaining(final METHOD_ARG_VALUE_CONSUMER action) {
					// Hoist containing class field ref into local
					final int max = size;
					while (pos < max) {
						action.accept(VALUE_GENERIC_CAST value[pos++]);
					}
				}

				// TODO either override skip or extend from AbstractIndexBasedIterator.
			};
		}

		final class ValuesSpliterator extends VALUE_PACKAGE.VALUE_SPLITERATORS.EarlyBindingSizeIndexBasedSpliterator VALUE_GENERIC
				implements VALUE_PACKAGE.VALUE_SPLITERATOR VALUE_GENERIC {

			ValuesSpliterator(int pos, int maxPos) {
				super(pos, maxPos);
			}

			@Override
			public int characteristics() {
				return VALUE_PACKAGE.VALUE_SPLITERATORS.COLLECTION_SPLITERATOR_CHARACTERISTICS
					| java.util.Spliterator.SUBSIZED | java.util.Spliterator.ORDERED;
			}

			@Override
			SUPPRESS_WARNINGS_VALUE_UNCHECKED
			protected final VALUE_GENERIC_TYPE get(int location) { return VALUE_GENERIC_CAST value[location]; }

			@Override
			protected final ValuesSpliterator makeForSplit(int pos, int maxPos) {
				return new ValuesSpliterator(pos, maxPos);
			}

			@Override
			SUPPRESS_WARNINGS_VALUE_UNCHECKED
			public void forEachRemaining(final METHOD_ARG_VALUE_CONSUMER action) {
				// Hoist containing class field ref into local
				final int max = size;
				while (pos < max) {
					action.accept(VALUE_GENERIC_CAST value[pos++]);
				}
			}
		}

		@Override
		public VALUE_PACKAGE.VALUE_SPLITERATOR VALUE_GENERIC spliterator() {
			return new ValuesSpliterator(0, size);
		}

		@Override
		SUPPRESS_WARNINGS_VALUE_UNCHECKED
		public void forEach(METHOD_ARG_VALUE_CONSUMER action) {
			// Hoist containing class field ref into local
			for (int i = 0, max = size; i < max; ++i) {
				action.accept(VALUE_GENERIC_CAST value[i]);
			}
		}

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

		@Override
		public void clear() {
			ARRAY_MAP.this.clear();
		}
	}

	@Override
	public VALUE_COLLECTION VALUE_GENERIC values() {
		if (values == null) values = new ValuesCollection();
		return values;
	}

	/** 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.
	 */
	@Override
	SUPPRESS_WARNINGS_KEY_VALUE_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();
		c.entries = null;
		c.keys = null;
		c.values = null;
		return c;
	}

	private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
		s.defaultWriteObject();
		for(int i = 0, max = size; i < max; i++) {
			s.WRITE_KEY(key[i]);
			s.WRITE_VALUE(value[i]);
		}
	}

	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();
		}
	}
}