1 | /*
|
---|
2 | * Created on Nov 11, 2004
|
---|
3 | * Copyright (C) Andrea Schweer, 2004
|
---|
4 | *
|
---|
5 | * This file is part of the Greenstone Alerting Service.
|
---|
6 | * Refer to the COPYING file in the base directory of this package
|
---|
7 | * for licensing information.
|
---|
8 | *
|
---|
9 | */
|
---|
10 | package org.greenstone.gsdlas.util;
|
---|
11 |
|
---|
12 | import java.util.*;
|
---|
13 |
|
---|
14 | /**
|
---|
15 | * @author andrea
|
---|
16 | *
|
---|
17 | * TODO To change the template for this generated type comment go to
|
---|
18 | * Window - Preferences - Java - Code Style - Code Templates
|
---|
19 | */
|
---|
20 | public class PatriciaTree {
|
---|
21 |
|
---|
22 | private Node root;
|
---|
23 |
|
---|
24 | public PatriciaTree () {
|
---|
25 | }
|
---|
26 |
|
---|
27 | public void put(CharSequence key, Object value) {
|
---|
28 | root = put(key, value, root, 0);
|
---|
29 | }
|
---|
30 |
|
---|
31 | public Set get(CharSequence key) {
|
---|
32 | return get(key, root, 0);
|
---|
33 | }
|
---|
34 |
|
---|
35 | public String toString() {
|
---|
36 | return toPreorderString(root).toString();
|
---|
37 | }
|
---|
38 |
|
---|
39 | private StringBuffer toPreorderString(Node root) {
|
---|
40 | StringBuffer buffer = new StringBuffer("(\n");
|
---|
41 | buffer.append(root);
|
---|
42 | buffer.append("\nchildren:");
|
---|
43 | if (root.hasChildren()) {
|
---|
44 | for (Iterator iter = root.children.keySet().iterator(); iter.hasNext();) {
|
---|
45 | Character key = (Character) iter.next();
|
---|
46 | Node child = root.getChild(key);
|
---|
47 | buffer.append("\n");
|
---|
48 | buffer.append(key);
|
---|
49 | buffer.append("->");
|
---|
50 | buffer.append(toPreorderString(child));
|
---|
51 | }
|
---|
52 | }
|
---|
53 |
|
---|
54 | buffer.append("\n)");
|
---|
55 | return buffer;
|
---|
56 | }
|
---|
57 |
|
---|
58 | /**
|
---|
59 | * @param key
|
---|
60 | * @param root
|
---|
61 | * @param position
|
---|
62 | * @return the set of values associated with <code>key</code>
|
---|
63 | */
|
---|
64 | private Set get(CharSequence key, Node root, int position) {
|
---|
65 | Set result = new HashSet();
|
---|
66 |
|
---|
67 | int i = findFirstMismatch(key, root, position);
|
---|
68 |
|
---|
69 | if (i == root.skipped.length()) {
|
---|
70 | Character nextChar = new Character(key.charAt(position + i));
|
---|
71 | if (key.length() > position + i + 1) { // nextChar is not last character
|
---|
72 | if (root.hasChild(nextChar)) {
|
---|
73 | result.addAll(get(key, root.getChild(nextChar), position + i + 1));
|
---|
74 | }
|
---|
75 | } else {
|
---|
76 | result.addAll(root.getValues(nextChar));
|
---|
77 | }
|
---|
78 | }
|
---|
79 |
|
---|
80 | return result;
|
---|
81 | }
|
---|
82 |
|
---|
83 | /**
|
---|
84 | * @param key
|
---|
85 | * @param value
|
---|
86 | * @param root
|
---|
87 | * @param position
|
---|
88 | * @return the new root node
|
---|
89 | */
|
---|
90 | private Node put(CharSequence key, Object value, Node root, int position) {
|
---|
91 | if (root == null) {
|
---|
92 | root = new Node();
|
---|
93 | root.skipped = key.subSequence(position, key.length() - 1);
|
---|
94 | root.addValue(new Character(key.charAt(key.length() - 1)), value);
|
---|
95 | return root;
|
---|
96 | }
|
---|
97 |
|
---|
98 | if (root.skipped == null || root.skipped.length() == 0) {
|
---|
99 | addAsValueOrChild(key, value, root, position);
|
---|
100 | return root;
|
---|
101 | }
|
---|
102 |
|
---|
103 | int i = findFirstMismatch(key, root, position);
|
---|
104 | if (i >= root.skipped.length() && position + i < key.length()) {
|
---|
105 | addAsValueOrChild(key, value, root, position + i);
|
---|
106 | return root;
|
---|
107 | }
|
---|
108 |
|
---|
109 | if (i >= root.skipped.length() && isLastCharacter(key, position + i - 1)) {
|
---|
110 | Node newRoot = new Node();
|
---|
111 | newRoot.skipped = root.skipped.subSequence(0, i - 1);
|
---|
112 | newRoot.addChild(new Character(root.skipped.charAt(i - 1)), root);
|
---|
113 | try {
|
---|
114 | root.skipped = root.skipped.subSequence(i, root.skipped.length());
|
---|
115 | } catch (StringIndexOutOfBoundsException e) {
|
---|
116 | root.skipped = "";
|
---|
117 | }
|
---|
118 | addAsValueOrChild(key, value, newRoot, position + i - 1);
|
---|
119 | return newRoot;
|
---|
120 | }
|
---|
121 |
|
---|
122 | Node newRoot = new Node();
|
---|
123 | newRoot.skipped = root.skipped.subSequence(0, i);
|
---|
124 | newRoot.addChild(new Character(root.skipped.charAt(i)), root);
|
---|
125 | try {
|
---|
126 | root.skipped = root.skipped.subSequence(i + 1, root.skipped.length());
|
---|
127 | } catch (StringIndexOutOfBoundsException e) {
|
---|
128 | root.skipped = "";
|
---|
129 | }
|
---|
130 |
|
---|
131 | addAsValueOrChild(key, value, newRoot, position + i);
|
---|
132 |
|
---|
133 | return newRoot;
|
---|
134 | }
|
---|
135 |
|
---|
136 | /**
|
---|
137 | * @param key
|
---|
138 | * @param value
|
---|
139 | * @param root
|
---|
140 | * @param position
|
---|
141 | */
|
---|
142 | private void addAsValueOrChild(CharSequence key, Object value, Node root, int position) {
|
---|
143 | Character nextChar = new Character(key.charAt(position));
|
---|
144 | if (isLastCharacter(key, position)) {
|
---|
145 | root.addValue(nextChar, value);
|
---|
146 | } else {
|
---|
147 | Node newChild = put(key, value, root.getChild(nextChar), position + 1);
|
---|
148 | root.addChild(nextChar, newChild);
|
---|
149 | }
|
---|
150 | }
|
---|
151 |
|
---|
152 | /**
|
---|
153 | * @param key
|
---|
154 | * @param position
|
---|
155 | * @return
|
---|
156 | */
|
---|
157 | private boolean isLastCharacter(CharSequence key, int position) {
|
---|
158 | return key.length() - position == 1;
|
---|
159 | }
|
---|
160 |
|
---|
161 | /**
|
---|
162 | * @param key
|
---|
163 | * @param root
|
---|
164 | * @param position
|
---|
165 | * @return
|
---|
166 | */
|
---|
167 | private int findFirstMismatch(CharSequence key, Node root, int position) {
|
---|
168 | int i = 0;
|
---|
169 | while (i < root.skipped.length()) {
|
---|
170 | try {
|
---|
171 | if (root.skipped.charAt(i) == key.charAt(position + i)) {
|
---|
172 | i++;
|
---|
173 | } else {
|
---|
174 | return i;
|
---|
175 | }
|
---|
176 | } catch (StringIndexOutOfBoundsException e) {
|
---|
177 | return i;
|
---|
178 | }
|
---|
179 | }
|
---|
180 | return i;
|
---|
181 | }
|
---|
182 |
|
---|
183 |
|
---|
184 | private class Node {
|
---|
185 | private CharSequence skipped = "";
|
---|
186 | private Map children;
|
---|
187 | private Map values;
|
---|
188 |
|
---|
189 | /**
|
---|
190 | * @return
|
---|
191 | */
|
---|
192 | public Set getValues(Character key) {
|
---|
193 | if (values == null || !values.containsKey(key))
|
---|
194 | return new HashSet();
|
---|
195 | return (Set) values.get(key);
|
---|
196 | }
|
---|
197 |
|
---|
198 | boolean hasChild(Character key) {
|
---|
199 | return children != null && children.containsKey(key);
|
---|
200 | }
|
---|
201 |
|
---|
202 | boolean hasChildren() {
|
---|
203 | return children != null && !children.isEmpty();
|
---|
204 | }
|
---|
205 |
|
---|
206 | void addChild(Character key, Node child) {
|
---|
207 | if (children == null ) {
|
---|
208 | children = new TreeMap();
|
---|
209 | }
|
---|
210 | children.put(key, child);
|
---|
211 | }
|
---|
212 |
|
---|
213 | Node getChild(Character key) {
|
---|
214 | if (children == null) return null;
|
---|
215 | return (Node) children.get(key);
|
---|
216 | }
|
---|
217 |
|
---|
218 | void addValue(Character key, Object value) {
|
---|
219 | if (values == null) {
|
---|
220 | values = new TreeMap();
|
---|
221 | }
|
---|
222 | Set valueSet;
|
---|
223 | if (values.containsKey(key)) {
|
---|
224 | valueSet = (Set) values.get(key);
|
---|
225 | } else {
|
---|
226 | valueSet = new HashSet();
|
---|
227 | values.put(key, valueSet);
|
---|
228 | }
|
---|
229 | valueSet.add(value);
|
---|
230 | }
|
---|
231 |
|
---|
232 | public String toString() {
|
---|
233 | StringBuffer buffer = new StringBuffer();
|
---|
234 | buffer.append(skipped);
|
---|
235 | buffer.append("\nvalues:");
|
---|
236 | if (values != null) {
|
---|
237 | buffer.append(values);
|
---|
238 | }
|
---|
239 | return buffer.toString();
|
---|
240 | }
|
---|
241 | }
|
---|
242 | }
|
---|