Shinya Kitaoka 810553
#pragma once
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifndef TCG_LIST_H
Toshihiro Shimizu 890ddd
#define TCG_LIST_H
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// tcg includes
Toshihiro Shimizu 890ddd
#include "alignment.h"
Toshihiro Shimizu 890ddd
#include "macros.h"
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// STD includes
Shinya Kitaoka 120a6e
#include <cstddef>  // size_t</cstddef>
Shinya Kitaoka 120a6e
#include <new>      // placement new</new>
Toshihiro Shimizu 890ddd
#include <vector></vector>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#include "assert.h"
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
// Discriminate rvalues support - either use Boost's config.hpp for automatic
Shinya Kitaoka 120a6e
// lookup,
Toshihiro Shimizu 890ddd
// or deal with it manually
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifndef TCG_RVALUES_SUPPORT
Toshihiro Shimizu 890ddd
#include <boost config.hpp=""></boost>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#ifdef BOOST_NO_RVALUE_REFERENCES
Toshihiro Shimizu 890ddd
#define TCG_RVALUES_SUPPORT 0
Toshihiro Shimizu 890ddd
#else
Toshihiro Shimizu 890ddd
#define TCG_RVALUES_SUPPORT 1
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#if (TCG_RVALUES_SUPPORT > 0)
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// Perfect forwarding macros
Toshihiro Shimizu 890ddd
#define TCG_FORWARD_TYPE(TheType) TheType##__ &&
Toshihiro Shimizu 890ddd
#define TCG_FORWARD_TEMPLATE(TheType) template <typename thetype##__=""></typename>
Toshihiro Shimizu 890ddd
#define TCG_FORWARD(TheType, Val) std::forward<thetype##__>(Val)</thetype##__>
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#else
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
// Common const reference forwarding macros
Toshihiro Shimizu 890ddd
#define TCG_FORWARD_TYPE(TheType) const TheType &
Toshihiro Shimizu 890ddd
#define TCG_FORWARD_TEMPLATE(TheType)
Toshihiro Shimizu 890ddd
#define TCG_FORWARD(TheType, Val) Val
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
/*! \file     tcg_list.h
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
    \brief    This file contains the implementation of an indexed list,
Toshihiro Shimizu 890ddd
              a list class based on a random access sequential container.
Toshihiro Shimizu 890ddd
*/
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//************************************************************************************
Toshihiro Shimizu 890ddd
//    Preliminaries
Toshihiro Shimizu 890ddd
//************************************************************************************
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
namespace tcg {
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
static const size_t _neg = -1, _invalid = -2;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
}  // namespace tcg
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//************************************************************************************
Toshihiro Shimizu 890ddd
//    Indexed list node  definition
Toshihiro Shimizu 890ddd
//************************************************************************************
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
namespace tcg {
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
/*!
Toshihiro Shimizu 890ddd
  \brief    Internal node class used in the implementation of a tcg::list_base.
Toshihiro Shimizu 890ddd
*/
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename t=""></typename>
Toshihiro Shimizu 890ddd
struct _list_node {
Shinya Kitaoka 120a6e
  TCG_STATIC_ASSERT(sizeof(T) == sizeof(aligned_buffer<t>));</t>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  aligned_buffer<t> m_val;</t>
Shinya Kitaoka 120a6e
  size_t m_prev, m_next;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  TCG_DEBUG(T &m_t;)  // Provided for debuggers' convenience
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  _list_node() : m_prev(_neg), m_next(_invalid) TCG_DEBUG2(, m_t(value())) {}
Shinya Kitaoka 120a6e
  _list_node(const T &val)
Shinya Kitaoka 120a6e
      : m_prev(_neg), m_next(_neg) TCG_DEBUG2(, m_t(value())) {
Shinya Kitaoka 120a6e
    constructValue(val);
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  ~_list_node() {
Shinya Kitaoka 120a6e
    if (isValid()) destroyValue();
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  _list_node(const _list_node &other)
Shinya Kitaoka 120a6e
      : m_prev(other.m_prev), m_next(other.m_next) TCG_DEBUG2(, m_t(value())) {
Shinya Kitaoka 120a6e
    if (other.isValid()) constructValue(other.value());
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  _list_node &operator=(const _list_node &other) {
Shinya Kitaoka 120a6e
    if (isValid())
Shinya Kitaoka 120a6e
      if (other.isValid())
Shinya Kitaoka 120a6e
        value() = other.value();
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        destroyValue();
Shinya Kitaoka 120a6e
    else
Shinya Kitaoka 120a6e
      constructValue(other.value());
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    m_prev = other.m_prev, m_next = other.m_next;
Shinya Kitaoka 120a6e
    return *this;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  const T &value() const { return reinterpret_cast<const &="" t="">(m_val.m_buf); }</const>
Shinya Kitaoka 120a6e
  T &value() { return reinterpret_cast<t &="">(m_val.m_buf); }</t>
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  bool isValid() const { return (m_next != _invalid); }
Shinya Kitaoka 120a6e
  void invalidate() {
Shinya Kitaoka 120a6e
    assert(isValid());
Shinya Kitaoka 120a6e
    destroyValue();
Shinya Kitaoka 120a6e
    m_next = _invalid;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#if (TCG_RVALUES_SUPPORT > 0)
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  _list_node(T &&val) : m_prev(_neg), m_next(_neg) TCG_DEBUG2(, m_t(value())) {
Shinya Kitaoka 120a6e
    constructValue(std::move(val));
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  _list_node(_list_node &&other)
Shinya Kitaoka 120a6e
      : m_prev(other.m_prev), m_next(other.m_next) TCG_DEBUG2(, m_t(value())) {
Shinya Kitaoka 120a6e
    if (other.isValid())
Shinya Kitaoka 120a6e
      constructValue(std::move(other.value())), other.invalidate();
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  _list_node &operator=(_list_node &&other) {
Shinya Kitaoka 120a6e
    if (isValid())
Shinya Kitaoka 120a6e
      if (other.isValid())
Shinya Kitaoka 120a6e
        value() = other.value();
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        destroyValue();
Shinya Kitaoka 120a6e
    else
Shinya Kitaoka 120a6e
      constructValue(std::move(other.value()));
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    value() = std::move(other.value());
Shinya Kitaoka 120a6e
    m_prev = other.m_prev, m_next = other.m_next;
Shinya Kitaoka 120a6e
    return *this;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  void constructValue(const T &val) { new (m_val.m_buf) T(val); }
Shinya Kitaoka 120a6e
  void destroyValue() { value().~T(); }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#if (TCG_RVALUES_SUPPORT > 0)
Shinya Kitaoka 120a6e
  void constructValue(T &&val) { new (m_val.m_buf) T(std::move(val)); }
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//************************************************************************************
Toshihiro Shimizu 890ddd
//    Base indexed list  definition
Toshihiro Shimizu 890ddd
//************************************************************************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
/*!
Toshihiro Shimizu 890ddd
  \brief    Base class for list-like containers based on <tt>tcg::list</tt>'s
Toshihiro Shimizu 890ddd
            indexed list implementation.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
  \details  This class implements a barebone container class which manages
Toshihiro Shimizu 890ddd
            a collection of nodes stored in an iternal random access container.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
            Nodes management is limited to the \a acquisition and \a release
Toshihiro Shimizu 890ddd
            of individual nodes (see the buyNode() and sellNode() functions).
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
            Links between list nodes must be managed externally.
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
  \sa       Template class \p tcg::list for an explanation of the indexed list
Toshihiro Shimizu 890ddd
            container concept.
Toshihiro Shimizu 890ddd
*/
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
template <typename t=""></typename>
Shinya Kitaoka 120a6e
class list_base {
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  typedef T value_type;
Shinya Kitaoka 120a6e
  typedef ::size_t size_t;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  static const size_t _neg = -1;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
protected:
Shinya Kitaoka 120a6e
  typedef _list_node<t> list_node;</t>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  std::vector<list_node> m_vector;</list_node>
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  size_t m_size;
Shinya Kitaoka 120a6e
  size_t m_clearedHead;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  struct const_iterator
Shinya Kitaoka 120a6e
      : public std::iterator<std::bidirectional_iterator_tag, const="" t=""> {</std::bidirectional_iterator_tag,>
Shinya Kitaoka 120a6e
    const list_base *m_list;
Shinya Kitaoka 120a6e
    size_t m_idx;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    TCG_DEBUG(const list_node *m_node;)  // Provided for debuggers' convenience
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  public:
Shinya Kitaoka 120a6e
    typedef const T value_type;
Shinya Kitaoka 120a6e
    typedef const T *pointer;
Shinya Kitaoka 120a6e
    typedef const T &reference;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  public:
Shinya Kitaoka 120a6e
    const_iterator() {}
Shinya Kitaoka 120a6e
    const_iterator(const list_base *list, size_t idx)
Shinya Kitaoka 120a6e
        : m_list(list), m_idx(idx) {
Shinya Kitaoka 120a6e
      TCG_DEBUG(m_node = (m_idx == _neg) ? 0 : &m_list->m_vector[m_idx]);
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    size_t index() const { return m_idx; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    reference operator*() const { return (*m_list)[m_idx]; }
Shinya Kitaoka 120a6e
    pointer operator->() const { return &(*m_list)[m_idx]; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    const_iterator operator++(int) {
Shinya Kitaoka 120a6e
      const_iterator temp(*this);
Shinya Kitaoka 120a6e
      operator++();
Shinya Kitaoka 120a6e
      return temp;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    const_iterator &operator++() {
Shinya Kitaoka 120a6e
      m_idx = m_list->m_vector[m_idx].m_next;
Shinya Kitaoka 120a6e
      TCG_DEBUG(m_node = (m_idx == _neg) ? 0 : &m_list->m_vector[m_idx]);
Shinya Kitaoka 120a6e
      return *this;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    const_iterator operator--(int) {
Shinya Kitaoka 120a6e
      const_iterator temp(*this);
Shinya Kitaoka 120a6e
      operator--();
Shinya Kitaoka 120a6e
      return temp;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    const_iterator &operator--() {
Shinya Kitaoka 120a6e
      m_idx = m_list->m_vector[m_idx].m_prev;
Shinya Kitaoka 120a6e
      TCG_DEBUG(m_node = (m_idx == _neg) ? 0 : &m_list->m_vector[m_idx]);
Shinya Kitaoka 120a6e
      return *this;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    bool operator==(const const_iterator &it) const {
Shinya Kitaoka 120a6e
      return (m_idx == it.m_idx);
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    bool operator!=(const const_iterator &it) const {
Shinya Kitaoka 120a6e
      return (m_idx != it.m_idx);
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  };
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  struct iterator : public const_iterator {
Shinya Kitaoka 120a6e
  public:
Shinya Kitaoka 120a6e
    typedef T value_type;
Shinya Kitaoka 120a6e
    typedef T *pointer;
Shinya Kitaoka 120a6e
    typedef T &reference;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  public:
Shinya Kitaoka 120a6e
    iterator() {}
Shinya Kitaoka 120a6e
    iterator(list_base *list, size_t idx) : const_iterator(list, idx) {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    reference operator*() const {
Shinya Kitaoka 120a6e
      return const_cast<reference>(const_iterator::operator*());</reference>
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    pointer operator->() const {
Shinya Kitaoka 120a6e
      return const_cast<pointer>(const_iterator::operator->());</pointer>
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    iterator operator++(int) {
Shinya Kitaoka 120a6e
      iterator temp(*this);
Shinya Kitaoka 120a6e
      operator++();
Shinya Kitaoka 120a6e
      return temp;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    iterator &operator++() {
Shinya Kitaoka 120a6e
      const_iterator::operator++();
Shinya Kitaoka 120a6e
      return *this;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    iterator operator--(int) {
Shinya Kitaoka 120a6e
      iterator temp(*this);
Shinya Kitaoka 120a6e
      operator--();
Shinya Kitaoka 120a6e
      return temp;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
    iterator &operator--() {
Shinya Kitaoka 120a6e
      const_iterator::operator--();
Shinya Kitaoka 120a6e
      return *this;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  };
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  friend struct iterator;
Shinya Kitaoka 120a6e
  friend struct const_iterator;
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
public:
Shinya Kitaoka 120a6e
  list_base() : m_size(0), m_clearedHead(_neg) {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  list_base(size_t count, const T &val)
Shinya Kitaoka 120a6e
      : m_vector(count, list_node(val)), m_size(count), m_clearedHead(_neg) {
Shinya Kitaoka 120a6e
    assert(m_size >= 0);
Shinya Kitaoka 120a6e
    for (size_t i        = 0; i < m_size; ++i)
Shinya Kitaoka 120a6e
      m_vector[i].m_prev = i - 1, m_vector[i].m_next = i + 1;
Shinya Kitaoka 120a6e
    if (m_size > 0) m_vector[m_size - 1].m_next = _neg;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  template <typename init=""></typename>
Shinya Kitaoka 120a6e
  list_base(InIt begin, InIt end)
Shinya Kitaoka 120a6e
      : m_vector(begin, end), m_size(m_vector.size()), m_clearedHead(_neg) {
Shinya Kitaoka 120a6e
    assert(m_size >= 0);
Shinya Kitaoka 120a6e
    for (size_t i        = 0; i < m_size; ++i)
Shinya Kitaoka 120a6e
      m_vector[i].m_prev = i - 1, m_vector[i].m_next = i + 1;
Shinya Kitaoka 120a6e
    if (m_size > 0) m_vector[m_size - 1].m_next = _neg;
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  //-----------------------------------------------------------------------------------------
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  list_base(const list_base &other)
Shinya Kitaoka 120a6e
      : m_vector(other.m_vector)
Shinya Kitaoka 120a6e
      , m_size(other.m_size)
Shinya Kitaoka 120a6e
      , m_clearedHead(other.m_clearedHead) {}
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  list_base &operator=(const list_base &other) {
Shinya Kitaoka 120a6e
    // Note: not using the copy-and-swap idiom. We want to attempt preservation
Shinya Kitaoka 120a6e
    // of m_vector's buffer in case its current capacity is sufficient.
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    m_size        = other.m_size;
Shinya Kitaoka 120a6e
    m_clearedHead = other.m_clearedHead;
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    // A clear must be performed before the actual =. It's necessary to prevent
Shinya Kitaoka 120a6e
    // copying to
Shinya Kitaoka 120a6e
    // objects that were already destroyed - but are still in the vector as
Shinya Kitaoka 120a6e
    // zombies.
Shinya Kitaoka 120a6e
    // In this case, the value-to-value vector::operator= would assume that the
Shinya Kitaoka 120a6e
    // assigned-to object is NOT a zombie - and would attempt its release, which
Shinya Kitaoka 120a6e
    // is UB!
Shinya Kitaoka 120a6e
    m_vector.clear();
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
    m_vector = other.m_vector;
Shinya Kitaoka 120a6e
    return *this;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#if (TCG_RVALUES_SUPPORT > 0)
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  list_base(list_base &&other)
Shinya Kitaoka 120a6e
      : m_vector(std::move(other.m_vector))
Shinya Kitaoka 120a6e
      , m_size(other.m_size)
Shinya Kitaoka 120a6e
      , m_clearedHead(other.m_clearedHead) {}
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  list_base &operator=(list_base &&other) {
Shinya Kitaoka 120a6e
    swap(*this, std::forward<list_base>(other));</list_base>
Shinya Kitaoka 120a6e
    return *this;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  T &operator[](size_t idx) {
Shinya Kitaoka 120a6e
    assert(idx < m_vector.size() && isValid(idx));
Shinya Kitaoka 120a6e
    return m_vector[idx].value();
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
  const T &operator[](size_t idx) const {
Shinya Kitaoka 120a6e
    assert(idx < m_vector.size() && isValid(idx));
Shinya Kitaoka 120a6e
    return m_vector[idx].value();
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  bool isValid(size_t idx) const { return m_vector[idx].isValid(); }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  size_t size() const { return m_size; }
Shinya Kitaoka 120a6e
  size_t nodesCount() const { return m_vector.size(); }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  void reserve(size_t size) { m_vector.reserve(size); }
Shinya Kitaoka 120a6e
  size_t capacity() const { return m_vector.capacity(); }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  void clear() {
Shinya Kitaoka 120a6e
    m_size        = 0;
Shinya Kitaoka 120a6e
    m_clearedHead = _neg;
Shinya Kitaoka 120a6e
    m_vector.clear();
Shinya Kitaoka 120a6e
  }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  bool empty() const { return m_size == 0; }
Shinya Kitaoka 120a6e
Shinya Kitaoka 120a6e
  void _swap(list_base &a, list_base &b) {
Shinya Kitaoka 120a6e
    std::swap(a.m_size, b.m_size);
Shinya Kitaoka 120a6e
    std::swap(a.m_clearedHead, b.m_clearedHead);
Shinya Kitaoka 120a6e
    a.m_vector.swap(b.m_vector);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#if (TCG_RVALUES_SUPPORT > 0)
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  void _swap(list_base &a, list_base &&b) {
Shinya Kitaoka 120a6e
    a.m_size        = b.m_size;
Shinya Kitaoka 120a6e
    a.m_clearedHead = b.m_clearedHead;
Shinya Kitaoka 120a6e
    a.m_vector.swap(b.m_vector);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  void _swap(list_base &&a, list_base &b) { swap(b, std::move(a)); }
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
#endif
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  //-----------------------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  //! Constructs from a range of (index, value) pairs
Shinya Kitaoka 120a6e
  template <typename forit=""></typename>
Shinya Kitaoka 120a6e
  list_base(ForIt begin, ForIt end, size_t nodesCount) {
Shinya Kitaoka 120a6e
    // Initialize the vector with invalid nodes up to the required nodes count
Shinya Kitaoka 120a6e
    m_vector.resize(nodesCount, list_node());
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // Iterate the range and add corresponding value pairs
Shinya Kitaoka 120a6e
    size_t lastIdx = _neg;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    for (; begin != end; ++begin) {
Shinya Kitaoka 120a6e
      size_t idx = (*begin).first;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      assert(idx >= 0);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      // Further resize the vector with holes if necessary
Shinya Kitaoka 120a6e
      if (idx >= m_vector.size()) {
Shinya Kitaoka 120a6e
        // The nodesCount hint was not sufficient. Thus, we have to readjust the
Shinya Kitaoka 120a6e
        // correct minimal
Shinya Kitaoka 120a6e
        // allocation size. Let's do it now with a further single pass toward
Shinya Kitaoka 120a6e
        // the end.
Shinya Kitaoka 120a6e
        size_t newSize = m_vector.size();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
        for (ForIt it = begin; it != end; ++it)
Shinya Kitaoka 120a6e
          newSize = std::max(newSize, size_t((*it).first) + 1);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
        m_vector.resize(newSize, list_node());
Shinya Kitaoka 120a6e
      }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      // Place current node in the vector
Shinya Kitaoka 120a6e
      list_node &node = m_vector[idx];
Shinya Kitaoka 120a6e
      new (&node) list_node((*begin).second);
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      // Link the node
Shinya Kitaoka 120a6e
      node.m_prev                                   = lastIdx;
Shinya Kitaoka 120a6e
      if (lastIdx != _neg) m_vector[lastIdx].m_next = idx;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      lastIdx = idx;
Shinya Kitaoka 120a6e
    }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // Finally, make up a consistent links chain for holes
Shinya Kitaoka 120a6e
    lastIdx = _neg;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    size_t n, nCount = m_vector.size();
Shinya Kitaoka 120a6e
    for (n = 0; n != nCount; ++n) {
Shinya Kitaoka 120a6e
      list_node &node = m_vector[n];
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      if (!node.isValid()) node.m_prev = lastIdx, lastIdx = n;
Shinya Kitaoka 120a6e
    }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    m_clearedHead = lastIdx;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  //-----------------------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
protected:
Shinya Kitaoka 120a6e
  TCG_FORWARD_TEMPLATE(T)
Shinya Kitaoka 120a6e
  size_t buyNode(TCG_FORWARD_TYPE(T) val) {
Shinya Kitaoka 120a6e
    size_t nodeIdx;
Shinya Kitaoka 120a6e
    list_node *node;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    ++m_size;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    if (m_clearedHead != _neg) {
Shinya Kitaoka 120a6e
      assert(m_clearedHead < m_vector.size());
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      // Take the last cleared element
Shinya Kitaoka 120a6e
      nodeIdx = m_clearedHead;
Shinya Kitaoka 120a6e
      node    = &m_vector[nodeIdx];
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      m_clearedHead = node->m_prev;
Shinya Kitaoka 120a6e
    } else {
Shinya Kitaoka 120a6e
      m_vector.push_back(list_node());
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      nodeIdx = m_vector.size() - 1;
Shinya Kitaoka 120a6e
      node    = &m_vector[nodeIdx];
Shinya Kitaoka 120a6e
    }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // Construct the node's value
Shinya Kitaoka 120a6e
    node->constructValue(TCG_FORWARD(T, val));
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    return nodeIdx;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  //-----------------------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  void sellNode(size_t idx) {
Shinya Kitaoka 120a6e
    assert(isValid(idx));
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    list_node &node = m_vector[idx];
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // Relink neighbours
Shinya Kitaoka 120a6e
    if (node.m_prev != _neg) m_vector[node.m_prev].m_next = node.m_next;
Shinya Kitaoka 120a6e
    if (node.m_next != _neg) m_vector[node.m_next].m_prev = node.m_prev;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // Explicitly invoke the node's destructor
Shinya Kitaoka 120a6e
    node.invalidate();
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // Now, the node is a zombie - still, use its indices data to remember the
Shinya Kitaoka 120a6e
    // list
Shinya Kitaoka 120a6e
    // of unused nodes
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // Remember the last cleared element in element.m_prev
Shinya Kitaoka 120a6e
    node.m_prev   = m_clearedHead;
Shinya Kitaoka 120a6e
    m_clearedHead = idx;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    --m_size;
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  //-----------------------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  void sellNodes(size_t begin, size_t end) {
Shinya Kitaoka 120a6e
    for (size_t i = begin; i != end; i = m_vector[i].m_next) sellNode(i);
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  //-----------------------------------------------------------------------------------------
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  void move(size_t afterDst, size_t &dstBegin, size_t &dstRBegin,
Shinya Kitaoka 120a6e
            size_t srcBegin, size_t srcEnd, size_t srcRBegin) {
Shinya Kitaoka 120a6e
    if (srcBegin == _neg || srcBegin == afterDst) return;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // afterDst-1 -> srcBegin
Shinya Kitaoka 120a6e
    {
Shinya Kitaoka 120a6e
      size_t beforeDst =
Shinya Kitaoka 120a6e
          (afterDst == _neg) ? dstRBegin : m_vector[afterDst].m_prev;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      m_vector[srcBegin].m_prev = beforeDst;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      if (beforeDst != _neg)
Shinya Kitaoka 120a6e
        m_vector[beforeDst].m_next = srcBegin;
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        dstBegin = srcBegin;
Shinya Kitaoka 120a6e
    }
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
    // srcEnd-1 -> afterDst
Shinya Kitaoka 120a6e
    {
Shinya Kitaoka 120a6e
      size_t srcLast = (srcEnd == _neg) ? srcRBegin : m_vector[srcEnd].m_prev;
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      m_vector[srcLast].m_next = afterDst;  // NOTE: srcLast cannot be _neg
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
      if (afterDst != _neg)
Shinya Kitaoka 120a6e
        m_vector[afterDst].m_prev = srcLast;
Shinya Kitaoka 120a6e
      else
Shinya Kitaoka 120a6e
        dstRBegin = srcLast;
Shinya Kitaoka 120a6e
    }
Shinya Kitaoka 120a6e
  }
Toshihiro Shimizu 890ddd
};
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
//************************************************************************************
Toshihiro Shimizu 890ddd
//    Indexed list  definition
Toshihiro Shimizu 890ddd
//************************************************************************************
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
/*!
Toshihiro Shimizu 890ddd
  \brief    Double linked list container class with indexed access to elements.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
  \details  This class is the result of implementing a double linked list using
Shinya Kitaoka 120a6e
a
Shinya Kitaoka 120a6e
            dynamic random access sequential container as the underlying pool
Shinya Kitaoka 120a6e
for
Toshihiro Shimizu 890ddd
            the list's nodes.
Toshihiro Shimizu 890ddd
Shinya Kitaoka 120a6e
            This is somewhat different than supplying a custom allocator to an
Shinya Kitaoka 120a6e
existing
Toshihiro Shimizu 890ddd
            list implementation, like \p std::list, since:
Toshihiro Shimizu 890ddd
Toshihiro Shimizu 890ddd
              
    Toshihiro Shimizu 890ddd
                  
  • No memory model of the underlying container is actually
  • Toshihiro Shimizu 890ddd
                        required.
    Toshihiro Shimizu 890ddd
                  
  • The underlying container provides explicit access to nodes
  • Shinya Kitaoka 120a6e
                        using their associated insertion indexes, so \p
    Shinya Kitaoka 120a6e
    std::list
    Toshihiro Shimizu 890ddd
                        could not be used as-is.
    Toshihiro Shimizu 890ddd
                  
    Toshihiro Shimizu 890ddd
    \n
    Shinya Kitaoka 120a6e
                The nodes pool (see \p list_base) is an internal \a lazy container
    Shinya Kitaoka 120a6e
    that
    Shinya Kitaoka 120a6e
                saves released nodes \a without actually deallocating them (of
    Shinya Kitaoka 120a6e
    course,
    Toshihiro Shimizu 890ddd
                their content is properly destroyed). They are rather stored into an
    Toshihiro Shimizu 890ddd
                internal \a stack of released nodes, ready to be reacquired.
    Toshihiro Shimizu 890ddd
                  \par Features
    Shinya Kitaoka 120a6e
                  \li  Insertion indexes are automatically generated keys with the
    Shinya Kitaoka 120a6e
    same
    luz paz 1414d5
                       access time of the underlying container (typically super-fast
    Toshihiro Shimizu 890ddd
                       \p O(1)).
    Shinya Kitaoka 120a6e
                  \li  Stable indexes and iterators with respect to every
    Shinya Kitaoka 120a6e
    operation.
    Toshihiro Shimizu 890ddd
                  \li  Copying an indexed list \a preserves the original indexes.
    Toshihiro Shimizu 890ddd
                  \li  Indexes are process independent - they can be saved
    Toshihiro Shimizu 890ddd
                       on file and restored later (although you probably want to
    Toshihiro Shimizu 890ddd
                       \a squeeze the list before saving).
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
                  \par Use cases
    Toshihiro Shimizu 890ddd
                This class is surprisingly useful for cross-referencing.
    Shinya Kitaoka 120a6e
                A graph data structure, for example, can be implemented using a pair
    Shinya Kitaoka 120a6e
    of
    Toshihiro Shimizu 890ddd
                indexed lists for vertexes and edges.
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
                  \par Known issues
    Shinya Kitaoka 120a6e
                The lazy nature of this container class may require \a squeezing the
    Shinya Kitaoka 120a6e
    list's
    Toshihiro Shimizu 890ddd
                content at strategic places in your code, as noted before.
    Shinya Kitaoka 120a6e
                Beware that composite cross-referencing may be hard to track \a
    Shinya Kitaoka 120a6e
    precisely
    Toshihiro Shimizu 890ddd
                during this particular operation.
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      \remark   Current implementation explicitly uses an \p std::vector class as
    Shinya Kitaoka 120a6e
    the
    Shinya Kitaoka 120a6e
                underlying random access container. Future improvements will make
    Shinya Kitaoka 120a6e
    the
    Toshihiro Shimizu 890ddd
                container class a template parameter.
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
      \sa       Template class \p tcg::Mesh for a notable use case.
    Toshihiro Shimizu 890ddd
    */
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    template <typename t=""></typename>
    Shinya Kitaoka 120a6e
    class list : public list_base<t> {</t>
    Shinya Kitaoka 120a6e
      size_t m_begin, m_rbegin;
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    protected:
    Shinya Kitaoka 120a6e
      typedef typename list_base<t>::list_node list_node;</t>
    Shinya Kitaoka 120a6e
      using list_base<t>::m_vector;</t>
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    public:
    Shinya Kitaoka 120a6e
      struct iterator : public list_base<t>::iterator {</t>
    Shinya Kitaoka 120a6e
        iterator() {}
    Shinya Kitaoka 120a6e
        iterator(list *l, size_t idx) : list_base<t>::iterator(l, idx) {}</t>
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
        iterator &operator++() {
    Shinya Kitaoka 120a6e
          list_base<t>::iterator::operator++();</t>
    Shinya Kitaoka 120a6e
          return *this;
    Shinya Kitaoka 120a6e
        }
    Shinya Kitaoka 120a6e
        iterator &operator--() {
    Shinya Kitaoka 120a6e
          if (this->m_idx == _neg)
    Shinya Kitaoka 120a6e
            operator=(static_cast<list *="">(this->m_list)->last());</list>
    Shinya Kitaoka 120a6e
          else
    Shinya Kitaoka 120a6e
            list_base<t>::iterator::operator--();</t>
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
          return *this;
    Shinya Kitaoka 120a6e
        }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
        iterator operator++(int) {
    Shinya Kitaoka 120a6e
          iterator temp(*this);
    Shinya Kitaoka 120a6e
          operator++();
    Shinya Kitaoka 120a6e
          return temp;
    Shinya Kitaoka 120a6e
        }
    Shinya Kitaoka 120a6e
        iterator operator--(int) {
    Shinya Kitaoka 120a6e
          iterator temp(*this);
    Shinya Kitaoka 120a6e
          operator--();
    Shinya Kitaoka 120a6e
          return temp;
    Shinya Kitaoka 120a6e
        }
    Shinya Kitaoka 120a6e
      };
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      struct const_iterator : public list_base<t>::const_iterator {</t>
    Shinya Kitaoka 120a6e
        const_iterator() {}
    Shinya Kitaoka 120a6e
        const_iterator(const list *l, size_t idx)
    Shinya Kitaoka 120a6e
            : list_base<t>::const_iterator(l, idx) {}</t>
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
        const_iterator &operator++() {
    Shinya Kitaoka 120a6e
          list_base<t>::const_iterator::operator++();</t>
    Shinya Kitaoka 120a6e
          return *this;
    Shinya Kitaoka 120a6e
        }
    Shinya Kitaoka 120a6e
        const_iterator &operator--() {
    Shinya Kitaoka 120a6e
          if (this->m_idx == _neg)
    Shinya Kitaoka 120a6e
            operator=(static_cast<const *="" list="">(this->m_list)->last());</const>
    Shinya Kitaoka 120a6e
          else
    Shinya Kitaoka 120a6e
            list_base<t>::const_iterator::operator--();</t>
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
          return *this;
    Shinya Kitaoka 120a6e
        }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
        const_iterator operator++(int) {
    Shinya Kitaoka 120a6e
          const_iterator temp(*this);
    Shinya Kitaoka 120a6e
          operator++();
    Shinya Kitaoka 120a6e
          return temp;
    Shinya Kitaoka 120a6e
        }
    Shinya Kitaoka 120a6e
        const_iterator operator--(int) {
    Shinya Kitaoka 120a6e
          const_iterator temp(*this);
    Shinya Kitaoka 120a6e
          operator--();
    Shinya Kitaoka 120a6e
          return temp;
    Shinya Kitaoka 120a6e
        }
    Shinya Kitaoka 120a6e
      };
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    public:
    Shinya Kitaoka 120a6e
      list() : m_begin(_neg), m_rbegin(_neg) {}
    Shinya Kitaoka 120a6e
      list(size_t count, const T &val)
    Shinya Kitaoka 120a6e
          : list_base<t>(count, val), m_begin(0), m_rbegin(count - 1) {}</t>
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      template <typename init=""></typename>
    Shinya Kitaoka 120a6e
      list(InIt begin, InIt end)
    Shinya Kitaoka 120a6e
          : list_base<t>(begin, end)</t>
    Shinya Kitaoka 120a6e
          , m_begin(list_base<t>::m_size ? 0 : _neg)</t>
    Shinya Kitaoka 120a6e
          , m_rbegin(list_base<t>::m_size - 1) {}</t>
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      //! Constructs from a range of (index, value) pairs
    Shinya Kitaoka 120a6e
      template <typename bidit=""></typename>
    Shinya Kitaoka 120a6e
      list(BidIt begin, BidIt end, size_t nodesCount)
    Shinya Kitaoka 120a6e
          : list_base<t>(begin, end, nodesCount) {</t>
    Shinya Kitaoka 120a6e
        if (begin != end) m_begin = (*begin).first, m_rbegin = (*--end).first;
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      //-----------------------------------------------------------------------------------------
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      list(const list &other)
    Shinya Kitaoka 120a6e
          : list_base<t>(other), m_begin(other.m_begin), m_rbegin(other.m_rbegin) {}</t>
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      /*!
    Shinya Kitaoka 120a6e
    \warning  \p tcg::list has a different copy behavior from other container
    Shinya Kitaoka 120a6e
    classes, since
    Shinya Kitaoka 120a6e
            it is intended to preserve the source's node indices in the process.
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
            This means that no value-to-value assignment can take place, and thus
    Shinya Kitaoka 120a6e
    <tt>operator=</tt>'s
    Shinya Kitaoka 120a6e
            behavior is equivalent to first clearing it, and then copy-constructing
    Shinya Kitaoka 120a6e
    each value.
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
            This typically leads to performance penalties with respect to other
    Shinya Kitaoka 120a6e
    container classes that
    Shinya Kitaoka 120a6e
            implement value-to-value assignments, like \p std::vector in case its
    Shinya Kitaoka 120a6e
    capacity is not exceeded.
    Shinya Kitaoka 120a6e
    */
    Shinya Kitaoka 120a6e
      list &operator=(const list &other) {
    Shinya Kitaoka 120a6e
        m_begin = other.m_begin, m_rbegin = other.m_rbegin;
    Shinya Kitaoka 120a6e
        list_base<t>::operator=(other);</t>
    Shinya Kitaoka 120a6e
        return *this;
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    #if (TCG_RVALUES_SUPPORT > 0)
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      list(list &&other)
    Shinya Kitaoka 120a6e
          : list_base<t>(std::forward<list_base<t>>(other))</list_base<t></t>
    Shinya Kitaoka 120a6e
          , m_begin(other.m_begin)
    Shinya Kitaoka 120a6e
          , m_rbegin(other.m_rbegin) {}
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      list &operator=(list &&other) {
    Shinya Kitaoka 120a6e
        swap(*this, std::forward<list>(other));</list>
    Shinya Kitaoka 120a6e
        return *this;
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    #endif
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      //-----------------------------------------------------------------------------------------
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      TCG_FORWARD_TEMPLATE(T)
    Shinya Kitaoka 120a6e
      size_t insert(size_t idx, TCG_FORWARD_TYPE(T) val) {
    Shinya Kitaoka 120a6e
        assert(idx == _neg || list_base<t>::isValid(idx));</t>
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        size_t nodeIdx  = list_base<t>::buyNode(TCG_FORWARD(T, val));</t>
    Shinya Kitaoka 120a6e
        list_node &node = m_vector[nodeIdx];
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        // Update links
    Shinya Kitaoka 120a6e
        if (idx != _neg) {
    Shinya Kitaoka 120a6e
          // node has a valid next
    Shinya Kitaoka 120a6e
          list_node &next = m_vector[idx];
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
          node.m_prev                                           = next.m_prev;
    Shinya Kitaoka 120a6e
          next.m_prev                                           = nodeIdx;
    Shinya Kitaoka 120a6e
          node.m_next                                           = idx;
    Shinya Kitaoka 120a6e
          if (node.m_prev != _neg) m_vector[node.m_prev].m_next = nodeIdx;
    Shinya Kitaoka 120a6e
        } else {
    Shinya Kitaoka 120a6e
          node.m_next                                     = _neg;
    Shinya Kitaoka 120a6e
          node.m_prev                                     = m_rbegin;
    Shinya Kitaoka 120a6e
          if (m_rbegin != _neg) m_vector[m_rbegin].m_next = nodeIdx;
    Shinya Kitaoka 120a6e
          m_rbegin                                        = nodeIdx;
    Shinya Kitaoka 120a6e
        }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        if (idx == m_begin) m_begin = nodeIdx;
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        return nodeIdx;
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      template <typename iter=""></typename>
    Shinya Kitaoka 120a6e
      size_t insert(size_t idx, Iter begin, Iter end) {
    Shinya Kitaoka 120a6e
        if (begin == end) return idx;
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        assert(idx == _neg || list_base<t>::isValid(idx));</t>
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        size_t res = insert(idx, *begin);
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        for (++begin; begin != end; ++begin) insert(idx, *begin);
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        return res;
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      size_t erase(size_t idx) {
    Shinya Kitaoka 120a6e
        assert(list_base<t>::isValid(idx));</t>
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        if (idx == m_begin) m_begin   = m_vector[idx].m_next;
    Shinya Kitaoka 120a6e
        if (idx == m_rbegin) m_rbegin = m_vector[idx].m_prev;
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        size_t result = m_vector[idx].m_next;
    Shinya Kitaoka 120a6e
        list_base<t>::sellNode(idx);</t>
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        return result;
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      size_t erase(size_t begin, size_t end) {
    Shinya Kitaoka 120a6e
        assert(list_base<t>::isValid(begin));</t>
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        if (begin == m_begin) m_begin = end;
    Shinya Kitaoka 120a6e
        if (end == m_rbegin) m_rbegin = m_vector[begin].m_prev;
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        list_base<t>::sellNodes(begin, end);</t>
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        return end;
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      void clear() {
    Shinya Kitaoka 120a6e
        list_base<t>::clear();</t>
    Shinya Kitaoka 120a6e
        m_begin = m_rbegin = _neg;
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      void swap(list &other) {
    Shinya Kitaoka 120a6e
        _swap(*this, other);
    Shinya Kitaoka 120a6e
        std::swap(m_begin, other.m_begin);
    Shinya Kitaoka 120a6e
        std::swap(m_rbegin, other.m_rbegin);
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      void swap(list &a, list &b) { a.swap(b); }
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    #if (TCG_RVALUES_SUPPORT > 0)
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      void swap(list &&other) {
    Shinya Kitaoka 120a6e
        this->_swap(*this, std::move(other));
    Shinya Kitaoka 120a6e
        m_begin  = other.m_begin;
    Shinya Kitaoka 120a6e
        m_rbegin = other.m_rbegin;
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      void swap(list &a, list &&b) { a.swap(std::move(b)); }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      void swap(list &&a, list &b) { b.swap(std::move(a)); }
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    #endif
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      //-----------------------------------------------------------------------------------------
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      /*!
    Shinya Kitaoka 120a6e
    \details  This function is \p tcg::list's counterpart to \p std::list::splice().
    Shinya Kitaoka 120a6e
            It moves the specified range to a different part of the list, \a without
    Shinya Kitaoka 120a6e
            touching any element elements - just by altering node links.
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
    \note     Unlike \p std::list::splice(), the list must be the same.
    Shinya Kitaoka 120a6e
    */
    Shinya Kitaoka 120a6e
      void move(size_t afterDst, size_t srcBegin,
    Shinya Kitaoka 120a6e
                size_t srcEnd)  //! Moves range <tt>[srcBegin, srcEnd)</tt> right
    Shinya Kitaoka 120a6e
                                //! before afterDst.      \param afterDst  Index
    Shinya Kitaoka 120a6e
                                //! right after the destination position. \param
    Shinya Kitaoka 120a6e
                                //! srcBegin  Start index of the moved range. \param
    Shinya Kitaoka 120a6e
                                //! srcEnd  End index of the moved range.
    Shinya Kitaoka 120a6e
      {
    Shinya Kitaoka 120a6e
        return move(afterDst, m_begin, m_rbegin, srcBegin, srcEnd, m_rbegin);
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
    Shinya Kitaoka 120a6e
      /*!
    Shinya Kitaoka 120a6e
    \sa       The equivalent function move(size_t, size_t, size_t).
    Shinya Kitaoka 120a6e
    */
    Shinya Kitaoka 120a6e
      void move(iterator afterDst, iterator srcBegin,
    Shinya Kitaoka 120a6e
                iterator srcEnd)  //! Moves range <tt>[srcBegin, srcEnd)</tt> right
    Shinya Kitaoka 120a6e
                                  //! before afterDst.      \param afterDst
    Shinya Kitaoka 120a6e
                                  //! Iterator right after the destination position.
    Shinya Kitaoka 120a6e
                                  //! \param srcBegin  Start of the moved range.
    Shinya Kitaoka 120a6e
                                  //! \param srcEnd  End of the moved range.
    Shinya Kitaoka 120a6e
      {
    Shinya Kitaoka 120a6e
        assert(afterDst.m_list == this && srcBegin.m_list == this &&
    Shinya Kitaoka 120a6e
               srcEnd.m_list == this);
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
        return move(afterDst.m_idx, srcBegin.m_idx, srcEnd.m_idx);
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      //-----------------------------------------------------------------------------------------
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      iterator insert(iterator it, const T &val) {
    Shinya Kitaoka 120a6e
        return iterator(this, insert(it.m_idx, val));
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
      iterator erase(iterator it) { return iterator(this, erase(it.m_idx)); }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      template <typename iter=""></typename>
    Shinya Kitaoka 120a6e
      iterator insert(iterator it, Iter begin, Iter end) {
    Shinya Kitaoka 120a6e
        return iterator(this, insert(it.m_idx, begin, end));
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
      iterator erase(iterator begin, iterator end) {
    Shinya Kitaoka 120a6e
        return iterator(this, erase(begin.m_idx, end.m_idx));
    Shinya Kitaoka 120a6e
      }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      size_t push_front(const T &val) { return insert(m_begin, val); }
    Shinya Kitaoka 120a6e
      size_t push_back(const T &val) { return insert(_neg, val); }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      void pop_front() { erase(m_begin); }
    Shinya Kitaoka 120a6e
      void pop_back() { erase(m_rbegin); }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      T &front() { return m_vector[m_begin].value(); }
    Shinya Kitaoka 120a6e
      const T &front() const { return m_vector[m_begin].value(); }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      T &back() { return m_vector[m_rbegin].value(); }
    Shinya Kitaoka 120a6e
      const T &back() const { return m_vector[m_rbegin].value(); }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      iterator begin() { return iterator(this, m_begin); }
    Shinya Kitaoka 120a6e
      const_iterator begin() const { return const_iterator(this, m_begin); }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      iterator last() { return iterator(this, m_rbegin); }
    Shinya Kitaoka 120a6e
      const_iterator last() const { return const_iterator(this, m_rbegin); }
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      iterator end() { return iterator(this, _neg); }
    Shinya Kitaoka 120a6e
      const_iterator end() const { return const_iterator(this, _neg); }
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    #if (TCG_RVALUES_SUPPORT > 0)
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
      iterator insert(iterator it, T &&val) {
    Shinya Kitaoka 120a6e
        return iterator(this, insert<t>(it.m_idx, std::forward<t>(val)));</t></t>
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
      size_t push_front(T &&val) {
    Shinya Kitaoka 120a6e
        return insert<t>(m_begin, std::forward<t>(val));</t></t>
    Shinya Kitaoka 120a6e
      }
    Shinya Kitaoka 120a6e
      size_t push_back(T &&val) { return insert<t>(_neg, std::forward<t>(val)); }</t></t>
    Toshihiro Shimizu 890ddd
    Toshihiro Shimizu 890ddd
    #endif
    Toshihiro Shimizu 890ddd
    };
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
    }  // namespace tcg
    Toshihiro Shimizu 890ddd
    Shinya Kitaoka 120a6e
    #endif  // TCG_LIST_H