CISC 3130
Data Structures
Building Containers

Overview

• an array type doesn't introduce any new semantics, it's still the same-old homogeneous container with subscripting, just a different element type
• coding a class is diffeent, one aggregates different instance variables and introduces new behavior through the writing of methods
• it is thus the creation of new classes that produces the 'interesting' elements of coding; and in particular building new classes from existing classes

Relationships Among Classes

• independent: no relationship between the classes
• composition: one class contains another class as an instance variable
• inheritance: one class the behavior and state of another class; or one interface inherits the behavior specification of another class

Implementation Approaches / Relationships Among Classes

Independent

• no relationship between the classes

  class Engine {
  	…
  }
  

  class Tire {
  	…
  }
  

• The above two classes bear no relationship to each other; i.e., they share no behavior or logic and neither can use the other for leveraging or delegation.
  • Some other class (e.g. Vehicle could use them both for composition, and even relate them somehow (e.g., the engine specs might impact the choice of tire), but the classes are themselves independent.

Composition

• a class contains another class as an instance variable

  class Engine {
  	…
  }
  		

  class Vehicle {
  	…
  	Engine engine;
  }
  		

• We say that an instance of the 'outer'/'enclosing' class has-a instance of the superclass
  • A Vehicle has-a Engine

Inheritance

• a subclass extends a superclass and inherits its behavior and state

  class Vehicle {
  	…
  }
  		

  class Truck extends Vehicle {
  	…
  }
  		

  • We say that an instance of the subclass is-a instance of the superclass
    • A Truck is-a Vehicle

Interface Inheritance

• a subinterface extends a superinterface and inherits its set of behaviors (methods)
  • in essence, the subinterface is adding implementation requirements to its superinterface

  interface Set<E> {
  	boolean add(E e);
  	boolean remove(E e);;
  	…
  }
  		

  interface SortedSet<E> extends Set<E> {
  	E first();
  	E last();
  	…
  }
  		

  • A class implementing a SortedSet must all the methods of Set as well.
  • We say that an instance of the subclass is-a instance of the superclass
    • A SortedSet is-a Set

Summary

• Classes extend (inherit) classes and are called subclasses and superclasses
• Interfaces extend (inherit) interfaces and are called subinterfaces and superinterfaces
• Classes implement interfaces and are called implementing classes of the interface

An Example: A Counter Class

A Basic Counter

public class counter {
	void up() {val++;}	
	void down() {val--;}	

	int val() {return val;}

	private int val = 0;
}

Independent

public class UpperBoundedCounter {
	UpperBoundedCounter(int limit) {this.limit = limit;} 

	void up() {if (val < limit) val++;}	
	void down() {val--;}	

	int val() {return val;}

	private int val = 0;
	private int limit;
}

Composition

public class UpperBoundedCounter {
	UpperBoundedCounter(int limit) {this.limit = limit;} 

	// New method
	void up() {if (counter.val() < limit) counter.up();}	

	//Delegation methods
	void down() {counter.down();}
	int val() {return counter.val();}

	// Contained/member type
	private Counter counter = new Counter();
	private int limit;
}

Inheritance

public class UpperBoundedCounter extends Counter {
	UpperBoundedCounter(int limit) {this.limit = limit;} 

	// Overridden methods
	void up() {if (val() < limit) super.up();}	

	private int limit;
}

Inheritance of Interfaces

interface Shape {
	int getArea();
}

interface Ovalesque extends Shape {
	getArcLength();
}

interface Quadrilateral extends Shape {
	getDiagonal();
}

class Circle implements Ovalesque {
	double getArea() {…}
	double getArcLength() {…}
}

class Rectangle implements  Quadrilateral {
	int getArea() {…}
	double getDiagonal() {…}
}

The Above In the Context of Containers

What we did in Lecture / Lab 5 is different than any of these three approaches. What we did there was use an existing class as a stack, or queue, or deque, etc, as opposed to creating a stack, queue, deque, etc using some other class. I.e., we used an ArrayList as a stack, or a LinkedList as a deque. WHat we are doing here (an din general when we want a container) is creating a new class (e.g., Stack, Queue, Deque) using another container via composition or inheritance or an altogether independent implementation.

Composition

• Use an underlying container to provide the basic mechanism for the abstraction.
• This will often use delegate-to / leverage the underlying container

class ArrayStack<E> {
	…
	void push(E e) {arrayList.add(e);}		// append
	E pop() {return arrayList.remove(arrayList.size()-1);} // remove last element
	boolean empty() {return arrayList.isEmpty();}
	…
	ArrayList<E> arrayList;
}

Advantages

• attempts to leverage existing functionality
  • the degree of leveraging influences choice of underlying container
• allows selective delegation of underlying container's functionality

Disadvantages

• requires delegation methods (compare to inheritance)

(Class) Inheritance

• Arrange containers in a super/subclass hierarchy

class FifoQueue<E> extends ArrayDeque<E> {}

• We're cheating a bit; the names of the methods being inherited are addLast and removeFirst, rather than add and remove, but we wanted to take the inheritance to its extreme.
  • We probably should have implemented as:

    class FifoQueue<E> extends ArraDeque<E> {
    	void add(E e) {addLast(e);}
    	E remove() {return removeFirst();}
    }
    				

    i.e., using the correct method names for a FIFO queue (despite having to introduce wrapper methods)
• We're also inheriting quite a number of other methods; we'll have more to say about that eventually.

Advantages

• leverages existing functionality to a large degree
• avoids actual delegation methods; functionality is already available through inheritance

Disadvantages

• The is-a relationship is not always valid in these contexts
• No real control over the methods inherited (e.g. removeLast, addFirst in the above example).

(Interface) Inheritance

• Arrange interfaces in a super/subinterface hierarchy
• Java's Collection Framework use this approach extensively

Advantages

• formalizes behavior relationships between classes implementing the interfaces
• is-a is easier to maintain in this context

Disadvantages

• No leveraging or code sharing for the most part (abstract helper classes provide some help here)

Independent

• The container is written in isolation of the others

class Stack<E> {
	Stack() {…}
	void push(E e) {arr[++tos] = e;}
	E pop(E e) {
		if (empty()) throw … 
		return arr[tos--];
	}
	void empty() {return tos == -1;}

	E [] arr;
	int tos = -1;
}

• Notice there is some level of composition in that we do have an underlying array.
• By independent here, we mean that we are not using another container class; rather we're trying to get as low-level as we can to get the most efficient container.

Advantages

• can optimize operation to the specific semantics of the container

Disadvantages

• no leveraging/delegation

Overloading Functions for Specialized Functionality

• add(value) overload for add(size(), value)
  • eliminates the empty shift-loop and makes for a nicely intuitive signature (no location argument necessary)
  • OTOH, this usually means much of the actually add logic is being repeated in both methods. This might be avoided by having that logic reside in a (third) workhorse method, and have the two add method call it.

Code Used in the Lecture