Making your data structure more flexible (with interfaces and parameterized types)

Review: Java Interface (CS171 material -- see: click here)

Interface:

Interface is used to define a specific functionality

An interface contains only method specifications

(I.e., an interface contains only the headers of methods --- no method bodies allowed)

Example:

public interface Map { public Integer get( String key ); public Integer put( String key, Integer value ); public Integer remove( String key ); }

You can define variables with an interface:
You can use an interface variable (x in the above example) to invoke the methods defined in the interface after instantiation (see below)
Example:
You cannot instantiate an object using an interface
This is illegal:
(because an interface is not a class)

Implementating an interface:

An interface is implemented by some class
(Because an interface contains specification (declaration) of methods ---- a class can provide the definitions of methods specified in the interface)

A class that implements an interface must be specified as follows:

public class ClassName implements InterfaceName { ... }

Furthermore: a class that implements an interface must define every method specified in the interface

Example:

public class HashMap implements Map { you must defined these methods: public Integer get( String key ) { ... } public Integer put( String key, Integer value ) { ... } public Integer remove( String key ) { ... } inside this class }

You can use an implementation class to instantiate an interface variable.

Example:

Map x; // Interface variable x = new HashMap(); // Instantiate using implementation class Then: x.get( ... ); will invoke the get() method defined in HahMap !

Polymorphism using interface variables:

The advantage of using interface variables is polymorphism:

Example:

Suppose we have written some program that uses a Map data structure:

public class MyWonderfulClass { public void MyWonderfulMethod( Map x ) // Uses a Map data structure { x.get( ... ); } }

Fact:

The MyWonderfulClass uses the interface Map
The implementation of the Map can still be chosen !!!

We can choose to use a linked list based implementation of Map in the MyWonderfulClass if we instantiate the Map variable as follows:

public class Main { public static void main( String[] args ) { Map M = new ListMap() ; // Map M will use methods in class ListMap ! MyWonderfulClass C = new MyWonderfulClass(); C.MyWonderfulMethod( M ); } } public class ListMap implements Map { ... use linked list to implement: get() put() remove() }

We can choose to use a hash table based implementation of Map in the MyWonderfulClass if we instantiate the Map variable as follows:

public class Main { public static void main( String[] args ) { Map M = new HashMap() ; // Map M will use methods in class HashMap ! MyWonderfulClass C = new MyWonderfulClass(); C.MyWonderfulMethod( M ); } } public class HashMap implements Map { ... use hash table to implement: get() put() remove() }

Parameterized classes (types) Review: Parameterized classes/types (CS171 material -- see: click here)

What is a parameterized type:

Ordinary class definition:

public class ClassName { ... ... }

Parameterized class definition:

public class ClassName< Type1 , Type2 , ... > { ... ... }

The type parameters is used inside the class Classname to define variables.

Example:

Suppose we want to define 2 different types of linked list:

We will need to define 2 different classes:

public class StringListElem { String value; StringListElem next; } public class IntegerListElem { Integer value; IntegerListElem next; } StringListElem head1 = null; <--- start of a linked list of Strings IntegerListElem head2 = null; <--- start of a linked list of Integers

We can accomplish this easier using a parameterized type:

public class ListElem<T> { T value; ListElem next; }

This is a list element that store one value of the type T.

If we want to create a list element that can store a String, we do the following:

ListElem<String> head1 = null; <--- start of a linked list of Strings ListElem<Integer> head2 = null; <--- start of a linked list of Integers

Explanation:

The definition:

ListElem<String> head1 ...
will define a variable of the type: public class ListElem { String value; // T is replaced by String ListElem next; }

Organization of the interfaces and classes

User programs wants (requires ?) certain functionality (data structure) --- the functionality is best specified by an interface:

How to express this in Java:

public class UserProgram { public static void main(String[] args) { Map<String,Integer> M = new ....; // Define a Map variable // to gain access to // the Map functionalities M.put( ... ); M.get( ... ); } }
/* Functionality (= methods) specified by an interface */ public interface Map<K,V> { /** Returns the number of items in the map. */ public int size(); /** Returns whether the map is empty. */ public boolean isEmpty(); /** Puts a given key-value pair in the map, replacing a previous * one, if any, and returns the old value. */ public V put(K key, V value); /** Returns the value associated with a key. */ public V get(K key); /** Removes the key-value pair with a given key. */ public V remove(K key); /** Returns an iterable object containing all the keys in the map. */ public Collection keySet(); /** Returns an iterable object containing all the values in the map. */ public Collection values(); /** Returns an iterable object containing all the entries in the map. */ public Collection<Entry<K,V>> entrySet(); }

Note:

For flexbility sake, you should also define an interface to describe the functionality of the entry (= item) that is stored in the map:

public interface Entry<K,V> { /** Returns the key stored in this entry. */ public K getKey(); /** Returns the value stored in this entry. */ public V getValue(); }

These functionalities (specified by an interface) can be realized using different implementations:

I first showed you an implementation of the Map functionalities using a linked list
Then I showed you the implementation of the same Map functionalities using a hash table

What I want to show you now is how to organize (= write) the Java class using the interfaces above.

Implementing the Map interface using a linked list ("ListMap"):

Relationship between (1) the user program, (2) the interfaces and (3) the implementation classes (using a linked list):
Notice that a ListMap uses ListEntry that contains links (in order to make a linked list !)

How to express this relationship in Java:

/* ==================================================================== To instruct the user program to use the ListMap implementation, we instantiate the Map variable USING the ListMap class ==================================================================== */ public class MyTestListMap { public static void main(String[] args) { Map<String, Integer> M = new ListMap<String, Integer>( ); // Choosing to use the ListMap implementation M.put("a", 1); // Method calls are unchanged ! Integer x = M.get("a"); // Method calls are unchanged ! } }
/* ==================================================================== The implementation (ListMap) class must specify the fact that it implements the Map interface ==================================================================== */ public class ListMap<K, V> implements Map<K, V> { public ListEntry<K, V> head; // This variable contains the linked list public int N; (List based functions that provide functionality for put(), get(), remove() and so on are omitted for brevity) }
/* ==================================================================== The implementation (ListEntry) class must specify the fact that it implements the Entry interface ==================================================================== */ public class ListEntry<K, V> implements Entry<K,V> { private K key; // These variables store (key,value) private V value; public ListEntry<K,V> prev; // These variables make the linked list public ListEntry<K,V> next; // I use double links to make delete easy public ListEntry(K k, V v) { key = k; value = v; prev = null; next = null; } public K getKey() { return key; } public V getValue() { return value; } }

Example Program: (Demo above code)
- Test program (this represent the user program): click here
- The Map interface: click here
- The Entry interface: click here
- The Map implementation using linked list: click here
- The Entry implementation (ListEntry): click here
How to run the program:

Implementing the Map interface using a hash table ("HashMap"):

Relationship between (1) the user program, (2) the interfaces and (3) the implementation classes (using a hash table):
Notice that a HashMap uses a HashEntry that does not contains links !!!!

How to express this relationship in Java:

/* ==================================================================== To instruct the user program to use the HashMap implementation, we instantiate the Map variable USING the HashMap class ==================================================================== */ public class MyTestHashMap { public static void main(String[] args) { Map<String, Integer> M = new HashMap<String, Integer>( ); // Choosing to use the HashMap implementation M.put("a", 1); // Method calls are unchanged ! Integer x = M.get("a"); // Method calls are unchanged ! } }
/* ==================================================================== The implementation (HashMap) class must specify the fact that it implements the Map interface ==================================================================== */ public class HashMap<K, V> implements Map<K, V> { public HashEntry<K,V>[] bucket; // This is the hash table public int capacity; // capacity == bucket.length public int NItems; // NItems = # entries in hash table public int MAD_p; // These variables are used to public int MAD_a; // implement the MAD compression public int MAD_b; // function (Hashing) (Hash based functions that provide functionality for put(), get(), remove() and so on are omitted for brevity) }
/* ==================================================================== The implementation (HashEntry) class must specify the fact that it implements the Entry interface ==================================================================== */ public class HashEntry<K, V> implements Entry<K,V> { private K key; // These variables store (key,value) private V value; // Notice: no links !!! public HashEntry(K k, V v) { key = k; value = v; } public K getKey() { return key; } public V getValue() { return value; } }

Example Program: (Demo above code)
- Test program (this represent the user program): click here
- The Map interface: click here (this is the same file as above !)
- The Entry interface: click here (this is the same file as above !)
- The Map implementation using hash table: click here
- The Entry implementation (HashEntry): click here
How to run the program: