CTR_UHeap.h

Go to the documentation of this file.

/*
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
 * All rights reserved.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): none yet.
 *
 * ***** END GPL LICENSE BLOCK *****
 */

#ifndef NAN_INCLUDED_CTR_UHeap_h
#define NAN_INCLUDED_CTR_UHeap_h

#include <vector>

#include "MEM_NonCopyable.h"

class CTR_UHeapable {

public :
        int &
    HeapPos(
    ){
        return m_ind;
    };
        float &
    HeapKey(
    ) {
        return m_key;
    };

    const 
        float &
    HeapKey(
    ) const {
        return m_key;
    };

    const 
        int &
    HeapPos(
    ) const {
        return m_ind;
    };

private :

    float m_key;
    int m_ind;

protected :

    CTR_UHeapable(
    ) : m_key (0),
        m_ind (0)
    {
    };

    ~CTR_UHeapable(
    ){
    };
};
    
template <class HeapType>   
class CTR_UHeap : public MEM_NonCopyable
{

public:     

    static
        CTR_UHeap *
    New(
    ) {
        return new CTR_UHeap();
    }

        void
    MakeHeap(
        HeapType *base
    ) {
        int i;
        int start = Parent(m_vector.size()-1);
        for (i = start; i >=0; --i) {
            DownHeap(base,i);
        }
    }; 
    
        void
    Insert(
        HeapType *base,
        int elem
    ) {
        // add element to vector
        m_vector.push_back(elem);
        base[elem].HeapPos() = m_vector.size()-1;

        // push the element up the heap
        UpHeap(base,m_vector.size()-1);
    }

    // access to the vector for initial loading of elements

        std::vector<int> &
    HeapVector(
    ) {
        return m_vector;
    };


        void
    Remove(
        HeapType *base,
        int i
    ) {
    
        // exchange with last element - pop last
        // element and move up or down the heap as appropriate
        if (m_vector.empty()) {
            assert(false);
        }

        if (i  != int(m_vector.size())-1) {
            
            Swap(base,i,m_vector.size() - 1);
            m_vector.pop_back();

            if (!m_vector.empty()) {
                UpHeap(base,i);
                DownHeap(base,i);
            }
        } else {
            m_vector.pop_back();
        }
    }

        int
    Top(
    ) const {
        if (m_vector.empty()) return -1;
        return m_vector[0];
    }
        

        void
    SC_Heap(
        HeapType *base
    ) {
        int i;
        for (i = 1; i < int(m_vector.size()) ; i++) {
            
            CTR_UHeapable * elem = base + m_vector[i];          
            CTR_UHeapable * p_elem = base + m_vector[Parent(i)];            

            assert(p_elem->HeapKey() >= elem->HeapKey());
            assert(elem->HeapPos() == i);
        }

    };
            

    ~CTR_UHeap(
    ) {
    };  


private:

    CTR_UHeap(
    ) {
    };


    std::vector<int> m_vector;
        
private:
        void 
    Swap(
        HeapType *base,
        int i, 
        int j
    ){
        std::swap(m_vector[i],m_vector[j]);
        
        CTR_UHeapable *heap_i = base + m_vector[i];
        CTR_UHeapable *heap_j = base + m_vector[j];
        
        // Exchange heap positions
        heap_i->HeapPos() = i;
        heap_j->HeapPos() = j;
    }

        int 
    Parent(
        unsigned int i
    ) {
        return (i-1) >> 1;
    }
        int 
    Left(
        int i
    ) {
        return (i<<1)+1;
    }

        int 
    Right(
        int i
    ) {
        return (i<<1)+2;
    }

        float
    HeapVal(
        HeapType *base,
        int i
    ) {
        return base[m_vector[i]].HeapKey();
    }

        void
    DownHeap(
        HeapType *base,     
        int i
    ) {
        int heap_size = m_vector.size();

        int l = Left(i);
        int r = Right(i);

        int largest;
        if (l < heap_size && HeapVal(base,l) > HeapVal(base,i)) {
            largest = l;
        } else {
            largest = i;
        }

        if (r < heap_size && HeapVal(base,r) > HeapVal(base,largest)) {
            largest = r;
        }   

        if (largest != i) {
            // exchange i and largest
            Swap(base,i,largest);
            DownHeap(base,largest);
        }
    }

        void
    UpHeap(
        HeapType *base,
        int i
    ) {

        // swap parents untill it's found a place in the heap < it's parent or
        // top of heap

        while (i > 0) {
            int p = Parent(i);
            if (HeapVal(base,i) < HeapVal(base,p)) {
                break;
            }
            Swap(base,p,i);
            i = p;
        }
    }       
};

#endif