/*
 DSPAM Peak Window-Value Heap Sorting Algorithm
 COPYRIGHT (C) 2002-2004 NETWORK DWEEBS CORPORATION

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

*/

#include <stdlib.h>
#include <math.h>
#include "heap.h"

/*
   heap_create(): Create a new heap-sort
   Allocates and initializes a new heap-sort
   Returns: pointer to new heap-sort, NULL on error

   Data Type            Var     Description
   ---------------------------------------------------------------------------
   int			size	Peak Window-Size

   Peak Window-Size: The number of elements used in your Bayesian combination;
     for example 15 for Paul Graham's Bayes, 27 for Brian Burton's.
*/

struct heap *
heap_create(int size)
{
  struct heap *h;

  h = calloc(1, sizeof(struct heap));
  h->size = size;
  return h;
}

/*
   heap_destroy(): destroy a heap sort
   Frees allocated memory for a heap and its elements
   Returns: 0 on success

   Data Type            Var     Description
   ---------------------------------------------------------------------------
   struct heap *        h       pointer to the heap sort to destroy
*/


int
heap_destroy(struct heap *h)
{
  struct heap_node *node, *next;

  if (h == NULL)
    return 0;

  node = h->root;
  while(node) {
    next = node->next;
    free(node);
    node = next;
  }
  free(h);
  return 0;
}

/*
   heap_node_create(): create a new element [private]
   Allocates and initializes a new heap element
   Returns: pointer to new heap element

   Data Type            Var     Description
   ---------------------------------------------------------------------------
   double               delta   p-value distance from neutral 0.5
   unsigned long long   key     64-bit numeric representation of token (crc64)

*/

struct heap_node *
heap_node_create (double delta, unsigned long long token)
{
  struct heap_node *node = malloc(sizeof(struct heap_node));

  if (node == NULL) return NULL;

  node->delta	= delta;
  node->key	= token;

  return node;
}

/*
   heap_insert(): present a new element to the sort
   If the presented element is greater than any in the heap, insert it
   If not, either discard it or grow the heap to accomodate (up to window-size)
   Returns: 0 on insertion, <0 on discard

   Data Type		Var	Description
   ---------------------------------------------------------------------------
   struct heap *	h	pointer to the heap sort
   double		delta	p-value distance from neutral 0.5
   unsigned long long	key	64-bit numeric representation of token (crc64)

*/

int
heap_insert (struct heap *h, double delta, unsigned long long key)
{
  struct heap_node *current = h->root, 
                    *insert = NULL, 
                    *node;

  /* Determine if and where we should insert this item */

  while(current) {
    if (delta >= current->delta) 
      insert = current;
    else 
      break;
    current = current->next;
  }

  /* Insert item, throw out new least significant item if necessary */

  if (insert) {
    node = heap_node_create(delta, key);
    node->next = insert->next;
    insert->next = node;
    h->items++;
    if (h->items > h->size) {
      node = h->root;
      h->root = node->next;
      free(node);
      h->items--;
    }

  /* Item is least significant; discard it or grow the heap */

  } else {

    /* Discard */
    if (h->items == h->size)
      return -1;

    /* Grow heap */
    node = heap_node_create(delta, key);
    node->next = h->root;
    h->root = node;
    h->items++;
  }

  return 0;
}