/* -*- Mode: C; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ 
/* vim: set ts=2 et sw=2 tw=80: */
/*
   Copyright (c) 2013 D. Richard Hipp
  
   This program is free software; you can redistribute it and/or
   modify it under the terms of the Simplified BSD License (also
   known as the "2-Clause License" or "FreeBSD License".)
  
   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.
  
   Author contact information:
     drh@hwaci.com
     http://www.hwaci.com/drh/
  
  *****************************************************************************
   This file houses the priority queue class.
*/
#include <assert.h>

#include "fossil-scm/fossil.h"
#include "fossil-scm/fossil-internal.h"

void fsl_pq_clear(fsl_pq *p){
  fsl_free(p->list);
  *p = fsl_pq_empty;
}

/*
   Change the size of the queue so that it contains N slots
*/
static int fsl_pq_resize(fsl_pq *p, fsl_size_t N){
  void * re = fsl_realloc(p->list, sizeof(fsl_pq_e)*N);
  if(!re) return FSL_RC_OOM;
  else{
    p->list = (fsl_pq_e*)re;
    p->capacity = N;
    return 0;
  }
}

/**
   Insert element e into the queue.
*/
int fsl_pq_insert(fsl_pq *p, fsl_id_t e,
                  fsl_double_t v, void *pData){
  fsl_size_t i, j;
  if( p->used+1>p->capacity ){
    int const rc = fsl_pq_resize(p, p->used+5);
    if(rc) return rc;
  }
  for(i=0; i<p->used; ++i){
    if( p->list[i].value>v ){
      for(j=p->used; j>i; --j){
        p->list[j] = p->list[j-1];
      }
      break;
    }
  }
  p->list[i].id = e;
  p->list[i].p = pData;
  p->list[i].value = v;
  ++p->used;
  return 0;
}

/**
   Extract the first element from the queue (the element with
   the smallest value) and return its ID. Return 0 if the queue
   is empty. If pp is not NULL then *pp is (on success) assigned
   to the value member of the extracted element.
*/
fsl_id_t fsl_pq_extract(fsl_pq *p, void **pp){
  fsl_id_t e, i;
  if( p->used==0 ){
    if( pp ) *pp = 0;
    return 0;
  }
  e = p->list[0].id;
  if( pp ) *pp = p->list[0].p;
  for(i=0; i<((fsl_id_t)p->used-1); ++i){
    p->list[i] = p->list[i+1];
  }
  --p->used;
  return e;
}