Skip to content

Instantly share code, notes, and snippets.

@hyamamoto
Last active December 18, 2015 15:19
Show Gist options
  • Save hyamamoto/5803171 to your computer and use it in GitHub Desktop.
Save hyamamoto/5803171 to your computer and use it in GitHub Desktop.
Over-engineered navigation queue. (Data structure for history token management)
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class NavigationQueue<E> {
private class NavigationQueueIterator<T> implements Iterator<T> {
private int op;
private int limit;
public NavigationQueueIterator( int from, int to) {
this.op = from;
this.limit = to;
}
@Override
public boolean hasNext() {
return op != limit;
}
@Override
public T next() {
@SuppressWarnings( "unchecked")
final T obj = ( T) tokens[op];
op = (op + 1) % tokens.length;
return obj;
}
@Override
public void remove() {
throw new UnsupportedOperationException(); // TODO: implement
}
}
private interface NavigationQueueListener<T> {
public void onRemove( NavigationQueue<T> q, int from, int to);
public void onAdd( NavigationQueue<T> q, int from, int to);
public void onChange( NavigationQueue<T> q, int from, int to);
}
private List<NavigationQueueListener<E>> listeners = new ArrayList<NavigationQueueListener<E>>();
private Object[] tokens;
private int start;
private int end;
private int current;
public NavigationQueue( int size) {
tokens = new Object[size + 1];
start = end = current = 0;
}
protected final void fireOnRemove( int from, int to) {
for ( NavigationQueueListener<E> l : listeners)
l.onRemove( this, from, to);
}
protected final void fireOnAdd( int from, int to) {
for ( NavigationQueueListener<E> l : listeners)
l.onAdd( this, from, to);
}
protected final void fireOnChange( int from, int to) {
for ( NavigationQueueListener<E> l : listeners)
l.onChange( this, from, to);
}
public NavigationQueue<E> addListener( NavigationQueueListener<E> listener) {
if ( listener == null)
throw new IllegalArgumentException( "listener == null");
return this;
}
public boolean removeListener( NavigationQueueListener<E> listener) {
return listener != null && listeners.remove( listener);
}
public NavigationQueue<E> clear() {
for ( int i = 0; i < tokens.length; ++i)
tokens[i] = null;
final int oldStart = start;
final int oldEnd = end;
start = end = current = 0;
if ( oldStart != oldEnd)
fireOnRemove( oldStart, (oldEnd > 0) ? oldEnd - 1 : tokens.length - 1);
return this;
}
public NavigationQueue<E> put( E obj) {
if ( !isEmpty()) {
final int newE = (current + 1) % tokens.length;
if ( newE != this.end) {
final int oldE = this.end;
this.end = newE;
fireOnRemove( newE, (oldE > 0) ? oldE - 1 : tokens.length - 1);
}
}
add( obj);
return this;
}
public NavigationQueue<E> add( E obj) {
if ( isFull()) {
start = (start + 1) % tokens.length;
fireOnRemove( start, start);
}
tokens[end] = obj;
current = end;
end = (end + 1) % tokens.length;
fireOnAdd( current, current);
return this;
}
@SuppressWarnings( "unchecked")
public E current() {
return ( E) (!isEmpty() ? tokens[current] : null);
}
@SuppressWarnings( "unchecked")
public E peekPrevious() {
if ( current == start)
return null;
else {
int prev = (current > 0) ? current - 1 : tokens.length - 1;
return ( E) tokens[prev];
}
}
@SuppressWarnings( "unchecked")
public E peekNext() {
if ( start == end)
return null;
int nx = (current + 1) % tokens.length;
if ( nx == end)
return null;
else
return ( E) tokens[nx];
}
public Iterator<E> all() {
return new NavigationQueueIterator<E>( start, end);
}
public Iterator<E> listNext() {
return (current == end) ? //
new NavigationQueueIterator<E>( current, end)
: new NavigationQueueIterator<E>( (current + 1) % tokens.length, end);
}
public Iterator<E> listPrevious() {
return new NavigationQueueIterator<E>( start, current);
}
public NavigationQueue<E> swap( E obj) {
if ( isEmpty())
put( obj);
else {
tokens[current] = obj;
fireOnChange( current, current);
}
return this;
}
@SuppressWarnings( "unchecked")
public E previous() {
if ( current == start)
return null;
else {
current = (current > 0) ? current - 1 : tokens.length - 1;
fireOnChange( current, current);
return ( E) tokens[current];
}
}
@SuppressWarnings( "unchecked")
public E next() {
if ( start == end)
return null;
int newCurr = (current + 1) % tokens.length;
if ( newCurr == end)
return null;
else {
current = newCurr;
fireOnChange( current, current);
return ( E) tokens[current];
}
}
@SuppressWarnings( "unchecked")
public E goBeginning() {
if ( current != start) {
current = start;
fireOnChange( current, current);
}
return ( E) tokens[current];
}
@SuppressWarnings( "unchecked")
public E goLast() {
if ( start == end)
return null;
final int newCurr = (end > 0) ? end - 1 : tokens.length - 1;
if ( current != newCurr) {
current = newCurr;
fireOnChange( current, current);
}
return ( E) tokens[current];
}
public boolean hasPrevious() {
return current != start;
}
public boolean hasNext() {
return (current + 1) % tokens.length != end;
}
public boolean isEmpty() {
return start == end;
}
public boolean isSingleOrEmpty() {
final int diff = end - start;
return diff >= 0 && diff <= 1;
}
public boolean isFull() {
return start == (end + 1) % tokens.length;
}
public boolean contains( E obj) {
for ( int i = start; i != end; i = (i + 1) % tokens.length)
if ( tokens[i].equals( obj))
return true;
return false;
}
public static <T> NavigationQueue<T> copyOf( NavigationQueue<T> original) {
final NavigationQueue<T> copy = new NavigationQueue<T>( original.tokens.length - 1);
copy.tokens = new Object[original.tokens.length];
System.arraycopy( original.tokens, 0, copy.tokens, 0, original.tokens.length);
copy.start = original.start;
copy.end = original.end;
copy.current = original.current;
return copy;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment