#StackBounty: #c++ #library #pathfinding #fluent-interface Pathfinding library in C++ with fluent API

Bounty: 50

Introduction

I have this C++ pathfinding library. My primary requirement is that a client programmer may couple his/her own graph representation and the library will work with that representation.

The only API a client graph node type is to implement is begin() and end() which should return a sequence of neighbors in case of undirected graphs, or a sequence of child nodes in case of directed graphs.

What comes to weight function, my library expects only that the weight type is default-constructible (which must represent the “zero-weight”) and a operator>. In my 2nd demo, the weights are $2 times 2$-matrices, for example.

Critique request

Please tell me anything that comes to mind. However, I am most interested in hearing the comments regarding

  • const (in)correctness,
  • efficiency,
  • adherence to C++ programming idioms.

Code

pathfinding.hpp

#ifndef NET_CODERODDE_PATHFINDING_HPP
#define NET_CODERODDE_PATHFINDING_HPP

#include "a_star.hpp"
#include "dijkstra.hpp"
#include "heuristic_function.hpp"
#include "weight_function.hpp"
#include "weighted_path.hpp"

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename Weight>
    class heuristic_function_selector {
    public:
        heuristic_function_selector(
                                Node& source,
                                Node& target,
                                weight_function<Node, Weight>* weight_function)
        :
        m_source{source},
        m_target{target},
        m_weight_function{weight_function} {}

        weighted_path<Node, Weight> without_heuristic_function() {
            return search(m_source, m_target, *m_weight_function);
        }

        weighted_path<Node, Weight>
        with_heuristic_function(
                        heuristic_function<Node, Weight>* heuristic_function) {
            return search(m_source,
                          m_target,
                          *m_weight_function,
                          *heuristic_function);
        }

    private:
        Node m_source;
        Node m_target;
        weight_function<Node, Weight>* m_weight_function;
    };

    template<typename Node, typename Weight>
    class weight_function_selector {
    public:
        weight_function_selector(Node& source, Node& target) :
        m_source{source},
        m_target{target} {}

        heuristic_function_selector<Node, Weight>
        with_weights(weight_function<Node, Weight>* wf) {
            return heuristic_function_selector<Node, Weight>(m_source,
                                                             m_target,
                                                             wf);
        }

    private:
        Node m_source;
        Node m_target;
    };

    template<typename Node, typename Weight>
    class target_node_selector {
    public:
        target_node_selector(Node source) : m_source{source} {}
        weight_function_selector<Node, Weight> to(Node& target) {
            return weight_function_selector<Node, Weight>(m_source, target);
        }

    private:
        Node m_source;
    };

    template<typename Node, typename Weight>
    class source_node_selector {
    public:
        target_node_selector<Node, Weight> from(Node& source) {
            return target_node_selector<Node, Weight>{source};
        }
    };

    template<typename Node, typename Weight>
    source_node_selector<Node, Weight> find_shortest_path() {
        return source_node_selector<Node, Weight>{};
    }

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_HPP

a_star.hpp

#ifndef NET_CODERODDE_PATHFINDING_A_STAR_HPP
#define NET_CODERODDE_PATHFINDING_A_STAR_HPP

#include "child_node_iterator.hpp"
#include "heuristic_function.hpp"
#include "path_not_found_exception.hpp"
#include "weighted_path.hpp"
#include "weight_function.hpp"
#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename Weight>
    struct node_holder {
        Node* m_node;
        Weight m_f;

        node_holder(Node* node, Weight f) : m_node{node}, m_f{f} {}
    };

    template<typename Node, typename Weight, typename Cmp>
    void remove_and_delete_all_node_holders(
                std::priority_queue<node_holder<Node, Weight>*,
                                            std::vector<node_holder<Node, Weight>*>,
                                            Cmp>& open) {
        while (!open.empty()) {
            node_holder<Node, Weight>* current_node_holder = open.top();
            open.pop();
            delete current_node_holder;
        }
    }

    template<typename Node, typename Weight>
    weighted_path<Node, Weight>
    traceback_path(Node& target,
                   std::unordered_map<Node*, Node*>& parents,
                   weight_function<Node, Weight>& w) {
        std::vector<Node*> path;
        Node* current_node = &target;

        while (current_node) {
            path.push_back(current_node);
            current_node = parents[current_node];
        }

        std::reverse(path.begin(), path.end());

        Weight total_weight {};

        for (size_t i = 0; i < path.size() - 1; ++i) {
            total_weight += w(*path[i], *path[i + 1]);
        }

        return weighted_path<Node, Weight>(path, total_weight);
    }

    template<typename Node, typename Weight>
    weighted_path<Node, Weight> search(Node& source,
                                       Node& target,
                                       weight_function<Node, Weight>& w,
                                       heuristic_function<Node, Weight>& h) {

        auto cmp = [](node_holder<Node, Weight>* nh1,
                      node_holder<Node, Weight>* nh2) {
            return nh1->m_f > nh2->m_f;
        };

        std::priority_queue<node_holder<Node, Weight>*,
                            std::vector<node_holder<Node, Weight>*>,
                            decltype(cmp)> open(cmp);

        std::unordered_set<Node*> closed;
        std::unordered_map<Node*, Node*> parents;
        std::unordered_map<Node*, Weight> distances;

        open.push(new node_holder<Node, Weight>(&source, Weight{}));
        parents[&source] = nullptr;
        distances[&source] = Weight{};

        while (!open.empty()) {
            Node* current_node = open.top()->m_node;
            open.pop();

            if (*current_node == target) {
                remove_and_delete_all_node_holders(open);
                return traceback_path(*current_node, parents, w);
            }

            if (closed.find(current_node) != closed.end()) {
                continue;
            }

            closed.insert(current_node);

            for (Node& child_node : *current_node) {
                if (closed.find(&child_node) != closed.end()) {
                    continue;
                }

                Weight tentative_distance = distances[current_node] +
                w(*current_node, child_node);

                if (distances.find(&child_node) == distances.end()
                    || distances[&child_node] > tentative_distance) {
                    open.push(new node_holder<Node, Weight>(
                                        &child_node,
                                        tentative_distance + h(child_node)));
                    distances[&child_node] = tentative_distance;
                    parents[&child_node] = current_node;
                }
            }
        }

        remove_and_delete_all_node_holders(open);
        throw path_not_found_exception<Node>(source, target);
    }
} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_A_STAR_HPP

dijkstra.hpp

#ifndef NET_CODERODDE_PATHFINDING_DIJKSTRA_HPP
#define NET_CODERODDE_PATHFINDING_DIJKSTRA_HPP

#include "a_star.hpp"
#include "heuristic_function.hpp"

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename DistanceType>
    class zero_heuristic :
    public virtual heuristic_function<Node, DistanceType> {

    public:
        DistanceType operator()(const Node& target) const {
            DistanceType zero{};
            return zero;
        }
    };

    template<typename Node, typename Weight>
    weighted_path<Node, Weight> search(Node& source,
                                       Node& target,
                                       weight_function<Node, Weight>& w) {
        zero_heuristic<Node, Weight> h;
        return search(source, target, w, h);
    }

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_DIJKSTRA_HPP

child_node_iterator.hpp

#ifndef NET_CODERODDE_PATHFINDING_FORWARD_NODE_EXPANDER_HPP
#define NET_CODERODDE_PATHFINDING_FORWARD_NODE_EXPANDER_HPP

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node>
    class child_node_iterator {

    public:
        virtual child_node_iterator<Node>& operator++() = 0;
        virtual Node& operator*()                       = 0;
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // End of NET_CODERODDE_PATHFINDING_FORWARD_NODE_EXPANDER_HPP.

heuristic_function.hpp

#ifndef NET_CODERODDE_PATHFINDING_HEURISTIC_FUNCTION_HPP
#define NET_CODERODDE_PATHFINDING_HEURISTIC_FUNCTION_HPP

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename DistanceType>
    class heuristic_function {

    public:
        virtual DistanceType operator()(const Node& target) const = 0;
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // End of NET_CODERODDE_PATHFINDING_HEURISTIC_FUNCTION_HPP.

path_not_found_exception.hpp

#ifndef NET_CODERODDE_PATHFINDING_PATH_NOT_FOUND_EXCEPTION_HPP
#define NET_CODERODDE_PATHFINDING_PATH_NOT_FOUND_EXCEPTION_HPP

#include <sstream>
#include <stdexcept>

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node>
    class path_not_found_exception : public virtual std::logic_error {
    public:
        path_not_found_exception(const Node& source,
                                 const Node& target)
        :
        std::logic_error{""},
        m_source{&source},
        m_target{&target}
        {}

        const char* what() {
            std::stringstream ss;
            ss << "A path from source {" << *m_source << "} to target {"
               << *m_target << "} not found.";
            return ss.str().c_str();
        }

    private:
        const Node* m_source;
        const Node* m_target;
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_PATH_NOT_FOUND_EXCEPTION_HPP

weight_function.hpp

#ifndef NET_CODERODDE_PATHFINDING_WEIGHT_FUNCTION_HPP
#define NET_CODERODDE_PATHFINDING_WEIGHT_FUNCTION_HPP

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename WeightType>
    class weight_function {

    public:
        virtual WeightType operator()(const Node& a, const Node& b) = 0;
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_WEIGHT_FUNCTION_HPP

weighted_path.hpp

#ifndef NET_CODERODDE_PATHFINDING_WEIGHTED_PATH_HPP
#define NET_CODERODDE_PATHFINDING_WEIGHTED_PATH_HPP

#include <iostream>

namespace net {
namespace coderodde {
namespace pathfinding {

    template<typename Node, typename Weight>
    class weighted_path {
    public:
        weighted_path(std::vector<Node*> path_vector, Weight total_weight)
        :
        m_path_vector{path_vector},
        m_total_weight{total_weight}
        {}

        Node& node_at(size_t index) {
            return *m_path_vector->at(index);
        }

        Weight total_weight() const {
            return m_total_weight;
        }

    private:
        std::vector<Node*> m_path_vector;
        Weight             m_total_weight;

        friend std::ostream& operator<<(std::ostream& out, weighted_path& path) {
            std::string separator{};
            out << "[";

            for (Node* node : path.m_path_vector) {
                out << separator;
                separator = ", ";
                out << *node;
            }

            return out << "]";
        }
    };

} // End of namespace net::coderodde::pathfinding.
} // End of namespace net::coderodde.
} // End of namespace net.

#endif // NET_CODERODDE_PATHFINDING_WEIGHTED_PATH_HPP

main.cpp

#include "pathfinding.hpp"
#include "child_node_iterator.hpp"
#include "path_not_found_exception.hpp"

#include <cstdlib>
#include <functional>
#include <iostream>
#include <unordered_set>
#include <utility>
#include <vector>

using net::coderodde::pathfinding::child_node_iterator;
using net::coderodde::pathfinding::heuristic_function;
using net::coderodde::pathfinding::weight_function;
using net::coderodde::pathfinding::weighted_path;
using net::coderodde::pathfinding::find_shortest_path;
using net::coderodde::pathfinding::path_not_found_exception;

// This is just a sample graph node type. The only requirement for coupling it
// with the search algorithms is 'bool operator==(const grid_node& other) const'
// and 'begin()' + 'end()' for iterating over the child nodes.
class grid_node {
private:

    class grid_node_neighbor_iterator : public child_node_iterator<grid_node> {
    private:
        std::vector<grid_node*>* m_neighbor_vector;
        std::size_t m_index;

    public:
        grid_node_neighbor_iterator(std::vector<grid_node*>* neighbor_vector,
                                    std::size_t index)
        :
        m_neighbor_vector{neighbor_vector},
        m_index{index} {}

        ~grid_node_neighbor_iterator() {
            delete m_neighbor_vector;
        }

        grid_node_neighbor_iterator& operator++() {
            ++m_index;
            return *this;
        }

        bool operator==(grid_node_neighbor_iterator& other) const {
            return m_index == other.m_index;
        }

        bool operator!=(grid_node_neighbor_iterator& other) const {
            return m_index != other.m_index;
        }

        grid_node& operator*() {
            return *m_neighbor_vector->at(m_index);
        }
    };

public:

    grid_node(int x, int y, bool traversable);

    void set_top_neighbor    (grid_node& neighbor);
    void set_bottom_neighbor (grid_node& neighbor);
    void set_left_neighbor   (grid_node& neighbor);
    void set_right_neighbor  (grid_node& neighbor);

    bool operator==(const grid_node& other) {
        return m_x == other.m_x && m_y == other.m_y;
    }

    grid_node_neighbor_iterator begin() {
        std::vector<grid_node*>* neighbor_vector =
        new std::vector<grid_node*>;

        if (m_top_neighbor && m_top_neighbor->m_traversable) {
            neighbor_vector->push_back(m_top_neighbor);
        }

        if (m_bottom_neighbor && m_bottom_neighbor->m_traversable) {
            neighbor_vector->push_back(m_bottom_neighbor);
        }

        if (m_left_neighbor && m_left_neighbor->m_traversable) {
            neighbor_vector->push_back(m_left_neighbor);
        }

        if (m_right_neighbor && m_right_neighbor->m_traversable) {
            neighbor_vector->push_back(m_right_neighbor);
        }

        return grid_node_neighbor_iterator(neighbor_vector, 0);
    }

    grid_node_neighbor_iterator end() {
        std::size_t neighbor_count = 0;

        if (m_top_neighbor && m_top_neighbor->m_traversable) {
            neighbor_count++;
        }

        if (m_bottom_neighbor && m_bottom_neighbor->m_traversable) {
            neighbor_count++;
        }

        if (m_left_neighbor && m_left_neighbor->m_traversable) {
            neighbor_count++;
        }

        if (m_right_neighbor && m_right_neighbor->m_traversable) {
            neighbor_count++;
        }

        return grid_node_neighbor_iterator(nullptr, neighbor_count);
    }

    // Heuristic function must know the coordinates:
    friend class grid_node_heuristic_function;

    // For printing to, say, cout:
    friend std::ostream& operator<<(std::ostream& out, const grid_node& gn);

    // std::hash and std::equal_to so that the internal unordered_* data
    // structures may work with grid nodes via pointers:
    friend class std::hash<grid_node*>;
    friend class std::equal_to<grid_node*>;

private:

    int m_x;
    int m_y;

    bool   m_traversable;

    grid_node* m_top_neighbor;
    grid_node* m_bottom_neighbor;
    grid_node* m_left_neighbor;
    grid_node* m_right_neighbor;
};

grid_node::grid_node(int x, int y, bool traversable)
:
m_x{x},
m_y{y},
m_traversable{traversable}
{
    m_top_neighbor    = nullptr;
    m_bottom_neighbor = nullptr;
    m_left_neighbor   = nullptr;
    m_right_neighbor  = nullptr;
}

void grid_node::set_top_neighbor(grid_node& neighbor)
{
    m_top_neighbor = &neighbor;
}

void grid_node::set_bottom_neighbor(grid_node& neighbor)
{
    m_bottom_neighbor = &neighbor;
}

void grid_node::set_left_neighbor(grid_node& neighbor)
{
    m_left_neighbor = &neighbor;
}

void grid_node::set_right_neighbor(grid_node& neighbor)
{
    m_right_neighbor = &neighbor;
}

std::ostream& operator<<(std::ostream& out, const grid_node& gn)
{
    out << "{x=" << gn.m_x << ", y=" << gn.m_y << "}";
    return out;
}

// This class will be used as an EDGE WEIGHT:
class matrix {
public:
    matrix(int a1, int a2, int b1, int b2)
    :
    m_a1{a1},
    m_a2{a2},
    m_b1{b1},
    m_b2{b2}
    {}

    matrix() : matrix{0, 0, 0, 0} {}

    int determinant() const {
        return m_a1 * m_b2 - m_a2 * m_b1;
    }

    matrix operator+(const matrix& other) {
        return matrix{m_a1 + other.m_a1,
                      m_a2 + other.m_a2,
                      m_b1 + other.m_b1,
                      m_b2 + other.m_b2};
    }

    matrix& operator+=(const matrix& other) {
        m_a1 += other.m_a1;
        m_a2 += other.m_a2;
        m_b1 += other.m_b1;
        m_b2 += other.m_b2;
        return *this;
    }

    bool operator>(const matrix& other) {
        return abs(determinant()) > abs(other.determinant());
    }

    friend std::ostream& operator<<(std::ostream& out, const matrix& m) {
        return out << "{{" << m.m_a1 << ", " << m.m_a2 << "}, {"
                   << m.m_b1 << ", " << m.m_b2 << "}}";
    }

    friend class grid_node_heuristic_function;
    friend class std::hash<grid_node*>;
    friend class std::equal_to<grid_node*>;

private:
    int m_a1;
    int m_a2;
    int m_b1;
    int m_b2;
};

// A graph node type whose edge weights are matrix. This is just a demonstration
// of flexibility of the library.
class matrix_node {
private:

    class matrix_node_child_iterator :
    public child_node_iterator<matrix_node> {

    private:
        std::size_t m_index;
        std::vector<matrix_node*>* m_matrix_node_pointer_vector;

    public:
        matrix_node_child_iterator(
                        std::vector<matrix_node*>& matrix_node_pointer_vector,
                        std::size_t index)
        : m_matrix_node_pointer_vector{&matrix_node_pointer_vector},
          m_index{index} {}

        matrix_node_child_iterator& operator++() {
            m_index++;
            return *this;
        }

        bool operator!=(const matrix_node_child_iterator& other) {
            return m_index != other.m_index;
        }

        matrix_node& operator*() {
            return *m_matrix_node_pointer_vector->at(m_index);
        }
    };

public:

    matrix_node(size_t id) : m_id{id} {}

    bool operator==(const matrix_node& other) const {
        return m_id == other.m_id;
    }

    void add_neighbor(matrix_node& neighbor) {
        m_neighbors.push_back(&neighbor);
    }

    matrix_node_child_iterator begin() {
        return matrix_node_child_iterator(m_neighbors, 0);
    }

    matrix_node_child_iterator end() {
        return matrix_node_child_iterator(m_neighbors, m_neighbors.size());
    }

private:

    friend class std::hash<matrix_node>;
    friend class std::equal_to<matrix_node>;
    friend std::ostream& operator<<(std::ostream& out, const matrix_node& n);

    std::vector<matrix_node*> m_neighbors;
    size_t m_id;
};

std::ostream& operator<<(std::ostream& out, const matrix_node& node) {
    return out << "{id=" << node.m_id << "}";
}

namespace std {
    template<>
    struct hash<matrix_node> {
        std::size_t operator()(const matrix_node& node) const {
            return node.m_id;
        }
    };

    template<>
    struct equal_to<matrix_node> {
        bool operator()(const matrix_node& a, const matrix_node& b) const {
            return a.m_id == b.m_id;
        }
    };
}

class grid_node_weight_function :
public virtual weight_function<grid_node, int>
{
public:
    int operator()(const grid_node& a, const grid_node& b) {
        return 1;
    }
};

class grid_node_heuristic_function :
public virtual heuristic_function<grid_node, int>
{
public:
    grid_node_heuristic_function(const grid_node source)
    :
    m_source{source}
    {}

    int operator()(const grid_node& target) const {
        // Manhattan-distance:
        return abs(m_source.m_x - target.m_x) + abs(m_source.m_y - target.m_y);
    }

private:
    grid_node m_source;
};

class matrix_node_weight_function :
public virtual weight_function<matrix_node, matrix>
{
public:
    std::unordered_map<matrix_node, matrix>&
    operator[](const matrix_node& node) {
        return m_map[node];
    }

    matrix operator()(const matrix_node& tail, const matrix_node& head) override {
        return m_map[tail][head];
    }

private:
    std::unordered_map<matrix_node,
    std::unordered_map<matrix_node, matrix>> m_map;
};

namespace std {

    template<>
    struct hash<grid_node*> {
        std::size_t operator()(const grid_node* gn) const {
            return gn->m_x ^ gn->m_y;
        }
    };

    template<>
    struct equal_to<grid_node*> {
        bool operator()(const grid_node* a, const grid_node* b) const {
            return a->m_x == b->m_x && a->m_y == b->m_y;
        }
    };
}

int main(int argc, const char * argv[]) {
    std::vector<std::vector<int>> maze = {
        { 0, 0, 0, 1, 0, 0 },
        { 0, 1, 1, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 0 },
        { 1, 1, 0, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 0 },
        { 0, 1, 1, 1, 0, 0 },
        { 0, 0, 0, 0, 0, 0 },
    };

    std::vector<std::vector<grid_node>> grid_node_maze;

    for (size_t y = 0; y < maze.size(); ++y) {
        std::vector<grid_node> grid_node_maze_row;

        for (size_t x = 0; x < maze[y].size(); ++x) {
            grid_node_maze_row.push_back(grid_node(x, y, maze[y][x] != 1));
        }

        grid_node_maze.push_back(grid_node_maze_row);
    }

    for (size_t y = 0; y < grid_node_maze.size(); ++y) {
        for (int x = 0; x < grid_node_maze[0].size() - 1; ++x) {
            grid_node_maze[y][x].set_right_neighbor(grid_node_maze[y][x + 1]);
        }

        for (int x = 1; x < grid_node_maze[0].size(); ++x) {
            grid_node_maze[y][x].set_left_neighbor(grid_node_maze[y][x - 1]);
        }
    }

    for (size_t x = 0; x < grid_node_maze[0].size(); ++x) {
        for (int y = 0; y < grid_node_maze.size() - 1; ++y) {
            grid_node_maze[y][x].set_bottom_neighbor(grid_node_maze[y + 1][x]);
        }

        for (int y = 1; y < grid_node_maze.size(); ++y) {
            grid_node_maze[y][x].set_top_neighbor(grid_node_maze[y - 1][x]);
        }
    }

    grid_node_weight_function grid_node_wf;
    grid_node_heuristic_function grid_node_hf(grid_node_maze[6][5]);

    try {
        auto path = find_shortest_path<grid_node, int>()
                    .from(grid_node_maze[0][0])
                    .to(grid_node_maze[6][5])
                    .with_weights(&grid_node_wf)
                    .with_heuristic_function(&grid_node_hf);
        std::cout << path << "n";
        std::cout << "Final maze distance: " << path.total_weight() << "n";
    } catch (path_not_found_exception<grid_node>& ex) {
        std::cerr << ex.what() << "n";
    }

    ////////// MATRIX DEMO ///////////
    matrix_node a{1};
    matrix_node b{2};
    matrix_node c{3};
    matrix_node d{4};
    matrix_node e{5};

    matrix_node_weight_function matrix_wf;

    matrix mab{1,   2,  3, 4};
    matrix mac{1,  -2, -3, 4};
    matrix mbc{2,   2,  1, 3};
    matrix mcd{5,  10,  7, 8};
    matrix mce{4,   0,  1, 3};
    matrix mde{1, -10,  9, 2};

    matrix_wf[a][b] = mab; a.add_neighbor(b);
    matrix_wf[a][c] = mac; a.add_neighbor(c);
    matrix_wf[b][c] = mbc; b.add_neighbor(c);
    matrix_wf[c][d] = mcd; c.add_neighbor(d);
    matrix_wf[c][e] = mce; c.add_neighbor(e);
    matrix_wf[d][e] = mde; d.add_neighbor(e);

    try {
        weighted_path<matrix_node, matrix> path
        = find_shortest_path<matrix_node, matrix>()
            .from(a)
            .to(e)
            .with_weights(&matrix_wf)
            .without_heuristic_function();

        std::cout << path << "n";
        std::cout << "Final matrix length: " << path.total_weight() << "n";
    } catch (path_not_found_exception<matrix_node>& ex) {
        std::cerr << ex.what() << "n";
    }
}


Get this bounty!!!

#StackBounty: #open-source #library #file-management #python #cloud-storage Library for file management. Two backends: filesystem, s3

Bounty: 50

I am dreaming of a Python library which abstracts the file handling of my application.

The application should run in two different configurations:

  1. No storage server. All file operations get done on the local disk.
  2. With storage server. All file operations should get done via s3.

I would like to do separation of concerns.

The application code should not care which configuration gets used. Choosing the right configuration (with or without storage server) gets done via configuration management.

I don’t need all file operations which I can do via os and os.path. I just need all operations which can be done via s3.

Other required features:

  • Open source: BSD or LGPL, not GPL
  • Support for Linux. Other operating systems are not important in this context.

Distinction / out off scope

I don’t want all file operations (like os.walk()). I just need the fundamental storage APIs of s3, but without a running storage server.


Get this bounty!!!

#StackBounty: #library #software-development #c++ #c #memory-management 'abstract' slab/arena memory management/allocation libr…

Bounty: 50

I’m interested in a library for managing allocation and de-allocation of memory within an abstract slab. That is, a library which doesn’t use malloc()/operator new/sbrk, but initially gets a contiguous range of addresses (maybe I’ve malloc()ed for it, or maybe it’s managing space on some remote device), but takes allocation and de-allocation requests and returns regions within the slab. The memory managing code does also not access the memory it manages; it doesn’t know what that memory is, so it can’t do things like write to it, or move parts of it elsewhere etc.

Requirements:

  • Gratis
  • Free and Open Source
  • Has some documentation
  • Note that the allocation mechanism cannot use the slab/arena to store any state (counters, pointers etc.); it can use the default allocator (e.g. malloc()/new) or some other mechanism for that.

Preferences:

  • C or C++ bindings
  • Written in modern C++
  • Supports prospective/time-based allocation (“I need X bytes between abstract time point t_1 and abstract time point t_2”; this allows for over-allocation over all time units, as long as there is no over-allocation at an individual time unit.)
  • Supports specifying alignment requirements
  • Supports resizing better than allocating a new segment and deallocating the old one
  • Actively maintained


Get this bounty!!!

#StackBounty: #library #software-development #c++ #c #memory-management 'abstract' slab/arena memory management/allocation libr…

Bounty: 50

I’m interested in a library for managing allocation and de-allocation of memory within an abstract slab. That is, a library which doesn’t use malloc()/operator new/sbrk, but initially gets a contiguous range of addresses (maybe I’ve malloc()ed for it, or maybe it’s managing space on some remote device), but takes allocation and de-allocation requests and returns regions within the slab. The memory managing code does also not access the memory it manages; it doesn’t know what that memory is, so it can’t do things like write to it, or move parts of it elsewhere etc.

Requirements:

  • Gratis
  • Free and Open Source
  • Has some documentation
  • Note that the allocation mechanism cannot use the slab/arena to store any state (counters, pointers etc.); it can use the default allocator (e.g. malloc()/new) or some other mechanism for that.

Preferences:

  • C or C++ bindings
  • Written in modern C++
  • Supports prospective/time-based allocation (“I need X bytes between abstract time point t_1 and abstract time point t_2”; this allows for over-allocation over all time units, as long as there is no over-allocation at an individual time unit.)
  • Supports specifying alignment requirements
  • Supports resizing better than allocating a new segment and deallocating the old one
  • Actively maintained


Get this bounty!!!

#StackBounty: #library #software-development #c++ #c #memory-management 'abstract' slab/arena memory management/allocation libr…

Bounty: 50

I’m interested in a library for managing allocation and de-allocation of memory within an abstract slab. That is, a library which doesn’t use malloc()/operator new/sbrk, but initially gets a contiguous range of addresses (maybe I’ve malloc()ed for it, or maybe it’s managing space on some remote device), but takes allocation and de-allocation requests and returns regions within the slab. The memory managing code does also not access the memory it manages; it doesn’t know what that memory is, so it can’t do things like write to it, or move parts of it elsewhere etc.

Requirements:

  • Gratis
  • Free and Open Source
  • Has some documentation
  • Note that the allocation mechanism cannot use the slab/arena to store any state (counters, pointers etc.); it can use the default allocator (e.g. malloc()/new) or some other mechanism for that.

Preferences:

  • C or C++ bindings
  • Written in modern C++
  • Supports prospective/time-based allocation (“I need X bytes between abstract time point t_1 and abstract time point t_2”; this allows for over-allocation over all time units, as long as there is no over-allocation at an individual time unit.)
  • Supports specifying alignment requirements
  • Supports resizing better than allocating a new segment and deallocating the old one
  • Actively maintained


Get this bounty!!!

#StackBounty: #library #software-development #c++ #c #memory-management 'abstract' slab/arena memory management/allocation libr…

Bounty: 50

I’m interested in a library for managing allocation and de-allocation of memory within an abstract slab. That is, a library which doesn’t use malloc()/operator new/sbrk, but initially gets a contiguous range of addresses (maybe I’ve malloc()ed for it, or maybe it’s managing space on some remote device), but takes allocation and de-allocation requests and returns regions within the slab. The memory managing code does also not access the memory it manages; it doesn’t know what that memory is, so it can’t do things like write to it, or move parts of it elsewhere etc.

Requirements:

  • Gratis
  • Free and Open Source
  • Has some documentation
  • Note that the allocation mechanism cannot use the slab/arena to store any state (counters, pointers etc.); it can use the default allocator (e.g. malloc()/new) or some other mechanism for that.

Preferences:

  • C or C++ bindings
  • Written in modern C++
  • Supports prospective/time-based allocation (“I need X bytes between abstract time point t_1 and abstract time point t_2”; this allows for over-allocation over all time units, as long as there is no over-allocation at an individual time unit.)
  • Supports specifying alignment requirements
  • Supports resizing better than allocating a new segment and deallocating the old one
  • Actively maintained


Get this bounty!!!

#StackBounty: #library #software-development #c++ #c #memory-management 'abstract' slab/arena memory management/allocation libr…

Bounty: 50

I’m interested in a library for managing allocation and de-allocation of memory within an abstract slab. That is, a library which doesn’t use malloc()/operator new/sbrk, but initially gets a contiguous range of addresses (maybe I’ve malloc()ed for it, or maybe it’s managing space on some remote device), but takes allocation and de-allocation requests and returns regions within the slab. The memory managing code does also not access the memory it manages; it doesn’t know what that memory is, so it can’t do things like write to it, or move parts of it elsewhere etc.

Requirements:

  • Gratis
  • Free and Open Source
  • Has some documentation
  • Note that the allocation mechanism cannot use the slab/arena to store any state (counters, pointers etc.); it can use the default allocator (e.g. malloc()/new) or some other mechanism for that.

Preferences:

  • C or C++ bindings
  • Written in modern C++
  • Supports prospective/time-based allocation (“I need X bytes between abstract time point t_1 and abstract time point t_2”; this allows for over-allocation over all time units, as long as there is no over-allocation at an individual time unit.)
  • Supports specifying alignment requirements
  • Supports resizing better than allocating a new segment and deallocating the old one
  • Actively maintained


Get this bounty!!!

#StackBounty: #library #software-development #c++ #c #memory-management 'abstract' slab/arena memory management/allocation libr…

Bounty: 50

I’m interested in a library for managing allocation and de-allocation of memory within an abstract slab. That is, a library which doesn’t use malloc()/operator new/sbrk, but initially gets a contiguous range of addresses (maybe I’ve malloc()ed for it, or maybe it’s managing space on some remote device), but takes allocation and de-allocation requests and returns regions within the slab. The memory managing code does also not access the memory it manages; it doesn’t know what that memory is, so it can’t do things like write to it, or move parts of it elsewhere etc.

Requirements:

  • Gratis
  • Free and Open Source
  • Has some documentation
  • Note that the allocation mechanism cannot use the slab/arena to store any state (counters, pointers etc.); it can use the default allocator (e.g. malloc()/new) or some other mechanism for that.

Preferences:

  • C or C++ bindings
  • Written in modern C++
  • Supports prospective/time-based allocation (“I need X bytes between abstract time point t_1 and abstract time point t_2”; this allows for over-allocation over all time units, as long as there is no over-allocation at an individual time unit.)
  • Supports specifying alignment requirements
  • Supports resizing better than allocating a new segment and deallocating the old one
  • Actively maintained


Get this bounty!!!

#StackBounty: #library #software-development #c++ #c #memory-management 'abstract' slab/arena memory management/allocation libr…

Bounty: 50

I’m interested in a library for managing allocation and de-allocation of memory within an abstract slab. That is, a library which doesn’t use malloc()/operator new/sbrk, but initially gets a contiguous range of addresses (maybe I’ve malloc()ed for it, or maybe it’s managing space on some remote device), but takes allocation and de-allocation requests and returns regions within the slab. The memory managing code does also not access the memory it manages; it doesn’t know what that memory is, so it can’t do things like write to it, or move parts of it elsewhere etc.

Requirements:

  • Gratis
  • Free and Open Source
  • Has some documentation
  • Note that the allocation mechanism cannot use the slab/arena to store any state (counters, pointers etc.); it can use the default allocator (e.g. malloc()/new) or some other mechanism for that.

Preferences:

  • C or C++ bindings
  • Written in modern C++
  • Supports prospective/time-based allocation (“I need X bytes between abstract time point t_1 and abstract time point t_2”; this allows for over-allocation over all time units, as long as there is no over-allocation at an individual time unit.)
  • Supports specifying alignment requirements
  • Supports resizing better than allocating a new segment and deallocating the old one
  • Actively maintained


Get this bounty!!!

#StackBounty: #library #software-development #c++ #c #memory-management 'abstract' slab/arena memory management/allocation libr…

Bounty: 50

I’m interested in a library for managing allocation and de-allocation of memory within an abstract slab. That is, a library which doesn’t use malloc()/operator new/sbrk, but initially gets a contiguous range of addresses (maybe I’ve malloc()ed for it, or maybe it’s managing space on some remote device), but takes allocation and de-allocation requests and returns regions within the slab. The memory managing code does also not access the memory it manages; it doesn’t know what that memory is, so it can’t do things like write to it, or move parts of it elsewhere etc.

Requirements:

  • Gratis
  • Free and Open Source
  • Has some documentation
  • Note that the allocation mechanism cannot use the slab/arena to store any state (counters, pointers etc.); it can use the default allocator (e.g. malloc()/new) or some other mechanism for that.

Preferences:

  • C or C++ bindings
  • Written in modern C++
  • Supports prospective/time-based allocation (“I need X bytes between abstract time point t_1 and abstract time point t_2”; this allows for over-allocation over all time units, as long as there is no over-allocation at an individual time unit.)
  • Supports specifying alignment requirements
  • Supports resizing better than allocating a new segment and deallocating the old one
  • Actively maintained


Get this bounty!!!