Simple, self created, bidirectional and dynamic list in C++ - leant to the JavaScript array syntax

example.cpp

/*
    © 2018 - present Ringo Hoffmann (zekro Development)

    If you want to use this code, please read
    this first: https://zekro.de/policy

    With usage of this code or parts of it in
    any way, you agree to the terms above.
*/

include "list.h"

using namespace std;


int main() {

    // Creating an empty list object
    List<int> l;
    
    // Pushing some values into it
    l.push(new int[7] {4, 1, 5, 7, 2, 8, 9}, 7);
    
    // Output the result in console
    l.output();

    /*
        OUTPUT:
        0 [0000000000000000<-000001CEFD78CB80->000001CEFD78CD00] : 4
        1 [000001CEFD78CB80<-000001CEFD78CD00->000001CEFD78CD60] : 1
        2 [000001CEFD78CD00<-000001CEFD78CD60->000001CEFD78C7C0] : 5
        3 [000001CEFD78CD60<-000001CEFD78C7C0->000001CEFD78C820] : 7
        4 [000001CEFD78C7C0<-000001CEFD78C820->000001CEFD792C80] : 2
        5 [000001CEFD78C820<-000001CEFD792C80->000001CEFD792620] : 8
        6 [000001CEFD792C80<-000001CEFD792620->0000000000000000] : 9
    */

    // Insert new value at index 2 with value 12
    l.insert(2, 12);
    l.output();

    /*
        OUTPUT:
        0 [0000000000000000<-000001CEFD78CB80->000001CEFD78CD00] : 4
        1 [000001CEFD78CB80<-000001CEFD78CD00->000001CEFD792560] : 1
        2 [000001CEFD78CD00<-000001CEFD792560->000001CEFD78CD60] : 12
        3 [000001CEFD792560<-000001CEFD78CD60->000001CEFD78C7C0] : 5
        4 [000001CEFD78CD60<-000001CEFD78C7C0->000001CEFD78C820] : 7
        5 [000001CEFD78C7C0<-000001CEFD78C820->000001CEFD792C80] : 2
        6 [000001CEFD78C820<-000001CEFD792C80->000001CEFD792620] : 8
        7 [000001CEFD792C80<-000001CEFD792620->0000000000000000] : 9
    */

    // I don't like value at index 5, so remove it ;)
    l.remove(5);
    l.output();

    /*
        OUTPUT:
        0 [0000000000000000<-000001CEFD78CB80->000001CEFD78CD00] : 4
        1 [000001CEFD78CB80<-000001CEFD78CD00->000001CEFD792560] : 1
        2 [000001CEFD78CD00<-000001CEFD792560->000001CEFD78CD60] : 12
        3 [000001CEFD792560<-000001CEFD78CD60->000001CEFD78C7C0] : 5
        4 [000001CEFD78CD60<-000001CEFD78C7C0->000001CEFD792C80] : 7
        5 [000001CEFD78C7C0<-000001CEFD792C80->000001CEFD792620] : 8
        6 [000001CEFD792C80<-000001CEFD792620->0000000000000000] : 9
    */

    // Now, bring some order into this ^^
    l.sort([](int a, int b) { return a > b; });
    l.output();

    /*
        OUTPUT:
        0 [0000000000000000<-000001CEFD7921A0->000001CEFD792140] : 1
        1 [0000000000000000<-000001CEFD792140->000001CEFD792A40] : 4
        2 [0000000000000000<-000001CEFD792A40->000001CEFD792D40] : 5
        3 [0000000000000000<-000001CEFD792D40->000001CEFD792800] : 7
        4 [0000000000000000<-000001CEFD792800->000001CEFD7925C0] : 8
        5 [0000000000000000<-000001CEFD7925C0->000001CEFD792680] : 9
        6 [0000000000000000<-000001CEFD792680->0000000000000000] : 12
    */

    // Also some filtering is possible
    //        value ↓      ↓ index
    l.filter([](int v, int i) { 
        return v % 2 == 0;
    }).output();
    // The filter functions returns a new list to don't mess
    // up the old one, so here the output after the function ;)

    /*
        OUTPUT:
        0 [0000000000000000<-000001CEFD792860->000001CEFD792320] : 4
        1 [000001CEFD792860<-000001CEFD792320->000001CEFD7928C0] : 8
        2 [000001CEFD792320<-000001CEFD7928C0->0000000000000000] : 12
    */

    // Or do some mapping
    l.map([](int v, int i) {
        return v * v;
    }).output();
    // same here as above, returning new list

    /*
        OUTPUT:
        0 [0000000000000000<-000001CEFD792200->000001CEFD7926E0] : 1
        1 [000001CEFD792200<-000001CEFD7926E0->000001CEFD792440] : 16
        2 [000001CEFD7926E0<-000001CEFD792440->000001CEFD792FE0] : 25
        3 [000001CEFD792440<-000001CEFD792FE0->000001CEFD792740] : 49
        4 [000001CEFD792FE0<-000001CEFD792740->000001CEFD7927A0] : 64
        5 [000001CEFD792740<-000001CEFD7927A0->000001CEFD793040] : 81
        6 [000001CEFD7927A0<-000001CEFD793040->0000000000000000] : 144
    */

    // Also some forEach loops are possible ;)
    l.forEach([](int v, int i) {
        printf("At index %i, there is value %i\n", i, v);
    });

    /*
        OUTPUT:
        At index 0, there is value 1
        At index 1, there is value 4
        At index 2, there is value 5
        At index 3, there is value 7
        At index 4, there is value 8
        At index 5, there is value 9
        At index 6, there is value 12
    */
}

list.h

#pragma once

#include <iostream>
#include <functional>

using namespace std;


/*
    Just an exception type to throw if index of element
    selected in list is out of bounds.
    Source: http://www.cplusplus.com/doc/tutorial/exceptions/
*/
class IndexOutOfBoundsException : public exception {
    virtual const char* what() const throw() {
        return "Specified index of element in list is out of bounds.";
    }
};


/*
    List element containing value,
    next elements and previous elements
    pointer.
*/
template <typename T>
class Element {

public:
    // Constructor
    Element(const T &value, Element *prev = 0, Element *next = 0) {
        m_value = value;
        m_prev = prev;
        m_next = next;
    }

    // Destructor
    ~Element() {}

    // Getter
    T        value() { return m_value; }
    Element  *next() { return m_next; }
    Element  *prev() { return m_prev; }

    // Setter
    void setValue(T value) { m_value = value; }
    void setNext(Element *next) { m_next = next; }
    void setPrev(Element *prev) { m_prev = prev; }

    // Other
    bool hasNext() { return m_next != 0; }
    bool hasPrev() { return m_prev != 0; }


private:
    // Elements value
    T       m_value;
    // Next elements pointer
    Element *m_prev;
    // Previous elements pointer
    Element *m_next;

};


/*
    Create a list.

    @param (*start) Pointer to start Element (defaultly 0)
*/
template <typename T>
class List {

public:
    // Constructor
    List(Element<T> *start = 0) {
        m_start = start;
    }

    // Destructor
    ~List() {}

    /*
        Add one element at the end of the list.

        @param inpt Value of appended element
    */
    void push(const T &inpt) {
        if (m_start == 0)
            m_start = new Element<T>(inpt);
        else {
            /*
                Searching for next element until this has
                no next element (= last element), then set
                its next element to a new element with previous
                element is the current element and the new value.
            */
            Element<T> *curr = m_start;
            while (curr->hasNext())
                curr = curr->next();
            curr->setNext(new Element<T>(inpt, curr));
        }
    }

    /*
        Overload of push with array of values.

        @param inpt[] Array of values to push
        @param size   Numer of values in array to push
    */
    void push(const T inpt[], int size) {
        for (int i = 0; i < size; i++)
            push(inpt[i]);
    }

    /*
        Get number of elements in the list.

        @returns length
    */
    int length() {
        int counter = 0;
        Element<T> *curr = m_start;
        if (curr == 0)
            return 0;
        do {
            curr = curr->next();
            counter++;
        } while (curr != 0);
        return counter;
    }

    /*
        Get elements value at specific point in
        list chain.

        @param   (index) index of element (defaultly 0)
        @returns value of element of specified index
    */
    T get(int index = 0) {
        if (index < 0)
            throw new IndexOutOfBoundsException;
        if (index == 0)
            return m_start->value();
        else {
            return m_getElement(index)->value();
        }
    }

    /*
        Creates an console output for every element in list
        like following:
        INDEX [PREVIIOUSADDR<-CURRENTADDR->NEXTADDR]: VALUE
    */
    void output() {
        Element<T> *curr = m_start;
        int index = 0;
        while (curr != 0) {
            cout << index++ << " [" << curr->prev() << "<-" << curr << "->" << curr->next() << "] : " << curr->value() << endl;
            curr = curr->next();
        }
        cout << "----------------------------------\n";
    }

    /*
        Reverse the current list.
    */
    void reverse() {
        Element<T> *curr = m_start;
        while (curr != 0) {
            Element<T> *tmp = curr->next();
            curr->setNext(curr->prev());
            curr->setPrev(tmp);
            curr = curr->prev();
            if (curr != 0)
                m_start = curr;
        }
    }

    /*
        Insert a value after a specific position
        in list.

        @param index index where to insert after
        @param value value of new element to insert
    */
    void insert(int index, const T &value) {
        if (m_start == 0)
            m_start = new Element<T>(value);
        else
            m_insert(m_getElement(index), value);
    }

    /*
        Remove a specific element from list by index.

        @param index index of element to delete
    */
    void remove(int index = 0) {
        m_remove(m_getElement(index));
    }

    /*
        Deletes and returns the value of the last 
        element of the list.
        
        @returns Value of last element of the list
    */
    T pop() {
        Element<T> *curr = m_start;
        while (curr->next() != 0)
            curr = curr->next();
        T out = curr->value();
        if (curr->hasPrev())
            curr->prev()->setNext(0);
        else
            m_start = 0;
        delete curr;
        return out;
    }

    /*
        Deletes and returns the value of the first 
        element of the list.
        
        @returns Value of first element of the list 
    */
    T shift() {
        Element<T> *curr = m_start;
        if (curr->hasNext()) {
            curr->next()->setPrev(0);
            m_start = curr->next();
        }
        else
            m_start = 0;
        T out = curr->value();
        delete curr;
        return out;
    }

    /*
        Sort list with specified filter method.
        [SHOULD NOT BE BUGGY ANYMORE :^)]

        @param filter Filter function returning boolean
    */
    void sort(function<bool(T a, T b)> filter) {
        
        List<T> finished;

        while (m_start != 0) {
            Element<T> *curr = m_start;
            Element<T> *top = 0;

            while (curr != 0) {
                if (top == 0 || filter(curr->value(), top->value()))
                    top = curr;
                curr = curr->next();
            }
            finished.insert(0, top->value());
            m_remove(top);
        }

        m_start = finished.m_start;
    }

    /*
        Returns if list's elements containing
        specified value.

        @param   v Value to find
        @returns true if value was found
    */
    bool contains(T v) {
        Element<T> *curr = m_start;
        while (curr != 0) {
            if (curr->value() == v)
                return true;
            curr = curr->next();
        }
        return false;
    }

    /*
        Returns a new list with values between
        index a and b. If b is not set, only
        the list will besliced at the beginning.

        @param   a start index after
        @param   b end index
        @returns new sliced list
    */
    List<T> slice(int a, int b = -1) {
        Element<T> *curr = m_start;
        List<T> out;
        int counter = 0;

        while (curr != 0) {
            if (counter >= a && (counter < b || b < 0))
                out.push(curr->value());
            curr = curr->next();
            ++counter;
        }

        return out;
    }

    /*
        Returns a new list, filtered by the passed 
        pattern function.

        @param   pattern Pattern function returning boolean
        @returns new filtered list
    */
    List<T> filter(function<bool(T a, int index)> pattern) {
        List<T> out;
        Element<T> *curr = m_start;
        int index = 0;

        while (curr != 0) {
            T val = curr->value();
            if (pattern(val, index++))
                out.push(val);
            curr = curr->next();
        }

        return out;
    }

    /*
        Returns a new list, mapped with the passed
        pattern function.

        @param   pattern Pattern function returning value type T
        @returns new mapped list
    */
    List<T> map(function<T(T a, int index)> pattern) {
        List<T> out;
        Element<T> *curr = m_start;
        int index = 0;

        while (curr != 0) {
            out.push(pattern(curr->value(), index++));
            curr = curr->next();
        }

        return out;
    }

    /*
        Executes the passed function for every element.

        @param   function to execute
    */
    void forEach(function<void(T a, int index)> exec) {
        Element<T> *curr = m_start;
        int index = 0;

        while (curr != 0) {
            exec(curr->value(), index++);
            curr = curr->next();
        }
    }

    /*
        Swap specified entity with its next element.

        @param index index of element to swap with next one
    */
    void swap(int index) {
        m_swap(m_getElement(index));
    }


private:
    // Start element
    Element<T> * m_start;

    /*
        Get element by index in list.

        @param   index
        @returns element
    */
    Element<T> *m_getElement(int index) {
        Element<T> *curr = m_start;
        for (int i = 0; i < index; i++) {
            if (curr->hasNext())
                curr = curr->next();
            else
                throw new IndexOutOfBoundsException;
        }
        return curr;
    }

    /*
        Swap element with next element.

        @param curr element to swap
    */
    void m_swap(Element<T> *curr) {
        if (!curr->hasNext())
            return;
        T tmp = curr->value();
        m_remove(curr);
        m_insert(curr->next(), tmp);
    }

    /*
        Remove specified element from list.

        @param rem elment to remove
    */
    void m_remove(Element<T> *rem) {
        if (rem->hasNext())
            rem->next()->setPrev(rem->prev());
        else
            rem->setNext(0);

        if (rem->hasPrev())
            rem->prev()->setNext(rem->next());
        else
            m_start = rem->next();

        rem->~Element();
    }

    /*
        Intert element after specified element.

        @param before element where to insert after
        @param value  value to insert
    */
    void m_insert(Element<T> *curr, const T &value) {

        Element<T> *before = 0;
        if (curr->hasPrev()) {
            before = curr->prev();
        }

        Element<T> *newelem = new Element<T>(value, before, curr);

        if (before == 0)
            m_start = newelem;
        else {
            before->setNext(newelem);
            curr->setPrev(newelem);
        }
    }
};