1/*
2 *  ConcatenationRopeIteratorImpl.java
3 *  Copyright (C) 2007 Amin Ahmad.
4 *
5 *  This file is part of Java Ropes.
6 *
7 *  Java Ropes is free software: you can redistribute it and/or modify
8 *  it under the terms of the GNU General Public License as published by
9 *  the Free Software Foundation, either version 3 of the License, or
10 *  (at your option) any later version.
11 *
12 *  Java Ropes is distributed in the hope that it will be useful,
13 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
14 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 *  GNU General Public License for more details.
16 *
17 *  You should have received a copy of the GNU General Public License
18 *  along with Java Ropes.  If not, see <http://www.gnu.org/licenses/>.
19 *
20 *  Amin Ahmad can be contacted at amin.ahmad@gmail.com or on the web at
21 *  www.ahmadsoft.org.
22 */
23package org.ahmadsoft.ropes.impl;
24
25import java.util.ArrayDeque;
26import java.util.Iterator;
27
28import org.ahmadsoft.ropes.Rope;
29
30/**
31 * A fast iterator for concatenated ropes. Iterating over a complex
32 * rope structure is guaranteed to be O(n) so long as it is reasonably
33 * well-balanced. Compare this to O(nlogn) for iteration using
34 * <code>charAt</code>.
35 *
36 * @author aahmad
37 */
38public class ConcatenationRopeIteratorImpl implements Iterator<Character> {
39
40	private final ArrayDeque<Rope> toTraverse;
41	private Rope currentRope;
42	private int currentRopePos;
43	private int skip;
44	private int currentAbsolutePos;
45
46
47	public ConcatenationRopeIteratorImpl(final Rope rope) {
48		this(rope, 0);
49	}
50
51	public ConcatenationRopeIteratorImpl(final Rope rope, final int start) {
52		this.toTraverse = new ArrayDeque<Rope>();
53		this.toTraverse.push(rope);
54		this.currentRope = null;
55		this.initialize();
56
57		if (start < 0 || start > rope.length()) {
58			throw new IllegalArgumentException("Rope index out of range: " + start);
59		}
60		this.moveForward(start);
61	}
62
63	public boolean canMoveBackwards(final int amount) {
64		return (-1 <= (this.currentRopePos - amount));
65	}
66
67	public int getPos() {
68		return this.currentAbsolutePos;
69	}
70
71	@Override
72	public boolean hasNext() {
73		return this.currentRopePos < this.currentRope.length() - 1 || !this.toTraverse.isEmpty();
74	}
75
76	/**
77	 * Initialize the currentRope and currentRopePos fields.
78	 */
79	private void initialize() {
80		while (!this.toTraverse.isEmpty()) {
81			this.currentRope = this.toTraverse.pop();
82			if (this.currentRope instanceof ConcatenationRope) {
83				this.toTraverse.push(((ConcatenationRope) this.currentRope).getRight());
84				this.toTraverse.push(((ConcatenationRope) this.currentRope).getLeft());
85			} else {
86				break;
87			}
88		}
89		if (this.currentRope == null)
90			throw new IllegalArgumentException("No terminal ropes present.");
91		this.currentRopePos = -1;
92		this.currentAbsolutePos = -1;
93	}
94
95	public void moveBackwards(final int amount) {
96		if (!this.canMoveBackwards(amount))
97			throw new IllegalArgumentException("Unable to move backwards " + amount + ".");
98		this.currentRopePos -= amount;
99		this.currentAbsolutePos -= amount;
100	}
101
102	public void moveForward(final int amount) {
103		this.currentAbsolutePos += amount;
104		int remainingAmt = amount;
105		while (remainingAmt != 0) {
106			final int available = this.currentRope.length() - this.currentRopePos - 1;
107			if (remainingAmt <= available) {
108				this.currentRopePos += remainingAmt;
109				return;
110			}
111			remainingAmt -= available;
112			if (this.toTraverse.isEmpty()) {
113				this.currentAbsolutePos -= remainingAmt;
114				throw new IllegalArgumentException("Unable to move forward " + amount + ". Reached end of rope.");
115			}
116
117			while (!this.toTraverse.isEmpty()) {
118				this.currentRope = this.toTraverse.pop();
119				if (this.currentRope instanceof ConcatenationRope) {
120					this.toTraverse.push(((ConcatenationRope) this.currentRope).getRight());
121					this.toTraverse.push(((ConcatenationRope) this.currentRope).getLeft());
122				} else {
123					this.currentRopePos = -1;
124					break;
125				}
126			}
127		}
128	}
129
130	@Override
131	public Character next() {
132		this.moveForward(1 + this.skip);
133		this.skip = 0;
134		return this.currentRope.charAt(this.currentRopePos);
135	}
136
137	@Override
138	public void remove() {
139		throw new UnsupportedOperationException("Rope iterator is read-only.");
140	}
141
142	/* (non-Javadoc)
143	 * @see org.ahmadsoft.ropes.impl.RopeIterators#skip(int)
144	 */
145	public void skip(final int skip) {
146		this.skip = skip;
147	}
148}
149