#pragma once
#include <list>
#include <cassert>

template <class T> class ConstSafeListAdaptor;
template <class T> class SafeListAdaptor;

/**
 * @brief Base class for safe list, whose only purpose is to declare the return structures
 *        so that they are accessible without going through the templated safe list class.
 */
class SafeListBase
{
public:
  struct ConstIterationStep
  {
    ConstIterationStep()
      : breakIteration(false) {}
    ConstIterationStep(bool _breakIteration)
      : breakIteration(_breakIteration) {}
    bool breakIteration;
  };

  struct IterationStep : ConstIterationStep
  {
    IterationStep()
      : ConstIterationStep(), deleteCurrent(false) {}
    IterationStep(bool _deleteCurrent, bool _breakIteration)
      : ConstIterationStep(_breakIteration), deleteCurrent(_deleteCurrent) {}
    IterationStep(ConstIterationStep r)
      : ConstIterationStep(r), deleteCurrent(false) {}
    bool deleteCurrent;
  };
};

/**
 * @brief A safe list is like a regular list storing values, but in addition it allows one
 *        to iterate over its elements while some are being deleted and new ones are being added.
 *        Multiple iterations can be performed on the safe list at the same time. To allow this,
 *        deleted elements are kept in the safe list until the last iteration has finished, which is
 *        when they are removed.
 * @tparam T The type of values to store.
 */
template <class T>
class SafeList : public SafeListBase
{
protected:
  friend class ConstSafeListAdaptor<T>;
  friend class SafeListAdaptor<T>;
  /**
   * @brief Wraps an element of the list by including other data, in particular 
   *        a flag indicating whether this element has been deleted.
   */
  class Wrapper
  {
  public:
    Wrapper(T t)
      : m_t(t), m_deleted(false) {}
    /**
     * @return Whether this element has been deleted.
     */
    bool isDeleted() const { return m_deleted; }
    operator T&() { return m_t; }
    operator const T&() const { return m_t; }
    bool operator==(const Wrapper& other) const { return m_t == other.m_t; }
    bool operator!=(const Wrapper& other) const { return m_t != other.m_t; }
  protected:
    friend class SafeList;
    /**
     * @brief The wrapped element.
     */
    T m_t;
    /**
     * @brief Whether the element has been deleted.
     */
    mutable bool m_deleted;
  };
  typedef typename std::list<Wrapper>::const_iterator internal_const_iterator;
  typedef typename std::list<Wrapper>::iterator internal_iterator;

public:
  class iterator
  {
  public:
    iterator()
    {}
    iterator(internal_iterator it)
      : m_it(it)
    {}
    typename internal_iterator::reference operator*() const
    {
      return *m_it;
    }
    typename internal_iterator::reference operator->() const
    {
      return *m_it;
    }
    bool operator==(const iterator& it) const
    {
      return m_it == it.m_it;
    }
  private:
    friend class SafeList;

    internal_iterator m_it;
  };

  /**
   * @brief Safe list constructor.
   */
  SafeList()
    : m_size(0)
    , m_nbCurrentIterations(0)
  {
  }

  SafeList(const SafeList& other)
    : m_size(0)
    , m_nbCurrentIterations(0)
  {
    for (internal_const_iterator it = other.m_list.begin(); it != other.m_list.end(); ++it)
    {
      if (!it->isDeleted())
        add(*it);
    }
  }

  /**
   * @brief Adds a new element to the safe list.
   * @param t The new element to add.
   * @return The position of the newly inserted element.
   */
  iterator add(const T& t)
  {
    ++m_size;
    internal_iterator it = m_list.insert(m_list.end(), t);
    return iterator(it);
  }

  /**
   * @brief Adds a new element to the safe list.
   * @param pos The position at which the new element must be added.
   * @param t The new element to add.
   * @return The position of the newly inserted element.
   */
  iterator add(iterator pos, const T& t)
  {
    ++m_size;
    m_list.insert(pos.m_it, t);
    return iterator(--(internal_iterator(pos.m_it)));
  }

  iterator end()
  {
    return iterator(m_list.end());
  }

  /**
   * @brief Iterates on all the elements in the list, including potential new elements added up during the iteration.
   * @tparam Function The type of function to apply to the elements. The function must take an element T as
   *                  unique parameter and return a IterationStep result;
   * @param function The function to apply to the elements. The function returns whether to break the iteration and
   *                 whether the current element iterated over should be deleted.
   * @return A copy of the function applied to the elements.
   */
  template <class Function>
  Function do_while(Function function)
  {
    Iteration iteration(*this);

    bool breakIteration = false;
    for (internal_iterator it = m_list.begin(); !breakIteration && it != m_list.end(); ++it)
    {
      if (!(*it).m_deleted)
      {
        IterationStep result = function((*it).m_t);
        if (result.deleteCurrent)
        {
          (*it).m_deleted = true;
          --m_size;
        }
        breakIteration = result.breakIteration;
      }
    }

    return function;
  }

  /**
   * @brief Iterates on all the elements in the list, including potential new elements added up during the iteration.
   * @tparam Function The type of function to apply to the elements. The function must take an element T as
   *                  unique parameter and return a ConstIterationStep result;
   * @param function The function to apply to the elements. The function returns whether to break the iteration.
   * @return A copy of the function applied to the elements.
   */
  template <class Function>
  Function do_while(Function function) const
  {
    Iteration iteration(*this);

    bool breakIteration = false;
    for (internal_const_iterator it = m_list.begin(); !breakIteration && it != m_list.end(); ++it)
    {
      if (!(*it).m_deleted)
      {
        ConstIterationStep result = function((*it).m_t);
        breakIteration = result.breakIteration;
      }
    }

    return function;
  }

  /**
   * @brief Iterates on the elements in the list, not considering new elements added up during the iteration.
   * @tparam Function The type of function to apply to the elements. The function must take an element T as
   *                  unique parameter and return a IterationStep result;
   * @param function The function to apply to the elements. The function returns whether to break the iteration and
   *                 whether the current element iterated over should be deleted.
   * @return A copy of the function applied to the elements.
   */
  template <class Function>
  Function for_each(Function function)
  {
    Iteration iteration(*this);

    if (!m_list.empty())
    {
      internal_iterator stop = --m_list.end();
      internal_iterator it = m_list.begin();
      bool breakIteration = false;
      do
      {
        if (!(*it).m_deleted)
        {
          IterationStep result = function((*it).m_t);
          if (result.deleteCurrent)
          {
            (*it).m_deleted = true;
            --m_size;
          }
          breakIteration = result.breakIteration;
        }
      } while (!breakIteration && it++ != stop);
    }
    return function;
  }

  template <class Function>
  Function reverse_for_each(Function function)
  {
    Iteration iteration(*this);

    if (!m_list.empty())
    {
      std::list<Wrapper>::reverse_iterator stop = --m_list.rend();
      std::list<Wrapper>::reverse_iterator it = m_list.rbegin();
      bool breakIteration = false;
      do
      {
        if (!(*it).m_deleted)
        {
          IterationStep result = function((*it).m_t);
          if (result.deleteCurrent)
          {
            (*it).m_deleted = true;
            --m_size;
          }
          breakIteration = result.breakIteration;
        }
      } while (!breakIteration && it++ != stop);
    }
    return function;
  }

  /**
   * @brief Iterates on the elements in the list, not considering new elements added up during the iteration.
   * @tparam Function The type of function to apply to the elements. The function must take an element T as
   *                  unique parameter and return a ConstIterationStep result;
   * @param function The function to apply to the elements. The function returns whether to break the iteration.
   * @return A copy of the function applied to the elements.
   */
  template <class Function>
  Function for_each(Function function) const
  {
    Iteration iteration(*this);

    if (!m_list.empty())
    {
      internal_const_iterator stop = --m_list.end();
      internal_const_iterator it = m_list.begin();
      bool breakIteration = false;
      do
      {
        if (!(*it).m_deleted)
        {
          ConstIterationStep result = function((*it).m_t);
          breakIteration = result.breakIteration;
        }
      } while (!breakIteration && it++ != stop);
    }
    return function;
  }

  template <class Function>
  Function reverse_for_each(Function function) const
  {
    Iteration iteration(*this);

    if (!m_list.empty())
    {
      std::list<Wrapper>::reverse_const_iterator stop = --m_list.rend();
      std::list<Wrapper>::reverse_const_iterator it = m_list.rbegin();
      bool breakIteration = false;
      do
      {
        if (!(*it).m_deleted)
        {
          ConstIterationStep result = function((*it).m_t);
          breakIteration = result.breakIteration;
        }
      } while (!breakIteration && it++ != stop);
    }
    return function;
  }

  /**
   * @brief Erases the element at the given position from the list.
   * @param position Iterator to the element to remove.
   */
  void erase(iterator position)
  {
    assert(!position.m_it->m_deleted);
    position.m_it->m_deleted = true;
    --m_size;
    if (m_nbCurrentIterations == 0)
    {
      m_list.erase(position.m_it);
    }
  }

  void increment(iterator& it) const
  {
    do
    {
      ++it.m_it;
    } while (it.m_it != m_list.end() && it.m_it->isDeleted());
  }

  /**
   * @return The number of elements present in the list.
   */
  size_t size() const
  {
    assert(m_nbCurrentIterations != 0 || m_size == m_list.size()); // m_list includes deleted elements if m_nbCurrentIterations > 0
    return m_size;
  }

  /**
   * @return Whether the list is empty.
   */
  bool empty() const
  {
    return size() == 0;
  }

protected:
  SafeList& operator=(const SafeList& other) const;

  /**
   * @brief Provides an automatic (and exception-aware, although there's no need to be) mechanism 
   *        for acquisition and release.
   */
  class Iteration
  {
  public:
    Iteration(const SafeList& safeList)
      : m_safeList(safeList)
    {
      m_safeList.iterationStarted(*this);
    }
    ~Iteration()
    {
      m_safeList.iterationEnded(*this);
    }
  private:
    Iteration(const Iteration&);
    Iteration& operator=(const Iteration&);

    const SafeList& m_safeList;
  };
  friend class Iteration;

  /**
   * @brief This method is called by Iteration instances to signal that another iteration
   *        over the safe list is being performed.
   * @param iteration The new iteration being performed.
   */
  void iterationStarted(Iteration& iteration) const
  {
    unused(iteration);

    ++m_nbCurrentIterations;
  }

  /**
   * @brief This method is called by Iteration instances to signal that an iteration over
   *        the safe list has ended. If this was the last iteration, elements marked as 'deleted' 
   *        are removed.
   * @param iteration The iteration having ended.
   */
  void iterationEnded(Iteration& iteration) const
  {
    unused(iteration);

    if (--m_nbCurrentIterations == 0)
    {
      internal_iterator it = m_list.begin();
      while (it != m_list.end())
      {
        internal_iterator next = it;
        ++next;
        if ((*it).m_deleted)
        {
          m_list.erase(it);
        }
        it = next;
      }
    }
  }

  /**
   * @brief An inner list storing all the elements on the safe list, including deleted elements which
   *        are removed when all iterations over the safe list have ended.
   */
  mutable std::list<Wrapper> m_list;
  /**
   * @brief The number of iterations currently being performed on the safe list.
   */
  mutable size_t m_nbCurrentIterations;
  /**
   * @brief The number of elements in the safe list, excluding deleted ones.
   *        Note that this number should be equal to the number of elements in m_list, when no iterations
   *        are being performed on the safe list.
   */
  size_t m_size;
};
