In java
below is an example of the alphabet class
public class IteratorExample1Client {
public static void main(String[] args) { // // Create an instance of the Alphabet class which is // just a LinkedPositiionalList of Letters. //
Alphabet alphabet = new Alphabet(); // // Look at the toString( ) method in the Alphabet class. // This method uses a iterator to move across the list // System.out.println( "Using toString() alphabet = " + alphabet.toString() ); System.out.print(" "); // // Let's create an Iterator for the LinkedPositionalList // // Decision: Do you want a PositionInterator or an ElementIterator? // // Let's pick the PositionIterator. // // Since the PositionIterator class is a private class nested in // the LinkedPositionalList class we cannot call the class methods // directly. // // The PositionalIterable class is also a private class nested in // the LinkedPositionalList class that we cannot call the class methods // directly. // // Fortunately (or perhaps by design) the Iterable class is a public // class nexted in LinkedPositionalList class so we can call its // class methods directly. // // This class has one method "positions()" that generally // returns an object of type IterablePositions // and in our specific case // returns an object of type IterablePostions // // The object returned by "positions()" gives us access to the // nested private class PositionIterable class that returns an // PositionIterator object. // // The PositionIterator object is the iterator. // Iterator> letterListIterator = alphabet.positions().iterator(); System.out.print("Using letterListIterator alphabet = "); while ( letterListIterator.hasNext() ) System.out.print( letterListIterator.next().getElement().toString() + " " ); System.out.print( " " ); // // This seems like a lot of work to traverse a list but provided we have // access to the Iterator classes we can build an iterator to traverse // the list without any knowledge of how the list is implemented. // // Also we have the opportunity to build customized iterators that // allow us the specify how we will traverse the list. // // For example we may want to build an iterator that moves accross all // of the vowels in the alphabet. // // To do this we create a nested interator class inside of our // Alphabet class. //
Iterator> vowelListIterator = alphabet.vowelPositions().iterator(); System.out.print("Using VowelListIterator alphabet = "); while ( vowelListIterator.hasNext() ) System.out.print( vowelListIterator.next().getElement().toString() + " " ); System.out.print( " " ); } }
============================================================================
public class Alphabet { private LinkedPositionalList alphabet = null;
// // Constructor builds a LinkedPositionalList of Letters. // public Alphabet( ){ alphabet = new LinkedPositionalList();
String alphabetString = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; Letter nextLetter; for ( int i = 0; i listIterator = alphabet.iterator(); while ( listIterator.hasNext() ) returnString += listIterator.next() + " "; return returnString; } // // The following classes are the nested Iterator classes from // Code Fragment 7.14 // // Only the classes for the Position Itertor have bee included. // // These fragements have been modified so that they are specific to the // Alphabet class. // // It is necessary to put the iterator code here since we want to create // iterators specifically for the Alphabet class which is a concrete class // based on the generic ADT LinkedPositionalList. // // Our code needs to have knowledge of Letter. // // Generally the Generic placeholders have been replaced with // concret references // AND // Call to LinkedPositionalList methods have be replaced by calls using // the instance reference alphabet // e.g. // private Position cursor = first(); // became // private Position cursor = alphabet.first(); // //----- nested PositionIterator class ----- private class PositionIterator implements Iterator>{ private Position cursor = alphabet.first(); // position of the next element to report private Position recent = null; // position of last reported element /** Tests whether the iterator has a next object. */ @Override public boolean hasNext( ) { return ( cursor != null ); } /** Returns the next position in the iterator. */ @Override public Position next( ) throws NoSuchElementException { if ( cursor == null ) throw new NoSuchElementException( "nothing left " ); recent = cursor; cursor = alphabet.after( cursor ); return recent; } /** Removes the element returned by most recent call to next. */ @Override public void remove( ) throws IllegalStateException { if ( recent == null ) throw new IllegalStateException( "nothing to remove" ); alphabet.remove( recent ); // remove from outer list recent = null; // do not allow remove again until next is called } } //----- end of nested PositionIterator class ----- //----- nested PositionIterable class ----- private class PositionIterable implements Iterable>{ @Override public Iterator> iterator( ) { return new PositionIterator( ); } } //----- end of nested PositionIterable class ----- /** Returns an iterable representation of the list's positions. * @return */ public Iterable> positions( ) { return new PositionIterable( ); // create a new instace of the inner class } // // Below are the nested iterator classes modified to iterate over just the // vowels in a the alphabet list // // Aside from taking care of name conflicts the only real modification // that is necessary is in the next() method betweeen the lines: // recent = cursor; // >{ private Position cursor = alphabet.first(); // position of the next element to report private Position recent = null; // position of last reported element /** Tests whether the iterator has a next object. */ @Override public boolean hasNext( ) { return ( cursor != null ); } /** Returns the next position in the iterator. */ @Override public Position next( ) throws NoSuchElementException { // On the first call to next (i.e. when recent == null) you need to //>{ @Override public Iterator> iterator( ) { return new VowelPositionIterator( ); } } //----- end of nested PositionIterable class ----- /** Returns an iterable representation of the list's positions. * @return */ public Iterable> vowelPositions( ) { return new VowelPositionIterable( ); // create a new instace of the inner class } }
===============================================================================
public interface Iterable { Iterator iterator( ); // Returns an iterator of the elements in the collection }
=======================================================================
public interface Iterator { boolean hasNext( ); // Returns true if there is at least one additional // element in the sequence, and false otherwise. E next( ); // Returns the next element in the sequence. void remove( ) throws IllegalStateException; // Removes from the collection the element returned by // the most recent call to next( ). Throws an // IllegalStateException if next has not yet been called, // or if remove was already called since the most recent // call to next. }
===================================================================
public class Letter { String letter; public Letter() { } public Letter( String letter ) { this.letter = letter; } public Letter( char letter ) { String newLetter = "" + letter; this.letter = newLetter.toUpperCase(); } public String toString( ){ return letter; } }
========================================================================
/** Implementation of a positional list stored as a doubly linked list. */ public class LinkedPositionalList implements PositionalList { //----- nested Node class ----- private static class Node implements Position { private E element; // reference to the element stored at this node private Node prev; // reference to the prevous node in the list private Node next; // reference to the subsequent node in the list public Node( E e, Node p, Node n ){ element = e; prev = p; next = n; } @Override public E getElement( ) throws IllegalStateException { if ( next == null ) throw new IllegalStateException( "Position no longer valid." ); return element; } public Node getPrev( ) { return prev; } public Node getNext( ) { return next; } public void setElemetn( E e ) { element = e; } public void setPrev( Node p ) { prev = p; } public void setNext( Node n ) { next = n; } } //----- end of nested Node class ----- /** * Data Structures & Algorithms 6th Edition * Goodrick, Tamassia, Goldwasser * Code Fragement 7.14 */ //----- nested PositionIterator class ----- private class PositionIterator implements Iterator>{ private Position cursor = first(); // position of the next element to report private Position recent = null; // position of last reported element /** Tests whether the iterator has a next object. */ @Override public boolean hasNext( ) { return ( cursor != null ); } /** Returns the next position in the iterator. */ @Override public Position next( ) throws NoSuchElementException { if ( cursor == null ) throw new NoSuchElementException( "nothing left " ); recent = cursor; cursor = after( cursor ); return recent; } /** Removes the element returned by most recent call to next. */ @Override public void remove( ) throws IllegalStateException { if ( recent == null ) throw new IllegalStateException( "nothing to remove" ); LinkedPositionalList.this.remove( recent ); // remove from outer list recent = null; // do not allow remove again until next is called } } //----- end of nested PositionIterator class ----- //----- nested PositionIterable class ----- private class PositionIterable implements Iterable>{ @Override public Iterator> iterator( ) { return new PositionIterator( ); } } //----- end of nested PositionIterable class ----- /** Returns an iterable representation of the list's positions. * @return */ public Iterable> positions( ) { return new PositionIterable( ); // create a new instance of the inner class } //----- nested ElementIterator class ----- /* This class adapts the iteration produced by positions( ) to return elements. */ private class ElementIterator implements Iterator { Iterator> posIterator = new PositionIterator( ); @Override public boolean hasNext( ) { return posIterator.hasNext( ); } @Override public E next( ) { return posIterator.next( ).getElement( ); } // return element @Override public void remove( ) { posIterator.remove( ); } } /** Returns an iterator of the elements stored in the list */ public Iterator iterator( ) { return new ElementIterator( ); } // instance variables of the LinkedPositionalList private Node header; // header sentinel private Node trailer; // trailer sentinel private int size = 0; // number of elements in the list public LinkedPositionalList( ){ header = new Node( null, null, null ); // create header trailer = new Node( null, header, null ); // create trailer is preceded by header header.setNext(trailer); // header is followed by trailer } // private utilities /** * @param p position to validate * @return node if position is valid * @throws IllegalArgumentException if p no longer in list or p is not a position */ private Node validate( Position p ) throws IllegalArgumentException { if( !(p instanceof Node )) throw new IllegalArgumentException( "Invalid p" ); Node node = ( Node ) p; // safe cast if ( node.getNext() == null ) throw new IllegalArgumentException( "p is no longer in the list" ); return node; } /** * @param node to be returned as position if not header or trailer * @return position of node */ private Position position( Node node ){ if ( node == header || node == trailer ) return null; return node; } // public accessor methods /** * @return number of elements in linked list */ @Override public int size( ){ return size; } /** * @return true if list is empty, false other wise */ @Override public boolean isEmpty( ){ return ( size == 0 ); } /** * @return the first position in linked list (null if empty). */ @Override public Position first( ){ return position( header.getNext( ) ); } /** * @return the last position in linked list (null if empty). */ @Override public Position last( ){ return position( trailer.getPrev( ) ); } /** * @param p position to get position immediately before * @return position before p * @throws IllegalArgumentException if p not valid */ @Override public Position before( Position p ) throws IllegalArgumentException{ Node node = validate( p ); return position( node.getPrev( ) ); } /** * @param p position to get immediately after * @return position after p * @throws IllegalArgumentException if p not valid */ @Override public Position after( Position p ) throws IllegalArgumentException{ Node node = validate( p ); return position( node.getNext( ) ); } // private utilities /** * @param e element to be added * @param pred node to add element after * @param succ node to add element before * @return position of newly added element */ private Position addBetween(E e, Node pred, Node succ ){ Node newest = new Node(e, pred, succ); // create and link new node pred.setNext(newest); succ.setPrev(newest); size++; return newest; } // public update methods /** * @param e element to be added just after header * @return position of newly added element */ @Override public Position addFirst(E e) { return addBetween( e, header, header.getNext() ); } /** * @param e element to be added just before trailer * @return position of newly added element */ @Override public Position addLast( E e ){ return addBetween(e, trailer.getPrev( ), trailer ); } /** * * @param p position to add element before * @param e element to be added * @return position of newly added element * @throws IllegalArgumentException if p is not valid */ @Override public Position addBefore( Position p, E e ) throws IllegalArgumentException { Node node = validate( p ); return addBetween(e, node.getPrev( ), node ); } /** * @param p position to add element after * @param e element to be added * @return position of newly added element * @throws IllegalArgumentException if p is not valid */ @Override public Position addAfter( Position p, E e ) throws IllegalArgumentException { Node node = validate( p ); return addBetween(e, node, node.getNext( ) ); } /** * @param p position of node to update * @param e new element for node * @return old element in node before update * @throws IllegalArgumentException if p not valid */ @Override public E set( Position p, E e ) throws IllegalArgumentException { Node node = validate( p ); E answer = node.getElement( ); node.setElemetn( e ); return answer; } /** * @param p position to be removed * @return element that was removed * @throws IllegalArgumentException if p not valid */ public E remove( Position p ) throws IllegalArgumentException { Node node = validate( p ); Node predecessor = node.getPrev(); Node successor = node.getNext(); predecessor.setNext( successor ); successor.setPrev( predecessor ); size--; E answer = node.getElement( ); node.setElemetn( null ); node.setNext( null ); node.setPrev( null ); return answer; } }
========================================================================================
public interface Position { /** * Returns the element stored at this position. * * @return the stored element * @thorws IllegalStateExceptoin if position no longer valid */ E getElement( ) throws IllegalStateException; }
=======================================================================
public interface PositionalList { /** * @return the number of elements in the list. */ int size( ); /** * @return true if the list is empty. */ boolean isEmpty( ); /** * @return the first Position in the list ( or null, if empty ). */ Position first( ); /** * @return the last Position in the list ( or null, if empty ). */ Position last( ); /** * @param p a position in the list, * @return position immediately before p ( or null if p is first ). * @throws IllegalArgumentException if p is not in list. */ Position before( Position p ) throws IllegalArgumentException; /** * @param p a position in the list, * @return position immediately after p ( or null if p is last ). * @throws IllegalArgumentException if p is not in list. */ Position after( Position p ) throws IllegalArgumentException; /** * @param e element to be inserted at front of list * @return position of inserted element */ Position addFirst( E e ); /** * @param e element to be inserted at back of list * @return position of inserted element */ Position addLast( E e ); /** * @param p position to be inserted before * @param e element to be inserted before position p * @return position of e * @throws IllegalArgumentException if p not in list */ Position addBefore( Position p, E e ) throws IllegalArgumentException; /** * @param p position to be inserted after * @param e element to be inserted after position p * @return position of e * @throws IllegalArgumentException if p not in list */ Position addAfter( Position p, E e ) throws IllegalArgumentException; /** * @param p position to store element at * @param e element to be stored at p * @return the element that is replaced * @throws IllegalArgumentException if p is not in list */ E set( Position p, E e ) throws IllegalArgumentException; /** * @param p position of element to be removed * @return removed element * @throws IllegalArgumentException if p not in list */ E remove( Position p ) throws IllegalArgumentException; }
===========================================
Create a class named LuckyNumber that has the following instance variables: String name - int luckyNumber This class should only have a single overload constructor that: takes a single parameter, name automatically assigns luckyNumber a random number between 0 and 9 (inclusive of both) to the instance being created This class must have the following methods: - getName get luckyNumber - toString make sure your toString returns the class name the class name will be useful if you "become lost" in your data structure o o - edquals This class should not have the following methods: set name o yo u are who you are - set luckyNumber o you can't change your luck Create a class named LuckyNumber that has the following instance variables: String name - int luckyNumber This class should only have a single overload constructor that: takes a single parameter, name automatically assigns luckyNumber a random number between 0 and 9 (inclusive of both) to the instance being created This class must have the following methods: - getName get luckyNumber - toString make sure your toString returns the class name the class name will be useful if you "become lost" in your data structure o o - edquals This class should not have the following methods: set name o yo u are who you are - set luckyNumber o you can't change your luck
