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}