View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *   http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.myfaces.trinidad.model;
20  
21  import java.io.Serializable;
22  
23  import java.util.ArrayList;
24  import java.util.Collection;
25  import java.util.Collections;
26  import java.util.HashMap;
27  import java.util.Iterator;
28  import java.util.List;
29  import java.util.Map;
30  import java.util.Map.Entry;
31  import java.util.NoSuchElementException;
32  import java.util.Set;
33  import java.util.Stack;
34  
35  import org.apache.myfaces.trinidad.logging.TrinidadLogger;
36  
37  
38  /**
39   * Implements a collection of rowKeys from a TreeModel.
40   * The methods on this class are optimized such that it is possible
41   * to add/remove all the rowkeys in a subtree in constant time.
42   * <P>
43   * The generic type E is the type of a rowKey.
44   */
45  public class RowKeySetTreeImpl extends RowKeySet implements Serializable
46  {
47    /**
48     * Creates a new Set that is initially empty.
49     */
50    public RowKeySetTreeImpl()
51    {
52      this(false);
53    }
54  
55    /**
56     * Creates a new Set, that may contain every rowKey by default.
57     * @param addAll if this is true, every rowKey is initially added to this set.
58     */
59    public RowKeySetTreeImpl(boolean addAll)
60    {
61      _root = new Node<Object>(addAll);
62    }
63  
64    /**
65     * Tests to see if the given rowKey is included in this Set.
66     * @return true If the rowKey is included in this Set.
67     */
68    @Override
69    public boolean contains(Object rowKey)
70    {
71      return _isContained(rowKey);
72    }
73  
74    /**
75     * @deprecated do not use. this will be removed post Tier 1.
76     */
77    @Override
78    @Deprecated
79    public boolean isContainedByDefault()
80    {
81      TreeModel model = getCollectionModel();
82      
83      if (model != null)
84      {
85        Object rowkey = model.getRowKey();
86        return new Search().find(rowkey).isDefaultContained;
87      }
88      return false;
89    }
90  
91    @Override
92    public Iterator<Object> iterator()
93    {
94      if(_root.isDefaultContained)
95        return new PathIterator();
96      else
97        return new NodeIterator();
98    }
99  
100   /**
101    * Adds the given rowKey to this Set.
102    * @return false if the given rowKey was already in this Set.
103    * @see #remove(Object)
104    * @see #addAll()
105    */
106   @Override
107   public boolean add(Object rowKey)
108   {
109     return _setContained(rowKey, true);
110   }
111 
112   /**
113    * Removes the given rowKey from this Set.
114    * @return false if the given rowKey was already not in this Set.
115    * @see #add
116    * @see #removeAll()
117    */
118   @Override
119   public boolean remove(Object rowKey)
120   {
121     return _setContained(rowKey, false);
122   }
123 
124   /**
125    * Adds the current rowKey and all rowKeys beneath the current rowKey to this Set.
126    * This method executes in constant time.
127    * @see #add
128    * @see #removeAll()
129    */
130   @Override
131   public void addAll()
132   {
133     _selectAll(true);
134   }
135 
136   /**
137    * Removes the current rowKey and all rowKeys beneath the current rowKey to this Set.
138    * This method executes in constant time.
139    * @see #remove(Object)
140    * @see #clear()
141    * @see #addAll()
142    */
143   @Override
144   public void removeAll()
145   {
146     _selectAll(false);
147   }
148 
149   /**
150    * {@inheritDoc}
151    * <P>
152    * If the parameter is another RowKeySetTreeImpl, this method is
153    * optimized to give superior performance and avoid iteration.
154    */
155   @Override
156   public boolean addAll(Collection<? extends Object> other)
157   {
158     if (other instanceof RowKeySetTreeImpl)
159     {
160       RowKeySetTreeImpl otherset = (RowKeySetTreeImpl) other;
161       return _processOperation(this._root, otherset._root, true);
162     }
163     return super.addAll(other);
164   }
165 
166   /**
167    * {@inheritDoc}
168    * <P>
169    * If the parameter is another RowKeySetTreeImpl, this method is
170    * optimized to give superior performance and avoid iteration.
171    */
172   @Override
173   public boolean removeAll(Collection<?> other)
174   {
175     if (other instanceof RowKeySetTreeImpl)
176     {
177       RowKeySetTreeImpl otherset = (RowKeySetTreeImpl) other;
178       return _processOperation(this._root, otherset._root, false);
179     }
180     return super.removeAll(other);
181   }
182 
183   private boolean _processOperation(Node<Object> set1, Node<Object> set2, boolean add)
184   {
185     /*
186      * setXdef = setX.isDefaultContained
187      * setXdif = setX.isDifferent
188      * asterisks (*) indicate changes.
189      *
190      * TABLE ---------------------------------------------------
191      |-----------Inputs---------|--------Outputs---------------|
192      | set1def | set2def | add  | removeAll | addAll | set1def |
193      |    0    |    0    |  1   |     0     |   1    |    0    |
194      |    0    |    1    |  1   |     1     |   1    |    1*   |
195      |    1    |    0    |  1   |     0     |   0    |    1    |
196      |    1    |    1    |  1   |     1     |   0    |    1    |
197      |    0    |    0    |  0   |     0     |   0    |    0    |
198      |    0    |    1    |  0   |     1     |   0    |    0    |
199      |    1    |    0    |  0   |     0     |   1    |    1    |
200      |    1    |    1    |  0   |     1     |   1    |    0*   |
201      |---------------------------------------------------------|
202      */
203 
204     boolean hasChanges = false;
205 
206     // See TABLE (above) 'removeAll' column:
207     // if set2 contains everything, then there is no point hanging on to
208     // any set1-deltas that are not in set2, so remove them:
209     if (set2.isDefaultContained && set1.keySet().retainAll(set2.keySet()))
210         hasChanges = true;
211 
212     // See TABLE (above) 'addAll' column:
213     // this "addAll" flag controls whether to process any set2-deltas that are not
214     // already in set1. If set1 has everything by default and we're adding set2,
215     // then there is no point processing any set2-deltas not already in set1.
216     // Similarly, if set1 has nothing by default and we're removing set2,
217     // then there is no point processing any set2-deltas not already in set1.
218     // So only process the set2-deltas if we're doing an add (and set1
219     // does not contain everything) or we're doing a remove (and set1
220     // has everything):
221     boolean addAll = add ^ set1.isDefaultContained;
222 
223     for(Entry<Object, Node<Object>> en:set2.entrySet())
224     {
225       Object segment = en.getKey();
226       Node<Object> subset2 = en.getValue();
227       Node<Object> subset1 = set1.get(segment);
228 
229       if (subset1 == null)
230       {
231         if (addAll)
232         {
233           subset1 = new Node<Object>(set1, segment);
234           hasChanges = true;
235         }
236         else
237           continue;
238       }
239       if (_processOperation(subset1, subset2, add))
240         hasChanges = true;
241     }
242 
243     // See TABLE (above) 'Outputs/set1Def' column:
244     // if set2 contains everything by default, then that will affect
245     // the default flag of set1:
246     if (set2.isDefaultContained && (set1.isDefaultContained != add))
247     {
248       set1.isDefaultContained = add;
249       // since we toggled the default state, toggle the diff state
250       // as well so that we maintain the status for this node:
251       set1.isDifferent = !set1.isDifferent;
252       hasChanges = true;
253     }
254 
255     // if this node is contained by set2, then depending on the
256     // add flag, this node should (not) be contained by set1:
257     if ((set2.isDefaultContained ^ set2.isDifferent) &&
258         ((set1.isDefaultContained ^ set1.isDifferent) != add))
259     {
260       set1.isDifferent = !set1.isDifferent;
261       hasChanges = true;
262     }
263 
264     return hasChanges;
265   }
266 
267   /**
268    * Removes all rowKeys from this Set.
269    * This method executes in the same time as
270    * {@link HashMap#clear()}
271    */
272   @Override
273   public void clear()
274   {
275     _root.clear();
276     _root.isDefaultContained = _root.isDifferent = false;
277   }
278 
279   /**
280    * Gets the number of elements contained by this set.
281    * Does not force the underlying model to compute its size.
282    * @return -1 if the number of elements is unknown.
283    */
284   @Override
285   public int getSize()
286   {
287     return _getSize(null, _root, getCollectionModel(), false);
288   }
289 
290   /**
291    * Gets the number of elements in this Set.
292    * This might force the underlying model to compute its size.
293    * @return a non-negative number.
294    */
295   @Override
296   public int size()
297   {
298     return _getSize(null, _root, getCollectionModel(), true);
299   }
300 
301   @Override
302   public boolean isEmpty()
303   {
304     return (getSize() == 0);
305   }
306 
307   /**
308    * Sets the TreeModel associated with this Set.
309    * @param model This must be of type {@link TreeModel}
310    */
311   @Override
312   public final void setCollectionModel(CollectionModel model)
313   {
314     if (model != null && !(model instanceof TreeModel))
315       throw new IllegalArgumentException();
316 
317     _model = (TreeModel) model;
318   }
319 
320   /**
321    * Creates a clone of this Set. RowKeys may be added/removed from the
322    * clone without affecting this instance.
323    */
324   @Override
325   public RowKeySetTreeImpl clone()
326   {
327     RowKeySetTreeImpl clone = (RowKeySetTreeImpl) super.clone();
328     clone._root = _root.clone();
329     return clone;
330   }
331 
332   /**
333    * @deprecated not implemented.
334    */
335   @Deprecated
336   @Override
337   public void invertAll()
338   {
339     // TODO
340     throw new UnsupportedOperationException();
341   }
342 
343   /**
344    * Gets the TreeModel associated with this set.
345    * This TreeModel will be used to get the current rowKey, and also to
346    * get parent rowKeys, from child rowKeys.
347    * @see TreeModel#getRowKey
348    */
349   @Override
350   protected TreeModel getCollectionModel()
351   {
352     return _model;
353   }
354 
355   /**
356    * Gets the total number of nodes in the subtree of the given TreeModel.
357    *
358    * WARNING: this method changes the TreeModel's currency.
359    * The caller is responsible for restoring the model currency.
360    *
361    * @param exclusions any rowKeys present in this Set are excluded from the count.
362    */
363   @SuppressWarnings("unchecked")
364   private int _getTreeSize(TreeModel model, Set<Object> exclusions)
365   {
366     int sz = 0;
367     for(int i=0;true;i++)
368     {
369       model.setRowIndex(i);
370       if (model.isRowAvailable())
371       {
372         Object rowkey = model.getRowKey();
373         if (exclusions.contains(rowkey))
374           continue;
375         sz++;
376         if (model.isContainer())
377         {
378           model.enterContainer();
379           Set<Object> empty = Collections.emptySet();
380           sz += _getTreeSize(model, empty);
381           model.exitContainer();
382         }
383       }
384       else
385         return sz;
386     }
387   }
388 
389   private int _getSize(Object rowkey, Node<Object> set, TreeModel model,  boolean fetchall)
390   {
391     // special-case the root collection:
392     int sz = ((rowkey != null) && (set.isDefaultContained ^ set.isDifferent)) ? 1 : 0;
393     if (set.isDefaultContained)
394     {
395       if (!fetchall || model == null)
396         return -1;
397 
398       Object old = model.getRowKey();
399       try
400       {
401         model.setRowKey(rowkey);
402         // special-case the root collection:
403         if (rowkey == null)
404         {
405           sz += _getTreeSize(model, set.keySet());
406         }
407         else if (model.isContainer())
408         {
409           model.enterContainer();
410           sz += _getTreeSize(model, set.keySet());
411         }
412       }
413       finally
414       {
415         model.setRowKey(old);
416       }
417     }
418 
419     for(Entry<Object, Node<Object>> en:set.entrySet())
420     {
421       Object newrowkey = en.getKey();
422       Node<Object> subset = en.getValue();
423       int size = _getSize(newrowkey, subset, model, fetchall);
424       if (size < 0)
425         return -1;
426       sz+= size;
427     }
428     return sz;
429   }
430 
431   /**
432    * adds or removes all the paths rooted at the current path
433    * @param isSelectAll if true does an add-all. else does remove-all.
434    */
435   private void _selectAll(final boolean isSelectAll)
436   {
437     Search search = new Search()
438     {
439       @Override
440       protected boolean create(Node<Object> parent, Object rowkey)
441       {
442         // if the parent does not have the correct default, then
443         // we need to add entries for the children, since we need
444         // to store a delta:
445         return (parent.isDefaultContained != isSelectAll);
446       }
447 
448       @Override
449       protected Node<Object> found(Node<Object> child)
450       {
451         child.isDefaultContained = isSelectAll;
452         child.isDifferent = false;
453         child.clear();
454         return null;
455       }
456     };
457 
458     TreeModel model = getCollectionModel();
459     Object rowkey = model.getRowKey();
460     search.find(rowkey);
461   }
462 
463   private boolean _isContained(Object rowkey)
464   {
465     Search search = new Search()
466     {
467       @Override
468       protected Node<Object> notFound(Node<Object> parent, Object rowkey)
469       {
470         return parent.isDefaultContained ? parent : null;
471       }
472 
473       @Override
474       protected Node<Object> found(Node<Object> child)
475       {
476         return (child.isDefaultContained ^ child.isDifferent) ? child : null;
477       }
478     };
479 
480     return (search.find(rowkey) != null);
481   }
482 
483   /**
484    * Adds or removes the given path from this set.
485    * @param isContained If true, the current path is added. Otherwise,
486    * it is removed.
487    * @return true if this Set changed due to this operation.
488    */
489   private boolean _setContained(Object rowkey, final boolean isContained)
490   {
491     Search search = new Search()
492     {
493       @Override
494       protected boolean create(Node<Object> parent, Object rowkey)
495       {
496         // only need to create child deltas, if the parent's
497         // default is wrong:
498         return parent.isDefaultContained != isContained;
499       }
500 
501       @Override
502       protected Node<Object> notFound(Node<Object> parent, Object rowkey)
503       {
504         return null;
505       }
506     };
507 
508     Node<Object> current = search.find(rowkey);
509     if ((current != null) &&
510         ((current.isDefaultContained ^ current.isDifferent) != isContained))
511     {
512       current.isDifferent = !current.isDifferent;
513       return true;
514     }
515     return false;
516   }
517 
518   /**
519    * Advances the currency of the given TreeModel to the next node in a
520    * depth-first walk of the tree.
521    * @param minDepth the minimum depth of the rowkey. use this to
522    * walk within a subtree. Use 0 to walk entire tree.
523    * @param recurseChildren if true, will walk children.
524    * @return true if the currency of the model was successfully advanced to
525    * the next rowData.
526    */
527   private static boolean _advanceToNextItem(
528     TreeModel model, int minDepth, boolean recurseChildren)
529   {
530     assert minDepth >= 0;
531 
532     if (recurseChildren && model.isRowAvailable() && model.isContainer())
533     {
534       model.enterContainer();
535       model.setRowIndex(-1);
536     }
537     while(true)
538     {
539       int ri = model.getRowIndex();
540       model.setRowIndex(ri+1);
541       if (model.isRowAvailable())
542         return true;
543 
544       int depth = model.getDepth();
545       if (depth <= minDepth)
546         return false;
547 
548       model.exitContainer();
549     }
550   }
551 
552   /**
553    * Check for "default contained" nodes in the set
554    * @return true if there are "default contained" nodes
555    */
556   private boolean _containsDefaultNodes()
557   {
558     if(_root.isDefaultContained)
559       return true;
560 
561     SetLoop loop = new SetLoop()
562     {
563       protected boolean next(Object rowKey, Node<Object> value)
564       {
565         return value.isDefaultContained;
566       }
567     };
568     return loop.run(_root);
569   }
570 
571   /**
572    * Utility to dump Node attributes
573    */
574   private void _dumpFlags()
575   {
576     System.out.println("root " + _root.isDefaultContained + " " + _root.isDifferent);
577     SetLoop loop = new SetLoop()
578     {
579       protected boolean next(Object rowKey, Node<Object> value)
580       {
581         System.out.println(rowKey + " " + value.isDefaultContained + " " + value.isDifferent);
582         return false;
583       }
584     };
585     loop.run(_root);
586   }
587 
588   // Needs to be Serializable and Cloneable - but HashMap already is
589   private static final class Node<K> extends HashMap<K, Node<K>>
590      /* implements Serializable, Cloneable */
591   {
592     public boolean isDifferent = false;
593     public boolean isDefaultContained = false;
594 
595     public Node(boolean isDefaultContained)
596     {
597       this.isDefaultContained = isDefaultContained;
598     }
599 
600     public Node(Node<K> parent, K segment)
601     {
602       this(parent.isDefaultContained);
603       parent.put(segment, this);
604     }
605 
606     // clone all the values as well:
607     private void _deepClone(Node<K> root)
608     {
609       for(Entry<K, Node<K>> en:root.entrySet())
610       {
611         Node<K> original = en.getValue();
612         Node<K> clone = original.clone();
613         en.setValue(clone);
614       }
615     }
616 
617     @SuppressWarnings("unchecked")
618     @Override
619     public Node<K> clone()
620     {
621       Node<K> clone = (Node<K>) super.clone();
622       _deepClone(clone);
623       return clone;
624     }
625 
626     private static final long serialVersionUID = 1L;
627   }
628 
629   private class Search
630   {
631     public Search()
632     {
633     }
634 
635     protected boolean create(Node<Object> parent, Object rowkey)
636     {
637       return false;
638     }
639 
640     protected Node<Object> notFound(Node<Object> parent, Object rowkey)
641     {
642       return parent;
643     }
644 
645     protected Node<Object> found(Node<Object> result)
646     {
647       return result;
648     }
649 
650     public Node<Object> find(Object rowkey)
651     {
652       Node<Object> current = _root;
653       if (rowkey != null)
654       {
655         TreeModel model = getCollectionModel();
656         if (model == null)
657         {
658           return notFound(current, rowkey);
659         }
660         List<Object> parentkeys = model.getAllAncestorContainerRowKeys(rowkey);
661         List<Object> allkeys = new ArrayList<Object>(parentkeys.size() + 1);
662         allkeys.addAll(parentkeys);
663         allkeys.add(rowkey);
664         for(Object key:allkeys)
665         {
666           Node<Object> next = current.get(key);
667           if (next == null)
668           {
669             if (create(current, key))
670               next = new Node<Object>(current, key);
671             else
672               return notFound(current, key);
673           }
674           current = next;
675         }
676       }
677       return found(current);
678     }
679   }
680 
681   /**
682    * Loop (depth first) over the set or a subset and call a callback function
683    * for each node
684    */
685   private static abstract class SetLoop
686   {
687     public SetLoop()
688     {
689     }
690 
691     public boolean run (Node<Object> set)
692     {
693       for(Entry<Object, Node<Object>> en : set.entrySet())
694       {
695         Object keyEnt = en.getKey();
696         Node<Object> subset = en.getValue();
697         if(next(keyEnt, subset))
698           return true;
699         if(run(subset))
700           return true;
701       }
702       return false;
703     }
704 
705     protected abstract boolean next(Object rowKey, Node<Object> value );
706   }
707 
708   private class PathIterator implements Iterator<Object>
709   {
710     PathIterator()
711     {
712       _value = (getCollectionModel() == null || isEmpty()) ? null : nextItem(); // initialize;
713     }
714 
715     PathIterator(Object noop)
716     {
717     }
718 
719     public Object next()
720     {
721       if (!hasNext())
722         throw new NoSuchElementException();
723       Object value = _value;
724       _value = nextItem();
725       return value;
726     }
727 
728     public boolean hasNext()
729     {
730       return (_value != null);
731     }
732 
733     public void remove()
734     {
735       throw new UnsupportedOperationException();
736     }
737 
738     protected Object nextItem()
739     {
740       return nextModelKey(0);
741     }
742 
743     protected Object nextModelKey(int minDepth)
744     {
745       TreeModel model = getCollectionModel();
746       if (model == null)
747         return null;
748 
749       Object oldPath = model.getRowKey();
750       try
751       {
752         model.setRowKey(_currPath);
753         while(true)
754         {
755           boolean searchChildren = _containsSubtree(_currPath);
756           boolean hasMore = _advanceToNextItem(model, minDepth, searchChildren);
757           if (!hasMore)
758             return null;
759 
760           _currPath = model.getRowKey();
761           if (contains(_currPath))
762             return _currPath;
763         }
764       }
765       finally
766       {
767         model.setRowKey(oldPath);
768       }
769     }
770 
771     private boolean _containsSubtree(Object rowkey)
772     {
773       Search search = new Search()
774       {
775         @Override
776         protected Node<Object> notFound(Node<Object> parent, Object rowkey)
777         {
778           return parent.isDefaultContained ? parent : null;
779         }
780       };
781       Node<Object> current = search.find(rowkey);
782       return (current != null) &&
783         ((!current.isEmpty()) || current.isDefaultContained);
784     }
785 
786     protected Object _value;
787     protected Object _currPath = null;
788   }
789 
790   /**
791    * An iterator which avoids looping over the model by default (like the
792    * PathIterator does). Instead NodeIterator loops over the model only for nodes that are "default contained".
793    * Otherwise, it just does a depth first walk of the set and returns "isDifferent" nodes.
794    */
795   private class NodeIterator extends PathIterator
796   {
797     public NodeIterator()
798     {
799       super(null);
800       _currIterator = _root.entrySet().iterator();
801       _value = (getCollectionModel() == null || isEmpty()) ? null : nextItem(); // initialize;
802     }
803 
804     protected Object nextItem()
805     {
806       Object nextKey = null;
807 
808       while(((nextKey = _nextEntry()) == null) && _iteratorStack.size() > 0)
809         if(_currPath == null)
810           _currIterator = _iteratorStack.pop();
811       return nextKey;
812     }
813 
814     private Object _nextEntry()
815     {
816       Object nextKey = null;
817       if(_currPath != null)
818       {
819         nextKey = nextModelKey(_minDepth);
820         if(nextKey == null)
821         {
822           _currPath = null;
823           // Since, all the child nodes of the curent iterator are
824           // iterated by nextModelKey call updating the _currIterator here to avoid 
825           // looping through the same node again and again.  
826           if(_iteratorStack.size() > 0)
827             _currIterator = _iteratorStack.pop();
828           _nextEntry();
829         }
830       }
831       else
832       {
833         Map.Entry<Object, Node<Object>> nextNode;
834         while(nextKey == null && _currIterator.hasNext())
835         {
836           nextNode = _currIterator.next();
837           if(_isContained(nextNode.getKey()))
838             nextKey = nextNode.getKey();
839           // When the currentNode has no child nodes, the 
840           // iterator instance is not pushed to iteratorStack.
841           if(!nextNode.getValue().isEmpty())
842           {
843             _iteratorStack.push(_currIterator);
844             _currIterator = nextNode.getValue().entrySet().iterator();
845             if(nextNode.getValue().isDefaultContained)
846             {
847               _currPath = nextNode.getKey();
848               TreeModel model = getCollectionModel();
849               Object oldPath = model.getRowKey();
850               model.setRowKey(_currPath);
851               _minDepth = model.getDepth() + 1;
852               model.setRowKey(oldPath);
853               return nextKey;
854             }
855           }
856         }
857       }
858       return nextKey;
859     }
860 
861     private Stack<Iterator <Map.Entry<Object, Node<Object>>>> _iteratorStack =
862       new Stack<Iterator <Map.Entry<Object, Node<Object>>>>();
863     private Iterator <Map.Entry<Object, Node<Object>>> _currIterator;
864     private int _minDepth;
865   }
866 
867   private Node<Object> _root;
868   private transient TreeModel _model = null;
869   private static final long serialVersionUID = 1L;
870   private static final TrinidadLogger _LOG =
871     TrinidadLogger.createTrinidadLogger(RowKeySetTreeImpl.class);
872 }