Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/util/bin_heap.h	Lines:	163	165	98.8 %
Date:	2021-09-18	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	640885	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	187505	BinaryHeap(const CmpFcn& c = CmpFcn())
68		: d_heap()
69	187505	, d_cmp(c)
70	187505	{}
71
72	187502	~BinaryHeap(){
73	187502	clear();
74	187502	}
75
76		class handle {
77		private:
78		HElement* d_pointer;
79	726264	handle(HElement* p) : d_pointer(p){}
80		friend class BinaryHeap;
81		public:
82	1006213	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	355170	const_iterator(const typename ElementVector::const_iterator& iter)
103	355170	: d_iter(iter)
104	355170	{}
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	364171	inline bool operator!=(const const_iterator& ci) const{
111	364171	return d_iter != ci.d_iter;
112		}
113	186592	inline const_iterator& operator++(){
114	186592	++d_iter;
115	186592	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	186610	inline const T& operator*() const{
123	186610	const HElement* he = *d_iter;
124	186610	return he->d_elem;
125		}
126
127		};/* BinaryHeap<>::const_iterator */
128
129		typedef const_iterator iterator;
130
131	2741742	inline size_t size() const { return d_heap.size(); }
132	2722985	inline bool empty() const { return d_heap.empty(); }
133
134	177585	inline const_iterator begin() const {
135	177585	return const_iterator(d_heap.begin());
136		}
137
138	177585	inline const_iterator end() const {
139	177585	return const_iterator(d_heap.end());
140		}
141
142	990022	void clear(){
143	990022	typename ElementVector::iterator i=d_heap.begin(), iend=d_heap.end();
144	1578462	for(; i!=iend; ++i){
145	294220	HElement* he = *i;
146	294220	delete he;
147		}
148	990022	d_heap.clear();
149	990022	}
150
151	177561	void swap(BinaryHeap& heap){
152	177561	std::swap(d_heap, heap.d_heap);
153	177561	std::swap(d_cmp, heap.d_cmp);
154	177561	}
155
156	640885	handle push(const T& toAdded){
157	640885	Assert(size() < MAX_SIZE);
158	640885	HElement* he = new HElement(size(), toAdded);
159	640885	d_heap.push_back(he);
160	640885	up_heap(he);
161	640885	return handle(he);
162		}
163
164	322655	void erase(handle h){
165	322655	Assert(!empty());
166	322655	Assert(debugHandle(h));
167
168	322655	HElement* he = h.d_pointer;
169	322655	size_t pos = he->d_pos;
170	322655	if(pos == root()){
171		// the top element can be efficiently removed by pop
172	200292	pop();
173	122363	}else if(pos == last()){
174		// the last element can be safely removed
175	36984	d_heap.pop_back();
176	36984	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	85379	swapIndices(pos, last());
183	85379	d_heap.pop_back();
184	85379	delete he;
185	85379	update(handle(d_heap[pos]));
186		}
187	322655	}
188
189	224302	void pop(){
190	224302	Assert(!empty());
191	224302	swapIndices(root(), last());
192	224302	HElement* b = d_heap.back();
193	224302	d_heap.pop_back();
194	224302	delete b;
195
196	224302	if(!empty()){
197	134854	down_heap(d_heap.front());
198		}
199	224302	}
200
201	258116	const T& top() const {
202	258116	Assert(!empty());
203	258116	return (d_heap.front())->d_elem;
204		}
205
206		private:
207	220890	void update(handle h){
208	220890	Assert(!empty());
209	220890	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	220890	Assert(!empty());
216	220890	HElement* he = h.d_pointer;
217
218	220890	size_t pos = he->d_pos;
219	220890	if(pos == root()){
220		// no parent
221	5066	down_heap(he);
222		}else{
223	215824	size_t par = parent(pos);
224	215824	HElement* at_parent = d_heap[par];
225	215824	if(gt(he->d_elem, at_parent->d_elem)){
226		// he > parent
227	28498	up_heap(he);
228		}else{
229	187326	down_heap(he);
230		}
231		}
232	220890	}
233
234		public:
235	135511	void update(handle h, const T& val){
236	135511	Assert(!empty());
237	135511	Assert(debugHandle(h));
238	135511	h.d_pointer->d_elem = val;
239	135511	update(h);
240	135511	}
241
242		/** (std::numeric_limits<size_t>::max()-2)/2; */
243		static const size_t MAX_SIZE;
244
245		private:
246	940982	inline bool gt(const T& a, const T& b) const{
247		// cmp acts like an operator<
248	940982	return d_cmp(b, a);
249		}
250
251	972617	inline bool lt(const T& a, const T& b) const{
252	972617	return d_cmp(a, b);
253		}
254
255	940982	inline static size_t parent(size_t p){
256	940982	Assert(p != root());
257	940982	return (p-1)/2;
258		}
259	731237	inline static size_t right(size_t p){ return 2*p+2; }
260	791522	inline static size_t left(size_t p){ return 2*p+1; }
261	2765696	inline static size_t root(){ return 0; }
262	432044	inline size_t last() const{
263	432044	Assert(!empty());
264	432044	return size() - 1;
265		}
266
267	309681	inline void swapIndices(size_t i, size_t j){
268	309681	HElement* at_i = d_heap[i];
269	309681	HElement* at_j = d_heap[j];
270	309681	swap(i,j,at_i,at_j);
271	309681	}
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	1117694	inline void swap(size_t i, size_t j, HElement* at_i, HElement* at_j){
281		// still works if i == j
282	1117694	Assert(i == at_i->d_pos);
283	1117694	Assert(j == at_j->d_pos);
284	1117694	d_heap[i] = at_j;
285	1117694	d_heap[j] = at_i;
286	1117694	at_i->d_pos = j;
287	1117694	at_j->d_pos = i;
288	1117694	}
289
290	669383	void up_heap(HElement* he){
291	669383	const size_t& curr = he->d_pos;
292		// The value of curr changes implicitly during swap operations.
293	1444351	while(curr != root()){
294		// he->d_elem > parent
295	725158	size_t par = parent(curr);
296	725158	HElement* at_parent = d_heap[par];
297	725158	if(gt(he->d_elem, at_parent->d_elem)){
298	387484	swap(curr, par, he, at_parent);
299		}else{
300	337674	break;
301		}
302		}
303	669383	}
304
305	327246	void down_heap(HElement* he){
306	327246	const size_t& curr = he->d_pos;
307		// The value of curr changes implicitly during swap operations.
308	327246	size_t N = size();
309		size_t r, l;
310
311	1135228	while((r = right(curr)) < N){
312	464276	l = left(curr);
313
314		// if at_left == at_right, favor left
315	464276	HElement* at_left = d_heap[l];
316	464276	HElement* at_right = d_heap[r];
317	464276	if(lt(he->d_elem, at_left->d_elem)){
318		// he < at_left
319	385640	if(lt(at_left->d_elem, at_right->d_elem)){
320		// he < at_left < at_right
321	170664	swap(curr, r, he, at_right);
322		}else{
323		// he < at_left
324		// at_right <= at_left
325	214976	swap(curr, l, he, at_left);
326		}
327		}else{
328		// at_left <= he
329	78636	if(lt(he->d_elem, at_right->d_elem)){
330		// at_left <= he < at_right
331	18351	swap(curr, r, he, at_right);
332		}else{
333		// at_left <= he
334		// at_right <= he
335	60285	break;
336		}
337		}
338		}
339	327246	l = left(curr);
340	327246	if(r >= N && l < N){
341		// there is a left but not a right
342	44065	HElement* at_left = d_heap[l];
343	44065	if(lt(he->d_elem, at_left->d_elem)){
344		// he < at_left
345	16538	swap(curr, l, he, at_left);
346		}
347		}
348	327246	}
349
350	679056	bool debugHandle(handle h) const{
351	679056	HElement* he = h.d_pointer;
352	679056	if( he == NULL ){
353		return true;
354	679056	}else if(he->d_pos >= size()){
355		return false;
356		}else{
357	679056	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 */