#pragma once

#ifndef TCG_LIST_H

#define TCG_LIST_H

// tcg includes

#include "alignment.h"

#include "macros.h"

// STD includes

#include <cstddef>  // size_t</cstddef>

#include <new>      // placement new</new>

#include <vector></vector>

#include "assert.h"

// Discriminate rvalues support - either use Boost's config.hpp for automatic

// lookup,

// or deal with it manually

#ifndef TCG_RVALUES_SUPPORT

#include <boost config.hpp=""></boost>

#ifdef BOOST_NO_RVALUE_REFERENCES

#define TCG_RVALUES_SUPPORT 0

#else

#define TCG_RVALUES_SUPPORT 1

#endif

#endif

#if (TCG_RVALUES_SUPPORT > 0)

// Perfect forwarding macros

#define TCG_FORWARD_TYPE(TheType) TheType##__ &&

#define TCG_FORWARD_TEMPLATE(TheType) template <typename thetype##__=""></typename>

#define TCG_FORWARD(TheType, Val) std::forward<thetype##__>(Val)</thetype##__>

#else

// Common const reference forwarding macros

#define TCG_FORWARD_TYPE(TheType) const TheType &

#define TCG_FORWARD_TEMPLATE(TheType)

#define TCG_FORWARD(TheType, Val) Val

#endif

/*! \file     tcg_list.h

    \brief    This file contains the implementation of an indexed list,

              a list class based on a random access sequential container.

*/

//************************************************************************************

//    Preliminaries

//************************************************************************************

namespace tcg {

static const size_t _neg = -1, _invalid = -2;

}  // namespace tcg

//************************************************************************************

//    Indexed list node  definition

//************************************************************************************

namespace tcg {

/*!

  \brief    Internal node class used in the implementation of a tcg::list_base.

*/

template <typename t=""></typename>

struct _list_node {

  TCG_STATIC_ASSERT(sizeof(T) == sizeof(aligned_buffer<t>));</t>

  aligned_buffer<t> m_val;</t>

  size_t m_prev, m_next;

  TCG_DEBUG(T &m_t;)  // Provided for debuggers' convenience

public:

  _list_node() : m_prev(_neg), m_next(_invalid) TCG_DEBUG2(, m_t(value())) {}

  _list_node(const T &val)

      : m_prev(_neg), m_next(_neg) TCG_DEBUG2(, m_t(value())) {

    constructValue(val);

  }

  ~_list_node() {

    if (isValid()) destroyValue();

  }

  _list_node(const _list_node &other)

      : m_prev(other.m_prev), m_next(other.m_next) TCG_DEBUG2(, m_t(value())) {

    if (other.isValid()) constructValue(other.value());

  }

  _list_node &operator=(const _list_node &other) {

    if (isValid())

      if (other.isValid())

        value() = other.value();

      else

        destroyValue();

    else

      constructValue(other.value());

    m_prev = other.m_prev, m_next = other.m_next;

    return *this;

  }

  const T &value() const { return reinterpret_cast<const &="" t="">(m_val.m_buf); }</const>

  T &value() { return reinterpret_cast<t &="">(m_val.m_buf); }</t>

  bool isValid() const { return (m_next != _invalid); }

  void invalidate() {

    assert(isValid());

    destroyValue();

    m_next = _invalid;

  }

#if (TCG_RVALUES_SUPPORT > 0)

  _list_node(T &&val) : m_prev(_neg), m_next(_neg) TCG_DEBUG2(, m_t(value())) {

    constructValue(std::move(val));

  }

  _list_node(_list_node &&other)

      : m_prev(other.m_prev), m_next(other.m_next) TCG_DEBUG2(, m_t(value())) {

    if (other.isValid())

      constructValue(std::move(other.value())), other.invalidate();

  }

  _list_node &operator=(_list_node &&other) {

    if (isValid())

      if (other.isValid())

        value() = other.value();

      else

        destroyValue();

    else

      constructValue(std::move(other.value()));

    value() = std::move(other.value());

    m_prev = other.m_prev, m_next = other.m_next;

    return *this;

  }

#endif

public:

  void constructValue(const T &val) { new (m_val.m_buf) T(val); }

  void destroyValue() { value().~T(); }

#if (TCG_RVALUES_SUPPORT > 0)

  void constructValue(T &&val) { new (m_val.m_buf) T(std::move(val)); }

#endif

};

//************************************************************************************

//    Base indexed list  definition

//************************************************************************************

/*!

  \brief    Base class for list-like containers based on <tt>tcg::list</tt>'s

            indexed list implementation.

  \details  This class implements a barebone container class which manages

            a collection of nodes stored in an iternal random access container.

            Nodes management is limited to the \a acquisition and \a release

            of individual nodes (see the buyNode() and sellNode() functions).

            Links between list nodes must be managed externally.

  \sa       Template class \p tcg::list for an explanation of the indexed list

            container concept.

*/

template <typename t=""></typename>

class list_base {

public:

  typedef T value_type;

  typedef ::size_t size_t;

  static const size_t _neg = -1;

protected:

  typedef _list_node<t> list_node;</t>

  std::vector<list_node> m_vector;</list_node>

  size_t m_size;

  size_t m_clearedHead;

public:

  struct const_iterator

      : public std::iterator<std::bidirectional_iterator_tag, const="" t=""> {</std::bidirectional_iterator_tag,>

    const list_base *m_list;

    size_t m_idx;

    TCG_DEBUG(const list_node *m_node;)  // Provided for debuggers' convenience

  public:

    typedef const T value_type;

    typedef const T *pointer;

    typedef const T &reference;

  public:

    const_iterator() {}

    const_iterator(const list_base *list, size_t idx)

        : m_list(list), m_idx(idx) {

      TCG_DEBUG(m_node = (m_idx == _neg) ? 0 : &m_list->m_vector[m_idx]);

    }

    size_t index() const { return m_idx; }

    reference operator*() const { return (*m_list)[m_idx]; }

    pointer operator->() const { return &(*m_list)[m_idx]; }

    const_iterator operator++(int) {

      const_iterator temp(*this);

      operator++();

      return temp;

    }

    const_iterator &operator++() {

      m_idx = m_list->m_vector[m_idx].m_next;

      TCG_DEBUG(m_node = (m_idx == _neg) ? 0 : &m_list->m_vector[m_idx]);

      return *this;

    }

    const_iterator operator--(int) {

      const_iterator temp(*this);

      operator--();

      return temp;

    }

    const_iterator &operator--() {

      m_idx = m_list->m_vector[m_idx].m_prev;

      TCG_DEBUG(m_node = (m_idx == _neg) ? 0 : &m_list->m_vector[m_idx]);

      return *this;

    }

    bool operator==(const const_iterator &it) const {

      return (m_idx == it.m_idx);

    }

    bool operator!=(const const_iterator &it) const {

      return (m_idx != it.m_idx);

    }

  };

  struct iterator : public const_iterator {

  public:

    typedef T value_type;

    typedef T *pointer;

    typedef T &reference;

  public:

    iterator() {}

    iterator(list_base *list, size_t idx) : const_iterator(list, idx) {}

    reference operator*() const {

      return const_cast<reference>(const_iterator::operator*());</reference>

    }

    pointer operator->() const {

      return const_cast<pointer>(const_iterator::operator->());</pointer>

    }

    iterator operator++(int) {

      iterator temp(*this);

      operator++();

      return temp;

    }

    iterator &operator++() {

      const_iterator::operator++();

      return *this;

    }

    iterator operator--(int) {

      iterator temp(*this);

      operator--();

      return temp;

    }

    iterator &operator--() {

      const_iterator::operator--();

      return *this;

    }

  };

  friend struct iterator;

  friend struct const_iterator;

public:

  list_base() : m_size(0), m_clearedHead(_neg) {}

  list_base(size_t count, const T &val)

      : m_vector(count, list_node(val)), m_size(count), m_clearedHead(_neg) {

    assert(m_size >= 0);

    for (size_t i        = 0; i < m_size; ++i)

      m_vector[i].m_prev = i - 1, m_vector[i].m_next = i + 1;

    if (m_size > 0) m_vector[m_size - 1].m_next = _neg;

  }

  template <typename init=""></typename>

  list_base(InIt begin, InIt end)

      : m_vector(begin, end), m_size(m_vector.size()), m_clearedHead(_neg) {

    assert(m_size >= 0);

    for (size_t i        = 0; i < m_size; ++i)

      m_vector[i].m_prev = i - 1, m_vector[i].m_next = i + 1;

    if (m_size > 0) m_vector[m_size - 1].m_next = _neg;

  }

  //-----------------------------------------------------------------------------------------

  list_base(const list_base &other)

      : m_vector(other.m_vector)

      , m_size(other.m_size)

      , m_clearedHead(other.m_clearedHead) {}

  list_base &operator=(const list_base &other) {

    // Note: not using the copy-and-swap idiom. We want to attempt preservation

    // of m_vector's buffer in case its current capacity is sufficient.

    m_size        = other.m_size;

    m_clearedHead = other.m_clearedHead;

    // A clear must be performed before the actual =. It's necessary to prevent

    // copying to

    // objects that were already destroyed - but are still in the vector as

    // zombies.

    // In this case, the value-to-value vector::operator= would assume that the

    // assigned-to object is NOT a zombie - and would attempt its release, which

    // is UB!

    m_vector.clear();

    m_vector = other.m_vector;

    return *this;

  }

#if (TCG_RVALUES_SUPPORT > 0)

  list_base(list_base &&other)

      : m_vector(std::move(other.m_vector))

      , m_size(other.m_size)

      , m_clearedHead(other.m_clearedHead) {}

  list_base &operator=(list_base &&other) {

    swap(*this, std::forward<list_base>(other));</list_base>

    return *this;

  }

#endif

  T &operator[](size_t idx) {

    assert(idx < m_vector.size() && isValid(idx));

    return m_vector[idx].value();

  }

  const T &operator[](size_t idx) const {

    assert(idx < m_vector.size() && isValid(idx));

    return m_vector[idx].value();

  }

  bool isValid(size_t idx) const { return m_vector[idx].isValid(); }

  size_t size() const { return m_size; }

  size_t nodesCount() const { return m_vector.size(); }

  void reserve(size_t size) { m_vector.reserve(size); }

  size_t capacity() const { return m_vector.capacity(); }

  void clear() {

    m_size        = 0;

    m_clearedHead = _neg;

    m_vector.clear();

  }

  bool empty() const { return m_size == 0; }

  void _swap(list_base &a, list_base &b) {

    std::swap(a.m_size, b.m_size);

    std::swap(a.m_clearedHead, b.m_clearedHead);

    a.m_vector.swap(b.m_vector);

  }

#if (TCG_RVALUES_SUPPORT > 0)

  void _swap(list_base &a, list_base &&b) {

    a.m_size        = b.m_size;

    a.m_clearedHead = b.m_clearedHead;

    a.m_vector.swap(b.m_vector);

  }

  void _swap(list_base &&a, list_base &b) { swap(b, std::move(a)); }

#endif

  //-----------------------------------------------------------------------------------------

  //! Constructs from a range of (index, value) pairs

  template <typename forit=""></typename>

  list_base(ForIt begin, ForIt end, size_t nodesCount) {

    // Initialize the vector with invalid nodes up to the required nodes count

    m_vector.resize(nodesCount, list_node());

    // Iterate the range and add corresponding value pairs

    size_t lastIdx = _neg;

    for (; begin != end; ++begin) {

      size_t idx = (*begin).first;

      assert(idx >= 0);

      // Further resize the vector with holes if necessary

      if (idx >= m_vector.size()) {

        // The nodesCount hint was not sufficient. Thus, we have to readjust the

        // correct minimal

        // allocation size. Let's do it now with a further single pass toward

        // the end.

        size_t newSize = m_vector.size();

        for (ForIt it = begin; it != end; ++it)

          newSize = std::max(newSize, size_t((*it).first) + 1);

        m_vector.resize(newSize, list_node());

      }

      // Place current node in the vector

      list_node &node = m_vector[idx];

      new (&node) list_node((*begin).second);

      // Link the node

      node.m_prev                                   = lastIdx;

      if (lastIdx != _neg) m_vector[lastIdx].m_next = idx;

      lastIdx = idx;

    }

    // Finally, make up a consistent links chain for holes

    lastIdx = _neg;

    size_t n, nCount = m_vector.size();

    for (n = 0; n != nCount; ++n) {

      list_node &node = m_vector[n];

      if (!node.isValid()) node.m_prev = lastIdx, lastIdx = n;

    }

    m_clearedHead = lastIdx;

  }

  //-----------------------------------------------------------------------------------------

protected:

  TCG_FORWARD_TEMPLATE(T)

  size_t buyNode(TCG_FORWARD_TYPE(T) val) {

    size_t nodeIdx;

    list_node *node;

    ++m_size;

    if (m_clearedHead != _neg) {

      assert(m_clearedHead < m_vector.size());

      // Take the last cleared element

      nodeIdx = m_clearedHead;

      node    = &m_vector[nodeIdx];

      m_clearedHead = node->m_prev;

    } else {

      m_vector.push_back(list_node());

      nodeIdx = m_vector.size() - 1;

      node    = &m_vector[nodeIdx];

    }

    // Construct the node's value

    node->constructValue(TCG_FORWARD(T, val));

    return nodeIdx;

  }

  //-----------------------------------------------------------------------------------------

  void sellNode(size_t idx) {

    assert(isValid(idx));

    list_node &node = m_vector[idx];

    // Relink neighbours

    if (node.m_prev != _neg) m_vector[node.m_prev].m_next = node.m_next;

    if (node.m_next != _neg) m_vector[node.m_next].m_prev = node.m_prev;

    // Explicitly invoke the node's destructor

    node.invalidate();

    // Now, the node is a zombie - still, use its indices data to remember the

    // list

    // of unused nodes

    // Remember the last cleared element in element.m_prev

    node.m_prev   = m_clearedHead;

    m_clearedHead = idx;

    --m_size;

  }

  //-----------------------------------------------------------------------------------------

  void sellNodes(size_t begin, size_t end) {

    for (size_t i = begin; i != end; i = m_vector[i].m_next) sellNode(i);

  }

  //-----------------------------------------------------------------------------------------

  void move(size_t afterDst, size_t &dstBegin, size_t &dstRBegin,

            size_t srcBegin, size_t srcEnd, size_t srcRBegin) {

    if (srcBegin == _neg || srcBegin == afterDst) return;

    // afterDst-1 -> srcBegin

    {

      size_t beforeDst =

          (afterDst == _neg) ? dstRBegin : m_vector[afterDst].m_prev;

      m_vector[srcBegin].m_prev = beforeDst;

      if (beforeDst != _neg)

        m_vector[beforeDst].m_next = srcBegin;

      else

        dstBegin = srcBegin;

    }

    // srcEnd-1 -> afterDst

    {

      size_t srcLast = (srcEnd == _neg) ? srcRBegin : m_vector[srcEnd].m_prev;

      m_vector[srcLast].m_next = afterDst;  // NOTE: srcLast cannot be _neg

      if (afterDst != _neg)

        m_vector[afterDst].m_prev = srcLast;

      else

        dstRBegin = srcLast;

    }

  }

};

//************************************************************************************

//    Indexed list  definition

//************************************************************************************

/*!

  \brief    Double linked list container class with indexed access to elements.

  \details  This class is the result of implementing a double linked list using

a

            dynamic random access sequential container as the underlying pool

for

            the list's nodes.

            This is somewhat different than supplying a custom allocator to an

existing

            list implementation, like \p std::list, since:

              
  No memory model of the underlying container is actually

                    required.

              
  The underlying container provides explicit access to nodes

                    using their associated insertion indexes, so \p

std::list

                    could not be used as-is.

\n

            The nodes pool (see \p list_base) is an internal \a lazy container

that

            saves released nodes \a without actually deallocating them (of

course,

            their content is properly destroyed). They are rather stored into an

            internal \a stack of released nodes, ready to be reacquired.

              \par Features

              \li  Insertion indexes are automatically generated keys with the

same

                   access time of the undelying container (typically super-fast

                   \p O(1)).

              \li  Stable indexes and iterators with respect to every

operation.

              \li  Copying an indexed list \a preserves the original indexes.

              \li  Indexes are process independent - they can be saved

                   on file and restored later (although you probably want to

                   \a squeeze the list before saving).

              \par Use cases

            This class is surprisingly useful for cross-referencing.

            A graph data structure, for example, can be implemented using a pair

of

            indexed lists for vertexes and edges.

              \par Known issues

            The lazy nature of this container class may require \a squeezing the

list's

            content at strategic places in your code, as noted before.

            Beware that composite cross-referencing may be hard to track \a

precisely

            during this particular operation.

  \remark   Current implementation explicitly uses an \p std::vector class as

the

            underlying random access container. Future improvements will make

the

            container class a template parameter.

  \sa       Template class \p tcg::Mesh for a notable use case.

*/

template <typename t=""></typename>

class list : public list_base<t> {</t>

  size_t m_begin, m_rbegin;

protected:

  typedef typename list_base<t>::list_node list_node;</t>

  using list_base<t>::m_vector;</t>

public:

  struct iterator : public list_base<t>::iterator {</t>

    iterator() {}

    iterator(list *l, size_t idx) : list_base<t>::iterator(l, idx) {}</t>

    iterator &operator++() {

      list_base<t>::iterator::operator++();</t>

      return *this;

    }

    iterator &operator--() {

      if (this->m_idx == _neg)

        operator=(static_cast<list *="">(this->m_list)->last());</list>

      else

        list_base<t>::iterator::operator--();</t>

      return *this;

    }

    iterator operator++(int) {

      iterator temp(*this);

      operator++();

      return temp;

    }

    iterator operator--(int) {

      iterator temp(*this);

      operator--();

      return temp;

    }

  };

  struct const_iterator : public list_base<t>::const_iterator {</t>

    const_iterator() {}

    const_iterator(const list *l, size_t idx)

        : list_base<t>::const_iterator(l, idx) {}</t>

    const_iterator &operator++() {

      list_base<t>::const_iterator::operator++();</t>

      return *this;

    }

    const_iterator &operator--() {

      if (this->m_idx == _neg)

        operator=(static_cast<const *="" list="">(this->m_list)->last());</const>

      else

        list_base<t>::const_iterator::operator--();</t>

      return *this;

    }

    const_iterator operator++(int) {

      const_iterator temp(*this);

      operator++();

      return temp;

    }

    const_iterator operator--(int) {

      const_iterator temp(*this);

      operator--();

      return temp;

    }

  };

public:

  list() : m_begin(_neg), m_rbegin(_neg) {}

  list(size_t count, const T &val)

      : list_base<t>(count, val), m_begin(0), m_rbegin(count - 1) {}</t>

  template <typename init=""></typename>

  list(InIt begin, InIt end)

      : list_base<t>(begin, end)</t>

      , m_begin(list_base<t>::m_size ? 0 : _neg)</t>

      , m_rbegin(list_base<t>::m_size - 1) {}</t>

  //! Constructs from a range of (index, value) pairs

  template <typename bidit=""></typename>

  list(BidIt begin, BidIt end, size_t nodesCount)

      : list_base<t>(begin, end, nodesCount) {</t>

    if (begin != end) m_begin = (*begin).first, m_rbegin = (*--end).first;

  }

  //-----------------------------------------------------------------------------------------

  list(const list &other)

      : list_base<t>(other), m_begin(other.m_begin), m_rbegin(other.m_rbegin) {}</t>

  /*!

\warning  \p tcg::list has a different copy behavior from other container

classes, since

        it is intended to preserve the source's node indices in the process.

        This means that no value-to-value assignment can take place, and thus

<tt>operator=</tt>'s

        behavior is equivalent to first clearing it, and then copy-constructing

each value.

        This typically leads to performance penalties with respect to other

container classes that

        implement value-to-value assignments, like \p std::vector in case its

capacity is not exceeded.

*/

  list &operator=(const list &other) {

    m_begin = other.m_begin, m_rbegin = other.m_rbegin;

    list_base<t>::operator=(other);</t>

    return *this;

  }

#if (TCG_RVALUES_SUPPORT > 0)

  list(list &&other)

      : list_base<t>(std::forward<list_base<t>>(other))</list_base<t></t>

      , m_begin(other.m_begin)

      , m_rbegin(other.m_rbegin) {}

  list &operator=(list &&other) {

    swap(*this, std::forward<list>(other));</list>

    return *this;

  }

#endif

  //-----------------------------------------------------------------------------------------

  TCG_FORWARD_TEMPLATE(T)

  size_t insert(size_t idx, TCG_FORWARD_TYPE(T) val) {

    assert(idx == _neg || list_base<t>::isValid(idx));</t>

    size_t nodeIdx  = list_base<t>::buyNode(TCG_FORWARD(T, val));</t>

    list_node &node = m_vector[nodeIdx];

    // Update links

    if (idx != _neg) {

      // node has a valid next

      list_node &next = m_vector[idx];

      node.m_prev                                           = next.m_prev;

      next.m_prev                                           = nodeIdx;

      node.m_next                                           = idx;

      if (node.m_prev != _neg) m_vector[node.m_prev].m_next = nodeIdx;

    } else {

      node.m_next                                     = _neg;

      node.m_prev                                     = m_rbegin;

      if (m_rbegin != _neg) m_vector[m_rbegin].m_next = nodeIdx;

      m_rbegin                                        = nodeIdx;

    }

    if (idx == m_begin) m_begin = nodeIdx;

    return nodeIdx;

  }

  template <typename iter=""></typename>

  size_t insert(size_t idx, Iter begin, Iter end) {

    if (begin == end) return idx;

    assert(idx == _neg || list_base<t>::isValid(idx));</t>

    size_t res = insert(idx, *begin);

    for (++begin; begin != end; ++begin) insert(idx, *begin);

    return res;

  }

  size_t erase(size_t idx) {

    assert(list_base<t>::isValid(idx));</t>

    if (idx == m_begin) m_begin   = m_vector[idx].m_next;

    if (idx == m_rbegin) m_rbegin = m_vector[idx].m_prev;

    size_t result = m_vector[idx].m_next;

    list_base<t>::sellNode(idx);</t>

    return result;

  }

  size_t erase(size_t begin, size_t end) {

    assert(list_base<t>::isValid(begin));</t>

    if (begin == m_begin) m_begin = end;

    if (end == m_rbegin) m_rbegin = m_vector[begin].m_prev;

    list_base<t>::sellNodes(begin, end);</t>

    return end;

  }

  void clear() {

    list_base<t>::clear();</t>

    m_begin = m_rbegin = _neg;

  }

  void swap(list &other) {

    _swap(*this, other);

    std::swap(m_begin, other.m_begin);

    std::swap(m_rbegin, other.m_rbegin);

  }

  void swap(list &a, list &b) { a.swap(b); }

#if (TCG_RVALUES_SUPPORT > 0)

  void swap(list &&other) {

    this->_swap(*this, std::move(other));

    m_begin  = other.m_begin;

    m_rbegin = other.m_rbegin;

  }

  void swap(list &a, list &&b) { a.swap(std::move(b)); }

  void swap(list &&a, list &b) { b.swap(std::move(a)); }

#endif

  //-----------------------------------------------------------------------------------------

  /*!

\details  This function is \p tcg::list's counterpart to \p std::list::splice().

        It moves the specified range to a different part of the list, \a without

        touching any element elements - just by altering node links.

\note     Unlike \p std::list::splice(), the list must be the same.

*/

  void move(size_t afterDst, size_t srcBegin,

            size_t srcEnd)  //! Moves range <tt>[srcBegin, srcEnd)</tt> right

                            //! before afterDst.      \param afterDst  Index

                            //! right after the destination position. \param

                            //! srcBegin  Start index of the moved range. \param

                            //! srcEnd  End index of the moved range.

  {

    return move(afterDst, m_begin, m_rbegin, srcBegin, srcEnd, m_rbegin);

  }

  /*!

\sa       The equivalent function move(size_t, size_t, size_t).

*/

  void move(iterator afterDst, iterator srcBegin,

            iterator srcEnd)  //! Moves range <tt>[srcBegin, srcEnd)</tt> right

                              //! before afterDst.      \param afterDst

                              //! Iterator right after the destination position.

                              //! \param srcBegin  Start of the moved range.

                              //! \param srcEnd  End of the moved range.

  {

    assert(afterDst.m_list == this && srcBegin.m_list == this &&

           srcEnd.m_list == this);

    return move(afterDst.m_idx, srcBegin.m_idx, srcEnd.m_idx);

  }

  //-----------------------------------------------------------------------------------------

  iterator insert(iterator it, const T &val) {

    return iterator(this, insert(it.m_idx, val));

  }

  iterator erase(iterator it) { return iterator(this, erase(it.m_idx)); }

  template <typename iter=""></typename>

  iterator insert(iterator it, Iter begin, Iter end) {

    return iterator(this, insert(it.m_idx, begin, end));

  }

  iterator erase(iterator begin, iterator end) {

    return iterator(this, erase(begin.m_idx, end.m_idx));

  }