← Back to branch summary

~ubuntu-branches/ubuntu/wily/qgis/wily

« back to all changes in this revision

Viewing changes to src/core/pal/priorityqueue.h

  • Committer: Bazaar Package Importer
  • Author(s): Johan Van de Wauw
  • Date: 2010-07-11 20:23:24 UTC
  • mfrom: (3.1.4 squeeze)
  • Revision ID: james.westby@ubuntu.com-20100711202324-5ktghxa7hracohmr
Tags: 1.4.0+12730-3ubuntu1
https://launchpad.net/bugs/540941
* Merge from Debian unstable (LP: #540941).
* Fix compilation issues with QT 4.7
* Add build-depends on libqt4-webkit-dev 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/pal/priorityqueue.h
 
1
/*
 
2
 *   libpal - Automated Placement of Labels Library
 
3
 *
 
4
 *   Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
 
5
 *                      University of Applied Sciences, Western Switzerland
 
6
 *                      http://www.hes-so.ch
 
7
 *
 
8
 *   Contact:
 
9
 *      maxence.laurent <at> heig-vd <dot> ch
 
10
 *    or
 
11
 *      eric.taillard <at> heig-vd <dot> ch
 
12
 *
 
13
 * This file is part of libpal.
 
14
 *
 
15
 * libpal is free software: you can redistribute it and/or modify
 
16
 * it under the terms of the GNU General Public License as published by
 
17
 * the Free Software Foundation, either version 3 of the License, or
 
18
 * (at your option) any later version.
 
19
 *
 
20
 * libpal is distributed in the hope that it will be useful,
 
21
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
22
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
23
 * GNU General Public License for more details.
 
24
 *
 
25
 * You should have received a copy of the GNU General Public License
 
26
 * along with libpal.  If not, see <http://www.gnu.org/licenses/>.
 
27
 *
 
28
 */
 
29
 
 
30
#ifdef HAVE_CONFIG_H
 
31
#include <config.h>
 
32
#endif
 
33
 
 
34
#ifndef _PRIORITYQUEUE_H
 
35
#define _PRIORITYQUEUE_H
 
36
 
 
37
#include <iostream>
 
38
 
 
39
#define LEFT(x) (2*x+1)
 
40
#define RIGHT(x) (2*x+2)
 
41
#define PARENT(x) ((x-1)/2)
 
42
 
 
43
 
 
44
namespace pal
 
45
{
 
46
 
 
47
  class PriorityQueue
 
48
  {
 
49
    private:
 
50
      int size;
 
51
      int maxsize;
 
52
      int maxId;
 
53
      int *heap;
 
54
      double *p;
 
55
      int *pos;
 
56
 
 
57
      bool ( *greater )( double l, double r );
 
58
 
 
59
    public:
 
60
      /** \brief Create a priority queue of max size n
 
61
       * \@param n max size of the queuet
 
62
       * \@param p external vector representing the priority
 
63
       * \@param min best element has the smalest p when min is True ans has the biggest when min is false
 
64
       */
 
65
      PriorityQueue( int n, int maxId, bool min );
 
66
      ~PriorityQueue();
 
67
 
 
68
      void print();
 
69
 
 
70
      int getSize();
 
71
      int getSizeByPos();
 
72
 
 
73
      bool isIn( int key );
 
74
 
 
75
      int getBest(); // O(log n)
 
76
 
 
77
      void remove( int key );
 
78
      void insert( int key, double p );
 
79
 
 
80
      void sort(); // O(n log n)
 
81
 
 
82
      void downheap( int id );
 
83
      void upheap( int key );
 
84
 
 
85
      void decreaseKey( int key );
 
86
      void setPriority( int key, double new_p );
 
87
 
 
88
 
 
89
      int getId( int key );
 
90
  };
 
91
 
 
92
} // namespace
 
93
 
 
94
#endif