135 lines
2.7 KiB
C++
135 lines
2.7 KiB
C++
/* 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;
|
|
}
|