main/classes/core/src/com/ibm/icu/impl/TextTrieMap.java

/*
 * ********************************************************************************
 * Copyright (C) 2007-2009, International Business Machines Corporation and others.
 * All Rights Reserved.
 * ********************************************************************************
 */
package com.ibm.icu.impl;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import com.ibm.icu.lang.UCharacter;
import com.ibm.icu.text.UTF16;

/**
 * TextTrieMap is a trie implementation for supporting
 * fast prefix match for the key.
 */
public class TextTrieMap<V> {
    /**
     * Constructs a TextTrieMap object.
     * 
     * @param ignoreCase true to use case insensitive match
     */
    public TextTrieMap(boolean ignoreCase) {
        this.ignoreCase = ignoreCase;
    }

    /**
     * Adds the text key and its associated object in this object.
     * 
     * @param text The text.
     * @param o The object associated with the text.
     */
    public synchronized void put(String text, V o) {
        CharacterNode node = root;
        for (int i = 0; i < text.length(); i++) {
            int ch = UTF16.charAt(text, i);
            node = node.addChildNode(ch);
            if (UTF16.getCharCount(ch) == 2) {
                i++;
            }
        }
        node.addObject(o);
    }

    /**
     * Gets an iterator of the objects associated with the
     * longest prefix matching string key.
     * 
     * @param text The text to be matched with prefixes.
     * @return An iterator of the objects associated with
     * the longest prefix matching matching key, or null
     * if no matching entry is found.
     */
    public Iterator<V> get(String text) {
        return get(text, 0);
    }

    /**
     * Gets an iterator of the objects associated with the
     * longest prefix matching string key starting at the 
     * specified position.
     * 
     * @param text The text to be matched with prefixes.
     * @param start The start index of of the text
     * @return An iterator of the objects associated with the
     * longest prefix matching matching key, or null if no 
     * matching entry is found.
     */
    public Iterator<V> get(String text, int start) {
        LongestMatchHandler<V> handler = new LongestMatchHandler<V>();
        find(text, start, handler);
        return handler.getMatches();
    }

    public void find(String text, ResultHandler<V> handler) {
        find(text, 0, handler);
    }
    
    public void find(String text, int start, ResultHandler<V> handler) {
        find(root, text, start, start, handler);
    }

    /*
     * Find an iterator of the objects associated with the
     * longest prefix matching string key under the specified node.
     * 
     * @param node The character node in this trie.
     * @param text The text to be matched with prefixes.
     * @param start The start index within the text.
     * @param index The current index within the text.
     * @param handler The result handler, ResultHandler#handlePrefixMatch
     * is called when any prefix match is found.
     */
    private synchronized void find(CharacterNode node, String text,
            int start, int index, ResultHandler<V> handler) {
        Iterator<V> itr = node.iterator();
        if (itr != null) {
            if (!handler.handlePrefixMatch(index - start, itr)) {
                return;
            }
        }
        if (index < text.length()) {
            List<CharacterNode> childNodes = node.getChildNodes();
            if (childNodes == null) {
                return;
            }
            int ch = UTF16.charAt(text, index);
            int chLen = UTF16.getCharCount(ch);
            for (int i = 0; i < childNodes.size(); i++) {
                CharacterNode child = childNodes.get(i);
                if (compare(ch, child.getCharacter())) {
                    find(child, text, start, index + chLen, handler);
                    break;
                }
            }
        }
    }
    
    /**
     * A private method used for comparing two characters.
     * 
     * @param ch1 The first character.
     * @param ch2 The second character.
     * @return true if the first character matches the second.
     */
    private boolean compare(int ch1, int ch2) {
        if (ch1 == ch2) {
            return true;
        }
        else if (ignoreCase) {
            if (UCharacter.toLowerCase(ch1) == UCharacter.toLowerCase(ch2)) {
                return true;
            }
            else if (UCharacter.toUpperCase(ch1) == UCharacter.toUpperCase(ch2)) {
                return true;
            }
        }
        return false;
    }

    // The root node of this trie
    private CharacterNode root = new CharacterNode(0);

    // Character matching option
    boolean ignoreCase;

    /**
     * Inner class representing a character node in the trie.
     */
    private class CharacterNode {
        int character;
        List<CharacterNode> children;
        List<V> objlist;

        /**
         * Constructs a node for the character.
         * 
         * @param ch The character associated with this node.
         */
        public CharacterNode(int ch) {
            character = ch;
        }

        /**
         * Gets the character associated with this node.
         * 
         * @return The character
         */
        public int getCharacter() {
            return character;
        }

        /**
         * Adds the object to the node.
         *  
         * @param obj The object set in the leaf node.
         */
        public void addObject(V obj) {
            if (objlist == null) {
                objlist = new LinkedList<V>();
            }
            objlist.add(obj);
        }

        /**
         * Gets an iterator of the objects associated with
         * the leaf node.
         * 
         * @return The iterator or null if no objects are
         * associated with this node.
         */
        public Iterator<V> iterator() {
            if (objlist == null) {
                return null;
            }
            return objlist.iterator();
        }

        /**
         * Adds a child node for the character under this character
         * node in the trie.  When the matching child node already
         * exists, the reference of the existing child node is
         * returned.
         * 
         * @param ch The character associated with a child node.
         * @return The child node.
         */
        public CharacterNode addChildNode(int ch) {
            if (children == null) {
                children = new ArrayList<CharacterNode>();
                CharacterNode newNode = new CharacterNode(ch);
                children.add(newNode);
                return newNode;
            }
            CharacterNode node = null;
            for (int i = 0; i < children.size(); i++) {
                CharacterNode cur = children.get(i);
                if (compare(ch, cur.getCharacter())) {
                    node = cur;
                    break;
                }               
            }
            if (node == null) {
                node = new CharacterNode(ch);
                children.add(node);
            }
            return node;
        }

        /**
         * Gets the list of child nodes under this node.
         * 
         * @return The list of child nodes.
         */
        public List<CharacterNode> getChildNodes() {
            return children;
        }
    }

    /**
     * Callback handler for processing prefix matches used by
     * find method.
     */
    public interface ResultHandler<V> {
        /**
         * Handles a prefix key match
         * 
         * @param matchLength Matched key's length
         * @param values An iterator of the objects associated with the matched key
         * @return Return true to continue the search in the trie, false to quit.
         */
        public boolean handlePrefixMatch(int matchLength, Iterator<V> values);
    }

    private static class LongestMatchHandler<V> implements ResultHandler<V> {
        private Iterator<V> matches = null;
        private int length = 0;

        public boolean handlePrefixMatch(int matchLength, Iterator<V> values) {
            if (matchLength > length) {
                length = matchLength;
                matches = values;
            }
            return true;
        }

        public Iterator<V> getMatches() {
            return matches;
        }
    }
}