From 4359caa3ca15c75c4241d869259af3be8cc8375f Mon Sep 17 00:00:00 2001 From: Aryadev Chavali Date: Mon, 29 Apr 2024 15:43:17 +0530 Subject: Moved implementations to folder --- impls/list.cpp | 134 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 134 insertions(+) create mode 100644 impls/list.cpp (limited to 'impls/list.cpp') diff --git a/impls/list.cpp b/impls/list.cpp new file mode 100644 index 0000000..b87a3e2 --- /dev/null +++ b/impls/list.cpp @@ -0,0 +1,134 @@ +/* list.cpp + * Date: 2021-11-20 + * Author: Aryadev Chavali + */ + +#include +#include +#include + +template +struct List +{ + T value; + List *next; + + List(T val, List *n) + { + value = val; + next = n; + } + + ~List() + { + if (next == nullptr) + return; + delete next; + } +}; + +template +List *append(List *lst, T value) +{ + List *node; + if (lst == nullptr) + return new List(value, nullptr); + + for (node = lst; node->next != nullptr; node = node->next) + continue; + + node->next = new List(value, nullptr); + return lst; +} + +/** Reverse a list + */ +template +List *reverse(List *lst, List *prev = nullptr) +{ + auto next = lst->next; + lst->next = prev; + if (next == nullptr) + return lst; + return reverse(next, lst); +} + +template +List *map(List *lst, U (*f)(T)) +{ + if (!lst) + return nullptr; + return new List(f(lst->value), map(lst->next, f)); +} + +template +T reduce(List *lst, T (*reducer)(T, T), T init = 0) +{ + if (!lst) + return init; + else if (!init) + init = lst->value; + else + init = reducer(init, lst->value); + return reduce(lst->next, reducer, init); +} + +template +List *filter(List *lst, bool (*f)(T), List *new_lst = nullptr) +{ + if (!lst) + return new_lst; + if (f(lst->value)) + new_lst = append(new_lst, lst->value); + return filter(lst->next, f, new_lst); +} + +template +std::ostream &operator<<(std::ostream &ostream, const List *lst) +{ + if (!lst) + return ostream; + ostream << "|" << lst->value << lst->next; + return ostream; +} + +int main(void) +{ + puts("Create linked list with 1..10"); + auto lst = append(nullptr, 1); + for (int i = 2; i <= 10; ++i) + lst = append(lst, i); + printf("Current output for list: "); + std::cout << lst << std::endl; + lst = reverse(lst); + printf("Reverse list: "); + std::cout << lst << std::endl; + puts("Reverse list again..."); + printf("Map list with f(x) = 2x: "); + auto mapped = map(lst = reverse(lst), + [](int x) + { + return x * 2; + }); + std::cout << mapped << std::endl; + delete mapped; + printf("Sum all numbers in list: "); + std::cout << reduce( + lst, + [](int a, int b) + { + return a + b; + }, + 0) + << std::endl; + printf("Print all even numbers 1..10: "); + auto evens = filter(lst, + [](int a) + { + return a % 2 == 0; + }); + std::cout << evens << std::endl; + delete lst; + delete evens; + return 0; +} -- cgit v1.2.3-13-gbd6f