/*
** Copyright (C) 2001-2011 by Carnegie Mellon University.
**
** @OPENSOURCE_HEADER_START@
**
** Use of the SILK system and related source code is subject to the terms
** of the following licenses:
**
** GNU Public License (GPL) Rights pursuant to Version 2, June 1991
** Government Purpose License Rights (GPLR) pursuant to DFARS 252.227.7013
**
** NO WARRANTY
**
** ANY INFORMATION, MATERIALS, SERVICES, INTELLECTUAL PROPERTY OR OTHER
** PROPERTY OR RIGHTS GRANTED OR PROVIDED BY CARNEGIE MELLON UNIVERSITY
** PURSUANT TO THIS LICENSE (HEREINAFTER THE "DELIVERABLES") ARE ON AN
** "AS-IS" BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY
** KIND, EITHER EXPRESS OR IMPLIED AS TO ANY MATTER INCLUDING, BUT NOT
** LIMITED TO, WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE,
** MERCHANTABILITY, INFORMATIONAL CONTENT, NONINFRINGEMENT, OR ERROR-FREE
** OPERATION. CARNEGIE MELLON UNIVERSITY SHALL NOT BE LIABLE FOR INDIRECT,
** SPECIAL OR CONSEQUENTIAL DAMAGES, SUCH AS LOSS OF PROFITS OR INABILITY
** TO USE SAID INTELLECTUAL PROPERTY, UNDER THIS LICENSE, REGARDLESS OF
** WHETHER SUCH PARTY WAS AWARE OF THE POSSIBILITY OF SUCH DAMAGES.
** LICENSEE AGREES THAT IT WILL NOT MAKE ANY WARRANTY ON BEHALF OF
** CARNEGIE MELLON UNIVERSITY, EXPRESS OR IMPLIED, TO ANY PERSON
** CONCERNING THE APPLICATION OF OR THE RESULTS TO BE OBTAINED WITH THE
** DELIVERABLES UNDER THIS LICENSE.
**
** Licensee hereby agrees to defend, indemnify, and hold harmless Carnegie
** Mellon University, its trustees, officers, employees, and agents from
** all claims or demands made against them (and any related losses,
** expenses, or attorney's fees) arising out of, or relating to Licensee's
** and/or its sub licensees' negligent use or willful misuse of or
** negligent conduct or willful misconduct regarding the Software,
** facilities, or other rights or assistance granted by Carnegie Mellon
** University under this License, including, but not limited to, any
** claims of product liability, personal injury, death, damage to
** property, or violation of any laws or regulations.
**
** Carnegie Mellon University Software Engineering Institute authored
** documents are sponsored by the U.S. Department of Defense under
** Contract FA8721-05-C-0003. Carnegie Mellon University retains
** copyrights in all material produced under this contract. The U.S.
** Government retains a non-exclusive, royalty-free license to publish or
** reproduce these documents, or allow others to do so, for U.S.
** Government purposes only pursuant to the copyright license under the
** contract clause at 252.227.7013.
**
** @OPENSOURCE_HEADER_END@
*/
#ifndef _SKHEAP_H
#define _SKHEAP_H

#include <silk/silk.h>

RCSIDENTVAR(rcsID_SKHEAP_H, "$SiLK: skheap.h 16752 2011-02-24 17:41:51Z mthomas $");


#define HEAP_OK 0

/* Return value when attempting to add node to a full heap */
#define HEAP_ERR_FULL 3

/* Return value when attempting to get or to delete the top element of
 * an empty heap */
#define HEAP_ERR_EMPTY 4

/* Return value when heap iterator reaches end-of-data */
#define HEAP_NO_MORE_ENTRIES 5


/* The Heap object */
typedef struct skheap_st skheap_t;

/* The nodes stored in the heap data structure */
typedef void* skheapnode_t;

/* Used to iterate over the entries in the heap */
typedef struct skheapiterator_st skheapiterator_t;


/*
 *    The signature of the comparator function that the caller must
 *    pass to the skHeapCreate() function.  The function takes two
 *    skheapnode_t's, node1 and node2, and returns:
 *     -- an integer value > 0 if node1 should be a closer to the root
 *        of the heap than node2
 *     -- an integer value < 0 if node2 should be a closer to the root
 *        of the heap than node1
 *    For example: a heap with the lowest value at the root could return
 *    1 if node1<node2
 */
typedef int (*skheapcmpfn_t)(
    const skheapnode_t  node1,
    const skheapnode_t  node2);

typedef int (*skheapcmp2fn_t)(
    const skheapnode_t  node1,
    const skheapnode_t  node2,
    void               *cmp_data);


/*
 *    Creates a heap of capable of holding 'max_entries'
 *    skheapnode_t's each of size 'entry_size.  The 'cmpfun'
 *    determines how the nodes are ordered in the heap.
 *
 *    If 'data' is non-NULL, it must be a block of memory of size
 *    max_entries*entry_size bytes.  The heap will use it to store the
 *    entries.  If 'data' is NULL, the heap will manage the memory for
 *    entries itself.
 */
skheap_t *skHeapCreate(
    skheapcmpfn_t       cmpfun,
    uint32_t            max_entries,
    uint32_t            entry_size,
    skheapnode_t       *data);

skheap_t *skHeapCreate2(
    skheapcmp2fn_t      cmpfun,
    uint32_t            max_entries,
    uint32_t            entry_size,
    skheapnode_t       *data,
    void               *cmp_data);


/*
 *    Set the number of entries in the heap to 0, effectively emptying
 *    the heap.  Does not modify the bytes in the data array.
 */
void skHeapEmpty(skheap_t *heap);


/*
 *    Destroy an existing heap.  Does not modify the data array when
 *    using caller-supplied data---that is, when a non-NULL 'data'
 *    value was passed to skHeapCreate().
 */
void skHeapFree(skheap_t *heap);


/*
 *    Return the maximum number of entries the heap can accommodate.
 */
uint32_t skHeapGetMaxSize(const skheap_t *heap);


/*
 *    Return the number of entries currently in the heap.
 */
uint32_t skHeapGetNumberEntries(const skheap_t *heap);


/*
 *    Return the size of each element that is stored in the heap.
 */
uint32_t skHeapGetEntrySize(const skheap_t *heap);


/*
 *    Add the entry at 'new_node' to the heap.  Return HEAP_ERR_FULL
 *    if the heap is full.  This function will read 'entry_size' bytes
 *    of data from the location pointed by 'new_node'.
 */
int skHeapInsert(skheap_t *heap, const skheapnode_t new_node);


/*
 *    Set the value of 'top_node' to point at the entry at the top of
 *    the heap.  Does not modify the heap, and the caller must not
 *    modify the data that 'top_node' is pointing to.  Return
 *    HEAP_ERR_EMPTY if the heap is empty.
 */
int skHeapPeekTop(const skheap_t *heap, skheapnode_t *top_node);


/*
 *    Remove the entry at the top of the heap.  If 'top_node' is
 *    non-NULL, the removed entry is copied there---that is,
 *    'entry_size' bytes of data will be written to the location
 *    pointed by 'top_node'.  Return HEAP_ERR_EMPTY if the heap is
 *    empty.
 */
int skHeapExtractTop(skheap_t *heap, skheapnode_t top_node);


/*
 *    Remove the entry at the top of the heap and insert a new entry
 *    into the heap.  If 'top_node' is non-NULL, the removed entry is
 *    copied there---that is, 'entry_size' bytes of data will be
 *    written to the location pointed by 'top_node'.  This function
 *    will read 'entry_size' bytes of data from the location pointed
 *    by 'new_node'.  Return HEAP_ERR_EMPTY if the heap is empty and
 *    do NOT add 'new_node' to the heap.
 */
int skHeapReplaceTop(
    skheap_t           *heap,
    const skheapnode_t  new_node,
    skheapnode_t        top_node);


/*
 *    Sort the entries in the heap.  (Note that a sorted heap is still
 *    a heap).  This can be used to order the entries before using a
 *    skheapiterator_t, or for user-managed heap storage.
 */
int skHeapSortEntries(skheap_t *heap);


/*
 *    Return a skheapiterator_t that can be used to iterate over the
 *    nodes in the heap.  Return NULL if the iterator cannot be
 *    created.  If direction is non-negative, the iterator starts at
 *    the root and works toward the leaves; otherwise, the iterator
 *    works from the leaves to the root.  The iterator visits all
 *    nodes on one level before moving to the next.  By calling
 *    skHeapSortEntries() before creating the iterator, the nodes will
 *    be traversed in the order determined by the cmpfun.
 */
skheapiterator_t *skHeapIteratorCreate(const skheap_t *heap, int direction);


/*
 *    Free the memory associated with the iterator
 */
void skHeapIteratorFree(skheapiterator_t *iter);


/*
 *    Set 'heap_node' to the memory location of the next entry.
 *    Return HEAP_OK if 'heap_node' was set to the next node; return
 *    HEAP_NO_MORE_ENTRIES if all nodes have been visited.
 */
int skHeapIteratorNext(skheapiterator_t *iter, skheapnode_t *heap_node);

#endif /* _SKHEAP_H */

/*
** Local Variables:
** mode:c
** indent-tabs-mode:nil
** c-basic-offset:4
** End:
*/
