In developing the code for the class ExtendedDerivedArrayStack
we adopt a strategy that does not access the data members of the class
ArrayLinearList.
Adopting this strategy means that changes in the implementation
of
ArrayLinearList do not require us to
make any changes to the class
ExtendedDerivedArrayStack. At the same time,
this strategy results in code that is less efficient than
code that directly accesses the data members of
ArrayLinearList. The nature
of the more efficient code that is possible when direct access
is made to the data members of
ArrayLinearList is illustrated by
our implementation of ExtendedArrayStack.
The code for the class ExtendedDerivedArrayStack is:
public class ExtendedDerivedArrayStack extends DerivedArrayStack
implements ExtendedStack
{
// constructors
/** create a stack with the given initial capacity */
public ExtendedDerivedArrayStack(int initialCapacity)
{super(initialCapacity);}
/** create a stack with initial capacity 10 */
public ExtendedDerivedArrayStack()
{this(10);}
// methods of ExtendedStack
// methods size() and toString() are inherited from ArrayLinearList
/** input a stack from the input stream inStream using
* the method inputMethod to input each element */
public void input(Method inputMethod, MyInputStream inStream)
{
// first empty the stack
for (int i = size() - 1; i >= 0; i--)
remove(i);
// input size of new stack
System.out.println("Enter number of elements in stack");
int s = inStream.readInteger();
if (s < 0)
throw new MyInputException
("stack size must be >= 0");
// input the stack elements bottom to top
Object [] inputMethodArgs = {inStream};
System.out.println("Enter stack elements from bottom to top");
try
{
for (int i = 0; i < s; i++)
add(i, inputMethod.invoke(null, inputMethodArgs));
}
catch (Exception e)
{
System.out.println(e);
throw new IllegalArgumentException
("input method for stack element type is incorrect");
}
}
/** split the stack this into the stacks a and b
* a gets the bottom-half elements, b gets the rest */
public void split(ExtendedStack a, ExtendedStack b)
{
// first emty out a and b
for (int i = a.size() - 1; i >= 0; i--)
((ExtendedDerivedArrayStack) a).remove(i);
for (int i = b.size() - 1; i >= 0; i--)
((ExtendedDerivedArrayStack) b).remove(i);
// put bottom-half elements into a
int halfSize = size() / 2;
for (int i = 0; i < halfSize; i++)
((ExtendedDerivedArrayStack) a).add(i, get(i));
// put remaining elements into b
for (int i = halfSize; i < size(); i++)
((ExtendedDerivedArrayStack) b).add(i - halfSize, get(i));
}
/** set the stack this to contain the elements in a
* followed by those in b */
public void combine(ExtendedStack a, ExtendedStack b)
{
// first emty out this
for (int i = size() - 1; i >= 0; i--)
remove(i);
// put elements of a into this
for (int i = 0; i < a.size(); i++)
add(i, ((ExtendedDerivedArrayStack) a).get(i));
// put elements of b into this
for (int i = 0; i < b.size(); i++)
add(a.size() + i, ((ExtendedDerivedArrayStack) b).get(i));
}
}
The code for the class ExtendedArrayStack is:
public class ExtendedArrayStack extends ArrayStack
implements ExtendedStack
{
// constructors
/** create a stack with the given initial capacity */
public ExtendedArrayStack(int initialCapacity)
{super(initialCapacity);}
/** create a stack with initial capacity 10 */
public ExtendedArrayStack()
{this(10);}
// methods of ExtendedStack
/** @return number of elements in the stack */
public int size()
{return top + 1;}
/** input a stack from the input stream inStream using
* the method inputMethod to input each element */
public void input(Method inputMethod, MyInputStream inStream)
{
// input size of new stack
System.out.println("Enter number of elements in stack");
int s = inStream.readInteger();
if (s < 0)
throw new MyInputException
("stack size must be >= 0");
// increase array size if necessary
if (s > stack.length)
stack = new Object [s];
// input the stack elements bottom to top
Object [] inputMethodArgs = {inStream};
System.out.println("Enter stack elements from bottom to top");
try
{
for (int i = 0; i < s; i++)
stack[i] = inputMethod.invoke(null, inputMethodArgs);
}
catch (Exception e)
{
System.out.println(e);
throw new IllegalArgumentException
("input method for stack element type "
+ "is incorrect");
}
top = s - 1;
}
/** convert to a string */
public String toString()
{
StringBuffer s = new StringBuffer("[");
if (top >= 0)
{// nonempty stack
// do first element
s.append(stack[0].toString());
// do remaining elements
for (int i = 1; i <= top; i++)
s.append(", " + stack[i].toString());
}
s.append("]");
// create equivalent String
return new String(s);
}
/** split the stack this into the stacks a and b
* a gets the bottom-half elements, b gets the rest */
public void split(ExtendedStack a, ExtendedStack b)
{
// determine size of resulting stacks a and b
int sizeOfA = size() / 2;
int sizeOfB = size() - sizeOfA;
// cast a and b into ExtendedArrayStacks
ExtendedArrayStack aa = (ExtendedArrayStack) a;
ExtendedArrayStack ab = (ExtendedArrayStack) b;
// make sure array sizes are adequate
if (sizeOfA > aa.stack.length)
aa.stack = new Object [sizeOfA];
if (sizeOfB > ab.stack.length)
ab.stack = new Object [sizeOfB];
// put bottom-half elements into a
for (int i = 0; i < sizeOfA; i++)
aa.stack[i] = stack[i];
aa.top = sizeOfA - 1;
// put remaining elements into b
for (int i = sizeOfA; i <= top ; i++)
ab.stack[i - sizeOfA] = stack[i];
ab.top = sizeOfB - 1;
}
/** set the stack this to contain the elements in a
* followed by those in b */
public void combine(ExtendedStack a, ExtendedStack b)
{
// cast a and b into ExtendedArrayStacks
ExtendedArrayStack aa = (ExtendedArrayStack) a;
ExtendedArrayStack ab = (ExtendedArrayStack) b;
// make sure array size is adequate
top = aa.top + ab.top + 1; // new top of this
if (top >= stack.length)
stack = new Object [top + 1];
// put elements of a into this
for (int i = 0; i <= aa.top; i++)
stack[i] = aa.stack[i];
// put elements of b into this
for (int i = 0; i <= ab.top; i++)
stack[i + aa.top + 1] = ab.stack[i];
}
}