QGIS API Documentation 3.40.0-Bratislava (b56115d8743)
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
66 PriorityQueue( const PriorityQueue & ) = delete;
68
69 void print();
70
71 int getSize() const;
72 int getSizeByPos() const;
73
74 bool isIn( int key ) const;
75
76 int getBest(); // O(log n)
77
78 void remove( int key );
79 void insert( int key, double p );
80
81 void sort(); // O(n log n)
82
83 void downheap( int id );
84 void upheap( int key );
85
86 void decreaseKey( int key );
87 void setPriority( int key, double new_p );
88
89
90 int getId( int key ) const;
91 private:
92
93 int size;
94 int maxsize;
95 int maxId;
96 int *heap = nullptr;
97 double *p = nullptr;
98 int *pos = nullptr;
99
100 bool ( *greater )( double l, double r );
101 };
102
103} // namespace
104
105#endif
Custom priority queue for use in pal labeling engine.
PriorityQueue(const PriorityQueue &)=delete
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