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