diff options
Diffstat (limited to 'impls/list.cpp')
-rw-r--r-- | impls/list.cpp | 134 |
1 files changed, 134 insertions, 0 deletions
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 <cstdio> +#include <cstdlib> +#include <iostream> + +template <typename T> +struct List +{ + T value; + List<T> *next; + + List(T val, List<T> *n) + { + value = val; + next = n; + } + + ~List() + { + if (next == nullptr) + return; + delete next; + } +}; + +template <typename T> +List<T> *append(List<T> *lst, T value) +{ + List<T> *node; + if (lst == nullptr) + return new List<T>(value, nullptr); + + for (node = lst; node->next != nullptr; node = node->next) + continue; + + node->next = new List<T>(value, nullptr); + return lst; +} + +/** Reverse a list + */ +template <typename T> +List<T> *reverse(List<T> *lst, List<T> *prev = nullptr) +{ + auto next = lst->next; + lst->next = prev; + if (next == nullptr) + return lst; + return reverse(next, lst); +} + +template <typename T, typename U> +List<U> *map(List<T> *lst, U (*f)(T)) +{ + if (!lst) + return nullptr; + return new List<U>(f(lst->value), map(lst->next, f)); +} + +template <typename T> +T reduce(List<T> *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 <typename T> +List<T> *filter(List<T> *lst, bool (*f)(T), List<T> *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 <typename T> +std::ostream &operator<<(std::ostream &ostream, const List<T> *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<int>(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<int, int>(lst = reverse(lst), + [](int x) + { + return x * 2; + }); + std::cout << mapped << std::endl; + delete mapped; + printf("Sum all numbers in list: "); + std::cout << reduce<int>( + lst, + [](int a, int b) + { + return a + b; + }, + 0) + << std::endl; + printf("Print all even numbers 1..10: "); + auto evens = filter<int>(lst, + [](int a) + { + return a % 2 == 0; + }); + std::cout << evens << std::endl; + delete lst; + delete evens; + return 0; +} |