#include <cstdio>
#include <memory>
#include <functional>

template <typename T>
struct Node
{
    Node(const T &t) { val = t; }
    ~Node() { printf("removing Node\n"); }
    T val;
    std::shared_ptr<Node> next;
};

template <typename T>
class List
{
public:
    List(bool _sorted = false) : sorted(_sorted) {}

    // this function switches the list back and forth
    // between sorted and unsorted
    void setSorted(bool _sorted = true)
    {
        if(!sorted && _sorted)
        {
            // quick! we need to sort everything!
            List list(true);
            applyNode( [&list](std::shared_ptr<Node<T> > node) { list.insert(node); } );
            head=list.head;
            tail=list.tail;
        }
        sorted = _sorted;
    }

    // this function inserts a new item in the list
    // while maintaining the sorted (or unsorted) property
    void insert(const T &t)
    {
        auto node=std::make_shared<Node<T> >(t);
        insert(node);
    }

    // apply each data point in list to function
    void apply(std::function<void(const T &)> fn)
    {
        for(auto ptr=head; ptr; ptr=ptr->next)
            fn(ptr->val);
    }

private:
    void applyNode(std::function<void(std::shared_ptr<Node<T> > node)> fn)
    {
        for(auto ptr=head; ptr;)
        {
            auto save=ptr->next; // in case fn changes next
            fn(ptr);
            ptr=save;
        }
    }

    void insert(std::shared_ptr<Node<T> > node)
    {
        node->next = std::shared_ptr<Node<T> >();

        auto ptr = &head;
        if(sorted) // place in appropriate location
        {
            for(; *ptr; ptr=&((*ptr)->next))
            {
                if(node->val < (*ptr)->val) // insert before ptr
                {
                    node->next = *ptr;
                    *ptr=node;
                    break;
                }
            }
        }

        if(!sorted || !*ptr) // place at end
        {
            if(!head)
                head=node;
            if(tail)
                tail->next = node;
            tail = node;
        }
    }

    bool sorted;
    std::shared_ptr<Node<T> > head;
    std::shared_ptr<Node<T> > tail;
};

int
main()
{
    List<int> list;
    
    printf("insert 4,1,3\n");
    list.insert(4);
    list.insert(1);
    list.insert(3);

    printf("unsorted:\n");
    list.apply( [](const int &i){ printf("%d\n", i); } );

    printf("sorted:\n");
    list.setSorted(true);
    list.apply( [](const int &i){ printf("%d\n", i); } );

    printf("insert 5,0,2\n");
    list.insert(5);
    list.insert(0);
    list.insert(2);
    list.apply( [](const int &i){ printf("%d\n", i); } );

    printf("set back to unsorted, insert -1, 6:\n");
    list.setSorted(false);
    list.insert(-1);
    list.insert(6);
    list.apply( [](const int &i){ printf("%d\n", i); } );

    printf("sorted:\n");
    list.setSorted(true);
    list.apply( [](const int &i){ printf("%d\n", i); } );
}