TreeList


1   /*
2   
3   This software is OSI Certified Open Source Software.
4   OSI Certified is a certification mark of the Open Source Initiative.
5   
6   The license (Mozilla version 1.0) can be read at the MMBase site.
7   See http://www.MMBase.org/license
8   
9   */
10  
11  package org.mmbase.bridge.util;
12  
13  import org.mmbase.bridge.*;
14  import org.mmbase.storage.search.*;
15  import org.mmbase.util.logging.*;
16  
17  import java.util.*;
18  
19  /**
20   * Queries a Tree from MMBase. A Tree is presented as a List of MultiLevel results (ClusterNodes),
21   * combined with a smart iterator which iterates through the elements of these lists as if it was one
22   * list ordered as a Tree.
23   *
24   *
25   * @author  Michiel Meeuwissen
26   * @version $Id: TreeList.java,v 1.21 2006/06/23 15:21:51 michiel Exp $
27   * @since   MMBase-1.7
28   */
29  
30  public class TreeList extends AbstractSequentialBridgeList implements NodeList {
31      private static final Logger log = Logging.getLoggerInstance(TreeList.class);
32  
33      public static final String   REAL_NODES = "realnodes";
34  
35      protected Cloud cloud;
36      protected final List /*<Branch>*/ branches        = new ArrayList();
37  
38      protected int topQuery = 0;
39      protected int numberOfSteps;
40      private   int size;
41      private boolean needsSizeCheck = true;
42  
43      protected boolean foundEnd = false;
44      protected int     leafConstraintOffset = Integer.MAX_VALUE;
45  
46      /**
47       * @since MMBase-1.8.1
48       */
49      protected int    max = SearchQuery.DEFAULT_MAX_NUMBER;
50  
51      /**
52       * @param q              The 'base' query defining the minimal depth of the tree elements. The trunk of the tree.
53       */
54  
55      public TreeList(NodeQuery q) {
56  
57          if (q.getOffset() > 0) {
58              throw new UnsupportedOperationException  ("Don't know how to implement that");
59          }
60          cloud = q.getCloud();
61          branches.add(new Branch(q));
62          numberOfSteps = q.getSteps().size();
63  
64      }
65  
66      /**
67       * Copy-constructor
68       * @since MMBase-1.8
69       */
70      public TreeList(TreeList tl) {
71          cloud = tl.cloud;
72          Iterator i = tl.branches.iterator();
73          while(i.hasNext()) {
74              Branch b = (Branch) i.next();
75              branches.add(new Branch(b));
76          }
77          topQuery = tl.topQuery;
78          numberOfSteps = tl.numberOfSteps;
79          size = tl.size;
80          needsSizeCheck = tl.needsSizeCheck;
81          foundEnd = tl.foundEnd;
82          leafConstraintOffset = tl.leafConstraintOffset;
83      }
84  
85      /**
86       * @since MMBase-1.8.1
87       */
88      public void setMax(int m) {
89          max = m;
90      }
91  
92      /**
93       * @since MMBase-1.8.1
94       */
95      public int getMax() {
96          return max;
97      }
98  
99      /**
100      * @since MMBase-1.8
101      */
102     public Cloud getCloud() {
103         return cloud;
104     }
105 
106     // javadoc inherited
107     public int size() {
108         sizeCheck();
109         return max != SearchQuery.DEFAULT_MAX_NUMBER ? (max < size ? max : size) : size;
110     }
111 
112 
113     /**
114      * Checks if the size of the List needs to be (re)determined, and if not, does so. After growing
115      * a List the size needs recalculation.
116      * @since MMBase-1.7.1
117      */
118     protected void sizeCheck() {
119         if (needsSizeCheck) {
120             int count;
121             Branch branch = (Branch) branches.get(topQuery);
122             if (branch.leafResult != null) {  // not quite sure that this can hapen
123                 count = branch.leafResult.size();
124             } else {
125                 NodeQuery newQuery = branch.getLeafQuery();
126                 count = Queries.count(newQuery);
127             }
128 
129             if (count == 0) {
130                 foundEnd =
131                     branch.leafConstraint == null || 
132                     Queries.count(branch.getQuery()) == 0;
133             }
134             size += count;
135             needsSizeCheck = false;
136         }
137     }
138 
139     /**
140      * Grows branches of the Tree, which means that one new query will be created which is one
141      * relationStep longer than the longest one until now.
142      * This new relationStep is returned, which can be used to create new constraints.
143      *
144      * @return <code>null</code> if no relationstep is added because that would not increase the number of results.
145      */
146 
147     public RelationStep grow(NodeManager nodeManager, String   role, String   searchDir) {
148         sizeCheck();
149         if (foundEnd) {
150             return null;
151         }
152         needsSizeCheck = true;
153 
154         NodeQuery lastQuery = ((Branch)branches.get(topQuery)).getQuery();
155         NodeQuery newQuery  = (NodeQuery)lastQuery.cloneWithoutFields();
156 
157         // add relations step
158         RelationStep step = newQuery.addRelationStep(nodeManager, role, searchDir);
159         Step nextStep = step.getNext();
160 
161         // make sure every step has a unique alias
162         newQuery.setAlias(step, step.getTableName() + (numberOfSteps - 1));
163         newQuery.setAlias(nextStep, nodeManager.getName() + numberOfSteps);
164 
165         // new number of steps
166         numberOfSteps = newQuery.getSteps().size();
167 
168         // the new step must be the 'node' step
169         newQuery.setNodeStep(nextStep);
170 
171         branches.add(new Branch(newQuery));
172         topQuery++;
173 
174         return step;
175     }
176 
177     /**
178      * Returns the top most query, associated with the last call to {@link #grow}.
179      * @since MMBase-1.8
180      */
181     public NodeQuery getLeafQuery() {
182         return ((Branch) branches.get(topQuery)).getQuery();
183     }
184 
185     /**
186      * Sets a 'leaf constraint' on the last 'growed' step. A leaf constraint is a constraint which is only
187      * used on leafs, so if the tree is grown further, the leaf constraint will not be passed to the branches.
188      * @since MMBase-1.8
189      */
190     public void setLeafConstraint(Constraint constraint) {
191 
192         Branch branch = (Branch) branches.get(topQuery);
193         if (branch.result != null) {
194             throw new IllegalStateException  ("The query for branch " + topQuery + " was already executed");
195         }
196         if (topQuery < leafConstraintOffset) {
197             leafConstraintOffset = topQuery;
198         }
199         leafConstraintOffset = 0;
200         branch.leafConstraint = constraint;
201 
202     }
203 
204     /**
205      * Executes one query if that did not happen yet, and stores the result in the 'results' List
206      * @return NodeList or <code>null</code> if queryNumber too big
207      * @throws IndexOutOfBoundsException if queryNumber < 0
208      */
209     protected NodeList getList(int queryNumber) {
210         if (queryNumber < 0) {
211             throw new IndexOutOfBoundsException  ("No query for '" + queryNumber + "'");
212         }
213 
214         if (queryNumber >= branches.size()) {
215             return null;
216         }
217 
218         Branch branch = (Branch) branches.get(queryNumber);
219         if (branch.result == null) {
220             NodeQuery query = branch.getQuery();
221             branch.result =  cloud.getList(query);
222             if (branch.leafConstraint == null) {
223                 branch.leafResult = branch.result;
224             }
225         }
226         return branch.result;
227     }
228     /**
229      * Executes one query as a 'leaf' query.
230      * @since MMBase-1.8
231      */
232     protected NodeList getLeafList(int queryNumber) {
233         if (queryNumber < 0) {
234             throw new IndexOutOfBoundsException  ("No query for '" + queryNumber + "'");
235         }
236 
237         if (queryNumber >= branches.size()) {
238             return null;
239         }
240 
241         Branch branch = (Branch) branches.get(queryNumber);
242         if (branch.leafResult == null) {
243             NodeQuery query = branch.getLeafQuery();
244             branch.leafResult =  cloud.getList(query);
245             if (branch.leafConstraint == null) {
246                 branch.result = branch.leafResult;
247             }
248         }
249         return branch.leafResult;
250     }
251 
252     // javadoc inherited
253     public ListIterator listIterator(int ind) {
254         return treeIterator(ind);
255     }
256 
257     public NodeIterator nodeIterator() {
258         return treeIterator(0);
259     }
260 
261     public TreeIterator treeIterator() {
262         return treeIterator(0);
263     }
264 
265     protected TreeIterator treeIterator(int ind) {
266         return new TreeItr(ind);
267     }
268 
269     // javadoc inherited
270     public Node getNode(int i) {
271         return (Node)get(i);
272     }
273 
274     /**
275      * Returns node 'index' of query result 'queryIndex' as a 'real' node (so not a cluster node)
276      */
277     protected Node getRealNode(int queryIndex, int index) {
278         NodeList nodeList  = getLeafList(queryIndex);
279         NodeList realNodes = (NodeList)nodeList.getProperty(REAL_NODES);
280         if (realNodes == null) {
281             Branch branch = (Branch) branches.get(queryIndex);
282             NodeQuery nq = branch.getLeafQuery();
283             realNodes = nq.getNodeManager().getList(nq); // We trust the query cache! (the query is performed already, but on Cloud)
284             nodeList.setProperty(REAL_NODES, realNodes);
285         }
286         return realNodes.getNode(index);
287     }
288 
289     public NodeList subNodeList(int start, int end) {
290         throw new UnsupportedOperationException  ("SubNodeLists not implemented for TreeList");
291     }
292 
293     public String   toString() {
294         int size = size();
295         return "size: " + size + " " + branches.toString();
296     }
297 
298 
299     /**
300      * Structure to hold the information for every branch-depth.
301      * @since MMBase-1.8
302      */
303     protected class Branch {
304         final private NodeQuery query;
305         private NodeQuery leafQuery = null;
306         NodeList result     =   null;
307         NodeList leafResult    = null;
308         Constraint leafConstraint = null;
309 
310         Branch(NodeQuery q) {
311             query = q;
312         }
313         Branch(Branch b) {
314             query = (NodeQuery) b.query.clone();
315             result = b.result;
316             leafQuery = b.leafQuery == null ? null : (NodeQuery) b.leafQuery.clone();
317             leafResult = null;
318             leafConstraint = b.leafConstraint;
319         }
320         NodeQuery getQuery() {
321             return query;
322         }
323 
324         NodeQuery getLeafQuery() {
325             if (leafQuery != null) return leafQuery;
326             Queries.sortUniquely(query);
327             Queries.addSortedFields(query);
328             int m = TreeList.this.getMax();
329             if (m != SearchQuery.DEFAULT_MAX_NUMBER) {
330                 int cm = query.getMaxNumber();
331                 if (cm == -1 || m < cm) {
332                     query.setMaxNumber(m);
333                 }
334             }
335             query.markUsed();
336             if (leafConstraint != null) {
337                 leafQuery = (NodeQuery) query.clone();
338                 Queries.addConstraint(leafQuery, leafConstraint);
339                 leafQuery.markUsed();
340             } else {
341                 leafQuery = query;
342             }
343             return leafQuery;
344         }
345 
346 
347         public String   toString() {
348             return query.toString()  + (leafConstraint != null ? "[" + leafConstraint + "]" : "");
349         }
350 
351     }
352 
353     /**
354      * The TreeIterator contains the core-functionality of TreeList.
355      */
356     protected class TreeItr implements TreeIterator {
357 
358         private List nodeIterators = new ArrayList(); // an iterator for each query result
359         private NodeList nextNodes = TreeList.this.cloud.createNodeList();
360         // contains 'next' nodes for each query result (needed for 'next()')
361 
362         private NodeList previousNodes = TreeList.this.cloud.createNodeList();
363         // contains 'previous' nodes for each query result (needed for 'previous()')
364 
365         private int currentIterator; // number of current iterator which is iterated
366         private int nextIndex;       // the next index number, so this is 0 on the beginning, and <size> just before the last next()
367 
368         private boolean encounteredLeafConstraint = false;
369 
370         TreeItr(int i) {
371             if (i < 0 || (i > 0 && i > TreeList.this.size())) {
372                 throw new IndexOutOfBoundsException  ("Index: " + i + ", Size: " + TreeList.this.size());
373             }
374             currentIterator = 0;
375             nextIndex = 0;
376             while (nextIndex < i) {
377                 next(); // fast forward to requested start index.
378             }
379 
380         }
381 
382         public boolean hasNext() {
383             if (TreeList.this.max != SearchQuery.DEFAULT_MAX_NUMBER && nextIndex > TreeList.this.max) return false;
384             if (TreeList.this.foundEnd) { // why bother
385                 return nextIndex < TreeList.this.size();
386             } else {
387                 int i = 0;
388                 while (prepare(i)) {
389                     NodeIterator iterator = (NodeIterator)nodeIterators.get(i);
390                     Node nextNode = (Node) nextNodes.get(i);
391                     if (nextNode != null) {
392                         return true;
393                     } else {
394                         i++;
395                     }
396                 }
397                 return false;
398             }
399         }
400 
401         /**
402          * Makes sure that query with given index has an iterator, a 'next' node and a 'previous' node.
403          * @return true it such  query existed, false, otherwise
404          */
405         protected final boolean prepare(int index) {
406             for (int i = nodeIterators.size(); i <= index; i++) {
407                 NodeList nl = TreeList.this.getLeafList(i);
408                 if (TreeList.this.leafConstraintOffset <= i) {
409                     encounteredLeafConstraint = true;
410                 }
411                 NodeIterator iterator = null;
412                 if (nl != null) {
413                     iterator = nl.nodeIterator();
414                 }
415                 nodeIterators.add(iterator);
416                 previousNodes.add(null);     // just prepared iterator never has a previous node already
417                 if (iterator == null) {
418                     nextNodes.add(null);
419                     return false;
420                 } else {
421                     if (iterator.hasNext()) {
422                         nextNodes.add(iterator.nextNode());
423                     } else {
424                         nextNodes.add(null);
425                         return true;
426                     }
427                 }
428             }
429             return true;
430         }
431 
432         /**
433          * Uses the new 'next' node of the iterator with the given index.
434          * This means that it becomes the previous node and that a new 'next' node will be determined
435          */
436         protected final void useNext(int index) {
437             Node node = nextNodes.getNode(index);
438             if (node == null) throw new NoSuchElementException("No such element " + index + " in " + nextNodes);
439             previousNodes.set(index, node);
440             NodeIterator iterator = (NodeIterator)nodeIterators.get(index);
441             if (iterator.hasNext()) {
442                 Node nextNode = iterator.nextNode();
443                 nextNodes.set(index, nextNode);
444             } else {
445                 nextNodes.set(index, null);
446             }
447         }
448 
449         /**
450          * Returns the 'real' node, us the just used 'next' node of index.
451          */
452         protected final Node getRealNode(int index) {
453             ListIterator iterator = (ListIterator)nodeIterators.get(index);
454             return TreeList.this.getRealNode(index, iterator.previousIndex());
455         }
456 
457         public Node nextNode() {
458             nextIndex++;
459             return getNextNode();
460         }
461 
462         /**
463          * Depth of the last node fetched with next() or nextNode()
464          */
465         public int currentDepth() {
466             Branch branch = (Branch) TreeList.this.branches.get(currentIterator);
467             int depth = (branch.query.getSteps().size() + 1) / 2;
468             if (nextIndex == 0) {
469                 return depth - 1;
470             } else {
471                 return depth;
472             }
473         }
474 
475         public Object   next() {
476             return nextNode();
477         }
478 
479         /**
480          *
481          * Implementation idea graphicly.
482          <pre>
483                         iterators
484 
485 
486               current-2  current-1  current       current+1                         [///]: used node
487                [///]       [///]     [///]         [///]                            [|||]: last used node (lastNode)
488                                                                                     [   ]: unused node
489          ...   [///]       [///]     [|||] _       [///]    previousNodes           [ * ]: considered next node (nextListNextNode)
490                                             \
491                [   ]       [   ]     [   ]   `---> [ * ]    nextNodes
492 
493                if (! [|||] contained by [ * ]) current--
494          </pre>
495 
496          Every time next is called, the last used node is compared with the next node of the
497          next iterator (the arrow in the above scheme). If the last used node is 'contained' by
498          this next node, then this next node of the next iterator will be 'next()' otherwise current
499          is decreased by one and next is called recursively. This means that the next node is always
500          one longer than the current one, equally long, or shorter.
501 
502          If 'leaf constraints' are in use, then the implementation jumps to getNextLeafNode, which simply returns the 'smallest node' of all iterators.
503         */
504         protected final Node getNextNode() {
505             prepare(currentIterator);
506             if (encounteredLeafConstraint) {
507                 return getNextLeafNode();
508             }
509 
510             final Branch currentBranch = (Branch) TreeList.this.branches.get(currentIterator);
511 
512             Node previousNode = previousNodes.getNode(currentIterator);
513             if (previousNode == null) {  // first of iterator
514                 Node node = getRealNode(currentIterator);
515                 useNext(currentIterator);
516                 return node;
517             }
518 
519             Node nextListNextNode =  prepare(currentIterator + 1) ? nextNodes.getNode(currentIterator + 1) : null;
520 
521             if (nextListNextNode == null) {
522                 if (currentIterator > 0) {
523                     currentIterator--;
524                     return getNextNode();
525                 } else {
526                     Node node = getRealNode(0);
527                     useNext(0);
528                     return node;
529                 }
530             }
531 
532             List sortOrders = currentBranch.getQuery().getSortOrders();
533             final boolean contains = Queries.compare(previousNode, nextListNextNode, sortOrders) >= 0;
534 
535             if (log.isDebugEnabled()) {
536                 log.debug("comparing " + previousNode + " with " + nextListNextNode);
537             }
538 
539             if (contains) {
540                 currentIterator++;
541                 Node node = getRealNode(currentIterator);
542                 useNext(currentIterator);
543                 return node;
544             } else {
545                 if (currentIterator > 0) {
546                     currentIterator--;
547                     return getNextNode();
548                 } else {
549                     Node node = getRealNode(0);
550                     useNext(0);
551                     return node;
552                 }
553             }
554         }
555 
556         /**
557          * Simply returns the 'smallest' of all available nodes (compared to the 'previous node')
558          * This is actually an alternavite implementation for getNextNode, but it also works when
559          * 'leaf' constraints are applied.
560          * @since MMBase-1.8
561          */
562         protected final Node getNextLeafNode() {
563             Node smallestAvailableNode = null;
564             List smallestSortOrders = null;  // Sort-Orders list of smallest availabe node.
565             int i = -1;
566 
567             while(prepare(++i)) {
568                 Node candidate = i < nextNodes.size() ? nextNodes.getNode(i) : null;
569                 if (candidate == null) {
570                     continue;
571                 }
572                 Branch branch = (Branch) TreeList.this.branches.get(i);
573                 List sortOrders = branch.getLeafQuery().getSortOrders();
574                 if (smallestAvailableNode == null) {
575                     smallestAvailableNode = candidate;
576                     smallestSortOrders    = sortOrders;
577                     currentIterator       = i;
578                 } else {
579                     List compareSortOrders = sortOrders.size() < smallestSortOrders.size() ? sortOrders : smallestSortOrders;
580                     int compare = Queries.compare(candidate, smallestAvailableNode, compareSortOrders);
581                     if (compare < 0) {
582                         smallestAvailableNode = candidate;
583                         smallestSortOrders   = sortOrders;
584                         currentIterator      = i;
585                     }
586                 }
587             }
588             if (smallestAvailableNode == null) {
589                 throw new NoSuchElementException();
590             }
591             Node node = getRealNode(currentIterator);
592             useNext(currentIterator);
593             return node;
594         }
595 
596         public boolean hasPrevious() {
597             return nextIndex > 0;
598         }
599 
600         public Node previousNode() {
601             nextIndex--;
602             throw new UnsupportedOperationException  ("unfinished");
603         }
604         public Object   previous() {
605             return previousNode();
606         }
607         public int nextIndex() {
608             return nextIndex;
609         }
610 
611         public int previousIndex() {
612             return nextIndex - 1;
613         }
614 
615         public void remove() {
616             throw new UnsupportedOperationException  ("TreeList is not modifiable");
617         }
618 
619         public void set(Object   o) {
620             throw new UnsupportedOperationException  ("TreeList is not modifiable");
621         }
622 
623         public void add(Object   o) {
624             throw new UnsupportedOperationException  ("TreeList is not modifiable");
625         }
626 
627     }
628 
629     /**
630      * For testing only. Based on RMMCI,
631      * please use the System property to specify de cloud context
632      * -Dmmbase.defaultcloudcontext=rmi://localhost:1111/remotecontext
633      * @param args the start node (in one argument)
634      */
635 
636     protected static NodeQuery getQuery(String  [] args) {
637         if (args.length == 0) {
638             System.err.println("Usage: java -Dmmbase.defaultcloudcontext=rmi://localhost:1111/remotecontext " + TreeList.class.getName() + " <startnode>");
639             System.exit(1);
640         }
641 
642         String   startNodes = args[0];
643         Cloud cloud = ContextProvider.getDefaultCloudContext().getCloud("mmbase");
644 
645         NodeManager object = cloud.getNodeManager("segments");
646 
647         NodeQuery q = cloud.createNodeQuery();
648         Step step = q.addStep(object);
649         q.setNodeStep(step);
650         RelationStep relationStep = q.addRelationStep(object, "index", "destination");
651         q.setNodeStep(relationStep.getNext());
652         StepField pos = q.createStepField(relationStep, "pos");
653         q.addSortOrder(pos, SortOrder.ORDER_ASCENDING);
654 
655         object.getList(q);
656 
657         Queries.addStartNodes(q, startNodes);
658         return q;
659     }
660 
661     public static void doTest(java.io.Writer   writer, NodeQuery q) {
662         Cloud cloud = q.getCloud();
663 
664         NodeManager object = cloud.getNodeManager("segments");
665         try {
666             //String text = "%potjandosie%";
667             String   text = "%%";
668 
669             long startTime = System.currentTimeMillis();
670 
671             TreeList tree = new TreeList(q);
672             Constraint con2 = Queries.createConstraint(tree.getLeafQuery(), "body", Queries.getOperator("LIKE"), text);
673             //tree.setLeafConstraint(con2);
674 
675             writer.write("grow1:\n");
676             writer.flush();
677             RelationStep step = tree.grow(object, "index", "destination");
678             NodeQuery top = tree.getLeafQuery();
679             Constraint con1 = Queries.createConstraint(top, "body", Queries.getOperator("LIKE"), text);
680             //tree.setLeafConstraint(con1);
681             StepField pos = top.createStepField(step, "pos");
682             top.addSortOrder(pos, SortOrder.ORDER_ASCENDING);
683 
684             writer.write("top " + top.toSql() + " grow2:\n");
685             writer.flush();
686             tree.grow(object, "index", "destination");
687             NodeQuery leaf = tree.getLeafQuery();
688             Constraint con = Queries.createConstraint(leaf, "body", Queries.getOperator("LIKE"), text);
689             //tree.setLeafConstraint(con);
690 
691             writer.write("GROWN, now using ================================================================================");writer.flush();
692             TreeIterator i = tree.treeIterator();
693             writer.write("initial depth " + i.currentDepth() + "\n");
694             writer.flush();
695             writer.write("size: " + tree.size() + "\n");
696             writer.flush();
697             while (i.hasNext()) {
698                 Node n = (Node)i.next();
699                 try {
700                     writer.write(n.getFunctionValue("index", null).toString() + "\t");
701                 } catch(Exception   e) {
702                 }
703                 writer.write(i.currentDepth() + "  " + n.getNumber() + " " + n.getFunctionValue("gui", null) + "\n");
704                 writer.flush();
705             }
706             writer.write("size: " + tree.size() + "\n");
707             writer.write("duration: " + (System.currentTimeMillis() - startTime) + " ms\n");
708             writer.write("finish depth: " + i.currentDepth());
709             writer.flush();
710         } catch (Exception   e) {
711             System.err.println(e.getClass().getName() + e.getMessage() + Logging.stackTrace(e));
712         }
713 
714     }
715 
716     public static void main(String  [] args) {
717         NodeQuery q = getQuery(args);
718         doTest(new java.io.OutputStreamWriter  (System.out), q);
719 
720     }
721 
722 }
723
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags