QGIS API Documentation  3.16.0-Hannover (43b64b13f3)
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 #ifndef PAL_PRIORITYQUEUE_H
31 #define PAL_PRIORITYQUEUE_H
32 
33 #define SIP_NO_FILE
34 
35 
36 #include <iostream>
37 
38 #define LEFT(x) (2*x+1)
39 #define RIGHT(x) (2*x+2)
40 #define PARENT(x) ((x-1)/2)
41 
42 
43 namespace pal
44 {
45 
52  {
53 
54  public:
55 
62  PriorityQueue( int n, int maxId, bool min );
64 
66  PriorityQueue( const PriorityQueue & ) = delete;
68  PriorityQueue &operator=( const PriorityQueue & ) = delete;
69 
70  void print();
71 
72  int getSize();
73  int getSizeByPos();
74 
75  bool isIn( int key );
76 
77  int getBest(); // O(log n)
78 
79  void remove( int key );
80  void insert( int key, double p );
81 
82  void sort(); // O(n log n)
83 
84  void downheap( int id );
85  void upheap( int key );
86 
87  void decreaseKey( int key );
88  void setPriority( int key, double new_p );
89 
90 
91  int getId( int key );
92  private:
93 
94  int size;
95  int maxsize;
96  int maxId;
97  int *heap = nullptr;
98  double *p = nullptr;
99  int *pos = nullptr;
100 
101  bool ( *greater )( double l, double r );
102  };
103 
104 } // namespace
105 
106 #endif
pal::PriorityQueue::getSize
int getSize()
Definition: priorityqueue.cpp:76
pal::PriorityQueue::getSizeByPos
int getSizeByPos()
Definition: priorityqueue.cpp:307
pal::PriorityQueue
Definition: priorityqueue.h:52
pal::PriorityQueue::getId
int getId(int key)
Definition: priorityqueue.cpp:111
pal::PriorityQueue::isIn
bool isIn(int key)
Definition: priorityqueue.cpp:106
pal::PriorityQueue::downheap
void downheap(int id)
Definition: priorityqueue.cpp:211
pal::PriorityQueue::~PriorityQueue
~PriorityQueue()
Definition: priorityqueue.cpp:69
pal
Definition: qgsdiagramrenderer.h:49
pal::PriorityQueue::remove
void remove(int key)
Definition: priorityqueue.cpp:134
pal::PriorityQueue::upheap
void upheap(int key)
Definition: priorityqueue.cpp:168
pal::PriorityQueue::operator=
PriorityQueue & operator=(const PriorityQueue &)=delete
PriorityQueue cannot be copied.
pal::PriorityQueue::sort
void sort()
Definition: priorityqueue.cpp:154
pal::PriorityQueue::setPriority
void setPriority(int key, double new_p)
Definition: priorityqueue.cpp:252
pal::PriorityQueue::decreaseKey
void decreaseKey(int key)
Definition: priorityqueue.cpp:273
pal::PriorityQueue::getBest
int getBest()
Definition: priorityqueue.cpp:82
pal::PriorityQueue::PriorityQueue
PriorityQueue(int n, int maxId, bool min)
Create a priority queue of max size n \param n max size of the queuet \param p external vector repres...
Definition: priorityqueue.cpp:48
pal::PriorityQueue::PriorityQueue
PriorityQueue(const PriorityQueue &)=delete
PriorityQueue cannot be copied.
pal::PriorityQueue::insert
void insert(int key, double p)
Definition: priorityqueue.cpp:116
pal::PriorityQueue::print
void print()
Definition: priorityqueue.cpp:291