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 }