Programming Assignment # 1 Implementing and Using Lists Solution

Description

The goal of this assignment is to implement and use the ADT List. The assignment is divided into two parts. In the rst part, you will implement the ADT List with additional operations using linked and array representations. In the second part, you will write methods that use these implementations to store and query information about movies.

• Implementing List

Write two classes ArrayList and LinkedList that implement the interface List below. You may use code from the lecture notes for the methods similar to those discussed in class.

p u b l i c	i n t e r f a c e List <T > {
boolean		empty () ;
boolean		full () ;
void	fi nd Fi rs t () ;
void	findNext () ;
boolean		last () ;

• retrieve () ; void update ( T e ) ; void insert ( T e ) ; void remove () ;

• • Searches for the first element that sa ti sf ie s a co nd it io n . If found , it is set as current and true is returned , ot he rw is e current

remains un ch an ge d and false is returned . The co nd it io n is tested using cnd .

boolean f i n d F i r s t E l e ( Cond <T > cnd ) ;

• Searches and returns all elements that satisfy a co nd it io n . If none is found , the empty list is returned . This method does not change current . The co nd it io n is tested using cnd .

List <T > f i n d A l l E l e ( Cond <T > cnd ) ;

}

The interface Cond is given below:

p u b l i c i n t e r f a c e Cond <T > {

• Return true if e sa ti sf ie s the co nd it io n . boolean test ( T e ) ;

}

2

Example 1.1. If you want to search for the rst occurence of a given string in a list of strings, you can proceed as follows. First write the following implementation of the interface Cond:

p u b l i c c l a s s S t r i n g E q u a l C o n d implements Cond < String > { p r i v a t e String str ;

p u b l i c S t r i n g E q u a l C o n d ( String str ) {

t h i s . str = str ;

}

@ Ov er ri de

p u b l i c boolean test ( String s ) {

return str . equals ( s ) ;

}

}

You can the use it to serach for “hello” as follows:

p u b l i c c l a s s S e a r c h H e l l o {

p u b l i c s t a t i c void main ( String [] args ) {

List < String > l = new LinkedList < String >() ;

l . insert ( ” cat ” ) ;

l . insert ( ” hello ” ) ;

l . insert ( ” dog ” ) ;

S t r i n g E q u a l C o n d cnd = new S t r i n g E q u a l C o n d ( ” hello ” ) ; System . out . println ( l . f i n d F i r s t E l e ( cnd ) ) ; // prints true

}

}

• Using List

Information about movies is stored in the class Movie:

p u b l i c c l a s s Movie {

p u b l i c i n t id ;

p u b l i c String title ;

p u b l i c List < String > genres ;

p u b l i c Movie ( i n t id , String title , List < String > genres ) {

t h i s . id = id ;

t h i s . title = title ;

t h i s . genres = genres ;

}

}

Note that IDs are unique but not titles and genres.

Example 2.1. This is an example of using the class Movie:

List < String > genres = new LinkedList < String >() ; genres . insert ( ” A dv en tu r e ” ) ; genres . insert ( ” A ni ma ti o n ” ) ;

genres . insert ( ” Children ” ) ;

genres . insert ( ” Comedy ” ) ;

genres . insert ( ” Fantasy ” ) ;

movies . insert (new Movie (1, “Toy Story (1995) “, genres ));

We want to write the following class that answers queries about movies:

3

p u b l i c c l a s s M o v i e U t i l s {
// Return		the	movie with the given id if found , null ot he rw is e .
p u b l i c	s t a t i c		Movie f i n d M o v i e B y I d ( List < Movie > movies , i n t id ) {
return n u l l ;
}
// Return the list of movies having a given title . If none is found ,
empty list is returned .
p u b l i c	s t a t i c		List < Movie > f i n d M o v i e B y T i t l e ( List < Movie > movies ,	String
title )		{
return n u l l ;
}
// Return		the list of movies of a given genre . If none is found , empty
list	is	returned .
p u b l i c	s t a t i c		List < Movie > f i n d M o v i e s B y G e n r e ( List < Movie > movies ,	String
genre )		{
return n u l l ;
}
// Return the list of movies of given genres ( a movie must have all
genres to be in the list ) . If none is found , empty list is returned .
Assume		genres is not empty .
p u b l i c	s t a t i c		List < Movie > f i n d M o v i e s B y G e n r e s ( List < Movie > movies , List <
String >		genres ) {
return n u l l ;
}
}

Example 2.2. An example of using the class MovieUtils can be found in the class Main attached to this assignment.

3 Deliverable and rules

You must deliver:

1. Source code submission to Web-CAT. You have to upload the following classed in a zipped le in addition to any other classes you need:

LinkedList.java ArrayList.java MovieUtils.java

Notice that you should not upload the interfaces List, Cond and the classes Movie, Main.

The submission deadline

You have to read and follow the following rules:

1. The speci cation given in the assignment (class and interface names, and method signatures) must not be modi ed. Any change to the speci cation results in compilation errors and consequently the mark zero.

2. All data structures used in this assignment must be implemented by the student. The use of Java collections or any other data structures library is strictly forbidden.

3. This assignment is an individual assignment. Sharing code with other students will result in harsh penalties.

4

4. Posting the code of the assignment or a link to it on public servers, social platforms or any communication media including but not limited to Facebook, Twitter or WhatsApp will result in disciplinary measures against any involved parties.

4. The submitted software will be evaluated automatically using Web-Cat.

4. All submitted code will be automatically checked for similarity, and if plagiarism is con-rmed penalties will apply.

4. You may be selected for discussing your code with an examiner at the discretion of the teaching team. If the examiner concludes plagiarism has taken place, penalties will apply.

CSC 212 PA # 1