001: /*
002: * Copyright (c) 1998-2002 Carnegie Mellon University. All rights
003: * reserved.
004: *
005: * Redistribution and use in source and binary forms, with or without
006: * modification, are permitted provided that the following conditions
007: * are met:
008: *
009: * 1. Redistributions of source code must retain the above copyright
010: * notice, this list of conditions and the following disclaimer.
011: *
012: * 2. Redistributions in binary form must reproduce the above copyright
013: * notice, this list of conditions and the following disclaimer in
014: * the documentation and/or other materials provided with the
015: * distribution.
016: *
017: * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
018: * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
019: * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
020: * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
021: * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
022: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
023: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
024: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
025: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
026: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
027: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028: *
029: */
030:
031: package rcm.util;
032:
033: import java.util.Enumeration;
034:
035: public class History {
036: public static rcm.util.Debug debug = rcm.util.Debug.QUIET;
037:
038: protected Object[] history; // array of history objects (arranged as
039: // a circular queue)
040: protected int start; // points to oldest object in history
041: protected int end; // points after newest object in history
042: protected int curr; // points to current object;
043:
044: // either start <= curr < end (modulo history.length)
045: // or start == curr == end
046:
047: /**
048: * Make a History.
049: * @param max Maximum length of history
050: */
051: public History(int max) {
052: history = new Object[max + 1];
053: start = end = curr = 0;
054: }
055:
056: /**
057: * Make a duplicate of another History.
058: * @param h History to copy
059: */
060: public History(History h) {
061: this .history = new Object[h.history.length];
062: System.arraycopy(h.history, 0, this .history, 0,
063: h.history.length);
064: this .start = h.start;
065: this .end = h.end;
066: this .curr = h.curr;
067: }
068:
069: /**
070: * Clear the history.
071: */
072: public void clear() {
073: for (int i = 0; i < history.length; ++i)
074: history[i] = null;
075:
076: int s = start;
077: int e = end;
078: start = end = curr = 0;
079:
080: if (s != e)
081: fireRemoved(s, (e > 0) ? e - 1 : history.length - 1);
082: }
083:
084: /**
085: * Double the capacity of the history.
086: */
087: public void expand() {
088: Object[] newHistory = new Object[(history.length * 2) - 1];
089: int i = 0;
090: int newCurr = 0;
091: for (int j = start; j != end; j = (j + 1) % history.length, ++i) {
092: newHistory[i] = history[j];
093: if (j == curr)
094: newCurr = i;
095: }
096: history = newHistory;
097: start = 0;
098: end = i;
099: curr = newCurr;
100: }
101:
102: /**
103: * Add an object to the history after the current point (deleting all
104: * objects forward of this point). If history overflows, the oldest
105: * object is thrown away.
106: * @param obj Object to add to history
107: */
108: public void put(Object obj) {
109: if (!isEmpty()) {
110: // throw away all objects after curr
111: int newEnd = (curr + 1) % history.length;
112: if (newEnd != end) {
113: int e = end;
114: end = newEnd;
115: fireRemoved(newEnd, (e > 0) ? e - 1
116: : history.length - 1);
117: }
118: }
119:
120: add(obj);
121: }
122:
123: /**
124: * Add an object to the end of the history, moving the current point to it.
125: * If history overflows, the oldest object is thrown away.
126: * @param obj Object to add to history
127: */
128: public void add(Object obj) {
129: if (isFull()) {
130: // throw away oldest object to make room
131: start = (start + 1) % history.length;
132: fireRemoved(start, start);
133: }
134:
135: // insert the new object at end
136: history[end] = obj;
137: curr = end;
138: end = (end + 1) % history.length;
139: fireAdded(curr, curr);
140:
141: debug.println("after put: start=" + start + ", end=" + end
142: + ", curr=" + curr);
143: }
144:
145: /**
146: * Get the current object of the history.
147: * @return current object of history, or null if history is empty.
148: */
149: public Object get() {
150: return !isEmpty() ? history[curr] : null;
151: }
152:
153: /**
154: * Get the object that would be returned by back(), without actually
155: * changing the current object.
156: * @return object before current object, or null if at beginning of
157: * history or history is empty.
158: */
159: public Object peekBack() {
160: if (curr == start)
161: return null;
162: else {
163: int bk = (curr > 0) ? curr - 1 : history.length - 1;
164: return history[bk];
165: }
166: }
167:
168: /**
169: * Get the object that would be returned by forward(), without actually
170: * changing the current object.
171: * @return object after current object, or null if at end of
172: * history or history is empty.
173: */
174: public Object peekForward() {
175: if (start == end)
176: return null;
177:
178: int fw = (curr + 1) % history.length;
179: if (fw == end)
180: return null;
181: else
182: return history[fw];
183: }
184:
185: /**
186: * Replace the current object of the history. The rest of the history
187: * is unaffected, and the current pointer stays where it is.
188: * <P> If the history is empty,
189: * then this call is equivalent to put(obj).
190: * @param obj object to substitute
191: */
192: public void replace(Object obj) {
193: if (isEmpty())
194: put(obj);
195: else {
196: history[curr] = obj;
197: fireChanged(curr, curr);
198: }
199: }
200:
201: /**
202: * Move back one object in the history, if possible.
203: * @return previous object in the history, or null if at start.
204: */
205: public Object back() {
206: if (curr == start)
207: return null;
208: else {
209: curr = (curr > 0) ? curr - 1 : history.length - 1;
210: fireChanged(curr, curr);
211: return history[curr];
212: }
213: }
214:
215: /**
216: * Move forward one object in the history, if possible.
217: * @return next object in the history, or null if at end of history.
218: */
219: public Object forward() {
220: if (start == end)
221: return null;
222:
223: int newCurr = (curr + 1) % history.length;
224: if (newCurr == end)
225: return null;
226: else {
227: curr = newCurr;
228: fireChanged(curr, curr);
229: return history[curr];
230: }
231: }
232:
233: /**
234: * Move to first (oldest) object in the history, if possible.
235: * @return first object in the history, or null if history empty.
236: */
237: public Object toStart() {
238: if (curr != start) {
239: curr = start;
240: fireChanged(curr, curr);
241: }
242: return history[curr];
243: }
244:
245: /**
246: * Move to last (newest) object in the history, if possible.
247: * @return last object in the history, or null if history empty.
248: */
249: public Object toEnd() {
250: if (start == end)
251: return null;
252: int newCurr = (end > 0) ? end - 1 : history.length - 1;
253: if (curr != newCurr) {
254: curr = newCurr;
255: fireChanged(curr, curr);
256: }
257: return history[curr];
258: }
259:
260: /**
261: * Test whether back() will succeed.
262: * @return true if and only if there are objects before the current object
263: */
264: public boolean canBack() {
265: return (curr != start);
266: }
267:
268: /**
269: * Test whether forward() will succeed.
270: * @return true if and only if there are objects after the current object
271: */
272: public boolean canForward() {
273: return ((curr + 1) % history.length != end);
274: }
275:
276: /**
277: * Test whether history is empty.
278: * @return true if and only if history contains no objects
279: */
280: public boolean isEmpty() {
281: return start == end;
282: }
283:
284: /**
285: * Test whether history is full.
286: * @return true if and only if history contains max objects
287: */
288: public boolean isFull() {
289: return start == (end + 1) % history.length;
290: }
291:
292: /**
293: * Test whether history already contains an object.
294: * @param obj Object to search for
295: * @return true if and only if history contains an object that equals() obj
296: */
297: public boolean contains(Object obj) {
298: for (int i = start; i != end; i = (i + 1) % history.length)
299: if (history[i].equals(obj))
300: return true;
301: return false;
302: }
303:
304: /**
305: * Get the objects in the history.
306: * @returns enumeration yielding the history objects in order from
307: * oldest to newest.
308: */
309: public Enumeration elements() {
310: return new HistoryEnumeration(start, end);
311: }
312:
313: /**
314: * Get the objects AFTER the current object.
315: * @returns enumeration yielding the history objects after current,
316: * in order from oldest to newest.
317: */
318: public Enumeration forwardElements() {
319: return (curr == end) ? new HistoryEnumeration(curr, end)
320: : new HistoryEnumeration((curr + 1) % history.length,
321: end);
322: }
323:
324: /**
325: * Get the objects BEFORE the current object.
326: * @returns enumeration yielding the history objects before current,
327: * in order from oldest to newest.
328: */
329: public Enumeration backElements() {
330: return new HistoryEnumeration(start, curr);
331: }
332:
333: class HistoryEnumeration implements Enumeration {
334: int p;
335: int e;
336:
337: public HistoryEnumeration(int start, int end) {
338: p = start;
339: e = end;
340: }
341:
342: public boolean hasMoreElements() {
343: return p != e;
344: }
345:
346: public Object nextElement() {
347: Object obj = history[p];
348: p = (p + 1) % history.length;
349: return obj;
350: }
351: }
352:
353: protected void fireRemoved(int i, int j) {
354: }
355:
356: protected void fireAdded(int i, int j) {
357: }
358:
359: protected void fireChanged(int i, int j) {
360: }
361: }
|