cp-algo/data_structures/stack_union.hpp

• View this file on GitHub
• Last update: 2024-08-06 17:01:27+02:00
• Include: #include "cp-algo/data_structures/stack_union.hpp"

Required by

• cp-algo/graph/base.hpp
• cp-algo/graph/cycle.hpp
• cp-algo/graph/euler.hpp
• cp-algo/graph/mst.hpp
• cp-algo/graph/shortest_path.hpp

Verified with

• Cycle Detection (Directed) (verify/graph/cycle_directed.test.cpp)
• Cycle Detection (Undirected) (verify/graph/cycle_undirected.test.cpp)
• Eulerian Trail (Directed) (verify/graph/euler_directed.test.cpp)
• Eulerian Trail (Undirected) (verify/graph/euler_undirected.test.cpp)
• Minimum Spanning Tree (verify/graph/mst.test.cpp)
• Shortest Path (verify/graph/shortest_path.test.cpp)

Code

#ifndef CP_ALGO_DATA_STRUCTURES_STACK_UNION_HPP
#define CP_ALGO_DATA_STRUCTURES_STACK_UNION_HPP
#include <cstddef>
#include <vector>
namespace cp_algo::data_structures {
    template<class datatype>
    struct stack_union {
        stack_union(int n = 0): head(n), next(1), data(1) {}

        void push(int v, datatype const& vdata) {
            next.push_back(head[v]);
            head[v] = std::size(next) - 1;
            data.push_back(vdata);
        }
        template<typename... Args>
        void emplace(int v, Args&&... vdata) {
            next.push_back(head[v]);
            head[v] = size(next) - 1;
            data.emplace_back(std::forward<Args...>(vdata...));
        }

        void reserve(int m) {
            data.reserve(m);
            next.reserve(m);
        }

        size_t size() const {return std::size(head);}
        size_t nodes() const {return std::size(data);}

        std::vector<int> head, next;
        std::vector<datatype> data;
    };
}
#endif // CP_ALGO_DATA_STRUCTURES_STACK_UNION_HPP

#line 1 "cp-algo/data_structures/stack_union.hpp"


#include <cstddef>
#include <vector>
namespace cp_algo::data_structures {
    template<class datatype>
    struct stack_union {
        stack_union(int n = 0): head(n), next(1), data(1) {}

        void push(int v, datatype const& vdata) {
            next.push_back(head[v]);
            head[v] = std::size(next) - 1;
            data.push_back(vdata);
        }
        template<typename... Args>
        void emplace(int v, Args&&... vdata) {
            next.push_back(head[v]);
            head[v] = size(next) - 1;
            data.emplace_back(std::forward<Args...>(vdata...));
        }

        void reserve(int m) {
            data.reserve(m);
            next.reserve(m);
        }

        size_t size() const {return std::size(head);}
        size_t nodes() const {return std::size(data);}

        std::vector<int> head, next;
        std::vector<datatype> data;
    };
}

Back to top page