/***********************************************************************
Filename   : rvpqueue.h
Description: rvpqueue header file
************************************************************************
      Copyright (c) 2001,2002 RADVISION Inc. and RADVISION Ltd.
************************************************************************
NOTICE:
This document contains information that is confidential and proprietary
to RADVISION Inc. and RADVISION Ltd.. No part of this document may be
reproduced in any form whatsoever without written prior approval by
RADVISION Inc. or RADVISION Ltd..

RADVISION Inc. and RADVISION Ltd. reserve the right to revise this
publication and make changes without obligation to notify any person of
such revisions or changes.
***********************************************************************/
/*$
{package:
	{name: PQueue}
	{superpackage: CUtils}
	{include: rvpqueue.h}
	{description:	
		{p: This module provides functions for creating and manipulating
			binary heap priority queues. Memory for the pool will be allocated
			and freed via callback functions.}
		{p: There are three types of pools:}
		{bulletlist:
			{item:  FIXED: This creates a fixed priority queue. The size
					may only be changed with the RvPQueueChangeSize function.}
			{item:  EXPANDING: This creates a priority queue which expands as
					needed. When the priority queue runs out of space is will
					allocate a new space double the old size and release the old
					sace. The size may also be changed with the RvPQueueChangeSize
					function.}
			{item:  DYNAMIC: This creates a priority queue which expands exactly
					like an EXPANDING priority queue but also has the ability to
					reduce its size. When only 25% of the priority queue is in
					use, a new space 50% the old size will be allocated and the
					old space will be released. The size may also be changed with
					the RvPQueueChangeSize function. The size will never be reduced
					below the starting size.}
		}
	}
	{notes:
		{note:  This module does no locking at all. The locking of the
				priority queue is the responsibility of the user.}
	}
}
$*/
#ifndef RV_PQUEUE_H
#define RV_PQUEUE_H

#include "rvtypes.h"

/*$
{type:
	{name: RvPQueueFuncs}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:	
		{p: A structure containing callback information for a priority queue. This structure
			must be completely filled out before passing it to RvPQueueConstruct.}
		{p: The memalloc and memfree callbacks will be used to allocate and release
			memory used for the priority queue.}
		{p: The itemcmp callback is the user defined operation that determines how the
			priority queue sorts the items in the queue.}
		{p: The newindex callback is a call that is made whenever an item is moved in the
			priority queue. This allows the item to save its current position in case
			it needs to remove itself from the priority queue.}
	}
	{attributes scope="public":
		{attribute: {t: void *()(RvSize_t size, void *data)} {n: memalloc} {d: Callback to allocate size bytes of memory. Return pointer to memory or NULL for failure.}}
		{attribute: {t: void  ()(void *ptr, void *data} {n: memfree} {d: Callback to free the memory at ptr.}}
		{attribute: {t: RvBool ()(void *ptr1, void *ptr2)} {n: itemcmp} {d: Callback to compare two items. Return RV_TRUE if ptr1 is higher priority, else RV_FALSE.}}
		{attribute: {t: void  ()(void *item, RvSize_t index)} {n: newindex} {d: Callback to notify item of new index value.}}
		{attribute: {t: void *} {n: memallocdata} {d: User data parameter passed into memalloc.}}
		{attribute: {t: void *} {n: memfreedata} {d: User data parameter passed into memfree.}}
	}
}
$*/
typedef struct {
	void  *(*memalloc)(RvSize_t size, void *data);  /* Allocate memory for heap. Return pointer to memory, NULL = failed. */
	void   (*memfree)(void *ptr, void *data);       /* Free memory allocated by memalloc. */
	RvBool (*itemcmp)(void *ptr1, void *ptr2);      /* Compare 2 items, return RV_TRUE if ptr1 higher priority, else RV_FALSE. */
	void   (*newindex)(void *item, RvSize_t index); /* Store new index for item, use this for removing items. */
	void *memallocdata;    /* User data parameter passed into memalloc */
	void *memfreedata;     /* User data parameter passed into memfree */
} RvPQueueFuncs;

/*$
{type:
	{name: RvPQueue}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:	
		{p: An priority queue object.}
	}
}
$*/
typedef struct {
	RvSize_t startsize;      /* Starting size of queue (heap), also is minimum size */
	RvSize_t cursize;        /* Current size of queue (heap) */
	RvInt qtype;             /* type of queue: see RV_PQUEUE_TYPE_ */
	RvPQueueFuncs callbacks; /* User defined function callbacks */
	RvSize_t numitems;       /* Number or items currently in the heap */
	void **heap;             /* Actual heap array (which will be allocated) */
} RvPQueue;

/* Priority Queue Types */
/*   FIXED: heap stays fixed at starting size */
/*   EXPANDING: heap size is increased by a factor of 2 and reallocated when heap is full */
/*   DYNAMIC: heap size is reduced by a factor of 2 (min of startsize) when heap only 25% full */
#define RV_PQUEUE_TYPE_FIXED RvIntConst(0)
#define RV_PQUEUE_TYPE_EXPANDING RvIntConst(1)
#define RV_PQUEUE_TYPE_DYNAMIC RvIntConst(2)

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

/* Prototypes: See documentation blocks below for details. */
RvPQueue *RvPQueueConstruct(RvPQueue *pqueue, RvInt qtype, RvSize_t startsize, RvPQueueFuncs *callbacks);
void RvPQueueDestruct(RvPQueue *pqueue);
void *RvPQueuePut(RvPQueue *pqueue, void *newitem);
void *RvPQueueGet(RvPQueue *pqueue);
void *RvPQueuePeek(RvPQueue *pqueue);
RvSize_t RvPQueueNumItems(RvPQueue *pqueue);
RvSize_t RvPQueueSize(RvPQueue *pqueue);
RvSize_t RvPQueueChangeSize(RvPQueue *pqueue, RvSize_t newsize);
void RvPQueueClear(RvPQueue *pqueue);
void *RvPQueueRemove(RvPQueue *pqueue, RvSize_t itemindex);

#if defined(RV_TEST_CODE)
void RvPQueueTest(void);
#endif /* RV_TEST_CODE */

#if defined(__cplusplus)
}
#endif

/* Function Docs */
/*$
{function:
	{name: RvPQueueConstruct}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:
		{p: Constructs a priority queue.}
	}
	{proto: RvPQueue *RvPQueueConstruct(RvPQueue *pqueue, RvInt qtype, RvSize_t startsize, RvPQueueFuncs *callbacks);}
	{params:
		{param: {n: pqueue} {d: Pointer to priority queue object to construct.}}
		{param: {n: qtype} {d: The type of priority queue: RV_PQUEUE_TYPE_FIXED, RV_PQUEUE_TYPE_EXPANDING, or RV_PQUEUE_TYPE_DYNAMIC.}}
		{param: {n: startsize} {d: Starting size of priority queue.}}
		{param: {n: callbacks} {d: Pointer to structure with callback information.}}
	}
	{returns: A pointer to the priority queue object or, if there is an error, NULL.}
	{notes:
		{note:  The callbacks structure will be copied so there is no need to maintain this
				structure after construction.}
		{note:  If startsize is less than 2 it will be set to 2, which is the minimum size.}
		{note:  DYNAMIC priority queues will never shrink below startsize.}
	}
}
$*/
/*$
{function:
	{name: RvPQueueDestruct}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:
		{p: Destructs a priority queue.}
	}
	{proto: void RvPQueueDestruct(RvPQueue *pqueue);}
	{params:
		{param: {n: pqueue} {d: Pointer to priority queue object to destruct.}}
	}
	{notes:
		{note:  Any items in the priority queue when it is destructed are considered removed.}
	}
}
$*/
/*$
{function:
	{name: RvPQueuePut}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:
		{p: Puts a new item into a priority queue.}
	}
	{proto: void *RvPQueuePut(RvPQueue *pqueue, void *newitem);}
	{params:
		{param: {n: pqueue} {d: Pointer to priority queue to add newitem into.}}
		{param: {n: newitem} {d: Pointer to the item to put into the queue.}}
	}
	{returns: A pointer to newitem or, if the item can not be added to the priority queue, NULL.}
}
$*/
/*$
{function:
	{name: RvPQueueGet}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:
		{p: Gets the highest priority item from a priority queue. The item is removed from the queue.}
	}
	{proto: void *RvPQueueGet(RvPQueue *pqueue);}
	{params:
		{param: {n: pqueue} {d: Pointer to priority queue to get item from.}}
	}
	{returns: A pointer to the highest priority item or NULL if the priority queue is empty.}
}
$*/
/*$
{function:
	{name: RvPQueuePeek}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:
		{p: Gets the highest priority item from a priority queue. Does not remove the item from the queue.}
	}
	{proto: void *RvPQueuePeek(RvPQueue *pqueue);}
	{params:
		{param: {n: pqueue} {d: Pointer to priority queue to get item from.}}
	}
	{returns: A pointer to the highest priority item or NULL if the priority queue is empty.}
}
$*/
/*$
{function:
	{name: RvPQueueNumItems}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:
		{p: Gets number of items currently in a priority queue.}
	}
	{proto: RvSize_t RvPQueueNumItems(RvPQueue *pqueue);}
	{params:
		{param: {n: pqueue} {d: Pointer to priority queue to get number of items of.}}
	}
	{returns: The number of items in the priority queue.}
}
$*/
/*$
{function:
	{name: RvPQueueSize}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:
		{p: Gets the size of a priority queue.}
	}
	{proto: RvSize_t RvPQueueSize(RvPQueue *pqueue);}
	{params:
		{param: {n: pqueue} {d: Pointer to priority queue to get size of.}}
	}
	{returns: The size of the priority queue.}
}
$*/
/*$
{function:
	{name: RvPQueueChangeSize}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:
		{p: Changes the size of a priority queue.}
	}
	{proto: RvSize_t RvPQueueChangeSize(RvPQueue *pqueue, RvSize_t newsize);}
	{params:
		{param: {n: pqueue} {d: Pointer to priority queue to change the size of.}}
		{param: {n: newsize} {d: New size of priority queue.}}
	}
	{returns:   The size of the priority queue. If the size could not be changed than the
				old size of the queue is returned.}
	{notes:
		{note:  The size can not be made smaller than the current number of items in the
				priority queue.}
		{note:  The size can not be set smaller than 2.}
		{note:  For DYNAMIC priority queues this value replaces the startsize as
				the minimum size of the priority queue.}
	}
}
$*/
/*$
{function:
	{name: RvPQueueClear}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:
		{p: Clears all items from a priority queue.}
	}
	{proto: void RvPQueueClear(RvPQueue *pqueue);}
	{params:
		{param: {n: pqueue} {d: Pointer to priority queue to clear.}}
	}
	{notes:
		{note:  For DYNAMIC priority queues, their size will shrink back to
				their minimum size, which is their starting size unless it was
				changed with a call to RvPQueueChangeSize.}
	}
}
$*/
/*$
{function:
	{name: RvPQueueRemove}
	{superpackage: PQueue}
	{include: rvpqueue.h}
	{description:
		{p: Removes an item from a priority queue. The item is specified by its
			index which it is given via the newindex callback. }
	}
	{proto: void *RvPQueueRemove(RvPQueue *pqueue, RvSize_t itemindex);}
	{params:
		{param: {n: pqueue} {d: Pointer to priority queue to remove item from.}}
		{param: {n: itemindex} {d: Index of the item to be removed.}}
	}
	{returns: A pointer to item that has been removed from the priority queue or NULL there is an error.}
}
$*/

#endif /* RV_PQUEUE_H */