Programming Assignment # 1 Implementing and Using Lists Solution

$35.00 $30.80

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:

 

 

 

 

 

 

CSC 212 PA # 1

 

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.

 

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

 

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

 

 

 

CSC 212 PA # 1

 

4

 

 

 

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

 

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

 

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

 

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