Mombu the Programming Forum sponsored links

Go Back   Mombu the Programming Forum > Programming > Array ADT
User Name
Password
REGISTER NOW! Mark Forums Read

sponsored links


Reply
 
1 16th November 02:32
bruno
External User
 
Posts: 1
Default Array ADT


Hello everyone, this is my first post in this group.
I would like to have some critics about the next code.

/*
*
================================================== =======================
* Filename: array.h
* Desription: ADT for Dynamic arrays
*
* Creation: 04/11/2006 01:20:25 AM WEST
*
* Author: Bruno Martins
* (bruno.ac.martins@gmail.com)
*
================================================== =======================
*/

#ifndef _ARRAY__H_
#define _ARRAY__H_

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE 0
#define FALSE 1


/*
================================================== =======================
* some definitions
*
================================================== =======================
*/
typedef void ( *Destroy ) ( void * );
typedef int ( *Match ) ( const void *, const void * );

/*
================================================== =======================
* some return values
*
================================================== =======================
*/
#define SUCCESS 0
#define NULL_PTR 1 /* malloc error */
#define IO_ERR 2 /* input-output error */


/*
================================================== =======================
* the definition of an array
*
================================================== =======================
*/

/*
* - NOTES --------------------------------------------------------
* Because of the use of funtions like exchange, that swap two
* elements of the array, we must know the size of an element.
* -----------------------------------------------------------------
*/

typedef struct
{

int size; /* current size of the array */
int esize; /* size of each element */
int sort; /* the array is ordered */
void **array; /* the real array */

Match match; /* function to compare data */

} Array;


/*
================================================== =======================
* public functions
*
================================================== =======================
*/

/*
* newArray: create a new array
* - PARAMETERS ---------------------------------------------------
* int : array must be sorted (1) or no (0)
* int : size of each element of array
* Match : compare function
*/
Array *newArray ( int, int, Match );

/* insertArray: insert a new element into array */
Array *insertArray ( Array *, void * );

/* remIndexArray: remove element (index+1) of the array */
Array *remIndexArray ( Array *, int );

/* bubbleSort: sort an array using the bubble sort algorithm */
void bubbleSort ( Array *, Match );
/* insertionSort: sort an array using insertion sort algorithm. */
void insertionSort ( Array *, Match );
/* quicksort: quicksort an array using Match to compare. */
void quicksort ( Array *, Match );

/* bsrchArray: binary search of element in array, return index
* or -1 if element doesnt exists */
int bsrchArray ( Array *, void *, Match );

/* walkForw: traverse the array and call fn on each element */
void walkForward ( Array *, void ( *fn ) ( void * ) );

/* saveArray: save array data in binary file */
void saveArray ( Array *, char * );

/* loadArray: load array data from a binary file */
Array *loadArray ( Array *, char * );

/* freeArray: free array and call destroy on all elements */
void freeArray ( Array *, Destroy );


#endif


/*
*
================================================== =======================
* Filename: array.c
* Desription: ADT for Dynamic arrays
*
* Creation: 04/11/2006 01:19:58 AM WEST
*
* Author: Bruno Martins
* (bruno.ac.martins@gmail.com)
*
================================================== =======================
*/

#include "array.h"


/*
================================================== =======================
* local functioms
*
================================================== =======================
*/

/* allocElm: alloc a new element */
static void *allocElm ( int size )
{
void *elm = NULL;

if ( ( elm = malloc ( size ) ) == NULL )
{
fprintf ( stderr, "ERROR: allocElm (malloc failed)" );
exit ( NULL_PTR );
}

return elm;
}

/* appendArray: append a new element to array */
static Array *appendArray ( Array *array, void *elm )
{
int pos = array->size - 1;
array->array[pos] = elm;

#ifdef DEBUG
printf ( "appending index %d to array\n", pos );
printf ( "array->array[%d] stored at %p\n\n",
pos, (void *) &array->array[pos] );
#endif

return array;
}

/* insSortArray: insert a new element into ordered array */
static Array *insSortArray ( Array *array, void *elm )
{
int i, j;
void *aux1 = NULL, *aux2 = NULL;

for ( i = 0; i < ( array->size - 1 ); i++ )
{
if ( array->array [i] == NULL )
{
fprintf ( stderr, "ERROR: insSortArray (NULL element found).\n" );
exit ( NULL_PTR );
}
if ( array->match ( array->array [i], elm ) > 0 )
break;
}

aux1 = array->array [i];
array->array [i++] = elm;

#ifdef DEBUG
printf ( "insertion of index %d into array\n", i-1 );
printf ( "array->array[%d] is stored at %p\n\n",
i-1, (void *) &array->array[i-1] );
#endif

for ( j = i; j < array->size; j++ )
{
aux2 = array->array [j];
array->array [j] = aux1;
aux1 = aux2;
}

return array;
}

/*
* - NOTES --------------------------------------------------------
*
* From "Introduction to Algorithms, 2nd ed. MIT 2001"
*
* QUICKSORT(A, p, r)
* 1 if p < r
* 2 then q <- PARTITION(A, p, r)
* 3 QUICKSORT(A, p, q - 1)
* 4 QUICKSORT(A, q + 1, r)
*
* PARTITION(A, p, r)
* 1 x <- A[r]
* 2 i <- p-1
* 3 for j <- p to r - 1
* 4 do if A[j] <= x
* 5 then i <- i + 1
* 6 exchange A[i] <-> A[j]
* 7 exchange A[i + 1] <-> A[r]
* 8 return i + 1
*
* -----------------------------------------------------------------
*/

/* exchange: dynamic swap */
static int exchange ( void *x, void *y, int size )
{
void *tmp;

if ( ( tmp = malloc ( size ) ) == NULL )
return -1;

/* REF:
* Practice of Programming (1999) pg 43
* "The ANSI C standard defines two functions: memcpy,
* which is fast but might overwrite memory if source
* and destination overlap; and memmove, which might
* be slower but will always be correct."
*/
memmove ( tmp, x, size );
memmove ( x, y, size );
memmove ( y, tmp, size );

free(tmp);

return 0;
}

/* partition: function used in quicksort (see NOTES) */
static int partition ( Array *array, int p, int r, Match match )
{
int i, j;
void *x = malloc ( array->esize );
memcpy ( x, array->array [r], array->esize );

i = p - 1;
for ( j = p; j < r; j++ )
if ( match ( array->array [j], x ) <= 0 )
{
i++;
exchange ( array->array [i], array->array [j],
array->esize );
}

exchange ( array->array [i+1], array->array [j],
array->esize );

free ( x );
return ( i+1 );
}

/* qksort: recursive quicksort implementation (see NOTES) */
static void qksort ( Array *array, int p, int r, Match match )
{
int q;

if ( p < r )
{
q = partition ( array, p, r, match );
qksort ( array, p, q - 1, match );
qksort ( array, q + 1, r, match );
}
}


/*
================================================== =======================
* public functions
*
================================================== =======================
*/

/*
* newArray: create a new array
* - PARAMETERS ---------------------------------------------------
* int : array must be sorted (1) or no (0)
* int : size of each element of array
* Match : compare function
*/
Array *newArray ( int sort, int esize, Match match )
{
Array *array = ( Array * ) malloc ( sizeof ( Array ) );
if ( array == NULL )
{
fprintf ( stderr, "ERROR: newArray (malloc failed)\n" );
exit ( NULL_PTR );
}

array->size = 0;
array->esize = esize;
array->sort = sort;
array->array = NULL;
array->match = match;

return array;
}

/* insertArray: insert a new element into array */
Array *insertArray ( Array *array, void *elm )
{

#ifdef DEBUG
printf ( "\nDEBUGGING\narray->array is stored at %p\n", (void*)
&array->array );
#endif

array->size++;
array->array = ( void ** ) realloc ( array->array,
array->size * sizeof ( void * ) );

if ( array->sort == 0 || array->size < 2 )
array = appendArray ( array, elm );
else
array = insSortArray ( array, elm );

return array;
}

/* remIndexArray: remove element (i+1) of the array */
Array *remIndexArray ( Array *array, int index )
{
int i;

if ( index < 0 || index > (array->size - 1) )
return array;

free ( array->array [index] );

/* we want the last element into (last-1) position */
for ( i = index; i < (array->size - 1); i++ )
array->array [i] = array->array [i+1];

array->size--;

array->array = ( void ** ) realloc ( array->array,
array->size * sizeof ( void * ) );

if ( array->array == NULL && array->size != 0 )
{
fprintf ( stderr, "ERROR: remArray (realloc failed)\n" );
exit ( NULL_PTR );
}

return array;
}

/*
* - NOTES --------------------------------------------------------
*
* From "Introduction to Algorithms, 2nd ed. MIT 2001"
*
* INSERTION-SORT(A)
* 1 for j <- 2 to length[A]
* 2 do key <- A[j]
* 3 // Insert A[j] into the sorted sequence A[1..j-1].
* 4 i <- j-1
* 5 while i > 0 and A[i] > key
* 6 do A[i + 1] <- A[i]
* 7 iā†i-1
* 8 A[i+1] <- key
*
* -----------------------------------------------------------------
*/

/* insertionSort: sort an array using insertion sort algorithm. */
void insertionSort ( Array *array, Match match )
{
int i, j;
void *aux = allocElm ( array->esize );
for ( j = 1; j < array->size; j++ )
{
memmove ( aux, array->array [j], array->esize );
i = j - 1;

while ( (i >= 0) && (match ( array->array [i], aux ) > 0 ) )
{
memmove ( array->array [i+1], array->array [i], array->esize );
i--;
}

memmove ( array->array [i+1], aux, array->esize );
}
}

/*
* - NOTES --------------------------------------------------------
*
* From "Introduction to Algorithms, 2nd ed. MIT 2001"
*
* BUBBLESORT(A)
* 1 for i ā† 1 to length[A]
* 2 do for j ā† length[A] downto i + 1
* 3 do if A[j] < A[j - 1]
* 4 then exchange A[j] ā†" A[j - 1]
*
* -----------------------------------------------------------------
*/
/* bubbleSort: sort an array using the bubble sort algorithm */
void bubbleSort ( Array *array, Match match )
{
int i, j;
for ( i = 0; i < array->size; i++ )
{
for ( j = array->size - 1; i < j; j-- )
{
if ( match (array->array [j],
array->array [j-1]) < 0 )

/* swap A[j] with A[j-1] */
exchange ( array->array [j],
array->array [j-1], array->esize );
}
}
}

/* quicksort: sort an array using quicksort algorithm. */
void quicksort ( Array *array, Match match )
{
qksort ( array, 0, array->size - 1, match );
array->sort = 1;
}

/* bsrchArray: binary search of element in array, return index
* or -1 if element doesnt exists */
int bsrchArray ( Array *array, void *elm, Match match )
{
int left = 0,
middle = 0,
right = array->size - 1;

if ( array->size == 0 || elm == NULL )
return -1;

if ( array->sort == 0 )
{
fprintf ( stderr, "ERROR: bsrchArray (The array must be sorted)\n" );
return -1;
}

while ( left <= right )
{
middle = ( left + right ) / 2;

if ( array->array [middle] == NULL )
{
fprintf ( stderr, "ERROR: bsrchArray (NULL element found)\n" );
exit ( NULL_PTR );
}

if ( match ( elm, array->array [middle] ) == 0 )
return middle;
else
{
if ( match ( elm, array->array [middle] ) > 0 )
right = middle - 1;
if ( match ( elm, array->array [middle] ) < 0 )
left = middle + 1;
}
}

return -1;
}


/* walkForw: traverse the array and call fn on each element */
void walkForward ( Array *array, void ( *fn ) ( void * ) )
{
int i;

for ( i = 0; i < array->size; i++ )
( *fn ) ( array->array [i] );
}

/* saveArray: save data of array in binary file */
void saveArray ( Array *array, char *filename )
{
int i;

FILE *fp = fopen ( filename, "wb" );

if ( fp == NULL )
{
fprintf ( stderr, "ERROR: saveArray (fopen failed)\n" );
exit ( IO_ERR );
}

for ( i = 0; i < array->size; i++ )
fwrite ( array->array [i], array->esize, 1, fp );

fclose ( fp );
}

/* loadArray: load array data from a binary file */
Array *loadArray ( Array *array, char *filename )
{
void *data = NULL;

FILE *fp = fopen ( filename, "rb" );

if ( fp == NULL )
return array;

while ( !feof ( fp ) )
{
data = allocElm ( array->esize );

if ( fread ( data, array->esize, 1, fp ) == 1 )
array = insertArray ( array, data );
else
{
free ( data );
break;
}
}

fclose ( fp );
return array;
}

/* freeArray: free array and call destroy on all elements */
void freeArray ( Array *array, Destroy destroy )
{
int i;

if ( array->size > 0 )
{
for ( i = 0; i < array->size; i++ )
destroy ( array->array [i] );

free ( array->array );
}

free ( array );
}


Thanks in advance
  Reply With Quote


  sponsored links


Reply


Thread Tools
Display Modes




Copyright © 2006 SmartyDevil.com - Dies Mies Jeschet Boenedoesef Douvema Enitemaus -
666