/* Copyright (c) 2013, Ben Noordhuis <info@bnoordhuis.nl>

 *

 * Permission to use, copy, modify, and/or distribute this software for any

 * purpose with or without fee is hereby granted, provided that the above

 * copyright notice and this permission notice appear in all copies.

 *

 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES

 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF

 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR

 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES

 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN

 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF

 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

 */

#ifndef UV_SRC_HEAP_H_

#define UV_SRC_HEAP_H_

#include <stddef.h>  /* NULL */

#if defined(__GNUC__)

# define HEAP_EXPORT(declaration) __attribute__((unused)) static declaration

#else

# define HEAP_EXPORT(declaration) static declaration

#endif

struct heap_node {

  struct heap_node* left;

  struct heap_node* right;

  struct heap_node* parent;

};

/* A binary min heap.  The usual properties hold: the root is the lowest

 * element in the set, the height of the tree is at most log2(nodes) and

 * it's always a complete binary tree.

 *

 * The heap function try hard to detect corrupted tree nodes at the cost

 * of a minor reduction in performance.  Compile with -DNDEBUG to disable.

 */

struct heap {

  struct heap_node* min;

  unsigned int nelts;

};

/* Return non-zero if a < b. */

typedef int (*heap_compare_fn)(const struct heap_node* a,

                               const struct heap_node* b);

/* Public functions. */

HEAP_EXPORT(void heap_init(struct heap* heap));

HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap));

HEAP_EXPORT(void heap_insert(struct heap* heap,

                             struct heap_node* newnode,

                             heap_compare_fn less_than));

HEAP_EXPORT(void heap_remove(struct heap* heap,

                             struct heap_node* node,

                             heap_compare_fn less_than));

HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than));

/* Implementation follows. */

HEAP_EXPORT(void heap_init(struct heap* heap)) {

  heap->min = NULL;

  heap->nelts = 0;

}

HEAP_EXPORT(struct heap_node* heap_min(const struct heap* heap)) {

  return heap->min;

}

/* Swap parent with child. Child moves closer to the root, parent moves away. */

static void heap_node_swap(struct heap* heap,

                           struct heap_node* parent,

                           struct heap_node* child) {

  struct heap_node* sibling;

  struct heap_node t;

  t = *parent;

  *parent = *child;

  *child = t;

  parent->parent = child;

  if (child->left == child) {

    child->left = parent;

    sibling = child->right;

  } else {

    child->right = parent;

    sibling = child->left;

  }

  if (sibling != NULL)

    sibling->parent = child;

  if (parent->left != NULL)

    parent->left->parent = parent;

  if (parent->right != NULL)

    parent->right->parent = parent;

  if (child->parent == NULL)

    heap->min = child;

  else if (child->parent->left == parent)

    child->parent->left = child;

  else

    child->parent->right = child;

}

HEAP_EXPORT(void heap_insert(struct heap* heap,

                             struct heap_node* newnode,

                             heap_compare_fn less_than)) {

  struct heap_node** parent;

  struct heap_node** child;

  unsigned int path;

  unsigned int n;

  unsigned int k;

  newnode->left = NULL;

  newnode->right = NULL;

  newnode->parent = NULL;

  /* Calculate the path from the root to the insertion point.  This is a min

   * heap so we always insert at the left-most free node of the bottom row.

   */

  path = 0;

  for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)

    path = (path << 1) | (n & 1);

  /* Now traverse the heap using the path we calculated in the previous step. */

  parent = child = &heap->min;

  while (k > 0) {

    parent = child;

    if (path & 1)

      child = &(*child)->right;

    else

      child = &(*child)->left;

    path >>= 1;

    k -= 1;

  }

  /* Insert the new node. */

  newnode->parent = *parent;

  *child = newnode;

  heap->nelts += 1;

  /* Walk up the tree and check at each node if the heap property holds.

   * It's a min heap so parent < child must be true.

   */

  while (newnode->parent != NULL && less_than(newnode, newnode->parent))

    heap_node_swap(heap, newnode->parent, newnode);

}

HEAP_EXPORT(void heap_remove(struct heap* heap,

                             struct heap_node* node,

                             heap_compare_fn less_than)) {

  struct heap_node* smallest;

  struct heap_node** max;

  struct heap_node* child;

  unsigned int path;

  unsigned int k;

  unsigned int n;

  if (heap->nelts == 0)

    return;

  /* Calculate the path from the min (the root) to the max, the left-most node

   * of the bottom row.

   */

  path = 0;

  for (k = 0, n = heap->nelts; n >= 2; k += 1, n /= 2)

    path = (path << 1) | (n & 1);

  /* Now traverse the heap using the path we calculated in the previous step. */

  max = &heap->min;

  while (k > 0) {

    if (path & 1)

      max = &(*max)->right;

    else

      max = &(*max)->left;

    path >>= 1;

    k -= 1;

  }

  heap->nelts -= 1;

  /* Unlink the max node. */

  child = *max;

  *max = NULL;

  if (child == node) {

    /* We're removing either the max or the last node in the tree. */

    if (child == heap->min) {

      heap->min = NULL;

    }

    return;

  }

  /* Replace the to be deleted node with the max node. */

  child->left = node->left;

  child->right = node->right;

  child->parent = node->parent;

  if (child->left != NULL) {

    child->left->parent = child;

  }

  if (child->right != NULL) {

    child->right->parent = child;

  }

  if (node->parent == NULL) {

    heap->min = child;

  } else if (node->parent->left == node) {

    node->parent->left = child;

  } else {

    node->parent->right = child;

  }

  /* Walk down the subtree and check at each node if the heap property holds.

   * It's a min heap so parent < child must be true.  If the parent is bigger,

   * swap it with the smallest child.

   */

  for (;;) {

    smallest = child;

    if (child->left != NULL && less_than(child->left, smallest))

      smallest = child->left;

    if (child->right != NULL && less_than(child->right, smallest))

      smallest = child->right;

    if (smallest == child)

      break;

    heap_node_swap(heap, child, smallest);

  }

  /* Walk up the subtree and check that each parent is less than the node

   * this is required, because `max` node is not guaranteed to be the

   * actual maximum in tree

   */

  while (child->parent != NULL && less_than(child, child->parent))

    heap_node_swap(heap, child->parent, child);

}

HEAP_EXPORT(void heap_dequeue(struct heap* heap, heap_compare_fn less_than)) {

  heap_remove(heap, heap->min, less_than);

}

#undef HEAP_EXPORT

#endif  /* UV_SRC_HEAP_H_ */