path: root/projects/net.wotonomy.foundation/src/main/java/net/wotonomy/foundation/internal/QueueMap.java

/*
Wotonomy: OpenStep design patterns for pure Java applications.
Copyright (C) 2000 Blacksmith, Inc.

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this library; if not, see http://www.gnu.org
*/

package net.wotonomy.foundation.internal;

import java.util.*; //collections

/**
 * A queue based implementation of the Map interface. This class provides for
 * all the operations of a map, but keeps the entries in the same sequence as
 * originally added. The first entry placed in the map will be the first entry
 * retrieved during iteration: first-in, first-out (FIFO). <BR>
 * <BR>
 *
 * Keys cannot be duplicated. If an entry is made using a key that already
 * exists, the value for that key will be replaced with that new value. There
 * are no such restrictions on the values. The values may be null. <BR>
 * <BR>
 *
 * Some convenience methods are provided for the queue type operations. The
 * first key can be retrieved as well as the last key. A key can be used to
 * retrieve its corresponding value from the map. A value can also be used to
 * retrieve its key from the map, however, since there may be multiple values of
 * the same equality, the first key found will be returned. <BR>
 * <BR>
 *
 * @author rglista@blacksmith.com
 * @author mpowers@blacksmith.com
 * @date $Date: 2006-02-18 17:41:36 -0500 (Sat, 18 Feb 2006) $
 * @revision $Revision: 899 $
 */
public class QueueMap<K, V> implements Map<K, V> {
	List<V> values;
	List<K> keys;
	Map<K, V> keyToValue;

	/**
	 * Creates an empty QueueMap.
	 */
	public QueueMap() {
		values = new LinkedList<>();
		keys = new LinkedList<>();
		keyToValue = new HashMap<>();
	}

	/**
	 * Creates a QueueMap and places the entries from the passed in map into this
	 * map. The order of the entries is based on however the iterator iterated
	 * through the map entries.
	 * 
	 * @param t A map object.
	 */
	public QueueMap(Map<K, V> t) {
		values = new ArrayList<>();
		keys = new ArrayList<>();
		keyToValue = new HashMap<>();

		putAll(t);
	}

	/**
	 * Removes all the entries from this map.
	 */
	@Override
	public void clear() {
		values.clear();
		keys.clear();
		keyToValue.clear();
	}

	/**
	 * Tests to see if the key is contained in the map. If the key is present in the
	 * map, then TRUE is returned, otherwise FALSE is returned. The equals()
	 * operation is used to determine equality.
	 * 
	 * @return True if the map contains the given key, false otherwise.
	 */
	@Override
	public boolean containsKey(Object key) {
		return keyToValue.containsKey(key);
	}

	/**
	 * Tests to see if the value is contained in the map. If the value is present in
	 * the map, then TRUE is returned, otherwise FALSE is returned. The equals()
	 * operation is used to determine equality. The value can be null and will
	 * return TRUE if null is a value in the map. If TRUE is returned, then there
	 * may be more than one values in the map.
	 * 
	 * @return True if the map contains the given value, false otherwise.
	 */
	@Override
	public boolean containsValue(Object value) {
		return keyToValue.containsValue(value);
	}

	/**
	 * Returns a set view of the mappings contained in this map. Each element in the
	 * returned set is a <tt>Map.Entry</tt>. The returned set is NOT backed by the
	 * map, so changes to the map are NOT reflected in the set, and vice-versa. The
	 * returned set is independent of this Map and its underlying structure.
	 *
	 * @return a set view of the mappings contained in this map.
	 */
	@Override
	public Set<Map.Entry<K, V>> entrySet() {
		Set<Map.Entry<K, V>> result = new HashSet<>(keys.size(), 1F);

		for (int i = 0; i < keys.size(); i++) {
			result.add(new KeyValuePair<>(keys.get(i), values.get(i)));
		}

		return result;
	}

	/**
	 * Compares the specified object with this map for equality. Returns
	 * <tt>true</tt> if the given object is also a map and the two Maps represent
	 * the same mappings. More formally, two maps <tt>t1</tt> and <tt>t2</tt>
	 * represent the same mappings if <tt>t1.entrySet().equals(t2.entrySet())</tt>.
	 * This ensures that the <tt>equals</tt> method works properly across different
	 * implementations of the <tt>Map</tt> interface.
	 *
	 * @param o object to be compared for equality with this map.
	 * @return <tt>true</tt> if the specified object is equal to this map.
	 */
	@Override
	public boolean equals(Object o) {
		return keyToValue.equals(o);
	}

	/**
	 * Returns the corresponding value for the given key. The returned value may be
	 * null as that is a legal value in this map. However, if the key is not
	 * contained in this map then null is also returned. Use the containsKey()
	 * method to distinguish between the two cases.
	 * 
	 * @param key A key into the map.
	 * @return The value corresponding to the key (can be null), or null if the key
	 *         is not contained in the map.
	 */
	@Override
	public V get(Object key) {
		return keyToValue.get(key);
	}

	/**
	 * Returns the hash code value for this map. The hash code of a map is defined
	 * to be the sum of the hashCodes of each entry in the map's entrySet view. This
	 * ensures that <tt>t1.equals(t2)</tt> implies that
	 * <tt>t1.hashCode()==t2.hashCode()</tt> for any two maps <tt>t1</tt> and
	 * <tt>t2</tt>, as required by the general contract of Object.hashCode.
	 *
	 * @return the hash code value for this map.
	 */
	@Override
	public int hashCode() {
		return keyToValue.hashCode();
	}

	/**
	 * Returns true is this map contains no key-value mappings.
	 * 
	 * @return True is this map contains no entries, false otherwise.
	 */
	@Override
	public boolean isEmpty() {
		return keyToValue.isEmpty();
	}

	/**
	 * Returns the keys used in the map. There is no order implied in the returned
	 * set and may be different than the the order in which they were inserted.
	 * 
	 * @return A Set containing all the keys used in the map.
	 */
	@Override
	public Set<K> keySet() {
		Set<K> result = new HashSet<>(keys.size(), 1F);

		for (int i = 0; i < keys.size(); i++) {
			result.add(keys.get(i));
		}

		return result;
	}

	/**
	 * Places the key/value entry into the map at the end position. If the key
	 * already exists in the map, then its value is replaced by the new given value.
	 * The mapping does not change order in this case. The specified key cannot be
	 * null.
	 * 
	 * @param key   The key to place into the map, cannot be null.
	 * @param value The value to associate with the key, may be null.
	 * @return Null if the key is new, the replaced value if the key already
	 *         existed. (Note: If the key was null, then null is returned.)
	 */
	@Override
	public V put(K key, V value) {
		if (key == null)
			return null;

		if (keys.contains(key)) {
			values.remove(keys.indexOf(key));
			values.add(keys.indexOf(key), value);
		} else {
			values.add(value);
			keys.add(key);
		}

		return keyToValue.put(key, value);
	}

	/**
	 * Places all the entries from this given map into this map. If the keys already
	 * exist, then there values are replaced.
	 * 
	 * @param t A map of key/value entries.
	 */
	@Override
	public void putAll(Map<? extends K, ? extends V> t) {
		if (t == null) {
			// Nothing to do!
			return;
		}

		// Place the entries from the passed in map into this map.
		for (Iterator<? extends K> it = t.keySet().iterator(); it.hasNext();) {
			K aKey = it.next();
			put(aKey, t.get(aKey));
		}
	}

	/**
	 * Remove the mapping of the key and associated value from this map. Note: null
	 * is a valid value in the map.
	 * 
	 * @param key A key to remove from the map, cannot be null.
	 * @return The value of the removed mapping, null if the mapping did not exist.
	 *         Null could also be returned if the associated value of the key was
	 *         null.
	 */
	@Override
	public V remove(Object key) {
		if (key == null)
			return null;

		V value = null;

		if (containsKey(key)) {
			value = keyToValue.remove(key);
			int i = values.indexOf(value);
			if (i != -1) {
				keys.remove(i);
				values.remove(i);
			}
		}

		return value;
	}

	/**
	 * Returns the number of key/value pairs in this map.
	 * 
	 * @return The number of pairs.
	 */
	@Override
	public int size() {
		return values.size();
	}

	/**
	 * Returns an ordered list of keys from the map. The order is the same as the
	 * added order of the mapped items.<br>
	 * NOTE: The returned list is the underlying keys list used by this class. If
	 * modification are to be made to this list, it should be cloned first.
	 * 
	 * @return An ordered list of keys.
	 */
	public List<K> keys() {
		return keys;
	}

	/**
	 * Returns an ordered list of values from the map. The order is the same as the
	 * added order of the mapped items. NOTE: The returned list is the underlying
	 * keys list used by this class. If modification are to be made to this list, it
	 * should be cloned first.
	 * 
	 * @return An ordered list of values.
	 */
	@Override
	public Collection<V> values() {
		return values;
	}

	/**
	 * Returns the corresponding value for the given key. The returned value may be
	 * null as that is a legal value in this map. However, if the key is not
	 * contained in this map then null is also returned. Use the containsKey()
	 * method to distinguish between the two cases.
	 * 
	 * @param key A key into the map.
	 * @return The value corresponding to the key (can be null), or null if the key
	 *         is not contained in the map.
	 */
	public V getValueForKey(K key) {
		return keyToValue.get(key);
	}

	/**
	 * Returns the associated key for this value. Since there may be more than one
	 * of the same value in the map, this returns the first key associated with this
	 * value. Null is returned if the value is not in the map.
	 * 
	 * @param value A value that is contained in this map.
	 * @return A first key that corresponds to this value.
	 */
	public K getKeyForValue(V value) {
		int i = values.indexOf(value);
		if (i != -1) {
			return keys.get(i);
		}
		return null;
	}

	/**
	 * Returns the first key in the map. If the map is empty, then null is returned.
	 * 
	 * @return The first key in the map, null if there are no mappings.
	 */
	public K getFirstKey() {
		if (keys.size() < 1) {
			return null;
		}
		return keys.get(0);
	}

	/**
	 * Returns the last key in the map. If the map is empty, then null is returned.
	 * 
	 * @return The last key in the map, null if there are no mappings.
	 */
	public K getLastKey() {
		if (keys.size() < 1) {
			return null;
		}
		return keys.get(keys.size() - 1);
	}

	/**
	 * This class contains a key/value pair. The key must be a valid object, it
	 * cannot be null. The value can be a valid object or null.
	 */
	static public class KeyValuePair<K, V> implements Map.Entry<K, V> {
		K key;
		V value;

		/**
		 * Default constructor. The constructor takes the key and value as parameters.
		 * Since the key cannot be null, it must be specified during initialization. The
		 * value can be null.
		 * 
		 * @param key   The key object of this pair. The key cannot be null.
		 * @param value The value object of this pair. The value can be null.
		 */
		public KeyValuePair(K aKey, V aValue) {
			key = aKey;
			value = aValue;
		}

		/**
		 * Returns the key object of this pair.
		 * 
		 * @return The key object.
		 */
		@Override
		public K getKey() {
			return key;
		}

		/**
		 * Returns the the value object of this pair. May be null.
		 * 
		 * @return The value object.
		 */
		@Override
		public V getValue() {
			return value;
		}

		/**
		 * Sets the value object of this pair. May be an object or null.
		 * 
		 * @param aValue The value object to place into this pair.
		 */
		@Override
		public V setValue(V aValue) {
			V result = value;
			value = aValue;
			return result;
		}

		@Override
		public boolean equals(Object o) {
			if (o instanceof KeyValuePair) {
				@SuppressWarnings("unchecked")
				KeyValuePair<K, V> p = (KeyValuePair<K, V>) o;
				if ((key.equals(p.getKey())) && (value.equals(p.getValue()))) {
					return true;
				}
			}
			return false;
		}
	}

	/**
	 * Returns a string representation of this class. The contents of the map are
	 * placed in the string in its proper order.
	 */
	@Override
	public String toString() {
		int max = size() - 1;
		StringBuffer buf = new StringBuffer();

		buf.append("{");
		for (int j = 0; j <= max; j++) {
			buf.append(keys.get(j) + "=" + values.get(j));
			if (j < max) {
				buf.append(", ");
			}
		}
		buf.append("}");

		return buf.toString();
	}

	// unit test
	// TODO convert to JUnit test
	public static void main(String[] argv) {
		QueueMap<String, String> qMap;

		qMap = new QueueMap<>();
		for (int i = 0; i < 5; i++) {
			qMap.put(Integer.toString(i), Integer.toString(i));
		}
		System.out.println("\nMap = " + qMap);
		System.out.println("Keys = " + qMap.keys());
		System.out.println("Values = " + qMap.values());

		qMap = new QueueMap<>();
		for (int i = 0; i < 5; i++) {
			qMap.put(Integer.toString(i), "A");
		}
		System.out.println("\nMap = " + qMap);
		System.out.println("Keys = " + qMap.keys());
		System.out.println("Values = " + qMap.values());

		qMap = new QueueMap<>();
		for (int i = 0; i < 5; i++) {
			qMap.put(Integer.toString(i), null);
		}
		System.out.println("\nMap = " + qMap);
		System.out.println("Keys = " + qMap.keys());
		System.out.println("Values = " + qMap.values());

		Map<String, String> aMap = new HashMap<>();
		for (int i = 0; i < 5; i++) {
			aMap.put(Integer.toString(i), Integer.toString(i));
		}
		qMap = new QueueMap<>(aMap);
		System.out.println("\nHashMap = " + aMap);
		System.out.println("Map = " + qMap);
		System.out.println("Keys = " + qMap.keys());
		System.out.println("Values = " + qMap.values());

		qMap = new QueueMap<>();
		qMap.put("Test1", "String1");
		qMap.put("Test2", "String2");
		qMap.put("Test3", "String3");
		qMap.put("Test4", "String4");
		qMap.put("Test5", "String5");
		System.out.println("\nStandard Test, Map = " + qMap);
		qMap.put("Test6", "String6");
		qMap.put("Test7", "String7");
		System.out.println("Put New Test, Map = " + qMap);
		qMap.put("Test2", "New String2");
		qMap.put("Test6", "New String6");
		System.out.println("Put Existing Test, Map = " + qMap);
		qMap.put("Test5", null);
		qMap.put("Test8", null);
		System.out.println("Put Null Test, Map = " + qMap);
		qMap.remove("Test1");
		qMap.remove("Test3");
		qMap.remove("Test5");
		qMap.remove("Test9");
		System.out.println("Remove Test, Map = " + qMap);
		System.out.println("             Keys = " + qMap.keys());
		System.out.println("             Values = " + qMap.values());
		qMap.clear();
		qMap.put("Test10", "String10");
		qMap.put("Test11", "String11");
		qMap.put("Test12", "String12");
		System.out.println("Clear Test, Map = " + qMap);

		aMap = new HashMap<>();
		aMap.put("Test10", "String10");
		aMap.put("Test11", "String11");
		aMap.put("Test12", "String12");
		System.out.println("Equality Test, Equal = " + qMap.equals(aMap));
	}

}