//===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator -------*- C++ -*-==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_ILIST_ITERATOR_H
#define LLVM_ADT_ILIST_ITERATOR_H

#include "llvm/ADT/ilist_node.h"
#include <cassert>
#include <cstddef>
#include <iterator>
#include <type_traits>

namespace llvm {

namespace ilist_detail {

template <class NodeTy> struct ConstCorrectNodeType {
  typedef ilist_node<NodeTy> type;
};
template <class NodeTy> struct ConstCorrectNodeType<const NodeTy> {
  typedef const ilist_node<NodeTy> type;
};

template <bool IsReverse = false> struct IteratorHelper {
  template <class T> static void increment(T *&I) {
    I = ilist_node_access::getNext(*I);
  }
  template <class T> static void decrement(T *&I) {
    I = ilist_node_access::getPrev(*I);
  }
};
template <> struct IteratorHelper<true> {
  template <class T> static void increment(T *&I) {
    IteratorHelper<false>::decrement(I);
  }
  template <class T> static void decrement(T *&I) {
    IteratorHelper<false>::increment(I);
  }
};

} // end namespace ilist_detail

/// Iterator for intrusive lists  based on ilist_node.
template <typename NodeTy, bool IsReverse> class ilist_iterator {
public:
  typedef NodeTy value_type;
  typedef value_type *pointer;
  typedef value_type &reference;
  typedef ptrdiff_t difference_type;
  typedef std::bidirectional_iterator_tag iterator_category;

  typedef typename std::add_const<value_type>::type *const_pointer;
  typedef typename std::add_const<value_type>::type &const_reference;

  typedef typename ilist_detail::ConstCorrectNodeType<NodeTy>::type node_type;
  typedef node_type *node_pointer;
  typedef node_type &node_reference;

private:
  node_pointer NodePtr;

public:
  /// Create from an ilist_node.
  explicit ilist_iterator(node_reference N) : NodePtr(&N) {}

  explicit ilist_iterator(pointer NP)
      : NodePtr(ilist_node_access::getNodePtr(NP)) {}
  explicit ilist_iterator(reference NR)
      : NodePtr(ilist_node_access::getNodePtr(&NR)) {}
  ilist_iterator() : NodePtr(nullptr) {}

  // This is templated so that we can allow constructing a const iterator from
  // a nonconst iterator...
  template <class node_ty>
  ilist_iterator(
      const ilist_iterator<node_ty, IsReverse> &RHS,
      typename std::enable_if<std::is_convertible<node_ty *, NodeTy *>::value,
                              void *>::type = nullptr)
      : NodePtr(RHS.getNodePtr()) {}

  // This is templated so that we can allow assigning to a const iterator from
  // a nonconst iterator...
  template <class node_ty>
  const ilist_iterator &
  operator=(const ilist_iterator<node_ty, IsReverse> &RHS) {
    NodePtr = RHS.getNodePtr();
    return *this;
  }

  /// Convert from an iterator to its reverse.
  ///
  /// TODO: Roll this into the implicit constructor once we're sure that no one
  /// is relying on the std::reverse_iterator off-by-one semantics.
  ilist_iterator<NodeTy, !IsReverse> getReverse() const {
    if (NodePtr)
      return ilist_iterator<NodeTy, !IsReverse>(*NodePtr);
    return ilist_iterator<NodeTy, !IsReverse>();
  }

  void reset(pointer NP) { NodePtr = NP; }

  // Accessors...
  reference operator*() const {
    assert(!NodePtr->isKnownSentinel());
    return *ilist_node_access::getValuePtr(NodePtr);
  }
  pointer operator->() const { return &operator*(); }

  // Comparison operators
  friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
    return LHS.NodePtr == RHS.NodePtr;
  }
  friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
    return LHS.NodePtr != RHS.NodePtr;
  }

  // Increment and decrement operators...
  ilist_iterator &operator--() {
    ilist_detail::IteratorHelper<IsReverse>::decrement(NodePtr);
    return *this;
  }
  ilist_iterator &operator++() {
    ilist_detail::IteratorHelper<IsReverse>::increment(NodePtr);
    return *this;
  }
  ilist_iterator operator--(int) {
    ilist_iterator tmp = *this;
    --*this;
    return tmp;
  }
  ilist_iterator operator++(int) {
    ilist_iterator tmp = *this;
    ++*this;
    return tmp;
  }

  /// Get the underlying ilist_node.
  node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
};

template <typename From> struct simplify_type;

/// Allow ilist_iterators to convert into pointers to a node automatically when
/// used by the dyn_cast, cast, isa mechanisms...
///
/// FIXME: remove this, since there is no implicit conversion to NodeTy.
template <typename NodeTy> struct simplify_type<ilist_iterator<NodeTy>> {
  typedef NodeTy *SimpleType;

  static SimpleType getSimplifiedValue(ilist_iterator<NodeTy> &Node) {
    return &*Node;
  }
};
template <typename NodeTy> struct simplify_type<const ilist_iterator<NodeTy>> {
  typedef /*const*/ NodeTy *SimpleType;

  static SimpleType getSimplifiedValue(const ilist_iterator<NodeTy> &Node) {
    return &*Node;
  }
};

} // end namespace llvm

#endif // LLVM_ADT_ILIST_ITERATOR_H