001: /*
002: * *****************************************************************************
003: * Copyright (C) 2006, International Business Machines Corporation and others.
004: * All Rights Reserved.
005: * *****************************************************************************
006: */
007: package com.ibm.icu.impl;
008:
009: import java.util.ArrayList;
010: import java.util.List;
011:
012: import com.ibm.icu.lang.UCharacter;
013: import com.ibm.icu.text.UTF16;
014:
015: /**
016: * TextTrieMap is a trie implementation for supporting
017: * fast prefix match for the key.
018: */
019: public class TextTrieMap {
020: /**
021: * Costructs a TextTrieMap object.
022: *
023: * @param ignoreCase true to use case insensitive match
024: */
025: public TextTrieMap(boolean ignoreCase) {
026: this .ignoreCase = ignoreCase;
027: }
028:
029: /**
030: * Adds the text key and its associated object in this object.
031: *
032: * @param text The text.
033: * @param o The object associated with the text.
034: * @return The previous value associated with specified text,
035: * or null if there was no mapping for the text.
036: */
037: public synchronized Object put(String text, Object o) {
038: CharacterNode node = root;
039: for (int i = 0; i < text.length(); i++) {
040: int ch = UTF16.charAt(text, i);
041: node = node.addChildNode(ch);
042: if (UTF16.getCharCount(ch) == 2) {
043: i++;
044: }
045: }
046: Object prevObj = node.getObject();
047: node.setObject(o);
048: return prevObj;
049: }
050:
051: /**
052: * Gets the object associated with the longest prefix
053: * matching string key.
054: *
055: * @param text The text to be matched with prefixes.
056: * @return The object associated with the longet prefix matching
057: * matching key, or null if no matching entry is found.
058: */
059: public Object get(String text) {
060: return get(root, text, 0);
061: }
062:
063: /**
064: * Gets the object associated with the longest prefix
065: * matching string key starting at the specified position.
066: *
067: * @param text The text to be matched with prefixes.
068: * @param start The start index of of the text
069: * @return The object associated with the longet prefix matching
070: * matching key, or null if no matching entry is found.
071: */
072: public Object get(String text, int start) {
073: return get(root, text, start);
074: }
075:
076: /**
077: * Gets the object associated with the longet prefix
078: * matching string key under the specified node.
079: *
080: * @param node The character node in this trie.
081: * @param text The text to be matched with prefixes.
082: * @param index The current index within the text.
083: * @return The object associated with the longest prefix
084: * match under the node.
085: */
086: private synchronized Object get(CharacterNode node, String text,
087: int index) {
088: Object obj = node.getObject();
089: if (index < text.length()) {
090: List childNodes = node.getChildNodes();
091: if (childNodes == null) {
092: return obj;
093: }
094: int ch = UTF16.charAt(text, index);
095: int chLen = UTF16.getCharCount(ch);
096: for (int i = 0; i < childNodes.size(); i++) {
097: CharacterNode child = (CharacterNode) childNodes.get(i);
098: if (compare(ch, child.getCharacter())) {
099: Object tmp = get(child, text, index + chLen);
100: if (tmp != null) {
101: obj = tmp;
102: }
103: break;
104: }
105: }
106: }
107: return obj;
108: }
109:
110: /**
111: * A private method used for comparing two characters.
112: *
113: * @param ch1 The first character.
114: * @param ch2 The second character.
115: * @return true if the first character matches the second.
116: */
117: private boolean compare(int ch1, int ch2) {
118: if (ch1 == ch2) {
119: return true;
120: } else if (ignoreCase) {
121: if (UCharacter.toLowerCase(ch1) == UCharacter
122: .toLowerCase(ch2)) {
123: return true;
124: } else if (UCharacter.toUpperCase(ch1) == UCharacter
125: .toUpperCase(ch2)) {
126: return true;
127: }
128: }
129: return false;
130: }
131:
132: // The root node of this trie
133: private CharacterNode root = new CharacterNode(0);
134:
135: // Character matching option
136: boolean ignoreCase;
137:
138: /**
139: * Inner class representing a character node in the trie.
140: */
141: private class CharacterNode {
142: int character;
143: List children;
144: Object obj;
145:
146: /**
147: * Constructs a node for the character.
148: *
149: * @param ch The character associated with this node.
150: */
151: public CharacterNode(int ch) {
152: character = ch;
153: }
154:
155: /**
156: * Gets the character associated with this node.
157: *
158: * @return The character
159: */
160: public int getCharacter() {
161: return character;
162: }
163:
164: /**
165: * Sets the object to the node. Only a leaf node has
166: * the reference of an object associated with a key.
167: *
168: * @param obj The object set in the leaf node.
169: */
170: public void setObject(Object obj) {
171: this .obj = obj;
172: }
173:
174: /**
175: * Gets the object associated the leaf node.
176: *
177: * @return The object.
178: */
179: public Object getObject() {
180: return obj;
181: }
182:
183: /**
184: * Adds a child node for the characer under this character
185: * node in the trie. When the matching child node already
186: * exists, the reference of the existing child node is
187: * returned.
188: *
189: * @param ch The character associated with a child node.
190: * @return The child node.
191: */
192: public CharacterNode addChildNode(int ch) {
193: if (children == null) {
194: children = new ArrayList();
195: CharacterNode newNode = new CharacterNode(ch);
196: children.add(newNode);
197: return newNode;
198: }
199: CharacterNode node = null;
200: for (int i = 0; i < children.size(); i++) {
201: CharacterNode cur = (CharacterNode) children.get(i);
202: if (compare(ch, cur.getCharacter())) {
203: node = cur;
204: break;
205: }
206: }
207: if (node == null) {
208: node = new CharacterNode(ch);
209: children.add(node);
210: }
211: return node;
212: }
213:
214: /**
215: * Gets the list of child nodes under this node.
216: *
217: * @return The list of child nodes.
218: */
219: public List getChildNodes() {
220: return children;
221: }
222: }
223: }
|