You cannot submit for this problem because the homework's deadline is due.

Ex.1 List

Related Topics: ADT, list.

Li, an expert programmer, has implemented his own "list". Knowing that you are taking VE280, he asks for your help to test his "list". He provides you some starter files for this "list" and asks you to implement some functions using his "list".

A "list" is a sequence of zero or more numbers in no particular order. A list is well-formed if:

a) It is the empty list, or

b) It is an integer followed by a well‐formed list.

A list is an example of a linear‐recursive structure: it is "recursive" because the definition refers to itself. It is "linear" because there is only one such reference.

Here are some examples of well‐formed lists:

( 1 2 3 4 ) // a list of four elements
( 1 2 4 ) // a list of three elements
( ) // a list of zero element---the empty list

The file recursive.h defines the type list_t and the following operations on lists:

bool list_isEmpty(list_t list);
   // EFFECTS: returns true if list is empty, false otherwise

list_t list_make();
   // EFFECTS: returns an empty list.

list_t list_make(int elt, list_t list);
   // EFFECTS: given the list make a new list consisting of
   //          the new element followed by the elements of the
   //          original list. 

int list_first(list_t list);
   // REQUIRES: list is not empty
   // EFFECTS: returns the first element of list

list_t list_rest(list_t list);
   // REQUIRES: list is not empty
   // EFFECTS: returns the list containing all but the first element of list

void list_print(list_t list);
    // MODIFIES: cout
    // EFFECTS: prints list to cout.

They are implemented in recursive.cpp for you, what you need to do is to implement the functions declared in ex1.h.

int dot(list_t v1, list_t v2);
// REQUIRES: Both "v1" and "v2" are non-empty
//
// EFFECTS: Treats both lists as vectors. Returns the dot
//          product of the two vectors. If one list is longer
//          than the other, ignore the longer part of the vector.

list_t filter(list_t list, bool (*fn)(int));
// EFFECTS: Returns a list containing precisely the elements of "list"
//          for which the predicate fn() evaluates to true, in the
//          order in which they appeared in list.
//
//          For example, if predicate bool odd(int a) returns true
//          if a is odd, then with input ( 3 4 1 5 6 ) and bool odd(int a),
//          you would get the list ( 3 1 5 ).

bool is_palindrome_list(list_t list);
// EFFECTS: Returns if the list is a palindrome list, which means the list
//          reads the same both ways. An empty list and a list containing only 
//          one element is still considered as a palindrome list.
//
//          For example, ( 32 32 4 1 4 32 32 ) is a palindrome list, while 
//          ( 23 4 1 4 32 ) is not a palindrome list.

Hint

You can think in the way that recursive.h provides an ADT for you and you need to implement the new functions declared in ex1.h using the methods provided.

Problem

1. Implement the functions in ex1.cpp.

Requirements

1. If you define any helper functions yourself, be sure to declare them "**static**", so that they are not visible outside this file.

Testing

Since you are only required to implement new methods, there is no IO requirements. You need to design your own test cases to get full score.