(Updated January 16, 2025)
Table of contents
-
Overview
The
Cloneable InterfaceThe
Comparable InterfaceGeneric Methods
Generic Classes
Generic Data Structures
Exercises
Overview
Much of the code we have dealt with up to this point has been geared toward a specific data type. For example, a particular method or class is often centered around strings or integers.
Now, this may be useful for some instances, but there comes a time when we have to write a piece of code generically. That is, we need the method or class to accept any data type we pass to it and still perform the actions accurately.
Both methods and classes support handling generic data type. We will start our discussion with two interfaces, Cloneable and Comparable, since these interfaces allow us to override some standard methods of the Object class. By doing so, we gain better support in handling data generically.
The Cloneable Interface
Recall from our discussion of arrays that they can be cloned using the clone() method. This is because the array class implements the Cloneable interface. The clone() method is a protected method of the Object superclass. Recall that all objects are descendants of the Object superclass. This method is protected and does not work for just any class we create or existing in some package. Instead, we must elect to implement the interface and override the clone() method with a public one.
Any attempt to use the clone() method without implementing the interface and overriding the clone() method with a public one will result in the following error:
clone() has protected access in java.lang.Object
Example 1 shows a basic implementation of cloning with the essential details highlighted.
public class CloneEx1 {
public static class MyClass implements Cloneable {
String s; // immutable String
int a, b; // primitive types
public MyClass(String s, int a, int b) {
this.s = s;
this.a = a;
this.b = b;
}
public Object clone() {
MyClass dup;
try {
dup = (MyClass) super.clone();
} catch (CloneNotSupportedException e) {
return null;
}
return dup;
}
}
public static void main(String[] args) {
MyClass orig, copy;
orig = new MyClass("Computer", 6, 24);
copy = (MyClass) orig.clone();
}
}
Example 1: Program to demonstrate the use of clone() method.
The act of cloning returns a field-for-field copy of the data in the object. The clone intends to be a complete duplicate of the information. We need to recognize the difference between a clone and simply using the statement:
copy = orig;That statement only makes copy point to the same object, whereas we wanted an exact duplicate.
In Example 1, since there exists only one String object with the value “Computer” we do not have to worry about an explicit clone of the instance variable s. What if it was not a string but another object like an array? Consider the code in Example 2.
public class CloneEx2 {
public static class MyClass implements Cloneable {
String s; // immutable String
int ia[]; // array class object
public MyClass(String s, int len) {
this.s = s;
ia = new int[len];
}
public Object clone() {
MyClass dup;
try {
dup = (MyClass) super.clone();
dup.ia = (int[]) ia.clone();
} catch (CloneNotSupportedException e) {
return null;
}
return dup;
}
}
public static void main(String[] args) {
MyClass orig, copy;
orig = new MyClass("Grades", 50);
copy = (MyClass) orig.clone();
}
}
Example 2: Program to demonstrate the need for deep copying when cloning an object.
If we did not explicitly clone the ia instance variable, we would have ended up with a copy of the reference to the original array object. We must always be mindful of our objects when implementing clone(); otherwise, we may alter data that is referenced by another object. These can be very time-consuming bugs to resolve.
The Comparable Interface
This Comparable interface allows us to create a compareTo() method to compare two objects properly. Recall that the String class uses a similar method to compare strings and returns a positive, negative or zero value to indicate if a string is greater than, less than, or equal to the other, respectively like so:
String a = "abc", b = "abb";
if (a.compareTo(b) > 0)
System.out.println(“a is greater than b.”);
else if (a.compareTo(b) < 0)
System.out.println(“a is less than b.”);
else
System.out.println(“a and b are equal”);
We will now consider a class that implements both interfaces Cloneable and Comparable. Example 3 demonstrates this with a Time class that represents clock time.
public class Time implements Cloneable, Comparable {
int hours, minutes, seconds;
public Time (int hr, int min, int sec) {
hours = hr;
minutes = min;
seconds = sec;
}
public Object clone() {
Time dup;
try {
dup = (Time) super.clone();
}
catch (CloneNotSupportedException e) {
return null;
}
return dup;
}
public int compareTo(Object otherTime) {
int delta;
Time t = (Time) otherTime;
delta = hours - t.hours;
if (delta != 0)
return delta;
delta = minutes - t.minutes;
if ( delta != 0)
return delta;
return seconds - t.seconds;
}
public boolean equals(Object otherTime) {
Time t = (Time) otherTime;
return hours == t.hours && minutes == t.minutes && seconds == t.seconds;
}
public String toString() {
return String.format("%02d:%02d:%02d", hours, minutes, seconds);
}
}
Example 3: Implementation of the Time class that implements both Cloneable and Comparable interfaces.
Within the Time class, we have stripped much of the checking that would ordinarily be in place. All of the checks for accurate time, including making sure minutes and seconds are in the range of 0-59, and 24-hour representation is in the range of 0-23, would ordinarily be present. This was done to focus on the two interfaces implemented within the class.
The code in Example 3 includes the clone() method and the new compareTo() method. We have also included an equals() method that overrides the equals() method of the Object superclass so that it accurately verifies that two times are equivalent.
The code in Example 3 also has a main() method that exercises the Time class to make certain that clone(), compareTo() and equals() work as expected.
Generic (Parameterized) Methods
Imagine that we need to display a variable list of data. This data could be any primitive type or class. Imagine further that we have several methods to do the same work but specialized to a particular data type. Consider the following display() methods:
public static void display(int ... items) {
for (int x : items)
System.out.print(x + " ");
System.out.println();
}
public static void display(double ... items) {
for (int x : items)
System.out.print(x + " ");
System.out.println();
}
public static void display(String ... items) {
for (int x : items)
System.out.print(x + " ");
System.out.println();
}
The ellipsis (...) indicates we want a variable argument list or varargs. It is used to designate that we may pass one or more items as individual, comma-separated values or as an array of that type like so:
int x, y, z, ia[] = new int[50];
// Sometime later
display(x);
display(z);
display(x, y, z);
display(ia);
Although overloading allows us to create as many methods as we need to deal with all of the possible types we might want to display, it is simply inconvenient to duplicate code in this manner. Using generic methods with type parameter or type variables allows us to simplify this arrangement into a single method as seen here:
public static <T> void display(T ... items) {
for ( T x : items )
System.out.print(x + " ");
System.out.println();
}
The portions of the new display() method with the capital T indicate how the type is to be applied to the method. This is also known as a parameterized method.
- First, the
<T>is the comma-delimited list of type variables used in this method. This is placed just before specifying the return type for the method. - Second, we state that
itemsis a list of references of typeT. Type parameters can only represent references. There is no problem using primitive types since they will be autoboxed for us in JDK5 and later. The exception is an array of a primitive type since each array element is not autoboxed when passed. - Third, the variable
xis of typeTto complete theforeachloop.
It is not uncommon to specify the return type, formal parameters, or local variables using the type parameter. Any combination is allowed. In our display() example, the only item that was not specified by the type variable T is the return type - which is void.
It is essential to realize that we cannot instantiate objects specified by the type parameter. So, although we can declare variables:
T refName;we cannot instantiate the objects:
refName = new T();This is due to type erasure. Type erasure essentially removes all type knowledge at compile time so that there are only items of type Object to manipulate at runtime. This changes slightly if the type is bounded (see below), at which point the type becomes the type specified by the bound.
The program in Example 5 demonstrates using our generic display() method.
public class GenMethod {
@SafeVarargs //For JDK 7 and higher
public static void display(T... items) {
for (T x : items)
System.out.print(x + " ");
System.out.println();
}
public static void main(String[] args) {
Time clock1, clock2;
int x = 10, y = 15;
Integer[] ia = {1, 2, 3, 4, 5};
clock1 = new Time(11, 57, 0); // 11:57:00am
clock2 = new Time(14, 0, 0); // 2:00:00pm
System.out.print("x = ");
display(x);
System.out.print("y = ");
display(y);
System.out.print("x & y = ");
display(x, y);
System.out.print("ia = ");
display(ia);
System.out.print("clock1 & clock2 = ");
display(clock1, clock2);
}
}
Example 4: Program demonstrating a generic method with the Time class from a previous example.
The code in Example 4 also contains an annotation called @SafeVarargs. A warning will be given if parameterized values are used with varargs, which can lead to heap corruption. The details of this are many and can be found here.
We can also restrict the data type we will process in a method by using a bounded type parameter. This is shown in the following:
public static <T extends Comparable<T>> T min(T a, T b) {
if (a.compareTo(b) < 0)
return a;
else
return b;
}
public static <T extends Comparable<T>> T max(T a, T b) {
if (a.compareTo(b) >= 0)
return a;
else
return b;
}
The expression <T extends Comparable<T>> simply sets a different upper bound on what can be used as the type parameter. Normally, this is Object. This states that only those objects that implement the Comparable interface. This is necessary because we are using the compareTo() method, and not all classes implement that method.
Note that we are using extends instead of implements. Ordinarily, we would use implements when specifying an interface like Comparable. Whenever we are setting bounds on the type parameter we always use extends.
public class Bounded {
public static <T extends Comparable<T>> T min(T a, T b) {
if (a.compareTo(b) < 0)
return a;
else
return b;
}
public static <T extends Comparable<T>> T max(T a, T b) {
if (a.compareTo(b) >= 0)
return a;
else
return b;
}
public static void main(String[] args) {
int a = 10, b = 15;
double f = 4.01, g = 3.14;
String s = "ZZZ", t = "abd";
System.out.println(min(a, b) + " is smaller than " + max(a, b));
System.out.println(min(f, g) + " is smaller than " + max(f, g));
System.out.println(min(s, t) + " is smaller than " + max(s, t));
}
}
Example 5: Program to demonstrate a generic method with a bounded type parameter.
The program in Example 5 shows how we can use the new min() and max() bounded generic methods.
In this program, note that the int and double type variables in the main() method are autoboxed before being sent to the min() and max() methods. The output is as follows:
10 is smaller than 15 3.14 is smaller than 4.01 ZZZ is smaller than abd
Generic Classes
Recall our use of checked types when using the Vector class. That is, we place the class type to be stored in the object into <> immediately after the name of the class, such as Vector<String>. We can create generic classes by the same means.
We will now take our Linked_List from a previous discussion and make it generic. Example 7 shows how this can be done. In this example, it is as simple as placing <T> after the class name and then using T for those variables that represent the data type being stored.
public class GenList<T> {
private Node head;
private class Node {
private T data;
private Node next;
private Node(T item) {
data = item;
next = null;
}
}
public GenList() {
head = null;
}
public void insert(T item) {
Node n = new Node(item);
n.next = head;
head = n;
}
public void delete(T item) {
Node cur = head, back = null;
while (cur != null) {
if (cur.data.equals(item)) {
if (back == null)
head = cur.next;
else
back.next = cur.next;
break; // leave the loop
} else {
back = cur;
cur = cur.next; // move to the next node
}
}
}
@Override
public String toString() {
String o = "[";
Node p = head;
// first data value is alone.
if (p != null) {
o += p.data;
p = p.next;
}
// remaining data values have ", value"
while (p != null) {
o += ", " + p.data;
p = p.next;
}
return o + "]";
}
}
Example 6: Class GenList demonstrating a generic class for a linked list.
The programs in Example 7, Example 8 and Example 9 exercise the generic class with the Integer, String and Time classes.
First, we test GenList with Integer as shown in Example 7.
public class TestGenListInt {
public static void main(String[] args) {
GenList<Integer> ll = new GenList<>();
System.out.println("\nAdding 35, 78, 45 and 0 to the list");
ll.insert(35);
ll.insert(78);
ll.insert(45);
ll.insert(0);
System.out.println(ll);
System.out.println("\nRemoving 0 from head of list");
ll.delete(0); // beginning
System.out.println(ll);
System.out.println("\nRemoving 78 from middle of list");
ll.delete(78); // middle
System.out.println(ll);
System.out.println("\nRemoving 35 from end of list");
ll.delete(35); // end
System.out.println(ll);
}
}
Example 7: Program to test GenList with Integer class objects.
The output of Example 7 is show below:
Adding 35, 78, 45 and 0 to the list [0, 45, 78, 35] Removing 0 from head of list [45, 78, 35] Removing 78 from middle of list [45, 35] Removing 35 from end of list [45]
Next, Example 8 uses String to test the GenList class.
public class TestGenListString {
public static void main(String[] args) {
GenList<String> ll = new GenList<String>();
System.out.println("\nAdding Blue, Red, Orange and Green to the list");
ll.insert("Blue");
ll.insert("Red");
ll.insert("Orange");
ll.insert("Green");
System.out.println(ll);
System.out.println("\nRemoving Green from head of list");
ll.delete("Green"); // beginning
System.out.println(ll);
System.out.println("\nRemoving Red from middle of list");
ll.delete("Red"); // middle
System.out.println(ll);
System.out.println("\nRemoving Blue from end of list");
ll.delete("Blue"); // end
System.out.println(ll);
}
}
Example 8: Program to test GenList with String objects.
The output of Example 9 is show below:
Adding Blue, Red, Orange and Green to the list [Green, Orange, Red, Blue] Removing Green from head of list [Orange, Red, Blue] Removing Red from middle of list [Orange, Blue] Removing Blue from end of list [Orange]
public class TestGenListTime {
public static void main(String[] args) {
GenListExample 9: Program to test GenList with Time objects.
The output of Example 9 is shown below:
Adding 11:35:00, 00:00:00, 16:00:00 & 23:59:59 to the list. [23:59:59, 16:00:00, 00:00:00, 11:35:00] Removing 23:59:59 from head of list [16:00:00, 00:00:00, 11:35:00] Removing 00:00:00 from middle of list [16:00:00, 11:35:00] Removing 11:35:00 from end of list [16:00:00]
Generic Data Structures
We discussed Stacks, Queues, and Deques in the previous topic. Below are all those with slight modifications to make them basic generic classes.
Stack
import java.util.EmptyStackException;
public class GenStack<T> {
// the top of the stack
private Node top;
private int size;
private class Node {
private T data;
private Node next;
private Node(T item) {
data = item;
next = null;
}
}
public GenStack() {
top = null;
size = 0;
}
// returns the top value or exception when empty.
public T peek() {
if (isEmpty())
throw new EmptyStackException();
else
return top.data;
}
// push new item on the top
public void push(T item) {
Node n = new Node(item);
n.next = top;
top = n;
size++;
}
// remove item from the top and return the removed value.
public T pop() {
T v;
if (isEmpty())
throw new EmptyStackException();
v = top.data;
top = top.next;
size--;
return v;
}
// debug method to dump the contents of the stack to the screen
public String toString() {
Node p = top;
String s = "";
while (p != null) {
s = s + p.data + "\n";
p = p.next;
}
return s;
}
// method to determine if the stack is empty.
public boolean isEmpty() {
return top == null;
}
// method to return the number of frames
public int size() {
return size;
}
// main method to test the class
public static void main(String[] args) {
GenStack<Integer> s = new GenStack<>();
s.push(7);
s.push(5);
s.push(3);
System.out.println("Stack length is " + s.size());
System.out.println("Stack contains:\n" + s);
while (!s.isEmpty()) {
System.out.println("Popped " + s.pop());
}
// intentially try to pop an empty stack
try {
System.out.println("Popped " + s.pop());
} catch (EmptyStackException e) {
System.out.println("That could have been bad!");
}
}
}
Queue
import java.util.NoSuchElementException;
public class GenQueue<T> {
// the top of the queue
private Node first, last;
private int size;
private class Node {
private T data;
private Node next;
private Node(T item) {
data = item;
next = null;
}
}
public GenQueue() {
first = null;
last = null;
size = 0;
}
// returns the first value or exception when empty.
public T peek() {
if (isEmpty())
throw new NoSuchElementException();
else
return first.data;
}
// enqueue (add) new item on the last
public void enq(T item) {
Node oldlast = last;
last = new Node(item);
if (isEmpty())
first = last;
else
oldlast.next = last;
size++;
}
// dequeue (remove) item from the first of the queue and return the removed value.
public T deq() {
T v;
if (isEmpty())
throw new NoSuchElementException();
v = first.data;
first = first.next;
if (first == null)
last = null;
size--;
return v;
}
// debug method to dump the contents of the queue to the screen
public String toString() {
Node p = first;
String s;
s = "FIRST ->";
while (p != null) {
s = s + " " + p.data + " ";
p = p.next;
}
s = s + "<- LAST\n";
return s;
}
// method to determine if the queue is empty.
public boolean isEmpty() {
return first == null;
}
// method to return the number of queue entries
public int size() {
return size;
}
// main method to test the class
public static void main(String[] args) {
GenQueue<Integer> q = new GenQueue<>();
q.enq(7);
q.enq(5);
q.enq(3);
System.out.print("Queue contains:\n" + q);
System.out.println("Queue length is " + q.size());
while (!q.isEmpty()) {
System.out.println("Dequeued " + q.deq());
}
// intentionally try to deq an empty queue
try {
System.out.println("Dequeued " + q.deq());
} catch (NoSuchElementException e) {
System.out.println("That could have been bad!");
}
}
}
Deque
import java.util.NoSuchElementException;
public class GenDeque<T> {
// the top of the queue
private Node first, last;
private int size;
private class Node {
private T data;
private Node next, prev;
private Node(T item) {
data = item;
next = null;
prev = null;
}
}
public GenDeque() {
first = null;
last = null;
size = 0;
}
// returns the first value or exception when empty.
public T peekFirst() {
if (isEmpty())
throw new NoSuchElementException();
else
return first.data;
}
// returns the last value or exception when empty.
public T peekLast() {
if (isEmpty())
throw new NoSuchElementException();
else
return last.data;
}
// enqueue (add) new item on the last
public void addLast(T item) {
Node oldlast = last;
last = new Node(item);
if (isEmpty())
first = last;
else {
// link up both directions
oldlast.next = last;
last.prev = oldlast;
}
size++;
}
// enqueue (add) new item on the first
public void addFirst(T item) {
Node oldfirst = first;
first = new Node(item);
if (isEmpty())
last = first;
else {
// link up both directions
oldfirst.prev = first;
first.next = oldfirst;
}
size++;
}
// dequeue (remove) item from the first of the queue and return the removed value.
public T removeFirst() {
T v;
if (isEmpty())
throw new NoSuchElementException();
v = first.data;
// advance and null the prev link.
first = first.next;
if (first != null)
first.prev = null;
else
last = null;
size--;
return v;
}
// dequeue (remove) item from the first of the queue and return the removed value.
public T removeLast() {
T v;
if (isEmpty())
throw new NoSuchElementException();
v = last.data;
// advance and null the prev link.
last = last.prev;
if (last != null)
last.next = null;
else
first = null;
size--;
return v;
}
// debug method to dump the contents of the queue to the screen
public String toString() {
Node p = first;
String s;
s = "FIRST ->";
while (p != null) {
s = s + " " + p.data + " ";
p = p.next;
}
s = s + "<- LAST\n";
s = s + "LAST ->";
p = last;
while (p != null) {
s = s + " " + p.data + " ";
p = p.prev;
}
s = s + "<- FIRST\n";
return s;
}
// method to determine if the queue is empty.
public boolean isEmpty() {
return first == null;
}
// method to return the number of queue entries
public int size() {
return size;
}
// main method to test the class
public static void main(String[] args) {
GenDeque<Integer> d = new GenDeque<>();
int x;
d.addLast(7);
d.addLast(5);
d.addLast(3);
d.addFirst(13);
d.addFirst(15);
d.addFirst(17);
System.out.print("Deque contains:\n" + d);
System.out.println("Deque length is " + d.size());
x = 0;
while (x < 3) {
System.out.println("Dequeued from front " + d.removeFirst());
x++;
}
System.out.print("Deque contains:\n" + d);
x = 0;
while (x < 3) {
System.out.println("Dequeued from end " + d.removeLast());
x++;
}
System.out.print("Deque contains:\n" + d);
// intentionally try to deq an empty queue
try {
System.out.println("Dequeued from front " + d.removeFirst());
} catch (NoSuchElementException e) {
System.out.println("That could have been bad!");
}
// intentionally try to deq an empty queue
try {
System.out.println("Dequeued fron end " + d.removeLast());
} catch (NoSuchElementException e) {
System.out.println("That could have been bad!");
}
}
}
Exercises
-
(Beginner) Rewrite Example 5 using ternary operators.