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.List;
024 import java.util.Map;
025 import java.util.Set;
026
027 /**
028 * An implementation class used to implement {@link DestinationMap}
029 *
030 *
031 */
032 public class DestinationMapNode implements DestinationNode {
033 protected static final String ANY_CHILD = DestinationMap.ANY_CHILD;
034 protected static final String ANY_DESCENDENT = DestinationMap.ANY_DESCENDENT;
035
036 // we synchronize at the DestinationMap level
037 private DestinationMapNode parent;
038 private List<Object> values = new ArrayList<Object>();
039 private Map<String, DestinationNode> childNodes = new HashMap<String, DestinationNode>();
040 private String path = "Root";
041 // private DestinationMapNode anyChild;
042 private int pathLength;
043
044 public DestinationMapNode(DestinationMapNode parent) {
045 this.parent = parent;
046 if (parent == null) {
047 pathLength = 0;
048 } else {
049 pathLength = parent.pathLength + 1;
050 }
051 }
052
053 /**
054 * Returns the child node for the given named path or null if it does not
055 * exist
056 */
057 public DestinationNode getChild(String path) {
058 return childNodes.get(path);
059 }
060
061 /**
062 * Returns the child nodes
063 */
064 public Collection<DestinationNode> getChildren() {
065 return childNodes.values();
066 }
067
068 public int getChildCount() {
069 return childNodes.size();
070 }
071
072 /**
073 * Returns the child node for the given named path, lazily creating one if
074 * it does not yet exist
075 */
076 public DestinationMapNode getChildOrCreate(String path) {
077 DestinationMapNode answer = (DestinationMapNode)childNodes.get(path);
078 if (answer == null) {
079 answer = createChildNode();
080 answer.path = path;
081 childNodes.put(path, answer);
082 }
083 return answer;
084 }
085
086 /**
087 * Returns a mutable List of the values available at this node in the tree
088 */
089 @SuppressWarnings({ "rawtypes", "unchecked" })
090 public List getValues() {
091 return values;
092 }
093
094 /**
095 * Returns a mutable List of the values available at this node in the tree
096 */
097 @SuppressWarnings({ "rawtypes", "unchecked" })
098 public List removeValues() {
099 ArrayList v = new ArrayList(values);
100 // parent.getAnyChildNode().getValues().removeAll(v);
101 values.clear();
102 pruneIfEmpty();
103 return v;
104 }
105
106 @SuppressWarnings({ "rawtypes", "unchecked" })
107 public Set removeDesendentValues() {
108 Set answer = new HashSet();
109 removeDesendentValues(answer);
110 return answer;
111 }
112
113 @SuppressWarnings({ "rawtypes", "unchecked" })
114 protected void removeDesendentValues(Set answer) {
115 answer.addAll(removeValues());
116 }
117
118 /**
119 * Returns a list of all the values from this node down the tree
120 */
121 @SuppressWarnings({ "rawtypes", "unchecked" })
122 public Set getDesendentValues() {
123 Set answer = new HashSet();
124 appendDescendantValues(answer);
125 return answer;
126 }
127
128 public void add(String[] paths, int idx, Object value) {
129 if (idx >= paths.length) {
130 values.add(value);
131 } else {
132 getChildOrCreate(paths[idx]).add(paths, idx + 1, value);
133 }
134 }
135
136 public void remove(String[] paths, int idx, Object value) {
137 if (idx >= paths.length) {
138 values.remove(value);
139 pruneIfEmpty();
140 } else {
141 getChildOrCreate(paths[idx]).remove(paths, ++idx, value);
142 }
143 }
144
145 public void removeAll(Set<DestinationNode> answer, String[] paths, int startIndex) {
146 DestinationNode node = this;
147 int size = paths.length;
148 for (int i = startIndex; i < size && node != null; i++) {
149
150 String path = paths[i];
151 if (path.equals(ANY_DESCENDENT)) {
152 answer.addAll(node.removeDesendentValues());
153 break;
154 }
155
156 node.appendMatchingWildcards(answer, paths, i);
157 if (path.equals(ANY_CHILD)) {
158 // node = node.getAnyChildNode();
159 node = new AnyChildDestinationNode(node);
160 } else {
161 node = node.getChild(path);
162 }
163 }
164
165 if (node != null) {
166 answer.addAll(node.removeValues());
167 }
168
169 }
170
171 @SuppressWarnings({ "rawtypes", "unchecked" })
172 public void appendDescendantValues(Set answer) {
173 answer.addAll(values);
174
175 // lets add all the children too
176 for(DestinationNode child : childNodes.values()) {
177 child.appendDescendantValues(answer);
178 }
179 }
180
181 /**
182 * Factory method to create a child node
183 */
184 protected DestinationMapNode createChildNode() {
185 return new DestinationMapNode(this);
186 }
187
188 /**
189 * Matches any entries in the map containing wildcards
190 */
191 @SuppressWarnings({ "rawtypes", "unchecked" })
192 public void appendMatchingWildcards(Set answer, String[] paths, int idx) {
193 if (idx - 1 > pathLength) {
194 return;
195 }
196 DestinationNode wildCardNode = getChild(ANY_CHILD);
197 if (wildCardNode != null) {
198 wildCardNode.appendMatchingValues(answer, paths, idx + 1);
199 }
200 wildCardNode = getChild(ANY_DESCENDENT);
201 if (wildCardNode != null) {
202 answer.addAll(wildCardNode.getDesendentValues());
203 }
204 }
205
206 public void appendMatchingValues(Set<DestinationNode> answer, String[] paths, int startIndex) {
207 DestinationNode node = this;
208 boolean couldMatchAny = true;
209 int size = paths.length;
210 for (int i = startIndex; i < size && node != null; i++) {
211 String path = paths[i];
212 if (path.equals(ANY_DESCENDENT)) {
213 answer.addAll(node.getDesendentValues());
214 couldMatchAny = false;
215 break;
216 }
217
218 node.appendMatchingWildcards(answer, paths, i);
219
220 if (path.equals(ANY_CHILD)) {
221 node = new AnyChildDestinationNode(node);
222 } else {
223 node = node.getChild(path);
224 }
225 }
226 if (node != null) {
227 answer.addAll(node.getValues());
228 if (couldMatchAny) {
229 // lets allow FOO.BAR to match the FOO.BAR.> entry in the map
230 DestinationNode child = node.getChild(ANY_DESCENDENT);
231 if (child != null) {
232 answer.addAll(child.getValues());
233 }
234 }
235 }
236 }
237
238 public String getPath() {
239 return path;
240 }
241
242 protected void pruneIfEmpty() {
243 if (parent != null && childNodes.isEmpty() && values.isEmpty()) {
244 parent.removeChild(this);
245 }
246 }
247
248 protected void removeChild(DestinationMapNode node) {
249 childNodes.remove(node.getPath());
250 pruneIfEmpty();
251 }
252 }