001: // Copyright (c) 2001, 2002, 2003 Per M.A. Bothner and Brainfood Inc.
002: // This is free software; for terms and warranty disclaimer see ./COPYING.
003:
004: package gnu.lists;
005:
006: /** LListPosition - a SeqPosition for LLists.
007: * Normally, we just use an int pos to indicate a position in a
008: * sequence. But for linked lists that would be very inefficient.
009: * So this sub-class in addition uses an xpos field to point to the
010: * current Pair. However, we do so in a non-obvious way. After a next(),
011: * xpos points to *two* Pairs before the logical iterator position
012: * (the cursor). This is because of the requirement for remove(),
013: * which needs to be able to remove the element *before* the cursor.
014: * But to unlink that element, we need to change the 'next' field
015: * of the Pair before that again.
016: * However, after a call to 'previous', we cannot cheaply move the
017: * xpos pointer backwards, so we leave it as is. Therefore, we
018: * get the rule that when isAfter() is false the cursor position is
019: * after the Pair pointed by xpos; when isAfter() is true then
020: * the cursor position is after the Pair ((Pair) xpos).cdr).
021: * If the cursor position is too early in the list to satisfy this
022: * invariant, then xpos==null.
023: */
024:
025: class LListPosition extends ExtPosition {
026: Object xpos;
027:
028: public LListPosition(LListPosition old) {
029: sequence = old.sequence;
030: ipos = old.ipos;
031: xpos = old.xpos;
032: }
033:
034: public SeqPosition copy() {
035: return new LListPosition(this );
036: }
037:
038: public LListPosition(LList seq, int index, boolean isAfter) {
039: set(seq, index, isAfter);
040: }
041:
042: public void set(LList seq, int index, boolean isAfter) {
043: sequence = seq;
044: ipos = (index << 1) | (isAfter ? 1 : 0);
045: int skip = index;
046: if (isAfter) {
047: skip -= 2;
048: } else {
049: skip -= 1;
050: }
051: if (skip >= 0) {
052: Object p = seq;
053: while (--skip >= 0) {
054: p = ((Pair) p).cdr;
055: }
056: xpos = p;
057: } else
058: xpos = null;
059: }
060:
061: public void set(AbstractSequence seq, int index, boolean isAfter) {
062: set((LList) seq, index, isAfter);
063: }
064:
065: public boolean hasNext() {
066: Object next;
067: if (xpos == null) {
068: if ((ipos >> 1) == 0)
069: return sequence != LList.Empty;
070: return ((Pair) sequence).cdr != LList.Empty;
071: } else
072: next = ((Pair) xpos).cdr;
073: if ((ipos & 1) > 0) // if isAfter
074: next = ((Pair) next).cdr;
075: return next != LList.Empty;
076: }
077:
078: public boolean hasPrevious() {
079: return (ipos >>> 1) != 0;
080: }
081:
082: /** Get the Pair whose car contains the next element, or null. */
083: public Pair getNextPair() {
084: int isAfter = (ipos & 1);
085: Object next;
086: if (isAfter > 0) {
087: if (xpos == null) {
088: next = sequence;
089: if ((ipos >> 1) != 0)
090: next = ((Pair) next).cdr;
091: } else
092: next = ((Pair) (((Pair) xpos).cdr)).cdr;
093: } else {
094: if (xpos == null)
095: next = sequence;
096: else
097: next = ((Pair) xpos).cdr;
098: }
099: if (next == LList.Empty)
100: return null;
101: return (Pair) next;
102: }
103:
104: public Object getNext() {
105: Pair pair = getNextPair();
106: return pair == null ? LList.eofValue : pair.car;
107: }
108:
109: public void setNext(Object value) {
110: Pair pair = getNextPair();
111: pair.car = value;
112: }
113:
114: /** Get the Pair whose car contains the previous element, or null. */
115: public Pair getPreviousPair() {
116: int isAfter = (ipos & 1);
117: Object p = xpos;
118: if (isAfter > 0)
119: p = p == null ? sequence : ((Pair) p).cdr;
120: else if (p == null)
121: return null;
122: if (p == LList.Empty)
123: return null;
124: return (Pair) p;
125: }
126:
127: public Object getPrevious() {
128: Pair pair = getPreviousPair();
129: return pair == null ? LList.eofValue : pair.car;
130: }
131:
132: public void setPrevious(Object value) {
133: Pair pair = getPreviousPair();
134: pair.car = value;
135: }
136:
137: public int nextIndex() {
138: return ipos >> 1;
139: }
140:
141: public boolean gotoNext() {
142: boolean isAfter = (ipos & 1) != 0;
143: int old_i = ipos;
144: Object xp = xpos;
145: if (xp != null) {
146: if (isAfter)
147: xp = ((Pair) xp).cdr;
148: if (((Pair) xp).cdr == LList.Empty)
149: return false;
150: xpos = xp;
151: ipos = (ipos | 1) + 2;
152: } else if ((ipos >> 1) == 0) // position is 0
153: {
154: if (sequence == LList.Empty)
155: return false;
156: ipos = (1 << 1) | 1;
157: } else // position is 1, iAfter must be true
158: {
159: xp = sequence;
160: if (((Pair) xp).cdr == LList.Empty)
161: return false;
162: ipos = (2 << 1) | 1;
163: xpos = xp;
164: }
165: return true;
166: }
167:
168: public boolean gotoPrevious() {
169: if (ipos >>> 1 == 0)
170: return false;
171: if ((ipos & 1) != 0) // isAfter()
172: {
173: // Decrement index; clear isAfter bit.
174: ipos -= 3;
175: return true;
176: }
177: int index = nextIndex();
178: set((LList) sequence, index - 1, false);
179: return true;
180: }
181:
182: public String toString() {
183: StringBuffer sbuf = new StringBuffer();
184: sbuf.append("LListPos[");
185: //sbuf.append(super.toString());
186: sbuf.append("index:");
187: sbuf.append(ipos);
188: if (isAfter())
189: sbuf.append(" after");
190: if (position >= 0) {
191: sbuf.append(" position:");
192: sbuf.append(position);
193: }
194: sbuf.append(']');
195: return sbuf.toString();
196: }
197: }
|