|
Packit |
89ede9 |
/*
|
|
Packit |
89ede9 |
* intlist.c
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Copyright (c) Chris Putnam 2007-2018
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Version 1/12/2017
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Source code released under the GPL version 2
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Implements a simple managed array of ints
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
#include <stdlib.h>
|
|
Packit |
89ede9 |
#include <assert.h>
|
|
Packit |
89ede9 |
#include "intlist.h"
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
#define INTLIST_MINALLOC (20)
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static int
|
|
Packit |
89ede9 |
intlist_validn( intlist *il, int n )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
if ( n < 0 || n >= il->n ) return 0;
|
|
Packit |
89ede9 |
return 1;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_wasfound( intlist *il, int n )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
if ( n!=-1 ) return 1;
|
|
Packit |
89ede9 |
else return 0;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_wasnotfound( intlist *il, int n )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
if ( n==-1 ) return 1;
|
|
Packit |
89ede9 |
else return 0;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static int
|
|
Packit |
89ede9 |
intlist_alloc( intlist *il, int alloc_size )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
il->data = ( int * ) calloc( alloc_size, sizeof( int ) );
|
|
Packit |
89ede9 |
if ( !(il->data) ) return INTLIST_MEMERR;
|
|
Packit |
89ede9 |
il->max = alloc_size;
|
|
Packit |
89ede9 |
il->n = 0;
|
|
Packit |
89ede9 |
return INTLIST_OK;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static int
|
|
Packit |
89ede9 |
intlist_realloc( intlist *il, int alloc_size )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int i, *more;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
more = ( int * ) realloc( il->data, sizeof( int ) * alloc_size );
|
|
Packit |
89ede9 |
if ( !more ) return INTLIST_MEMERR;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
il->data = more;
|
|
Packit |
89ede9 |
il->max = alloc_size;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=il->max; i
|
|
Packit |
89ede9 |
il->data[i] = 0;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return INTLIST_OK;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static int
|
|
Packit |
89ede9 |
intlist_ensure_space( intlist *il, int n )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int alloc = n;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( il->max == 0 ) {
|
|
Packit |
89ede9 |
if ( alloc < INTLIST_MINALLOC ) alloc = INTLIST_MINALLOC;
|
|
Packit |
89ede9 |
return intlist_alloc( il, alloc );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
else if ( il->max <= n ) {
|
|
Packit |
89ede9 |
if ( alloc < il->max * 2 ) alloc = il->max * 2;
|
|
Packit |
89ede9 |
return intlist_realloc( il, alloc );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return INTLIST_OK;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_add()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Returns INTLIST_OK/INTLIST_MEMERR
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_add( intlist *il, int value )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
status = intlist_ensure_space( il, il->n+1 );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( status == INTLIST_OK ) {
|
|
Packit |
89ede9 |
il->data[ il->n ] = value;
|
|
Packit |
89ede9 |
il->n++;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_add_unique()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Returns INTLIST_OK/INTLIST_MEMERR
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_add_unique( intlist *il, int value )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int n;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
n = intlist_find( il, value );
|
|
Packit |
89ede9 |
if ( intlist_wasnotfound( il, n ) )
|
|
Packit |
89ede9 |
return intlist_add( il, value );
|
|
Packit |
89ede9 |
else
|
|
Packit |
89ede9 |
return INTLIST_OK;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_find_or_add( intlist *il, int value )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int n, status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
n = intlist_find( il, value );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( intlist_wasfound( il, n ) ) {
|
|
Packit |
89ede9 |
return n;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
else {
|
|
Packit |
89ede9 |
status = intlist_add( il, value );
|
|
Packit |
89ede9 |
if ( status!=INTLIST_OK ) return -1;
|
|
Packit |
89ede9 |
else return il->n - 1;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_find()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Returns position of value in range [0,n), or -1 if
|
|
Packit |
89ede9 |
* value cannot be found
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_find( intlist *il, int value )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int i;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=0; i<il->n; ++i )
|
|
Packit |
89ede9 |
if ( il->data[i]==value ) return i;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return -1;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static int
|
|
Packit |
89ede9 |
intlist_remove_pos_core( intlist *il, int pos )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int i;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=pos; i<il->n-1; ++i )
|
|
Packit |
89ede9 |
il->data[i] = il->data[i+1];
|
|
Packit |
89ede9 |
il->n -= 1;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return INTLIST_OK;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_remove_pos()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Returns INTLIST_OK on success.
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_remove_pos( intlist *il, int pos )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
assert( intlist_validn( il, pos ) );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return intlist_remove_pos_core( il, pos );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_remove()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Removes first instance of value from the intlist.
|
|
Packit |
89ede9 |
* Returns INTLIST_OK/INTLIST_VALUE_MISSING
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_remove( intlist *il, int value )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int pos;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
pos = intlist_find( il, value );
|
|
Packit |
89ede9 |
if ( pos==-1 ) return INTLIST_VALUE_MISSING;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return intlist_remove_pos_core( il, pos );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* don't actually free space, just reset counter */
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
intlist_empty( intlist *il )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
il->n = 0;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
intlist_free( intlist *il )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( il->data ) free( il->data );
|
|
Packit |
89ede9 |
intlist_init( il );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
intlist_delete( intlist *il )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( il->data ) free( il->data );
|
|
Packit |
89ede9 |
free( il );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
intlist_init( intlist *il )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
il->data = NULL;
|
|
Packit |
89ede9 |
il->max = 0;
|
|
Packit |
89ede9 |
il->n = 0;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* Returns INTLIST_OK/INTLIST_MEMERR
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_init_fill( intlist *il, int n, int v )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
intlist_init( il );
|
|
Packit |
89ede9 |
return intlist_fill( il, n, v );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_init_range()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Initializes intlist to values from [low,high) with step step.
|
|
Packit |
89ede9 |
* Returns INTLIST_OK/INTLIST_MEMERR.
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_init_range( intlist *il, int low, int high, int step )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
intlist_init( il );
|
|
Packit |
89ede9 |
return intlist_fill_range( il, low, high, step );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_new()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Allocates an empty intlist.
|
|
Packit |
89ede9 |
* Returns pointer to intlist on success, NULL on memory error.
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
intlist *
|
|
Packit |
89ede9 |
intlist_new( void )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
intlist *il;
|
|
Packit |
89ede9 |
il = ( intlist * ) malloc( sizeof( intlist ) );
|
|
Packit |
89ede9 |
if ( il ) intlist_init( il );
|
|
Packit |
89ede9 |
return il;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_new_range()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Allocates a intlist initialized to values from [low,high) in increments of step.
|
|
Packit |
89ede9 |
* Returns pointer to intlist on success, NULL on memory error.
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
intlist *
|
|
Packit |
89ede9 |
intlist_new_range( int low, int high, int step )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
intlist *il;
|
|
Packit |
89ede9 |
int status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
il = intlist_new();
|
|
Packit |
89ede9 |
if ( il ) {
|
|
Packit |
89ede9 |
status = intlist_fill_range( il, low, high, step );
|
|
Packit |
89ede9 |
if ( status==INTLIST_MEMERR ) {
|
|
Packit |
89ede9 |
intlist_free( il );
|
|
Packit |
89ede9 |
free( il );
|
|
Packit |
89ede9 |
il = NULL;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
return il;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_new_range()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Allocates a intlist initialized to n elements with value v.
|
|
Packit |
89ede9 |
* Returns pointer to intlist on success, NULL on memory error.
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
intlist *
|
|
Packit |
89ede9 |
intlist_new_fill( int n, int v )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
intlist *il;
|
|
Packit |
89ede9 |
int status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
il = intlist_new();
|
|
Packit |
89ede9 |
if ( il ) {
|
|
Packit |
89ede9 |
status = intlist_fill( il, n, v );
|
|
Packit |
89ede9 |
if ( status==INTLIST_MEMERR ) {
|
|
Packit |
89ede9 |
intlist_free( il );
|
|
Packit |
89ede9 |
free( il );
|
|
Packit |
89ede9 |
il = NULL;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
return il;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_fill()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Fill an intlist with n elements of value v.
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Returns INTLIST_OK or INTLIST_MEMERR.
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_fill( intlist *il, int n, int v )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int i, status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert ( n > 0 );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
status = intlist_ensure_space( il, n );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( status==INTLIST_OK ) {
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=0; i
|
|
Packit |
89ede9 |
il->data[i] = v;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
il->n = n;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_fill_range()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Fill an intlist with the values [low,high) in increments of step
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Returns INTLIST_OK or INTLIST_MEMERR.
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_fill_range( intlist *il, int low, int high, int step )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int i, n, status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
n = ( high - low ) / step + 1;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert ( n > 0 );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
status = intlist_ensure_space( il, n );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( status==INTLIST_OK ) {
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
il->n = 0;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* ...fill intlist with range */
|
|
Packit |
89ede9 |
if ( step > 0 ) {
|
|
Packit |
89ede9 |
for ( i=low; i
|
|
Packit |
89ede9 |
il->data[il->n] = i;
|
|
Packit |
89ede9 |
il->n += 1;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
else {
|
|
Packit |
89ede9 |
for ( i=low; i>high; i+=step ) {
|
|
Packit |
89ede9 |
il->data[il->n] = i;
|
|
Packit |
89ede9 |
il->n += 1;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static int
|
|
Packit |
89ede9 |
intcomp( const void *v1, const void *v2 )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int *i1 = ( int * ) v1;
|
|
Packit |
89ede9 |
int *i2 = ( int * ) v2;
|
|
Packit |
89ede9 |
if ( *i1 < *i2 ) return -1;
|
|
Packit |
89ede9 |
else if ( *i1 > *i2 ) return 1;
|
|
Packit |
89ede9 |
return 0;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
intlist_sort( intlist *il )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
qsort( il->data, il->n, sizeof( int ), intcomp );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* Returns random integer in the range [floor,ceil) */
|
|
Packit |
89ede9 |
static int
|
|
Packit |
89ede9 |
randomint( int floor, int ceil )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int len = ceil - floor;
|
|
Packit |
89ede9 |
return floor + rand() % len;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
static void
|
|
Packit |
89ede9 |
swap( int *a, int *b )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int tmp;
|
|
Packit |
89ede9 |
tmp = *a;
|
|
Packit |
89ede9 |
*a = *b;
|
|
Packit |
89ede9 |
*b = tmp;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
void
|
|
Packit |
89ede9 |
intlist_randomize( intlist *il )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int i, j;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( il->n < 2 ) return;
|
|
Packit |
89ede9 |
for ( i=0; i<il->n; ++i ) {
|
|
Packit |
89ede9 |
j = randomint( i, il->n );
|
|
Packit |
89ede9 |
if ( i==j ) continue;
|
|
Packit |
89ede9 |
swap( &(il->data[i]), &(il->data[j]) );
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* Returns INTLIST_OK/INTLIST_MEMERR */
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_copy( intlist *to, intlist *from )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int i, status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( to );
|
|
Packit |
89ede9 |
assert( from );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
status = intlist_ensure_space( to, from->n );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( status==INTLIST_OK ) {
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
to->n = from->n;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=0; i<from->n; ++i )
|
|
Packit |
89ede9 |
to->data[i] = from->data[i];
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* Returns pointer on success, NULL on error */
|
|
Packit |
89ede9 |
intlist *
|
|
Packit |
89ede9 |
intlist_dup( intlist *il )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
intlist *l;
|
|
Packit |
89ede9 |
int status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
l = intlist_new();
|
|
Packit |
89ede9 |
if ( l ) {
|
|
Packit |
89ede9 |
status = intlist_copy( l, il );
|
|
Packit |
89ede9 |
if ( status==INTLIST_MEMERR ) {
|
|
Packit |
89ede9 |
intlist_delete( l );
|
|
Packit |
89ede9 |
l = NULL;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return l;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_append( intlist *to, intlist *from )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int i, status;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( to );
|
|
Packit |
89ede9 |
assert( from );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
status = intlist_ensure_space( to, to->n + from->n );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( status == INTLIST_OK ) {
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=0; i<from->n; ++i )
|
|
Packit |
89ede9 |
to->data[ to->n + i ] = from->data[ i ];
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
to->n += from->n;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_append_unique( intlist *to, intlist *from )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
int i, nsave, status = INTLIST_OK;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( to );
|
|
Packit |
89ede9 |
assert( from );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
nsave = to->n;
|
|
Packit |
89ede9 |
for ( i=0; i<from->n; ++i ) {
|
|
Packit |
89ede9 |
if ( intlist_find( to, from->data[i] )!=-1 ) continue;
|
|
Packit |
89ede9 |
status = intlist_add( to, from->data[i] );
|
|
Packit |
89ede9 |
if ( status==INTLIST_MEMERR ) {
|
|
Packit |
89ede9 |
to->n = nsave;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
return status;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_get( intlist *il, int pos )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
assert( intlist_validn( il, pos ) );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return il->data[pos];
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
/* intlist_set()
|
|
Packit |
89ede9 |
*
|
|
Packit |
89ede9 |
* Returns INTLIST_OK
|
|
Packit |
89ede9 |
*/
|
|
Packit |
89ede9 |
int
|
|
Packit |
89ede9 |
intlist_set( intlist *il, int pos, int value )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
assert( intlist_validn( il, pos ) );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
il->data[pos] = value;
|
|
Packit |
89ede9 |
return INTLIST_OK;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
float
|
|
Packit |
89ede9 |
intlist_median( intlist *il )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
intlist *tmp;
|
|
Packit |
89ede9 |
float median;
|
|
Packit |
89ede9 |
int m1, m2;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( il->n==0 ) return 0.0;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
tmp = intlist_dup( il );
|
|
Packit |
89ede9 |
if ( !tmp ) return 0.0;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
intlist_sort( tmp );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( tmp->n % 2 == 1 ) {
|
|
Packit |
89ede9 |
median = intlist_get( tmp, tmp->n / 2 );
|
|
Packit |
89ede9 |
} else {
|
|
Packit |
89ede9 |
m1 = intlist_get( tmp, tmp->n / 2 );
|
|
Packit |
89ede9 |
m2 = intlist_get( tmp, tmp->n / 2 - 1);
|
|
Packit |
89ede9 |
median = ( m1 + m2 ) / 2.0;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
intlist_delete( tmp );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return median;
|
|
Packit |
89ede9 |
}
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
float
|
|
Packit |
89ede9 |
intlist_mean( intlist *il )
|
|
Packit |
89ede9 |
{
|
|
Packit |
89ede9 |
float sum = 0.0;
|
|
Packit |
89ede9 |
int i;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
assert( il );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
if ( il->n==0 ) return 0.0;
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
for ( i=0; i<il->n; ++i )
|
|
Packit |
89ede9 |
sum += intlist_get( il, i );
|
|
Packit |
89ede9 |
|
|
Packit |
89ede9 |
return sum / il->n;
|
|
Packit |
89ede9 |
}
|