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     * Removes 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        ArrayList<DestinationNode> candidates = new ArrayList<>();
116        for (Map.Entry<String, DestinationNode> child : childNodes.entrySet()) {
117            candidates.add(child.getValue());
118        }
119
120        for (DestinationNode node : candidates) {
121            // remove all the values from the child
122            answer.addAll(node.removeValues());
123            answer.addAll(node.removeDesendentValues());
124        }
125    }
126
127    /**
128     * Returns a list of all the values from this node down the tree
129     */
130    @SuppressWarnings({ "rawtypes", "unchecked" })
131    public Set getDesendentValues() {
132        Set answer = new HashSet();
133        appendDescendantValues(answer);
134        return answer;
135    }
136
137    public void add(String[] paths, int idx, Object value) {
138        if (idx >= paths.length) {
139            values.add(value);
140        } else {
141            getChildOrCreate(paths[idx]).add(paths, idx + 1, value);
142        }
143    }
144
145    public void set(String[] paths, int idx, Object value) {
146        if (idx >= paths.length) {
147            values.clear();
148            values.add(value);
149        } else {
150            getChildOrCreate(paths[idx]).set(paths, idx + 1, value);
151        }
152    }
153
154    public void remove(String[] paths, int idx, Object value) {
155        if (idx >= paths.length) {
156            values.remove(value);
157            pruneIfEmpty();
158        } else {
159            getChildOrCreate(paths[idx]).remove(paths, ++idx, value);
160        }
161    }
162
163    public void removeAll(Set<DestinationNode> answer, String[] paths, int startIndex) {
164        DestinationNode node = this;
165        int size = paths.length;
166        for (int i = startIndex; i < size && node != null; i++) {
167
168            String path = paths[i];
169            if (path.equals(ANY_DESCENDENT)) {
170                answer.addAll(node.removeDesendentValues());
171                break;
172            }
173
174            // TODO is this correct, we are appending wildcard values here???
175            node.appendMatchingWildcards(answer, paths, i);
176            if (path.equals(ANY_CHILD)) {
177                // node = node.getAnyChildNode();
178                node = new AnyChildDestinationNode(node);
179            } else {
180                node = node.getChild(path);
181            }
182        }
183
184        if (node != null) {
185            answer.addAll(node.removeValues());
186        }
187
188    }
189
190    @SuppressWarnings({ "rawtypes", "unchecked" })
191    public void appendDescendantValues(Set answer) {
192        // add children values, then recursively add their children
193        for(DestinationNode child : childNodes.values()) {
194            answer.addAll(child.getValues());
195            child.appendDescendantValues(answer);
196        }
197    }
198
199    /**
200     * Factory method to create a child node
201     */
202    protected DestinationMapNode createChildNode() {
203        return new DestinationMapNode(this);
204    }
205
206    /**
207     * Matches any entries in the map containing wildcards
208     */
209    @SuppressWarnings({ "rawtypes", "unchecked" })
210    public void appendMatchingWildcards(Set answer, String[] paths, int idx) {
211        if (idx - 1 > pathLength) {
212            return;
213        }
214        DestinationNode wildCardNode = getChild(ANY_CHILD);
215        if (wildCardNode != null) {
216            wildCardNode.appendMatchingValues(answer, paths, idx + 1);
217        }
218        wildCardNode = getChild(ANY_DESCENDENT);
219        if (wildCardNode != null) {
220            // for a wildcard Node match, add all values of the descendant node
221            answer.addAll(wildCardNode.getValues());
222            // and all descendants for paths like ">.>"
223            answer.addAll(wildCardNode.getDesendentValues());
224        }
225    }
226
227    @SuppressWarnings({"rawtypes", "unchecked"})
228    public void appendMatchingValues(Set answer, String[] paths, int idx) {
229        appendMatchingValues(answer, paths, idx, true);
230    }
231
232    public void appendMatchingValues(Set<DestinationNode> answer, String[] paths, int startIndex, boolean deep) {
233        DestinationNode node = this;
234        boolean couldMatchAny = true;
235        int size = paths.length;
236        for (int i = startIndex; i < size && node != null; i++) {
237            String path = paths[i];
238            if (deep && path.equals(ANY_DESCENDENT)) {
239                answer.addAll(node.getDesendentValues());
240                couldMatchAny = false;
241                break;
242            }
243
244            node.appendMatchingWildcards(answer, paths, i);
245
246            if (path.equals(ANY_CHILD)) {
247                node = new AnyChildDestinationNode(node);
248            } else {
249                node = node.getChild(path);
250            }
251        }
252        if (node != null) {
253            answer.addAll(node.getValues());
254            if (couldMatchAny) {
255                // lets allow FOO.BAR to match the FOO.BAR.> entry in the map
256                DestinationNode child = node.getChild(ANY_DESCENDENT);
257                if (child != null) {
258                    answer.addAll(child.getValues());
259                }
260            }
261        }
262    }
263
264    public String getPath() {
265        return path;
266    }
267
268    public boolean isEmpty(){
269        return childNodes.isEmpty();
270    }
271
272    protected void pruneIfEmpty() {
273        if (parent != null && childNodes.isEmpty() && values.isEmpty()) {
274            parent.removeChild(this);
275        }
276    }
277
278    protected void removeChild(DestinationMapNode node) {
279        childNodes.remove(node.getPath());
280        pruneIfEmpty();
281    }
282}