Java/Collections Data Structure/History
History management
/*
* 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.
* <P> 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) {
}
}
