/* modified by Juncheng Yang for use in libCacheSim 201606
 */

/*
 * Copyright (c) 2014, Volkan Yazıcı <volkan.yazici@gmail.com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * 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.
 */

#include "pqueue.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#ifdef __cplusplus
extern "C" {
#endif

#define left(i) ((i) << 1)
#define right(i) (((i) << 1) + 1)
#define parent(i) ((i) >> 1)

pqueue_t *pqueue_init(size_t n) {
  return pqueue_init_full(n, cmp_pri, get_pri, set_pri, get_pos, set_pos);
}

pqueue_t *pqueue_init_full(size_t n, pqueue_cmp_pri_f cmppri,
                           pqueue_get_pri_f getpri, pqueue_set_pri_f setpri,
                           pqueue_get_pos_f getpos, pqueue_set_pos_f setpos) {
  pqueue_t *q;

  if (!(q = malloc(sizeof(pqueue_t)))) return NULL;

  /* Need to allocate n+1 elements since element 0 isn't used. */
  if (!(q->d = malloc((n + 1) * sizeof(void *)))) {
    free(q);
    return NULL;
  }

  q->size = 1;
  q->avail = q->step = (n + 1); /* see comment above about n+1 */
  q->cmppri = cmppri;
  q->setpri = setpri;
  q->getpri = getpri;
  q->getpos = getpos;
  q->setpos = setpos;

  return q;
}

void pqueue_free(pqueue_t *q) {
  free(q->d);
  free(q);
}

size_t pqueue_size(pqueue_t *q) {
  /* queue element 0 exists but doesn't count since it isn't used. */
  return (q->size - 1);
}

static void bubble_up(pqueue_t *q, size_t i) {
  size_t parent_node;
  void *moving_node = q->d[i];
  pqueue_pri_t moving_pri = q->getpri(moving_node);

  for (parent_node = parent(i);
       ((i > 1) && q->cmppri(q->getpri(q->d[parent_node]), moving_pri));
       i = parent_node, parent_node = parent(i)) {
    q->d[i] = q->d[parent_node];
    q->setpos(q->d[i], i);
  }

  q->d[i] = moving_node;
  q->setpos(moving_node, i);
}

static size_t maxchild(pqueue_t *q, size_t i) {
  size_t child_node = left(i);

  if (child_node >= q->size) return 0;

  if ((child_node + 1) < q->size &&
      q->cmppri(q->getpri(q->d[child_node]), q->getpri(q->d[child_node + 1])))
    child_node++; /* use right child instead of left */

  return child_node;
}

static void percolate_down(pqueue_t *q, size_t i) {
  size_t child_node;
  void *moving_node = q->d[i];
  pqueue_pri_t moving_pri = q->getpri(moving_node);

  while ((child_node = maxchild(q, i)) &&
         q->cmppri(moving_pri, q->getpri(q->d[child_node]))) {
    q->d[i] = q->d[child_node];
    q->setpos(q->d[i], i);
    i = child_node;
  }

  q->d[i] = moving_node;
  q->setpos(moving_node, i);
}

int pqueue_insert(pqueue_t *q, void *d) {
  void *tmp;
  size_t i;
  size_t newsize;

  if (!q) return 1;

  /* allocate more memory if necessary */
  if (q->size >= q->avail) {
    newsize = q->size + q->step;
    if (!(tmp = realloc(q->d, sizeof(void *) * newsize))) return 1;
    q->d = tmp;
    q->avail = newsize;
  }

  /* insert obj_id */
  i = q->size++;
  q->d[i] = d;
  bubble_up(q, i);

  return 0;
}

void pqueue_change_priority(pqueue_t *q, pqueue_pri_t new_pri, void *d) {
  size_t posn;
  pqueue_pri_t old_pri = q->getpri(d);

  q->setpri(d, new_pri);
  posn = q->getpos(d);
  if (q->cmppri(old_pri, new_pri))
    bubble_up(q, posn);
  else
    percolate_down(q, posn);
}

int pqueue_remove(pqueue_t *q, void *d) {
  size_t posn = q->getpos(d);
  q->d[posn] = q->d[--q->size];
  if (q->cmppri(q->getpri(d), q->getpri(q->d[posn])))
    bubble_up(q, posn);
  else
    percolate_down(q, posn);

  return 0;
}

void *pqueue_pop(pqueue_t *q) {
  void *head;

  if (!q || q->size == 1) return NULL;

  head = q->d[1];
  q->d[1] = q->d[--q->size];
  percolate_down(q, 1);

  return head;
}

void *pqueue_peek(pqueue_t *q) {
  void *d;
  if (!q || q->size == 1) return NULL;
  d = q->d[1];
  return d;
}

void pqueue_dump(pqueue_t *q, FILE *out, pqueue_print_entry_f print) {
  int i;

  fprintf(stdout, "posn\tleft\tright\tparent\tmaxchild\t...\n");
  for (i = 1; i < (int)q->size; i++) {
    fprintf(stdout, "%d\t%d\t%d\t%d\t%ul\t", i, left(i), right(i), parent(i),
            (unsigned int)maxchild(q, i));
    print(out, q->d[i]);
  }
}

void pqueue_print(pqueue_t *q, FILE *out, pqueue_print_entry_f print) {
  pqueue_t *dup;
  void *e;

  dup = pqueue_init_full(q->size, q->cmppri, q->getpri, q->setpri, q->getpos,
                         q->setpos);
  dup->size = q->size;
  dup->avail = q->avail;
  dup->step = q->step;

  memcpy(dup->d, q->d, (q->size * sizeof(void *)));

  while ((e = pqueue_pop(dup))) print(out, e);

  pqueue_free(dup);
}

static int subtree_is_valid(pqueue_t *q, int pos) {
  if (left(pos) < (int)q->size) {
    /* has a left child */
    if (q->cmppri(q->getpri(q->d[pos]), q->getpri(q->d[left(pos)]))) return 0;
    if (!subtree_is_valid(q, left(pos))) return 0;
  }
  if (right(pos) < (int)q->size) {
    /* has a right child */
    if (q->cmppri(q->getpri(q->d[pos]), q->getpri(q->d[right(pos)]))) return 0;
    if (!subtree_is_valid(q, right(pos))) return 0;
  }
  return 1;
}

int pqueue_is_valid(pqueue_t *q) { return subtree_is_valid(q, 1); }

#ifdef __cplusplus
}
#endif
