• Due: 2009-12-07 13:00

Overview

A convenient data structure is the dynamic array (java Vector and C++ std::vector are example). Typical operations include expanding the array by adding an element to the end, and accessing an element by index. One implementation is store a linked list of subarrays. This works well when there are not too many subarrays (i.e. the initial estimate for the subarray size is pretty close to the final array size).

Your assignment is implement such a dynamic array structure. Note that although minimal header files are provided here, you are responsible for documenting to coding standard. You should make a file intvec.h for declarations, and intvec.c for function definitions. Make a seperate main function for each test program. Hand in test cases for each question in seperate files.

Basic operations

Start with the following header file intvec.h The macro IV_CHUNK_SIZE is defined artificially small here, to help debug your code.

 
#ifndef INTVEC_H 
#define INTVEC_H

#define IV_CHUNK_SIZE 3
typedef struct iv_chunk_s {
  int data[IV_CHUNK_SIZE];
  struct iv_chunk_s *next;
  int count;
} iv_chunk_t, *iv_chunk_p;

typedef  struct intvec_s {
  iv_chunk_p first,last;
  int length;
} intvec_t, *intvec_p;

intvec_p iv_new(void);
void iv_push(intvec_p v,int n);
int iv_get(intvec_p v,int pos);
#endif

Provide definitions for iv_new, iv_push, and iv_get so that the following code snippet prints "0 1 2 3 4 5 6 7 8 9".

  int i;
  intvec_p v=iv_new();

  for (i=0; i<10; i++)
    iv_push(v,i);

  for (i=0; i<10; i++)
    printf("%d ",iv_get(v,i));

14 Marks Provide at least 3 test cases, and function and data structure doxygen comments. Note that as implemented, the performance of iv_get will depend on the number of chunks.

Iterator

Add the following declaration to intvec.h

typedef struct iv_iter_s {
  iv_chunk_p cur;
  int pos;
} iv_iter_t, *iv_iter_p;

iv_iter_p iv_first(intvec_p v);
iv_iter_p iv_next(iv_iter_p iter);
int iv_cur(iv_iter_p iter);

Provide definitions for iv_first, iv_next, and iv_cur so that the following code snippet prints "0 1 2 3 4 5 6 7 8 9"

  intvec_p v=iv_new();
  iv_iter_p iter;

  for (i=0; i<10; i++)
    iv_push(v,i);

  for (iter=iv_first(v); iter; iter=iv_next(iter))
    printf("%d ",iv_cur(iter));

iv_first, iv_next, and iv_cur should all have constant time performance, i.e. independent of the number of chunks.

8 marks Provide at least 2 test cases, and function and data structure documentation doxygen comments.

Pop

Implement the following function

int iv_pop(intvec_p v);

This removes and returns the last element of the intvec. When all elements of a given chunk have been popped, you should remove that chunk and free it.

The following snippet prints "0 1 2 3 4"

  for (i=0; i<10; i++)
    iv_push(v,i);

  for (i=0; i<5; i++)
    iv_pop(v);

  for (iter=iv_first(v); iter; iter=iv_next(iter))
    printf("%d ",iv_cur(iter));
  putchar('\n');

8 marks Provide at least 2 test cases, and function doxygen comments. Make sure you test this function in valgrind; hand in output from valgrind for running your test cases.

Bonus

For up to 3 bonus marks, modify the data structure so that iv_pop is constant time, while maintaining the same time bounds for other operations (in particular, iv_next should still be constant time).