List iterative filtering derived from list recursive filtering

main.cpp

#include <iostream>
#include <functional>

#include <vld.h>

using namespace std;

template <typename T>
struct Node {
    T mInfo;
    Node<T> *mNext;

    Node(T info, Node<T> *next)
        : mInfo(info), mNext(next) {}
};

template <typename T>
Node<T> *push(Node<T> *head, T value) {
    return new Node(value, head);    
}

template <typename T>
void foreach(Node<T> *head, function<void(T)> action) {
    if (nullptr == head) {
        return;
    } else {
        action(head->mInfo);
        foreach(head->mNext, action);
    }
}

template <typename T>
Node<T> *filterInPlace(Node<T> *head, function<bool(T)> pred) {
    if (nullptr == head) {
        return head;
    } else {
        if (pred(head->mInfo)) {
            head->mNext = filterInPlace(head->mNext, pred);
            return head;
        } else {
            auto result = filterInPlace(head->mNext, pred);
            delete head;
            return result;
        }
    }
}

template <typename T>
Node<T> *filterInPlace3(Node<T> *head, function<bool(T)> pred, Node<T> *origHead, Node<T> *prev) {    
    if (nullptr == head) {
        return origHead;
    } else {
        //cout << "fip3 " << head->mInfo << endl;
        if (pred(head->mInfo)) {
            return filterInPlace3(head->mNext, pred, origHead, head);
        } else {
            auto aux = head->mNext;
            if (head == origHead) {
                origHead = aux;
            }
            delete head;
            if (nullptr != prev) {
                prev->mNext = aux;
            }
            return filterInPlace3(aux, pred, origHead, prev);
        }
    }
}

template <typename T>
Node<T> *filterInPlace2(Node<T> *head, function<bool(T)> pred) {
    return filterInPlace3<T>(head, pred, head, nullptr);
}

template <typename T>
Node<T> *filterInPlace4(Node<T> *head, function<bool(T)> pred) {
    auto origHead = head;
    Node<T> *prev = nullptr;
    while (nullptr != head) {
        if (pred(head->mInfo)) {
            prev = head;
            head = head->mNext;
        } else {
            auto aux = head->mNext;
            if (head == origHead) {
                origHead = aux;
            }
            delete head;
            if (nullptr != prev) {
                prev->mNext = aux;
            }
            head = aux;
        }
    }
    return origHead;
}

template <typename T>
void clear(Node<T> *head) {
    if (nullptr != head) {
        clear(head->mNext);
        delete head;
    }
}

template <typename T>
void dump(Node<T> *head) {
    foreach<T>(head, [](T elt) { cout << elt << " "; });
    cout << endl;
}

template <typename T>
Node<T> *fill(T values[], size_t offset, size_t count) {
    if (0 == count) {
        return nullptr;
    } else {
        return new Node<T>(values[offset], fill(values, offset + 1, count - 1));
    }
}

int main(int argc, char* argv[])
{
    int values[] = { -2, 10, 20, 50, -30, 3 };
    auto list = fill<int>(values, 0, sizeof(values) / sizeof(values[0]));
    list = filterInPlace4<int>(list, [](int elt) { return elt >= 0; });
    dump(list);
    clear(list);
    return 0;
}