QGIS API Documentation  2.6.0-Brighton
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
priorityqueue.h
Go to the documentation of this file.
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 
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:
65  PriorityQueue( int n, int maxId, bool min );
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