/*
 * Copyright (C) 2002-2024 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 static it.unimi.dsi.fastutil.Size64.sizeOf;
#if KEY_INDEX != VALUE_INDEX && !(KEYS_REFERENCE && VALUES_REFERENCE)
import VALUE_PACKAGE.VALUE_COLLECTION;
import VALUE_PACKAGE.VALUE_ABSTRACT_COLLECTION;
import VALUE_PACKAGE.VALUE_ITERATOR;
import VALUE_PACKAGE.VALUE_SPLITERATOR;
import VALUE_PACKAGE.VALUE_SPLITERATORS;
#if VALUES_BYTE_CHAR_SHORT_FLOAT || VALUE_CLASS_Boolean
import VALUE_PACKAGE.VALUE_CONSUMER;
#endif
#endif

#if KEYS_PRIMITIVE && VALUES_PRIMITIVE
import it.unimi.dsi.fastutil.objects.ObjectIterator;
import it.unimi.dsi.fastutil.objects.ObjectSpliterator;
import it.unimi.dsi.fastutil.objects.ObjectSpliterators;
#else
import java.util.function.Consumer;
#endif

#if KEYS_PRIMITIVE
import it.unimi.dsi.fastutil.objects.AbstractObjectSet;
#endif

import java.util.Iterator;
import java.util.Map;

/** An abstract class providing basic methods for maps implementing a type-specific interface.
 *
 * <p>Optional operations just throw an {@link
 * UnsupportedOperationException}. Generic versions of accessors delegate to
 * the corresponding type-specific counterparts following the interface rules
 * (they take care of returning {@code null} on a missing key).
 *
 * <p>As a further help, this class provides a {@link BasicEntry BasicEntry} inner class
 * that implements a type-specific version of {@link java.util.Map.Entry}; it
 * is particularly useful for those classes that do not implement their own
 * entries (e.g., most immutable maps).
 */

public abstract class ABSTRACT_MAP KEY_VALUE_GENERIC extends ABSTRACT_FUNCTION KEY_VALUE_GENERIC implements MAP KEY_VALUE_GENERIC, java.io.Serializable {

	private static final long serialVersionUID = -4940583368468432370L;

	protected ABSTRACT_MAP() {}

	/**
	 * {@inheritDoc}
	 * @implSpec This implementation does a linear search over the entry set, finding an entry that has the key specified.
	 *   <p>If you override {@link #keySet()}, you should probably override this method too
	 *   to take advantage of the (presumably) faster {@linkplain java.util.Set#contains key membership test} your {@link #keySet()} provides.
	 *   <p>If you override this method but not {@link #keySet()}, then the returned key set will take advantage of this method.
	 */
	@Override
	public boolean containsKey(final KEY_TYPE k) {
		final ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> i = ENTRYSET().iterator();
		while(i.hasNext())
			if (i.next().ENTRY_GET_KEY() == k)
				return true;

		return false;
	}

	/**
	 * {@inheritDoc}
	 * @implSpec This implementation does a linear search over the entry set, finding an entry that has the value specified.
	 *   <p>If you override {@link #values()}, you should probably override this method too
	 *   to take advantage of the (presumably) faster {@linkplain java.util.Collection#contains value membership test} your {@link #values()} provides.
	 *   <p>If you override this method but not {@link #values()}, then the returned values collection will take advantage of this method.
	 */
	@Override
	public boolean containsValue(final VALUE_TYPE v) {
		final ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> i = ENTRYSET().iterator();
		while(i.hasNext())
			if (i.next().ENTRY_GET_VALUE() == v)
				return true;

		return false;
	}

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

#if VALUES_INT_LONG_DOUBLE
	/** {@inheritDoc} 
	 * @implSpec This method just delegates to the interface default method,
	 * as the default method, but it is final, so it cannot be overridden.
	 */
	@Override
	public final VALUE_TYPE MERGE_VALUE(final KEY_GENERIC_TYPE key, final VALUE_TYPE value, final VALUE_PACKAGE.VALUE_BINARY_OPERATOR remappingFunction) {
		return MERGE_VALUE(key, value, (JDK_PRIMITIVE_VALUE_BINARY_OPERATOR)remappingFunction);
	}
#endif

	/** This class provides a basic but complete type-specific entry class for all those maps implementations
	 * that do not have entries on their own (e.g., most immutable maps).
	 *
	 * <p>This class does not implement {@link java.util.Map.Entry#setValue(Object) setValue()}, as the modification
	 * would not be reflected in the base map.
	 */

	public static class BasicEntry KEY_VALUE_GENERIC implements MAP.Entry KEY_VALUE_GENERIC {
		protected KEY_GENERIC_TYPE key;
		protected VALUE_GENERIC_TYPE value;

		public BasicEntry() {}

		public BasicEntry(final KEY_GENERIC_CLASS key, final VALUE_GENERIC_CLASS value) {
			this.key = KEY_CLASS2TYPE(key);
			this.value = VALUE_CLASS2TYPE(value);
		}

#if KEYS_PRIMITIVE || VALUES_PRIMITIVE

		public BasicEntry(final KEY_GENERIC_TYPE key, final VALUE_GENERIC_TYPE value) {
			this.key = key;
			this.value = value;
		}

#endif

		@Override
		public KEY_GENERIC_TYPE ENTRY_GET_KEY() {
			return key;
		}

		@Override
		public VALUE_GENERIC_TYPE ENTRY_GET_VALUE() {
			return value;
		}

		@Override
		public VALUE_GENERIC_TYPE setValue(final VALUE_GENERIC_TYPE value) {
			throw new UnsupportedOperationException();
		}

		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		@Override
		public boolean equals(final Object o) {
			if (!(o instanceof Map.Entry)) return false;
			if (o instanceof MAP.Entry) {
				final MAP.Entry KEY_VALUE_GENERIC e = (MAP.Entry KEY_VALUE_GENERIC) o;
				return KEY_EQUALS(key, e.ENTRY_GET_KEY()) && VALUE_EQUALS(value, e.ENTRY_GET_VALUE());
			}

			final Map.Entry<?,?> e = (Map.Entry<?,?>)o;
			final Object key = e.getKey();
#if KEYS_PRIMITIVE
			if (key == null || !(key instanceof KEY_CLASS)) return false;
#endif
			final Object value = e.getValue();
#if VALUES_PRIMITIVE
			if (value == null || !(value instanceof VALUE_CLASS)) return false;
#endif
			return KEY_EQUALS(this.key, KEY_OBJ2TYPE(key)) && VALUE_EQUALS(this.value, VALUE_OBJ2TYPE(value));
		}

		@Override
		public int hashCode() {
			return KEY2JAVAHASH(key) ^ VALUE2JAVAHASH(value);
		}

		@Override
		public String toString() {
			return key + "->" + value;
		}
	}

	/** This class provides a basic implementation for an Entry set which forwards some queries to the map.
	 */

	public abstract static class BasicEntrySet KEY_VALUE_GENERIC extends AbstractObjectSet<Entry KEY_VALUE_GENERIC> {
		protected final MAP KEY_VALUE_GENERIC map;

		public BasicEntrySet(final MAP KEY_VALUE_GENERIC map) {
			this.map = map;
		}

		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		@Override
		public boolean contains(final Object o) {
			if (!(o instanceof Map.Entry)) return false;

			if (o instanceof MAP.Entry) {
				final MAP.Entry KEY_VALUE_GENERIC e = (MAP.Entry KEY_VALUE_GENERIC) o;
				final KEY_GENERIC_TYPE k = e.ENTRY_GET_KEY();
				return map.containsKey(k) && VALUE_EQUALS(map.GET_VALUE(k), e.ENTRY_GET_VALUE());
			}

			final Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;

#if KEYS_PRIMITIVE
			final Object key = e.getKey();
			if (key == null || !(key instanceof KEY_GENERIC_CLASS)) return false;
			final KEY_TYPE k = KEY_OBJ2TYPE(key);
#else
			final Object k = e.getKey();
#endif
			final Object value = e.getValue();
#if VALUES_PRIMITIVE
			if (value == null || !(value instanceof VALUE_GENERIC_CLASS)) return false;
#endif

			return map.containsKey(k) && VALUE_EQUALS(map.GET_VALUE(k), VALUE_OBJ2TYPE(value));
		}

		SUPPRESS_WARNINGS_KEY_VALUE_UNCHECKED
		@Override
		public boolean remove(final Object o) {
			if (!(o instanceof Map.Entry)) return false;

			if (o instanceof MAP.Entry) {
				final MAP.Entry KEY_VALUE_GENERIC e = (MAP.Entry KEY_VALUE_GENERIC) o;
				return map.remove(e.ENTRY_GET_KEY(), e.ENTRY_GET_VALUE());
			}

			Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;

#if KEYS_PRIMITIVE
			final Object key = e.getKey();
			if (key == null || !(key instanceof KEY_GENERIC_CLASS)) return false;
			final KEY_TYPE k = KEY_OBJ2TYPE(key);
#else
			final Object k = e.getKey();
#endif
#if VALUES_PRIMITIVE
			final Object value = e.getValue();
			if (value == null || !(value instanceof VALUE_GENERIC_CLASS)) return false;
			final VALUE_TYPE v = VALUE_OBJ2TYPE(value);
#else
			final Object v = e.getValue();
#endif

			return map.remove(k, v);
		}

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

		@Override
		public ObjectSpliterator<Entry KEY_VALUE_GENERIC> spliterator() {
			return ObjectSpliterators.asSpliterator(
				iterator(), sizeOf(map), ObjectSpliterators.SET_SPLITERATOR_CHARACTERISTICS);
		}
	}


	/** Returns a type-specific-set view of the keys of this map.
	 *
	 * <p>The view is backed by the set returned by {@link Map#entrySet()}. Note that
	 * <em>no attempt is made at caching the result of this method</em>, as this would
	 * require adding some attributes that lightweight implementations would
	 * not need. Subclasses may easily override this policy by calling
	 * this method and caching the result, but implementors are encouraged to
	 * write more efficient ad-hoc implementations.
	 *
	 * @return a set view of the keys of this map; it may be safely cast to a type-specific interface.
	 */
	@Override
	public SET KEY_GENERIC keySet() {
		return new ABSTRACT_SET KEY_GENERIC() {
				@Override
				public boolean contains(final KEY_TYPE k) { return containsKey(k); }
				@Override
				public int size() { return ABSTRACT_MAP.this.size(); }
				@Override
				public void clear() { ABSTRACT_MAP.this.clear(); }
				@Override
				public KEY_ITERATOR KEY_GENERIC iterator() {
					return new KEY_ITERATOR KEY_GENERIC() {
							private final ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> i = MAPS.fastIterator(ABSTRACT_MAP.this);
							@Override
							public KEY_GENERIC_TYPE NEXT_KEY() { return i.next().ENTRY_GET_KEY(); }
							@Override
							public boolean hasNext() { return i.hasNext(); }
							@Override
							public void remove() { i.remove(); }
							@Override
							public void forEachRemaining(final METHOD_ARG_KEY_CONSUMER action) {
								i.forEachRemaining(entry -> action.accept(entry.ENTRY_GET_KEY()));
							}
						};
				}
				@Override
				public KEY_SPLITERATOR KEY_GENERIC spliterator() {
					return SPLITERATORS.asSpliterator(
						iterator(), sizeOf(ABSTRACT_MAP.this), SPLITERATORS.SET_SPLITERATOR_CHARACTERISTICS);
				}
			};
	}

	/** Returns a type-specific-set view of the values of this map.
	 *
	 * <p>The view is backed by the set returned by {@link Map#entrySet()}. Note that
	 * <em>no attempt is made at caching the result of this method</em>, as this would
	 * require adding some attributes that lightweight implementations would
	 * not need. Subclasses may easily override this policy by calling
	 * this method and caching the result, but implementors are encouraged to
	 * write more efficient ad-hoc implementations.
	 *
	 * @return a set view of the values of this map; it may be safely cast to a type-specific interface.
	 */
	@Override
	public VALUE_COLLECTION VALUE_GENERIC values() {
		return new VALUE_ABSTRACT_COLLECTION VALUE_GENERIC() {
				@Override
				public boolean contains(final VALUE_TYPE k) { return containsValue(k); }
				@Override
				public int size() { return ABSTRACT_MAP.this.size(); }
				@Override
				public void clear() { ABSTRACT_MAP.this.clear(); }

				@Override
				public VALUE_ITERATOR VALUE_GENERIC iterator() {
					return new VALUE_ITERATOR VALUE_GENERIC() {
							private final ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> i = MAPS.fastIterator(ABSTRACT_MAP.this);
							@Override
							public VALUE_GENERIC_TYPE NEXT_VALUE() { return i.next().ENTRY_GET_VALUE(); }
							@Override
							public boolean hasNext() { return i.hasNext(); }
							@Override
							public void remove() { i.remove(); }
							@Override
							public void forEachRemaining(final METHOD_ARG_VALUE_CONSUMER action) {
								i.forEachRemaining(entry -> action.accept(entry.ENTRY_GET_VALUE()));
							}
						};
				}
				@Override
				public VALUE_SPLITERATOR VALUE_GENERIC spliterator() {
					return VALUE_SPLITERATORS.asSpliterator(
						iterator(), sizeOf(ABSTRACT_MAP.this), VALUE_SPLITERATORS.COLLECTION_SPLITERATOR_CHARACTERISTICS);
				}
			};
	}

	/** {@inheritDoc} */
	@SuppressWarnings({"unchecked", "deprecation"})
	@Override
	public void putAll(final Map<? extends KEY_GENERIC_CLASS,? extends VALUE_GENERIC_CLASS> m) {
		if (m instanceof MAP) {
			ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> i = MAPS.fastIterator((MAP KEY_VALUE_GENERIC) m);

			while (i.hasNext()) {
				final MAP.Entry KEY_VALUE_EXTENDS_GENERIC e = i.next();
				put(e.ENTRY_GET_KEY(), e.ENTRY_GET_VALUE());
			}
		} else {
			int n = m.size();
			final Iterator<? extends Map.Entry<? extends KEY_GENERIC_CLASS,? extends VALUE_GENERIC_CLASS>> i = m.entrySet().iterator();
			Map.Entry<? extends KEY_GENERIC_CLASS,? extends VALUE_GENERIC_CLASS> e;
			while (n-- != 0) {
				e = i.next();
				put(e.getKey(), e.getValue());
			}
		}
	}

	/** Returns a hash code for this map.
	 *
	 * The hash code of a map is computed by summing the hash codes of its entries.
	 *
	 * @return a hash code for this map.
	 */
	@Override
	public int hashCode() {
		int h = 0, n = size();
		final ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> i = MAPS.fastIterator(this);

		while(n-- != 0) h += i.next().hashCode();
		return h;
	}

	@Override
	public boolean equals(Object o) {
		if (o == this) return true;
		if (! (o instanceof Map)) return false;

		final Map<?,?> m = (Map<?,?>)o;
		if (m.size() != size()) return false;
		return ENTRYSET().containsAll(m.entrySet());
	}

	@Override
	public String toString() {
		final StringBuilder s = new StringBuilder();
		final ObjectIterator<MAP.Entry KEY_VALUE_GENERIC> i = MAPS.fastIterator(this);
		int n = size();
		MAP.Entry KEY_VALUE_GENERIC e;
		boolean first = true;

		s.append("{");

		while(n-- != 0) {
			if (first) first = false;
			else s.append(", ");

			e = i.next();

#if KEYS_REFERENCE
			if (this == e.getKey()) s.append("(this map)"); else
#endif
				s.append(String.valueOf(e.ENTRY_GET_KEY()));
			s.append("=>");
#if VALUES_REFERENCE
			if (this == e.getValue()) s.append("(this map)"); else
#endif
				s.append(String.valueOf(e.ENTRY_GET_VALUE()));
		}

		s.append("}");
		return s.toString();
	}
}