add: graphs et rushs

6 files changed, 208 insertions, 0 deletions

diff --git a/graphs/cpp/doubly_linked_list/CMakeLists.txt b/graphs/cpp/doubly_linked_list/CMakeLists.txt
new file mode 100644
index 0000000..37204f6
--- /dev/null
+++ b/graphs/cpp/doubly_linked_list/CMakeLists.txt
@@ -0,0 +1,8 @@
+cmake_minimum_required(VERSION 3.21.2)
+project(doubly_linked_list)
+
+add_library(doubly_linked_list SHARED node.cc list.cc)
+target_compile_options(doubly_linked_list PRIVATE -Wall -Wextra -Werror -pedantic -std=c++20 -Wold-style-cast)
+set_target_properties(doubly_linked_list PROPERTIES
+        CXX_STANDARD 20
+        CXX_EXTENSIONS OFF)
\ No newline at end of file
diff --git a/graphs/cpp/doubly_linked_list/list.cc b/graphs/cpp/doubly_linked_list/list.cc
new file mode 100644
index 0000000..36cf5ad
--- /dev/null
+++ b/graphs/cpp/doubly_linked_list/list.cc
@@ -0,0 +1,88 @@
+#include "list.hh"
+List::List()
+    : nb_elts_{ 0 }
+{}
+void List::push_front(int i)
+{
+    nb_elts_++;
+    if (nb_elts_ == 1)
+    {
+        first_ = std::make_shared<Node>(i);
+        last_ = first_;
+        return;
+    }
+    std::shared_ptr<Node> ns = std::make_shared<Node>(i);
+    ns->set_next(first_);
+    first_->set_prev(ns);
+    first_ = ns;
+}
+std::optional<int> List::pop_front()
+{
+    if (nb_elts_ == 0)
+    {
+        return std::nullopt;
+    }
+    nb_elts_--;
+    int res = first_->get_val();
+    if (nb_elts_ == 0)
+    {
+        first_ = nullptr;
+        last_ = nullptr;
+        return res;
+    }
+    std::shared_ptr<Node> tmp = first_->get_next();
+    first_->set_next(nullptr);
+    tmp->set_prev(nullptr);
+    first_ = tmp;
+    return res;
+}
+void List::push_back(int i)
+{
+    nb_elts_++;
+    if (nb_elts_ == 1)
+    {
+        first_ = std::make_shared<Node>(i);
+        last_ = first_;
+        return;
+    }
+    std::shared_ptr<Node> ns = std::make_shared<Node>(i);
+    ns->set_prev(last_);
+    last_->set_next(ns);
+    last_ = ns;
+}
+std::optional<int> List::pop_back()
+{
+    if (nb_elts_ == 0)
+    {
+        return std::nullopt;
+    }
+    nb_elts_--;
+    int res = last_->get_val();
+    if (nb_elts_ == 0)
+    {
+        first_ = nullptr;
+        last_ = nullptr;
+        return res;
+    }
+    std::shared_ptr<Node> tmp = last_->get_prev();
+    last_->set_prev(nullptr);
+    tmp->set_next(nullptr);
+    last_ = tmp;
+    return res;
+}
+void List::print(std::ostream& os) const
+{
+    if (nb_elts_ == 0)
+        return;
+    os << first_->get_val();
+    for (Node* node = first_->get_next().get(); node;
+         node = node->get_next().get())
+    {
+        os << " " << node->get_val();
+    }
+    // os << "\n";
+}
+size_t List::length() const
+{
+    return nb_elts_;
+}
\ No newline at end of file
diff --git a/graphs/cpp/doubly_linked_list/list.hh b/graphs/cpp/doubly_linked_list/list.hh
new file mode 100644
index 0000000..50f71c6
--- /dev/null
+++ b/graphs/cpp/doubly_linked_list/list.hh
@@ -0,0 +1,24 @@
+#pragma once
+
+#include <optional>
+#include <ostream>
+
+#include "node.hh"
+
+class List
+{
+public:
+    List();
+
+    void push_front(int i);
+    void push_back(int i);
+    std::optional<int> pop_front();
+    std::optional<int> pop_back();
+    void print(std::ostream& os) const;
+    size_t length() const;
+
+private:
+    size_t nb_elts_;
+    std::shared_ptr<Node> first_;
+    std::shared_ptr<Node> last_;
+};
diff --git a/graphs/cpp/doubly_linked_list/main.cc b/graphs/cpp/doubly_linked_list/main.cc
new file mode 100644
index 0000000..cd9ab32
--- /dev/null
+++ b/graphs/cpp/doubly_linked_list/main.cc
@@ -0,0 +1,36 @@
+#include <iostream>
+
+#include "list.hh"
+
+int main()
+{
+    List l = List();
+    l.print(std::cout);
+    std::cout << '\n';
+
+    l.push_back(13);
+    l.print(std::cout);
+    std::cout << '\n';
+
+    l.push_front(5);
+    l.print(std::cout);
+    std::cout << '\n';
+
+    l.push_back(42);
+    l.print(std::cout);
+    std::cout << '\n';
+
+    l.pop_back();
+    l.print(std::cout);
+    std::cout << '\n';
+
+    l.push_back(42);
+    l.print(std::cout);
+    std::cout << '\n';
+
+    l.pop_front();
+    l.print(std::cout);
+    std::cout << '\n';
+
+    std::cout << "Nb elts: " << l.length() << '\n';
+}
diff --git a/graphs/cpp/doubly_linked_list/node.cc b/graphs/cpp/doubly_linked_list/node.cc
new file mode 100644
index 0000000..b6db962
--- /dev/null
+++ b/graphs/cpp/doubly_linked_list/node.cc
@@ -0,0 +1,29 @@
+#include "node.hh"
+
+Node::Node(int v)
+    : val_{ v }
+{}
+int Node::get_val() const
+{
+    return val_;
+}
+void Node::set_val(int val)
+{
+    val_ = val;
+}
+std::shared_ptr<Node> Node::get_next() const
+{
+    return next_;
+}
+void Node::set_next(std::shared_ptr<Node> next)
+{
+    next_ = next;
+}
+std::shared_ptr<Node> Node::get_prev() const
+{
+    return prev_.lock();
+}
+void Node::set_prev(std::shared_ptr<Node> prev)
+{
+    prev_ = prev;
+}
\ No newline at end of file
diff --git a/graphs/cpp/doubly_linked_list/node.hh b/graphs/cpp/doubly_linked_list/node.hh
new file mode 100644
index 0000000..9eb2e50
--- /dev/null
+++ b/graphs/cpp/doubly_linked_list/node.hh
@@ -0,0 +1,23 @@
+#pragma once
+
+#include <memory>
+
+class Node
+{
+public:
+    Node(int v);
+
+    int get_val() const;
+    void set_val(int val);
+
+    std::shared_ptr<Node> get_next() const;
+    void set_next(std::shared_ptr<Node> next);
+
+    std::shared_ptr<Node> get_prev() const;
+    void set_prev(std::shared_ptr<Node> prev);
+
+private:
+    int val_;
+    std::shared_ptr<Node> next_;
+    std::weak_ptr<Node> prev_;
+};