Implement the Java class depicted below. May not use the
Implement the Java class depicted below. May not use the
API’s ArrayList class or any other API collection save arrays. Be sure to follow the
specs exactly.
Will revise the Weiss ArrayList class(shown below) with the following modifications (Note that
from this point onward substitute “Whatever” with your “LAB” – details below):
1) The list must be sorted in ascending order at all times, with no null references in the
middle of the data. The list must have this order maintained at the end of every
public method call, so some existing methods will need to be modified.
2) Modify the add() (and any other supporting methods as you see fit) method of the
class so that each new item is inserted in sorted (ascending) order.
3) Add a new public. method, addAt(), that takes the object to add and the index to
insert it at, in that order. No items are replaced, just relocated. Note that if the index
parameter is not the proper one for that item based on ordering the method should
insert the item at the proper index that places it in order, not the requested one.
4) Modify the set() method so that it replaces and returns the item at the specified
index while putting the new item in its correct location in the list as with addAt().
5) Adjust the constructor that takes a Collection parameter so that it creates the
Whatever with the same size as the Collection passed to it. The constructor
still initializes the Whatever with the contents of the Collection parameter.
6) Add another constructor that takes in a lone integer parameter. The Whatever is
initially created to this size rather than the default size.
7) Add an instance method named getMode() that returns the most-occurring value in
the list. The method’s return type is Result, a generic interface that has two
methods: AnyType mode(), which returns the most-occurring item in the list, and
int count(), which returns how many times that item occurs. Tiebreak on first-
occurring item of the highest frequency. The code for the Result interface will be
provided to you to incorporate into your package. Do not send this interface file with
your code. Note that the object you return needs to be a very simple container with
the values necessary to support the interface methods. It does not include any
computation logic – all work should be done the list class.
8) Add a generic static method that takes in a (your) Whatever and performs a
binary search on it. The method takes exactly two parameters: a Whatever, and
the item to search for. The type of the second parameter needs to reflect what could
possibly be in the Whatever instance. This method returns an int that is the index
in the list where the item resides, or -1 if not found. The method header will look
similar (same name but you need to revise it to make it use generics) to:
public static int binSearch(Whatever list, AnyType item)
data must be Comparable.
Note:
Copy/revise the Weiss ArrayList(shown below), but don’t subclass
Have class “extend” (implement really, but generics use the keyword
“extend” for a parameterized type) Comparable
Will amend the basic ArrayList class provided, All existing functionality must be preserved unless explicitly specified otherwise. Remember that ArrayList is generic. Be sure to import the Weiss classes rather than those in the API – there’s less to implement, but definitely enough to get things done. All instance variables must be private.
Weiss ArrayList:
package weiss.util;
/**
* The ArrayList implements a growable array.
* Insertions are always done at the end.
*/
public class ArrayList
{
/**
* Construct an empty ArrayList.
*/
public ArrayList( )
{
clear( );
}
/**
* Construct an ArrayList with same items as another Collection.
*/
public ArrayList( Collection other )
{
clear( );
for( AnyType obj : other )
add( obj );
}
public ArrayList
{ return new SubList( from, to ); }
private class SubList extends ArrayList
{
private List
private int offset;
private int size;
public ArrayList
{
return new SubList( this, from, to );
}
public SubList( int from, int to )
{ if( from < 0 || to > ArrayList.this.size( ) ) throw new IllegalArgumentException( from + ” ” + to + ” ” + ArrayList.this.size( ) );
original = ArrayList.this; offset = from; size = to – from; }
public SubList( SubList sub, int from, int to )
{ if( from < 0 || to > sub.size( ) ) throw new IllegalArgumentException( from + ” ” + to + ” ” + sub.size( ) );
original = sub.original; offset = sub.offset + from; size = to – from; }
public int size( )
{ return size; }
public AnyType get( int idx )
{ return original.get( offset + idx ); }
public AnyType set( int idx, AnyType x )
{ return original.set( offset + idx, x ); }
public boolean add( AnyType x )
{ throw new UnsupportedOperationException( ); }
public AnyType remove( int idx )
{ throw new UnsupportedOperationException( ); }
public boolean remove( Object x )
{ throw new UnsupportedOperationException( ); }
public boolean contains( Object x )
{ for( AnyType item : this ) if( item.equals( x ) ) return true; return false; }
public ListIterator
{ return original.listIterator( offset + idx ); }
public Iterator
{ return original.listIterator( offset ); }
}
/**
* Returns the number of items in this collection.
* @return the number of items in this collection.
*/
public int size( )
{
return theSize;
}
/**
* Returns the item at position idx.
* @param idx the index to search in.
* @throws ArrayIndexOutOfBoundsException if index is out of range.
*/
public AnyType get( int idx )
{
if( idx < 0 || idx >= size( ) )
throw new ArrayIndexOutOfBoundsException( “Index ” + idx + “; size ” + size( ) );
return theItems[ idx ];
}
/**
* Changes the item at position idx.
* @param idx the index to change.
* @param newVal the new value.
* @return the old value.
* @throws ArrayIndexOutOfBoundsException if index is out of range.
*/
public AnyType set( int idx, AnyType newVal )
{
if( idx < 0 || idx >= size( ) )
throw new ArrayIndexOutOfBoundsException( “Index ” + idx + “; size ” + size( ) );
AnyType old = theItems[ idx ];
theItems[ idx ] = newVal;
return old;
}
/**
* Tests if some item is in this collection.
* @param x any object.
* @return true if this collection contains an item equal to x.
*/
public boolean contains( Object x )
{
return findPos( x ) != NOT_FOUND;
}
/**
* Returns the position of first item matching x in this collection,
* or NOT_FOUND if not found.
* @param x any object.
* @return the position of first item matching x in this collection,
* or NOT_FOUND if not found.
*/
private int findPos( Object x )
{
for( int i = 0; i < size( ); i++ )
if( x == null )
{
if( theItems[ i ] == null )
return i;
}
else if( x.equals( theItems[ i ] ) )
return i;
return NOT_FOUND;
}
/**
* Adds an item to this collection, at the end.
* @param x any object.
* @return true.
*/
public boolean add( AnyType x )
{
if( theItems.length == size( ) )
{
AnyType [ ] old = theItems;
theItems = (AnyType []) new Object[ theItems.length * 2 + 1 ];
for( int i = 0; i < size( ); i++ )
theItems[ i ] = old[ i ];
}
theItems[ theSize++ ] = x;
modCount++;
return true;
}
/**
* Removes an item from this collection.
* @param x any object.
* @return true if this item was removed from the collection.
*/
public boolean remove( Object x )
{
int pos = findPos( x );
if( pos == NOT_FOUND )
return false;
else
{
remove( pos );
return true;
}
}
/**
* Removes an item from this collection.
* @param idx the index of the object.
* @return the item was removed from the collection.
*/
public AnyType remove( int idx )
{
AnyType removedItem = theItems[ idx ];
for( int i = idx; i < size( ) - 1; i++ )
theItems[ i ] = theItems[ i + 1 ];
theSize--;
modCount++;
return removedItem;
}
/**
* Change the size of this collection to zero.
*/
public void clear( )
{
theSize = 0;
theItems = (AnyType []) new Object[ DEFAULT_CAPACITY ];
modCount++;
}
/**
* Obtains an Iterator object used to traverse the collection.
* @return an iterator positioned prior to the first element.
*/
public Iterator
{
return new ArrayListIterator( 0 );
}
/**
* Obtains a ListIterator object used to traverse the collection bidirectionally.
* @return an iterator positioned prior to the requested element.
* @param idx the index to start the iterator. Use size() to do complete
* reverse traversal. Use 0 to do complete forward traversal.
* @throws IndexOutOfBoundsException if idx is not between 0 and size(), inclusive.
*/
public ListIterator
{
return new ArrayListIterator( idx );
}
/**
* This is the implementation of the ArrayListIterator.
* It maintains a notion of a current position and of
* course the implicit reference to the ArrayList.
*/
private class ArrayListIterator implements ListIterator
{
private int current;
private int expectedModCount = modCount;
private boolean nextCompleted = false;
private boolean prevCompleted = false;
ArrayListIterator( int pos )
{
if( pos < 0 || pos > size( ) )
throw new IndexOutOfBoundsException( );
current = pos;
}
public boolean hasNext( )
{
if( expectedModCount != modCount )
throw new ConcurrentModificationException( );
return current < size( );
}
public boolean hasPrevious( )
{
if( expectedModCount != modCount )
throw new ConcurrentModificationException( );
return current > 0;
}
public AnyType next( )
{
if( !hasNext( ) )
throw new NoSuchElementException( );
nextCompleted = true;
prevCompleted = false;
return theItems[ current++ ];
}
public AnyType previous( )
{
if( !hasPrevious( ) )
throw new NoSuchElementException( );
prevCompleted = true;
nextCompleted = false;
return theItems[ –current ];
}
public void remove( )
{
if( expectedModCount != modCount )
throw new ConcurrentModificationException( );
if( nextCompleted )
ArrayList.this.remove( –current );
else if( prevCompleted )
ArrayList.this.remove( current );
else
throw new IllegalStateException( );
prevCompleted = nextCompleted = false;
expectedModCount++;
}
}
private static final int DEFAULT_CAPACITY = 10;
private static final int NOT_FOUND = -1;
private AnyType [ ] theItems;
private int theSize;
private int modCount = 0;
}
Complete Answer:
