FastUtils.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/GraphAttributes.h>
 
#ifdef OGDF_SYSTEM_UNIX
#include <sys/time.h>
#endif
 
#ifdef OGDF_FME_KERNEL_USE_SSE
#include <ogdf/basic/internal/intrinsics.h>
#endif
 
namespace ogdf {
namespace fast_multipole_embedder {
 
// use SSE for Multipole computations
//#define OGDF_FME_KERNEL_USE_SSE
 
// simple parallel quadtree sort
//#define OGDF_FME_PARALLEL_QUADTREE_SORT
 
// use SSE for direct interaction (this is slower than the normal direct computation)
//#define OGDF_FME_KERNEL_USE_SSE_DIRECT
 
inline void OGDF_FME_Print_Config()
{
#ifdef OGDF_FME_KERNEL_USE_SSE
    std::cout << "OGDF_FME_KERNEL_USE_SSE" << std::endl;
#endif
#ifdef OGDF_FME_PARALLEL_QUADTREE_SORT
    std::cout << "OGDF_FME_PARALLEL_QUADTREE_SORT" << std::endl;
#endif
#ifdef OGDF_FME_KERNEL_USE_SSE_DIRECT
    std::cout << "OGDF_FME_KERNEL_USE_SSE_DIRECT" << std::endl;
#endif
}
 
using MortonNR = uint64_t;
using CoordInt = uint32_t;
 
template<typename T>
inline bool is_align_16(T* ptr)
{
    return !(((size_t)(void*)ptr) & 0x0F);
}
 
template<typename T>
inline T* align_16_prev_ptr(T* t)
{
    return (T*)(((size_t)((void*)t))&~ 0x0F);
}
 
template<typename T>
inline T* align_16_next_ptr(T* t)
{
    return (T*)((((size_t)((void*)t)) + 15)&~ 0x0F);
}
 
#ifdef OGDF_SYSTEM_UNIX
inline timeval GetDiffTime(timeval _then, double& dtime)
{
    timeval then = (timeval) _then;
    timeval now;
    gettimeofday(&now, nullptr);
    timeval diff;
 
    diff.tv_sec = now.tv_sec - then.tv_sec;
    diff.tv_usec = now.tv_usec - then.tv_usec;
    while(diff.tv_usec < 0)
    {
        diff.tv_sec--;
        diff.tv_usec = 1000000 + now.tv_usec - then.tv_usec;
    }
 
    dtime = (double) diff.tv_sec;
    dtime += (double) diff.tv_usec / 1e6;
 
    return (timeval) now;
}
#endif
 
inline void printProfiledTime(double t, const char* text) { std::cout << t <<"s\t" << text << std::endl; }
inline void printProfiledTime(double t, double sum, const char* text) { std::cout << t <<"s\t" << text << "\t" << (t / sum)*100.0 <<"%"<< std::endl; }
 
#define OGDF_MALLOC_16(s) System::alignedMemoryAlloc16((s))
 
#define OGDF_FREE_16(ptr) System::alignedMemoryFree((ptr))
 
template<typename MNR_T, typename C_T>
inline MNR_T mortonNumber(C_T ix, C_T iy)
{
    MNR_T x = (MNR_T)ix;
    MNR_T y = (MNR_T)iy;
    // bit length of the result
    const unsigned int BIT_LENGTH = static_cast<unsigned int>(sizeof(MNR_T)) << 3;
    // set all bits
    MNR_T mask = 0x0;
    mask = ~mask;
 
    for (unsigned int i = (BIT_LENGTH >> 1);i>0; i = i >> 1) {
        // increase frequency
        mask = mask ^ (mask << i);
        x = (x | (x << i)) & mask;
        y = (y | (y << i)) & mask;
    }
    return x | (y << 1);
}
 
 
template<typename MNR_T, typename C_T>
inline void mortonNumberInv(MNR_T mnr, C_T& x, C_T& y)
{
    // bit length of the coordinates
    unsigned int BIT_LENGTH = static_cast<unsigned int>(sizeof(C_T)) << 3;
    // set least significant bit
    MNR_T mask = 0x1;
    // set coords to zero
    x = y = 0;
    for (unsigned int i=0; i < BIT_LENGTH; i++)
    {
        x = (C_T)(x | (mnr & mask));
        mnr = mnr >> 1;
        y = (C_T)(y | (mnr & mask));
        mask = mask << 1;
    }
}
 
template<typename T>
inline uint32_t mostSignificantBit(T n)
{
    uint32_t BIT_LENGTH = static_cast<uint32_t>(sizeof(T)) << 3;
    T mask = 0x1;
    mask = mask << (BIT_LENGTH - 1);
    for (uint32_t i = 0; i < BIT_LENGTH; i++)
    {
        if (mask & n)
            return i;
        mask = mask >> 1;
    }
    return BIT_LENGTH;
}
 
inline uint32_t prevPowerOfTwo(uint32_t n)
{
    uint32_t msb = 32 - mostSignificantBit(n);
    return 0x1 << (msb - 1);
}
 
class RandomNodeSet
{
public:
    explicit RandomNodeSet(const Graph& G) : m_graph(G) { allocate(); }
 
    ~RandomNodeSet() { deallocate(); }
 
    node chooseNode() const
    {
        int i = m_numNodesChoosen + ogdf::randomNumber(0,nodesLeft()-1);//(int)((double)nodesLeft()*rand()/(RAND_MAX+1.0));
        return m_array[i];
    }
 
    void removeNode(node v)
    {
        int i = m_nodeIndex[v];
        int j = m_numNodesChoosen;
        node w = m_array[j];
        std::swap(m_array[i], m_array[j]);
        m_nodeIndex[w] = i;
        m_nodeIndex[v] = j;
        m_numNodesChoosen++;
    }
 
    bool isAvailable(node v) const { return m_nodeIndex[v] >= m_numNodesChoosen; }
 
    int nodesLeft() const { return m_numNodes - m_numNodesChoosen; }
 
private:
    void allocate()
    {
        m_array = new node[m_graph.numberOfNodes()];
        m_nodeIndex.init(m_graph);
        m_numNodes = m_graph.numberOfNodes();
        m_numNodesChoosen = 0;
        int i = 0;
        for(node v : m_graph.nodes)
        {
            m_array[i] = v;
            m_nodeIndex[v] = i;
            i++;
        }
    }
 
    void deallocate()
    {
        delete[] m_array;
    }
 
    const Graph& m_graph;
 
    node* m_array;
 
    NodeArray<int> m_nodeIndex;
 
    int m_numNodes;
 
    int m_numNodesChoosen;
};
 
inline void gridGraph(Graph& G, int n, int m)
{
    G.clear();
    node v;
    node* topRow = new node[m];
    topRow[0] = G.newNode();
    for (int j=1; j<m; j++)
    {
        topRow[j] = G.newNode();
        G.newEdge(topRow[j-1], topRow[j]);
    }
    for (int i=1; i<n; i++)
    {
        v = G.newNode();
        G.newEdge(topRow[0], v);
        topRow[0] = v;
        for (int j=1; j<m; j++)
        {
            v = G.newNode();
            G.newEdge(topRow[j-1], v);
            G.newEdge(topRow[j], v);
            topRow[j] = v;
        }
    }
    delete[] topRow;
}
 
inline void randomGridGraph(Graph& G, int n, int m, double missinNodesPercentage = 0.03)
{
    gridGraph(G, n, m);
    int numberOfNodesToDelete = (int)((double)G.numberOfNodes() * missinNodesPercentage);
 
    RandomNodeSet rndSet(G);
    for(int i=0; i<numberOfNodesToDelete;i++)
    {
        node v = rndSet.chooseNode();
        rndSet.removeNode(v);
        G.delNode(v);
    }
}
 
template<class TYP>
class BinCoeff
{
public:
    explicit BinCoeff(unsigned int n) : m_max_n(n) {    init_array(); }
 
    ~BinCoeff() { free_array(); }
 
    void init_array()
    {
        using ptr = TYP*;
        unsigned int i,j;
        m_binCoeffs = new ptr[m_max_n+1];
        for(i = 0;i<= m_max_n ;i++)
        {
            m_binCoeffs[i]=  new TYP[i+1];
        }
 
        //Pascalsches Dreieck
        for (i = 0; i <= m_max_n;i++)
        {
            m_binCoeffs[i][0] = m_binCoeffs[i][i] = 1;
        }
 
        for (i = 2; i <= m_max_n; i ++)
        {
            for (j = 1; j < i; j++)
            {
                m_binCoeffs[i][j] = m_binCoeffs[i-1][j-1]+m_binCoeffs[i-1][j];
            }
        }
    }
 
    void free_array()
    {
        unsigned int i;
        for(i = 0;i<= m_max_n;i++)
        {
            delete[] m_binCoeffs[i];
        }
        delete[] m_binCoeffs;
    }
 
    //Returns n over k.
    inline TYP value(unsigned int n, unsigned int k) const
    {
        return m_binCoeffs[n][k];
    }
 
private:
    unsigned int m_max_n;
 
    TYP** m_binCoeffs;
};
 
 
// nothing
struct EmptyArgType {};
 
//
// Function Invoker for 8 args
//
template<typename FunctionType,
         typename ArgType1 = EmptyArgType,
         typename ArgType2 = EmptyArgType,
         typename ArgType3 = EmptyArgType,
         typename ArgType4 = EmptyArgType,
         typename ArgType5 = EmptyArgType,
         typename ArgType6 = EmptyArgType,
         typename ArgType7 = EmptyArgType,
         typename ArgType8 = EmptyArgType>
struct FuncInvoker
{
    FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7, ArgType8 _arg8) :
        function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3), arg4(_arg4), arg5(_arg5), arg6(_arg6), arg7(_arg7), arg8(_arg8) { }
 
    inline void operator()() { function(arg1, arg2, arg3, arg4, arg5, arg6, arg7, arg8); }
 
    FunctionType function;
    ArgType1 arg1;
    ArgType2 arg2;
    ArgType3 arg3;
    ArgType4 arg4;
    ArgType5 arg5;
    ArgType6 arg6;
    ArgType7 arg7;
    ArgType8 arg8;
};
 
 
//
// Function Invoker for 7 args
//
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5, typename ArgType6, typename ArgType7>
struct FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType>
{
    FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7) :
        function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3), arg4(_arg4), arg5(_arg5), arg6(_arg6), arg7(_arg7) { }
 
    inline void operator()() { function(arg1, arg2, arg3, arg4, arg5, arg6, arg7); }
 
    FunctionType function;
    ArgType1 arg1;
    ArgType2 arg2;
    ArgType3 arg3;
    ArgType4 arg4;
    ArgType5 arg5;
    ArgType6 arg6;
    ArgType7 arg7;
};
 
//
// Function Invoker for 6 args
//
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5, typename ArgType6>
struct FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, EmptyArgType, EmptyArgType>
{
    FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6) :
        function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3), arg4(_arg4), arg5(_arg5), arg6(_arg6) { }
 
    inline void operator()() { function(arg1, arg2, arg3, arg4, arg5, arg6); }
 
    FunctionType function;
    ArgType1 arg1;
    ArgType2 arg2;
    ArgType3 arg3;
    ArgType4 arg4;
    ArgType5 arg5;
    ArgType6 arg6;
};
 
//
// Function Invoker for 5 args
//
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5>
struct FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, EmptyArgType, EmptyArgType, EmptyArgType>
{
    FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5) :
        function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3), arg4(_arg4), arg5(_arg5) { }
 
    inline void operator()() { function(arg1, arg2, arg3, arg4, arg5); }
 
    FunctionType function;
    ArgType1 arg1;
    ArgType2 arg2;
    ArgType3 arg3;
    ArgType4 arg4;
    ArgType5 arg5;
};
 
//
// Function Invoker for 4 args
//
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4>
struct FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType>
{
    FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4) :
        function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3), arg4(_arg4) { }
 
    inline void operator()() { function(arg1, arg2, arg3, arg4); }
 
    FunctionType function;
    ArgType1 arg1;
    ArgType2 arg2;
    ArgType3 arg3;
    ArgType4 arg4;
};
 
//
// Function Invoker for 3 args
//
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3>
struct FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType>
{
    FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3) :
        function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3) { }
 
    inline void operator()() { function(arg1, arg2, arg3); }
 
    FunctionType function;
    ArgType1 arg1;
    ArgType2 arg2;
    ArgType3 arg3;
};
 
//
// Function Invoker for 2 args
//
template<typename FunctionType, typename ArgType1, typename ArgType2>
struct FuncInvoker<FunctionType, ArgType1, ArgType2, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType>
{
    FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2) :
        function(f), arg1(_arg1), arg2(_arg2) { }
 
    inline void operator()() { function(arg1, arg2); }
 
    FunctionType function;
    ArgType1 arg1;
    ArgType2 arg2;
};
 
//
// Function Invoker for 1 args
//
template<typename FunctionType, typename ArgType1>
struct FuncInvoker<FunctionType, ArgType1, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType>
{
    FuncInvoker(FunctionType f, ArgType1 _arg1) :
        function(f), arg1(_arg1) { }
 
    inline void operator()() { function(arg1); }
 
    FunctionType function;
    ArgType1 arg1;
};
 
//
// Function Invoker for 0 args
//
template<typename FunctionType>
struct FuncInvoker<FunctionType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType>
{
    FuncInvoker(FunctionType f) :
        function(f) { }
 
    inline void operator()() { function(); }
 
    FunctionType function;
};
 
 
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5, typename ArgType6, typename ArgType7, typename ArgType8>
FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, ArgType8>
createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7, ArgType8 _arg8)
{
    return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, ArgType8>(func, _arg1, _arg2, _arg3, _arg4, _arg5, _arg6, _arg7, _arg8);
}
 
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5, typename ArgType6, typename ArgType7, typename ArgType8>
FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, ArgType8>
createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7)
{
    return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType>(func, _arg1, _arg2, _arg3, _arg4, _arg5, _arg6, _arg7);
}
 
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5, typename ArgType6>
FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6>
createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6)
{
    return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6>(func, _arg1, _arg2, _arg3, _arg4, _arg5, _arg6);
}
 
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5>
FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5>
createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5)
{
    return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5>(func, _arg1, _arg2, _arg3, _arg4, _arg5);
}
 
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4>
FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4>
createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4)
{
    return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4>(func, _arg1, _arg2, _arg3, _arg4);
}
 
template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3>
FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3>
createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3)
{
    return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3>(func, _arg1, _arg2, _arg3);
}
 
template<typename FunctionType, typename ArgType1, typename ArgType2>
FuncInvoker<FunctionType, ArgType1, ArgType2>
createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2)
{
    return FuncInvoker<FunctionType, ArgType1, ArgType2>(func, _arg1, _arg2);
}
 
template<typename FunctionType, typename ArgType1>
FuncInvoker<FunctionType, ArgType1>
createFuncInvoker(FunctionType func, ArgType1 _arg1)
{
    return FuncInvoker<FunctionType, ArgType1>(func, _arg1);
}
 
template<typename FunctionType>
FuncInvoker<FunctionType>
createFuncInvoker(FunctionType func)
{
    return FuncInvoker<FunctionType>(func);
}
 
}
}