LListPosition


1   // Copyright (c) 2001, 2002, 2003  Per M.A. Bothner and Brainfood Inc.
2   // This is free software;  for terms and warranty disclaimer see ./COPYING.
3   
4   package gnu.lists;
5   
6   /** LListPosition - a SeqPosition for LLists.
7    * Normally, we just use an int pos to indicate a position in a
8    * sequence.  But for linked lists that would be very inefficient.
9    * So this sub-class in addition uses an xpos field to point to the
10   * current Pair.  However, we do so in a non-obvious way.  After a next(),
11   * xpos points to *two* Pairs before the logical iterator position
12   * (the cursor).  This is because of the requirement for remove(),
13   * which needs to be able to remove the element *before* the cursor.
14   * But to unlink that element, we need to change the 'next' field
15   * of the Pair before that again.
16   * However, after a call to 'previous', we cannot cheaply move the
17   * xpos pointer backwards, so we leave it as is.  Therefore, we
18   * get the rule that when isAfter() is false the cursor position is
19   * after the Pair pointed by xpos; when isAfter() is true then
20   * the cursor position is after the Pair ((Pair) xpos).cdr).
21   * If the cursor position is too early in the list to satisfy this
22   * invariant, then xpos==null.
23   */
24  
25  class LListPosition extends ExtPosition
26  {
27    Object   xpos;
28  
29    public LListPosition (LListPosition old)
30    {
31      sequence = old.sequence;
32      ipos = old.ipos;
33      xpos = old.xpos;
34    }
35  
36    public SeqPosition copy ()
37    {
38      return new LListPosition(this);
39    }
40  
41    public LListPosition (LList seq, int index, boolean isAfter)
42    {
43      set(seq, index, isAfter);
44    }
45  
46    public void set (LList seq, int index, boolean isAfter)
47    {
48      sequence = seq;
49      ipos = (index << 1) | (isAfter ? 1 : 0);
50      int skip = index;
51      if (isAfter)
52        {
53          skip -= 2;
54        }
55      else
56        {
57          skip -= 1;
58        }
59      if (skip >= 0)
60        {
61      Object   p = seq;
62          while (--skip >= 0)
63            {
64              p = ((Pair) p).cdr;
65            }
66      xpos = p;
67        }
68      else
69        xpos = null;
70    }
71  
72    public void set (AbstractSequence seq, int index, boolean isAfter)
73    {
74      set((LList) seq, index, isAfter);
75    }
76  
77    public boolean hasNext()
78    {
79      Object   next;
80      if (xpos == null)
81        {
82          if ((ipos >> 1) == 0)
83            return sequence != LList.Empty;
84          return ((Pair) sequence).cdr != LList.Empty;
85        }
86      else
87        next = ((Pair) xpos).cdr;
88      if ((ipos & 1) > 0) // if isAfter
89        next = ((Pair) next).cdr;
90      return next != LList.Empty;
91    }
92  
93    public boolean hasPrevious()
94    {
95      return (ipos >>> 1) != 0;
96    }
97  
98    /** Get the Pair whose car contains the next element, or null. */
99    public Pair getNextPair ()
100   {
101     int isAfter = (ipos & 1);
102     Object   next;
103     if (isAfter > 0)
104       {
105         if (xpos == null)
106           {
107         next = sequence;
108         if ((ipos >> 1) != 0)
109           next = ((Pair) next).cdr;
110           }
111         else
112           next = ((Pair) (((Pair) xpos).cdr)).cdr;
113       }
114     else
115       {
116         if (xpos == null)
117           next = sequence;
118         else
119           next = ((Pair) xpos).cdr;
120       }
121     if (next == LList.Empty)
122       return null;
123     return (Pair) next;
124   }
125 
126   public Object   getNext ()
127   {
128     Pair pair = getNextPair();
129     return pair == null ? LList.eofValue : pair.car;
130   }
131 
132   public void setNext (Object   value)
133   {
134     Pair pair = getNextPair();
135     pair.car = value;
136   }
137 
138   /** Get the Pair whose car contains the previous element, or null. */
139   public Pair getPreviousPair ()
140   {
141     int isAfter = (ipos & 1);
142     Object   p = xpos;
143     if (isAfter > 0)
144       p = p == null ? sequence : ((Pair) p).cdr;
145     else if (p == null)
146       return null;
147     if (p == LList.Empty)
148       return null;
149     return (Pair) p;
150   }
151 
152   public Object   getPrevious ()
153   {
154     Pair pair = getPreviousPair();
155     return pair == null ? LList.eofValue : pair.car;
156   }
157 
158   public void setPrevious (Object   value)
159   {
160     Pair pair = getPreviousPair();
161     pair.car = value;
162   }
163 
164   public int nextIndex ()
165   {
166     return ipos >> 1;
167   }
168 
169   public boolean gotoNext()
170   {
171     boolean isAfter = (ipos & 1) != 0;
172     int old_i = ipos;
173     Object   xp = xpos;
174     if (xp != null)
175       {
176     if (isAfter)
177       xp = ((Pair) xp).cdr;
178     if (((Pair) xp).cdr == LList.Empty)
179       return false;
180     xpos = xp;
181     ipos = (ipos | 1) + 2;
182       }
183     else if ((ipos >> 1) == 0) // position is 0
184       {
185     if (sequence == LList.Empty)
186       return false;
187     ipos = (1 << 1) | 1;
188       }
189     else // position is 1, iAfter must be true
190       {
191     xp = sequence;
192     if (((Pair) xp).cdr == LList.Empty)
193       return false;
194     ipos = (2 << 1) | 1;
195     xpos = xp;
196       }
197     return true;
198   }
199 
200   public boolean gotoPrevious()
201   {
202     if (ipos >>> 1 == 0)
203       return false;
204     if ((ipos & 1) != 0) // isAfter()
205       {
206     // Decrement index; clear isAfter bit.
207     ipos -= 3;
208     return true;
209       }
210     int index = nextIndex();
211     set((LList) sequence, index - 1, false);
212     return true;
213   }
214 
215   public String   toString()
216   {
217     StringBuffer   sbuf = new StringBuffer  ();
218     sbuf.append("LListPos[");
219     //sbuf.append(super.toString());
220     sbuf.append("index:");
221     sbuf.append(ipos);
222     if (isAfter())
223       sbuf.append(" after");
224     if (position >= 0)
225       {
226     sbuf.append(" position:");
227     sbuf.append(position);
228       }
229     sbuf.append(']');
230     return sbuf.toString();
231   }
232 }
233
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags