2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Back to the Main Page
|
|
||
|
Select a Chapter:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Back to the Main Page
|
||
| Chapter Fifteen listings: 5 classes | ||
public class Inventory
{
/** Read 2 files of data and make comparisons between them. */
public static void main (String[] args)
{ ArraySequence inventory;
ArraySequence purchased;
try
{ inventory = new ArraySequence ("inven.dat");
purchased = new ArraySequence ("purch.dat");
}catch (java.io.IOException e)
{ throw new RuntimeException ("A file is defective.");
}
if (inventory.equals (purchased))
System.out.println ("a perfect match");
else if (inventory.isEmpty())
System.out.println ("we've been robbed");
else if (inventory.containsAll (purchased))
System.out.println ("no losses and some gains");
else
System.out.println ("inventory has " + inventory.size()
+ " and purchased has " + purchased.size());
} //======================
}
import java.io.*;
import java.util.*;
public class ArraySequence implements Collection
{
private Object[] itsItem;
private int itsSize = 0;
public ArraySequence()
{ itsItem = new Object[100];
} //======================
public ArraySequence (String fileName) throws IOException
{ BufferedReader file = new BufferedReader
(new FileReader (fileName));
itsItem = new Object[100];
String s = file.readLine();
while (s != null)
{ if (itsSize == itsItem.length)
itsItem = copyOf (itsItem, 2);
itsItem[itsSize] = s;
itsSize++;
s = file.readLine();
}
} //======================
private Object[] copyOf (Object[] given, int big)
{ Object[] valueToReturn = new Object [given.length * big];
for (int k = 0; k < given.length; k++)
valueToReturn[k] = given[k];
return valueToReturn;
} //======================
public ArraySequence (ArraySequence that)
{ this.itsItem = copyOf (that.itsItem, 1);
this.itsSize = that.itsSize;
} //======================
public boolean equals (Object ob)
{ if ( ! (ob instanceof ArraySequence))
return false;
ArraySequence that = (ArraySequence) ob;
if (this.itsSize != that.itsSize)
return false;
for (int k = 0; k < that.itsSize; k++)
{ if ( ! this.itsItem[k].equals (that.itsItem[k]))
return false;
}
return true;
} //======================
public int size()
{ return itsSize;
} //======================
public boolean isEmpty()
{ return itsSize == 0;
} //======================
public boolean contains (Object ob)
{ for (int k = 0; k < itsSize; k++)
{ if (itsItem[k].equals (ob))
return true;
}
return false;
} //======================
public Object[] toArray()
{ return copyOf (itsItem, 1);
} //======================
// inserted so this compiles due to "implements Collection"
public boolean containsAll (Collection that) {return false;}
public Object[] toArray (Object[] array) {return null; }
public Iterator iterator() {return null; }
public void clear() { }
public boolean add (Object ob) {return false;}
public boolean addAll (Collection that) {return false;}
public boolean remove (Object ob) {return false;}
public boolean removeAll (Collection that) {return false;}
public boolean retainAll (Collection that) {return false;}
/** Internal invariant for ArraySequenceIterators
The instance variable itsSeq is the ArraySequence it iterates through.
The instance variable itsPos is the int such that
itsSeq.itsItem[itsPos+1] contains the element that next() will return,
except next() is illegal when itsPos+1 == itsSeq.itsSize. The instance
variable isRemovable tells whether a call of remove is allowed.
*/
private static class ArraySequenceIterator implements Iterator
{
private int itsPos = -1; // next() is itsItem[itsPos+1]
private boolean isRemovable = false;
private ArraySequence itsSeq;
public ArraySequenceIterator (ArraySequence givenSequence)
{ itsSeq = givenSequence;
} //======================
/** Tell whether there is a next element to be returned. */
public boolean hasNext()
{ return itsPos + 1 < itsSeq.itsSize;
} //======================
/** Advance to the next object to be returned and return it.
* Throw NoSuchElementException if hasNext() is false. */
public Object next()
{ if ( ! hasNext())
throw new NoSuchElementException ("hasNext is false");
isRemovable = true;
itsPos++;
return itsSeq.itsItem[itsPos];
} //======================
/** Remove the object that was just returned by next().
* Throw IllegalStateException if next() has never been
* called, or if next() has not been called since the
* most recent call of remove(). */
public void remove()
{ if ( ! isRemovable)
throw new IllegalStateException ("nothing to remove");
for (int k = itsPos + 1; k < itsSeq.itsSize; k++)
itsSeq.itsItem[k - 1] = itsSeq.itsItem[k];
itsSeq.itsSize--;
itsPos--;
isRemovable = false; // no remove twice in a row
} //======================
}
}
import java.io.*;
import java.util.*;
/* Internal invariant for NodeSequences
If the sequence does not contain any data values, itsFirst is null.
Otherwise itsFirst refers to the first Node in a linked list of Nodes.
For each Node x in that linked list, the value in x.itsData is one
non-null data value in the abstract sequence of data values.
The data values are in the linked list in the same order that they are
in the abstract sequence of data values, with itsFirst containing the
first one (if it exists). The Nodes in one NodeSequence are all
different objects from those in any other.
*/
public class NodeSequence implements Collection
{
private Node itsFirst = null;
/** Create an empty Collection. */
public NodeSequence()
{ super();
} //======================
/** Tell whether ob is an element of this sequence. */
public boolean contains (Object ob)
{ for (Node p = itsFirst; p != null; p = p.itsNext)
{ if (p.itsData.equals (ob))
return true;
}
return false;
} //======================
/** Tell whether every element of that sequence is
* somewhere in this sequence. */
public boolean containsAll (Collection that)
{ for (Node p = ((NodeSequence) that).itsFirst;
p != null; p = p.itsNext)
{ if ( ! this.contains (p.itsData))
return false;
}
return true;
} //======================
/** Return the number of elements in this sequence. */
public int size()
{ int count = 0;
for (Node p = itsFirst; p != null; p = p.itsNext)
count++;
return count;
} //======================
private static class Node
// nested in the NodeSequence class
{
public Object itsData;
public Node itsNext;
public Node (Object data, Node next)
{ itsData = data;
itsNext = next;
} //======================
public void addLater (Object ob)
{ if (itsNext == null)
itsNext = new Node (ob, null);
else
itsNext.addLater (ob);
} //======================
public boolean removeLater (Object ob)
{ if (itsNext == null)
return false;
if (itsNext.itsData.equals (ob))
{ itsNext = itsNext.itsNext;
return true;
}
return itsNext.removeLater (ob);
} //======================
} //======================
/** Tell whether the two sequences have the same elements
* in the same order. */
public boolean equals (Object ob)
{ if ( ! (ob instanceof NodeSequence)) //1
return false; //2
NodeSequence that = (NodeSequence) ob; //3
Node p = this.itsFirst; //4
for (Node q = that.itsFirst; q != null; q = q.itsNext) //5
{ if (p == null || ! p.itsData.equals (q.itsData)) //6
return false; //7
p = p.itsNext; //8
} //9
return p == null; //10
} //======================
/** Create a Collection containing one String for each line
* in the file, in the order they occur in that file.
* Throw an IOException if the file cannot be read. */
public NodeSequence (String fileName) throws IOException
{ BufferedReader file = new BufferedReader //11
(new FileReader (fileName)); //12
String s = file.readLine(); //13
if (s != null) //14
{ this.itsFirst = new Node (s, null); //15
Node previous = this.itsFirst; //16
s = file.readLine(); //17
while (s != null) //18
{ previous.itsNext = new Node (s, null); //19
previous = previous.itsNext; //20
s = file.readLine(); //21
} //22
} //23
} //======================
/** Return a duplicate of that. Precondition: that is not null. */
public NodeSequence (NodeSequence that)
{ if (that.itsFirst != null) //24
{ this.itsFirst = new Node (that.itsFirst.itsData, null);
Node previous = this.itsFirst; //26
for (Node p = that.itsFirst.itsNext; //27
p != null; p = p.itsNext) //28
{ previous.itsNext = new Node (p.itsData, null); //29
previous = previous.itsNext; //30
} //31
} //32
} //======================
/** Create a Collection containing all the values in the given
* array, in the same order. Precondition: given is not null. */
public NodeSequence (Object[ ] given)
{ itsFirst = null;
for (int k = given.length - 1; k >= 0; k--)
{ if (given[k] != null)
itsFirst = new Node (given[k], itsFirst);
}
} //======================
/** Return an iterator that goes through the elements of
* this sequence in an established order. */
public Iterator iterator()
{ return new NodeSequenceIterator (this);
} //======================
/** Internal invariant for NodeSequenceIterators
The instance variable itsSeq is the NodeSequence it iterates through.
The instance variable itsPos is the Node such that
itsPos.itsNext.itsData always contains the element that next() will
return when next() is legal. next() is illegal when itsPos.itsNext
is null. The instance variable itsPrevious is the Node before itsPos
if a call of remove is allowed, otherwise itsPrevious equals itsPos.
*/
private static class NodeSequenceIterator implements ListIterator
{
private Node itsPos; // next() is itsPos.itsNext.itsData
private Node itsPrevious; // == itsPos when remove disallowed
private NodeSequence itsSeq;
public NodeSequenceIterator (NodeSequence givenSequence)
{ itsSeq = givenSequence;
itsPos = new Node (null, itsSeq.itsFirst);
itsPrevious = itsPos; // signals no remove allowed
} //======================
/** Tell whether there is a next element to be returned. */
public boolean hasNext()
{ return itsPos.itsNext != null;
} //======================
/** Advance to the next object to be returned and return it.
* Throw NoSuchElementException if hasNext() is false. */
public Object next()
{ if ( ! hasNext())
throw new NoSuchElementException ("hasNext is false");
itsPrevious = itsPos;
itsPos = itsPos.itsNext; // so now itsPrevious != itsPos
return itsPos.itsData;
} //======================
/** Remove the object that was just returned by next().
* Throw IllegalStateException if next() has never been
* called, or if next() has not been called since the
* most recent call of remove(). */
public void remove()
{ if (itsPrevious == itsPos)
throw new IllegalStateException ("nothing to remove");
itsPrevious.itsNext = itsPos.itsNext;
if (itsSeq.itsFirst == itsPos)
itsSeq.itsFirst = itsPos.itsNext;
itsPos = itsPrevious;
} //======================
/** Replace the object last returned by next(). Throw an
* IllegalStateException if removal is not allowed. */
public void set (Object ob)
{ if (ob == null)
throw new IllegalArgumentException ("no nulls allowed");
if (itsPrevious == itsPos)
throw new IllegalStateException ("nothing to replace");
itsPos.itsData = ob;
} //======================
/** Add the given object just before the element that will be
* returned by next(), or at the end if hasNext() is false.
* Disallow set or remove until next is used again. */
public void add (Object ob)
{ if (ob == null)
throw new IllegalArgumentException ("no nulls allowed");
itsPos.itsNext = new Node (ob, itsPos.itsNext);
itsPos = itsPos.itsNext;
if (itsSeq.itsFirst == itsPos.itsNext)
itsSeq.itsFirst = itsPos;
itsPrevious = itsPos; // so no one can remove it
} //======================
// The following four do not apply to sequences
public boolean hasPrevious() // is there a previous one?
{ throw new UnsupportedOperationException(); }
public Object previous() // return the one before
{ throw new UnsupportedOperationException(); }
public int nextIndex() // index of what next() returns
{ throw new UnsupportedOperationException(); }
public int previousIndex() // index of what previous() returns
{ throw new UnsupportedOperationException(); }
}
/** Same as repeated remove for each element in that
* Collection. */
public boolean removeAll (Collection that)
{ boolean changed = false;
Iterator it = that.iterator();
while (it.hasNext())
changed = this.remove (it.next()) || changed;
return changed;
} //======================
/** Add the given Object at the end of this sequence.
* No effect if the Collection does not allow duplicates.
* Precondition: the parameter is not null. */
public boolean add (Object ob)
{ if (ob == null)
throw new IllegalArgumentException ("no nulls allowed");
if (itsFirst == null)
itsFirst = new Node (ob, null);
else
itsFirst.addLater (ob);
return true; // we accept duplicates of elements
} //======================
/** Remove the first instance of the given object from the
* Collection, if present. */
public boolean remove (Object ob)
{ if (itsFirst == null)
return false;
if (itsFirst.itsData.equals (ob))
{ itsFirst = itsFirst.itsNext;
return true;
}
return itsFirst.removeLater (ob);
} //======================
/** Make the Collection have no elements at all. */
public void clear()
{ itsFirst = null;
} //======================
/** Same as repeated add for each element in sequence. */
public boolean addAll (Collection that)
{ Iterator it = that.iterator();
boolean valueToReturn = false;
while (it.hasNext())
valueToReturn = this.add (it.next()) || valueToReturn;
return valueToReturn;
} //======================
/** Remove every element not in that Collection. Keep the
* original order for those elements that remain. */
public boolean retainAll (Collection that)
{ boolean valueToReturn = false;
while (this.itsFirst != null &&
! that.contains (this.itsFirst.itsData))
{ this.itsFirst = this.itsFirst.itsNext;
valueToReturn = true;
}
if (this.itsFirst != null)
return valueToReturn;
Node p = this.itsFirst;
while (p.itsNext != null)
{ if ( ! that.contains (p.itsNext.itsData))
{ p.itsNext = p.itsNext.itsNext;
valueToReturn = true;
}
else
p = p.itsNext;
}
return valueToReturn;
} //======================
/** Tell whether this sequence has no elements in it. */
public boolean isEmpty()
{ return itsFirst == null;
} //======================
/** Tell how many elements of the Collection equal the parameter. */
public int howManyEqual (Object ob)
{ int count = 0;
for (Node p = this.itsFirst; p != null; p = p.itsNext)
{ if (p.itsData.equals (ob))
count++;
}
return count;
} //======================
/** Return an array filled with the elements of this
* sequence in the same order. */
public Object[] toArray()
{ Object[] valueToReturn = new Object [this.size()];
int count = 0;
for (Node p = this.itsFirst; p != null; p = p.itsNext)
{ valueToReturn[count] = p.itsData;
count++;
}
return valueToReturn;
} //======================
// inserted so this compiles due to "implements Collection"
public Object[] toArray (Object[] array)
{ return null;
}
}
public class LostItems
{
/** List all purchased items not in inventory. */
public static void main (String[] args)
{ java.util.Collection inventory;
java.util.Collection purchased;
try
{ inventory = new ArraySequence ("inven.dat");
purchased = new ArraySequence ("purch.dat");
}catch (java.io.IOException e)
{ throw new RuntimeException ("A file is defective.");
}
if (inventory.equals (purchased))
System.out.println ("a perfect match");
else if ( ! inventory.containsAll (purchased))
{ System.out.println ("Listing all values we lost:");
java.util.Iterator it = purchased.iterator();
while (it.hasNext())
{ Object data = it.next();
if ( ! inventory.contains (data))
System.out.println (data.toString());
}
}
} //======================
}
import java.io.*;
import java.util.*;
public class TwoWaySequence implements Collection
{
private final Node itsHead = new Node (null, null, null);
private static class Node // inside TwoWaySequence
{
public Object itsData;
public Node itsNext;
public Node itsPrevious;
public Node (Object data, Node next, Node previous)
{ itsData = data;
itsNext = next;
itsPrevious = previous;
} //======================
}
public TwoWaySequence()
{ itsHead.itsNext = itsHead;
itsHead.itsPrevious = itsHead;
} //======================
public boolean contains (Object ob)
{ for (Node p = itsHead.itsNext; p != itsHead; p = p.itsNext)
{ if (p.itsData.equals (ob))
return true;
}
return false;
} //======================
public TwoWaySequence (Collection that)
{ itsHead.itsNext = itsHead;
itsHead.itsPrevious = itsHead;
Iterator it = that.iterator();
while (it.hasNext())
{ Node last = itsHead.itsPrevious;
last.itsNext = new Node (it.next(), itsHead, last);
itsHead.itsPrevious = last.itsNext;
}
} //======================
public boolean equals (Object ob)
{ if ( ! (ob instanceof Collection))
return false;
Node p = this.itsHead.itsNext;
Iterator it = ((Collection) ob).iterator();
while (it.hasNext())
{ if (p == this.itsHead || ! p.itsData.equals (it.next()))
return false;
p = p.itsNext;
}
return p == this.itsHead; // != means p has more than it
} //======================
public Iterator iterator()
{ return new TwoWaySequenceIterator (this);
} //======================
private static class TwoWaySequenceIterator implements ListIterator
{
// Internal invariant: itsPos.itsNext is the header node if
// hasNext() is false; otherwise, itsPos.itsNext is the node
// containing the data that next() will return.
private Node itsPos;
private int itsDirection = 0; // signals remove() not allowed
private int itsIndex = -1; // returned by previousIndex()
public TwoWaySequenceIterator (TwoWaySequence given)
{ itsPos = given.itsHead;
} //======================
public boolean hasNext()
{ return itsPos.itsNext.itsData != null;
} //======================
public Object previous()
{ if (itsPos.itsData == null)
throw new NoSuchElementException ("cannot back up");
itsPos = itsPos.itsPrevious;
itsDirection = -1;
itsIndex--;
return itsPos.itsNext.itsData;
} //======================
public void add (Object ob)
{ if (ob == null)
throw new IllegalArgumentException ("no nulls allowed");
itsPos = new Node (ob, itsPos.itsNext, itsPos);
itsPos.itsNext.itsPrevious = itsPos;
itsPos.itsPrevious.itsNext = itsPos;
itsDirection = 0;
itsIndex++;
} //======================
public Object next()
{ if (itsPos.itsNext.itsData == null) //sequence's header node
throw new NoSuchElementException ("already at end");
itsPos = itsPos.itsNext;
itsDirection = 1;
itsIndex++;
return itsPos.itsData;
} //======================
public void remove()
{ if (itsDirection == 0)
throw new IllegalStateException ("cannot remove");
if (itsDirection == 1)
{ itsPos = itsPos.itsPrevious;
itsIndex--;
}
itsDirection = 0; // so it cannot be removed again
itsPos.itsNext = itsPos.itsNext.itsNext;
itsPos.itsNext.itsPrevious = itsPos;
} //======================
public void set (Object ob) { }
public boolean hasPrevious() { return itsIndex >= 0; }
public int nextIndex() { return itsIndex + 1; }
public int previousIndex() { return itsIndex; }
}
public boolean isEmpty()
{ return itsHead.itsNext == itsHead;
} //======================
public int size()
{ int count = 0;
for (Node p = itsHead.itsNext; p != itsHead; p = p.itsNext)
count++;
return count;
} //======================
public boolean add (Object ob)
{ if (ob == null)
throw new IllegalArgumentException ("no nulls allowed");
itsHead.itsPrevious = new Node (ob, itsHead, itsHead.itsPrevious);
itsHead.itsPrevious.itsPrevious.itsNext = itsHead.itsPrevious;
return true;
} //======================
public boolean containsAll (Collection that) { return true; }
public Object[] toArray() { return null; }
public Object[] toArray (Object[] array) { return null; }
public void clear() { }
public boolean addAll (Collection that) { return true; }
public boolean remove (Object ob) { return true; }
public boolean removeAll (Collection that) { return true; }
public boolean retainAll (Collection that) { return true; }
}
|
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved. |