/*
Copyright (c) 2000-2010, Dirk Krause
All rights reserved.

Redistribution and use in source and binary forms,
with or without modification, are permitted provided
that the following conditions are met:

* Redistributions of source code must retain the above
  copyright notice, this list of conditions and the
  following disclaimer.
* Redistributions in binary form must reproduce the above 
  opyright notice, this list of conditions and the following
  disclaimer in the documentation and/or other materials
  provided with the distribution.
* Neither the name of the Dirk Krause nor the names of
  contributors may be used to endorse or promote
  products derived from this software without specific
  prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED.
IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
DAMAGE.
*/

/**	@file dksto.h
	Unsorted and sorted containers.
	This module contains functions to store pointers in sorted
	and unsorted containers, to search for objects in containers
	and to iterate through containers.

	To create containers for sorted storage set a comparison
	or evaluation function for a container immediately after
	creating the container and before inserting the first
	element.

	The file tutorial/stotut.c contains an example for sorted storage.
*/

#ifndef DK_STO_INCLUDED
#define DK_STO_INCLUDED 1

#include <dk.h>
#include <dktypes.h>

#if defined(EXTERN)
#undef EXTERN
#endif
#ifndef DK_STO_C
#if !DK_HAVE_PROTOTYPES
#define EXTERN extern
#else
#define EXTERN /* nix */
#endif
#else
#define EXTERN /* nix */
#endif

#if defined(__cplusplus)
extern "C" {
#endif



/**	Create a new containter (dk_storage_t).
	For sorted containers we need to store a critical path
	during insert and remove operations. The \a c parameter
	controls the size of the critical path (64, 128, 512, 1024 or 1536)
	which affects the number of elements which can be stored in the
	container.
	The container is created in dynamically allocated memory, you
	must release the memory by calling dksto_close() when the
	container is no longer used.
	To switch the container to sorted storage call one of the
	dksto_set_eval_...() or dksto_set_comp() functions before
	inserting the first element.
	@param	c	Key number to specify the critical path length.
			The recommended value is DK_STO_SIZE_HUGE.
	@return	Pointer to the new container on success, NULL on error.
*/
EXTERN dk_storage_t *
dksto_open DK_PR((int c));



/**	Set char type evaluation function and criteria for container.
	@param	c	Pointer to container.
	@param	f	Pointer to evaluation function.
	@param	s	Criteria passed to evaluation function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_eval_c DK_PR((dk_storage_t *c, dk_fct_eval_c_t *f, int s));



/**	Set unsigned char type evaluation function and criteria for container.
	@param	c	Pointer to container.
	@param	f	Pointer to evaluation function.
	@param	s	Criteria passed to evaluation function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_eval_uc DK_PR((dk_storage_t *c, dk_fct_eval_uc_t *f, int s));



/**	Set short type evaluation function and criteria for container.
	@param	c	Pointer to container.
	@param	f	Pointer to evaluation function.
	@param	s	Criteria passed to evaluation function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_eval_s DK_PR((dk_storage_t *c, dk_fct_eval_s_t *f, int s));



/**	Set unsigned short type evaluation function and criteria for container.
	@param	c	Pointer to container.
	@param	f	Pointer to evaluation function.
	@param	s	Criteria passed to evaluation function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_eval_us DK_PR((dk_storage_t *c, dk_fct_eval_us_t *f, int s));



/**	Set int type evaluation function and criteria for container.
	@param	c	Pointer to container.
	@param	f	Pointer to evaluation function.
	@param	s	Criteria passed to evaluation function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_eval_i DK_PR((dk_storage_t *c, dk_fct_eval_i_t *f, int s));



/**	Set unsigned int type evaluation function and criteria for container.
	@param	c	Pointer to container.
	@param	f	Pointer to evaluation function.
	@param	s	Criteria passed to evaluation function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_eval_ui DK_PR((dk_storage_t *c, dk_fct_eval_ui_t *f, int s));



/**	Set long type evaluation function and criteria for container.
	@param	c	Pointer to container.
	@param	f	Pointer to evaluation function.
	@param	s	Criteria passed to evaluation function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_eval_l DK_PR((dk_storage_t *c, dk_fct_eval_l_t *f, int s));



/**	Set unsigned long type evaluation function and criteria for container.
	@param	c	Pointer to container.
	@param	f	Pointer to evaluation function.
	@param	s	Criteria passed to evaluation function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_eval_ul DK_PR((dk_storage_t *c, dk_fct_eval_ul_t *f, int s));



/**	Set float type evaluation function and criteria for container.
	@param	c	Pointer to container.
	@param	f	Pointer to evaluation function.
	@param	s	Criteria passed to evaluation function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_eval_f DK_PR((dk_storage_t *c, dk_fct_eval_f_t *f, int s));



/**	Set double type evaluation function and criteria for container.
	@param	c	Pointer to container.
	@param	f	Pointer to evaluation function.
	@param	s	Criteria passed to evaluation function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_eval_d DK_PR((dk_storage_t *c, dk_fct_eval_d_t *f, int s));



/**	Set object comparison function and search criteria for
	container.
	@param	c	Pointer to container.
	@param	f	Pointer to comparison funtion.
	@param	s	Criteria passed to comparison function.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_set_comp DK_PR((dk_storage_t *c, dk_fct_comp_t *f, int s));



/**	Close a containter obtained from dksto_open().
	@param	c	Pointer to the container.
*/
EXTERN void
dksto_close DK_PR((dk_storage_t *c));



/**	Remove all object pointers from container.
	@param	c	Pointer to the container.
*/
EXTERN void
dksto_remove_all DK_PR((dk_storage_t *c));



/**	Remove one object pointer from the container.
	@param	c	Pointer to the container.
	@param	o	Object pointer to remove.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_remove DK_PR((dk_storage_t *c, void *o));



/**	Add object pointer to container.
	@param	c	Pointer to the container.
	@param	o	Object pointer to add.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_add DK_PR((dk_storage_t *c, void *o));



/**	Create iterator for container. The iterator is created in
	dynamically allocated memory. You must destroy it/release the
	memory using dksto_it_close() if the iterator is not longer needed
	and before calling dksto_close() on the container.
	@param	c	Pointer to the container.
	@return	Pointer to the new iterator on success, nULL on error.
*/
EXTERN dk_storage_iterator_t *
dksto_it_open DK_PR((dk_storage_t *c));



/**	Close iterator and release memory for an iterator obtained
	from dksto_it_open().
	@param	i	Pointer to the iterator to close.
*/
EXTERN void
dksto_it_close DK_PR((dk_storage_iterator_t *i));



/**	Reset iterator. The next call of dksto_it_next() will return
	pointer to the first object (if any).
	@param	i	Pointer to the iterator.
*/
EXTERN void
dksto_it_reset DK_PR((dk_storage_iterator_t *i));



/**	Retrieve next pointer for iterator.
	@param	i	Pointer to the iterator.
*/
EXTERN void *
dksto_it_next DK_PR((dk_storage_iterator_t *i));



/**	Find the object \a o.
	The iterator is set to object \a o, the following calls
	to dksto_it_next() will deliver the objects after \a o.
	@param	i	Pointer to the iterator.
	@param	o	Object pointer.
	@return	Pointer to \a o or NULL if the object was not found.
*/
EXTERN void *
dksto_it_find_exact DK_PR((dk_storage_iterator_t *i, void *o));



/**	Find the first object evaluated equally to \a o.
	The function searches for the first object which is evaluated
	equally to \a o using the evaluation/comparison functions set
	for the container.
	The folling calls to dksto_it_next() will deliver the objects
	after the object found.
	@param	i	Pointer to the iterator.
	@param	o	Object pointer.
	@param	s	Search/comparison/evaluation criteria.
	@return	Pointer to first object evaluated equally to \a o or NULL
	if no such object is found.
*/
EXTERN void *
dksto_it_find_like DK_PR((dk_storage_iterator_t *i, void *o, int s));



/**	Allow/deny the use of AVL-trees for sorted storages (obsoleted).
	By default this feature is turned on.
	This function can only be used if there is no pointer stored in
	the container.
	@param	c	Pointer to container.
	@param	f	Flag to allow the use of AVL-trees.
	@return	Flag to indicate success.
*/
EXTERN int
dksto_use_trees DK_PR((dk_storage_t *c, int f));



/**	Find object placed at the root of the containers tree.
	@param	c	Pointer to the container.
	@return	Object pointer placed at the containers trees root or NULL
	if there are no elements in the container.
*/
EXTERN void *
dksto_find_root DK_PR((dk_storage_t *c));



/**	Find object placed as parent of the iterators current object
	in the containers tree.
	@param	i	Pointer to iterator.
	@return	Object pointer or NULL.
*/
EXTERN void *
dksto_it_find_parent DK_PR((dk_storage_iterator_t *i));



/**	Find object placed as left child of the iterators current
	object in the containers tree.
	@param	i	Pointer to iterator.
	@return	Object pointer or NULL.
*/
EXTERN void *
dksto_it_find_left DK_PR((dk_storage_iterator_t *i));



/**	Find object placed as right child of the iterators current
	object in the containers tree.
	@param	i	Pointer to iterator.
	@return	Object pointer or NULL.
*/
EXTERN void *
dksto_it_find_right DK_PR((dk_storage_iterator_t *i));



/**	Find object placed at the root of the iterators container.
	@param	i	Pointer to the iterator.
	@return	Pointer to object placed at the root of the
	iterators containers tree or NULL.
*/
EXTERN void *
dksto_it_find_root DK_PR((dk_storage_iterator_t *i));



#if defined(__cplusplus)
}
#endif



/** Container size (number of elements): Maximum - Recommended */
#define DK_STO_SIZE_HUGE   0

/** Container size (number of elements): Large, < 1.17987*10^214 */
#define DK_STO_SIZE_LARGE  1

/** Container size (number of elements): Medium, < 1.17534*10^107 */
#define DK_STO_SIZE_MEDIUM 2

/** Container size (number of elements): Small, < 6.59035*10^26 */
#define DK_STO_SIZE_SMALL  3

/** Container size (number of elements): Smallest, < 2.77779*10^13 */
#define DK_STO_SIZE_TINY   4

#endif

