Inheritance and Defining Subclasses

Subclassing is a convenient way to provide extra or more specialized functionality to an existing resource.  For example, a queue guarantees access to its elements in first-in, first-out order.  A priority queue behaves in most respects just like a queue, except that the higher priority elements are removed first.  If elements have equal priority, they are removed in standard FIFO order.  A priority queue is thus a subclass of queue, with a specialized method for insertions that guarantees the appropriate ordering of elements.  The priority queue obtains all of its other methods from the queue class for free.

Here is the definition of a LinkedQueue class for ordinary queues:

class OneWayNode:

    def __init__(self, data, next):
        self.data = data
        self.next = next

class LinkedQueue:

    def __init__(self):
        self.front = self.rear = None
        self.size = 0

    def enqueue(self, element):
        n = OneWayNode(element, None)
        if self.isEmpty():
            self.rear = self.front = n
        else:
            self.rear.next = n
            self.rear = n
        self.size += 1

    def dequeue(self):
        element = self.front.data
        self.front = self.front.next
        self.size -= 1
        if self.isEmpty():
            self.rear = None
        return element

    def peek(self):
        return self.front.data

    def isEmpty(self):
        return len(self) == 0

    def __len__(self):
        return self.size

The form for defining a subclass is

class <subclass name>(<parent class name>):

    <variables and methods>

The LinkedPriorityQueue class is a subclass of LinkedQueue.  The new class includes just two methods, __init__ and enqueue.  The __init__method in LinkedPriorityQueue simply calls the same method in its parent class, using the form

<parent class name>.__init__(self)

This causes the parent class to initialize its instance variables.

The new enqueue method first checks for an empty queue and if that is true, calls the enqueue method in the parent class using the form
<parent class name>.<method name>(<args>)

Otherwise, the method searches for the appropriate position of the new element and inserts it there.  Because the front of the queue is at the head of the linked structure, the search stops when the incoming element is strictly less than element in the queue.  Thus, an incoming element is placed behind all elements of equal priority.

Here is the definition of LinkedPriorityQueue:

class LinkedPriorityQueue(LinkedQueue):

    def __init__(self):
        LinkedQueue.__init__(self)

    def enqueue(self, element):
        if self.isEmpty():
            LinkedQueue.enqueue(self, element)
        else:
            probe = self.front
            while probe != None and element >= probe.data:
                trailer = probe
                probe = probe.next
            if probe == None:            # At rear of queue
                self.rear.next = OneWayNode(element, None)
                self.rear = self.rear.next
            elif probe == self.front:    # At front of queue
                self.front = Node(element, self.front.next)
            else:                        # Betwixt two nodes
                trailer.next = Node(element, probe)
            self.size += 1

Subclassing is a convenient way to provide extra or more specialized functionality to an existing resource.  For example, a queue guarantees access to its elements in first-in, first-out order.  A priority queue behaves in most respects just like a queue, except that the higher priority elements are removed first.  If elements have equal priority, they are removed in standard FIFO order.  A priority queue is thus a subclass of queue, with a specialized method for insertions that guarantees the appropriate ordering of elements.  The priority queue obtains all of its other methods from the queue class for free.

The LinkedQueue class makes its instance variables visible to subclasses but not to others by declaring them as protected.  Likewise, the inner OneWayNode class and its attributes are also defined as protected.

Here is the definition of a LinkedQueue class for ordinary queues:

import java.util.*;

public class LinkedQueue<E> implements TrueQueue<E>{

    protected OneWayNode<E> front, rear;
    Protected int size;

    public LinkedQueue(){
      this.front = this.rear = null;
      this.size = 0;
    }

    public void enqueue(E element){
        OneWayNode<E> n = OneWayNode<E>(element, null);
        if (this.isEmpty())
            this.rear = this.front = n;
        else{
            this.rear.next = n;
            this.rear = n;
        }
        this.size += 1;
    }

    public E dequeue(){
        E element = this.front.data;
        this.front = this.front.next;
        this.size -= 1;
        if (this.isEmpty())
            this.rear = null;
        return element;
    }

    public E peek(){;
      return this.front.data;
    }

    public boolean isEmpty(){
      return this.size() == 0;
    }

    public int size(){
      return this.size == 0;
    }

    protected class OneWayNode<E>{

        protected E data;
        protected OneWayNode<E> next;

        protected OneWayNode(E data, OneWayNode next){
            this.data = data;
            this.next = next;
        }
    }
}

The form for defining a subclass is

public class <subclass name> extends <parent class name>{

    <variables and methods>
}

The LinkedPriorityQueue class is a subclass of LinkedQueue.  The new class includes a constructor and the enqueue method.  The constructor in LinkedPriorityQueue is optional, but explicitly calls the constructor in its parent class, using the statement

super();

This causes the parent class to initialize its instance variables.

The new enqueue method first checks for an empty queue and if that is true, calls the enqueue method in the parent class using the form

super.<method name>(<args>)

Otherwise, the method searches for the appropriate position of the new element and inserts it there.  Because the front of the queue is at the head of the linked structure, the search stops only when the incoming element is strictly less than element in the queue.  Thus, an incoming element is placed behind all elements of equal priority.

Elements in a priority queue must be comparable.  Therefore, the element type of the LinkedPriorityQueue class is specified as Comparable.  The syntax for relating the element types of LinkedPriorityQueue and LinkedQueue in the class header is a bit tricky, but gets the job done.

Here is the definition of LinkedPriorityQueue:

import java.util.*;

public class LinkedPriorityQueue<E extends Comparable>
                                extends LinkedQueue<E>{

    public LinkedPriorityQueue(){
       super();
    }

    public void enqueue(E element){
       if (this.isEmpty())
           super.enqueue(element);
        else{
            OneWayNode<E> probe = this.front;
            OneWayNode<E> trailer = null;
            while (true){
                if (probe == null ||
                    element.compareTo(probe.data) < 0)
                    break;
                trailer = probe;
                probe = probe.next;
            }
            if (probe == null)                   # At rear of queue
                this.rear.next = new OneWayNode<E>(element, null);
                this.rear = this.rear.next;
            else if (probe == this.front)        # At front of queue
                this.front = new OneWayNode<E>(element, this.front.next);
            else                                 # Betwixt two nodes
                trailer.next = new OneWayNode<E>(element, probe);
            this.size += 1;
        }
    }
}