Iterator.h

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#ifndef KERNEL_UTILITIES_ITERATOR_H
#define KERNEL_UTILITIES_ITERATOR_H

#include "pedigree/kernel/utilities/cpp.h"
#include "pedigree/kernel/utilities/template.h"

template <
    typename originalT, class Struct,
    Struct *(Struct::*FunctionPrev)() = &Struct::previous,
    Struct *(Struct::*FunctionNext)() = &Struct::next, typename T = originalT>
class Iterator
{
    template <
        typename _originalT, class _Struct,
        _Struct *(_Struct::*_FunctionPrev)(),
        _Struct *(_Struct::*_FunctionNext)(), typename _T>
    friend class Iterator;

    template <
        typename _originalT, class _Struct,
        _Struct *(_Struct::*_FunctionPrev)(),
        _Struct *(_Struct::*_FunctionNext)(), typename _T1, typename _T2>
    friend bool operator==(
        const Iterator<_originalT, _Struct, _FunctionPrev, _FunctionNext, _T1>
            &x1,
        const Iterator<_originalT, _Struct, _FunctionPrev, _FunctionNext, _T2>
            &x2);

  public:
    typedef Iterator<originalT, Struct, FunctionPrev, FunctionNext, T const>
        Const;
    typedef Iterator<originalT, Struct, FunctionNext, FunctionPrev, T> Reverse;
    typedef Iterator<originalT, Struct, FunctionNext, FunctionPrev, T const>
        ConstReverse;

    Iterator() : m_Node(), m_Default()
    {
    }
    Iterator(const Iterator &x) : m_Node(x.m_Node), m_Default(x.m_Default)
    {
    }
    template <typename T2>
    Iterator(
        const Iterator<originalT, Struct, FunctionPrev, FunctionNext, T2> &x)
        : m_Node(x.m_Node), m_Default(x.m_Default)
    {
    }
    Iterator(Struct *Node) : m_Node(Node), m_Default()
    {
    }
    ~Iterator()
    {
    }

    Iterator &operator=(const Iterator &x)
    {
        m_Node = x.m_Node;
        m_Default = x.m_Default;
        return *this;
    }
    Iterator &operator++()
    {
        if (m_Node)
            m_Node = (m_Node->*FunctionNext)();
        return *this;
    }
    Iterator &operator--()
    {
        if (m_Node)
        {
            Struct *newNode = (m_Node->*FunctionPrev)();
            if (newNode)
                m_Node = newNode;
        }
        return *this;
    }
    T &operator*()
    {
        // Verify that we actually have a valid node
        if (m_Node)
            return m_Node->value;
        else
        {
            return m_Default;
        }
    }
    T &operator->()
    {
        return *this;
    }

    operator Const()
    {
        return Const(m_Node);
    }

    Struct *__getNode()
    {
        return m_Node;
    }

  protected:
    Struct *m_Node;
    T m_Default;
};

template <
    typename originalT, class Struct,
    Struct *(Struct::*FunctionPrev)() = &Struct::previous,
    Struct *(Struct::*FunctionNext)() = &Struct::next, typename K = originalT,
    typename T = originalT>
class TreeIterator
{
    template <
        typename _originalT, class _Struct,
        _Struct *(_Struct::*_FunctionPrev)(),
        _Struct *(_Struct::*_FunctionNext)(), typename _K, typename _T>
    friend class TreeIterator;

    template <
        typename _originalT, class _Struct,
        _Struct *(_Struct::*_FunctionPrev)(),
        _Struct *(_Struct::*_FunctionNext)(), typename _K1, typename _T1,
        typename _K2, typename _T2>
    friend bool operator==(
        const TreeIterator<
            _originalT, _Struct, _FunctionPrev, _FunctionNext, _K1, _T1> &x1,
        const TreeIterator<
            _originalT, _Struct, _FunctionPrev, _FunctionNext, _K2, _T2> &x2);

  public:
    typedef TreeIterator<
        originalT, Struct, FunctionPrev, FunctionNext, K, T const>
        Const;
    typedef TreeIterator<originalT, Struct, FunctionNext, FunctionPrev, K, T>
        Reverse;
    typedef TreeIterator<
        originalT, Struct, FunctionNext, FunctionPrev, K, T const>
        ConstReverse;

    TreeIterator() : m_Node()
    {
    }
    TreeIterator(const TreeIterator &x) : m_Node(x.m_Node)
    {
    }
    template <typename K2, typename T2>
    TreeIterator(const TreeIterator<
                 originalT, Struct, FunctionPrev, FunctionNext, K2, T2> &x)
        : m_Node(x.m_Node)
    {
    }
    TreeIterator(Struct *Node) : m_Node(Node)
    {
    }
    ~TreeIterator()
    {
    }

    TreeIterator &operator=(const TreeIterator &x)
    {
        m_Node = x.m_Node;
        return *this;
    }
    TreeIterator &operator++()
    {
        m_Node = (m_Node->*FunctionNext)();
        return *this;
    }
    TreeIterator &operator--()
    {
        m_Node = (m_Node->*FunctionPrev)();
        return *this;
    }
    T operator*()
    {
        return m_Node->value;
    }
    T operator->()
    {
        return m_Node->value;
    }

    operator Const()
    {
        return Const(m_Node);
    }

    Struct *__getNode()
    {
        return m_Node;
    }

    K key()
    {
        if (m_Node)
        {
            if (m_Node->value)
                return m_Node->value->key;
        }
        return 0;
    }

    T value()
    {
        if (m_Node)
        {
            if (m_Node->value)
                return m_Node->value->element;
        }
        return 0;
    }

    const T &value(const T &failed=T()) const
    {
        if (m_Node)
        {
            if (m_Node->value)
                return m_Node->value->element;
        }
        return failed;
    }

  protected:
    Struct *m_Node;
};

template <
    typename originalT, class Struct, Struct *(Struct::*FunctionPrev)(),
    Struct *(Struct::*FunctionNext)(), typename T1, typename T2>
bool operator==(
    const Iterator<originalT, Struct, FunctionPrev, FunctionNext, T1> &x1,
    const Iterator<originalT, Struct, FunctionPrev, FunctionNext, T2> &x2)
{
    if (x1.m_Node != x2.m_Node)
        return false;
    return true;
}

template <
    typename originalT, class Struct, Struct *(Struct::*FunctionPrev)(),
    Struct *(Struct::*FunctionNext)(), typename K1, typename T1, typename K2,
    typename T2>
bool operator==(
    const TreeIterator<originalT, Struct, FunctionPrev, FunctionNext, K1, T1>
        &x1,
    const TreeIterator<originalT, Struct, FunctionPrev, FunctionNext, K2, T2>
        &x2)
{
    if (!x2.m_Node)
    {
        if (!x1.m_Node)
            return false;
        else if (x1.m_Node->value)
            return false;
        return true;
    }
    return (x1.m_Node->value == x2.m_Node->value);
}

#endif