This is an initial draft, and it may change! A notice on the class web page will be posted after each revision, so please check class notice board frequently.

Change log:

• (v4) if a call to next, prev, findNext or findPrevious is not successful, cursor is not moved from the current position. For v4, see text with lightgreen background..
• (v3) the word IMMIDIATELY added in the descriptions of "delete" and "set" operations. For v3, see text with orange background.
• (v2) Revised descriptions/requirements of "delete" and "set" operations to reduce possible ambiguity. For v2, see text with yellow background.
• (v2) Submission instructions added.

Objectives

• to give you experience in implementing generic ADTs in C
• to give you (more) experience with doubly-linked lists
• to give you further practice with C and data structures
• to look at a (yet another) simple command interpreter

Admin

Aim

In this assignment, your task is to implement two listIterator ADTs, one for integer values in Part-1 (6 marks) and another for generic data types in Part-2 (4 marks). You will have to write wrapper code to test your implementations, and make sure to test a variety of conditions.

Please note that, you need to submit only the C code implementing the required listIterator ADTs. Submit file listIteratorInt.c for Part-1 and file listIteratorG.c for Part-2.

Iterator

An iterator offers an easy way to traverse through a collection, add new elements, delete and modify existing elements. Iterators are widely supported by langauges like C++ and Java. However, C does not offer iterators. In this assignment your task is to implement two list iterators that allow the programmer to traverse the list in either direction, modify the list during iteration, and obtain the iterator's current position in the list.

You will implement list iterators similar to the one available in Java. The following interface specifications are drawn from Java (7) ListIterator API and adapted for C implementations.

A List Iterator has no current element; its cursor position always lies between the element that would be returned by a call to previous and the element that would be returned by a call to next. An iterator for a list of length n has n+1 possible cursor positions, as illustrated by the carets (^) below:

                         Element(0)   Element(1)   Element(2)   ... Element(n-1)
 cursor positions:     ^            ^            ^            ^                  ^

Note that the delete and set methods are not defined in terms of the cursor position; they are defined to operate on the last element returned by a call to next or previous.

Part-1: List iterator for integer values

(6 marks)

First, implement a list iterator that can store integer values and offer the following interface to the programmer. You must use doubly linked list to implement your list iterator.

• Download files for Part-1: ass1p1.zip.

• Log from sample tests: sample_tests_log1.txt.

You need to implement the following methods in the file listIteratorInt.c. Note that you need to submit ONLY one file, listIteratorInt.c, for this part. Please do not modify the header file listIteratorInt.h. You can write your test code in testListIteratorInt.c. However, you will not submit your test code. We will test your implementation using our test sets, so make sure you do NOT modify function headers (signatures) in the header file listIteratorInt.h.

Interface for Part-1

IteratorInt IteratorIntNew()

Creates a new list iterator that can store integer values.

int add(IteratorInt it, int v)

Inserts the specified value v into the list iterator it. The element is inserted immediately before the element that would be returned by next(), if any, and after the element that would be returned by previous(), if any. (If the list contains no elements, the new element becomes the sole element on the list.) The new element is inserted before the implicit cursor: a subsequent call to next would be unaffected, and a subsequent call to previous would return the new element. Returns 1 if successful, 0 otherwise.

int hasNext(IteratorInt it)

Returns 1 if the given list iterator has more elements when traversing the list in the forward direction, returns 0 otherwise.

int hasPrevious(IteratorInt it)

Returns 1 if the given list iterator has more elements when traversing the list in the reverse direction, returns 0 otherwise.

int * next(IteratorInt it)

Returns the pointer to the next value in the given list iterator and advances the cursor position. This method may be called repeatedly to iterate through the list, or intermixed with calls to previous to go back and forth. (Note that alternating calls to next and previous will return the same element repeatedly.) The method returns NULL if it has no next value.

int * previous(IteratorInt it)

Returns the pointer to the previous value in the given list iterator and moves the cursor position backwards. This method may be called repeatedly to iterate through the list backwards, or intermixed with calls to next to go back and forth. (Note that alternating calls to next and previous will return the same element repeatedly.) The method returns NULL if it has no previous value.

int delete(IteratorInt it)

Deletes from the list iterator the last value that was returned by next or previous or findNext or findPrevious.
Precondition: A call to delete must be IMMEDIATELY preceded by a successful call to one of next or previous or findNext or findPrevious.
Returns 1 if successful, 0 otherwise (for example, invalid delete call).
This call can only be made once per call to next or previous or findNext or findPrevious. It can be made only if add or reset has not been called after the last call to next or previous or findNext or findPrevious.

int set(IteratorInt it, int v)

Replaces the last element (v) returned by next or previous or findNext or findPrevious with the specified element (v).
Precondition: A call to set must be IMMEDIATELY preceded by a successful call to one of next or previous or findNext or findPrevious.
Returns 1 if successful, 0 otherwise (for example, invalid set call).
This call can be made only if neither of delete or add or reset have been called after the last call to next or previous or findNext or findPrevious. This call can only be made once per call to next or previous or findNext or findPrevious.

int * findNext(IteratorInt it, int v)

Returns the pointer to the next value in it that matches the given value v and advances the cursor position.
The method returns NULL and the cursor is not moved from the current position, if it has no next value that match v.

int * findPrevious(IteratorInt it, int v)

Returns the pointer to the previous value in it that matches the given value v and moves the cursor position backwards.
The method returns NULL and the cursor is not moved from the current position, if it has no previous value that match v.

void reset(IteratorInt it)

Resets it to the start of the list.

Part-2: Generic List iterator

(4 marks)

In this part, you need to implement a generic list iterator that can store values of any type, and offer the following interface to the programmer. You must use doubly linked list to implement your list iterator. You need to implement the following methods in file listIteratorG.c, and submit this file as describe above in the "Admin" section.

• Download files for Part-2: ass1p2.zip.

Interface for Part-2

typedef struct IteratorGRep *IteratorG;

typedef int   (*ElmCompareFp)(void const *e1, void const *e2);
typedef void *(*ElmCopyFp)(void const *e1);
typedef void  (*ElmFreeFp)(void *e1);

IteratorG IteratorGNew(ElmCompareFp cmp, ElmCopyFp copy, ElmFreeFp free)

Creates a new generic list iterator with given functions to handle values.

int add(IteratorG it, void *vp)

Inserts the specified value poined by vp into the list iterator it. The element is inserted immediately before the element that would be returned by next(), if any, and after the element that would be returned by previous(), if any. (If the list contains no elements, the new element becomes the sole element on the list.) The new element is inserted before the implicit cursor: a subsequent call to next would be unaffected, and a subsequent call to previous would return the new element. Returns 1 if successful, 0 otherwise.

int hasNext(IteratorG it)

Returns 1 if the given list iterator has more elements when traversing the list in the forward direction, returns 0 otherwise.

int hasPrevious(IteratorG it)

Returns 1 if the given list iterator has more elements when traversing the list in the reverse direction, returns 0 otherwise.

void * next(IteratorG it)

Returns the pointer to the next value in the given list iterator and advances the cursor position. This method may be called repeatedly to iterate through the list, or intermixed with calls to previous to go back and forth. (Note that alternating calls to next and previous will return the same element repeatedly.) The method returns NULL if it has no next value.

void * previous(IteratorG it)

Returns the pointer to the previous value in the given list iterator and moves the cursor position backwards. This method may be called repeatedly to iterate through the list backwards, or intermixed with calls to next to go back and forth. (Note that alternating calls to next and previous will return the same element repeatedly.) The method returns NULL if it has no previous value.

int delete(IteratorG it)

Deletes from the list iterator the last value that was returned by next or previous or findNext or findPrevious.
Precondition: A call to delete must be IMMEDIATELY preceded by a successful call to one of next or previous or findNext or findPrevious.
Returns 1 if successful, 0 otherwise (for example, invalid delete call).
This call can only be made once per call to next or previous or findNext or findPrevious. It can be made only if add or reset has not been called after the last call to next or previous or findNext or findPrevious.

int set(IteratorG it, void * vp)

Replaces the last element returned by next or previous or findNext or findPrevious with the specified element (*vp).
Precondition: A call to set must be IMMEDIATELY preceded by a successful call to one of next or previous or findNext or findPrevious.
Returns 1 if successful, 0 otherwise (for example, invalid set call).
This call can be made only if neither of delete or add or reset have been called after the last call to next or previous or findNext or findPrevious. This call can only be made once per call to next or previous or findNext or findPrevious.

void * findNext(IteratorG it, void * vp)

Returns pointer to the next value in it that matches the value pointed to by vp. and advances the cursor position.
The method returns NULL if there is no such next value and the cursor is not moved from the current position.

void * findPrevious(IteratorG it, void * vp)

Returns pointer to the previous value in it that matches the value pointed to by vp and moves the cursor position backwards.
The method returns NULL if there is no such previous value and the cursor is not moved from the current position.

void reset(IteratorG it)

Resets it to the startof the list.

Submission

Plagiarism

This is an individual assignment. Each student will have to develop their own solution without help from other people. In particular, it is not permitted to exchange code or pseudocode. You are not allowed to use code developed by persons other than yourself. If you have questions about the assignment, ask your tutor Before submitting any work you should read and understand the following very useful guide by the Learning Centre How Not To Plagiarise. All work submitted for assessment must be entirely your own work. We regard unacknowledged copying of material, in whole or part, as an extremely serious offence. For further information, see the Course Information.

-- end --