/*
 * Created on Nov 11, 2004
 * Copyright (C) Andrea Schweer, 2004
 *
 * This file is part of the Greenstone Alerting Service.
 * Refer to the COPYING file in the base directory of this package
 * for licensing information.
 * 
 */
package org.greenstone.gsdlas.util;

import java.util.*;

/**
 * @author andrea
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class PatriciaTree {
	
	private Node root;
	
	public PatriciaTree () {
	}
	
	public void put(CharSequence key, Object value) {
		root = put(key, value, root, 0);
	}
	
	public Set get(CharSequence key) {
		return get(key, root, 0);
	}
	
	public String toString() {
	    return toPreorderString(root).toString();
	}
	
	private StringBuffer toPreorderString(Node root) {
	    StringBuffer buffer = new StringBuffer("(\n");
	    buffer.append(root);
	    buffer.append("\nchildren:");
	    if (root.hasChildren()) {
	        for (Iterator iter = root.children.keySet().iterator(); iter.hasNext();) {
	            Character key = (Character) iter.next();
	            Node child = root.getChild(key);
	            buffer.append("\n");
	            buffer.append(key);
	            buffer.append("->");
	            buffer.append(toPreorderString(child));
	        }
	    }
	    
	    buffer.append("\n)");
	    return buffer;
	}
	
	/**
	 * @param key
	 * @param root
	 * @param position
	 * @return the set of values associated with <code>key</code>
	 */
	private Set get(CharSequence key, Node root, int position) {
		Set result = new HashSet();
		
		int i = findFirstMismatch(key, root, position);
		
		if (i == root.skipped.length()) {
			Character nextChar = new Character(key.charAt(position + i));
			if (key.length() > position + i + 1) { // nextChar is not last character
				if (root.hasChild(nextChar)) {
					result.addAll(get(key, root.getChild(nextChar), position + i + 1));
				}	
			} else {
				result.addAll(root.getValues(nextChar));
			}
		}
		
		return result;
	}

	/**
	 * @param key
	 * @param value
	 * @param root
	 * @param position
	 * @return the new root node
	 */
	private Node put(CharSequence key, Object value, Node root, int position) {
	    if (root == null) {
	        root = new Node();
	        root.skipped = key.subSequence(position, key.length() - 1);
	        root.addValue(new Character(key.charAt(key.length() - 1)), value);
	        return root;
	    }
	    
	    if (root.skipped == null || root.skipped.length() == 0) {
	        addAsValueOrChild(key, value, root, position);
	        return root;
	    }
	    
	    int i = findFirstMismatch(key, root, position);
	    if (i >= root.skipped.length() && position + i < key.length()) {
	        addAsValueOrChild(key, value, root, position + i);
	        return root;
	    }
	    
	    if (i >= root.skipped.length() && isLastCharacter(key, position + i - 1)) {
	        Node newRoot = new Node();
	        newRoot.skipped = root.skipped.subSequence(0, i - 1);
	        newRoot.addChild(new Character(root.skipped.charAt(i - 1)), root);
	        try {
		        root.skipped = root.skipped.subSequence(i, root.skipped.length());
		    } catch (StringIndexOutOfBoundsException e) {
		        root.skipped = "";
		    }
		    addAsValueOrChild(key, value, newRoot, position + i - 1);
		    return newRoot;
	    }
	    
	    Node newRoot = new Node();
	    newRoot.skipped = root.skipped.subSequence(0, i);
	    newRoot.addChild(new Character(root.skipped.charAt(i)), root);
	    try {
	        root.skipped = root.skipped.subSequence(i + 1, root.skipped.length());
	    } catch (StringIndexOutOfBoundsException e) {
	        root.skipped = "";
	    }
	    
	    addAsValueOrChild(key, value, newRoot, position + i);
	    
	    return newRoot;
	}

    /**
     * @param key
     * @param value
     * @param root
     * @param position
     */
    private void addAsValueOrChild(CharSequence key, Object value, Node root, int position) {
        Character nextChar = new Character(key.charAt(position)); 
        if (isLastCharacter(key, position)) {
            root.addValue(nextChar, value); 
        } else {
            Node newChild = put(key, value, root.getChild(nextChar), position + 1);
            root.addChild(nextChar, newChild);
        }
    }

    /**
     * @param key
     * @param position
     * @return
     */
    private boolean isLastCharacter(CharSequence key, int position) {
        return key.length() - position == 1;
    }

    /**
	 * @param key
	 * @param root
	 * @param position
	 * @return
	 */
	private int findFirstMismatch(CharSequence key, Node root, int position) {
		int i = 0;
		while (i < root.skipped.length()) {
			try {
				if (root.skipped.charAt(i) == key.charAt(position + i)) {
					i++;
				} else {
					return i;
				}
			} catch (StringIndexOutOfBoundsException e) {
				return i;
			}
		}
		return i;
	}


	private class Node {
		private CharSequence skipped = "";
		private Map children;
		private Map values;
		
		/**
		 * @return
		 */
		public Set getValues(Character key) {
			if (values == null || !values.containsKey(key))
				return new HashSet();
			return (Set) values.get(key);
		}

		boolean hasChild(Character key) {
			return children != null && children.containsKey(key);
		}
		
		boolean hasChildren() {
			return children != null && !children.isEmpty();
		}
		
		void addChild(Character key, Node child) {
			if (children == null ) {
				children = new TreeMap();
			}
			children.put(key, child);
		}
		
		Node getChild(Character key) {
			if (children == null) return null;
			return (Node) children.get(key);
		}
		
		void addValue(Character key, Object value) {
			if (values == null) {
				values = new TreeMap();
			}
			Set valueSet;
			if (values.containsKey(key)) {
				valueSet = (Set) values.get(key);
			} else {
				valueSet = new HashSet();
				values.put(key, valueSet);
			}
			valueSet.add(value);
		}
		
		public String toString() {
		    StringBuffer buffer = new StringBuffer();
		    buffer.append(skipped);
		    buffer.append("\nvalues:");
		    if (values != null) {
		        buffer.append(values);
		    }
		    return buffer.toString();
		}
	}
}