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    }