source: trunk/gsdl3/packages/gsdl-as/src/org/greenstone/gsdlas/util/PatriciaTree.java@ 8609

/*
 * 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();
        }
    }
}