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 */ 017package org.apache.activemq.filter; 018 019import java.util.ArrayList; 020import java.util.Collection; 021import java.util.HashMap; 022import java.util.HashSet; 023import java.util.List; 024import java.util.Map; 025import java.util.Set; 026 027/** 028 * An implementation class used to implement {@link DestinationMap} 029 * 030 * 031 */ 032public 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}