"Example using single inheritance and Java/objective-C style interfaces"

/*************************************************************
 *  __  _   _   _   _                                        *
 * (_  |_) |_) |_| |_| |_/  Speech Processing, Recognition & *
 * __) |   | \ | | | | | \  Automatic Annotation Kit         *
 *                                                           *
 * Copyright 2006,2007,2008 K.U.Leuven                       *
 *                                                           *
 * Use of this software is governed by a License Agreement.  *
 * Modifications should be properly credited in line with    *
 * the License Agreement.                                    *
 *************************************************************/

#include <spraak/def.h>
#include <spraak/core/spr_oo.h>

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

/* same as taipan_cpp.c but now we use interfaces (which introduce more overhead) */


/*------------------------------------------------------------------------------*/
/*      The elementary types to put in the container types      */
/*------------------------------------------------------------------------------*/

/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef void Item;      /* a pure interface (fairly artificial, since we do need data to implement the reference counting) */

spr_public_lo_type
typedef struct
 {SprObject interface_;     /* avoid the use of 'interface', since Windows (more specific winsock.h) has problems with it */
  unsigned int ref_cnt;     /* how many parties reference this object */
 } DataItem;

spr_public_hi_class
SPR_CLASS(Item : SprInterface
 {spr_public lock[]()       = item_lock;
  spr_public unlock[]()     = item_unlock;
  spr_public cmp[]()        = item_cmp;
  spr_public hash[]()       = item_hash;
  spr_public read[]()       = item_read;
  spr_public write[]()      = item_write;
  spr_public clone[]()      = item_clone;
  spr_public dtor[]()       = item_dtor;
 } )
/*
An Item is a virtual class in the sense that it does not define the data. It
just defines a bunch of virtual methods to access the data.
In other words, this Item defines an interface which other objects can
implement.
*/
#define SPR_CLASS_IMPORT_Item
#include <spraak_classdef/taipan_objc.class.h>


spr_cmdoc spr_public_lo_ifunc
void item_lock(
  Item *item)
/*
Indicate that there is one more reference to this item.
Items will only be released (freeed) when there are zero reference to them.
*/
{++((DataItem*)item)->ref_cnt;
}

spr_cmdoc spr_public_lo_ifunc
void item_unlock(
  Item *item)
/*
Indicate that there is one less reference to this item and release the item
(free) if no one references the item any more.
*/
{if(--((DataItem*)item)->ref_cnt == 0)
   SPR_DO(Item,dtor,item);
}


spr_cmdoc spr_public_lo_func
int item_cmp(
  const Item *item1,        /* the first item in the comparion */
  const Item *item2)        /* the second item in the comparison */
/*
Compare the value of this item with the value of another item from the same class.
*/
;

spr_cmdoc spr_public_lo_func
uintptr_t item_hash(
  const Item *item)     /* item for which the hash value must be calculated */
/*
Calculate the hash value for the given item.
*/
;

spr_cmdoc spr_public_lo_func
int item_read(
  Item *item,           /* item for which the value must be set */
  FILE *fd)         /* file to read the value from */
/*
Set the value of an item to the value read from an open file.
*/
;

spr_cmdoc spr_public_lo_func
int item_write(
  const Item *item,     /* item for which the value must be written to file */
  FILE       *fd)       /* file to write the value to */
/*
Write the content of an item to an open file in a human readable format.
Note: the object on which the method is invoked must be the first argument.
*/
;

spr_cmdoc spr_public_lo_func
Item *item_clone(
  const Item *item)     /* item to clone */
/*
Make an exact duplicate of the object.
*/
;

spr_cmdoc spr_public_lo_func
void *item_dtor(
  Item *item)           /* item to 'destroy' */
/*
The item destructor.
*/
{free(item);
 return(NULL);
}


/* everything is there, so make the actual class */
#define SPR_CLASS_DEFINE_Item
#include <spraak_classdef/taipan_objc.class.h>


/*------------------------------------------------------------------------------*/
spr_public_hi_class
SPR_CLASS(DataItem : SprObject, Item
 {spr_public unlock[]()     := item_unlock; /* re-attached here to make it slower :-/ */
  spr_public lock[]()       := item_lock;   /* re-attached here to make it slower :-/ */
 } )
/*
Next to the 'interface' part, we now add a real (non virtual) part.
This real part provides reference counting (note: in C we can't make the
reference counting automatic since this requires support from the compiler).
*/
#define SPR_CLASS_IMPORT_DataItem
#include <spraak_classdef/taipan_objc.class.h>
#define SPR_CLASS_DEFINE_DataItem
#include <spraak_classdef/taipan_objc.class.h>



/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef struct
 {DataItem item;        /* implement the Item-interface */
  long value;
 } IntItem;

spr_public_hi_class
SPR_CLASS(IntItem : DataItem
 {spr_public static ctor()  = int_item_ctor;    /* constructors are never virtual: there is no pre-existing object! */
  /* let's make the virtual methods final (potentially faster) */
  spr_public cmp[]()        := int_item_cmp;
  spr_public hash[]()       := int_item_hash;
  spr_public read[]()       := int_item_read;
  spr_public write[]()      := int_item_write;
  spr_public clone[]()      := int_item_clone;
 } )
/*
An IntItem implements the Item class for an integer item.
*/
#define SPR_CLASS_IMPORT_IntItem
#include <spraak_classdef/taipan_objc.class.h>


/* Define the methods. This is a real class, so we have actual implementations. */

spr_cmdoc spr_public_lo_ifunc
IntItem *int_item_ctor(long value)
/*
Make a new item and set the reference count to 1.
Note: Since the method is not based on an existing object (this method creates
an object out of the blue), it must be a static method!
*/
{IntItem *item;
 if((item=malloc(sizeof(IntItem))) != NULL)
  {SPR_OBJECT_INIT(IntItem,item);           /* every object must be initialized! */
   item->item.ref_cnt = 1;
   item->value = value;
  }
 return(item);
}

spr_cmdoc spr_public_lo_afunc
int int_item_cmp(
  const IntItem *item1,
  const IntItem *item2)
/* Implements item_cmp(). */
{return((item1->value>item2->value)-(item1->value<item2->value));
}

spr_cmdoc spr_public_lo_afunc
uintptr_t int_item_hash(
  const IntItem *item)
/* Implements item_hash(). */
{return(item->value);
}

spr_cmdoc spr_public_lo_afunc
int int_item_read(
  IntItem *item,
  FILE    *fd)
/* Implements item_read(). */
{return(fscanf(fd,"%li",&item->value));
}

spr_cmdoc spr_public_lo_afunc
int int_item_write(
  const IntItem *item,
  FILE          *fd)
/* Implements item_write(). */
{return(fprintf(fd,"%li ",item->value));
}

spr_cmdoc spr_public_lo_afunc
IntItem *int_item_clone(
  const IntItem *item)
/* Implements item_clone(). */
{return(int_item_ctor(item->value));
}


#define SPR_CLASS_DEFINE_IntItem
#include <spraak_classdef/taipan_objc.class.h>


/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef struct
 {DataItem   item;      /* implement the Item-interface */
  double value;
 } FltItem;

spr_public_hi_class
SPR_CLASS(FltItem : DataItem
 {spr_public static ctor()  = flt_item_ctor;
  spr_public cmp[]()        = flt_item_cmp;
  spr_public hash[]()       = flt_item_hash;
  spr_public read[]()       = flt_item_read;
  spr_public write[]()      = flt_item_write;
  spr_public clone[]()      = flt_item_clone;
 } )
/*
An FltItem implements the Item class for an floating-point item.
*/
#define SPR_CLASS_IMPORT_FltItem
#include <spraak_classdef/taipan_objc.class.h>


/* Define the methods. This is a real class, so we have actual implementations. */

spr_cmdoc spr_public_lo_ifunc
FltItem *flt_item_ctor(double value)
/*
Make a new item.
Note: Since the method is not based on an existing object (this method creates
an object out of the blue), it must be a static method!
*/
{FltItem *item;
 if((item=malloc(sizeof(FltItem))) != NULL)
  {SPR_OBJECT_INIT(FltItem,item);               /* every object must be initialized! */
   item->item.ref_cnt = 1;
   item->value = value;
  }
 return(item);
}

spr_cmdoc spr_public_lo_afunc
int flt_item_cmp(
  const FltItem *item1,
  const FltItem *item2)
/* Implements item_cmp(). */
{return((item1->value>item2->value)-(item1->value<item2->value));
}

spr_cmdoc spr_public_lo_afunc
uintptr_t flt_item_hash(
  const FltItem *item)
/* Implements item_hash(). */
{uintptr_t hv = ((uintptr_t*)(void*)&item->value)[0];
 if(sizeof(double) >= 2*sizeof(uintptr_t))
   hv ^= ((uintptr_t*)&item->value)[1];
 if(sizeof(double) >= 3*sizeof(uintptr_t))
   hv ^= ((uintptr_t*)&item->value)[2];
 if(sizeof(double) >= 4*sizeof(uintptr_t))
   hv ^= ((uintptr_t*)&item->value)[3];
 return(hv);
}

spr_cmdoc spr_public_lo_afunc
int flt_item_read(
  FltItem *item,
  FILE    *fd)
/* Implements item_read(). */
{return(fscanf(fd,"%lf",&item->value));
}

spr_cmdoc spr_public_lo_afunc
int flt_item_write(
  const FltItem *item,
  FILE          *fd)
/* Implements item_write(). */
{return(fprintf(fd,"%.15g ",item->value));
}

spr_cmdoc spr_public_lo_afunc
FltItem *flt_item_clone(
  const FltItem *item)
/* Implements item_clone(). */
{return(flt_item_ctor(item->value));
}


#define SPR_CLASS_DEFINE_FltItem
#include <spraak_classdef/taipan_objc.class.h>


/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef struct
 {DataItem item;        /* implement the Item-interface */
  char *value;
 } StrItem;

spr_public_hi_class
SPR_CLASS(StrItem : DataItem
 {spr_public static ctor()  = str_item_ctor;
  spr_public cmp[]()        = str_item_cmp;
  spr_public hash[]()       = str_item_hash;
  spr_public read[]()       = str_item_read;
  spr_public write[]()      = str_item_write;
  spr_public clone[]()      = str_item_clone;
  spr_public dtor[]()       = str_item_dtor;
 } )
/*
An StrItem implements the Item class for a string item.
*/
#define SPR_CLASS_IMPORT_StrItem
#include <spraak_classdef/taipan_objc.class.h>


/* Define the methods. This is a real class, so we have actual implementations. */

spr_cmdoc spr_public_lo_ifunc
StrItem *str_item_ctor(const char *value)
/*
Make a new item.
Note: Since the method is not based on an existing object (this method creates
an object out of the blue), it must be a static method!
*/
{StrItem *item;
 if((item=malloc(sizeof(StrItem))) != NULL)
  {char *buf;
   SPR_OBJECT_INIT(StrItem,item);       /* every object must be initialized! */
   item->item.ref_cnt = 1;
   if(value == NULL)
     item->value = NULL;
   else
    {if((item->value=buf=malloc(strlen(value)+1)) == NULL)
       goto ERROR_;
     strcpy(buf,value);
    }
  }
 return(item);
ERROR_:
 free(item);
 return(item);
}

spr_cmdoc spr_public_lo_afunc
int str_item_cmp(
  const StrItem *item1,
  const StrItem *item2)
/* Implements item_cmp(). */
{if(item1->value != NULL)
  {if(item2->value != NULL)
     return(strcmp(item1->value,item2->value));
   else
     return(0);
  }
 else
   return(item2->value!=NULL);
}

spr_cmdoc spr_public_lo_afunc
uintptr_t str_item_hash(
  const StrItem *item)
/* Implements item_hash(). */
{uintptr_t hv = 1u;
 const char *ptr;
 if((ptr=item->value) != NULL)
  {unsigned int chr;
   do
    {hv = hv*8191u + (chr=*ptr++);
    } while(chr);
  }
 return(hv);
}

spr_cmdoc spr_public_lo_afunc
int str_item_read(
  StrItem *item,
  FILE    *fd)
/* Implements item_read(). */
{char buf[1024];
 int  rv;
 if((rv=fscanf(fd,"%1023s",buf)) == 1)
  {char *ptr;
   if((ptr=realloc(item->value,strlen(buf)+1)) == NULL)
     goto ERROR_;
   strcpy(ptr,buf);
   item->value = ptr;
  }
 return(rv);
ERROR_:
 return(-1);
}

spr_cmdoc spr_public_lo_afunc
int str_item_write(
  const StrItem *item,
  FILE          *fd)
/* Implements item_write(). */
{return(fprintf(fd,"%s ",item->value));
}

spr_cmdoc spr_public_lo_afunc
StrItem *str_item_clone(
  const StrItem *item)
/* Implements item_clone(). */
{return(str_item_ctor(item->value));
}


spr_cmdoc spr_public_lo_afunc
void *str_item_dtor(
  StrItem *item)        /* item to 'destroy' */
/* Implements item_dtor(). */
{free(item->value);
 free(item);
 return(NULL);
}


#define SPR_CLASS_DEFINE_StrItem
#include <spraak_classdef/taipan_objc.class.h>


/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef struct
 {DataItem item;        /* implement the Item-interface */
  unsigned int N;       /* number of elements in the tupple */
  Item *el[];           /* the elements */
 } Tuple;

spr_public_hi_class
SPR_CLASS(Tuple : DataItem
 {spr_public static ctor()  = tuple_ctor;
  spr_public static ctor_add()  = tuple_ctor_add;
  spr_public cmp[]()        = tuple_cmp;
  spr_public hash[]()       = tuple_hash;
  spr_public read[]()       = tuple_read;
  spr_public write[]()      = tuple_write;
  spr_public clone[]()      = tuple_clone;
  spr_public dtor[]()       = tuple_dtor;
 } )
/*
A Tuple implements the Item class for a collection of things;
*/
#define SPR_CLASS_IMPORT_Tuple
#include <spraak_classdef/taipan_objc.class.h>


/* Define the methods. This is a real class, so we have actual implementations. */

spr_cmdoc spr_public_lo_afunc
/*
Make a new tuple based on a NULL terminated list of items.
Note: Since the method is not based on an existing object (this method creates
an object out of the blue), it must be a static method!
*/
Tuple *tuple_ctor(Item *item,...)
{va_list argptr;
 Tuple *tuple;
 va_start(argptr,item);
 /* loc. var. */
  {int N;
   if((N=(item!=NULL)))
     while(va_arg(argptr,Item*) != NULL)
       N++;
   va_end(argptr);
   if((tuple=malloc(offsetof(Tuple,el)+sizeof(Item*)*N)) == NULL)
     goto ERROR_;
  }
 SPR_OBJECT_INIT(Tuple,tuple);      /* every object must be initialized! */
 tuple->item.ref_cnt = 1;
 va_start(argptr,item);
 /* loc. var. */
  {int  ndx = 0;
   for( ;item!=NULL;item=va_arg(argptr,Item*))
    {tuple->el[ndx] = item;
     SPR_DO(Item,lock,item);
     ndx++;
    }
   tuple->N = ndx;
   va_end(argptr);
  }
 return(tuple);
ERROR_:
 return(NULL);
}

spr_cmdoc spr_public_lo_afunc
/*
Create a new tupple by adding one extra item to an existing tuple.
*/
Tuple *tuple_ctor_add(Tuple *tuple,Item *item)
{Tuple *new_tuple;
 int   ndx;
 if((new_tuple=malloc(offsetof(Tuple,el)+sizeof(Item*)*((ndx=tuple->N)+1))) == NULL)
    goto ERROR_;
 SPR_OBJECT_INIT(Tuple,new_tuple);  /* every object must be initialized! */
 new_tuple->item.ref_cnt = 1;
 new_tuple->N = ndx+1;
 for( ;; )
  {new_tuple->el[ndx] = item;
   SPR_DO(Item,lock,item);
   if(--ndx < 0)
     break;
   item = tuple->el[ndx];
  }
ERROR_:
 return(new_tuple);
}

spr_cmdoc spr_public_lo_afunc
int tuple_cmp(
  const Tuple *tuple1,
  const Tuple *tuple2)
/* Implements item_cmp(). */
{unsigned int ndx,N;
 if((N=tuple1->N) > tuple2->N)
   N = tuple2->N;
 for(ndx=0;ndx<N;ndx++)
  {int rv = SPR_DO(Item,cmp,tuple1->el[ndx],tuple2->el[ndx]);
   if(rv)
     return(rv);
  }
 return(tuple1->N-tuple2->N);
}

spr_cmdoc spr_public_lo_afunc
uintptr_t tuple_hash(
  const Tuple *tuple)
/* Implements item_hash(). */
{int ndx = tuple->N;
 const Item *const *el = tuple->el-1;
 uintptr_t hv = 0;
 while(--ndx >= 0)
  {++el;                /* can't do ++el in the SPR_DO() macro!!! */
   hv = hv*31 + SPR_DO(Item,hash,*el);
  }
 return(hv);
}

spr_cmdoc spr_public_lo_afunc
int tuple_read(
  Tuple *tuple,
  FILE  *fd)
/* Implements item_read(). */
{int ndx = tuple->N;
 Item **el = tuple->el-1;
 while(--ndx >= 0)
  {++el;                /* can't do ++el in the SPR_DO() macro!!! */
   if(SPR_DO(Item,read,*el,fd) != 1)
     return(ndx-tuple->N);
  }
 return(1);
}

spr_cmdoc spr_public_lo_afunc
int tuple_write(
  const Tuple *tuple,
  FILE        *fd)
/* Implements item_write(). */
{int ndx = tuple->N;
 const Item *const *el = tuple->el-1;
 while(--ndx >= 0)
  {++el;                /* can't do ++el in the SPR_DO() macro!!! */
   if(SPR_DO(Item,write,*el,fd) <= 0)
     return(-1);
  }
 return(1);
}

spr_cmdoc spr_public_lo_afunc
void *tuple_dtor(
  Tuple *tuple)             /* tuple to 'destroy' */
/* Implements item_dtor(). */
{int ndx = tuple->N;
 Item **el = tuple->el-1;
 while(--ndx >= 0)
  {++el;                /* can't do ++el in the SPR_DO() macro!!! */
   SPR_DO(Item,unlock,*el);
  }
 free(tuple);
 return(NULL);
}


spr_cmdoc spr_public_lo_afunc
Tuple *tuple_clone(
  const Tuple *tuple)
/* Implements item_clone(). */
{int N = tuple->N;
 Tuple *new_tuple;
 if((new_tuple=malloc(offsetof(Tuple,el)+sizeof(Item*)*N)) != NULL)
  {int ndx;
   SPR_OBJECT_INIT(Tuple,new_tuple);        /* every object must be initialized! */
   new_tuple->item.ref_cnt = 1;
   new_tuple->N = N;
   for(ndx=0;ndx<N;ndx++)
    {const Item *el = tuple->el[ndx];
     if((new_tuple->el[ndx]=SPR_DO(Item,clone,el)) == NULL)
      {new_tuple->N = ndx;
       return(tuple_dtor(new_tuple));
      }
    }
  }
 return(new_tuple);
}


#define SPR_CLASS_DEFINE_Tuple
#include <spraak_classdef/taipan_objc.class.h>


/*------------------------------------------------------------------------------*/
/*              The container interfaces            */
/*------------------------------------------------------------------------------*/

/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef void Iterable;

spr_public_lo_type
typedef void Iterator;

spr_public_hi_class
SPR_CLASS(Iterable : SprInterface
 {spr_public iterator[]()   = iterable_iterator;
 } )
/*
The Iterable interface is very simple: the object must be able to provide an
'Iterator' object that allows iterating through all items in a
deterministic order.
*/
#define SPR_CLASS_IMPORT_Iterable
#include <spraak_classdef/taipan_objc.class.h>

spr_cmdoc spr_public_lo_afunc
Iterator *iterable_iterator(
  const Iterable *obj)      /* an Iterable object */
/*
Provide an 'Iterator' object that allows iterating through all items in a
deterministic order.
*/
;


#define SPR_CLASS_DEFINE_Iterable
#include <spraak_classdef/taipan_objc.class.h>


spr_public_hi_class
SPR_CLASS(Iterator : Iterable
 {spr_public item[]()       = iterator_item;
  spr_public next[]()       = iterator_next;
  spr_public iterator[]()   = iterator_iterator;
 } )
/*
The Iterator allows iterating through all items in a list, vector, ...
By itself, an Iterator is again Iterable.
*/
#define SPR_CLASS_IMPORT_Iterator
#include <spraak_classdef/taipan_objc.class.h>


spr_cmdoc spr_public_lo_afunc
Item *iterator_item(
  Iterator *iter)       /* the Iterator */
/*
Get the <i>i</i>'th item of the list (<i>i</i> being the number of time method
'iter_next' was called before).
Note: the reference count for the returned item is not changed.
In other words, if your algorithm end up setting one or more extra references
to the item, you must call the item_lock() method!
*/
;

spr_cmdoc spr_public_lo_afunc
Iterator *iterator_next(
  Iterator *iter)       /* the Iterator */
/*
Go to the <i>(i+1)</i>'th item of the list (<i>i</i> being the number of time
method 'iter_next' was called before).
*/
;

spr_cmdoc spr_public_lo_afunc
Iterator *iterator_iterator(    /* the Iterator */
  const Iterator *iter)
/*
Make a new iterator (clone the current one).
*/
;


#define SPR_CLASS_DEFINE_Iterator
#include <spraak_classdef/taipan_objc.class.h>


/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef void Queue;

spr_public_hi_class
SPR_CLASS(Queue : SprInterface
 {spr_public push[]()   = queue_push;
  spr_public pop[]()    = queue_pop;
  spr_public toq[]()    = queue_toq;
  spr_public empty[]()  = queue_empty;
 } )
/*
The Queue allows pushing and popping items and testing if the Queue is empty.
*/
#define SPR_CLASS_IMPORT_Queue
#include <spraak_classdef/taipan_objc.class.h>

spr_cmdoc spr_public_lo_afunc
Item *queue_push(
  Queue *queue,     /* the queue */
  Item  *item)      /* the item to push */
/*
Push an item onto the Queue. The reference count of the item is
increased by one.
Returns the item itself if successful and NULl otherwise.
*/
;

spr_cmdoc spr_public_lo_afunc
Item *queue_pop(
  Queue *queue)     /* the queue */
/*
Pop an item from the Queue. The reference count of the item is not adjusted.
The caller must make sure to call the item_unlock() method when it stops
refering to the popped item.
Note: the order in which items are popped depends on the type of Queue.
*/
;

spr_cmdoc spr_public_lo_afunc
Item *queue_toq(
  Queue *queue)     /* the queue */
/*
Get the top item of the queue, but unlike queue_pop() do not remove the item
from the queue.
The reference count of the item is not adjusted. The caller must make sure to
call the item_lock() method when it adds extra references to the item.
Note: which item is the top item depends on the type of Queue.
*/
;

spr_cmdoc spr_public_lo_afunc
int queue_empty(
  Queue *queue)     /* the queue */
/*
Check if the queue is empty.
*/
;


#define SPR_CLASS_DEFINE_Queue
#include <spraak_classdef/taipan_objc.class.h>


/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef void Container;

spr_public_hi_class
SPR_CLASS(Container : Iterable
 {spr_public get[]()    = container_get;
  spr_public add[]()    = container_add;
  spr_public cadd[]()   = container_cadd;
  spr_public remove[]() = container_remove;
 } )
/*
A Container contains indexable Items (and is iterable).
Depending on the type of the container, the type of the index may be
constrained to certain types.
*/
#define SPR_CLASS_IMPORT_Container
#include <spraak_classdef/taipan_objc.class.h>

spr_cmdoc spr_public_lo_afunc
Item *container_get(
  const Container *container,   /* the container */
  const Item      *ndx)     /* index of element to get() */
/*
Get an element from the container.
If the element is not in the container, a NULL is returned.
Note: the reference count is left unchanged.
*/
;

spr_cmdoc spr_public_lo_afunc
Item *container_add(
  Container *container,     /* the container */
  Item      *ndx,       /* index of the (new) element */
  Item      *el)        /* element to store in the container */
/*
Add an element to the container and return that element.
If an element is overwritten, the element is unlocked and deallocated if no one
references it any more (see item_unlock()).
If the operation fails (no more room, <ndx> out of bounds, ...) a NULL is
returned.
*/
;

spr_cmdoc spr_public_lo_afunc
Item *container_cadd(
  Container *container,     /* the container */
  Item      *ndx,       /* index of the (new) element */
  Item      *el)        /* element to store in the container */
/*
Conditionally add an element to the container and return that element.
If an old element was already stored at the requested location <ndx>, the cadd
operation fails and a NULL is returned.
*/
;

spr_cmdoc spr_public_lo_afunc
Item *container_remove(
  Container  *container,    /* the container */
  const Item *ndx)      /* index of the item to remove */
/*
Remove the element with the given index <ndx> from the container.
A NULL is returned if no element was found with the given index.
The reference count of the element is not adjusted. The caller must make sure
to call the item_unlock() method when it stops refering to the popped element.
*/
;


#define SPR_CLASS_DEFINE_Container
#include <spraak_classdef/taipan_objc.class.h>


/*------------------------------------------------------------------------------*/
/*          The actual container types              */
/*------------------------------------------------------------------------------*/


/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef struct t_stack_el
 {Item *item;
  struct t_stack_el *next;
 } StackEl;

spr_public_lo_type
typedef struct
 {SprObject interface_;
  StackEl  *stackel;
 } StackIterator;

spr_public_hi_class
SPR_CLASS(StackIterator : SprObject, Iterator
 {/* implement the Iterator interface */
  spr_public item[]()       := stack_iterator_item;
  spr_public next[]()       := stack_iterator_next;
  spr_public iterator[]()   := stack_iterator_iterator;
 } )
/*
Implementation of a stack iterator.
*/
#define SPR_CLASS_IMPORT_StackIterator
#include <spraak_classdef/taipan_objc.class.h>

spr_cmdoc spr_public_lo_afunc
Item *stack_iterator_item(
  StackIterator *iter)
/* Implements iterator_item(). */
{return(iter->stackel->item);
}

spr_cmdoc spr_public_lo_afunc
StackIterator *stack_iterator_next(
  StackIterator *iter)
/* Implements iterator_next(). */
{StackEl *stackel = iter->stackel->next;
 if(stackel != NULL)
  {iter->stackel = stackel;
   return(iter);
  }
 else
  {free(iter);
   return(NULL);
  }
}

spr_cmdoc spr_public_lo_afunc
StackIterator *stack_iterator_iterator(
  const StackIterator *iter)
/* Implements iterator_iterator(). */
{if(iter != NULL)
  {StackIterator *new_iter;
   if((new_iter=malloc(sizeof(StackIterator))) != NULL)
     *new_iter = *iter;         /* do this only if you are 100% sure that 'StackIterator' cannot be sub-classed, cannot be embedded, ... */
   return(new_iter);
  }
 return((StackIterator*)iter);
}


#define SPR_CLASS_DEFINE_StackIterator
#include <spraak_classdef/taipan_objc.class.h>


spr_public_lo_type
typedef struct
 {SprObject interface_;
  StackEl  *tos;            /* top of the stack */
 } Stack;

spr_public_hi_class
SPR_CLASS(Stack : SprObject, Queue, Iterable
 {/* implement the Queue interface */
  spr_public push[]()       := stack_push;
  spr_public pop[]()        := stack_pop;
  spr_public toq[]()        := stack_tos;
  spr_public empty[]()      := stack_empty;
  /* implement the Iterable interface */
  spr_public iterator[]()   = stack_iterator;
  /* implement some new methods */
  spr_public dtor()     = stack_dtor;
  spr_public static ctor()  = stack_ctor;
 } )
/*
Implementation of a stack using single linked lists.
Note: if the Stack class also implemented the Item interface, we could make
stack of stacks, ...
*/
#define SPR_CLASS_IMPORT_Stack
#include <spraak_classdef/taipan_objc.class.h>


spr_cmdoc spr_public_lo_afunc
void *stack_dtor(
  Stack *stack)
/*
Destroy an existing stack object.
*/
{StackEl *stackel;
 for(stackel=stack->tos;stackel!=NULL; )
  {StackEl *tmp = stackel;
   stackel = stackel->next;
   SPR_DO(Item,unlock,tmp->item);
   free(tmp);
  }
 free(stack);
 return(NULL);
}

spr_cmdoc spr_public_lo_afunc
Stack *stack_ctor(void)
/*
Create a new stack.
*/
{Stack *stack;
 if((stack=malloc(sizeof(Stack))) != NULL)
  {SPR_OBJECT_INIT(Stack,stack);            /* every object must be initialized! */
   stack->tos = NULL;
  }
 return(stack);
}

spr_cmdoc spr_public_lo_afunc
Item *stack_push(
  Stack *stack,
  Item *item)
/* Implements queue_push(). */
{StackEl *stackel;
 if((stackel=malloc(sizeof(StackEl))) == NULL)
   goto ERROR_;
 stackel->next = stack->tos;
 stackel->item = item;
 SPR_DO(Item,lock,item);
 stack->tos = stackel;
 return(item);
ERROR_:
 return(NULL);
}

spr_cmdoc spr_public_lo_afunc
Item *stack_pop(
  Stack *stack)
/* Implements queue_pop(). */
{StackEl *stackel = stack->tos;
 Item    *item;
 if(stackel == NULL)
   goto ERROR_;
 stack->tos = stackel->next;
 item = stackel->item;
 free(stackel);
 return(item);
ERROR_:
 return(NULL);
}


spr_cmdoc spr_public_lo_afunc
Item *stack_tos(
  Stack *stack)
/* Implements queue_toq(). */
{return((stack->tos!=NULL)?stack->tos->item:NULL);
}

spr_cmdoc spr_public_lo_afunc
int stack_empty(
  Stack *stack)
/* Implements queue_empty(). */
{return(stack->tos==NULL);
}

spr_cmdoc spr_public_lo_afunc
StackIterator *stack_iterator(
  const Stack *stack)
/* Implements iterable_iterator(). */
{StackIterator *iter;
 if((iter=malloc(sizeof(StackIterator))) != NULL)
  {SPR_OBJECT_INIT(StackIterator,iter);
   iter->stackel = stack->tos;
  }
 return(iter);
}


#define SPR_CLASS_DEFINE_Stack
#include <spraak_classdef/taipan_objc.class.h>


/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef struct
 {SprObject    interface_;      /* implements the Queue interface */
  Item         **heap;          /* the actual heap */
  unsigned int size;            /* the maximum size of the heap */
  unsigned int fill;            /* the heap is filled up till element <fill> */
 } HeapMin;

spr_public_hi_class
SPR_CLASS(HeapMin : SprObject, Queue
 {/* implements the Queue interface */
  spr_public push[]()       = heap_min_push;
  spr_public pop[]()        = heap_min_pop;
  spr_public toq[]()        = heap_min_toq;
  spr_public empty[]()      = heap_min_empty;
  /* implement some new methods */
  spr_public dtor()     = heap_min_dtor;
  spr_public static ctor()  = heap_min_ctor;
 } )
/*
Implements a heap with the smallest item on top.
*/
#define SPR_CLASS_IMPORT_HeapMin
#include <spraak_classdef/taipan_objc.class.h>


spr_cmdoc spr_public_lo_afunc
void *heap_min_dtor(HeapMin *heap)
/*
Destroy an existing heap object.
*/
{int    ndx = heap->fill;
 Item **tbl = heap->heap;
 while(--ndx >= 0)
   SPR_DO(Item,unlock,tbl[ndx]);
 free(tbl);
 free(heap);
 return(NULL);
}

spr_cmdoc spr_public_lo_afunc
HeapMin *heap_min_ctor(
  int size)             /* initial size of the heap */
/*
Create a new heap.
*/
{HeapMin *heap;
 if((heap=malloc(sizeof(HeapMin))) != NULL)
  {SPR_OBJECT_INIT(HeapMin,heap);   /* every object must be initialized! */
   heap->size = size;
   heap->fill = 0;
   if((heap->heap=malloc(sizeof(Item*)*size)) == NULL)
     return(heap_min_dtor(heap));
  }
 return(heap);
}

spr_cmdoc spr_public_lo_afunc
Item *heap_min_push(
  HeapMin *heap,
  Item    *item)
/* Implements queue_push(). */
{Item **tbl = heap->heap;
 unsigned int ndx_c,ndx_p;
 if(heap->fill == heap->size)
  {if((tbl=realloc(tbl,sizeof(Item*)*(heap->size+=31+(heap->size>>2)))) == NULL)
    {heap->size = heap->fill;
     goto ERROR_;
    }
   heap->heap = tbl;
  }
 ndx_c = heap->fill++;
 while(ndx_c && (SPR_DO(Item,cmp,item,tbl[ndx_p=(ndx_c-1)/2u])<0))
  {tbl[ndx_c] = tbl[ndx_p];
   ndx_c = ndx_p;
  }
 tbl[ndx_c] = item;
 SPR_DO(Item,lock,item);
 return(item);
ERROR_:
 return(NULL);
}

spr_cmdoc spr_public_lo_afunc
Item *heap_min_pop(
  HeapMin *heap)
/* Implements queue_pop(). */
{Item **tbl = heap->heap;
 Item *rv,*item;
 unsigned int ndx_c,ndx_p,fill;
 if((fill=heap->fill) == 0)
   goto ERROR_;
 rv = tbl[0];
 item = tbl[heap->fill=--fill];
 ndx_p = 0;
 ndx_c = 2;
 while(ndx_c <= fill)
  {if((ndx_c==fill) || (SPR_DO(Item,cmp,tbl[ndx_c-1],tbl[ndx_c])<0))
     ndx_c--;
   if(SPR_DO(Item,cmp,item,tbl[ndx_c]) < 0)
     break;
   tbl[ndx_p] = tbl[ndx_c];
   ndx_c = (ndx_p=ndx_c)*2+2;
  }
 tbl[ndx_p] = item;
 if((fill*2+32<=heap->size) && ((tbl=realloc(tbl,sizeof(Item*)*(fill+=fill/2u)))!=NULL))
  {heap->heap = tbl;
   heap->size = fill;
  }
 return(rv);
ERROR_:
 return(NULL);
}


spr_cmdoc spr_public_lo_afunc
Item *heap_min_toq(
  HeapMin *heap)
/* Implements queue_toq(). */
{return(heap->fill?heap->heap[0]:NULL);
}

spr_cmdoc spr_public_lo_afunc
int heap_min_empty(
  HeapMin *heap)
/* Implements queue_empty(). */
{return(heap->fill==0);
}


#define SPR_CLASS_DEFINE_HeapMin
#include <spraak_classdef/taipan_objc.class.h>


/*------------------------------------------------------------------------------*/
spr_public_lo_type
typedef struct t_hash_el
 {const Item *ndx;          /* the item index */
  Item *value;              /* the value */
  struct t_hash_el *next;
 } HashEl;

spr_public_lo_type
typedef struct
 {SprObject    interface_;      /* implements the Container & Queue interface */
  HashEl       **htbl;          /* the actual hash table */
  HashEl       *list;           /* the hash elements (one large array for efficiency reasons) */
  HashEl       *free_list;      /* the unused hash elements for the list */
  const HashEl *toq;            /* top of the queue */
  StrItem      *none;           /* an empty object, used when pushing items since then there is no value */
  unsigned int size;            /* the maximum size of the hash table */
  unsigned int fill;            /* the hash table is filled with <fill> items */
  unsigned int max_size;        /* max. used elements */
 } Hash;

spr_public_lo_type
typedef struct
 {SprObject iterface_;          /* implements the Iterator interface */
  const HashEl *ptr;            /* the pointer to the next element */
  unsigned int rem_cnt;         /* remaining number of possible items */
  const HashEl *list;           /* the list; used for checking */
  unsigned int size;            /* the size of the hash table; used for checking */
  const Hash *hash;         /* the hash table; used for checking */
 } HashIterator;

spr_public_hi_class
SPR_CLASS(Hash : SprObject, Container, Queue
 {/* implements the Container interface */
  spr_public get[]()        = hash_get;
  spr_public add[]()        = hash_add;
  spr_public cadd[]()       = hash_cadd;
  spr_public remove[]()     = hash_remove;
  /* implements the Iterable interface */
  spr_public iterator[]()   = hash_iterator;
  /* implements the Queue interface */
  spr_public push[]()       = hash_push;
  spr_public pop[]()        = hash_pop;
  spr_public toq[]()        = hash_toq;
  spr_public empty[]()      = hash_empty;
  /* implement some new methods */
  spr_public dtor()     = hash_dtor;
  spr_public static ctor()  = hash_ctor;
 } )
/*
Implements a heap with the smallest item on top.
*/
#define SPR_CLASS_IMPORT_Hash
#include <spraak_classdef/taipan_objc.class.h>

spr_public_hi_class
SPR_CLASS(HashIterator : SprObject, Iterator
 {/* implement the Iterator interface */
  spr_public item[]()       := hash_iterator_item;
  spr_public next[]()       := hash_iterator_next;
  spr_public iterator[]()   := hash_iterator_iterator;
 } )
#define SPR_CLASS_IMPORT_HashIterator
#include <spraak_classdef/taipan_objc.class.h>


spr_cmdoc spr_public_lo_afunc
Hash *hash_dtor(
  Hash *hash)
/*
Destroy an existing hash table object.
*/
{HashEl *el = hash->list;
 if(el != NULL)
  {int cnt = hash->max_size;
   while(--cnt >= 0)
    {if(el->ndx != NULL)
       SPR_DO(Item,unlock,(Item*)el->ndx);
     if(el->value != NULL)
       SPR_DO(Item,unlock,el->value);
     el++;
    }
  }
 if(hash->none != NULL)
   SPR_DO(Tuple,unlock,hash->none);
 free(hash->list);
 free(hash->htbl);
 free(hash);
 return(NULL);
}

static Hash *hash_resize(
  Hash         *hash,
  unsigned int size)
{Hash *rv = NULL;
 if(size == 0)
  {size = hash->fill;
   size += (size>>1) + 15;
  }
 size |= 1;             /* best prime, but we settle for odd */
 /* fprintf(stderr,"resizing %p: %u -> %u (fill=%u)\n",hash,hash->size,size,hash->fill); */
 /* resize htbl */
  {HashEl **htbl;
   if((htbl=realloc(hash->htbl,sizeof(HashEl*)*size)) == NULL)
     goto ERROR_;
   hash->htbl = htbl;
  }
 /* reorganize data if shrinking */
 rv = hash;
 if(hash->max_size != hash->fill)
  {unsigned int ndx = hash->fill;
   HashEl *el = hash->list;
   if((ndx))
    {HashEl *free_list = NULL;
     do
      {if(el->ndx == NULL)
        {el->next = free_list;
         free_list = el;
        }
       ++el;
      } while(--ndx);
     ndx = hash->max_size-hash->fill;
     do
      {if(el->ndx != NULL)
        {free_list->ndx = el->ndx;
         free_list->value = el->value;
         free_list = free_list->next;
        }
       ++el;
      } while(--ndx);
    }
   hash->max_size = hash->fill;
   rv = NULL;
  }
 /* loc. var. */
  {HashEl *list;
   int ndx;
   if((list=realloc(hash->list,sizeof(HashEl)*size)) != NULL)
    {rv = hash;
     hash->size = size;
     hash->toq = hash->list = list;
    }
   else if(rv != NULL)
    {rv = NULL;             /* no need to rebuild */
     goto ERROR_;
    }
   else                 /* will probabely never happen: shrinking normally does not fail */
     size = hash->size;         /* rebuild using the original size */
   ndx = size-hash->fill;
   hash->free_list = (list+=hash->fill);
   while(--ndx > 0)
     list = (list->next=list+1);
   list->next = NULL;
  }
 /* loc. var. */
  {HashEl **htbl = hash->htbl + size;
   int  ndx = -(int)size;
   do
    {htbl[ndx] = NULL;
    } while(++ndx);
   if((ndx=hash->fill))
    {HashEl *el = hash->list;
     htbl = hash->htbl;
     do
      {HashEl **pos = &htbl[SPR_DO(Item,hash,el->ndx)%size];
       el->next = *pos;
       *pos = el++;
      } while(--ndx);
    }
  }
ERROR_:
 return(rv);
}

spr_cmdoc spr_public_lo_afunc
Hash *hash_ctor(
  int size)             /* initial size of the hash table */
/*
Create a new heap.
*/
{Hash *hash;
 if((hash=malloc(sizeof(Hash))) != NULL)
  {SPR_OBJECT_INIT(Hash,hash);      /* every object must be initialized! */
   hash->htbl = NULL;
   hash->list = NULL;
   hash->free_list = NULL;
   hash->none = NULL;
   hash->size = 0;
   hash->fill = 0;
   hash->max_size = 0;
   if(hash_resize(hash,size) == NULL)
     goto ERROR_;
   if((hash->none=SPR_DO(StrItem,ctor,NULL)) == NULL)
     goto ERROR_;
  }
 return(hash);
ERROR_:
 return(hash_dtor(hash));
}

spr_cmdoc spr_public_lo_afunc
Item *hash_get(
  const Hash *hash,
  const Item *ndx)
/* Implements container_get(). */
{const HashEl *el;
 for(el=hash->htbl[SPR_DO(Item,hash,ndx)%hash->size];el!=NULL;el=el->next)
   if(SPR_DO(Item,cmp,ndx,el->ndx) == 0)
     return(el->value);
 return(NULL);
}

spr_cmdoc spr_public_lo_afunc
Item *hash_add(
  Hash *hash,
  Item *ndx,
  Item *value)
/* Implements container_add(). */
{HashEl **link,*el;
 if((hash->free_list==NULL) && (hash_resize(hash,0)==NULL))
   return(NULL);
 for(el=*(link=&hash->htbl[SPR_DO(Item,hash,ndx)%hash->size]);el!=NULL;el=el->next)
  {if(SPR_DO(Item,cmp,ndx,el->ndx) == 0)
    {SPR_DO(Item,lock,value);
     SPR_DO(Item,unlock,el->value);
     el->value = value;
     return(value);
    }
  }
 el = hash->free_list;
 if(++hash->fill > hash->max_size)
   hash->max_size = hash->fill;
 hash->free_list = el->next;
 el->next = *link;
 el->ndx = ndx;
 el->value = value;
 *link = el;
 if(el < hash->toq)
   hash->toq = el;
 SPR_DO(Item,lock,ndx);
 SPR_DO(Item,lock,value);
 return(value);
}

spr_cmdoc spr_public_lo_afunc
Item *hash_cadd(
  Hash *hash,
  Item *ndx,
  Item *value)
/* Implements container_add(). */
{HashEl **link,*el;
 if((hash->free_list==NULL) && (hash_resize(hash,0)==NULL))
   return(NULL);
 for(el=*(link=&hash->htbl[SPR_DO(Item,hash,ndx)%hash->size]);el!=NULL;el=el->next)
   if(SPR_DO(Item,cmp,ndx,el->ndx) == 0)
     return(NULL);
 el = hash->free_list;
 if(++hash->fill > hash->max_size)
   hash->max_size = hash->fill;
 hash->free_list = el->next;
 el->next = *link;
 el->ndx = ndx;
 el->value = value;
 *link = el;
 if(el < hash->toq)
   hash->toq = el;
 SPR_DO(Item,lock,ndx);
 SPR_DO(Item,lock,value);
 return(value);
}

spr_cmdoc spr_public_lo_afunc
Item *hash_remove(
  Hash *hash,
  const Item *ndx)
/* Implements container_add(). */
{HashEl **link,*el;
 for(el=*(link=&hash->htbl[SPR_DO(Item,hash,ndx)%hash->size]);el!=NULL;el=*(link=&el->next))
  {if(SPR_DO(Item,cmp,ndx,el->ndx) == 0)
    {Item *value = el->value;
     *link = el->next;
     SPR_DO(Item,unlock,(Item*)el->ndx);
     el->next = hash->free_list;
     el->ndx = NULL;
     el->value = NULL;
     hash->free_list = el;
     if((--hash->fill)*2+48 <= hash->size)
       hash_resize(hash,0);
     return(value);
    }
  }
 return(NULL);
}

spr_cmdoc spr_public_lo_afunc
Item *hash_push(
  Hash *hash,
  Item *item)
/* Implements queue_push(). */
{return(hash_cadd(hash,item,SPR_CAST(Item,StrItem,hash->none)));
}

spr_cmdoc spr_public_lo_afunc
Item *hash_toq(
  Hash *hash)
/* Implements queue_toq(). */
{const HashEl *el = hash->toq;
 int          cnt = hash->max_size-(el-hash->list);
 for( ;--cnt>=0;++el)
   if(el->ndx != NULL)
     return((Item*)(hash->toq=el)->ndx);
 return(NULL);
}

spr_cmdoc spr_public_lo_afunc
Item *hash_pop(
  Hash *hash)
/* Implements queue_pop(). */
{HashEl *el = (HashEl*)hash->toq;
 int    cnt = hash->max_size-(el-hash->list);
 for( ;--cnt>=0;++el)
  {if(el->ndx != NULL)
    {Item   *ndx   = (Item*)el->ndx;
     HashEl **link = &hash->htbl[SPR_DO(Item,hash,ndx)%hash->size];
     hash->toq = el+1;
     /* loc. var. */
      {HashEl *tmp;
       while((tmp=*link) != el)
         link = &tmp->next;
      }
     *link = el->next;
     SPR_DO(Item,unlock,el->value);
     el->ndx = NULL;
     el->value = NULL;
     el->next = hash->free_list;
     hash->free_list = el;
     if((--hash->fill)*2+48 <= hash->size)
       hash_resize(hash,0);
     return(ndx);
    }
  }
 return(NULL);
}

spr_cmdoc spr_public_lo_afunc
int hash_empty(
  Hash *hash)
/* Implements queue_empty(). */
{return(hash->fill==0);
}


spr_cmdoc spr_public_lo_afunc
Iterator *hash_iterator(
  const Hash *hash)
/* Implements iterable_iterator(). */
{HashIterator *iter;
 if((iter=malloc(sizeof(HashIterator))) != NULL)
  {int rem_cnt;
   const HashEl *ptr;
   SPR_OBJECT_INIT(HashIterator,iter);  /* every object must be initialized! */
   if((rem_cnt=hash->max_size-((ptr=hash->toq)-(iter->list=hash->list))) > 0)
    {iter->size = hash->size;
     iter->hash = hash;
     do
      {if(ptr->ndx != NULL)
        {iter->rem_cnt = rem_cnt;
         iter->ptr = ptr;
         return(SPR_CAST(Iterator,HashIterator,iter));
        }
       ptr++;
      } while(--rem_cnt > 0);
    }
   free(iter);
  }
 return(NULL);
}


#define SPR_CLASS_DEFINE_Hash
#include <spraak_classdef/taipan_objc.class.h>


spr_cmdoc spr_public_lo_afunc
Iterator *hash_iterator_next(
  HashIterator *iter)
/* Implements iterator_next(). */
{if((iter->size==iter->hash->size) && (iter->list==iter->hash->list))
  {const HashEl *ptr = iter->ptr;
   int rem_cnt = iter->rem_cnt;
   while(--rem_cnt> 0)
    {if((++ptr)->ndx != NULL)
      {iter->ptr = ptr;
       iter->rem_cnt = rem_cnt;
       return(SPR_CAST(Iterator,HashIterator,iter));
      }
    }
  }
 else
   fprintf(stderr,"Hash table %p was modified during loop\n",iter->hash);
 free(iter);
 return(NULL);
}

spr_cmdoc spr_public_lo_afunc
Item *hash_iterator_item(
  HashIterator *iter)
/* Implements iterator_item(). */
{return((Item*)iter->ptr->ndx);
}

spr_cmdoc spr_public_lo_afunc
Iterator *hash_iterator_iterator(
  const HashIterator *iter)
/* Implements iterator_iterator(). */
{if(iter != NULL)
  {HashIterator *new_iter;
   if((new_iter=malloc(sizeof(HashIterator))) != NULL)
     *new_iter = *iter;         /* do this only if you are 100% sure that 'StackIterator' cannot be sub-classed, cannot be embedded, ... */
   return(SPR_CAST(Iterator,HashIterator,new_iter));
  }
 return((Iterator*)iter);
}


#define SPR_CLASS_DEFINE_HashIterator
#include <spraak_classdef/taipan_objc.class.h>



/*------------------------------------------------------------------------------*/
static Item *make_item_example(const char *desc)
{Item *item = NULL;
 if(strcmp(desc,"int") == 0)
   item = SPR_CAST(Item,IntItem,SPR_DO(IntItem,ctor,0));
 else if(strcmp(desc,"float") == 0)
   item = SPR_CAST(Item,FltItem,SPR_DO(FltItem,ctor,0.0));
 else if(strcmp(desc,"str") == 0)
   item = SPR_CAST(Item,StrItem,SPR_DO(StrItem,ctor,NULL));
 else
   fprintf(stderr,"datatype must be int, float or str\n");
 return(item);
}

int main(int argc,char *argv[])
{int rv = 1;
 void  *op = NULL;
 Item  *item0 = NULL;
 Item  *item1 = NULL;
 Queue *queue;
 
 if((argc<3))
  {fprintf(stderr,"Use: spr_oo_tst <op>(sort/reverse/unique/unique1) <datatype1>(int/float/str) [datatype2](int/float/str) ...\nRead a sequence of <datatype1> items or (<datatype1>,<datatype2>,...) tuples from stdin (seperated by spaces and/or new-lines) and either sort them, reverse them or filter out duplicates (based on the first item in a tuple if op=unique1) and write the result to stdout.\n");
   return(1);
  }
 if(strcmp(argv[1],"sort") == 0)
  {op = SPR_DO(HeapMin,ctor,100);
   queue = SPR_CAST(Queue,HeapMin,(HeapMin*)op);
  }
 else if(strcmp(argv[1],"reverse") == 0)
  {op = SPR_DO(Stack,ctor);
   queue = SPR_CAST(Queue,Stack,(Stack*)op);
  }
 else if((strcmp(argv[1],"unique")==0) || (strcmp(argv[1],"unique1")==0))
  {op = SPR_DO(Hash,ctor,100);
   queue = SPR_CAST(Queue,Hash,(Hash*)op);
  }
 else
  {fprintf(stderr,"op must be sort, reverse, unique or unique1\n");
   goto ERROR_;
  }
 if((item0=make_item_example(argv[2])) == NULL)
   goto ERROR_;
 if(argc > 3)           /* make a tuple or in the case of unique1, a pair of items (with item0 a tuple if there are more than 2 items to group) */
  {int iarg = 3;
   if(strcmp(argv[1],"unique1") == 0)
    {item1 = item0;     /* item1 is the key, item0 is the value (tuple) */
     if((item0=make_item_example(argv[3])) == NULL)
       goto ERROR_;
     iarg = 4;
    }
   if(iarg < argc)
    {Tuple *tuple;
     if((tuple=SPR_DO(Tuple,ctor,item0,NULL)) == NULL)
       goto ERROR_;
     SPR_DO(Item,unlock,item0);
     item0 = SPR_CAST(Item,Tuple,tuple);
     while(iarg < argc)
      {Item *item;
       Tuple *prev_tuple;
       if((item=make_item_example(argv[iarg++])) == NULL)
         goto ERROR_;
       prev_tuple = tuple;
       tuple = SPR_DO(Tuple,ctor_add,tuple,item);
       SPR_DO(Tuple,unlock,prev_tuple);
       SPR_DO(Item,unlock,item);
       if(tuple == NULL)
         goto ERROR_;
       item0 = SPR_CAST(Item,Tuple,tuple);
      }
    }
  }
 if(item1 == NULL)
  {int rv;
   do
    {Item *item = SPR_DO(Item,clone,item0);
     if((rv=SPR_DO(Item,read,item,stdin)) == 1)
       SPR_DO(Queue,push,queue,item);
     SPR_DO(Item,unlock,item);
    } while(rv == 1);
   if(rv < -1)
     goto ERROR_;
  }
 else
  {int rv;
   Hash *htbl = op;
   do
    {Item *ndx = SPR_DO(Item,clone,item1);
     Item *val = SPR_DO(Item,clone,item0);
     if((rv=SPR_DO(Item,read,ndx,stdin)) == 1)
      {if(SPR_DO(Item,read,val,stdin) == 1)
         SPR_DO(Hash,cadd,htbl,ndx,val);
       else
         rv = -2;
      }
     SPR_DO(Item,unlock,ndx);
     SPR_DO(Item,unlock,val);
    } while(rv == 1);
   if(rv < -1)
     goto ERROR_;
  }
 if(!feof(stdin))
   goto ERROR_;
 if(item1 == NULL)
  {while(!SPR_DO(Queue,empty,queue))
    {Item *item = SPR_DO(Queue,pop,queue);
     SPR_DO(Item,write,item,stdout);
     SPR_DO(Item,unlock,item);
     fputc('\n',stdout);
    }
  }
 else
  {Hash *htbl = op;
   Iterator *iter;
   for(iter=SPR_DO(Hash,iterator,htbl);iter!=NULL;iter=SPR_DO(Iterator,next,iter))
    {const Item *ndx = SPR_DO(Iterator,item,iter);
     SPR_DO(Item,write,ndx,stdout);
     SPR_DO(Item,write,SPR_DO(Hash,get,htbl,ndx),stdout);
     fputc('\n',stdout);
    }
  }
 rv = 0;
ERROR_:
 if(rv)
   fprintf(stderr,"failed to process the data -- %s\n",strerror(errno));
 if(op != NULL)             /* you can only do this if you are sure that all objects inherit from SprObject */
   SPR_DO(SprObject,dtor,(SprObject*)op);
 if(item0 != NULL)
   SPR_DO(Item,dtor,item0);
 if(item1 != NULL)
   SPR_DO(Item,dtor,item1);
 return(rv);
}