list_templates.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/comparer.h>
 
#include <functional>
 
namespace ogdf {
 
template<typename CONTAINER>
inline void safeForEach(CONTAINER& container,
        std::function<void(typename CONTAINER::value_type)> func) {
    for (auto it = container.begin(); it != container.end();) {
        auto prev = it++;
        func(*prev);
    }
}
 
template<typename CONTAINER>
inline bool safeTestForEach(CONTAINER& container,
        std::function<bool(typename CONTAINER::value_type)> func) {
    for (auto it = container.begin(); it != container.end();) {
        auto prev = it++;
        if (!func(*prev)) {
            return false;
        }
    }
    return true;
}
 
// sorts list L using quicksort
template<class LIST>
void quicksortTemplate(LIST& L) {
    auto comparer = StdComparer<typename LIST::value_type>();
    quicksortTemplate(L, comparer);
}
 
// sorts list L using quicksort and compare element comp
template<class LIST, class COMPARER>
void quicksortTemplate(LIST& L, const COMPARER& comp) {
    const int n = L.size();
    Array<typename LIST::value_type> A(n);
 
    int i = 0;
    for (const typename LIST::value_type& x : L) {
        A[i++] = x;
    }
 
    A.quicksort(comp);
 
    i = 0;
    for (typename LIST::value_type& x : L) {
        x = A[i++];
    }
}
 
namespace internal {
 
template<typename CONTAINER, typename TYPE, typename ITERATOR>
ITERATOR chooseIteratorByFastTest(CONTAINER& container,
        std::function<bool(const TYPE&)> includeElement) {
    int nElements = 0;
 
    for (const auto& e : container) {
        nElements += includeElement(e) ? 1 : 0;
    }
 
    ITERATOR result = container.end();
 
    if (nElements > 0) {
        int chosenElement = randomNumber(1, nElements);
        int elemCounter = 0;
 
        for (ITERATOR it = container.begin(); result == container.end(); it++) {
            if (includeElement(*it)) {
                elemCounter++;
 
                if (elemCounter == chosenElement) {
                    result = it;
                }
            }
        }
    }
 
    return result;
};
 
template<typename CONTAINER, typename TYPE, typename ITERATOR>
ITERATOR chooseIteratorBySlowTest(CONTAINER& container,
        std::function<bool(const TYPE&)> includeElement, int size) {
    Array<ITERATOR> other(size);
 
    int i = 0;
    for (ITERATOR it = container.begin(); it != container.end(); it++) {
        other[i] = it;
        i++;
    }
 
    other.permute();
 
    ITERATOR result = container.end();
 
    for (auto it : other) {
        if (includeElement(*it)) {
            result = it;
            break;
        }
    }
 
    return result;
};
 
template<typename CONTAINER, typename TYPE, typename ITERATOR>
ITERATOR chooseIteratorFrom(CONTAINER& container, std::function<bool(const TYPE&)> includeElement,
        bool isFastTest) {
    ITERATOR result = container.begin();
    int size = container.size();
 
    if (size > 0) {
        // let's try to pick *any* element
        int index = randomNumber(0, size - 1);
 
        for (int i = 0; i < index; i++) {
            result++;
        }
 
        // the initially chosen element is not feasible?
        if (!includeElement(*result)) {
            if (isFastTest) {
                result = chooseIteratorByFastTest<CONTAINER, TYPE, ITERATOR>(container,
                        includeElement);
            } else {
                result = chooseIteratorBySlowTest<CONTAINER, TYPE, ITERATOR>(container,
                        includeElement, size);
            }
        }
    }
 
    return result;
}
 
 
}
 
template<typename CONTAINER, typename TYPE>
typename CONTAINER::iterator chooseIteratorFrom(
        CONTAINER& container,
        std::function<bool(const TYPE&)> includeElement = [](const TYPE&) { return true; },
        bool isFastTest = true) {
    return internal::chooseIteratorFrom<CONTAINER, TYPE, typename CONTAINER::iterator>(container,
            includeElement, isFastTest);
}
 
template<typename CONTAINER, typename TYPE>
typename CONTAINER::const_iterator chooseIteratorFrom(
        const CONTAINER& container,
        std::function<bool(const TYPE&)> includeElement = [](const TYPE&) { return true; },
        bool isFastTest = true) {
    return internal::chooseIteratorFrom<const CONTAINER, TYPE, typename CONTAINER::const_iterator>(
            container, includeElement, isFastTest);
}
 
}