ECE325-Lab 5 Java Collection Framework, Skip List and Apache ANT Solved

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.

Set
HashMap
As balanced trees (an example is the red black tree) have been used to efficiently implement  and  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 leveli 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

javac
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  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.

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

ArrayList
 or
Vector
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  can be accessed by



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:

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

Step 2:

src
Consider the sample ANT build file build.xml. Put it in the same directory with your  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

jar
, and finally
run
mean? Well, if we tell ANT to make the project by target first, and then .

Step 3:
 

run
 
, then it will automatically perform
 

compile
 
 
 
 
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