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