public class Scoreboard { private int numEntries = 0; private GameEntry[] board; public Scoreboard(int capacity){ board = new GameEntry[capacity]; } }
/* * From Data Structures and Algorithms in Java, Sixth Edition, Goodrich et al. */ public interface Position { /** * Returns the element stored at this position. * * @return the stored element * @throws IllegalStateException if position no longer valid */ E getElement() throws IllegalStateException; }
/* * From Data Structures and Algorithms in Java, Sixth Edition, Goodrich et al. */
public interface PositionalList {
/** * Returns the number of elements in the list. * @return number of elements in the list */ int size();
/** * Tests whether the list is empty. * @return true if the list is empty, false otherwise */ boolean isEmpty();
/** * Returns the first Position in the list. * * @return the first Position in the list (or null, if empty) */ Position first();
/** * Returns the last Position in the list. * * @return the last Position in the list (or null, if empty) */ Position last();
/** * Returns the Position immediately before Position p. * @param p a Position of the list * @return the Position of the preceding element (or null, if p is first) * @throws IllegalArgumentException if p is not a valid position for this list */ Position before(Position p) throws IllegalArgumentException;
/** * Returns the Position immediately after Position p. * @param p a Position of the list * @return the Position of the following element (or null, if p is last) * @throws IllegalArgumentException if p is not a valid position for this list */ Position after(Position p) throws IllegalArgumentException;
/** * Inserts an element at the front of the list. * * @param e the new element * @return the Position representing the location of the new element */ Position addFirst(E e);
/** * Inserts an element at the back of the list. * * @param e the new element * @return the Position representing the location of the new element */ Position addLast(E e);
/** * Inserts an element immediately before the given Position. * * @param p the Position before which the insertion takes place * @param e the new element * @return the Position representing the location of the new element * @throws IllegalArgumentException if p is not a valid position for this list */ Position addBefore(Position p, E e) throws IllegalArgumentException;
/** * Inserts an element immediately after the given Position. * * @param p the Position after which the insertion takes place * @param e the new element * @return the Position representing the location of the new element * @throws IllegalArgumentException if p is not a valid position for this list */ Position addAfter(Position p, E e) throws IllegalArgumentException;
/** * Replaces the element stored at the given Position and returns the replaced element. * * @param p the Position of the element to be replaced * @param e the new element * @return the replaced element * @throws IllegalArgumentException if p is not a valid position for this list */ E set(Position p, E e) throws IllegalArgumentException;
/** * Removes the element stored at the given Position and returns it. * The given position is invalidated as a result. * * @param p the Position of the element to be removed * @return the removed element * @throws IllegalArgumentException if p is not a valid position for this list */ E remove(Position p) throws IllegalArgumentException;
}
what do you mean by text book is not available?
Just let me know if you need anything else. 
PART B Implement a Positional List using an array. Refer to page 281 in your textbook. 1. Create 2 classes called Arraypositionallist with a nested class Locus that implement the positionallist and Position interfaces respectively. 2. Demonstrate your implementation by rewriting the Scoreboard example from L02. Use a Positionallist for the board, and in a Parts_Driver class use the players from the notes to demo (build the scoreboard in any way then add Jill and remove Paul). Note that all methods will be tested by your marker. To implement the ArrayPositionallist, use both the LinkedPositionalList and ArrayList implementations as a guide. a) Add the nested Locus class. Locus implements the Position interface (just like Node in a linked positional list). Note that there is no next or prev, but only an integer index b) Add the fields and constructors: an array of Locus objects a constant CAPACITY defaulted at 16, size field 2 constructors: no-arg and capacity as a parameter c) Add your size () and isEmpty() methods d) Implement the methods: Start with first() and last (): how would you get the first and last elements from an array? This should form a basis of how to move from linked to array. From there you can start thinking about how to convert all the methods from linked-based to array-based. To consider: with LinkedPositionallist, you get the previous and next positions through the node (which is a Position) and getNext() and getProv() methods. With ArrayPositionalList you get the next and previous through the position as well, but with the getIndex() and the array. Instead of simply calling node.next() you will find out what locus.getIndex () is, then return the Locus at the next index of your array. Notes: you will need a way to validate and explicitly cast Position objects to Locus objects in order to use Locus methods like getIndex() many methods declare exceptions in its signature: most can be handled in common private utility methods The index field of the Locus class needs to be updated with any methods that require a shift in elements Your data structure should be dynamic:grows and shrinks according to size/capacity Suggestions: Override the toString method to display both index and elementi.e. an ArrayPositionallist populated with names TOJ Harry [1] Ron [2] Hermione [3] Neville [4] Luna Can be helpful for testing/debugging Test each individual method as you write it 7.1. Positional Lists 281 Implementing a Positional List with an Array We can implement a positional list L using an array A for storage, but some care is necessary in designing objects that will serve as positions. At first glance, it would seem that a position p need only store the index i at which its associated element is stored within the array. We can then implement method getElement(p) simply by returning All The problem with this approach is that the index of an elemente changes when other insertions or deletions occur before it. If we have already returned a position p associated with element that stores an outdated index i to a user, the wrong array cell would be accessed when the position was used (Remember that positions in a positional list should always be defined relative to their neighboring positions, not their indices.) Hence, if we are going to implement a positional list with an array, we need a different approach. We recommend the following representation. Instead of storing the elements of L directly in array A, we store a new kind of position object in each cell of A. A position p stores the element e as well as the current index i of that element within the list. Such a data structure is illustrated in Figure 7.8. (O JFK) (1.BWI) |(2.PVD) (3.SFO) 0 1 2 3 N-1 Figure 7.8: An array-based representation of a positional list. With this representation, we can determine the index currently associated with a position, and we can determine the position currently associated with a specific index. We can therefore implement an accessor, such as before(p). by finding the index of the given position and using the array to find the neighboring position. When an element is inserted or deleted somewhere in the list, we can loop through the array to update the index variable stored in all later positions in the list that are shifted during the update. Efficiency Trade-Offs with an Array-Based Sequence In this array implementation of a sequence, the addFirst, addBefore, addAfter, and remove methods take O(n) time, because we have to shift position objects to make room for the new position or to fill in the hole created by the removal of the old position (just as in the insert and remove methods based on index). All the other position-based methods take O(1) time. www.it-ebooks.info 1 /** Class for storing high scores in an array in nondecreasing order. / 2 public class Scoreboard { 3 private int numEntries = 0; // number of actual entries 4 private GameEntry[ ] board; // array of game entries (names & scores) 5 /** Constructs an empty scoreboard with the given capacity for storing entries. */ 6 public Scoreboard (int capacity) { 7 board = new GameEntry(capacity]: 8 } // more methods will go here 36} * From Data Structures and Algorithms in Java, Sixth Edition, Goodrich et al. public interface Position
{ /** * Returns the element stored at this position. * * @return the stored element * @throws IllegalStateException if position no longer valid */ E getElement() throws IllegalStateException; Insert Editing Or 12.113.45 61.711.89.1.10 11 12 13 14 15 16 17 V From Data Structures and Algorithms in Java, sixth Edition, Goodrich et al. *7 public interface Positionallist { / * Returns the number of elements in the list. * @return number of elements in the list . int size(); . Tests whether the list is empty. @return true if the list is empty, false otherwise boolean isEmpty(); I Returns the first Position in the list. @return the first Position in the list (or null, if empty) ./ Position first(); / Returns the last position in the list. * @return the last position in the list (or null, if empty) 7 Position last(); /* Returns the position immediately before Position p. @param p a Position of the list * @return the Position of the preceding element for null, if p is first) @throws IllegalArgumentException if p is not a valid position for this list . Position before(Position p) throws IllegalArgumentException; / Returns the Position immediately after Position p. eparam p Position of the list return the position of the following element (or null, if p is last) Insert Editing 11 12 13 14 15 16 17 1 81.9 110 111 112 113 114 15 16 Returns the Position immediately after Position p. * @parampa Position of the list @return the Position of the following element (or null, if p is last) *@throws IllegalArgumentException if p is not a valid position for this list Positione after (Position p) throws IllegalArgumentException; /** Inserts an element at the front of the list. @param e the new element * @return the position representing the location of the new element +/ Position addFirst (E ); / Inserts an element at the back of the list. @param the new element * @return the position representing the location of the new element -/ Position addiast(e); 7. Inserts an element immediately before the given Position. @param p the position before which the insertion takes place @param e the new element @return the Position representing the location of the new @throws IllegalArgumentException if p is not a valid position for this list ./ Position addBefore(Position P, Ee) throws IllegalArgumentException; element Inserts an element immediately after the given Position. @param p the Position after which the insertion takes place @parame the new element return the Position representing the location of the new olament * Inserts an element immediately after the given Position. @param p the Position after which the insertion takes place * @param e the new element * @return the Position representing the location of the new element * @throws IllegalArgumentException if p is not a valid position for this list */ Position addAfter(Position P, Ee) throws IllegalArgumentException; ** * Replaces the element stored at the given Position and returns the replaced element. @param p the Position of the element to be replaced @param e the new element @return the replaced element * @throws IllegalArgumentException if p is not a valid position for this list */ E set (Position P, Ee) throws IllegalArgumentException; * Removes the element stored at the given Position and returns it. * The given position is invalidated as a result. * @param p the Position of the element to be removed @return the removed element * @throws IllegalArgumentException if p is not a valid position for this list +/ E remove (Position p) throws Illegal ArgumentException
