what

package cmsc420.bstrie;
/*
 * Author: Patrick
 * 
 * Created on Oct 11, 2004
 * 
 * .BPTree
 * 
 * modified by Di-Wei, summer 2010
 */
 
import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.SortedMap;
 
import org.w3c.dom.Document;
import org.w3c.dom.Element;
 
/**
 * BSTrie -
 */
@SuppressWarnings("unchecked")
public class BSTrie<K, V> implements SortedMap<K, V>{
 
	private RootNode root;
	private int size = 0;
	private final int cardinality;
	private int height = 1;
 
	protected int modCount = Integer.MIN_VALUE;
 
	public BSTrie(Comparator<K> comparator, int cardinality){
		root = new RootNode(comparator, cardinality);
		this.cardinality = cardinality;
	}
 
	public Comparator comparator(){
		return root.getComparator();
	}
 
	/* important method - basically done....*/
	public K firstKey(){
		if (isEmpty()){
			throw new NoSuchElementException();
		}
		return root.getFirstLeaf().getKeys().get(0);
	}
 
	/* IMPORTANT METHOD */
	public SortedMap headMap(Object arg0){
		throw new UnsupportedOperationException("HeadMap is not implemented");
	}
 
	/* important method- basically done...*/
	public K lastKey(){
		if (isEmpty())
			throw new NoSuchElementException();
		LeafNode<K, V> l = root.getLastLeaf();
		List<K> keys = l.getKeys();
		return keys.get(keys.size() - 1);
	}
 
	/* IMPORTANT METHOD */
	/*
	 * Like the entrySet() method which returns an inner class of your BSTrie whose 
	 * methods simply call the methods in the BSTrie class, you will be doing something 
	 * similiar with subMap(), except this time you will check the arguments before 
	 * blindly forwarding the method call to BSTrie. For instance, when invoking 
	 * put() on the submap returned by the method, if the specied key does not fall 
	 * between fromKey and toKey according to the rules of the API, the method throws 
	 * an IllegalArgumentException instead of forwarding the call to put in the BSTrie class.
	 * REFER TO BOTTOM OF PAGE 10
	 */
	public SortedMap<K, V> subMap(K arg0, K arg1){
		throw new UnsupportedOperationException("Submap is not implemented");
	}
 
	/* IMPORTANT METHOD */
	public SortedMap<K, V> tailMap(K arg0){
		throw new UnsupportedOperationException("TailMap is not implemented");
	}
 
	public void clear(){
		root = new RootNode(root.getComparator(), cardinality);
		size = 0;
		modCount++;
	}
 
	public boolean containsKey(Object key){
		if (key == null)
			throw new NullPointerException();
 
		return root.contains((K) key);
	}
 
	public boolean containsValue(Object arg0){
		Iterator it = entrySet().iterator();
		while (it.hasNext()){
			if (((Entry) it.next()).getValue().equals(arg0))
				return true;
		}
		return false;
	}
 
	public Set<Map.Entry<K, V>> entrySet(){
		return new EntrySet();
	}
 
	public V get(Object key){
		if (key == null)
			throw new NullPointerException();
 
		return root.get((K) key);
	}
 
	public boolean isEmpty(){
		return size == 0;
	}
 
	/* IMPORTANT METHOD - basically done... for now */
	public Set keySet(){
		return new KeySet();
	}
 
	public V put(K key, V value){
		if (key == null)
			throw new NullPointerException();
 
		V oldVal = get(key);
		if (!root.contains(key) && size != Integer.MAX_VALUE)
			size++;
 
		root.put(key, value);
		modCount++;
		return oldVal;
	}
 
	public void putAll(Map<? extends K, ? extends V> entries){
		Iterator<? extends K> it = entries.keySet().iterator();
		K key;
		while (it.hasNext())
		{
			key = it.next();
			put(key, entries.get(key));
		}
	}
 
	/* IMPORTANT METHOD - LAST ONE TO DO...*/
	public V remove(Object arg0){
		throw new UnsupportedOperationException("Remove is not implemented");
	}
 
	public int size(){
		return size;
	}
 
	/* IMPORTANT METHOD - still need to implement ValueCollection */
	public Collection<V> values(){
		return new ValueCollection();
	}
 
	public boolean equals(Object arg0){
		if (arg0 instanceof Map)
		{
			Map m1 = (Map) arg0;
			return m1.entrySet().equals(entrySet());
		}
		return false;
	}
 
	public int hashCode()
	{
		return entrySet().hashCode();
	}
 
	private class RootNode extends Node<K, V>
	{
		private Node<K, V> me;
		private EndNode<K, V> first;
		private EndNode<K, V> last;
		private int cardinality;
 
		public RootNode(Comparator<K> comparator, int cardinality)
		{
			super(comparator);
			this.cardinality = cardinality;
			LeafNode<K, V> tmp = new LeafNode<K, V>(comparator, this.cardinality);
			this.first = new EndNode<K, V>();
			this.last = new EndNode<K, V>();
			this.first.setRight(tmp);
			this.last.setLeft(tmp);
			tmp.setLeft(first);
			tmp.setRight(last);
			this.me = tmp;
		}
 
		public boolean contains(K key)
		{
			return me.contains(key);
		}
 
		public V get(K key)
		{
			return me.get(key);
		}
 
		public V remove(K key)
		{
			throw new UnsupportedOperationException("Remove is not implemented");
		}
 
		public Comparator<K> getComparator()
		{
			return me.getComparator();
		}
 
		public GuideNode<K, V> getParent()
		{
			return me.getParent();
		}
 
		public boolean isFull()
		{
			return me.isFull();
		}
 
		public boolean isEmpty()
		{
			return me.isEmpty();
		}
 
		public void put(K key, V value)
		{
			if (isFull())
			{
				// Add a new root node before insertion. If after insertion the new
				// root is not needed (i.e, it has only one kid), delete it.
				GuideNode<K, V> n = new GuideNode<K, V>(me.getComparator());
				n.setLeft(new EndNode<K, V>());
				n.setRight(new EndNode<K, V>());
				n.getLeft().setRight(n);
				n.getRight().setLeft(n);
				me.setParent(n);
				me.put(key, value);
				if (!n.isEmpty())
				{
					me = n;
					height++;
				}
				else
					me.setParent(null);
			}
			else
			{
				me.put(key, value);
			}
		}
 
		public void setParent(GuideNode<K, V> parent){
			me.setParent(parent);
		}
 
		public LeafNode<K, V> getFirstLeaf(){
			return (LeafNode<K, V>) first.getRight();
		}
 
		public LeafNode<K, V> getLastLeaf()
		{
			return (LeafNode<K, V>) last.getLeft();
		}
 
		public void printXML(Element parent, Document results) {
			me.printXML(parent, results);
		}
	}
 
	private class Entry implements Map.Entry<K, V>
	{
		private K key;
 
		public Entry(K key)
		{
			this.key = key;
		}
 
		public K getKey()
		{
			return key;
		}
 
		public V getValue()
		{
			return get(key);
		}
 
		public V setValue(V arg0)
		{
			return put(key, arg0);
		}
 
		public boolean equals(Object arg0)
		{
			if (arg0 instanceof Map.Entry)
			{
				Map.Entry e2 = (Map.Entry) arg0;
				return (key == null ? e2.getKey() == null : key.equals(e2
						.getKey()))
						&& (getValue() == null ? e2.getValue() == null
								: getValue().equals(e2.getValue()));
			}
			return false;
		}
 
		public int hashCode()
		{
			return (key == null ? 0 : key.hashCode())
			^ (getValue() == null ? 0 : getValue().hashCode());
		}
	}
 
	private class EntrySet implements Set<Map.Entry<K, V>>
	{
		public boolean add(Map.Entry<K, V> arg0)
		{
			throw new UnsupportedOperationException();
		}
 
		public boolean addAll(Collection<? extends Map.Entry<K, V>> arg0)
		{
			throw new UnsupportedOperationException();
		}
 
		public void clear()
		{
			BSTrie.this.clear();
		}
 
		public boolean contains(Object entry)
		{
			Map.Entry e1 = (Map.Entry) entry;
			Object value = BSTrie.this.get(e1.getKey());
			return e1.getValue() == null ? value == null : e1.getValue()
					.equals(value);
		}
 
		public boolean containsAll(Collection<?> entries)
		{
			Iterator it = entries.iterator();
			boolean flag = true;
			while (it.hasNext())
			{
				flag = flag && contains(it.next());
			}
			return flag;
		}
 
		public boolean isEmpty()
		{
			return BSTrie.this.isEmpty();
		}
 
		public Iterator iterator()
		{
			return new EntryIterator();
		}
 
		public boolean remove(Object entry){
			if (entry instanceof Map.Entry)
				return BSTrie.this.remove(((Entry) entry).getKey()) != null;
			return false;
		}
 
		public boolean removeAll(Collection entries)
		{
			Iterator it = entries.iterator();
			boolean flag = false;
			while (it.hasNext())
			{
				flag = flag || remove(it.next());
			}
			return flag;
		}
 
		public boolean retainAll(Collection entries)
		{
			Iterator it = new EntryIterator();
			boolean flag = false;
			while (it.hasNext())
			{
				if (!entries.contains(it.next()))
				{
					it.remove();
					flag = true;
				}
			}
			return flag;
		}
 
		public int size()
		{
			return BSTrie.this.size();
		}
 
		public Object[] toArray()
		{
			Object[] arr = new Object[size()];
			Iterator it = new EntryIterator();
			for (int i = 0; it.hasNext(); i++)
			{
				arr[i] = it.next();
			}
			return arr;
		}
 
		public Object[] toArray(Object[] array)
		{
			if (array.length < size())
				array = (Object[]) Array.newInstance(array.getClass()
						.getComponentType(), size());
 
			Iterator it = new EntryIterator();
			for (int i = 0; it.hasNext(); i++)
			{
				array[i] = it.next();
			}
			return array;
		}
 
		public boolean equals(Object arg0)
		{
			if (arg0 instanceof Set)
			{
				Set s1 = (Set) arg0;
				if (s1.size() != size())
					return false;
 
				Iterator it = s1.iterator();
				while (it.hasNext())
				{
					if (!contains(it.next()))
						return false;
				}
			}
			return true;
		}
 
		public int hashCode()
		{
			Iterator it = iterator();
			int hashCode = 0;
			while (it.hasNext())
			{
				hashCode += it.next().hashCode();
			}
			return hashCode;
		}
 
		private class EntryIterator implements Iterator<Map.Entry<K, V>>{
			private Entry curr, prev;
			private LeafNode<K, V> currNode;
			private Iterator<K> it;
			private int modCount = BSTrie.this.modCount;
 
			public EntryIterator()
			{
				if (BSTrie.this.isEmpty())
					return;
 
				this.currNode = root.getFirstLeaf();
				this.it = currNode.keyIterator();
 
				while (curr == null
						|| BSTrie.this.comparator().compare(curr.getKey(),
								BSTrie.this.firstKey()) < 0)
				{
					if (!it.hasNext())
					{
						if (currNode.getRight() instanceof EndNode)
							return;
 
						currNode = (LeafNode) currNode.getRight();
						it = currNode.keyIterator();
						continue;
					}
 
					curr = new Entry(it.next());
				}
			}
 
			public boolean hasNext()
			{
				return curr != null;
			}
 
			public Map.Entry<K, V> next()
			{
				if (modCount != BSTrie.this.modCount)
					throw new ConcurrentModificationException();
 
				if (curr == null)
					throw new NoSuchElementException();
 
				if (!it.hasNext() && !(currNode.getRight() instanceof EndNode))
				{
					currNode = (LeafNode) currNode.getRight();
					it = currNode.keyIterator();
					return next();
				}
 
				prev = curr;
				if (it.hasNext() && curr != null && BSTrie.this.lastKey() != null
						&& cmp(curr.getKey(), BSTrie.this.lastKey()) < 0)
					curr = new Entry(it.next());
				else
					curr = null;
 
				return prev;
			}
 
			public void remove()
			{
				BSTrie.this.remove(prev.getKey());
			}
 
			private int cmp(Object o1, Object o2)
			{
				return BSTrie.this.comparator().compare(o1, o2);
			}
		}
	}
 
 
 
 
	private class KeySet implements Set<K>{
 
		@Override
		public boolean add(K arg0) {
			throw new UnsupportedOperationException();
		}
 
		@Override
		public boolean addAll(Collection<? extends K> c) {
			throw new UnsupportedOperationException();
		}
 
		@Override
		public void clear() {
			BSTrie.this.clear();
		}
 
		@Override
		public boolean contains(Object key) {
			K k = (K) key;
			return BSTrie.this.containsKey(k);
		}
 
		@Override
		public boolean containsAll(Collection<?> c) {
			Iterator it = c.iterator();
			boolean flag = true;
			while (it.hasNext())
			{
				flag = flag && contains(it.next());
			}
			return flag;
		}
 
		@Override
		public boolean isEmpty() {
			return BSTrie.this.isEmpty();
		}
 
		@Override
		public Iterator<K> iterator() {
			return new KeyIterator();
		}
 
		@Override
		public boolean remove(Object o) {
			if(((K)o) != null){	
				return BSTrie.this.remove((K)o) != null;
			}
			return false;
		}
		@Override
		public boolean removeAll(Collection<?> c) {
			Iterator it = c.iterator();
			boolean flag = false;
			while(it.hasNext()){
				flag = flag || remove(it.next());
			}
			return flag;
		}
 
 
 
		@Override
		public boolean retainAll(Collection<?> c) {
			Iterator it = new KeyIterator();
			boolean flag = false;
			while(it.hasNext()){
				if(!c.contains(it.next())){
					it.remove();
					flag = true;
				}
			}
			return flag;
		}
 
 
 
		@Override
		public int size() {
			return BSTrie.this.size();
		}
 
		@Override
		public Object[] toArray() {
			Object[] arr = new Object[size()];
			Iterator it = new KeyIterator();
			for (int i = 0; it.hasNext(); i++){
				arr[i] = it.next();
			}
			return arr;
		}
 
 
		@Override
		public <K> K[] toArray(K[] a) {
			if(a.length < size()){
				a = (K[]) Array.newInstance(a.getClass().getComponentType(), size());
			}
 
			Iterator it = new KeyIterator();
			for(int i = 0; it.hasNext(); i++){
				a[i] = (K) it.next();
			}
			return a;
		}
 
 
		private class KeyIterator implements Iterator<K>{
			private Entry curr, prev;
			private LeafNode<K, V> currNode;
			private Iterator<K> it;
			private int modCount = BSTrie.this.modCount;
 
			public KeyIterator(){
				if (BSTrie.this.isEmpty()){
					return;
				}
 
				this.currNode = root.getFirstLeaf();
				this.it = currNode.keyIterator();
 
 
				while (curr == null || BSTrie.this.comparator().compare(curr.getKey(), 
						BSTrie.this.firstKey()) < 0){
					if (!it.hasNext()){
						if (currNode.getRight() instanceof EndNode)
							return;
 
						currNode = (LeafNode) currNode.getRight();
						it = currNode.keyIterator();
						continue;
					}
 
					curr = new Entry(it.next());
				}
			}
 
			public boolean hasNext()
			{
				return curr != null;
			}
 
			public K next()
			{
				if (modCount != BSTrie.this.modCount)
					throw new ConcurrentModificationException();
 
				if (curr == null)
					throw new NoSuchElementException();
 
				if (!it.hasNext() && !(currNode.getRight() instanceof EndNode))
				{
					currNode = (LeafNode) currNode.getRight();
					it = currNode.keyIterator();
					return next();
				}
 
				prev = curr;
				if (it.hasNext() && curr != null && BSTrie.this.lastKey() != null
						&& cmp(curr.getKey(), BSTrie.this.lastKey()) < 0)
					curr = new Entry(it.next());
				else
					curr = null;
 
				return prev.getKey();
			}
 
			public void remove()
			{
				BSTrie.this.remove(prev.getKey());
			}
 
			private int cmp(Object o1, Object o2)
			{
				return BSTrie.this.comparator().compare(o1, o2);
			}
		}
 
	}
 
	private class ValueCollection implements Collection<V>{
 
		@Override
		public boolean add(V e) {
			throw new UnsupportedOperationException();
		}
 
		@Override
		public boolean addAll(Collection<? extends V> c) {
			throw new UnsupportedOperationException();
		}
 
		@Override
		public void clear() {
			BSTrie.this.clear();
		}
 
		@Override
		public boolean contains(Object o) {
			V v = (V) o;
			return BSTrie.this.containsValue(v);
		}
 
		@Override
		public boolean containsAll(Collection<?> c) {
			Iterator it = c.iterator();
			boolean flag = true;
			while(it.hasNext()){
				flag = flag && contains(it.next());
			}
			return flag;
		}
 
		@Override
		public boolean isEmpty() {
			return BSTrie.this.isEmpty();
		}
 
		@Override
		public Iterator<V> iterator() {
			return new ValueIterator();
		}
 
		@Override
		public boolean remove(Object o) {
			K key = null;
			if(((V)o) != null && BSTrie.this.containsValue((V)o)){
				 Iterator it = BSTrie.this.entrySet().iterator();
				 while(it.hasNext()){
					 Entry entry = (Entry) it.next();
					 if(entry.getValue() == o){
						 key = entry.getKey();
						 break;
					 }
				 }
				 return BSTrie.this.remove(key) != null;
			}
			return false;
 
		}
 
		@Override
		public boolean removeAll(Collection<?> c) {
			Iterator it = c.iterator();
			boolean flag = false;
			while(it.hasNext()){
				flag = flag || remove(it.next());
			}
			return flag;
		}
 
 
		@Override
		public boolean retainAll(Collection<?> c) {
			Iterator it = new ValueIterator();
			boolean flag = false;
			while(it.hasNext()){
				if(!c.contains(it.next())){
					it.remove();
					flag = true;
				}
			}
			return flag;
		}
 
 
		@Override
		public int size() {
			return BSTrie.this.size();
		}
 
		@Override
		public Object[] toArray() {
			Object[] arr = new Object[size()];
			Iterator it = new ValueIterator();
			for(int i = 0; it.hasNext(); i++){
				arr[i] = it.next();
			}
			return arr;
		}
 
 
		@Override
		public <V> V[] toArray(V[] a) {
			if(a.length < size()){
				a = (V[]) Array.newInstance(a.getClass().getComponentType(), size());
			}
			Iterator it = new ValueIterator();
			for(int i = 0; it.hasNext(); i++){
				a[i] = (V) it.next();
 			}
			return a;
		}
 
 
 
		private class ValueIterator implements Iterator<V>{
			private Entry curr, prev;
			private LeafNode<K, V> currNode;
			private Iterator<K> it;
			private int modCount = BSTrie.this.modCount;
 
			public ValueIterator(){
				if (BSTrie.this.isEmpty()){
					return;
				}
 
				this.currNode = root.getFirstLeaf();
				this.it = currNode.keyIterator();
 
 
				while (curr == null || BSTrie.this.comparator().compare(curr.getKey(), 
						BSTrie.this.firstKey()) < 0){
					if (!it.hasNext()){
						if (currNode.getRight() instanceof EndNode)
							return;
 
						currNode = (LeafNode) currNode.getRight();
						it = currNode.keyIterator();
						continue;
					}
 
					curr = new Entry(it.next());
				}
			}
 
			public boolean hasNext()
			{
				return curr != null;
			}
 
			public V next()
			{
				if (modCount != BSTrie.this.modCount)
					throw new ConcurrentModificationException();
 
				if (curr == null)
					throw new NoSuchElementException();
 
				if (!it.hasNext() && !(currNode.getRight() instanceof EndNode))
				{
					currNode = (LeafNode) currNode.getRight();
					it = currNode.keyIterator();
					return next();
				}
 
				prev = curr;
				if (it.hasNext() && curr != null && BSTrie.this.lastKey() != null
						&& cmp(curr.getKey(), BSTrie.this.lastKey()) < 0)
					curr = new Entry(it.next());
				else
					curr = null;
 
				return prev.getValue();
			}
 
			public void remove()
			{
				BSTrie.this.remove(prev.getKey());
			}
 
			private int cmp(Object o1, Object o2)
			{
				return BSTrie.this.comparator().compare(o1, o2);
			}
		}
 
	}
 
 
 
 
	/**
	 * Attaches this tree as xml to the output node in the document results
	 * 
	 * @param outputNode
	 * @param results
	 */
	public void printXML(Element outputNode, Document results) {
		Element bsTrie = results.createElement("bsTrie");
		bsTrie.setAttribute("cardinality", Integer.toString(size()));
		// TODO: Fix height attribute if we decide we care.
		//		bsTrie.setAttribute("height", Integer.toString(-1));
		//		bsTrie.setAttribute("bpOrder", Integer.toString(order));
		bsTrie.setAttribute("leafOrder", Integer.toString(cardinality));
		root.printXML(bsTrie, results);
		outputNode.appendChild(bsTrie);
	}
}