arkadye's smart linked list

// smartlinkedlist.h

#include <functional>
#include <mutex>
#include <vector>

template<typename Type , typename Compare = std::less<Type>>
class SmartList
{
private:
    class Node
    {
        Type value;
        Node* nextNewest;
        Node* nextBiggest;
    public:
        Node(Type val, Node* newest, Node* bigger) : value(val), nextNewest(newest), nextBiggest(bigger) {}
        Type getValue() const { return value; }
        Node* getNextBiggest() const { return nextBiggest; }
        Node* getNextNewest() const { return nextNewest; }
        void setNextBiggest(Node* nb) { nextBiggest = nb; }
        void setNextNewest(Node* nn) { nextNewest = nn; }
    };

    Compare cmpFn;
    Node* smallest;
    Node* newest;
    mutable std::mutex lock;

    Node* getLargestSmallerThan(const Type& val)
    {
        if (smallest == nullptr || greatereq(smallest->getValue(),val))
            return nullptr;
        auto currentNode = smallest;
        while (true)
        {
            auto next = currentNode->getNextBiggest();
            if (next == nullptr)
                return currentNode;
            if (greatereq(next->getValue(), val))
                return currentNode;
            currentNode = currentNode->getNextBiggest();
        }
    }

    bool less(Type x, Type y) const { return cmpFn(x, y); }
    bool greatereq(Type x, Type y) const { return !cmpFn(x, y); }
    bool greater(Type x, Type y) const { return cmpFn(y, x); }
    bool lesseq(Type x, Type y) const { return !cmpFn(y, x); }
    SmartList&& buildCopy() const
    {
        auto items = getStack();
        SmartList copy;
        for (auto it = rbegin(items); it < rend(items); ++it)
        {
            copy.push(*it);
        }
        return std::move(copy);
    }
public:
    SmartList(Compare comparisonFunction = std::less<Type>()) : cmpFn(comparisonFunction), smallest(nullptr), newest(nullptr) {}
    SmartList(SmartList&& list) : cmpFn(list.cmpFn), smallest(list.smallest), newest(list.newest)
    {
        list.smallest = nullptr;
        list.newest = nullptr;
    }
    SmartList(const SmartList& list) : SmartList(buildCopy()) {}
    ~SmartList()
    {
        auto current = newest;
        while (current != nullptr)
        {
            auto next = current->getNextNewest();
            delete current;
            current = next;
        }
    }

    void push(const Type& val)
    {
        std::lock_guard<std::mutex> guard(lock);
        auto nextSmallest = getLargestSmallerThan(val);
        auto nextBiggest = nextSmallest == nullptr ? smallest : nextSmallest->getNextBiggest();
        auto newNode = new Node(val, newest, nextBiggest);
        if (nextSmallest != nullptr)
        {
            nextSmallest->setNextBiggest(newNode);
        }
        else
        {
            smallest = newNode;
        }
        newest = newNode;
    }

    Type pop()
    {
        std::lock_guard<std::mutex> guard(lock);
        Type ret = newest->getValue();
        auto nextSmallest = getLargestSmallerThan(ret);
        if (nextSmallest != nullptr)
        {
            nextSmallest->setNextBiggest(newest->getNextBiggest());
        }
        else
        {
            smallest = smallest->getNextBiggest();
        }
        auto newNewest = newest->getNextNewest();
        delete newest;
        newest = newNewest;
        return ret;
    }

    size_t size() const
    {
        std::lock_guard<std::mutex> guard(lock);
        auto current = newest;
        size_t size = 0;
        while (current != nullptr)
        {
            current = current->getNextNewest();
            ++size;
        }
        return size;
    }

    Type head() const
    {
        return newest->getValue();
    }

    void removeGreater(const Type& val)
    {
        std::lock_guard<std::mutex> guard(lock);
        if (smallest == nullptr) // There is nothing to be removed.
        {
            return;
        }
        auto newLargest = smallest;
        while (true)
        {
            auto nextLargest = newLargest->getNextBiggest();
            if (nextLargest == nullptr) // No values are removed.
            {
                return;
            }
            if (greater(nextLargest->getValue(), val))
            {
                break;
            }
            newLargest = nextLargest;
        }
        newLargest->setNextBiggest(nullptr);

        // Now go through and remove all the values.
        auto current = newest;

        // First find the new newest value.
        while (current != nullptr && greater(current->getValue(), val))
        {
            newest = current->getNextNewest();
            delete current;
            current = newest;
        }

        // Now go remove the rest of them.
        while (current != nullptr && current->getNextNewest() != nullptr)
        {
            auto next = current->getNextNewest();
            if (greater(next->getValue(), val))
            {
                current->setNextNewest(next->getNextNewest());
                delete next;
            }
            else
            {
                current = next;
            }
        }
        return;
    }

    std::vector<Type> getStack() const
    {
        std::lock_guard<std::mutex> guard(lock);
        auto current = newest;
        std::vector<Type> ret;
        while (current != nullptr)
        {
            ret.push_back(current->getValue());
            current = current->getNextNewest();
        }
        return ret;
    }

    std::vector<Type> getSorted() const
    {
        std::lock_guard<std::mutex> guard(lock);
        auto current = smallest;
        std::vector<Type> ret;
        while (current != nullptr)
        {
            ret.push_back(current->getValue());
            current = current->getNextBiggest();
        }
        return ret;
    }
};

// main.cpp

#include <random>
#include <iostream>
#include <chrono>

//#include "smartlinkedlist.h"

std::default_random_engine generator;

int getRandomNumber(int min, int max)
{
    std::uniform_int_distribution<int> n_maker(min, max);
    return n_maker(generator);
}

template <typename Container>
void displayContainer(const Container& in)
{
    for (const auto& val : in)
    {
        std::cout << val << '\n';
    }
    return;
}

template <class List>
void viewList(const List& list)
{
    std::cout << "Stack view:\n";
    displayContainer(list.getStack());
    std::cout << "\nSorted view:\n";
    displayContainer(list.getSorted());
}

int main()
{
    generator.seed(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count());
    const int n = getRandomNumber(1, 40);
    SmartList<int> list;

    std::cout << "Setup list with size " << n << '\n';
    for (int i(0); i<n; ++i)
    {
        const auto value = getRandomNumber(-1000, 1000);
        std::cout << "Push value " << value << '\n';
        list.push(value);
    }

    std::cout << "Start\n";
    viewList(list);

    const auto threshold = getRandomNumber(-1000, 1000);
    std::cout << "Remove greater than " << threshold << '\n';
    list.removeGreater(threshold);
    viewList(list);

    std::cout << "Pop half\n";
    const int size = list.size();
    for (int i(0); i<size / 2; ++i)
    {
        std::cout << "Popped value " << list.pop() << '\n';
    }

    viewList(list);
    std::cin.get();
    return 0;
}