From c9b6b9a5ca082fe7c1b6f58d7713f785a9eb6a5c Mon Sep 17 00:00:00 2001 From: Martial Simon Date: Mon, 15 Sep 2025 01:08:27 +0200 Subject: add: graphs et rushs --- graphs/cpp/doubly_linked_list/CMakeLists.txt | 8 +++ graphs/cpp/doubly_linked_list/list.cc | 88 ++++++++++++++++++++++++++++ graphs/cpp/doubly_linked_list/list.hh | 24 ++++++++ graphs/cpp/doubly_linked_list/main.cc | 36 ++++++++++++ graphs/cpp/doubly_linked_list/node.cc | 29 +++++++++ graphs/cpp/doubly_linked_list/node.hh | 23 ++++++++ 6 files changed, 208 insertions(+) create mode 100644 graphs/cpp/doubly_linked_list/CMakeLists.txt create mode 100644 graphs/cpp/doubly_linked_list/list.cc create mode 100644 graphs/cpp/doubly_linked_list/list.hh create mode 100644 graphs/cpp/doubly_linked_list/main.cc create mode 100644 graphs/cpp/doubly_linked_list/node.cc create mode 100644 graphs/cpp/doubly_linked_list/node.hh (limited to 'graphs/cpp/doubly_linked_list') 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(i); + last_ = first_; + return; + } + std::shared_ptr ns = std::make_shared(i); + ns->set_next(first_); + first_->set_prev(ns); + first_ = ns; +} +std::optional 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 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(i); + last_ = first_; + return; + } + std::shared_ptr ns = std::make_shared(i); + ns->set_prev(last_); + last_->set_next(ns); + last_ = ns; +} +std::optional 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 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 +#include + +#include "node.hh" + +class List +{ +public: + List(); + + void push_front(int i); + void push_back(int i); + std::optional pop_front(); + std::optional pop_back(); + void print(std::ostream& os) const; + size_t length() const; + +private: + size_t nb_elts_; + std::shared_ptr first_; + std::shared_ptr 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 + +#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::get_next() const +{ + return next_; +} +void Node::set_next(std::shared_ptr next) +{ + next_ = next; +} +std::shared_ptr Node::get_prev() const +{ + return prev_.lock(); +} +void Node::set_prev(std::shared_ptr 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 + +class Node +{ +public: + Node(int v); + + int get_val() const; + void set_val(int val); + + std::shared_ptr get_next() const; + void set_next(std::shared_ptr next); + + std::shared_ptr get_prev() const; + void set_prev(std::shared_ptr prev); + +private: + int val_; + std::shared_ptr next_; + std::weak_ptr prev_; +}; -- cgit v1.2.3