src/pqueue.c

Go to the documentation of this file.

/***************************************************************************
 *   Copyright (C) 2010 by Matthias Ihrke   *
 *   ihrke@nld.ds.mpg.de
 *                                                                         *
 *   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 "pqueue.h"
#include "helper.h"

PriorityQueue* pq_init( ) {
  PriorityQueue *pq=(PriorityQueue*)malloc(sizeof(PriorityQueue));
  pq->root=NULL;
  return pq;
}

PQnode* pqnode_init( void *c, double priority ){
  PQnode *pq;
  pq = (PQnode*)malloc(sizeof(PQnode));
  pq->priority=priority;
  pq->content = c;
  pq->next = NULL;
  return pq;
}

void  pq_insert( PriorityQueue *pq, void *c, double prior ){
  PQnode *node=pqnode_init( c, prior );
  PQnode *it=pq->root;
  
  dprintf("Inserting node %p with priority %f\n", c, prior );
  if( it==NULL || prior<it->priority ){
     node->next=pq->root;
     pq->root=node;
     return;
  }
  
  while( 1 ){
     if( it->next==NULL ){
        it->next = node;
        return;
     } else if( prior<it->next->priority ){
        node->next = it->next;
        it->next = node;
        return;
     } else {
        it=it->next;
     }
  }
}

PQnode* pq_pop_node( PriorityQueue *pq ){
  PQnode *tmp;
  if( pq->root==NULL ){
     warnprintf("Popping from empty PQ\n");
     return NULL;
  }
  tmp = pq->root;
  pq->root = tmp->next;
  tmp->next=NULL;
  return tmp;
}

void* pq_pop( PriorityQueue *pq ){
  PQnode *tmp;
  void *content;

  tmp = pq_pop_node( pq );
  content = tmp->content;
  pqnode_free( tmp );

  return content;
}


void pq_print( FILE *out, PriorityQueue *pq ){
  fprintf( out, "PQ(%p)=[ ", pq );
  pqnode_print( out, pq->root );
  fprintf( out, " ]\n");
}
void pqnode_print( FILE *out, PQnode *N ){
  if( N==NULL ){
     return;
  }
  fprintf( out, "(%p,%.2f) ", N->content, N->priority );
  pqnode_print( out, N->next );
}

void pqnode_free( PQnode *n ){
  if( !n ) return;
  if( n->next ){
     pqnode_free( n->next );
  }
  free( n );
}
void  pq_free( PriorityQueue *pq ){
  pqnode_free( pq->root );
  free( pq );
  return;
}