001 /**
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.activemq.filter;
018
019 import java.util.ArrayList;
020 import java.util.Collection;
021 import java.util.HashMap;
022 import java.util.HashSet;
023 import java.util.Iterator;
024 import java.util.List;
025 import java.util.Map;
026 import java.util.Set;
027
028 /**
029 * An implementation class used to implement {@link DestinationMap}
030 *
031 *
032 */
033 public class DestinationMapNode implements DestinationNode {
034 protected static final String ANY_CHILD = DestinationMap.ANY_CHILD;
035 protected static final String ANY_DESCENDENT = DestinationMap.ANY_DESCENDENT;
036
037 // we synchornize at the DestinationMap level
038 private DestinationMapNode parent;
039 private List values = new ArrayList();
040 private Map childNodes = new HashMap();
041 private String path = "Root";
042 // private DestinationMapNode anyChild;
043 private int pathLength;
044
045 public DestinationMapNode(DestinationMapNode parent) {
046 this.parent = parent;
047 if (parent == null) {
048 pathLength = 0;
049 } else {
050 pathLength = parent.pathLength + 1;
051 }
052 }
053
054 /**
055 * Returns the child node for the given named path or null if it does not
056 * exist
057 */
058 public DestinationMapNode getChild(String path) {
059 return (DestinationMapNode)childNodes.get(path);
060 }
061
062 /**
063 * Returns the child nodes
064 */
065 public Collection getChildren() {
066 return childNodes.values();
067 }
068
069 public int getChildCount() {
070 return childNodes.size();
071 }
072
073 /**
074 * Returns the child node for the given named path, lazily creating one if
075 * it does not yet exist
076 */
077 public DestinationMapNode getChildOrCreate(String path) {
078 DestinationMapNode answer = (DestinationMapNode)childNodes.get(path);
079 if (answer == null) {
080 answer = createChildNode();
081 answer.path = path;
082 childNodes.put(path, answer);
083 }
084 return answer;
085 }
086
087 /**
088 * Returns the node which represents all children (i.e. the * node)
089 */
090 // public DestinationMapNode getAnyChildNode() {
091 // if (anyChild == null) {
092 // anyChild = createChildNode();
093 // }
094 // return anyChild;
095 // }
096 /**
097 * Returns a mutable List of the values available at this node in the tree
098 */
099 public List getValues() {
100 return values;
101 }
102
103 /**
104 * Returns a mutable List of the values available at this node in the tree
105 */
106 public List removeValues() {
107 ArrayList v = new ArrayList(values);
108 // parent.getAnyChildNode().getValues().removeAll(v);
109 values.clear();
110 pruneIfEmpty();
111 return v;
112 }
113
114 public Set removeDesendentValues() {
115 Set answer = new HashSet();
116 removeDesendentValues(answer);
117 return answer;
118 }
119
120 protected void removeDesendentValues(Set answer) {
121 // if (anyChild != null) {
122 // anyChild.removeDesendentValues(answer);
123 // }
124 answer.addAll(removeValues());
125 }
126
127 /**
128 * Returns a list of all the values from this node down the tree
129 */
130 public Set getDesendentValues() {
131 Set answer = new HashSet();
132 appendDescendantValues(answer);
133 return answer;
134 }
135
136 public void add(String[] paths, int idx, Object value) {
137 if (idx >= paths.length) {
138 values.add(value);
139 } else {
140 // if (idx == paths.length - 1) {
141 // getAnyChildNode().getValues().add(value);
142 // }
143 // else {
144 // getAnyChildNode().add(paths, idx + 1, value);
145 // }
146 getChildOrCreate(paths[idx]).add(paths, idx + 1, value);
147 }
148 }
149
150 public void remove(String[] paths, int idx, Object value) {
151 if (idx >= paths.length) {
152 values.remove(value);
153 pruneIfEmpty();
154 } else {
155 // if (idx == paths.length - 1) {
156 // getAnyChildNode().getValues().remove(value);
157 // }
158 // else {
159 // getAnyChildNode().remove(paths, idx + 1, value);
160 // }
161 getChildOrCreate(paths[idx]).remove(paths, ++idx, value);
162 }
163 }
164
165 public void removeAll(Set answer, String[] paths, int startIndex) {
166 DestinationNode node = this;
167 int size = paths.length;
168 for (int i = startIndex; i < size && node != null; i++) {
169
170 String path = paths[i];
171 if (path.equals(ANY_DESCENDENT)) {
172 answer.addAll(node.removeDesendentValues());
173 break;
174 }
175
176 node.appendMatchingWildcards(answer, paths, i);
177 if (path.equals(ANY_CHILD)) {
178 // node = node.getAnyChildNode();
179 node = new AnyChildDestinationNode(node);
180 } else {
181 node = node.getChild(path);
182 }
183 }
184
185 if (node != null) {
186 answer.addAll(node.removeValues());
187 }
188
189 }
190
191 public void appendDescendantValues(Set answer) {
192 answer.addAll(values);
193
194 // lets add all the children too
195 Iterator iter = childNodes.values().iterator();
196 while (iter.hasNext()) {
197 DestinationNode child = (DestinationNode)iter.next();
198 child.appendDescendantValues(answer);
199 }
200
201 // TODO???
202 // if (anyChild != null) {
203 // anyChild.appendDescendantValues(answer);
204 // }
205 }
206
207 /**
208 * Factory method to create a child node
209 */
210 protected DestinationMapNode createChildNode() {
211 return new DestinationMapNode(this);
212 }
213
214 /**
215 * Matches any entries in the map containing wildcards
216 */
217 public void appendMatchingWildcards(Set answer, String[] paths, int idx) {
218 if (idx - 1 > pathLength) {
219 return;
220 }
221 DestinationMapNode wildCardNode = getChild(ANY_CHILD);
222 if (wildCardNode != null) {
223 wildCardNode.appendMatchingValues(answer, paths, idx + 1);
224 }
225 wildCardNode = getChild(ANY_DESCENDENT);
226 if (wildCardNode != null) {
227 answer.addAll(wildCardNode.getDesendentValues());
228 }
229 }
230
231 public void appendMatchingValues(Set answer, String[] paths, int startIndex) {
232 DestinationNode node = this;
233 boolean couldMatchAny = true;
234 int size = paths.length;
235 for (int i = startIndex; i < size && node != null; i++) {
236 String path = paths[i];
237 if (path.equals(ANY_DESCENDENT)) {
238 answer.addAll(node.getDesendentValues());
239 couldMatchAny = false;
240 break;
241 }
242
243 node.appendMatchingWildcards(answer, paths, i);
244
245 if (path.equals(ANY_CHILD)) {
246 node = new AnyChildDestinationNode(node);
247 } else {
248 node = node.getChild(path);
249 }
250 }
251 if (node != null) {
252 answer.addAll(node.getValues());
253 if (couldMatchAny) {
254 // lets allow FOO.BAR to match the FOO.BAR.> entry in the map
255 DestinationNode child = node.getChild(ANY_DESCENDENT);
256 if (child != null) {
257 answer.addAll(child.getValues());
258 }
259 }
260 }
261 }
262
263 public String getPath() {
264 return path;
265 }
266
267 protected void pruneIfEmpty() {
268 if (parent != null && childNodes.isEmpty() && values.isEmpty()) {
269 parent.removeChild(this);
270 }
271 }
272
273 protected void removeChild(DestinationMapNode node) {
274 childNodes.remove(node.getPath());
275 pruneIfEmpty();
276 }
277 }