priorityqueue.cpp

Go to the documentation of this file.

/*
 *   libpal - Automated Placement of Labels Library
 *
 *   Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
 *                      University of Applied Sciences, Western Switzerland
 *                      http://www.hes-so.ch
 *
 *   Contact:
 *      maxence.laurent <at> heig-vd <dot> ch
 *    or
 *      eric.taillard <at> heig-vd <dot> ch
 *
 * This file is part of libpal.
 *
 * libpal 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 3 of the License, or
 * (at your option) any later version.
 *
 * libpal 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 libpal.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include <cstdio>

#include "internalexception.h"
#include "priorityqueue.h"

using namespace pal;

bool smaller( double l, double r )
{
  return l > r;
}

bool bigger( double l, double r )
{
  return l < r;
}

// O (size log size)
PriorityQueue::PriorityQueue( int n, int maxId, bool min )
    : size( 0 )
    , maxsize( n )
    , maxId( maxId )
{
  heap = new int[maxsize];
  p = new double[maxsize];
  pos = new int[maxId+1];

  int i;

  for ( i = 0; i <= maxId; i++ )
    pos[i] = -1;


  if ( min )
    greater = smaller;
  else
    greater = bigger;
}

PriorityQueue::~PriorityQueue()
{
  delete[] heap;
  delete[] p;
  delete[] pos;
}

int PriorityQueue::getSize()
{
  return size;
}

// O(log size)
int PriorityQueue::getBest()
{
  if ( size <= 0 )
    throw InternalException::Empty();

  int return_value = heap[0];

  size--;

  pos[heap[0]] = -1;

  if ( size > 0 )
  {
    pos[heap[size]] = 0;

    heap[0] = heap[size];
    p[0] = p[size];
    downheap( 0 );
  }

  return return_value;
}


bool PriorityQueue::isIn( int key )
{
  return key <= maxId && pos[key] >= 0;
}

int PriorityQueue::getId( int key )
{
  return key <= maxId ? pos[key] : -1;
}

void PriorityQueue::insert( int key, double p )
{
  if ( size == maxsize || key > maxId || key < 0 )
    throw InternalException::Full();

  heap[size] = key;
  pos[key] = size;
  this->p[size] = p;

  size++;


  upheap( key );
}


// O(size)
//
void PriorityQueue::remove( int key )
{
  if ( key < 0 || key > maxId )
    return;
  int i = pos[key];

  if ( i >= 0 )
  {
    size--;
    pos[heap[size]] = i;
    pos[key] = -1;

    heap[i] = heap[size];
    p[i]    = p[size];

    downheap( i );
  }
}

// O (size log size)
void PriorityQueue::sort()
{
  int i;
  int pi = 2;
  while ( size > pi ) pi *= 2;

  i = pi / 2 - 2;

  for ( i = size - 1; i >= 0; i-- )
    downheap( i );

}


void PriorityQueue::upheap( int key )
{
  int i;
  int i2;

  int tmpT;
  double tmpP;


  if ( key < 0 || key > maxId )
    return;

  i = pos[key];

  if ( i >= -1 )
  {
    while ( i > 0 )
    {
      if ( greater( p[PARENT( i )], p[i] ) )
      {
        i2 = PARENT( i );

        pos[heap[i]] = i2;
        pos[heap[i2]] = i;

        tmpT = heap[i];
        tmpP = p[i];

        heap[i] = heap[i2];
        p[i]    = p[i2];

        heap[i2] = tmpT;
        p[i2]    = tmpP;

        i = i2;
      }
      else
        break;
    }
  }
}

// O(log n)
void PriorityQueue::downheap( int id )
{
  int min_child;
  int tmpT;
  double tmpP;

  for ( ;; )
  {
    if ( LEFT( id ) < size )
    {
      if ( RIGHT( id ) < size )
      {
        min_child = greater( p[RIGHT( id )], p[LEFT( id )] ) ? LEFT( id ) : RIGHT( id );
      }
      else
        min_child = LEFT( id );
    }
    else // leaf
      break;

    if ( greater( p[id], p[min_child] ) )
    {
      pos[heap[id]] = min_child;
      pos[heap[min_child]] = id;

      tmpT = heap[id];
      tmpP = p[id];

      heap[id] = heap[min_child];
      p[id]    = p[min_child];

      heap[min_child] = tmpT;
      p[min_child]    = tmpP;

      id = min_child;
    }
    else
      break;
  }
}

void PriorityQueue::setPriority( int key, double new_p )
{

  if ( key < 0 || key > maxId )
    return;

  int i = pos[key];

  if ( i < 0 )
  {
    insert( key, new_p );
    return;
  }

  p[i] = new_p;

  upheap( key );
  downheap( pos[key] );
}


void PriorityQueue::decreaseKey( int key )
{

  if ( key < 0 || key > maxId )
    return;

  int i = pos[key];

  if ( i < 0 )
    return;

  p[i]--;

  upheap( key );
  downheap( pos[key] );
}


void PriorityQueue::print()
{
  int i;

  fprintf( stderr, "Size: %d\nMaxSize: %d\n", size, maxsize );

  for ( i = 0; i < size; i++ )
  {
    //printf ("key: %7d  ->  index: %7d -> key: %7d   p: %7d\n", i, pos[i], heap[pos[i]], p[pos[i]]);
    fprintf( stderr, "id: %7d  ->  key: %7d -> id: %7d   p: %7f\n", i, heap[i], pos[heap[i]], p[i] );
  }
  fprintf( stderr, "\n" );

}


int PriorityQueue::getSizeByPos()
{
  int i;
  int count = 0;
  for ( i = 0; i < maxsize; i++ )
  {
    if ( pos[i] >= 0 )
      count++;
  }
  return count;
}