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) {
  // Exhausted traversal retains its cursor object; end() has no cursor.
  const auto* value1 = x1.m_Node ? x1.m_Node->value : nullptr;
  const auto* value2 = x2.m_Node ? x2.m_Node->value : nullptr;
  return value1 == value2;
}
 
#endif