Line data Source code
1 : /* Copyright (C) 2015 Wildfire Games.
2 : * This file is part of 0 A.D.
3 : *
4 : * 0 A.D. is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 2 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * 0 A.D. is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : *
14 : * You should have received a copy of the GNU General Public License
15 : * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 : */
17 :
18 : #ifndef INCLUDED_PRIORITYQUEUE
19 : #define INCLUDED_PRIORITYQUEUE
20 :
21 : /*
22 : * Priority queues for pathfinder.
23 : * (These probably aren't suitable for more general uses.)
24 : */
25 :
26 : #ifdef NDEBUG
27 : #define PRIORITYQUEUE_DEBUG 0
28 : #else
29 : #define PRIORITYQUEUE_DEBUG 1
30 : #endif
31 :
32 : template <typename Item, typename CMP>
33 : struct QueueItemPriority
34 : {
35 0 : bool operator()(const Item& a, const Item& b) const
36 : {
37 0 : if (CMP()(b.rank, a.rank)) // higher costs are lower priority
38 0 : return true;
39 0 : if (CMP()(a.rank, b.rank))
40 0 : return false;
41 : // Need to tie-break to get a consistent ordering
42 0 : if (CMP()(b.h, a.h)) // higher heuristic costs are lower priority
43 0 : return true;
44 0 : if (CMP()(a.h, b.h))
45 0 : return false;
46 0 : if (a.id < b.id)
47 0 : return true;
48 0 : if (b.id < a.id)
49 0 : return false;
50 : #if PRIORITYQUEUE_DEBUG
51 0 : debug_warn(L"duplicate tiles in queue");
52 : #endif
53 0 : return false;
54 : }
55 : };
56 :
57 :
58 : /**
59 : * Priority queue implemented as a binary heap.
60 : * This is quite dreadfully slow in MSVC's debug STL implementation,
61 : * so we shouldn't use it unless we reimplement the heap functions more efficiently.
62 : */
63 : template <typename ID, typename R, typename H, typename CMP = std::less<R> >
64 0 : class PriorityQueueHeap
65 : {
66 : public:
67 : struct Item
68 : {
69 : ID id;
70 : R rank; // f = g+h (estimated total cost of path through here)
71 : H h; // heuristic cost
72 : };
73 :
74 0 : void push(const Item& item)
75 : {
76 0 : m_Heap.push_back(item);
77 0 : push_heap(m_Heap.begin(), m_Heap.end(), QueueItemPriority<Item, CMP>());
78 0 : }
79 :
80 0 : void promote(ID id, R UNUSED(oldrank), R newrank, H newh)
81 : {
82 : // Loop backwards since it seems a little faster in practice
83 0 : for (ssize_t n = m_Heap.size() - 1; n >= 0; --n)
84 : {
85 0 : if (m_Heap[n].id == id)
86 : {
87 : #if PRIORITYQUEUE_DEBUG
88 0 : ENSURE(m_Heap[n].rank > newrank);
89 : #endif
90 0 : m_Heap[n].rank = newrank;
91 0 : m_Heap[n].h = newh;
92 0 : push_heap(m_Heap.begin(), m_Heap.begin()+n+1, QueueItemPriority<Item, CMP>());
93 0 : return;
94 : }
95 : }
96 : }
97 :
98 0 : Item pop()
99 : {
100 : #if PRIORITYQUEUE_DEBUG
101 0 : ENSURE(m_Heap.size());
102 : #endif
103 0 : Item r = m_Heap[0];
104 0 : pop_heap(m_Heap.begin(), m_Heap.end(), QueueItemPriority<Item, CMP>());
105 0 : m_Heap.pop_back();
106 0 : return r;
107 : }
108 :
109 0 : bool empty()
110 : {
111 0 : return m_Heap.empty();
112 : }
113 :
114 : size_t size()
115 : {
116 : return m_Heap.size();
117 : }
118 :
119 0 : void clear()
120 : {
121 0 : m_Heap.clear();
122 0 : }
123 :
124 : std::vector<Item> m_Heap;
125 : };
126 :
127 : /**
128 : * Priority queue implemented as an unsorted array.
129 : * This means pop() is O(n), but push and promote are O(1), and n is typically small
130 : * (average around 50-100 in some rough tests).
131 : * It seems fractionally slower than a binary heap in optimised builds, but is
132 : * much simpler and less susceptible to MSVC's painfully slow debug STL.
133 : */
134 : template <typename ID, typename R, typename H, typename CMP = std::less<R> >
135 : class PriorityQueueList
136 : {
137 : public:
138 : struct Item
139 : {
140 : ID id;
141 : R rank; // f = g+h (estimated total cost of path through here)
142 : H h; // heuristic cost
143 : };
144 :
145 : void push(const Item& item)
146 : {
147 : m_List.push_back(item);
148 : }
149 :
150 : Item* find(ID id)
151 : {
152 : for (size_t n = 0; n < m_List.size(); ++n)
153 : {
154 : if (m_List[n].id == id)
155 : return &m_List[n];
156 : }
157 : return NULL;
158 : }
159 :
160 : void promote(ID id, R UNUSED(oldrank), R newrank, H newh)
161 : {
162 : find(id)->rank = newrank;
163 : find(id)->h = newh;
164 : }
165 :
166 : Item pop()
167 : {
168 : #if PRIORITYQUEUE_DEBUG
169 : ENSURE(m_List.size());
170 : #endif
171 : // Loop backwards looking for the best (it's most likely to be one
172 : // we've recently pushed, so going backwards saves a bit of copying)
173 : Item best = m_List.back();
174 : size_t bestidx = m_List.size()-1;
175 : for (ssize_t i = (ssize_t)bestidx-1; i >= 0; --i)
176 : {
177 : if (QueueItemPriority<Item, CMP>()(best, m_List[i]))
178 : {
179 : bestidx = i;
180 : best = m_List[i];
181 : }
182 : }
183 : // Swap the matched element with the last in the list, then pop the new last
184 : m_List[bestidx] = m_List[m_List.size()-1];
185 : m_List.pop_back();
186 : return best;
187 : }
188 :
189 : bool empty()
190 : {
191 : return m_List.empty();
192 : }
193 :
194 : size_t size()
195 : {
196 : return m_List.size();
197 : }
198 :
199 :
200 : void clear()
201 : {
202 : m_List.clear();
203 : }
204 :
205 : std::vector<Item> m_List;
206 : };
207 :
208 : #endif // INCLUDED_PRIORITYQUEUE
|
