Abstract Classes and Methods

Python

Java

When two or more classes contain redundant code, it can be factored into a common parent class. This class is typically called an abstract class, because it is not instantiated.

Consider two implementations of stacks, ArrayStack and LinkedStack. Their internal containers of elements are different, as are their methods for adding, removing, and iterating through these structures. However, if we assume that each stack tracks its size in the same manner, the methods len and isEmpty will be the same for any implementation. And if we assume that each implementation includes an iter method, then we can implement several other methods, such as str and addAll, just once for all stacks.

class AbstractStack:

def __init__(self):

self.size = 0

def isEmpty(self):

return len(self) == 0

def __len__(self):

return self.size

def __str__(self):

result = ''

for element in self:

result += str(element) + '\n'

return result

def addAll(self, otherIterable):

for element in otherIterable:

self.push(element)

AbstractStack is responsible for initializing just one instance variable, size. Note that the str method uses a for loop over self, which implies that the stack object is iterable. Consequently, each stack implementation must include its own definition of the iter method. Finally, note that the addAll method copies elements from another interable object to the stack, using the push method. Thus, the push method also must be included in each stack implementation.

The first implementation, ArrayStack, includes an init method that allows the programmer to specify an optional iterable object as an argument. If this argument is not None, it is passed to the addAll method to copy its elements to the new stack. addAll can also be called to add several elements at any subsequent point in time. ArrayStack is also responsible for maintaining the sequence of elements. Thus, it includes the definitions of peek, pop, push, and iter.

Example:

class ArrayStack(AbstractStack):

def __init__(self, otherIterable = None):

AbstractStack.__init__(self)

self.items = []

if otherIterable != None:

self.addAll(otherIterable)

def push(self, element):

self.items.append(element)

self.size += 1

def pop(self):

self.size -= 1

return self.items.pop()

def peek(self):

return self.items[-1]

def __iter__(self):

probe = len(self.items) - 1

while True:

if probe < 0:

raise StopIteration

yield self.items[probe]

probe -= 1

The same methods are defined in LinkedStack, but of course they access elements in a very different type of internal structure.

class OneWayNode:

def __init__(self, data, next):

self.data = data

self.next = next

class LinkedStack(AbstractStack):

def __init__(self, otherIterable = None):

AbstractStack.__init__(self)

self.items = None

if otherIterable != None:

self.addAll(otherIterable)

def push(self, element):

self.items = OneWayNode(element, self.items)

self.size += 1

def pop(self):

element = self.items.data

self.items = self.items.next

self.size -= 1

return element

def peek(self):

return self.items.data

def __iter__(self):

probe = self.items

while True:

if probe is None:

raise StopIteration

yield probe.data

probe = probe.next

When two or more classes contain redundant code, it can be factored into a common parent class. This class is typically called an abstract class, because it is not instantiated.

The next example defines an AbstractStack class that includes the information common to all stack implementations. To access these resources, a stack implementation, such as ArrayStack or LinkedStack, simply extends AbstractStack. This class is specified as abstract with the reserved word abstract. The class must also include all of the methods in the TrueStack interface. The methods that must be defined in the subclasses are specified as abstract methods, again with the reserved word abstract.

import java.util.*;

abstract public AbstractStack<E> implements TrueStack<E>{

protected int size, modCount;

public AbstractStack(){

this.size = 0;

this.modCount = 0;

}

public boolean empty(){

return this.size() == 0;

}

public int size(){

return size;

}

public String toString(){

String result = '';

for (E element : this)

result += str(element) + '\n';

return result;

}

public void addAll(Collection<E> col){

for (E element : col)

this.push(element);

}

abstract public E peek();

abstract public E pop();

abstract public void push(E element){

abstract public Iterator<E> iterator();

}

AbstractStack is responsible for initializing two instance variables, size and modCount. Note that the toString method uses a for loop over this, which implies that the stack object is iterable. Consequently, each stack implementation must include its own definition of the iterator method. Finally, note that the addAll method copies elements from any Collection object to the stack. Any Collection object recognizes the iterator method, and thus can be used with a for loop.

The first implementation, ArrayStack, includes two constructors. One allows the programmer to specify a Collection object as an argument. This object is passed to the addAll method to copy its elements to the new stack. addAll can also be called to add several elements at any subsequent point in time. ArrayStack is also responsible for maintaining the sequence of elements. Thus, it includes the definitions of peek, pop, push, and iterator.

import java.util.*;

public class ArrayStack<E> extends AbstractStack<E>{

private List<E> list;

public ArrayStack(){

super();

this.list = new ArrayList<E>();

}

public ArrayStack(Collection<E> col){

this();

this.addAll(col);

}

public E peek(){

if (this.isEmpty())

throw new EmptyStackException();

return list.get(this.size() - 1);

}

public E pop(){

if (this.isEmpty())

throw new EmptyStackException();

this.size -= 1;

this.modCount += 1;

return this.list.remove(this.size());

}

public void push(E element){

this.list.add(element);

this.size += 1;

this.modCount += 1;

}

public Iterator<E> iterator(){

return new StackIterator<E>();

}

private class StackIterator<E> implements Iterator<E>{

private int curPos;

private int curModCount;

private StackIterator(){

this.curPos = this.size() - 1;

this.curModCount = modCount;

}

public boolean hasNext(){

return curPos >= 0;

}

public E next(){

if (! this.hasNext()

throw new IllegalStateException();

if (this.curModCount != modCount)

throw new ConcurrentModificationException()

E data = list.get(this.curPos);

this.curPos -= 1;

return data;

}

public void remove(){

throw new UnsupportedOperationException();

}

The same methods are defined in LinkedStack, but of course they access elements in a very different type of internal structure.

import java.util.iterator;

public class LinkedStack<E> extends AbstractStack<E>{

private OneWayNode<E> items;

public LinkedStack(){

super();

this.items = null;

}

public LinkedStack(Collection<E> col){

this();

this.addAll(col);

}

public void push(E element){

this.items = new OneWayNode<E>(element, items);

this.size += 1;

this.modCount += 1;

}

public E pop(){

E element = this.items.data;

this.items = this.items.next;

this.size -= 1;

this.modCount += 1;

return element;

}

public E peek(){

return this.items.data;

}

public Iterator<E> iterator(){

return new StackIterator<E>();

}

private class StackIterator<E> implements Iterator<E>{

private OneWayNode curPos;

private int curModCount;

private StackIterator(){

this.curPos = items;

this.curModCount = modCount;

}

public boolean hasNext(){

return curPos != null;

}

public E next(){

if (! this.hasNext()

throw new IllegalStateException();

if (this.curModCount != modCount)

throw new ConcurrentModificationException()

E data = this.curPos.data;

this.curPos = this.curPos.next();

return data;

}

public void remove(){

throw new UnsupportedOperationException();

}

private class OneWayNode<E>{

private E data;

private OneWayNode next;

private OneWayNode(E data, OneWayNode next){

this.data = data;

This.next = next;

}

Index