History


1   /*
2    * Copyright (c) 1998-2002 Carnegie Mellon University.  All rights
3    * reserved.
4    *
5    * Redistribution and use in source and binary forms, with or without
6    * modification, are permitted provided that the following conditions
7    * are met:
8    *
9    * 1. Redistributions of source code must retain the above copyright
10   *    notice, this list of conditions and the following disclaimer.
11   *
12   * 2. Redistributions in binary form must reproduce the above copyright
13   *    notice, this list of conditions and the following disclaimer in
14   *    the documentation and/or other materials provided with the
15   *    distribution.
16   *
17   * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS'' AND
18   * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
19   * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20   * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY
21   * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23   * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24   * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25   * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28   *
29   */
30  
31  package rcm.util;
32  
33  import java.util.Enumeration  ;
34  
35  public class History {
36      public static rcm.util.Debug debug = rcm.util.Debug.QUIET;
37      
38      protected Object  [] history;   // array of history objects (arranged as
39                          // a circular queue)
40      protected int start;      // points to oldest object in history
41      protected int end;        // points after newest object in history
42      protected int curr;       // points to current object;
43                      // either start <= curr < end (modulo history.length)
44                      // or start == curr == end
45  
46      /**
47       * Make a History.
48       * @param   max     Maximum length of history
49       */
50      public History (int max) {
51          history = new Object  [max+1];
52          start = end = curr = 0;
53      }
54  
55      /**
56       * Make a duplicate of another History.
57       * @param   h History to copy
58       */
59      public History (History h) {
60          this.history = new Object  [h.history.length];
61          System.arraycopy (h.history, 0, this.history, 0, h.history.length);
62          this.start = h.start;
63          this.end = h.end;
64          this.curr = h.curr;
65      }
66  
67      /**
68       * Clear the history.
69       */
70      public void clear () {
71          for (int i = 0; i < history.length; ++i)
72              history[i] = null;
73  
74          int s = start;
75          int e = end;
76          start = end = curr = 0;
77  
78          if (s != e)
79              fireRemoved (s, (e > 0) ? e-1 : history.length-1);
80      }
81  
82      /**
83       * Double the capacity of the history.
84       */
85      public void expand () {
86          Object  [] newHistory = new Object  [(history.length * 2) - 1];
87          int i = 0;
88          int newCurr = 0;
89          for (int j = start; j != end; j = (j+1) % history.length, ++i) {
90              newHistory[i] = history[j];
91              if (j == curr)
92                  newCurr = i;
93          }
94          history = newHistory;
95          start = 0;
96          end = i;
97          curr = newCurr;
98      }
99  
100     /**
101      * Add an object to the history after the current point (deleting all
102      * objects forward of this point).  If history overflows, the oldest
103      * object is thrown away.
104      * @param obj   Object to add to history
105      */
106     public void put (Object   obj) {
107         if (!isEmpty ()) {
108             // throw away all objects after curr
109             int newEnd = (curr+1) % history.length;
110             if (newEnd != end) {
111                 int e = end;
112                 end = newEnd;
113                 fireRemoved (newEnd, (e > 0) ? e-1 : history.length-1);
114             }
115         }
116 
117         add (obj);
118     }
119 
120     /**
121      * Add an object to the end of the history, moving the current point to it.
122      * If history overflows, the oldest object is thrown away.
123      * @param obj   Object to add to history
124      */
125     public void add (Object   obj) {
126         if (isFull ()) {
127             // throw away oldest object to make room
128             start = (start+1) % history.length;
129             fireRemoved (start, start);
130         }
131 
132         // insert the new object at end
133         history[end] = obj;
134         curr = end;
135         end = (end+1) % history.length;
136         fireAdded (curr, curr);
137 
138         debug.println ("after put: start=" + start + ", end=" + end + ", curr=" + curr);
139     }
140 
141     /**
142      * Get the current object of the history.
143      * @return current object of history, or null if history is empty.
144      */
145     public Object   get () {
146         return !isEmpty () ? history[curr] : null;
147     }
148 
149     /**
150      * Get the object that would be returned by back(), without actually
151      * changing the current object.
152      * @return object before current object, or null if at beginning of 
153      * history or history is empty.
154      */
155     public Object   peekBack () {
156         if (curr == start)
157             return null;
158         else {
159             int bk = (curr > 0) ? curr-1 : history.length-1;
160             return history[bk];
161         }
162     }
163 
164     /**
165      * Get the object that would be returned by forward(), without actually
166      * changing the current object.
167      * @return object after current object, or null if at end of 
168      * history or history is empty.
169      */
170     public Object   peekForward () {
171         if (start == end)
172             return null;
173 
174         int fw = (curr+1) % history.length;
175         if (fw == end)
176             return null;
177         else 
178             return history[fw];
179     }
180 
181     /**
182      * Replace the current object of the history. The rest of the history
183      * is unaffected, and the current pointer stays where it is.
184      * <P> If the history is empty,
185      * then this call is equivalent to put(obj).
186      * @param obj object to substitute
187      */
188     public void replace (Object   obj) {
189         if (isEmpty ())
190             put (obj);
191         else {
192             history[curr] = obj;
193             fireChanged (curr, curr);
194         }
195     }
196 
197     /**
198      * Move back one object in the history, if possible.
199      * @return previous object in the history, or null if at start.
200      */
201     public Object   back () {
202         if (curr == start)
203             return null;
204         else {
205             curr = (curr > 0) ? curr-1 : history.length-1;
206             fireChanged (curr, curr);
207             return history[curr];
208         }
209     }
210 
211     /**
212      * Move forward one object in the history, if possible.
213      * @return next object in the history, or null if at end of history.
214      */
215     public Object   forward () {
216         if (start == end)
217             return null;
218 
219         int newCurr = (curr+1) % history.length;
220         if (newCurr == end)
221             return null;
222         else {
223             curr = newCurr;
224             fireChanged (curr, curr);
225             return history[curr];
226         }
227     }
228 
229     /**
230      * Move to first (oldest) object in the history, if possible.
231      * @return first object in the history, or null if history empty.
232      */
233     public Object   toStart () {
234         if (curr != start) {
235             curr = start;
236             fireChanged (curr, curr);
237         }
238         return history[curr];
239     }
240 
241     /**
242      * Move to last (newest) object in the history, if possible.
243      * @return last object in the history, or null if history empty.
244      */
245     public Object   toEnd () {
246         if (start == end)
247             return null;
248         int newCurr = (end > 0) ? end-1 : history.length-1;
249         if (curr != newCurr) {
250             curr = newCurr;
251             fireChanged (curr, curr);
252         }
253         return history[curr];
254     }
255 
256     /**
257      * Test whether back() will succeed.
258      * @return true if and only if there are objects before the current object
259      */
260     public boolean canBack () {
261         return (curr != start);
262     }
263 
264     /**
265      * Test whether forward() will succeed.
266      * @return true if and only if there are objects after the current object
267      */
268     public boolean canForward () {
269         return ((curr+1) % history.length != end);
270     }
271 
272     /**
273      * Test whether history is empty.
274      * @return true if and only if history contains no objects
275      */
276     public boolean isEmpty () {
277         return start == end;
278     }
279 
280     /**
281      * Test whether history is full.
282      * @return true if and only if history contains max objects
283      */
284     public boolean isFull () {
285         return start == (end+1) % history.length;
286     }
287 
288     /**
289      * Test whether history already contains an object.
290      * @param obj   Object to search for
291      * @return true if and only if history contains an object that equals() obj
292      */
293     public boolean contains (Object   obj) {
294         for (int i = start; i != end; i = (i+1) % history.length)
295             if (history[i].equals (obj))
296                 return true;
297         return false;
298     }
299 
300     /**
301      * Get the objects in the history.
302      * @returns enumeration yielding the history objects in order from
303      * oldest to newest.
304      */
305     public Enumeration   elements () {
306         return new HistoryEnumeration (start, end);
307     }
308 
309     /**
310      * Get the objects AFTER the current object.
311      * @returns enumeration yielding the history objects after current,
312      * in order from oldest to newest.
313      */
314     public Enumeration   forwardElements () {
315         return 
316             (curr == end)
317             ? new HistoryEnumeration (curr, end)
318             : new HistoryEnumeration ((curr + 1) % history.length, end);
319     }
320 
321     /**
322      * Get the objects BEFORE the current object.
323      * @returns enumeration yielding the history objects before current,
324      * in order from oldest to newest.
325      */
326     public Enumeration   backElements () {
327         return new HistoryEnumeration (start, curr);
328     }
329 
330     class HistoryEnumeration implements Enumeration   {
331         int p;
332         int e;
333 
334         public HistoryEnumeration (int start, int end) {
335             p = start;
336             e = end;
337         }
338 
339         public boolean hasMoreElements () {
340             return p != e;
341         }
342 
343         public Object   nextElement () {
344             Object   obj = history[p];
345             p = (p+1) % history.length;
346             return obj;
347         }
348     }
349 
350     protected void fireRemoved (int i, int j) {
351     }
352     
353     protected void fireAdded (int i, int j) {
354     }
355     
356     protected void fireChanged (int i, int j) {
357     }
358 }
359
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags