Lab 5: Java Collection Framework, Skip List and Apache ANT Solution

Objectives

    • Getting familiar with Java collection framework

    • Getting familiar with skip list

    • Compile and run the code using Apache ANT

    • Full mark: 25 points


Source files

    • SkipList.java

    • build.xml


1 Collections

A collection (sometimes called a container) is simply an object that groups multiple elements into a single unit. Collections are used to store, retrieve, manipulate, and communicate aggregate data. Typically, they represent data items that form a natural group, such as a poker hand (a collection of cards), a mail folder (a collection of letters), or a telephone directory (a mapping of names to phone numbers).

A collection framework is a unified architecture for representing and manipulating collections. All collection frameworks contain the following:

    • Interfaces: These are abstract data types that represent collections. Interfaces allow collections to be manipulated independently of the details of their representation. In object-oriented languages, interfaces generally form a hierarchy.

    • Implementations: These are the concrete implementations of the collection interfaces. In essence, they are reusable data structures.

    • Algorithms: These are the methods that perform useful computations, such as searching and sorting, on

objects that implement collection interfaces. The algorithms are said to be polymorphic: that is, the same method can be used on many different implementations of the appropriate collection interface. In essence, algorithms are reusable functionality.


--------------------------------------------------------------------------------

| -------------------------------------------------------





------------------- |
| |

--------------


|
|
-------
| |
| |

| Collection |

|
|
| Map |
| |
| |

--------------


|
|
-------
| |
| |
+-----------
+-----
+------
+------------
+
|  |
-------------
| |
| |
-------
---------
---------
---------
|
|
| SortedMap |
| |
| |
| Set |
| List
|
| Queue |
| Deque |
|
|
-------------
| |
| |
-------
---------
---------
---------
|
|

| |
| |
|




|
|

| |
| |
-------------




|
|

| |
| |
| SortedSet |




|
|

| |
| |
-------------




|
|

| |
| -------------------------------------------------------





------------------- |
--------------------------------------------------------------------------------
The core collection interfaces encapsulate different types of collections, which are shown in the figure below. These interfaces allow collections to be manipulated independently of the details of their representation. Core collection interfaces are the foundation of the Java Collections Framework. Note that all the core collection interfaces are generic.

2 Skip Lists

Skip lists are designed to overcome the basic limitations of array-based and linked lists -- either search or update operations require linear time. It is also an example of a probabilistic data structure, because it makes some of its decisions at random.


As balanced trees (an example is the red black tree) have been used to efficiently implement Set and HashMap style data structures, skip list can be an alternative solution. Traditional balanced tree algorithms require continually rebalancing the tree, while skip list provides improved constant time overhead. Besides, search, insert and deletion are rather simple to understand and implement.


In a traditional linked list, each node contains one pointer to the next node. However, a node in a skip list contains an array of pointers. The size of this array, also called the level of the node, is chosen at random at the time when the node is created. For example, a level 3 node has 3 forward pointers, indexed from 0 to
    2. The pointer at index 0 (called the level 0 forward pointer) always points to the immediate next node in the list, and the other pointers point to further nodes. A level i pointer points to the next node in the list that satisfy level >= i . Level of the skip list equals to the max level of all its nodes.


---




----






--
2
| |===========================>|
|===================================>||

|-|

----

|--|

----

----
||
1
| |===========>|
|===========>|
|===========>|
|===========>|
|===>||

|-|
----
|--|
----
|--|
----
|--|
----
|--|
||
0
| |===>|  |===>|
|===>|  |===>|
|===>|  |===>|
|===>|  |===>|
|===>||

---
----
----
----
----
----
----
----
----
--

head
5

25
30

31
42

58
62

69
null

















3 Apache ANT

A defined build process is one of the most necessary tools in the software development process, ensuring that the software you produce is built to the required specifications. You should establish, document, and automate the exact series of steps required to correctly build your product.

A defined build process helps close the gap between the development, integration, test and production environments. A build process alone will speed the migration of software from one environment to another. It also removes many issues related to compilation, library paths, or properties that cost many projects considerable time and money.

From this, ANT (originally an acronym for "Another Neat Tool"), a Java-based build tool with special support for Java programming language, has emerged. It helps programmers to build complex applications and place the files in the desired location with less effort. ANT executes different tasks using Java classes and XML-based configuration files.

An ANT build file comes in the form of an XML document. All you need is a simple text editor to edit an ANT build file. The ANT installation comes with a JAXP-compliant XML parser, which means the
installation of an external XML parser is not necessary. The parser checks that the syntax of your ANT file is correct in a similar fashion to javac which checks the syntax of your Java code.



4 Deliverable 1 -- Skip List

Please refer to SkipList.java. For this lab assignment, you need to explore the Java Collections Framework to write a skip list class.


Note: it is acceptable if you use the ArrayList or Vector to store elements. However, remember a skip list

is a linked list -- this means the only element that can be directed accessed is the head, and you have to travel through elements to find the one you need. Elements in ArrayList or Vector can be accessed by


indexes.

DEMO this deliverable to the lab instructor (20 points).


5 Deliverable 2 -- ANT Build File

In this step, you need to compile and run your code using ANT.

Step 1:


Copy and paste your source code (all java files) into src folder in your home directory.

Step 2:


Consider the sample ANT build file build.xml. Put it in the same directory with your src






folder.

If you focus on each of the target tags, you can see how the targets are strung together by a series of dependant attributes. We can see that jar depends on compile , and run depends on jar . What does this mean? Well, if we tell ANT to make the project by target run , then it will automatically perform compile first, and then jar , and finally run .


Step 3:

Now I know about ANT, what do I need to do to allow the following commands to complete successfully?


$ ant -projecthelp
$ ant compile

$ ant jar

$ ant run

ANT can dramatically reduce the overhead related to compiling, archiving and executing your projects.

Step 4:


Change the default target for this build file. Change the default="compile" to default="run" , and then run:


$ ant run

Now by default, when you execute ANT, it will automatically compile, build a jar file and execute the code.

DEMO this deliverable to the lab instructor (5 points).