1/*
2 *  ConcatenationRopeReverseIteratorImpl.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 reverse iterator for concatenated ropes. Iterating over
32 * a complex rope structure is guaranteed to be O(n) so long as it
33 * is reasonably well-balanced. Compare this to O(n log n) for
34 * iteration using <code>charAt</code>.
35 *
36 * @author aahmad
37 */
38public class ConcatenationRopeReverseIteratorImpl implements Iterator<Character> {
39
40	private final ArrayDeque<Rope> toTraverse;
41	private final Rope rope;
42	private Rope currentRope;
43	private int currentRopePos;
44	private int skip;
45	private int currentAbsolutePos;
46
47
48	public ConcatenationRopeReverseIteratorImpl(final Rope rope) {
49		this(rope, 0);
50	}
51
52	public ConcatenationRopeReverseIteratorImpl(final Rope rope, final int start) {
53		this.rope = rope;
54		this.toTraverse = new ArrayDeque<Rope>();
55		this.toTraverse.push(rope);
56		this.currentRope = null;
57		this.initialize();
58
59		if (start < 0 || start > rope.length()) {
60			throw new IllegalArgumentException("Rope index out of range: " + start);
61		}
62		this.moveForward(start);
63	}
64
65	public boolean canMoveBackwards(final int amount) {
66		return (this.currentRopePos + amount <= this.currentRope.length());
67	}
68
69	public int getPos() {
70		return this.currentAbsolutePos;
71	}
72
73	@Override
74	public boolean hasNext() {
75		return this.currentRopePos > 0 || !this.toTraverse.isEmpty();
76	}
77
78	/**
79	 * Initialize the currentRope and currentRopePos fields.
80	 */
81	private void initialize() {
82		while (!this.toTraverse.isEmpty()) {
83			this.currentRope = this.toTraverse.pop();
84			if (this.currentRope instanceof ConcatenationRope) {
85				this.toTraverse.push(((ConcatenationRope) this.currentRope).getLeft());
86				this.toTraverse.push(((ConcatenationRope) this.currentRope).getRight());
87			} else {
88				break;
89			}
90		}
91		if (this.currentRope == null)
92			throw new IllegalArgumentException("No terminal ropes present.");
93		this.currentRopePos = this.currentRope.length();
94		this.currentAbsolutePos = this.rope.length();
95	}
96
97	public void moveBackwards(final int amount) {
98		if (!this.canMoveBackwards(amount))
99			throw new IllegalArgumentException("Unable to move backwards " + amount + ".");
100		this.currentRopePos += amount;
101		this.currentAbsolutePos += amount;
102	}
103
104	public void moveForward(final int amount) {
105		this.currentAbsolutePos -= amount;
106		int remainingAmt = amount;
107		while (remainingAmt != 0) {
108			if (this.currentRopePos - remainingAmt > -1) {
109				this.currentRopePos -= remainingAmt;
110				return;
111			}
112			remainingAmt = remainingAmt - this.currentRopePos;
113			if (remainingAmt > 0 && this.toTraverse.isEmpty())
114				throw new IllegalArgumentException("Unable to move forward " + amount + ". Reached end of rope.");
115
116			while (!this.toTraverse.isEmpty()) {
117				this.currentRope = this.toTraverse.pop();
118				if (this.currentRope instanceof ConcatenationRope) {
119					this.toTraverse.push(((ConcatenationRope) this.currentRope).getLeft());
120					this.toTraverse.push(((ConcatenationRope) this.currentRope).getRight());
121				} else {
122					this.currentRopePos = this.currentRope.length();
123					break;
124				}
125			}
126		}
127	}
128
129	@Override
130	public Character next() {
131		this.moveForward(1 + this.skip);
132		this.skip = 0;
133		return this.currentRope.charAt(this.currentRopePos);
134	}
135
136	@Override
137	public void remove() {
138		throw new UnsupportedOperationException("Rope iterator is read-only.");
139	}
140
141	/* (non-Javadoc)
142	 * @see org.ahmadsoft.ropes.impl.RopeIterators#skip(int)
143	 */
144	public void skip(final int skip) {
145		this.skip = skip;
146	}
147}
148