From 5a7b622274d47160f2e755b7dbb7af2999196a51 Mon Sep 17 00:00:00 2001 From: Roman Kennke Date: Thu, 30 Nov 2006 19:05:24 +0000 Subject: 2006-11-30 Roman Kennke * javax/swing/text/ElementIterator.java (ElementRef): New inner class. (currentDepth): Removed. (currentElement): Removed. (previousItem): Removed. (stack): New field. Holds the iteration stack. (state): Removed. (ElementIterator(Document)): Removed init of removed fields. (ElementIterator(Element)): Removed init of removed fields. (current): Changed to stack based algorithm. (deepestLeaf): New helper method. (depth): Changed to stack based algorithm. (first): Changed to stack based algorithm. (next): Changed to stack based algorithm. (previous): Changed to stack based algorithm. --- ChangeLog | 18 +++ javax/swing/text/ElementIterator.java | 203 ++++++++++++++++++++++++---------- 2 files changed, 165 insertions(+), 56 deletions(-) diff --git a/ChangeLog b/ChangeLog index 33a1b22a2..019d81972 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,21 @@ +2006-11-30 Roman Kennke + + * javax/swing/text/ElementIterator.java + (ElementRef): New inner class. + (currentDepth): Removed. + (currentElement): Removed. + (previousItem): Removed. + (stack): New field. Holds the iteration stack. + (state): Removed. + (ElementIterator(Document)): Removed init of removed fields. + (ElementIterator(Element)): Removed init of removed fields. + (current): Changed to stack based algorithm. + (deepestLeaf): New helper method. + (depth): Changed to stack based algorithm. + (first): Changed to stack based algorithm. + (next): Changed to stack based algorithm. + (previous): Changed to stack based algorithm. + 2006-11-30 Francis Kung * .settings/org.eclipse.jdt.core.prefs: Set compilar compliance to 1.4. diff --git a/javax/swing/text/ElementIterator.java b/javax/swing/text/ElementIterator.java index a6a5ff618..112d55e96 100644 --- a/javax/swing/text/ElementIterator.java +++ b/javax/swing/text/ElementIterator.java @@ -37,6 +37,8 @@ exception statement from your version. */ package javax.swing.text; +import java.util.Stack; + /** * This class can be used to iterate over the {@link Element} tree of * a {@link Document} or an {@link Element}. This iterator performs @@ -46,20 +48,41 @@ package javax.swing.text; */ public class ElementIterator implements Cloneable { + /** + * Uses to track the iteration on the stack. + */ + private class ElementRef + { + /** + * The element. + */ + Element element; + + /** + * The child index. -1 means the element itself. >= 0 values mean the + * n-th child of the element. + */ + int index; + + /** + * Creates a new ElementRef. + * + * @param el the element + */ + ElementRef(Element el) + { + element = el; + index = -1; + } + } + // The root element. private Element root; - // The current element. - private Element currentElement; - // The depth to which we have descended in the tree. - private int currentDepth; - - // This is at least as big as the current depth, and at index N - // contains the index of the child element we're currently - // examining. - private int[] state; - // The previous item. - private Element previousItem; + /** + * Holds ElementRefs. + */ + private Stack stack; /** * Create a new ElementIterator to iterate over the given document. @@ -67,9 +90,7 @@ public class ElementIterator implements Cloneable */ public ElementIterator(Document document) { - this.root = document.getDefaultRootElement(); - this.currentElement = root; - this.state = new int[5]; + root = document.getDefaultRootElement(); } /** @@ -79,8 +100,6 @@ public class ElementIterator implements Cloneable public ElementIterator(Element root) { this.root = root; - this.currentElement = root; - this.state = new int[5]; } /** @@ -105,7 +124,24 @@ public class ElementIterator implements Cloneable */ public Element current() { - return currentElement; + Element current; + if (stack == null) + current = first(); + else + { + current = null; + if (! stack.isEmpty()) + { + ElementRef ref = (ElementRef) stack.peek(); + Element el = ref.element; + int index = ref.index; + if (index == -1) + current = el; + else + current = el.getElement(index); + } + } + return current; } /** @@ -113,7 +149,10 @@ public class ElementIterator implements Cloneable */ public int depth() { - return currentDepth; + int depth = 0; + if (stack != null) + depth = stack.size(); + return depth; } /** @@ -121,11 +160,15 @@ public class ElementIterator implements Cloneable */ public Element first() { - // Reset the iterator. - currentElement = root; - currentDepth = 0; - previousItem = null; - return root; + Element first = null; + if (root != null) + { + stack = new Stack(); + if (root.getElementCount() > 0) + stack.push(new ElementRef(root)); + first = root; + } + return first; } /** @@ -134,48 +177,96 @@ public class ElementIterator implements Cloneable */ public Element next() { - previousItem = currentElement; - if (currentElement == null) - return null; - if (! currentElement.isLeaf()) + Element next; + if (stack == null) + next = first(); + else { - ++currentDepth; - if (currentDepth > state.length) - { - int[] newState = new int[state.length * 2]; - System.arraycopy(state, 0, newState, 0, state.length); - state = newState; - } - state[currentDepth] = 0; - currentElement = currentElement.getElement(0); - return currentElement; + next = null; + if (! stack.isEmpty()) + { + ElementRef ref = (ElementRef) stack.peek(); + Element el = ref.element; + int index = ref.index; + if (el.getElementCount() > index + 1) + { + Element child = el.getElement(index + 1); + if (child.isLeaf()) + ref.index++; + else + stack.push(new ElementRef(child)); + next = child; + next = child; + } + else + { + stack.pop(); + if (! stack.isEmpty()) + { + ElementRef top = (ElementRef) stack.peek(); + top.index++; + next = next(); + } + } + } + // else return null. } + return next; + } - while (currentDepth > 0) + /** + * Returns the previous item. Does not modify the iterator state. + */ + public Element previous() + { + Element previous = null; + int stackSize; + if (stack != null && (stackSize = stack.size()) > 0) { - // At a leaf, or done with a non-leaf's children, so go up a - // level. - --currentDepth; - currentElement = currentElement.getParentElement(); - ++state[currentDepth]; - if (state[currentDepth] < currentElement.getElementCount()) - { - currentElement = currentElement.getElement(state[currentDepth]); - return currentElement; - } + ElementRef ref = (ElementRef) stack.peek(); + Element el = ref.element; + int index = ref.index; + if (index > 0) + { + previous = deepestLeaf(el.getElement(--index)); + } + else if (index == 0) + { + previous = el; + } + else if (index == -1) + { + ElementRef top = (ElementRef) stack.pop(); + ElementRef item = (ElementRef) stack.peek(); + stack.push(top); + index = item.index; + el = item.element; + previous = index == -1 ? el : deepestLeaf(el.getElement(index)); + } } - - currentElement = null; - return currentElement; + return previous; } /** - * Returns the previous item. Does not modify the iterator state. + * Determines and returns the deepest leaf of the element el. + * + * @param el the base element + * + * @returnthe deepest leaf of the element el */ - public Element previous() + private Element deepestLeaf(Element el) { - if (currentElement == null || currentElement == root) - return null; - return previousItem; + Element leaf; + if (el.isLeaf()) + leaf = el; + else + { + int count = el.getElementCount(); + if (count == 0) + leaf = el; + else + leaf = deepestLeaf(el.getElement(count - 1)); + } + return leaf; } } -- cgit v1.2.1