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    }