(Version-04: 07:50am Friday 20/Apr)
The specifications may change! so please check the following change log frequently.
In this assignment, your task is to implement a generic list Iterator ADT, in the file iteratorG.c. 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 list Iterator ADT, in the file iteratorG.c.
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 a list iterator that allow the programmer to traverse the list in either direction and modify the list during iteration.
You will implement a list iterator defined below. The following interface specification is 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: ^ ^ ^ ^ ^
You must use doubly linked list to implement the following iterator for this assignment, otherwise you will receive zero mark for this assignment!
You need to implement a generic list iterator that can store elements of any type, and offer the following interface to the programmer. You need to implement the following methods in file iteratorG.c, and submit this file as described in the section named "Submission".
Note that you need to submit ONLY one file iteratorG.c for this assignment. Please do not modify the header file iteratorG.h. You can write your test code in testIteratorG.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 iteratorG.h.
typedef struct IteratorGRep *IteratorG; typedef int (*ElmCompareFp)(void const *e1, void const *e2); typedef void *(*ElmNewFp)(void const *e1); typedef void (*ElmFreeFp)(void *e1);
Let's say 'it' is [ ^ ]
add(it, 12) will result in the following, and return 1
[ ^ 12 ]
add(it, 7) will result in the following, and return 1
[ ^ 7 12 ]
add(it, 15) will result in the following, and return 1
[ ^ 15 7 12 ]
Let's say 'it' is [ 20 74 ^ 32 55 5 14 89 ]
// Alternative: 1 (compact)
int val = *((int *) next(it));
// Alternative: 2 (easy to understand!)
int *p1;
p1 = (int *) next(it);
int val = *p1;
val is now 32, and 'it' is [ 20 74 32 ^ 55 5 14 89 ]
Let's say 'it' is [ 20 74 ^ 32 55 5 14 89 ]
int val = *((int *) previous(it));
val is now 74, and 'it' is [ 20 ^ 74 32 55 5 14 89 ]
Let's say 'it' is [ 20 12 ^ 15 5 14 ]
del(it) will result in the following, and return 1
[ 20 ^ 15 5 14 ]
del(it) will result in the following, and return 1
[ ^ 15 5 14 ]
del(it) will result in the following, and return 0
[ ^ 15 5 14 ]
Let's say 'it' is [ 20 74 ^ 32 55 5 14 89 ]
int newVal = 50;
set(it, &newVal) will result in the following, and return 1
'it' is changed to [ 20 50 ^ 32 55 5 14 89 ]
Let's say 'it' is [ 20 ^ 12 15 5 14 10 5 9 3 ]
advance(it, 3) will result in the following, and return [ ^ 12 15 5 ]
[ 20 12 15 5 ^ 14 10 5 9 3 ]
advance(it, -2) will result in the following, and return [ ^ 5 15 ]
[ 20 12 ^ 15 5 14 10 5 9 3 ]
advance(it, 9) will result in the following (unchanged), and return 'null'
[ 20 12 ^ 15 5 14 10 5 9 3 ]
Let's say 'it' is [ 20 12 15 5 ^ 14 10 5 9 3 ]
reverse(it) will result in the following,
[ 3 9 5 10 14 ^ 5 15 12 20 ]
Let's say 'it' is [ ^ 7 1 8 9 4 ]
reverse(it) will result in the following,
[ 4 9 8 1 7 ^ ]
Let's say 'it' is [ 7 1 8 9 4 ^ ]
reverse(it) will result in the following,
[ ^ 4 9 8 1 7 ]
int gradeFL(void *vp) {
int marks = *((int *) vp );
if(marks < 50)
return 1;
else
return 0;
}
....
....
Let's say 'it' is [ 20 74 ^ 32 55 5 14 89 ]
newIt = find(it, gradeFL);
'newIt' will be [ ^ 32 5 14 ]
'it' is unchanged [ 20 74 ^ 32 55 5 14 89 ]
Let's say 'it' is [ 15 5 ^ 14 10 5 9 3 ] distanceFromStart(it) will return 2. Let's say 'it' is [ ^ 7 1 8 9 4 ] distanceFromStart(it) will return 0. Let's say 'it' is [ 7 1 8 9 4 ^ ] distanceFromStart(it) will return 5.
Let's say 'it' is [ 20 12 15 5 ^ 14 10 ] distanceToEnd(it) will return 2. Let's say 'it' is [ ^ 7 1 8 9 4 ] distanceToEnd(it) will return 5. Let's say 'it' is [ 7 1 8 9 4 ^ ] distanceToEnd(it) will return 0.
Your program will be tested thoroughly and objectively. This assignment will be marked out of 10 where 8 marks are for correctness (based on auto marking) and 2 marks are for your solution's complexity, style and comments.
You need to submit only one file iteratorG.c.
To Submit this assignment, go to the Submission page and click the tab named "Make Submission".
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 --