1/* GENERATED SOURCE. DO NOT MODIFY. */
2/*
3 * ********************************************************************************
4 * Copyright (C) 2007-2011, International Business Machines Corporation and others.
5 * All Rights Reserved.
6 * ********************************************************************************
7 */
8package android.icu.impl;
9
10import java.util.Iterator;
11import java.util.LinkedList;
12import java.util.List;
13import java.util.ListIterator;
14
15import android.icu.lang.UCharacter;
16
17/**
18 * TextTrieMap is a trie implementation for supporting
19 * fast prefix match for the key.
20 * @hide Only a subset of ICU is exposed in Android
21 */
22public class TextTrieMap<V> {
23
24    private Node _root = new Node();
25    boolean _ignoreCase;
26
27    /**
28     * Constructs a TextTrieMap object.
29     *
30     * @param ignoreCase true to use simple case insensitive match
31     */
32    public TextTrieMap(boolean ignoreCase) {
33        _ignoreCase = ignoreCase;
34    }
35
36    /**
37     * Adds the text key and its associated object in this object.
38     *
39     * @param text The text.
40     * @param val The value object associated with the text.
41     */
42    public TextTrieMap<V> put(CharSequence text, V val) {
43        CharIterator chitr = new CharIterator(text, 0, _ignoreCase);
44        _root.add(chitr, val);
45        return this;
46    }
47
48    /**
49     * Gets an iterator of the objects associated with the
50     * longest prefix matching string key.
51     *
52     * @param text The text to be matched with prefixes.
53     * @return An iterator of the objects associated with
54     * the longest prefix matching matching key, or null
55     * if no matching entry is found.
56     */
57    public Iterator<V> get(String text) {
58        return get(text, 0);
59    }
60
61    /**
62     * Gets an iterator of the objects associated with the
63     * longest prefix matching string key starting at the
64     * specified position.
65     *
66     * @param text The text to be matched with prefixes.
67     * @param start The start index of of the text
68     * @return An iterator of the objects associated with the
69     * longest prefix matching matching key, or null if no
70     * matching entry is found.
71     */
72    public Iterator<V> get(CharSequence text, int start) {
73        return get(text, start, null);
74    }
75
76    public Iterator<V> get(CharSequence text, int start, int[] matchLen) {
77        LongestMatchHandler<V> handler = new LongestMatchHandler<V>();
78        find(text, start, handler);
79        if (matchLen != null && matchLen.length > 0) {
80            matchLen[0] = handler.getMatchLength();
81        }
82        return handler.getMatches();
83    }
84
85    public void find(CharSequence text, ResultHandler<V> handler) {
86        find(text, 0, handler);
87    }
88
89    public void find(CharSequence text, int offset, ResultHandler<V> handler) {
90        CharIterator chitr = new CharIterator(text, offset, _ignoreCase);
91        find(_root, chitr, handler);
92    }
93
94    private synchronized void find(Node node, CharIterator chitr, ResultHandler<V> handler) {
95        Iterator<V> values = node.values();
96        if (values != null) {
97            if (!handler.handlePrefixMatch(chitr.processedLength(), values)) {
98                return;
99            }
100        }
101
102        Node nextMatch = node.findMatch(chitr);
103        if (nextMatch != null) {
104            find(nextMatch, chitr, handler);
105        }
106    }
107
108    public static class CharIterator implements Iterator<Character> {
109        private boolean _ignoreCase;
110        private CharSequence _text;
111        private int _nextIdx;
112        private int _startIdx;
113
114        private Character _remainingChar;
115
116        CharIterator(CharSequence text, int offset, boolean ignoreCase) {
117            _text = text;
118            _nextIdx = _startIdx = offset;
119            _ignoreCase = ignoreCase;
120        }
121
122        /* (non-Javadoc)
123         * @see java.util.Iterator#hasNext()
124         */
125        public boolean hasNext() {
126            if (_nextIdx == _text.length() && _remainingChar == null) {
127                return false;
128            }
129            return true;
130        }
131
132        /* (non-Javadoc)
133         * @see java.util.Iterator#next()
134         */
135        public Character next() {
136            if (_nextIdx == _text.length() && _remainingChar == null) {
137                return null;
138            }
139            Character next;
140            if (_remainingChar != null) {
141                next = _remainingChar;
142                _remainingChar = null;
143            } else {
144                if (_ignoreCase) {
145                    int cp = UCharacter.foldCase(Character.codePointAt(_text, _nextIdx), true);
146                    _nextIdx = _nextIdx + Character.charCount(cp);
147
148                    char[] chars = Character.toChars(cp);
149                    next = chars[0];
150                    if (chars.length == 2) {
151                        _remainingChar = chars[1];
152                    }
153                } else {
154                    next = _text.charAt(_nextIdx);
155                    _nextIdx++;
156                }
157            }
158            return next;
159        }
160
161        /* (non-Javadoc)
162         * @see java.util.Iterator#remove()
163         */
164        public void remove() {
165            throw new UnsupportedOperationException("remove() not supproted");
166        }
167
168        public int nextIndex() {
169            return _nextIdx;
170        }
171
172        public int processedLength() {
173            if (_remainingChar != null) {
174                throw new IllegalStateException("In the middle of surrogate pair");
175            }
176            return _nextIdx - _startIdx;
177        }
178    }
179
180    /**
181     * Callback handler for processing prefix matches used by
182     * find method.
183     */
184    public interface ResultHandler<V> {
185        /**
186         * Handles a prefix key match
187         *
188         * @param matchLength Matched key's length
189         * @param values An iterator of the objects associated with the matched key
190         * @return Return true to continue the search in the trie, false to quit.
191         */
192        public boolean handlePrefixMatch(int matchLength, Iterator<V> values);
193    }
194
195    private static class LongestMatchHandler<V> implements ResultHandler<V> {
196        private Iterator<V> matches = null;
197        private int length = 0;
198
199        public boolean handlePrefixMatch(int matchLength, Iterator<V> values) {
200            if (matchLength > length) {
201                length = matchLength;
202                matches = values;
203            }
204            return true;
205        }
206
207        public Iterator<V> getMatches() {
208            return matches;
209        }
210
211        public int getMatchLength() {
212            return length;
213        }
214    }
215
216    /**
217     * Inner class representing a text node in the trie.
218     */
219    private class Node {
220        private char[] _text;
221        private List<V> _values;
222        private List<Node> _children;
223
224        private Node() {
225        }
226
227        private Node(char[] text, List<V> values, List<Node> children) {
228            _text = text;
229            _values = values;
230            _children = children;
231        }
232
233        public Iterator<V> values() {
234            if (_values == null) {
235                return null;
236            }
237            return _values.iterator();
238        }
239
240        public void add(CharIterator chitr, V value) {
241            StringBuilder buf = new StringBuilder();
242            while (chitr.hasNext()) {
243                buf.append(chitr.next());
244            }
245            add(toCharArray(buf), 0, value);
246        }
247
248        public Node findMatch(CharIterator chitr) {
249            if (_children == null) {
250                return null;
251            }
252            if (!chitr.hasNext()) {
253                return null;
254            }
255            Node match = null;
256            Character ch = chitr.next();
257            for (Node child : _children) {
258                if (ch < child._text[0]) {
259                    break;
260                }
261                if (ch == child._text[0]) {
262                    if (child.matchFollowing(chitr)) {
263                        match = child;
264                    }
265                    break;
266                }
267            }
268            return match;
269        }
270
271        private void add(char[] text, int offset, V value) {
272            if (text.length == offset) {
273                _values = addValue(_values, value);
274                return;
275            }
276
277            if (_children == null) {
278                _children = new LinkedList<Node>();
279                Node child = new Node(subArray(text, offset), addValue(null, value), null);
280                _children.add(child);
281                return;
282            }
283
284            // walk through children
285            ListIterator<Node> litr = _children.listIterator();
286            while (litr.hasNext()) {
287                Node next = litr.next();
288                if (text[offset] < next._text[0]) {
289                    litr.previous();
290                    break;
291                }
292                if (text[offset] == next._text[0]) {
293                    int matchLen = next.lenMatches(text, offset);
294                    if (matchLen == next._text.length) {
295                        // full match
296                        next.add(text, offset + matchLen, value);
297                    } else {
298                        // partial match, create a branch
299                        next.split(matchLen);
300                        next.add(text, offset + matchLen, value);
301                    }
302                    return;
303                }
304            }
305            // add a new child to this node
306            litr.add(new Node(subArray(text, offset), addValue(null, value), null));
307        }
308
309        private boolean matchFollowing(CharIterator chitr) {
310            boolean matched = true;
311            int idx = 1;
312            while (idx < _text.length) {
313                if(!chitr.hasNext()) {
314                    matched = false;
315                    break;
316                }
317                Character ch = chitr.next();
318                if (ch != _text[idx]) {
319                    matched = false;
320                    break;
321                }
322                idx++;
323            }
324            return matched;
325        }
326
327        private int lenMatches(char[] text, int offset) {
328            int textLen = text.length - offset;
329            int limit = _text.length < textLen ? _text.length : textLen;
330            int len = 0;
331            while (len < limit) {
332                if (_text[len] != text[offset + len]) {
333                    break;
334                }
335                len++;
336            }
337            return len;
338        }
339
340        private void split(int offset) {
341            // split the current node at the offset
342            char[] childText = subArray(_text, offset);
343            _text = subArray(_text, 0, offset);
344
345            // add the Node representing after the offset as a child
346            Node child = new Node(childText, _values, _children);
347            _values = null;
348
349            _children = new LinkedList<Node>();
350            _children.add(child);
351        }
352
353        private List<V> addValue(List<V> list, V value) {
354            if (list == null) {
355                list = new LinkedList<V>();
356            }
357            list.add(value);
358            return list;
359        }
360    }
361
362    private static char[] toCharArray(CharSequence text) {
363        char[] array = new char[text.length()];
364        for (int i = 0; i < array.length; i++) {
365            array[i] = text.charAt(i);
366        }
367        return array;
368    }
369
370    private static char[] subArray(char[] array, int start) {
371        if (start == 0) {
372            return array;
373        }
374        char[] sub = new char[array.length - start];
375        System.arraycopy(array, start, sub, 0, sub.length);
376        return sub;
377    }
378
379    private static char[] subArray(char[] array, int start, int limit) {
380        if (start == 0 && limit == array.length) {
381            return array;
382        }
383        char[] sub = new char[limit - start];
384        System.arraycopy(array, start, sub, 0, limit - start);
385        return sub;
386    }
387}
388