FastUtils.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/System.h> // IWYU pragma: keep
#include <ogdf/basic/basic.h>
 
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <utility>
#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
 
#ifndef OGDF_SSE3_EXTENSIONS
// if we have no SSE3 these flags cannot be used (but they are sometime set nonethelless by CI for testing)
#   undef OGDF_FME_KERNEL_USE_SSE
#   undef OGDF_FME_KERNEL_USE_SSE_DIRECT
#endif
 
 
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);
}
 
}
}