20 September 2010

Java-like ArrayList in C

Al salamo Alykom,

Last week I had the change to have a look at the implementation of the java.util.ArrayList class in Java.

I decided to write a similar one in C, and hence it is fully depended on System.arraycopy, so I wrote arrayCopyutility function in C to use it.

The implementation of ArrayList we going to see here is depending on code wrote under the post of ArrayCopy.

I tried to include many of the functions of the java.util.ArrayList, and also missed many :).

Here's the header file:
/*
* ArrayList
*/
#ifndef ARRAYLIST_H
#define ARRAYLIST_H

typedef struct
{
int data;
}Element;

typedef struct
{
int current;
int size;
int increment_rate;
Element *elements;
}ArrayList;

typedef enum
{
RIFHT, LEFT
} Shift;

// public functions:
void init (ArrayList*const);
void initWithSize (ArrayList*const, int);
void initWithSizeAndIncRate (ArrayList*const, int, int);
void clean (ArrayList*);
int add (ArrayList*const, Element);
int insert (ArrayList*const, Element, int);
Element* removeAt (ArrayList*const, int);
void clear (ArrayList*const);
int set (ArrayList*const, Element, int);
Element* get (ArrayList*const, int);
void print (const ArrayList*const);
int lastIndexOf (const ArrayList*const, Element);
int indexOf (const ArrayList*const, Element);
int isEmpty (const ArrayList*const);
// TODO
int hashCode (const ArrayList*const);


// static (private) utility functions:

/* Abstracting the print method of the element by delegating it to the element itself (OOP-like feature) */
static void printElement(const Element*const);
static void shift(ArrayList *const list, int index, int rooms, Shift dir);
static void wide(ArrayList* const);

#endif // ARRAYLIST_H



And here's the implementation file:
#include <stdio.h>
#include <stdlib.h>

#include <array_list_impl/ArrayList.h>
#include <arrays/ArrayUtil.h>

void init (ArrayList *const list)
{
initWithSize(list, 100);
}
void initWithSize(ArrayList *const list, int size)
{
initWithSizeAndIncRate(list, size, 50);
}

void initWithSizeAndIncRate(ArrayList *const list, int size, int rate)
{
list->size = size;
list->increment_rate = rate;
list->elements = (Element*) calloc(sizeof(Element), list->size);
list->current = -1;
}

void clear (ArrayList *const list)
{
while (list->current>=0)
{
list->elements[list->current] = (Element){0};
list->current--;
}
}

int set (ArrayList *const list, Element e, int index)
{
if (index <= list->current)
{
list->elements[index] = e;
}
return 0;
}

Element* get (ArrayList *const list, int index)
{
if (index <= list->current)
{
Element *e = &list->elements[index];
return e;
}
return NULL;
}

int add (ArrayList *const list, Element e)
{
if (++list->current < list->size)
{
list->elements[list->current] = e;
return 1;
}else
{
wide(list);
list->elements[list->current] = e;
return 1;
}
return 0;
}
static void wide(ArrayList* const list)
{
list->size += list->increment_rate;
Element *newArr = (Element*) calloc(sizeof(Element), list->size) ;
arraryCopy(newArr, 0, list->elements, 0, list->current, list->size, sizeof(Element));
free(list->elements);
list->elements = newArr;
}

int insert (ArrayList *const list, Element e, int index)
{
if (index <= list->current && ++list->current < list->size)
{
shift(list, index, 1, RIFHT);
list->elements[index] = e;
return 1;
}
return 0;
}

int lastIndexOf (const ArrayList *const list, Element e)
{
int index = list->current;
while (index >-1)
{
if (e.data == list->elements[index].data) return (list->current-index);
index--;
}
return 0;
}

int indexOf (const ArrayList *const list, Element e)
{
int index = 0;
while (index <= list->current)
{
if (e.data == list->elements[index].data) return index;
index++;
}
return 0;
}

int isEmpty (const ArrayList *const list)
{
return list->current == -1;
}

Element *removeAt(ArrayList *const list, int index)
{
if (list->current >= index)
{
Element *e = &list->elements[index];
shift(list, index, 1, LEFT);
list->current--;
return e;
}
return NULL;
}

void print (const ArrayList *const list)
{
int i;
for (i=0; i<=list->current; i++)
{
Element e = list->elements[i];
printElement(&e);
}
printf("\n");
}

void clean(ArrayList *list)
{
free(list->elements);
}

static void printElement(const Element *const e)
{
printf("%i ", e->data);
}

static void shift(ArrayList *const list, int index, int rooms, Shift dir)
{
if (dir == RIFHT)
{
arraryCopy(list->elements, index+1, list->elements, index, rooms, list->current, sizeof(Element));
}else //SHIFT
{
arraryCopy(list->elements, index, list->elements, index+1, rooms, list->current, sizeof(Element));
}
}



And here's a test program:

#include <stdio.h>
#include <array_list_impl/ArrayList.h>

int main(void)
{

ArrayList list;
init(&list);
add(&list, (Element){10});
add(&list, (Element){30});
add(&list, (Element){40});
add(&list, (Element){50});
add(&list, (Element){60});
add(&list, (Element){30});
add(&list, (Element){80});
print(&list);

insert(&list, (Element){20}, 1);
insert(&list, (Element){15}, 1);
insert(&list, (Element){3}, 0);
print(&list);

printf("Removeing element at index 5\n");
removeAt(&list, 5);
print(&list);

Element *e = get(&list, 5);
printf("element at 5th index:\n %i\n", (e!=NULL? e->data:-1));

int i = indexOf(&list, (Element){30});
printf("Index of 30:\n %i\n", i);

i = lastIndexOf(&list, (Element){30});
printf("Last index of 30:\n %i\n", i);

printf("Clear...\n");
clear(&list);
print(&list);

for (i=0; i<180; i++)
{
add(&list, (Element){i});
}

print(&list);
clean(&list);

return 0;
}



That's all folks.
Just make sure to test the above code well before using it.

4 comments:

Andi said...

Thanks a lot for this nice article

mhewedy said...

@Andi,
Welcome :)
You also have an good blog, is it available in English too?

Anonymous said...

Hi,

I am trying to use this in a isolated embedded solutions, and i see that the "ArrayUtil.h" is missing. can you also share that file as well so it is complete.

Thanks
Viswanath

mhewedy said...

I already mentioned it in the post

http://m-hewedy.blogspot.com/2010/09/arraycopy.html