Head

GCC Code Coverage Report

Directory:	.		Exec	Total	Coverage
File:	src/prop/minisat/mtl/Heap.h	Lines:	69	77	89.6 %
Date:	2021-08-11	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 Minisat_Heap_h
#define Minisat_Heap_h

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

namespace cvc5 {
namespace Minisat {

//=================================================================================================
// 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 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 Minisat_Heap_h
22		#define Minisat_Heap_h
23
24		#include "base/check.h"
25		#include "prop/minisat/mtl/Vec.h"
26
27		namespace cvc5 {
28		namespace Minisat {
29
30		//=================================================================================================
31		// A heap implementation with support for decrease/increase key.
32
33
34		template<class Comp>
35	19836	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	66053442	static inline int left (int i) { return i*2+1; }
42	59483899	static inline int right (int i) { return (i+1)*2; }
43	103827958	static inline int parent(int i) { return (i-1) >> 1; }
44
45
46	53359452	void percolateUp(int i)
47		{
48	53359452	int x = heap[i];
49	53359452	int p = parent(i);
50
51	154296464	while (i != 0 && lt(x, heap[p])){
52	50468506	heap[i] = heap[p];
53	50468506	indices[heap[p]] = i;
54	50468506	i = p;
55	50468506	p = parent(p);
56		}
57	53359452	heap [i] = x;
58	53359452	indices[x] = i;
59	53359452	}
60
61
62	7995263	void percolateDown(int i)
63		{
64	7995263	int x = heap[i];
65	46865035	while (left(i) < heap.size()){
66	24660792	int child = right(i) < heap.size() && lt(heap[right(i)], heap[left(i)]) ? right(i) : left(i);
67	24660792	if (!lt(heap[child], x)) break;
68	19434886	heap[i] = heap[child];
69	19434886	indices[heap[i]] = i;
70	19434886	i = child;
71		}
72	7995263	heap [i] = x;
73	7995263	indices[x] = i;
74	7995263	}
75
76
77		public:
78	19836	Heap(const Comp& c) : lt(c) { }
79
80	883	int size () const { return heap.size(); }
81	4831213	bool empty () const { return heap.size() == 0; }
82	235262481	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	46676576	void decrease(int n)
90		{
91	46676576	Assert(inHeap(n));
92	46676576	percolateUp(indices[n]);
93	46676576	}
94	1570576	void increase(int n)
95		{
96	1570576	Assert(inHeap(n));
97	1570576	percolateDown(indices[n]);
98	1570576	}
99
100		// Safe variant of insert/decrease/increase:
101	690824	void update(int n)
102		{
103	690824	if (!inHeap(n))
104	13073	insert(n);
105		else {
106	677751	percolateUp(indices[n]);
107	677751	percolateDown(indices[n]); }
108	690824	}
109
110
111	6005125	void insert(int n)
112		{
113	6005125	indices.growTo(n+1, -1);
114	6005125	Assert(!inHeap(n));
115
116	6005125	indices[n] = heap.size();
117	6005125	heap.push(n);
118	6005125	percolateUp(indices[n]);
119	6005125	}
120
121
122	4755650	int removeMin()
123		{
124	4755650	int x = heap[0];
125	4755650	heap[0] = heap.last();
126	4755650	indices[heap[0]] = 0;
127	4755650	indices[x] = -1;
128	4755650	heap.pop();
129	4755650	if (heap.size() > 1) percolateDown(0);
130	4755650	return x;
131		}
132
133
134		// Rebuild the heap from scratch, using the elements in 'ns':
135	18063	void build(vec<int>& ns) {
136	2295110	for (int i = 0; i < heap.size(); i++)
137	2277047	indices[heap[i]] = -1;
138	18063	heap.clear();
139
140	2082901	for (int i = 0; i < ns.size(); i++){
141	2064838	indices[ns[i]] = i;
142	2064838	heap.push(ns[i]); }
143
144	1047261	for (int i = heap.size() / 2 - 1; i >= 0; i--)
145	1029198	percolateDown(i);
146	18063	}
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		}
159		} // namespace cvc5
160
161		#endif