QGIS API Documentation 3.36.0-Maidenhead (09951dc0acf)
Loading...
Searching...
No Matches
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
43namespace pal
44{
45
53 {
54
55 public:
56
63 PriorityQueue( int n, int maxId, bool min );
65
67 PriorityQueue( const PriorityQueue & ) = delete;
70
71 void print();
72
73 int getSize() const;
74 int getSizeByPos() const;
75
76 bool isIn( int key ) const;
77
78 int getBest(); // O(log n)
79
80 void remove( int key );
81 void insert( int key, double p );
82
83 void sort(); // O(n log n)
84
85 void downheap( int id );
86 void upheap( int key );
87
88 void decreaseKey( int key );
89 void setPriority( int key, double new_p );
90
91
92 int getId( int key ) const;
93 private:
94
95 int size;
96 int maxsize;
97 int maxId;
98 int *heap = nullptr;
99 double *p = nullptr;
100 int *pos = nullptr;
101
102 bool ( *greater )( double l, double r );
103 };
104
105} // namespace
106
107#endif
Custom priority queue for use in pal labeling engine.
PriorityQueue(const PriorityQueue &)=delete
PriorityQueue cannot be copied.
void decreaseKey(int key)
void setPriority(int key, double new_p)
void insert(int key, double p)
int getId(int key) const
bool isIn(int key) const
PriorityQueue & operator=(const PriorityQueue &)=delete
PriorityQueue cannot be copied.