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.Iterator;
024import java.util.List;
025import java.util.Map;
026import java.util.Set;
027
028/**
029 * An implementation class used to implement {@link DestinationMap}
030 * 
031 * 
032 */
033public 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}