"Example using C++ style multiple inheritance"

/*************************************************************
 *  __  _   _   _   _                                        *
 * (_  |_) |_) |_| |_| |_/  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 <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <errno.h>

spr_public_hi_doc
/*
@brief
Some example code to illustate the use of classes in the SPRAAK-toolkit.
@details
Implementation of of small subset of python's functionality using the
class-base framework from the SPRAAK-toolkit.
    @f$\int_{-\infty}^{\infty} x^{\frac{1}{4}} + e^y + \alpha + \sqrt{2} \times 1/\sqrt{2\pi} x_{\alpha}^{\omega}@f$
@author
    Kris Demuynck
@date
    11/08/2007
*/


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

/*------------------------------------------------------------------------------*/
spr_cmdoc spr_public_lo_type
typedef struct
 {SprObject interface_;     /* In C++, every class with virtual functions needs a 'vtbl' pointer.\\
                   Note: avoid the use of 'interface', since Windows (more specific winsock.h) has problems with it. */
  unsigned int ref_cnt;     /* Count how many parties reference this object. */
 } Item;

spr_public_hi_class
SPR_CLASS(Item : SprObject
 {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.
Next to the 'interface' part, there is 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_Item
#include <spraak_classdef/taipan_cpp.class.h>


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

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

spr_cmdoc spr_public_lo_afunc
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_afunc
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_afunc
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_afunc
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,
this in contrast to standard C-functions where the 'destination' is typically
the first argument.
*/
;

spr_cmdoc spr_public_lo_afunc
Item *item_clone(
  const Item *item)     /* Item to clone. */
/*
Make an exact duplicate of the item (shallow copy).
*/
;

spr_cmdoc spr_public_lo_afunc
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_cpp.class.h>


/*------------------------------------------------------------------------------*/
spr_cmdoc spr_public_lo_type
typedef struct
 {Item item;            /* Implement the Item-interface. */
  long value;           /* The actual integer value. */
 } IntItem;

spr_public_hi_class
SPR_CLASS(IntItem : Item
 {spr_public static ctor()  = int_item_ctor;    /* Note: 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_cpp.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_cpp.class.h>


/*------------------------------------------------------------------------------*/
spr_cmdoc spr_public_lo_type
typedef struct
 {Item   item;          /* Implement the Item-interface. */
  double value;         /* The actual floating point value. */
 } FltItem;

spr_public_hi_class
SPR_CLASS(FltItem : Item
 {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 a floating-point item.
*/
#define SPR_CLASS_IMPORT_FltItem
#include <spraak_classdef/taipan_cpp.class.h>


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

spr_cmdoc spr_public_lo_afunc
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_cpp.class.h>


/*------------------------------------------------------------------------------*/
spr_cmdoc spr_public_lo_type
typedef struct
 {Item item;            /* Implement the Item-interface. */
  char *value;          /* The actual string value (a standard '\0' terminated string). */
 } StrItem;

spr_public_hi_class
SPR_CLASS(StrItem : Item
 {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_cpp.class.h>


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

spr_cmdoc spr_public_lo_afunc
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_cpp.class.h>


/*------------------------------------------------------------------------------*/
spr_cmdoc spr_public_lo_type
typedef struct
 {Item 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 : Item
 {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 an ordered, non modifiable collection of
things.
*/
#define SPR_CLASS_IMPORT_Tuple
#include <spraak_classdef/taipan_cpp.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_cpp.class.h>


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

/*------------------------------------------------------------------------------*/
spr_cmdoc spr_public_lo_type
typedef struct
 {SprObject interface_;
 } Iterable;

spr_cmdoc spr_public_lo_type
typedef struct
 {Iterable iterable;        /* An iterator is iterable as well, so we inherit from 'Iterable'. */
 } Iterator;

spr_public_hi_class
SPR_CLASSr(Iterable : SprObject
 {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_cpp.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 of the
iterable object <obj> in a deterministic order.
*/
;


#define SPR_CLASS_DEFINE_Iterable
#include <spraak_classdef/taipan_cpp.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_cpp.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 times method
Iterator::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 times
method Iterator::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_cpp.class.h>


/*------------------------------------------------------------------------------*/
spr_cmdoc spr_public_lo_type
typedef struct
 {SprObject interface_;
 } Queue;

spr_public_hi_class
SPR_CLASSr(Queue : SprObject
 {spr_public push[]()   = queue_push;
  spr_public pop[]()    = queue_pop;
  spr_public toq[]()    = queue_toq;
  spr_public empty[]()  = queue_empty;
 } )
/*
A Queue allows pushing and popping items and testing if the queue is empty.
*/
#define SPR_CLASS_IMPORT_Queue
#include <spraak_classdef/taipan_cpp.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_cpp.class.h>


/*------------------------------------------------------------------------------*/
spr_cmdoc spr_public_lo_type
typedef struct
 {Iterable iterable;        /* A container is iterable, so we inherit from Iterable. */
 } 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_cpp.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, 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_cpp.class.h>


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


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

spr_cmdoc spr_public_lo_type
typedef struct
 {spr_private Iterator iterator;        /* Let's hide the internals. */
  spr_private StackEl  *stackel;
 } StackIterator;

spr_public_hi_class
SPR_CLASS(StackIterator : 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_cpp.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_cpp.class.h>


spr_cmdoc spr_public_lo_type
typedef struct
 {Queue    queue;           /* A stack is queue. */
  Iterable iterable;            /* A stack is iterable. */
  StackEl  *tos;            /* Top of the stack. */
 } Stack;

spr_public_hi_class
SPR_CLASS(Stack : 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_cpp.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_cpp.class.h>


/*------------------------------------------------------------------------------*/
spr_cmdoc spr_public_lo_type
typedef struct
 {Queue        queue;           /* Implements the Queue interface. */
  Item         **heap;          /* The actual heap. */
  unsigned int size;            /* The maximum size of the heap. */
  unsigned int fill;            /* Current number of elements in the heap. */
 } HeapMin;

spr_public_hi_class
SPR_CLASS(HeapMin : 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.\\
@remark pushing all elements to such a queue and then popping them again
results in the heap-sort sorting algorithm.
*/
#define SPR_CLASS_IMPORT_HeapMin
#include <spraak_classdef/taipan_cpp.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_cpp.class.h>


/*------------------------------------------------------------------------------*/
spr_nodoc spr_public_lo_type
typedef struct t_hash_el
 {const Item *ndx;          /* The item index. */
  Item *value;              /* The value. */
  struct t_hash_el *next;       /* Next element in case of collisions. */
 } HashEl;

spr_cmdoc spr_public_lo_type
typedef struct
 {Container    container;       /* Implements the Container interface. */
  Queue        queue;           /* Implements the Queue interface. */
  spr_private HashEl       **htbl;  /* The actual hash table. */
  spr_private HashEl       *list;   /* The hash elements (one large array for efficiency reasons). */
  spr_private HashEl       *free_list;  /* The unused hash elements from the above list. */
  spr_private const HashEl *toq;    /* Top of the queue (element with the lowest position in the <list> array). */
  spr_private StrItem      *none;   /* An empty object, used when pushing items since then there is no value. */
  spr_private unsigned int size;    /* The maximum size of the hash table. */
  spr_private unsigned int fill;    /* Current number of elements in the hash table. */
  spr_private unsigned int max_size;    /* Max. used elements (is also the max. index in the <list> array that was used). */
 } Hash;

spr_cmdoc spr_public_lo_type
typedef struct
 {Iterator iterator;            /* Implements the Iterator interface. */
  spr_private const HashEl *ptr;    /* The pointer to the next element. */
  spr_private unsigned int rem_cnt; /* Remaining number of possible items. */
  spr_private const HashEl *list;   /* Reference to the original list; used for checking. */
  spr_private unsigned int size;    /* Copy of the size of the hash table; used for checking. */
  spr_private const Hash *hash;     /* Reference to the original hash table; used for checking. */
 } HashIterator;

spr_public_hi_class
SPR_CLASS(Hash : 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 hash table with keys & values.
When used as a queue, the values will be some internal 'none' item.
*/
#define SPR_CLASS_IMPORT_Hash
#include <spraak_classdef/taipan_cpp.class.h>

spr_public_hi_class
SPR_CLASS(HashIterator : Iterator
 {/* implement the Iterator interface */
  spr_public item[]()       := hash_iterator_item;
  spr_public next[]()       := hash_iterator_next;
  spr_public iterator[]()   := hash_iterator_iterator;
 } )
/*
The iterator for the hash table.
@remark since Hash does not implement Item, we cannot lock the hash table, so
it is up to the user of this class to assure that the hash table is not
destroyed while there is still an iterator!
*/
#define SPR_CLASS_IMPORT_HashIterator
#include <spraak_classdef/taipan_cpp.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);
}

spr_private_func
Hash *hash_resize(
  Hash         *hash,
  unsigned int size)
/*
Resize the hash table.
*/
{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 hash table.
*/
{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::cadd(). */
{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::remove(). */
{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_cpp.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_cpp.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: taipan_cpp <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);
}