Java/Collections Data Structure/History
History management
<source lang="java">
/*
* Copyright (c) 1998-2002 Carnegie Mellon University. All rights * reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * THIS SOFTWARE IS PROVIDED BY CARNEGIE MELLON UNIVERSITY ``AS IS"" AND * ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY * NOR ITS EMPLOYEES BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * */
import java.util.Enumeration; public class History {
protected Object[] history; // array of history objects (arranged as // a circular queue) protected int start; // points to oldest object in history protected int end; // points after newest object in history protected int curr; // points to current object; // either start <= curr < end (modulo history.length) // or start == curr == end /** * Make a History. * @param max Maximum length of history */ public History (int max) { history = new Object[max+1]; start = end = curr = 0; } /** * Make a duplicate of another History. * @param h History to copy */ public History (History h) { this.history = new Object[h.history.length]; System.arraycopy (h.history, 0, this.history, 0, h.history.length); this.start = h.start; this.end = h.end; this.curr = h.curr; } /** * Clear the history. */ public void clear () { for (int i = 0; i < history.length; ++i) history[i] = null; int s = start; int e = end; start = end = curr = 0; if (s != e) fireRemoved (s, (e > 0) ? e-1 : history.length-1); } /** * Double the capacity of the history. */ public void expand () { Object[] newHistory = new Object[(history.length * 2) - 1]; int i = 0; int newCurr = 0; for (int j = start; j != end; j = (j+1) % history.length, ++i) { newHistory[i] = history[j]; if (j == curr) newCurr = i; } history = newHistory; start = 0; end = i; curr = newCurr; } /** * Add an object to the history after the current point (deleting all * objects forward of this point). If history overflows, the oldest * object is thrown away. * @param obj Object to add to history */ public void put (Object obj) { if (!isEmpty ()) { // throw away all objects after curr int newEnd = (curr+1) % history.length; if (newEnd != end) { int e = end; end = newEnd; fireRemoved (newEnd, (e > 0) ? e-1 : history.length-1); } } add (obj); } /** * Add an object to the end of the history, moving the current point to it. * If history overflows, the oldest object is thrown away. * @param obj Object to add to history */ public void add (Object obj) { if (isFull ()) { // throw away oldest object to make room start = (start+1) % history.length; fireRemoved (start, start); } // insert the new object at end history[end] = obj; curr = end; end = (end+1) % history.length; fireAdded (curr, curr); System.out.println("after put: start=" + start + ", end=" + end + ", curr=" + curr); } /** * Get the current object of the history. * @return current object of history, or null if history is empty. */ public Object get () { return !isEmpty () ? history[curr] : null; } /** * Get the object that would be returned by back(), without actually * changing the current object. * @return object before current object, or null if at beginning of * history or history is empty. */ public Object peekBack () { if (curr == start) return null; else { int bk = (curr > 0) ? curr-1 : history.length-1; return history[bk]; } } /** * Get the object that would be returned by forward(), without actually * changing the current object. * @return object after current object, or null if at end of * history or history is empty. */ public Object peekForward () { if (start == end) return null; int fw = (curr+1) % history.length; if (fw == end) return null; else return history[fw]; } /** * Replace the current object of the history. The rest of the history * is unaffected, and the current pointer stays where it is.*
If the history is empty, * then this call is equivalent to put(obj). * @param obj object to substitute */ public void replace (Object obj) { if (isEmpty ()) put (obj); else { history[curr] = obj; fireChanged (curr, curr); } } /** * Move back one object in the history, if possible. * @return previous object in the history, or null if at start. */ public Object back () { if (curr == start) return null; else { curr = (curr > 0) ? curr-1 : history.length-1; fireChanged (curr, curr); return history[curr]; } } /** * Move forward one object in the history, if possible. * @return next object in the history, or null if at end of history. */ public Object forward () { if (start == end) return null; int newCurr = (curr+1) % history.length; if (newCurr == end) return null; else { curr = newCurr; fireChanged (curr, curr); return history[curr]; } } /** * Move to first (oldest) object in the history, if possible. * @return first object in the history, or null if history empty. */ public Object toStart () { if (curr != start) { curr = start; fireChanged (curr, curr); } return history[curr]; } /** * Move to last (newest) object in the history, if possible. * @return last object in the history, or null if history empty. */ public Object toEnd () { if (start == end) return null; int newCurr = (end > 0) ? end-1 : history.length-1; if (curr != newCurr) { curr = newCurr; fireChanged (curr, curr); } return history[curr]; } /** * Test whether back() will succeed. * @return true if and only if there are objects before the current object */ public boolean canBack () { return (curr != start); } /** * Test whether forward() will succeed. * @return true if and only if there are objects after the current object */ public boolean canForward () { return ((curr+1) % history.length != end); } /** * Test whether history is empty. * @return true if and only if history contains no objects */ public boolean isEmpty () { return start == end; } /** * Test whether history is full. * @return true if and only if history contains max objects */ public boolean isFull () { return start == (end+1) % history.length; } /** * Test whether history already contains an object. * @param obj Object to search for * @return true if and only if history contains an object that equals() obj */ public boolean contains (Object obj) { for (int i = start; i != end; i = (i+1) % history.length) if (history[i].equals (obj)) return true; return false; } /** * Get the objects in the history. * @returns enumeration yielding the history objects in order from * oldest to newest. */ public Enumeration elements () { return new HistoryEnumeration (start, end); } /** * Get the objects AFTER the current object. * @returns enumeration yielding the history objects after current, * in order from oldest to newest. */ public Enumeration forwardElements () { return (curr == end) ? new HistoryEnumeration (curr, end) : new HistoryEnumeration ((curr + 1) % history.length, end); } /** * Get the objects BEFORE the current object. * @returns enumeration yielding the history objects before current, * in order from oldest to newest. */ public Enumeration backElements () { return new HistoryEnumeration (start, curr); } class HistoryEnumeration implements Enumeration { int p; int e; public HistoryEnumeration (int start, int end) { p = start; e = end; } public boolean hasMoreElements () { return p != e; } public Object nextElement () { Object obj = history[p]; p = (p+1) % history.length; return obj; } } protected void fireRemoved (int i, int j) { } protected void fireAdded (int i, int j) { } protected void fireChanged (int i, int j) { } } </source>