org.spearce.jgit/src/org/spearce/jgit/lib/TreeIterator.java

   1 /*
   2  * Copyright (C) 2008, Robin Rosenberg <robin.rosenberg@dewire.com>
   3  * Copyright (C) 2006, Shawn O. Pearce <spearce@spearce.org>
   4  *
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or
   8  * without modification, are permitted provided that the following
   9  * conditions are met:
  10  *
  11  * - Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  *
  14  * - Redistributions in binary form must reproduce the above
  15  *   copyright notice, this list of conditions and the following
  16  *   disclaimer in the documentation and/or other materials provided
  17  *   with the distribution.
  18  *
  19  * - Neither the name of the Git Development Community nor the
  20  *   names of its contributors may be used to endorse or promote
  21  *   products derived from this software without specific prior
  22  *   written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  25  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  26  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  27  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  28  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  29  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  31  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  34  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  35  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  36  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  37  */
  38
  39 package org.spearce.jgit.lib;
  40
  41 import java.io.IOException;
  42 import java.util.Iterator;
  43
  44 /**
  45  * A tree iterator iterates over a tree and all its members recursing into
  46  * subtrees according to order.
  47  *
  48  * Default is to only visit leafs. An {@link Order} value can be supplied to
  49  * make the iteration include Tree nodes as well either before or after the
  50  * child nodes have been visited.
  51  */
  52 public class TreeIterator implements Iterator<TreeEntry> {
  53
  54         private Tree tree;
  55
  56         private int index;
  57
  58         private TreeIterator sub;
  59
  60         private Order order;
  61
  62         private boolean visitTreeNodes;
  63
  64         private boolean hasVisitedTree;
  65
  66         /**
  67          * Traversal order
  68          */
  69         public enum Order {
  70                 /**
  71                  * Visit node first, then leaves
  72                  */
  73                 PREORDER,
  74
  75                 /**
  76                  * Visit leaves first, then node
  77                  */
  78                 POSTORDER
  79         };
  80
  81         /**
  82          * Construct a {@link TreeIterator} for visiting all non-tree nodes.
  83          *
  84          * @param start
  85          */
  86         public TreeIterator(Tree start) {
  87                 this(start, Order.PREORDER, false);
  88         }
  89
  90         /**
  91          * Construct a {@link TreeIterator} visiting all nodes in a tree in a given
  92          * order.
  93          *
  94          * @param start Root node
  95          * @param order {@link Order}
  96          */
  97         public TreeIterator(Tree start, Order order) {
  98                 this(start, order, true);
  99         }
 100
 101         /**
 102          * Construct a {@link TreeIterator}
 103          *
 104          * @param start First node to visit
 105          * @param order Visitation {@link Order}
 106          * @param visitTreeNode True to include tree node
 107          */
 108         private TreeIterator(Tree start, Order order, boolean visitTreeNode) {
 109                 this.tree = start;
 110                 this.visitTreeNodes = visitTreeNode;
 111                 this.index = -1;
 112                 this.order = order;
 113                 if (!visitTreeNodes)
 114                         this.hasVisitedTree = true;
 115                 try {
 116                         step();
 117                 } catch (IOException e) {
 118                         throw new Error(e);
 119                 }
 120         }
 121
 122         public TreeEntry next() {
 123                 try {
 124                         TreeEntry ret = nextTreeEntry();
 125                         step();
 126                         return ret;
 127                 } catch (IOException e) {
 128                         throw new Error(e);
 129                 }
 130         }
 131
 132         private TreeEntry nextTreeEntry() throws IOException {
 133                 TreeEntry ret;
 134                 if (sub != null)
 135                         ret = sub.nextTreeEntry();
 136                 else {
 137                         if (index < 0 && order == Order.PREORDER) {
 138                                 return tree;
 139                         }
 140                         if (order == Order.POSTORDER && index == tree.memberCount()) {
 141                                 return tree;
 142                         }
 143                         ret = tree.members()[index];
 144                 }
 145                 return ret;
 146         }
 147
 148         public boolean hasNext() {
 149                 try {
 150                         return hasNextTreeEntry();
 151                 } catch (IOException e) {
 152                         throw new Error(e);
 153                 }
 154         }
 155
 156         private boolean hasNextTreeEntry() throws IOException {
 157                 if (tree == null)
 158                         return false;
 159                 return sub != null
 160                         || index < tree.memberCount()
 161                         || order == Order.POSTORDER && index == tree.memberCount();
 162         }
 163
 164         private boolean step() throws IOException {
 165                 if (tree == null)
 166                         return false;
 167
 168                 if (sub != null) {
 169                         if (sub.step())
 170                                 return true;
 171                         sub = null;
 172                 }
 173
 174                 if (index < 0 && !hasVisitedTree && order == Order.PREORDER) {
 175                         hasVisitedTree = true;
 176                         return true;
 177                 }
 178
 179                 while (++index < tree.memberCount()) {
 180                         TreeEntry e = tree.members()[index];
 181                         if (e instanceof Tree) {
 182                                 sub = new TreeIterator((Tree) e, order, visitTreeNodes);
 183                                 if (sub.hasNextTreeEntry())
 184                                         return true;
 185                                 sub = null;
 186                                 continue;
 187                         }
 188                         return true;
 189                 }
 190
 191                 if (index == tree.memberCount() && !hasVisitedTree
 192                                 && order == Order.POSTORDER) {
 193                         hasVisitedTree = true;
 194                         return true;
 195                 }
 196                 return false;
 197         }
 198
 199         public void remove() {
 200                 throw new IllegalStateException(
 201                                 "TreeIterator does not suppport remove()");
 202         }
 203 }