fibheap.h

Go to the documentation of this file.

// Copyright (C) 1997-2010 by Pawel Pilarczyk.
//
// This file is part of the Homology Library.  This library 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 library 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 software; see the file "license.txt".  If not, write to the
// Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// Started on August 13, 2007. Last revision: January 23, 2010.


#ifndef _CHOMP_STRUCT_FIBHEAP_H_
#define _CHOMP_STRUCT_FIBHEAP_H_


#include "chomp/struct/multitab.h"
//#include "chomp/struct/pool.h"


namespace chomp {
namespace homology {


// --------------------------------------------------
// ----------------- FIBONACCI HEAP -----------------
// --------------------------------------------------

template <class element>
class FibonacciHeap
{
public:
        typedef int_t NodePtr;

        static const int_t NullPtr;

private:
        struct Node
        {
                element key;

                bool mark;

                int_t degree;

                int_t number;

                NodePtr parent;

                NodePtr child;

                NodePtr left;

                NodePtr right;
        };

public:
        FibonacciHeap (int_t maxSize = 0);

        ~FibonacciHeap ();

        int_t Insert (const element &value);

        int_t Minimum () const;

        const element &Value (int_t number) const;

        // Adds another heap to this one. Destroys the other one.
        // WARNING: Because of the node memory allocation strategy used
        // in this implementation of Fibonacci heaps, the complexity
        // of computing the union is O(n) instead of O(1).
        // Even worse, this operation is not yet implemented... Sorry!
//      void Union (FibonacciHeap<element> &h);

        element ExtractMinimum ();

        void DecreaseKey (int_t number, const element &value);

        void Delete (int_t number);

private:
        FibonacciHeap (const FibonacciHeap<element> &);

        FibonacciHeap<element> &operator = (const FibonacciHeap<element> &);

        NodePtr minRoot;

        int_t nodeCount;

        multitable<Node> nodes;

        element minValue;

        // The pool of nodes used for the Fibonacci heap.
//      static pool<typename FibonacciHeap<element>::Node> *p;

        // The number of Fibonacci heaps in use.
//      static int_t heapsInUse;

        void Consolidate ();

        multitable<NodePtr> auxArray;

        int_t arrayPrepared;

        void Cut (const typename FibonacciHeap<element>::NodePtr &x,
                const typename FibonacciHeap<element>::NodePtr &y);

        void CascadingCut (typename FibonacciHeap<element>::NodePtr y);

        void showGraph (std::ostream &out, int_t depth,
                const typename FibonacciHeap<element>::NodePtr &x) const;

public:
        friend inline std::ostream &operator << (std::ostream &out,
                const FibonacciHeap<element> &h)
        {
                out << "Fibonacci heap (min root = " << h. minRoot << "):\n";
                NodePtr rootPtr = h. minRoot;
                if (rootPtr == NullPtr)
                        return out;
                do
                {
                        h. showGraph (out, 0, rootPtr);
                        rootPtr = h. nodes [rootPtr]. right;
                } while (rootPtr != h. minRoot);
                return out;
        } /* operator << */

}; /* class FibonacciHeap */

template <class element>
const int_t FibonacciHeap<element>::NullPtr (-1);

//template <class element>
//pool<typename FibonacciHeap<element>::Node> *FibonacciHeap<element>::p = 0;

//template <class element>
//int_t FibonacciHeap<element>::heapsInUse = 0;

// --------------------------------------------------

template <class element>
void FibonacciHeap<element>::showGraph (std::ostream &out, int_t depth,
        const typename FibonacciHeap<element>::NodePtr &x) const
{
        // show this node
        for (int_t i = 0; i < depth; ++ i)
                out << "|   ";
        out << "+-- [" << nodes [x]. number << ": " << nodes [x]. key << "]";
        if (nodes [x]. left != NullPtr)
                out << " left=" << nodes [x]. left;
        if (nodes [x]. right != NullPtr)
                out << " right=" << nodes [x]. right;
        if (nodes [x]. parent != NullPtr)
                out << " parent=" << nodes [x]. parent;
        if (nodes [x]. child != NullPtr)
                out << " child=" << nodes [x]. child;
        out << " deg=" << nodes [x]. degree << "\n";

        // show all the children trees
        NodePtr child = nodes [x]. child;
        if (child == NullPtr)
                return;
        do
        {
                showGraph (out, depth + 1, child);
                child = nodes [child]. right;
        } while (child != nodes [x]. child);
        return;
} /* FibonacciHeap::showGraph */

template <class element>
inline FibonacciHeap<element>::FibonacciHeap (int_t maxSize):
        minRoot (NullPtr), nodeCount (0), nodes (maxSize), arrayPrepared (0)
{
        // allocate a new pool for elements if this is the first heap
//      if (!heapsInUse)
//              p = new pool<typename FibonacciHeap<element>::Node>;

        // increase the number of heaps in use
//      ++ heapsInUse;

        return;
} /* FibonacciHeap::FibonacciHeap */

template <class element>
inline FibonacciHeap<element>::~FibonacciHeap ()
{
        // decrease the number of heaps in use
//      -- heapsInUse;

        // delete the pool for elements if this was the last heap
//      if (!heapsInUse)
//              delete p;

        return;
} /* FibonacciHeap::~FibonacciHeap */

template <class element>
inline FibonacciHeap<element>::FibonacciHeap (const FibonacciHeap<element> &)
{
        throw "Copy constructor for a Fibonacci heap not implemented.";
        return;
} /* FibonacciHeap::FibonacciHeap */

template <class element>
inline FibonacciHeap<element> &FibonacciHeap<element>::operator =
        (const FibonacciHeap<element> &)
{
        throw "Assignment operator for a Fibonacci heap not implemented.";
        return *this;
} /* FibonacciHeap::operator = */

template <class element>
inline int_t FibonacciHeap<element>::Insert (const element &value)
{
        // allocate memory for the new node
        NodePtr nodePtr = nodeCount;

        // update the minimal value
        if (!nodeCount)
                minValue = value;
        else if (value < minValue)
                minValue = value;

        // fill in the fields of the new node
        Node &node = nodes [nodePtr];
        node. key = value;
        node. mark = false;
        node. degree = 0;
        node. number = nodeCount;
        node. parent = NullPtr;
        node. child = NullPtr;

        // insert the node to the unordered bidirectional list of roots
        if (minRoot == NullPtr)
        {
                node. left = nodePtr;
                node. right = nodePtr;
        }
        else
        {
                node. left = nodes [minRoot]. left;
                node. right = minRoot;
                nodes [node. left]. right = nodePtr;
                nodes [node. right]. left = nodePtr;
        }

        // make a correction to the pointer to the minimal root if necessary
        if ((minRoot == NullPtr) || (value < nodes [minRoot]. key))
                minRoot = nodePtr;

        // return the number of the new node and increase the number of nodes
        return nodeCount ++;
} /* FibonacciHeap::Insert */

template <class element>
inline int_t FibonacciHeap<element>::Minimum () const
{
        return minRoot;
} /* FibonacciHeap::Minimum */

template <class element>
inline const element &FibonacciHeap<element>::Value (int_t number) const
{
        return nodes [number]. key;
} /* FibonacciHeap::Value */

/*
template <class element>
inline void FibonacciHeap<element>::Union (FibonacciHeap<element> &h)
{
        // if the other heap is empty, then do nothing
        if (h. minRoot == NullPtr)
                return;

        // if this heap is empty, then just copy the data
        if (minRoot == NullPtr)
        {
                minRoot = h. minRoot;
                nodeCount = h. nodeCount;
                minValue = h. minValue;
                return;
        }

        // copy the nodes from the other heap to this one and update links
        // TODO

        // join the root lists
        // TODO

        // update the node count
        nodeCount += h. nodeCount;

        // update the minimal key value
        if (h. minValue < minValue)
                minValue = h. minValue;

        // make the other heap empty
        h. minRoot = NullPtr;
        h. nodeCount = 0;
        throw "The union of Fibonacci heaps not implemented, yet.";
        return;
}*/ /* FibonacciHeap::Union */

template <class element>
inline void FibonacciHeap<element>::Consolidate ()
{
        // do nothing if the heap is empty
        if (minRoot == NullPtr)
                return;

        // for each node in the root list of the heap...
        NodePtr node = minRoot;
        int_t maxDegree = 0;
        do
        {
                // take the node for the loop and get its degree
                NodePtr x = node;
                int_t d = nodes [x]. degree;

                // prepare the next node from the root list for the next time
                node = nodes [node]. right;

                // expand the auxiliary array if necessary
                while (arrayPrepared <= d)
                        auxArray [arrayPrepared ++] = NullPtr;

                // update the strict upper limit on the degree used
                if (maxDegree <= d)
                        maxDegree = d + 1;

                // join this tree with another one of the same degree if any
                while (auxArray [d] != NullPtr)
                {
                        // take the node of the same degree as x
                        NodePtr y = auxArray [d];

                        // swap the node pointers if necessary
                        if (nodes [y]. key < nodes [x]. key)
                        {
                                NodePtr tmp = x;
                                x = y;
                                y = tmp;
                        }

                        // clear the mark of the node y
                        nodes [y]. mark = false;

                        // make the node y a child of the node x
                        nodes [y]. parent = x;
                        NodePtr child = nodes [x]. child;
                        if (child == NullPtr)
                        {
                                nodes [x]. child = y;
                                nodes [y]. left = y;
                                nodes [y]. right = y;
                        }
                        else
                        {
                                nodes [y]. left = child;
                                nodes [y]. right = nodes [child]. right;
                                nodes [child]. right = y;
                                nodes [nodes [y]. right]. left = y;
                        }
                        ++ nodes [x]. degree;

                        // clear the entry which stored the node of degree d
                        auxArray [d] = NullPtr;

                        // increase the degree to the degree of x
                        ++ d;

                        // expand the auxiliary array if necessary
                        if (arrayPrepared <= d)
                                auxArray [arrayPrepared ++] = NullPtr;

                        // update the strict upper limit on the degree used
                        if (maxDegree <= d)
                                maxDegree = d + 1;
                }

                // put this node in the array
                auxArray [d] = x;

        } while (node != minRoot);

        // reconstruct the root list from the auxiliary array
        minRoot = NullPtr;
        for (int_t d = 0; d < maxDegree; ++ d)
        {
                // skip entries of the array which don't point to nodes
                if (auxArray [d] == NullPtr)
                        continue;

                // take the node pointer of the array
                NodePtr nodePtr = auxArray [d];
                auxArray [d] = NullPtr;
                Node &node = nodes [nodePtr];

                // link this node to the root list
                if (minRoot == NullPtr)
                {
                        node. left = nodePtr;
                        node. right = nodePtr;
                }
                else
                {
                        node. left = minRoot;
                        node. right = nodes [minRoot]. right;
                        nodes [node. left]. right = nodePtr;
                        nodes [node. right]. left = nodePtr;
                }

                // update the pointer to the minimal root node if necessary
                if ((minRoot == NullPtr) ||
                        (node. key < nodes [minRoot]. key))
                {
                        minRoot = nodePtr;
                }
        }
        return;
} /* FibonacciHeap::Consolidate */

template <class element>
inline element FibonacciHeap<element>::ExtractMinimum ()
{
        // determine the node with the minimum to extract
        NodePtr nodePtr = minRoot;
        Node &node = nodes [minRoot];

        // make the children of the node become root nodes
        // and attach them to the root list
        NodePtr child = node. child;
        if (child != NullPtr)
        {
                // clear the child pointer in the parent
                node. child = NullPtr;

                // clear the parent pointers in the children
                while (nodes [child]. parent != NullPtr)
                {
                        nodes [child]. parent = NullPtr;
                        child = nodes [child]. right;
                }

                // attach the children to the root list
                NodePtr leftChild = child;
                NodePtr rightChild = nodes [child]. right;
                NodePtr leftRoot = nodePtr;
                NodePtr rightRoot = node. right;
                nodes [leftRoot]. right = rightChild;
                nodes [rightRoot]. left = leftChild;
                nodes [leftChild]. right = rightRoot;
                nodes [rightChild]. left = leftRoot;
        }

        // make the min root pointer point at any other node
        // and remove the node from the root list
        if (node. right != nodePtr)
        {
                minRoot = node. right;
                nodes [minRoot]. left = node. left;
                nodes [node. left]. right = minRoot;
        }
        else
                minRoot = NullPtr;

        // reset the fields in the node to avoid any confusion in the future
        node. left = NullPtr;
        node. right = NullPtr;
        node. parent = NullPtr;
        node. child = NullPtr;
        node. degree = -1;

        // consolidate the heap
        Consolidate ();

        return node. key;
} /* FibonacciHeap::ExtractMinimum */

template <class element>
inline void FibonacciHeap<element>::Cut
        (const typename FibonacciHeap<element>::NodePtr &x,
        const typename FibonacciHeap<element>::NodePtr &y)
{
        // remove x from the children of y:
        // case 1: if x is the only child of y
        nodes [x]. parent = NullPtr;
        if (nodes [x]. right == x)
        {
                nodes [y]. child = NullPtr;
        }
        //case 2: if there are also other children of y
        else
        {
                NodePtr leftChild = nodes [x]. left;
                NodePtr rightChild = nodes [x]. right;
                nodes [y]. child = rightChild;
                nodes [leftChild]. right = rightChild;
                nodes [rightChild]. left = leftChild;
        }

        // update the degree of y
        -- nodes [y]. degree;

        // add x to the root list of the heap
        NodePtr leftRoot = minRoot;
        NodePtr rightRoot = nodes [minRoot]. right;
        nodes [x]. left = leftRoot;
        nodes [x]. right = rightRoot;
        nodes [leftRoot]. right = x;
        nodes [rightRoot]. left = x;

        // clear the marking of the node x if any
        nodes [x]. mark = false;

        return;
} /* FibonacciHeap::Cut */

template <class element>
inline void FibonacciHeap<element>::CascadingCut
        (typename FibonacciHeap<element>::NodePtr y)
{
        // do the cascading cut while the node has a parent
        while (!(nodes [y]. parent == NullPtr))
        {
                // if this is the first time the node lost its child,
                // then just mark the node and exit the cascading cut
                if (!nodes [y]. mark)
                {
                        nodes [y]. mark = true;
                        return;
                }

                // cut the node and continue the cascading cut
                // with its parent
                NodePtr z = nodes [y]. parent;
                Cut (y, z);
                y = z;
        }
        return;
} /* FibonacciHeap::CascadingCut */

template <class element>
inline void FibonacciHeap<element>::DecreaseKey (int_t number,
        const element &value)
{
        // translate the number to a node pointer
        NodePtr x (number);

        // ignore this action if the node is no longer in the heap
        if (nodes [x]. degree == -1)
                return;

        // update the minimal value in the heap
        if (value < minValue)
                minValue = value;

        // update the value of the node
        nodes [x]. key = value;

        // cut the tree so that the node x is in the root list
        NodePtr y = nodes [x]. parent;
        if ((y != NullPtr) && (value < nodes [y]. key))
        {
                Cut (x, y);
                CascadingCut (y);
        }

        // update the pointer to the minimal node in the root list
        if (value < nodes [minRoot]. key)
                minRoot = x;

        return;
} /* FibonacciHeap::DecreaseKey */

template <class element>
inline void FibonacciHeap<element>::Delete (int_t number)
{
        element value = minValue;
        DecreaseKey (number, value - 1);
        ExtractMinimum ();
        minValue = value;
        return;
} /* FibonacciHeap::Delete */


} // namespace homology
} // namespace chomp

#endif // _CHOMP_STRUCT_FIBHEAP_H_