Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/prop/bvminisat/mtl/Heap.h	Lines:	69	77	89.6 %
Date:	2021-05-22	Branches:	35	124	28.2 %


/******************************************************************************************[Heap.h]
Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
Copyright (c) 2007-2010, Niklas Sorensson

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
associated documentation files (the "Software"), to deal in the Software without restriction,
including without limitation the rights to use, copy, modify, merge, publish, distribute,
sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or
substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
**************************************************************************************************/

#ifndef BVMinisat_Heap_h
#define BVMinisat_Heap_h

#include "base/check.h"
#include "prop/bvminisat/mtl/Vec.h"

namespace cvc5 {
namespace BVMinisat {

//=================================================================================================
// A heap implementation with support for decrease/increase key.


template<class Comp>
class Heap {
    Comp     lt;       // The heap is a minimum-heap with respect to this comparator
    vec<int> heap;     // Heap of integers
    vec<int> indices;  // Each integers position (index) in the Heap

    // Index "traversal" functions
    static inline int left  (int i) { return i*2+1; }
    static inline int right (int i) { return (i+1)*2; }
    static inline int parent(int i) { return (i-1) >> 1; }


    void percolateUp(int i)
    {
        int x  = heap[i];
        int p  = parent(i);

        while (i != 0 && lt(x, heap[p])){
            heap[i]          = heap[p];
            indices[heap[p]] = i;
            i                = p;
            p                = parent(p);
        }
        heap   [i] = x;
        indices[x] = i;
    }


    void percolateDown(int i)
    {
        int x = heap[i];
        while (left(i) < heap.size()){
            int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i);
            if (!lt(heap[child], x)) break;
            heap[i]          = heap[child];
            indices[heap[i]] = i;
            i                = child;
        }
        heap   [i] = x;
        indices[x] = i;
    }


  public:
    Heap(const Comp& c) : lt(c) { }

    int  size      ()          const { return heap.size(); }
    bool empty     ()          const { return heap.size() == 0; }
    bool inHeap    (int n)     const { return n < indices.size() && indices[n] >= 0; }
    int operator[](int index) const
    {
      Assert(index < heap.size());
      return heap[index];
    }

    void decrease(int n)
    {
      Assert(inHeap(n));
      percolateUp(indices[n]);
    }
    void increase(int n)
    {
      Assert(inHeap(n));
      percolateDown(indices[n]);
    }

    // Safe variant of insert/decrease/increase:
    void update(int n)
    {
        if (!inHeap(n))
            insert(n);
        else {
            percolateUp(indices[n]);
            percolateDown(indices[n]); }
    }


    void insert(int n)
    {
        indices.growTo(n+1, -1);
        Assert(!inHeap(n));

        indices[n] = heap.size();
        heap.push(n);
        percolateUp(indices[n]);
    }


    int  removeMin()
    {
        int x            = heap[0];
        heap[0]          = heap.last();
        indices[heap[0]] = 0;
        indices[x]       = -1;
        heap.pop();
        if (heap.size() > 1) percolateDown(0);
        return x;
    }


    // Rebuild the heap from scratch, using the elements in 'ns':
    void build(vec<int>& ns) {
        for (int i = 0; i < heap.size(); i++)
            indices[heap[i]] = -1;
        heap.clear();

        for (int i = 0; i < ns.size(); i++){
            indices[ns[i]] = i;
            heap.push(ns[i]); }

        for (int i = heap.size() / 2 - 1; i >= 0; i--)
            percolateDown(i);
    }

    void clear(bool dealloc = false)
    {
        for (int i = 0; i < heap.size(); i++)
            indices[heap[i]] = -1;
        heap.clear(dealloc);
    }
};


//=================================================================================================
}  // namespace BVMinisat
}  // namespace cvc5

#endif


Generated by: GCOVR (Version 3.2)

Line	Exec	Source
1		/******************************************************************************************[Heap.h]
2		Copyright (c) 2003-2006, Niklas Een, Niklas Sorensson
3		Copyright (c) 2007-2010, Niklas Sorensson
4
5		Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
6		associated documentation files (the "Software"), to deal in the Software without restriction,
7		including without limitation the rights to use, copy, modify, merge, publish, distribute,
8		sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
9		furnished to do so, subject to the following conditions:
10
11		The above copyright notice and this permission notice shall be included in all copies or
12		substantial portions of the Software.
13
14		THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
15		NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
16		NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
17		DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT
18		OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
19		**************************************************************************************************/
20
21		#ifndef BVMinisat_Heap_h
22		#define BVMinisat_Heap_h
23
24		#include "base/check.h"
25		#include "prop/bvminisat/mtl/Vec.h"
26
27		namespace cvc5 {
28		namespace BVMinisat {
29
30		//=================================================================================================
31		// A heap implementation with support for decrease/increase key.
32
33
34		template<class Comp>
35	18844	class Heap {
36		Comp lt; // The heap is a minimum-heap with respect to this comparator
37		vec<int> heap; // Heap of integers
38		vec<int> indices; // Each integers position (index) in the Heap
39
40		// Index "traversal" functions
41	638480904	static inline int left (int i) { return i*2+1; }
42	592563868	static inline int right (int i) { return (i+1)*2; }
43	210374396	static inline int parent(int i) { return (i-1) >> 1; }
44
45
46	61785600	void percolateUp(int i)
47		{
48	61785600	int x = heap[i];
49	61785600	int p = parent(i);
50
51	358963192	while (i != 0 && lt(x, heap[p])){
52	148588796	heap[i] = heap[p];
53	148588796	indices[heap[p]] = i;
54	148588796	i = p;
55	148588796	p = parent(p);
56		}
57	61785600	heap [i] = x;
58	61785600	indices[x] = i;
59	61785600	}
60
61
62	55513391	void percolateDown(int i)
63		{
64	55513391	int x = heap[i];
65	465718009	while (left(i) < heap.size()){
66	242913876	int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i);
67	242913876	if (!lt(heap[child], x)) break;
68	205102309	heap[i] = heap[child];
69	205102309	indices[heap[i]] = i;
70	205102309	i = child;
71		}
72	55513391	heap [i] = x;
73	55513391	indices[x] = i;
74	55513391	}
75
76
77		public:
78	18844	Heap(const Comp& c) : lt(c) { }
79
80	5966	int size () const { return heap.size(); }
81	33955619	bool empty () const { return heap.size() == 0; }
82	422199033	bool inHeap (int n) const { return n < indices.size() && indices[n] >= 0; }
83		int operator[](int index) const
84		{
85		Assert(index < heap.size());
86		return heap[index];
87		}
88
89	25177673	void decrease(int n)
90		{
91	25177673	Assert(inHeap(n));
92	25177673	percolateUp(indices[n]);
93	25177673	}
94	20514166	void increase(int n)
95		{
96	20514166	Assert(inHeap(n));
97	20514166	percolateDown(indices[n]);
98	20514166	}
99
100		// Safe variant of insert/decrease/increase:
101	178363	void update(int n)
102		{
103	178363	if (!inHeap(n))
104	851	insert(n);
105		else {
106	177512	percolateUp(indices[n]);
107	177512	percolateDown(indices[n]); }
108	178363	}
109
110
111	36430415	void insert(int n)
112		{
113	36430415	indices.growTo(n+1, -1);
114	36430415	Assert(!inHeap(n));
115
116	36430415	indices[n] = heap.size();
117	36430415	heap.push(n);
118	36430415	percolateUp(indices[n]);
119	36430415	}
120
121
122	33944723	int removeMin()
123		{
124	33944723	int x = heap[0];
125	33944723	heap[0] = heap.last();
126	33944723	indices[heap[0]] = 0;
127	33944723	indices[x] = -1;
128	33944723	heap.pop();
129	33944723	if (heap.size() > 1) percolateDown(0);
130	33944723	return x;
131		}
132
133
134		// Rebuild the heap from scratch, using the elements in 'ns':
135	1623	void build(vec<int>& ns) {
136	1801461	for (int i = 0; i < heap.size(); i++)
137	1799838	indices[heap[i]] = -1;
138	1623	heap.clear();
139
140	1797813	for (int i = 0; i < ns.size(); i++){
141	1796190	indices[ns[i]] = i;
142	1796190	heap.push(ns[i]); }
143
144	899361	for (int i = heap.size() / 2 - 1; i >= 0; i--)
145	897738	percolateDown(i);
146	1623	}
147
148		void clear(bool dealloc = false)
149		{
150		for (int i = 0; i < heap.size(); i++)
151		indices[heap[i]] = -1;
152		heap.clear(dealloc);
153		}
154		};
155
156
157		//=================================================================================================
158		} // namespace BVMinisat
159		} // namespace cvc5
160
161		#endif