/* ** j###t ########## #### #### ** j###t ########## #### #### ** j###T "###L J###" ** ######P' ########## ######### ** ######k, ########## T######T ** ####~###L #### ** #### q###L ########## .##### ** #### \###L ########## #####" ** ** $Id$ ** ** Class History ** ** Date Name Description ** ---------|------------|----------------------------------------------- ** 19Aug98 subtle start of recorded history ** 20Oct98 subtle added serialisation ** 25Oct98 subtle fixed a small bug in count() ** 02Nov98 subtle moved to key.util package ** */ package key.util; import java.io.*; import java.util.Enumeration; import java.util.NoSuchElementException; /** * Implementation of a doubly linked list * * @version 1.2, 02Nov98 * @author Paul Mclachlan * */ public class LinkedList implements java.io.Serializable { private static final long serialVersionUID = -377921300625278844L; private Element First; private Element Last; private int Count; private static int totalLists; /** * creates the queue */ public LinkedList() { init(); } private void init() { totalLists++; First = null; Last = null; Count = 0; } private void readObject( ObjectInputStream from ) throws IOException,StreamCorruptedException,ClassNotFoundException { init(); int count; count = from.readInt(); while( count-- > 0 ) append( from.readObject() ); } private void writeObject( ObjectOutputStream to ) throws IOException { to.writeInt( Count ); for( Enumeration e = elements(); e.hasMoreElements(); ) to.writeObject( e.nextElement() ); } /** * Adds another object to the queue * * @param store the object to be added */ public final synchronized void append( Object store ) { Element latest = new Element( store ); if( Last != null ) { latest.setPrevious( Last ); Last.setNext( latest ); } else First = latest; Last = latest; Count++; } public final synchronized void appendCycle( Object store, int max ) { append( store ); while( Count > max && First != null ) { // remove lines from the front until // we have at most max lines. removeLinkedListElement( First ); } } /** * Adds another object to the queue * * @param store the object to be added */ public final synchronized void prepend( Object store ) { Element latest = new Element( store ); if( First != null ) { latest.setNext( First ); First.setPrevious( latest ); } else Last = latest; First = latest; Count++; } /** * Returns the number of objects in the queue * @return the number of objects in the queue */ public final int count() { return( Count ); } public final Object getFirstElement() { if( First != null ) return( First.item() ); else return( null ); } public final Object getLastElement() { if( Last != null ) return( Last.item() ); else return( null ); } public final Enumeration elements() { return( new Enumerator( First ) ); } public final boolean contains( Object o ) { for( Enumeration e = this.elements(); e.hasMoreElements(); ) if( e.nextElement() == o ) return true; return false; } public final boolean containsEqual( Object o ) { for( Enumeration e = this.elements(); e.hasMoreElements(); ) if( e.nextElement().equals( o ) ) return true; return false; } public final void replaceEqual( Object o ) { Element lle = First; while( lle != null ) { if( lle.stored.equals( o ) ) { lle.stored = o; return; } lle = lle.next; } } public final Object getElementAt( int c ) { int i = 0; for( Enumeration e = this.elements(); e.hasMoreElements(); i++ ) { Object o = e.nextElement(); if( i == c ) return o; } return( null ); } private final synchronized void removeLinkedListElement( Element s ) { if( s == First ) { if( s == Last ) { // only this element in the list First = null; Last = null; } else { // the first element in the list First = s.getNext(); First.setPrevious( null ); } } else { if( s == Last ) { // last element in the list Last = s.getPrevious(); Last.setNext( null ); } else { // middle element in the list s.getPrevious().setNext( s.getNext() ); s.getNext().setPrevious( s.getPrevious() ); } } Count--; return; } public final synchronized void removeElementAt( int c ) { Element s=First; int i = 0; while( s != null ) { if( i == c ) { removeLinkedListElement( s ); return; } s = s.getNext(); i++; } } /** * No action if o is not in the list */ public final synchronized void remove( Object o ) { Element s=First; while( s != null ) { if( s.item() == o ) { removeLinkedListElement( s ); return; } s = s.getNext(); } } /** * Call if you wish to use the .equals() method * to compare objects. */ public final synchronized void removeEqual( Object o ) { Element s=First; while( s != null ) { if( s.item().equals( o ) ) { removeLinkedListElement( s ); return; } s = s.getNext(); } } /** * Erase all elements in this list */ public final synchronized void clear() { // ahh, the wonders of a garbage collector First = null; Last = null; Count = 0; } public final Iterator iterator() { return( new Iterator() ); } /* TEST SUITE final void dump() { if( First != null ) System.out.println( "First: " + First.toString() ); else System.out.println( "First: null" ); if( Last != null ) System.out.println( "Last: " + Last.toString() ); else System.out.println( "Last: null" ); System.out.println( "----elements----" ); Element t; t = First; while( t != null ) { System.out.println( t.toString() + "---> " + t.item().toString() ); t = t.getNext(); } } public static void main( String args[] ) { LinkedList main = new LinkedList(); String entry; int count=0; do { System.out.println( "\nLinkedList contains " + main.count() + " elements" ); entry = input( "append,prepend,dump: " ); if( entry.length() == 0 ) { } else if( entry.equals( "dump" ) ) { System.out.println( "\nDUMPING:\n--------" ); main.dump(); } else if( entry.equals( "quit" ) ) { } else if( entry.startsWith( "append " ) ) { entry = entry.substring( 7 ); System.out.println( "Appending " + entry + "..." ); main.append( entry ); } else if( entry.startsWith( "prepend " ) ) { entry = entry.substring( 7 ); System.out.println( "Prepending " + entry + "..." ); main.prepend( entry ); } else { System.out.println( "Unknown command '" + entry + "'" ); } } while( !entry.equals( "quit" ) ); } public static String input( String prompt ) { StringBuffer buildInput = new StringBuffer(); char b=' '; System.out.print( prompt ); System.out.flush(); do { try { b = (char) System.in.read(); } catch( IOException e ) { System.out.println( e.toString() ); System.exit( 1 ); } if( b != '\n' && b != 0 ) buildInput.append( b ); } while( b != '\n' && b != 0 ); return( new String( buildInput ) ); } */ public static int getTotalLists() { return( totalLists ); } protected void finalize() throws Throwable { super.finalize(); totalLists--; } private final static class Enumerator implements Enumeration { Element c; public Enumerator( Element first ) { c = first; } public boolean hasMoreElements() { return( c != null ); } public Object nextElement() { if( c != null ) { Element result = c; c = c.getNext(); return( result.item() ); } else throw new NoSuchElementException( "iterating past end of linked list" ); } } private final static class Element { Object stored; Element next; Element prev; /** * Creates a new queue element to hold * this object */ public Element( Object store ) { stored = store; next = null; prev = null; } /** * Sets the value of 'next' to the given value @param next the next element in the queue */ public void setNext( Element Next ) { next = Next; } public Element getNext() { return( next ); } public void setPrevious( Element Previous ) { prev = Previous; } public Element getPrevious() { return( prev ); } public Object item() { return( stored ); } public String toString() { if( prev != null ) { if( next != null) return( String.valueOf( super.hashCode() ) + ": previous=" + prev.hashCode() + " next=" + next.hashCode() ); else return( String.valueOf( super.hashCode() ) + ": previous=" + prev.hashCode() + " next=null" ); } else { if( next != null) return( String.valueOf( super.hashCode() ) + ": previous=null next=" + next.hashCode() ); else return( String.valueOf( super.hashCode() ) + ": previous=null next=null" ); } } } public final class Iterator { Element c; public Iterator() { c = LinkedList.this.First; } public Object element() { return( c.item() ); } public void next() { c = c.getNext(); } public void previous() { c = c.getPrevious(); } public boolean isFirst() { return( LinkedList.this.First == c ); } /** * Use this to iterate through the linked list. eg: * * for( Iterator l = list.iterator(); l.isValid(); l.next() ) * loop(); */ public boolean isValid() { return( c != null ); } public boolean isLast() { return( LinkedList.this.Last == c ); } public void last() { c = LinkedList.this.Last; } public void first() { c = LinkedList.this.First; } public void insertBefore( Object o ) { Element lle = new Element( o ); lle.setPrevious( c.getPrevious() ); lle.setNext( c ); if( isFirst() ) LinkedList.this.First = lle; if( c.getPrevious() != null ) c.getPrevious().setNext( lle ); c.setPrevious( lle ); LinkedList.this.Count++; } public void insertAfter( Object o ) { Element lle = new Element( o ); lle.setNext( c.getNext() ); lle.setPrevious( c ); if( isLast() ) LinkedList.this.Last = lle; if( c.getNext() != null ) c.getNext().setPrevious( lle ); c.setNext( lle ); LinkedList.this.Count++; } public void remove() { if( isFirst() ) LinkedList.this.First = c.getNext(); if( isLast() ) LinkedList.this.Last = c.getPrevious(); if( c.getNext() != null ) c.getNext().setPrevious( c.getPrevious() ); if( c.getPrevious() != null ) c.getPrevious().setNext( c.getNext() ); LinkedList.this.Count--; c = c.getNext(); } } }