001 /*
002 * LAPIS lightweight structured text processing system
003 *
004 * Copyright (C) 1998-2002 Carnegie Mellon University,
005 * Copyright (C) 2003 Massachusetts Institute of Technology.
006 * All rights reserved.
007 *
008 * This library is free software; you can redistribute it
009 * and/or modify it under the terms of the GNU General
010 * Public License as published by the Free Software
011 * Foundation, version 2.
012 *
013 * LAPIS homepage: http://graphics.lcs.mit.edu/lapis/
014 */
015
016
017 package lapisx.util;
018
019 import java.util.Enumeration;
020 import java.util.NoSuchElementException;
021
022 /**
023 * A History is a list of objects with a current object.
024 * One application of History is a browser history, in which
025 * the objects are web pages and one page is currently displayed.
026 * <p>
027 * A History has a finite maximum size. When adding an object would exceed
028 * the maximum size, the oldest object is removed. The maximum size can
029 * be increased with {@link #expand}.
030 */
031 public class History {
032 /**
033 * Array of history objects, arranged as circular queue.
034 */
035 protected Object[] history;
036
037 /**
038 * Index of oldest object in history.
039 */
040 protected int start;
041
042 /**
043 * Index <i>after</i> newest object in history.
044 */
045 protected int end;
046
047 /**
048 * Index of current object. If history is empty, then
049 * curr == start == end.
050 */
051 protected int curr;
052
053 /**
054 * Make a History.
055 * @param max Maximum length of history
056 */
057 public History (int max) {
058 history = new Object[max+1];
059 start = end = curr = 0;
060 }
061
062 /**
063 * Make a duplicate of another History.
064 * @param h History to copy
065 */
066 public History (History h) {
067 this.history = new Object[h.history.length];
068 System.arraycopy (h.history, 0, this.history, 0, h.history.length);
069 this.start = h.start;
070 this.end = h.end;
071 this.curr = h.curr;
072 }
073
074 /**
075 * Clear the history.
076 */
077 public void clear () {
078 for (int i = 0; i < history.length; ++i)
079 history[i] = null;
080
081 int s = start;
082 int e = end;
083 start = end = curr = 0;
084
085 if (s != e)
086 fireRemoved (s, (e > 0) ? e-1 : history.length-1);
087 }
088
089 /**
090 * Double the capacity of the history.
091 */
092 public void expand () {
093 Object[] newHistory = new Object[(history.length * 2) - 1];
094 int i = 0;
095 int newCurr = 0;
096 for (int j = start; j != end; j = (j+1) % history.length, ++i) {
097 newHistory[i] = history[j];
098 if (j == curr)
099 newCurr = i;
100 }
101 history = newHistory;
102 start = 0;
103 end = i;
104 curr = newCurr;
105 }
106
107 /**
108 * Add an object to the history after the current point (deleting all
109 * objects forward of this point). If history overflows, the oldest
110 * object is thrown away.
111 * @param obj Object to add to history
112 */
113 public void put (Object obj) {
114 if (!isEmpty ()) {
115 // throw away all objects after curr
116 int newEnd = (curr+1) % history.length;
117 if (newEnd != end) {
118 int e = end;
119 end = newEnd;
120 fireRemoved (newEnd, (e > 0) ? e-1 : history.length-1);
121 }
122 }
123
124 add (obj);
125 }
126
127 /**
128 * Add an object to the end of the history, moving the current point to it.
129 * If history overflows, the oldest object is thrown away.
130 * @param obj Object to add to history
131 */
132 public void add (Object obj) {
133 if (isFull ()) {
134 // throw away oldest object to make room
135 start = (start+1) % history.length;
136 fireRemoved (start, start);
137 }
138
139 // insert the new object at end
140 history[end] = obj;
141 curr = end;
142 end = (end+1) % history.length;
143 fireAdded (curr, curr);
144 }
145
146 /**
147 * Get the current object of the history.
148 * @return current object of history, or null if history is empty.
149 */
150 public Object get () {
151 return !isEmpty () ? history[curr] : null;
152 }
153
154 /**
155 * Set the current object of the history.
156 * @param obj Object that should be the new current object.
157 * @throws NoSuchElementException if this doesn't contain obj.
158 */
159 public void jumpTo (Object obj) {
160 for (int i = start; i != end; i = (i+1) % history.length)
161 if (history[i].equals (obj)) {
162 curr = i;
163 fireChanged (curr, curr);
164 return;
165 }
166 throw new NoSuchElementException ();
167 }
168
169 /**
170 * Get the object that would be returned by back(), without actually
171 * changing the current object.
172 * @return object before current object, or null if at beginning of
173 * history or history is empty.
174 */
175 public Object peekBack () {
176 if (curr == start)
177 return null;
178 else {
179 int bk = (curr > 0) ? curr-1 : history.length-1;
180 return history[bk];
181 }
182 }
183
184 /**
185 * Get the object that would be returned by forward(), without actually
186 * changing the current object.
187 * @return object after current object, or null if at end of
188 * history or history is empty.
189 */
190 public Object peekForward () {
191 if (isEmpty ())
192 return null;
193
194 int fw = (curr+1) % history.length;
195 if (fw == end)
196 return null;
197 else
198 return history[fw];
199 }
200
201 /**
202 * Replace the current object of the history. The rest of the history
203 * is unaffected, and the current pointer stays where it is.
204 * <P> If the history is empty,
205 * then this call is equivalent to put(obj).
206 * @param obj object to substitute
207 */
208 public void replace (Object obj) {
209 if (isEmpty ())
210 put (obj);
211 else {
212 history[curr] = obj;
213 fireChanged (curr, curr);
214 }
215 }
216
217 /**
218 * Move back one object in the history, if possible.
219 * @return previous object in the history, or null if at start.
220 */
221 public Object back () {
222 if (curr == start)
223 return null;
224 else {
225 curr = (curr > 0) ? curr-1 : history.length-1;
226 fireChanged (curr, curr);
227 return history[curr];
228 }
229 }
230
231 /**
232 * Move forward one object in the history, if possible.
233 * @return next object in the history, or null if at end of history.
234 */
235 public Object forward () {
236 if (isEmpty ())
237 return null;
238
239 int newCurr = (curr+1) % history.length;
240 if (newCurr == end)
241 return null;
242 else {
243 curr = newCurr;
244 fireChanged (curr, curr);
245 return history[curr];
246 }
247 }
248
249 /**
250 * Move to first (oldest) object in the history, if possible.
251 * @return first object in the history, or null if history empty.
252 */
253 public Object toStart () {
254 if (curr != start) {
255 curr = start;
256 fireChanged (curr, curr);
257 }
258 return history[curr];
259 }
260
261 /**
262 * Move to last (newest) object in the history, if possible.
263 * @return last object in the history, or null if history empty.
264 */
265 public Object toEnd () {
266 if (isEmpty ())
267 return null;
268 int newCurr = (end > 0) ? end-1 : history.length-1;
269 if (curr != newCurr) {
270 curr = newCurr;
271 fireChanged (curr, curr);
272 }
273 return history[curr];
274 }
275
276 /**
277 * Test whether back() will succeed.
278 * @return true if and only if there are objects before the current object
279 */
280 public boolean canBack () {
281 return (curr != start);
282 }
283
284 /**
285 * Test whether forward() will succeed.
286 * @return true if and only if there are objects after the current object
287 */
288 public boolean canForward () {
289 return !isEmpty () && ((curr+1) % history.length != end);
290 }
291
292 /**
293 * Get number of objects currently in history.
294 * @return number of objects that would be returned by elements().
295 */
296 public int size () {
297 return ((end + history.length) - start) % history.length;
298 }
299
300 /**
301 * Test whether history is empty.
302 * @return true if and only if history contains no objects
303 */
304 public boolean isEmpty () {
305 return start == end;
306 }
307
308 /**
309 * Test whether history is full.
310 * @return true if and only if history contains max objects
311 */
312 public boolean isFull () {
313 return start == (end+1) % history.length;
314 }
315
316 /**
317 * Test whether history already contains an object.
318 * @param obj Object to search for
319 * @return true if and only if history contains an object that equals() obj
320 */
321 public boolean contains (Object obj) {
322 for (int i = start; i != end; i = (i+1) % history.length)
323 if (history[i].equals (obj))
324 return true;
325 return false;
326 }
327
328 /**
329 * Get the objects in the history.
330 * enumeration yielding the history objects in order from
331 * oldest to newest.
332 */
333 public Enumeration elements () {
334 return new HistoryEnumeration (start, end);
335 }
336
337 /**
338 * Get the objects AFTER the current object.
339 * enumeration yielding the history objects after current,
340 * in order from oldest to newest.
341 */
342 public Enumeration forwardElements () {
343 return
344 (curr == end)
345 ? new HistoryEnumeration (curr, end)
346 : new HistoryEnumeration ((curr + 1) % history.length, end);
347 }
348
349 /**
350 * Get the objects BEFORE the current object.
351 * enumeration yielding the history objects before current,
352 * in order from oldest to newest.
353 */
354 public Enumeration backElements () {
355 return new HistoryEnumeration (start, curr);
356 }
357
358 class HistoryEnumeration implements Enumeration {
359 int p;
360 int e;
361
362 public HistoryEnumeration (int start, int end) {
363 p = start;
364 e = end;
365 }
366
367 public boolean hasMoreElements () {
368 return p != e;
369 }
370
371 public Object nextElement () {
372 Object obj = history[p];
373 p = (p+1) % history.length;
374 return obj;
375 }
376 }
377
378 /**
379 * Called when history[i..j] is removed. Used by subclasses
380 * that need to generate events.
381 * Default implementation does nothing.
382 * @param i index of first removed element
383 * @param j index of last removed element
384 */
385 protected void fireRemoved (int i, int j) {
386 }
387
388 /**
389 * Called when new elements are added at history[i..j].
390 * Used by subclasses that need to generate events.
391 * Default implementation does nothing.
392 * @param i index of first added element
393 * @param j index of last added element
394 */
395 protected void fireAdded (int i, int j) {
396 }
397
398 /**
399 * Called when elements at history[i..j] are replaced.
400 * Also called when history[i] becomes the current element
401 * (in which case i == j).
402 * Used by subclasses that need to generate events.
403 * Default implementation does nothing.
404 * @param i index of first changed element
405 * @param j index of last changed element
406 */
407 protected void fireChanged (int i, int j) {
408 }
409 }