Gluco2::Heap< Comp > Class Template Reference

#include <Heap.h>

Public Member Functions
	Heap (const Comp &c)
int	size () const
bool	empty () const
bool	inHeap (int n) const
int	operator[] (int index) const
void	decrease (int n)
void	increase (int n)
void	prelocate (int ext_cap)
void	update (int n)
void	insert (int n)
int	removeMin ()
void	build (vec< int > &ns)
void	clear (bool dealloc=false)
void	clear_ (bool dealloc=false)

Detailed Description

template<class Comp>
class Gluco2::Heap< Comp >

Definition at line 35 of file Heap.h.

Constructor & Destructor Documentation

Heap()

template<class Comp>

Gluco2::Heap< Comp >::Heap ( const Comp & c )

inline

Definition at line 78 of file Heap.h.

: lt(c) { }

Member Function Documentation

build()

template<class Comp>

void Gluco2::Heap< Comp >::build ( vec< int > & ns )

inline

Definition at line 125 of file Heap.h.

                             {
        int i;
        for (i = 0; i < heap.size(); i++)
            indices[heap[i]] = -1;
        heap.clear();
 
        for (i = 0; i < ns.size(); i++){
            indices[ns[i]] = i;
            heap.push(ns[i]); }
 
        for (i = heap.size() / 2 - 1; i >= 0; i--)
            percolateDown(i);
    }

Here is the call graph for this function:

clear()

template<class Comp>

void Gluco2::Heap< Comp >::clear ( bool dealloc = false )

inline

Definition at line 139 of file Heap.h.

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

clear_()

template<class Comp>

void Gluco2::Heap< Comp >::clear_ ( bool dealloc = false )

inline

Definition at line 146 of file Heap.h.

    { 
        int i;
        for (i = 0; i < heap.size(); i++)
            indices[heap[i]] = -1;
 
        if( ! dealloc ) heap.shrink_( heap.size() );
        else            heap.clear(true); 
    }

decrease()

template<class Comp>

void Gluco2::Heap< Comp >::decrease ( int n )

inline

Definition at line 86 of file Heap.h.

{ assert(inHeap(n)); percolateUp  (indices[n]); }

Here is the call graph for this function:

empty()

template<class Comp>

bool Gluco2::Heap< Comp >::empty ( ) const

inline

Definition at line 81 of file Heap.h.

{ return heap.size() == 0; }

increase()

template<class Comp>

void Gluco2::Heap< Comp >::increase ( int n )

inline

Definition at line 87 of file Heap.h.

{ assert(inHeap(n)); percolateDown(indices[n]); }

Here is the call graph for this function:

inHeap()

template<class Comp>

bool Gluco2::Heap< Comp >::inHeap ( int n ) const

inline

Definition at line 82 of file Heap.h.

{ return n < indices.size() && indices[n] >= 0; }

Here is the caller graph for this function:

insert()

template<class Comp>

void Gluco2::Heap< Comp >::insert ( int n )

inline

Definition at line 101 of file Heap.h.

    {
        indices.growTo(n+1, -1);
        assert(!inHeap(n));
 
        indices[n] = heap.size();
        heap.push(n);
        percolateUp(indices[n]); 
    }

Here is the call graph for this function:

Here is the caller graph for this function:

operator[]()

template<class Comp>

int Gluco2::Heap< Comp >::operator[] ( int index ) const

inline

Definition at line 83 of file Heap.h.

{ assert(index < heap.size()); return heap[index]; }

prelocate()

template<class Comp>

void Gluco2::Heap< Comp >::prelocate ( int ext_cap )

inline

Definition at line 88 of file Heap.h.

{ indices.prelocate(ext_cap); }

removeMin()

template<class Comp>

int Gluco2::Heap< Comp >::removeMin ( )

inline

Definition at line 112 of file Heap.h.

    {
        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; 
    }

size()

template<class Comp>

int Gluco2::Heap< Comp >::size ( ) const

inline

Definition at line 80 of file Heap.h.

{ return heap.size(); }

update()

template<class Comp>

void Gluco2::Heap< Comp >::update ( int n )

inline

Definition at line 91 of file Heap.h.

    {
        if (!inHeap(n))
            insert(n);
        else {
            percolateUp(indices[n]);
            percolateDown(indices[n]); }
    }

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• src/sat/glucose2/Heap.h