Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/util/bin_heap.h	Lines:	163	165	98.8 %
Date:	2021-05-22	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	573067	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	163243	BinaryHeap(const CmpFcn& c = CmpFcn())
68		: d_heap()
69	163243	, d_cmp(c)
70	163243	{}
71
72	163243	~BinaryHeap(){
73	163243	clear();
74	163243	}
75
76		class handle {
77		private:
78		HElement* d_pointer;
79	651551	handle(HElement* p) : d_pointer(p){}
80		friend class BinaryHeap;
81		public:
82	904922	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	307608	const_iterator(const typename ElementVector::const_iterator& iter)
103	307608	: d_iter(iter)
104	307608	{}
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	314986	inline bool operator!=(const const_iterator& ci) const{
111	314986	return d_iter != ci.d_iter;
112		}
113	161188	inline const_iterator& operator++(){
114	161188	++d_iter;
115	161188	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	161206	inline const T& operator*() const{
123	161206	const HElement* he = *d_iter;
124	161206	return he->d_elem;
125		}
126
127		};/* BinaryHeap<>::const_iterator */
128
129		typedef const_iterator iterator;
130
131	2490093	inline size_t size() const { return d_heap.size(); }
132	2499177	inline bool empty() const { return d_heap.empty(); }
133
134	153804	inline const_iterator begin() const {
135	153804	return const_iterator(d_heap.begin());
136		}
137
138	153804	inline const_iterator end() const {
139	153804	return const_iterator(d_heap.end());
140		}
141
142	761638	void clear(){
143	761638	typename ElementVector::iterator i=d_heap.begin(), iend=d_heap.end();
144	1264352	for(; i!=iend; ++i){
145	251357	HElement* he = *i;
146	251357	delete he;
147		}
148	761638	d_heap.clear();
149	761638	}
150
151	153780	void swap(BinaryHeap& heap){
152	153780	std::swap(d_heap, heap.d_heap);
153	153780	std::swap(d_cmp, heap.d_cmp);
154	153780	}
155
156	573067	handle push(const T& toAdded){
157	573067	Assert(size() < MAX_SIZE);
158	573067	HElement* he = new HElement(size(), toAdded);
159	573067	d_heap.push_back(he);
160	573067	up_heap(he);
161	573067	return handle(he);
162		}
163
164	297700	void erase(handle h){
165	297700	Assert(!empty());
166	297700	Assert(debugHandle(h));
167
168	297700	HElement* he = h.d_pointer;
169	297700	size_t pos = he->d_pos;
170	297700	if(pos == root()){
171		// the top element can be efficiently removed by pop
172	185532	pop();
173	112168	}else if(pos == last()){
174		// the last element can be safely removed
175	33684	d_heap.pop_back();
176	33684	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	78484	swapIndices(pos, last());
183	78484	d_heap.pop_back();
184	78484	delete he;
185	78484	update(handle(d_heap[pos]));
186		}
187	297700	}
188
189	209542	void pop(){
190	209542	Assert(!empty());
191	209542	swapIndices(root(), last());
192	209542	HElement* b = d_heap.back();
193	209542	d_heap.pop_back();
194	209542	delete b;
195
196	209542	if(!empty()){
197	130469	down_heap(d_heap.front());
198		}
199	209542	}
200
201	241562	const T& top() const {
202	241562	Assert(!empty());
203	241562	return (d_heap.front())->d_elem;
204		}
205
206		private:
207	198679	void update(handle h){
208	198679	Assert(!empty());
209	198679	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	198679	Assert(!empty());
216	198679	HElement* he = h.d_pointer;
217
218	198679	size_t pos = he->d_pos;
219	198679	if(pos == root()){
220		// no parent
221	4667	down_heap(he);
222		}else{
223	194012	size_t par = parent(pos);
224	194012	HElement* at_parent = d_heap[par];
225	194012	if(gt(he->d_elem, at_parent->d_elem)){
226		// he > parent
227	23583	up_heap(he);
228		}else{
229	170429	down_heap(he);
230		}
231		}
232	198679	}
233
234		public:
235	120195	void update(handle h, const T& val){
236	120195	Assert(!empty());
237	120195	Assert(debugHandle(h));
238	120195	h.d_pointer->d_elem = val;
239	120195	update(h);
240	120195	}
241
242		/** (std::numeric_limits<size_t>::max()-2)/2; */
243		static const size_t MAX_SIZE;
244
245		private:
246	843552	inline bool gt(const T& a, const T& b) const{
247		// cmp acts like an operator<
248	843552	return d_cmp(b, a);
249		}
250
251	944348	inline bool lt(const T& a, const T& b) const{
252	944348	return d_cmp(a, b);
253		}
254
255	843552	inline static size_t parent(size_t p){
256	843552	Assert(p != root());
257	843552	return (p-1)/2;
258		}
259	699969	inline static size_t right(size_t p){ return 2*p+2; }
260	756663	inline static size_t left(size_t p){ return 2*p+1; }
261	2493891	inline static size_t root(){ return 0; }
262	400194	inline size_t last() const{
263	400194	Assert(!empty());
264	400194	return size() - 1;
265		}
266
267	288026	inline void swapIndices(size_t i, size_t j){
268	288026	HElement* at_i = d_heap[i];
269	288026	HElement* at_j = d_heap[j];
270	288026	swap(i,j,at_i,at_j);
271	288026	}
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	1046177	inline void swap(size_t i, size_t j, HElement* at_i, HElement* at_j){
281		// still works if i == j
282	1046177	Assert(i == at_i->d_pos);
283	1046177	Assert(j == at_j->d_pos);
284	1046177	d_heap[i] = at_j;
285	1046177	d_heap[j] = at_i;
286	1046177	at_i->d_pos = j;
287	1046177	at_j->d_pos = i;
288	1046177	}
289
290	596650	void up_heap(HElement* he){
291	596650	const size_t& curr = he->d_pos;
292		// The value of curr changes implicitly during swap operations.
293	1292186	while(curr != root()){
294		// he->d_elem > parent
295	649540	size_t par = parent(curr);
296	649540	HElement* at_parent = d_heap[par];
297	649540	if(gt(he->d_elem, at_parent->d_elem)){
298	347768	swap(curr, par, he, at_parent);
299		}else{
300	301772	break;
301		}
302		}
303	596650	}
304
305	305565	void down_heap(HElement* he){
306	305565	const size_t& curr = he->d_pos;
307		// The value of curr changes implicitly during swap operations.
308	305565	size_t N = size();
309		size_t r, l;
310
311	1094373	while((r = right(curr)) < N){
312	451098	l = left(curr);
313
314		// if at_left == at_right, favor left
315	451098	HElement* at_left = d_heap[l];
316	451098	HElement* at_right = d_heap[r];
317	451098	if(lt(he->d_elem, at_left->d_elem)){
318		// he < at_left
319	376991	if(lt(at_left->d_elem, at_right->d_elem)){
320		// he < at_left < at_right
321	167116	swap(curr, r, he, at_right);
322		}else{
323		// he < at_left
324		// at_right <= at_left
325	209875	swap(curr, l, he, at_left);
326		}
327		}else{
328		// at_left <= he
329	74107	if(lt(he->d_elem, at_right->d_elem)){
330		// at_left <= he < at_right
331	17413	swap(curr, r, he, at_right);
332		}else{
333		// at_left <= he
334		// at_right <= he
335	56694	break;
336		}
337		}
338		}
339	305565	l = left(curr);
340	305565	if(r >= N && l < N){
341		// there is a left but not a right
342	42152	HElement* at_left = d_heap[l];
343	42152	if(lt(he->d_elem, at_left->d_elem)){
344		// he < at_left
345	15979	swap(curr, l, he, at_left);
346		}
347		}
348	305565	}
349
350	616574	bool debugHandle(handle h) const{
351	616574	HElement* he = h.d_pointer;
352	616574	if( he == NULL ){
353		return true;
354	616574	}else if(he->d_pos >= size()){
355		return false;
356		}else{
357	616574	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 */