Description
Objectives
-
Getting familiar with Generics in Java programming language
-
Applying them in a Java project to write generic classes, methods, …
-
Full mark: 35 points
Source files
-
GenericStack.java
-
GenericHeap.java
-
GenericRedBlackTree.java
1 Introduction
Generics, or parameterized types, are a facility of generic programming that was added to the Java programming language in 2004 as part of Java 5 (JDK 1.5). They allow “a type or method to operate on objects of various types while providing compile-time type safety”. A common usage of this feature is when using a Java Collection that can hold objects of any type, to specify the specific type of object stored in it. In this lab, we try to address Generics for containers, such as vectors and stacks.
A Java collection (we will explore more in Lab 5) is a flexible data structure that can hold heterogeneous objects where the elements may have any reference type. It is your responsibility, however, to keep track of what types of objects your collections contain. For example, consider adding an integer to a collection: since you cannot have collections of primitive data types you must convert it to the corresponding reference type (i.e. Integer ) before storing it in the collection.
1.1 The Motivation
The motivation for adding generics to the Java programming language stems from the lack of information about a collection’s element type, the need for developers to keep track of what type of elements collections contain, and the need for casts all over the place. Using generics, a collection is no longer treated as a list of object references, but you would be able to differentiate between a collection of references to integers and collection of references to bytes. A collection with a generic type has a type parameter that specifies the element type to be stored in the collection. So, instead of relying on the programmer to keep track of object types and performing casts, which could lead to failures at runtime, the compiler can now help the programmer enforce a greater number of type checks and detect more failures at compile time.
This is a quick example of this application of Generics in the casting problem.
new Foo<Integer>(“I’m a string”);
1.3 Bounded Types
There may be times when you want to restrict the types of the generics. For example, a method that operates on numbers might only want to accept instances of Number or its subclasses. This is what
bounded type parameters are for. To declare a bounded type parameter, list the type parameter’s name, followed by the extends keyword, and then followed by its upper bound, which, in this example, is Number .
Note that in this context, extending is used in a general sense to mean either “extends” (as in classes) or “implements” (as in interfaces).
<T extends SomeSuperClassOrInterface>
Postfix Expression Result
-
Parse the expression string into an array of symbols, and feed them to the stack one by one.
-
If the next symbol is an operand (numbers), then push it to the stack.
-
If the next symbol is an operator, then there must be at least two operands already in the stack. Pop the two operands to do the corresponding calculation, and then re-push the result back to the stack.
-
Repeat through all the symbols.
-
Finally, we have only one element in the stack — it is the final result. Pop and print it out.
DEMO this deliverable to the lab instructor (10 points).
5 Deliverable 2 — Generic Heap
Make your heap sort algorithm generic. Please refer to the GenericHeap.java, and finish the TODO codes.
DEMO this deliverable to the lab instructor (5 points).
6 Deliverable 3 — Generic Red Black Tree
Make your red black tree algorithm generic. Please refer to the GenericRedBlackTree.java, and finish the TODO codes. Note you need also finish the delete method.
DEMO this deliverable to the lab instructor (20 points).
