FibonacciHeap.h

Go to the documentation of this file.

/*
 * 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 3 of the License, or
 * (at your option) any later version.
 *
 * Written (W) 2011 Evgeniy Andreev (gsomix)
 *
 * Copyright (C) 2011 Berlin Institute of Technology and Max-Planck-Society
 */

#ifndef FIBONACCI_H_
#define FIBONACCI_H_

#include <shogun/base/SGObject.h>
#include <shogun/lib/common.h>
#include <shogun/mathematics/Math.h>

namespace shogun
{

#ifndef DOXYGEN_SHOULD_SKIP_THIS
struct FibonacciHeapNode
{
    FibonacciHeapNode* parent;

    FibonacciHeapNode* child;

    FibonacciHeapNode* left;

    FibonacciHeapNode* right;

    int32_t rank;

    bool marked;

    int32_t index;

    float64_t key;
};

class CFibonacciHeap: public CSGObject
{
public:

    CFibonacciHeap();

    CFibonacciHeap(int32_t capacity);

    virtual inline const char* get_name() const
    {
        return "FibonacciHeap";
    }

    virtual ~CFibonacciHeap();


    int32_t get_num_nodes() const
    {
        return num_nodes;
    }

    int32_t get_num_trees()
    {
        return num_trees;
    }

    int32_t get_capacity()
    {
        return max_num_nodes;
    }

    void insert(int32_t index, float64_t key);

    int32_t extract_min(float64_t &ret_key);

    void clear();

    int32_t get_key(int32_t index, float64_t &ret_key);

    void decrease_key(int32_t index, float64_t key);

    void debug_print();

private:
    void add_to_roots(FibonacciHeapNode *up_node);

    void consolidate();

    void link_nodes(FibonacciHeapNode *right, FibonacciHeapNode *left);

    void clear_node(int32_t index);

    void cut(FibonacciHeapNode *child, FibonacciHeapNode *parent);

    void cascading_cut(FibonacciHeapNode* tree);

protected:
    FibonacciHeapNode* min_root;

    FibonacciHeapNode** nodes;

    int32_t num_nodes;

    int32_t num_trees;

    int32_t max_num_nodes;

    FibonacciHeapNode **A;

    int32_t Dn;
};
#endif /* DOXYGEN_SHOULD_SKIP_THIS */

}
#endif /* FIBONACCI_H_ */