Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/util/bin_heap.h	Lines:	163	165	98.8 %
Date:	2021-09-29	Branches:	123	564	21.8 %


/******************************************************************************
 * Top contributors (to current version):
 *   Tim King, Morgan Deters, Mathias Preiner
 *
 * This file is part of the cvc5 project.
 *
 * Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
 * in the top-level source directory and their institutional affiliations.
 * All rights reserved.  See the file COPYING in the top-level source
 * directory for licensing information.
 * ****************************************************************************
 *
 * An implementation of a binary heap
 *
 * Attempts to roughly follow the contract of Boost's d_ary_heap.
 * (http://www.boost.org/doc/libs/1_49_0/doc/html/boost/heap/d_ary_heap.html)
 * Also attempts to generalize ext/pd_bs/priority_queue.
 * (http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/priority_queue.html)
 */

#include "cvc5_private.h"

#ifndef CVC5__BIN_HEAP_H
#define CVC5__BIN_HEAP_H

#include <limits>
#include <functional>

#include "base/check.h"
#include "base/exception.h"

namespace cvc5 {

/**
 * BinaryHeap that orders its elements greatest-first (i.e., in the opposite
 * direction of the provided comparator).  Update of elements is permitted
 * via handles, which are not invalidated by mutation (pushes and pops etc.).
 * Handles are invalidted when their element is no longer a member of the
 * heap.  Iteration over elements is supported but iteration is unsorted and
 * iterators are immutable.
 */
template <class Elem, class CmpFcn = std::less<Elem> >
class BinaryHeap {
private:
  typedef Elem T;
  struct HElement;

  typedef std::vector<HElement*> ElementVector;

  struct HElement {
    HElement(size_t pos, const T& elem): d_pos(pos), d_elem(elem) {}
    size_t d_pos;
    T d_elem;
  };/* struct HElement */

  /** A 0 indexed binary heap. */
  ElementVector d_heap;

  /** The comparator. */
  CmpFcn d_cmp;

  // disallow copy and assignment
  BinaryHeap(const BinaryHeap&) = delete;
  BinaryHeap& operator=(const BinaryHeap&) = delete;

public:
  BinaryHeap(const CmpFcn& c = CmpFcn())
    : d_heap()
    , d_cmp(c)
  {}

  ~BinaryHeap(){
    clear();
  }

  class handle {
  private:
    HElement* d_pointer;
    handle(HElement* p) : d_pointer(p){}
    friend class BinaryHeap;
  public:
    handle() : d_pointer(NULL) {}
    const T& operator*() const {
      Assert(d_pointer != NULL);
      return d_pointer->d_elem;
    }

    bool operator==(const handle& h) const {
      return d_pointer == h.d_pointer;
    }

    bool operator!=(const handle& h) const {
      return d_pointer != h.d_pointer;
    }

  }; /* BinaryHeap<>::handle */

  class const_iterator : public std::iterator<std::input_iterator_tag, Elem> {
  private:
    typename ElementVector::const_iterator d_iter;
    friend class BinaryHeap;
    const_iterator(const typename ElementVector::const_iterator& iter)
      : d_iter(iter)
    {}
  public:
    const_iterator(){}
    inline bool operator==(const const_iterator& ci) const{
      return d_iter == ci.d_iter;
    }
    inline bool operator!=(const const_iterator& ci) const{
      return d_iter != ci.d_iter;
    }
    inline const_iterator& operator++(){
      ++d_iter;
      return *this;
    }
    inline const_iterator operator++(int){
      const_iterator i = *this;
      ++d_iter;
      return i;
    }
    inline const T& operator*() const{
      const HElement* he = *d_iter;
      return he->d_elem;
    }

  };/* BinaryHeap<>::const_iterator */

  typedef const_iterator iterator;

  inline size_t size() const { return d_heap.size(); }
  inline bool empty() const { return d_heap.empty(); }

  inline const_iterator begin() const {
    return const_iterator(d_heap.begin());
  }

  inline const_iterator end() const {
    return const_iterator(d_heap.end());
  }

  void clear(){
    typename ElementVector::iterator i=d_heap.begin(), iend=d_heap.end();
    for(; i!=iend; ++i){
      HElement* he = *i;
      delete he;
    }
    d_heap.clear();
  }

  void swap(BinaryHeap& heap){
    std::swap(d_heap, heap.d_heap);
    std::swap(d_cmp, heap.d_cmp);
  }

  handle push(const T& toAdded){
    Assert(size() < MAX_SIZE);
    HElement* he = new HElement(size(), toAdded);
    d_heap.push_back(he);
    up_heap(he);
    return handle(he);
  }

  void erase(handle h){
    Assert(!empty());
    Assert(debugHandle(h));

    HElement* he = h.d_pointer;
    size_t pos = he->d_pos;
    if(pos == root()){
      // the top element can be efficiently removed by pop
      pop();
    }else if(pos == last()){
      // the last element can be safely removed
      d_heap.pop_back();
      delete he;
    }else{
      // This corresponds to
      // 1) swapping the elements at pos with the element at last:
      // 2) deleting the new last element
      // 3) updating the position of the new element at pos
      swapIndices(pos, last());
      d_heap.pop_back();
      delete he;
      update(handle(d_heap[pos]));
    }
  }

  void pop(){
    Assert(!empty());
    swapIndices(root(), last());
    HElement* b = d_heap.back();
    d_heap.pop_back();
    delete b;

    if(!empty()){
      down_heap(d_heap.front());
    }
  }

  const T& top() const {
    Assert(!empty());
    return (d_heap.front())->d_elem;
  }

private:
  void update(handle h){
    Assert(!empty());
    Assert(debugHandle(h));

    // The relationship between h and its parent, left and right has become unknown.
    // But it is assumed that parent <= left, and parent <= right still hold.
    // Figure out whether to up_heap or down_heap.

    Assert(!empty());
    HElement* he = h.d_pointer;

    size_t pos = he->d_pos;
    if(pos == root()){
      // no parent
      down_heap(he);
    }else{
      size_t par = parent(pos);
      HElement* at_parent = d_heap[par];
      if(gt(he->d_elem, at_parent->d_elem)){
        // he > parent
        up_heap(he);
      }else{
        down_heap(he);
      }
    }
  }

public:
  void update(handle h, const T& val){
    Assert(!empty());
    Assert(debugHandle(h));
    h.d_pointer->d_elem = val;
    update(h);
  }

  /** (std::numeric_limits<size_t>::max()-2)/2; */
  static const size_t MAX_SIZE;

private:
  inline bool gt(const T& a, const T& b) const{
    // cmp acts like an operator<
    return d_cmp(b, a);
  }

  inline bool lt(const T& a, const T& b) const{
    return d_cmp(a, b);
  }

  inline static size_t parent(size_t p){
    Assert(p != root());
    return (p-1)/2;
  }
  inline static size_t right(size_t p){ return 2*p+2; }
  inline static size_t left(size_t p){ return 2*p+1; }
  inline static size_t root(){ return 0; }
  inline size_t last() const{
    Assert(!empty());
    return size() - 1;
  }

  inline void swapIndices(size_t i, size_t j){
    HElement* at_i = d_heap[i];
    HElement* at_j = d_heap[j];
    swap(i,j,at_i,at_j);
  }

  inline void swapPointers(HElement* at_i, HElement* at_j){
    // still works if at_i == at_j
    size_t i = at_i->d_pos;
    size_t j = at_j->d_pos;
    swap(i,j,at_i,at_j);
  }

  inline void swap(size_t i, size_t j, HElement* at_i, HElement* at_j){
    // still works if i == j
    Assert(i == at_i->d_pos);
    Assert(j == at_j->d_pos);
    d_heap[i] = at_j;
    d_heap[j] = at_i;
    at_i->d_pos = j;
    at_j->d_pos = i;
  }

  void up_heap(HElement* he){
    const size_t& curr = he->d_pos;
    // The value of curr changes implicitly during swap operations.
    while(curr != root()){
      // he->d_elem > parent
      size_t par = parent(curr);
      HElement* at_parent = d_heap[par];
      if(gt(he->d_elem, at_parent->d_elem)){
        swap(curr, par, he, at_parent);
      }else{
        break;
      }
    }
  }

  void down_heap(HElement* he){
    const size_t& curr = he->d_pos;
    // The value of curr changes implicitly during swap operations.
    size_t N = size();
    size_t r, l;

    while((r = right(curr)) < N){
      l = left(curr);

      // if at_left == at_right, favor left
      HElement* at_left = d_heap[l];
      HElement* at_right = d_heap[r];
      if(lt(he->d_elem, at_left->d_elem)){
        // he < at_left
        if(lt(at_left->d_elem, at_right->d_elem)){
          // he < at_left < at_right
          swap(curr, r, he, at_right);
        }else{
          //       he <  at_left
          // at_right <= at_left
          swap(curr, l, he, at_left);
        }
      }else{
        // at_left <= he
        if(lt(he->d_elem, at_right->d_elem)){
          // at_left <= he < at_right
          swap(curr, r, he, at_right);
        }else{
          // at_left  <= he
          // at_right <= he
          break;
        }
      }
    }
    l = left(curr);
    if(r >= N && l < N){
      // there is a left but not a right
      HElement* at_left = d_heap[l];
      if(lt(he->d_elem, at_left->d_elem)){
        // he < at_left
        swap(curr, l, he, at_left);
      }
    }
  }

  bool debugHandle(handle h) const{
    HElement* he = h.d_pointer;
    if( he == NULL ){
      return true;
    }else if(he->d_pos >= size()){
      return false;
    }else{
      return he == d_heap[he->d_pos];
    }
  }

}; /* class BinaryHeap<> */

template <class Elem, class CmpFcn>
const size_t BinaryHeap<Elem,CmpFcn>::MAX_SIZE = (std::numeric_limits<size_t>::max()-2)/2;

}  // namespace cvc5

#endif /* CVC5__BIN_HEAP_H */


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************
2		* Top contributors (to current version):
3		* Tim King, Morgan Deters, Mathias Preiner
4		*
5		* This file is part of the cvc5 project.
6		*
7		* Copyright (c) 2009-2021 by the authors listed in the file AUTHORS
8		* in the top-level source directory and their institutional affiliations.
9		* All rights reserved. See the file COPYING in the top-level source
10		* directory for licensing information.
11		* ****************************************************************************
12		*
13		* An implementation of a binary heap
14		*
15		* Attempts to roughly follow the contract of Boost's d_ary_heap.
16		* (http://www.boost.org/doc/libs/1_49_0/doc/html/boost/heap/d_ary_heap.html)
17		* Also attempts to generalize ext/pd_bs/priority_queue.
18		* (http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/priority_queue.html)
19		*/
20
21		#include "cvc5_private.h"
22
23		#ifndef CVC5__BIN_HEAP_H
24		#define CVC5__BIN_HEAP_H
25
26		#include <limits>
27		#include <functional>
28
29		#include "base/check.h"
30		#include "base/exception.h"
31
32		namespace cvc5 {
33
34		/**
35		* BinaryHeap that orders its elements greatest-first (i.e., in the opposite
36		* direction of the provided comparator). Update of elements is permitted
37		* via handles, which are not invalidated by mutation (pushes and pops etc.).
38		* Handles are invalidted when their element is no longer a member of the
39		* heap. Iteration over elements is supported but iteration is unsorted and
40		* iterators are immutable.
41		*/
42		template <class Elem, class CmpFcn = std::less<Elem> >
43		class BinaryHeap {
44		private:
45		typedef Elem T;
46		struct HElement;
47
48		typedef std::vector<HElement*> ElementVector;
49
50		struct HElement {
51	387536	HElement(size_t pos, const T& elem): d_pos(pos), d_elem(elem) {}
52		size_t d_pos;
53		T d_elem;
54		};/* struct HElement */
55
56		/** A 0 indexed binary heap. */
57		ElementVector d_heap;
58
59		/** The comparator. */
60		CmpFcn d_cmp;
61
62		// disallow copy and assignment
63		BinaryHeap(const BinaryHeap&) = delete;
64		BinaryHeap& operator=(const BinaryHeap&) = delete;
65
66		public:
67	111165	BinaryHeap(const CmpFcn& c = CmpFcn())
68		: d_heap()
69	111165	, d_cmp(c)
70	111165	{}
71
72	111162	~BinaryHeap(){
73	111162	clear();
74	111162	}
75
76		class handle {
77		private:
78		HElement* d_pointer;
79	441076	handle(HElement* p) : d_pointer(p){}
80		friend class BinaryHeap;
81		public:
82	612815	handle() : d_pointer(NULL) {}
83	60022	const T& operator*() const {
84	60022	Assert(d_pointer != NULL);
85	60022	return d_pointer->d_elem;
86		}
87
88	2	bool operator==(const handle& h) const {
89	2	return d_pointer == h.d_pointer;
90		}
91
92	12	bool operator!=(const handle& h) const {
93	12	return d_pointer != h.d_pointer;
94		}
95
96		}; /* BinaryHeap<>::handle */
97
98		class const_iterator : public std::iterator<std::input_iterator_tag, Elem> {
99		private:
100		typename ElementVector::const_iterator d_iter;
101		friend class BinaryHeap;
102	209828	const_iterator(const typename ElementVector::const_iterator& iter)
103	209828	: d_iter(iter)
104	209828	{}
105		public:
106		const_iterator(){}
107	6	inline bool operator==(const const_iterator& ci) const{
108	6	return d_iter == ci.d_iter;
109		}
110	203029	inline bool operator!=(const const_iterator& ci) const{
111	203029	return d_iter != ci.d_iter;
112		}
113	98121	inline const_iterator& operator++(){
114	98121	++d_iter;
115	98121	return *this;
116		}
117	8	inline const_iterator operator++(int){
118	8	const_iterator i = *this;
119	8	++d_iter;
120	8	return i;
121		}
122	98139	inline const T& operator*() const{
123	98139	const HElement* he = *d_iter;
124	98139	return he->d_elem;
125		}
126
127		};/* BinaryHeap<>::const_iterator */
128
129		typedef const_iterator iterator;
130
131	1753872	inline size_t size() const { return d_heap.size(); }
132	1785516	inline bool empty() const { return d_heap.empty(); }
133
134	104914	inline const_iterator begin() const {
135	104914	return const_iterator(d_heap.begin());
136		}
137
138	104914	inline const_iterator end() const {
139	104914	return const_iterator(d_heap.end());
140		}
141
142	613463	void clear(){
143	613463	typename ElementVector::iterator i=d_heap.begin(), iend=d_heap.end();
144	940507	for(; i!=iend; ++i){
145	163522	HElement* he = *i;
146	163522	delete he;
147		}
148	613463	d_heap.clear();
149	613463	}
150
151	104890	void swap(BinaryHeap& heap){
152	104890	std::swap(d_heap, heap.d_heap);
153	104890	std::swap(d_cmp, heap.d_cmp);
154	104890	}
155
156	387536	handle push(const T& toAdded){
157	387536	Assert(size() < MAX_SIZE);
158	387536	HElement* he = new HElement(size(), toAdded);
159	387536	d_heap.push_back(he);
160	387536	up_heap(he);
161	387536	return handle(he);
162		}
163
164	200004	void erase(handle h){
165	200004	Assert(!empty());
166	200004	Assert(debugHandle(h));
167
168	200004	HElement* he = h.d_pointer;
169	200004	size_t pos = he->d_pos;
170	200004	if(pos == root()){
171		// the top element can be efficiently removed by pop
172	123544	pop();
173	76460	}else if(pos == last()){
174		// the last element can be safely removed
175	22920	d_heap.pop_back();
176	22920	delete he;
177		}else{
178		// This corresponds to
179		// 1) swapping the elements at pos with the element at last:
180		// 2) deleting the new last element
181		// 3) updating the position of the new element at pos
182	53540	swapIndices(pos, last());
183	53540	d_heap.pop_back();
184	53540	delete he;
185	53540	update(handle(d_heap[pos]));
186		}
187	200004	}
188
189	147554	void pop(){
190	147554	Assert(!empty());
191	147554	swapIndices(root(), last());
192	147554	HElement* b = d_heap.back();
193	147554	d_heap.pop_back();
194	147554	delete b;
195
196	147554	if(!empty()){
197	95489	down_heap(d_heap.front());
198		}
199	147554	}
200
201	182914	const T& top() const {
202	182914	Assert(!empty());
203	182914	return (d_heap.front())->d_elem;
204		}
205
206		private:
207	150886	void update(handle h){
208	150886	Assert(!empty());
209	150886	Assert(debugHandle(h));
210
211		// The relationship between h and its parent, left and right has become unknown.
212		// But it is assumed that parent <= left, and parent <= right still hold.
213		// Figure out whether to up_heap or down_heap.
214
215	150886	Assert(!empty());
216	150886	HElement* he = h.d_pointer;
217
218	150886	size_t pos = he->d_pos;
219	150886	if(pos == root()){
220		// no parent
221	2849	down_heap(he);
222		}else{
223	148037	size_t par = parent(pos);
224	148037	HElement* at_parent = d_heap[par];
225	148037	if(gt(he->d_elem, at_parent->d_elem)){
226		// he > parent
227	14991	up_heap(he);
228		}else{
229	133046	down_heap(he);
230		}
231		}
232	150886	}
233
234		public:
235	97346	void update(handle h, const T& val){
236	97346	Assert(!empty());
237	97346	Assert(debugHandle(h));
238	97346	h.d_pointer->d_elem = val;
239	97346	update(h);
240	97346	}
241
242		/** (std::numeric_limits<size_t>::max()-2)/2; */
243		static const size_t MAX_SIZE;
244
245		private:
246	600174	inline bool gt(const T& a, const T& b) const{
247		// cmp acts like an operator<
248	600174	return d_cmp(b, a);
249		}
250
251	836216	inline bool lt(const T& a, const T& b) const{
252	836216	return d_cmp(a, b);
253		}
254
255	600174	inline static size_t parent(size_t p){
256	600174	Assert(p != root());
257	600174	return (p-1)/2;
258		}
259	583264	inline static size_t right(size_t p){ return 2*p+2; }
260	635209	inline static size_t left(size_t p){ return 2*p+1; }
261	1750448	inline static size_t root(){ return 0; }
262	277554	inline size_t last() const{
263	277554	Assert(!empty());
264	277554	return size() - 1;
265		}
266
267	201094	inline void swapIndices(size_t i, size_t j){
268	201094	HElement* at_i = d_heap[i];
269	201094	HElement* at_j = d_heap[j];
270	201094	swap(i,j,at_i,at_j);
271	201094	}
272
273		inline void swapPointers(HElement* at_i, HElement* at_j){
274		// still works if at_i == at_j
275		size_t i = at_i->d_pos;
276		size_t j = at_j->d_pos;
277		swap(i,j,at_i,at_j);
278		}
279
280	812666	inline void swap(size_t i, size_t j, HElement* at_i, HElement* at_j){
281		// still works if i == j
282	812666	Assert(i == at_i->d_pos);
283	812666	Assert(j == at_j->d_pos);
284	812666	d_heap[i] = at_j;
285	812666	d_heap[j] = at_i;
286	812666	at_i->d_pos = j;
287	812666	at_j->d_pos = i;
288	812666	}
289
290	402527	void up_heap(HElement* he){
291	402527	const size_t& curr = he->d_pos;
292		// The value of curr changes implicitly during swap operations.
293	901133	while(curr != root()){
294		// he->d_elem > parent
295	452137	size_t par = parent(curr);
296	452137	HElement* at_parent = d_heap[par];
297	452137	if(gt(he->d_elem, at_parent->d_elem)){
298	249303	swap(curr, par, he, at_parent);
299		}else{
300	202834	break;
301		}
302		}
303	402527	}
304
305	231384	void down_heap(HElement* he){
306	231384	const size_t& curr = he->d_pos;
307		// The value of curr changes implicitly during swap operations.
308	231384	size_t N = size();
309		size_t r, l;
310
311	935144	while((r = right(curr)) < N){
312	403825	l = left(curr);
313
314		// if at_left == at_right, favor left
315	403825	HElement* at_left = d_heap[l];
316	403825	HElement* at_right = d_heap[r];
317	403825	if(lt(he->d_elem, at_left->d_elem)){
318		// he < at_left
319	338142	if(lt(at_left->d_elem, at_right->d_elem)){
320		// he < at_left < at_right
321	151494	swap(curr, r, he, at_right);
322		}else{
323		// he < at_left
324		// at_right <= at_left
325	186648	swap(curr, l, he, at_left);
326		}
327		}else{
328		// at_left <= he
329	65683	if(lt(he->d_elem, at_right->d_elem)){
330		// at_left <= he < at_right
331	13738	swap(curr, r, he, at_right);
332		}else{
333		// at_left <= he
334		// at_right <= he
335	51945	break;
336		}
337		}
338		}
339	231384	l = left(curr);
340	231384	if(r >= N && l < N){
341		// there is a left but not a right
342	28566	HElement* at_left = d_heap[l];
343	28566	if(lt(he->d_elem, at_left->d_elem)){
344		// he < at_left
345	10389	swap(curr, l, he, at_left);
346		}
347		}
348	231384	}
349
350	448236	bool debugHandle(handle h) const{
351	448236	HElement* he = h.d_pointer;
352	448236	if( he == NULL ){
353		return true;
354	448236	}else if(he->d_pos >= size()){
355		return false;
356		}else{
357	448236	return he == d_heap[he->d_pos];
358		}
359		}
360
361		}; /* class BinaryHeap<> */
362
363		template <class Elem, class CmpFcn>
364		const size_t BinaryHeap<Elem,CmpFcn>::MAX_SIZE = (std::numeric_limits<size_t>::max()-2)/2;
365
366		} // namespace cvc5
367
368		#endif /* CVC5__BIN_HEAP_H */