www.pudn.com > GMapViewer-src.zip > LinkedHashtable.java

package org.sreid.j2me.util;

import java.util.*;

/**
 * Hashtable that maintains ordering.
 */
public class LinkedHashtable {

	private final Hashtable ht = new Hashtable(); // can't just subclass, as Hashtable can call put()
	private Entry first = null, last = null; // linked list start and end
	private Class keyType = null, valueType = null;
	private final Entry tmpEntry = new Entry(null, null); // used by getEntry

	private static class Entry {
		Object key;
		Object value;
		Entry prev, next;

		Entry(Object key, Object value) {
			this.key = key;
			this.value = value;
		}
		public boolean equals(Object o) {
			return key.equals(((Entry)o).key);
		}
		public int hashCode() {
			return key.hashCode();
		}
	}

	/**
	 * Constructs a weakly-typed LinkedHashtable.
	 */
	public LinkedHashtable() {
		this(null, null);
	}

	/**
	 * Constructs a strongly-typed LinkedHashtable.
	 */
	public LinkedHashtable(Class keyType, Class valueType) {
		this.keyType = keyType;
		this.valueType = valueType;
	}

	private void checkKey(Object key) {
		if (keyType != null && !keyType.isInstance(key)) {
			throw new ClassCastException("Received key of " + key.getClass() + " but we require " + keyType);
		}
	}
	private void checkValue(Object value) {
		if (valueType != null && !valueType.isInstance(value)) {
			throw new ClassCastException("Received value of " + value.getClass() + " but we require " + valueType);
		}
	}

	public void clear() {
		ht.clear();
		first = last = null;
	}

	public boolean contains(Object value) {
		checkValue(value);
		for (Entry e = first ; e != null ; e = e.next) {
			if ( (e.value == null ? value == null : e.value.equals(value)) ) {
				return true;
			}
		}
		return false;
	}

	public boolean containsKey(Object key) {
		checkKey(key);
		return getEntry(key) != null;
	}

	public Object get(Object key) {
		checkKey(key);
		Entry e = getEntry(key);
		return (e == null ? null : e.value);
	}

	private Entry getEntry(Object key) {
		tmpEntry.key = key; // reuse tmpEntry to reduce alloc/free
		return (Entry)ht.get(tmpEntry);
	}

	private void linkFirst(Entry e) {
		if (isInList(e)) {
			unlink(e);
		}
		if (first == null && last == null) {
			e.prev = e.next = null;
			first = last = e;
		}
		else {
			e.next = first;
			first.prev = e;
			e.prev = null;
			first = e;
		}
	}

	private void linkLast(Entry e) {
		if (isInList(e)) {
			unlink(e);
		}
		if (first == null && last == null) {
			e.prev = e.next = null;
			first = last = e;
		}
		else {
			e.prev = last;
			last.next = e;
			e.next = null;
			last = e;
		}
	}

	private void unlink(Entry e) {
		if (!isInList(e)) {
			return;
		}
		if (e == first) {
			first = e.next;
		}
		else {
			e.prev.next = e.next;
		}
		if (e == last) {
			last = e.prev;
		}
		else {
			e.next.prev = e.prev;
		}
		e.prev = e.next = null;
	}

	private boolean isInList(Entry e) {
		return e.next != null || e.prev != null || e == first || e == last;
	}

	public Object remove(Object key) {
		checkKey(key);
		Entry e = getEntry(key);
		if (e == null) {
			return null; // not in the hashtable in the first place
		}
		else {
			ht.remove(e);
			unlink(e);
			return e.value;
		}
	}

	public int size() {
		return ht.size();
	}

	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append('{');
		for (Entry e = first; e != null; e = e.next) {
			sb.append(e.key);
			sb.append('=');
			sb.append(e.value);
			if (e.next != null) sb.append(", ");
		}
		sb.append('}');
		return sb.toString();
	}

	private Entry justPut(Object key, Object value) {
		Entry existing = getEntry(key);
		if (existing != null) {
			existing.value = value;
			return existing;
		}
		else {
			Entry e = new Entry(key, value);
			ht.put(e, e);
			return e;
		}
	}

	public Object put(Object key, Object value) {
		Object oldVal = get(key);
		checkValue(value);
		Entry e = justPut(key, value);
		if (!isInList(e)) linkLast(e); // only move it if it's a new entry
		return oldVal;
	}

	public Object putFirst(Object key, Object value) {
		Object oldVal = get(key);
		checkValue(value);
		Entry e = justPut(key, value);
		linkFirst(e);
		return oldVal;
	}
		
	public Object putLast(Object key, Object value) {
		Object oldVal = get(key);
		checkValue(value);
		Entry e = justPut(key, value);
		linkLast(e);
		return oldVal;
	}

	public Object firstKey() {
		return (first == null ? null : first.key);
	}
	public Object firstElement() {
		return (first == null ? null : first.value);
	}
	public Object lastKey() {
		return (last == null ? null : last.key);
	}
	public Object lastElement() {
		return (last == null ? null : last.value);
	}

	public Enumeration keys() {
		return new LinkedHashtableEnumeration(true, true);
	}
	public Enumeration elements() {
		return new LinkedHashtableEnumeration(true, false);
	}
	public Enumeration keysInReverse() {
		return new LinkedHashtableEnumeration(false, true);
	}
	public Enumeration elementsInReverse() {
		return new LinkedHashtableEnumeration(false, false);
	}

	private class LinkedHashtableEnumeration implements Enumeration {
		Entry e;
		final boolean forward;
		final boolean keys;
		LinkedHashtableEnumeration(boolean forward, boolean keys) {
			this.forward = forward;
			this.keys = keys;
			e = (forward ? first : last);
		}
		public boolean hasMoreElements() {
			return (e != null);
		}
		public Object nextElement() {
			if (e == null) throw new NoSuchElementException();
			Object retval = (keys ? e.key : e.value);
			e = (forward ? e.next : e.prev);
			return retval;
		}
	}

	/*
	public static void main(String[] args) {
		new Test().test();
	}

	private static class Test {
		final LinkedHashtable lh = new LinkedHashtable();
		final String[] items = new String[] {
			"One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten"
		};

		void test() {
			for (int i = 0; i < items.length; i++) {
				lh.put("k" + items[i], "v" + items[i]);
			}
			validate("k", "v");
			for (int i = 0; i < items.length; i++) {
				lh.put("k" + items[i], "v" + items[i]);
			}
			validate("k", "v");
			for (int i = items.length - 1; i >= 0; i--) {
				lh.putFirst("k" + items[i], "v" + items[i]);
			}
			validate("k", "v");
			for (int i = 0; i < items.length; i++) {
				lh.putLast("k" + items[i], "v" + items[i]);
			}
			validate("k", "v");
			for (int i = items.length - 1; i >= 0; i--) {
				lh.putFirst("k" + items[i], "v" + items[i]);
				lh.putFirst("k2" + items[i], "v2" + items[i]);
			}
			for (int i = 0; i < items.length; i++) {
				lh.remove("k" + items[i]);
			}
			validate("k2", "v2");
			System.out.println("Test okay.");
		}

		void validate(String keyPrefix, String valuePrefix) {
			int i;
			Enumeration e;
			for (e = lh.keys(), i = 0 ; e.hasMoreElements() ; i++) {
				if (!e.nextElement().equals(keyPrefix + items[i])) throw new Error();
			}
			for (e = lh.elements(), i = 0 ; e.hasMoreElements() ; i++) {
				if (!e.nextElement().equals(valuePrefix + items[i])) throw new Error();
			}
			for (e = lh.keysInReverse(), i = 9 ; e.hasMoreElements() ; i--) {
				if (!e.nextElement().equals(keyPrefix + items[i])) throw new Error();
			}
			for (e = lh.elementsInReverse(), i = 9 ; e.hasMoreElements() ; i--) {
				if (!e.nextElement().equals(valuePrefix + items[i])) throw new Error();
			}
		}
	}
	*/
}