Program Listing for File SparseVector.hpp¶

/*
 * SparseVector.hpp
 *
 * Created: 2019-10-15
 * Author: Armin Wiebigke
 */
#ifndef NETWORKIT_AUXILIARY_SPARSE_VECTOR_HPP_
#define NETWORKIT_AUXILIARY_SPARSE_VECTOR_HPP_

#include <algorithm>
#include <cassert>
#include <vector>

#include <networkit/Globals.hpp>

namespace NetworKit {

template <typename T>
class SparseVector {
public:
    SparseVector();

    explicit SparseVector(index size);

    SparseVector(index size, T emptyValue);

    void setUpperBound(index size);

    index upperBound() const;

    count size() const;

    void insert(index i, T value);

    T &operator[](index i);

    const T &operator[](index i) const;

    bool indexIsUsed(index idx);

    void insertOrSet(index i, T value);

    void removeUnusedIndexes() {
        auto new_end = std::remove_if(usedIndexes.begin(), usedIndexes.end(),
                                      [&](index i) { return data[i] == emptyValue; });
        usedIndexes.erase(new_end, usedIndexes.end());
    }

    void reset();

    void clear();

    void resize(size_t size, T emptyValue);

    template <typename ElementHandler>
    void forElements(ElementHandler &&lambda) {
        for (index i : usedIndexes) {
            lambda(i, data[i]);
        }
    }

private:
    std::vector<T> data;
    std::vector<index> usedIndexes;
    T emptyValue;
};

template <typename T>
SparseVector<T>::SparseVector() : emptyValue(T{}) {}

template <typename T>
SparseVector<T>::SparseVector(count size) : SparseVector(size, T{}) {}

template <typename T>
SparseVector<T>::SparseVector(count size, T emptyValue)
    : data(size, emptyValue), emptyValue(emptyValue) {}

template <typename T>
void SparseVector<T>::reset() {
    for (index i : usedIndexes) {
        data[i] = emptyValue;
    }
    usedIndexes.clear();
}

template <typename T>
void SparseVector<T>::insert(index i, T value) {
    assert(data[i] == emptyValue);
    usedIndexes.push_back(i);
    data[i] = std::move(value);
}

template <typename T>
T &SparseVector<T>::operator[](index i) {
    return data[i];
}

template <typename T>
const T &NetworKit::SparseVector<T>::operator[](NetworKit::index i) const {
    assert(i < data.size());
    return data[i];
}

template <typename T>
void SparseVector<T>::setUpperBound(index size) {
    data.resize(size, emptyValue);
}

template <typename T>
index SparseVector<T>::upperBound() const {
    return data.size();
}

template <typename T>
count SparseVector<T>::size() const {
    return usedIndexes.size();
}

template <typename T>
void NetworKit::SparseVector<T>::clear() {
    usedIndexes.clear();
    usedIndexes.shrink_to_fit();
    data.clear();
    data.shrink_to_fit();
}

template <typename T>
void NetworKit::SparseVector<T>::resize(size_t size, T emptyValue) {
    if (size > upperBound()) {
        this->emptyValue = emptyValue;
        data = std::vector<T>(size, this->emptyValue);
        usedIndexes = std::vector<index>();
    }
}

template <typename T>
bool NetworKit::SparseVector<T>::indexIsUsed(index idx) {
    return data[idx] != emptyValue;
}

template <typename T>
void NetworKit::SparseVector<T>::insertOrSet(NetworKit::index i, T value) {
    if (!indexIsUsed(i)) {
        insert(i, value);
    } else {
        data[i] = value;
    }
}

} /* namespace NetworKit */

#endif // NETWORKIT_AUXILIARY_SPARSE_VECTOR_HPP_