SPAR/AIModule/SparAIModule/Utils/SafeList.h

Go to the documentation of this file.

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

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

class SafeListBase
{
public:
  struct ConstFunctionReturn
  {
    ConstFunctionReturn()
      : breakIteration(false) {}
    ConstFunctionReturn(bool _breakIteration)
      : breakIteration(_breakIteration) {}
    bool breakIteration;
  };

  struct FunctionReturn : ConstFunctionReturn
  {
    FunctionReturn()
      : ConstFunctionReturn(), deleteCurrent(false) {}
    FunctionReturn(bool _deleteCurrent, bool _breakIteration)
      : ConstFunctionReturn(_breakIteration), deleteCurrent(_deleteCurrent) {}
    FunctionReturn(ConstFunctionReturn r)
      : ConstFunctionReturn(r), deleteCurrent(false) {}
    bool deleteCurrent;
  };
};

template <class T>
class SafeList : public SafeListBase
{
protected:
  friend class ConstSafeListAdaptor<T>;
  friend class SafeListAdaptor<T>;
  class Wrapper
  {
  public:
    Wrapper(T t)
      : m_t(t), m_deleted(false) {}
    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;
    T m_t;
    mutable bool m_deleted;
  };

public:
  typedef typename std::list<Wrapper>::iterator iterator;
  typedef typename std::list<Wrapper>::const_iterator const_iterator;

  SafeList()
    : m_size(0)
    , m_nbCurrentIterations(0)
  {
  }

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

  iterator add(const T& t)
  {
    ++m_size;
    return m_list.insert(m_list.end(), t);
  }

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

    bool breakIteration = false;
    for (std::list<Wrapper>::iterator it = m_list.begin(); !breakIteration && it != m_list.end(); ++it)
    {
      if (!(*it).m_deleted)
      {
        FunctionReturn result = function((*it).m_t);
        if (result.deleteCurrent)
        {
          (*it).m_deleted = true;
          --m_size;
        }
        breakIteration = result.breakIteration;
      }
    }

    return function;
  }

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

    bool breakIteration = false;
    for (std::list<Wrapper>::const_iterator it = m_list.begin(); !breakIteration && it != m_list.end(); ++it)
    {
      if (!(*it).m_deleted)
      {
        ConstFunctionReturn result = function((*it).m_t);
        breakIteration = result.breakIteration;
      }
    }

    return function;
  }

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

    if (!m_list.empty())
    {
      std::list<Wrapper>::iterator stop = m_list.end();
      --stop;
      std::list<Wrapper>::iterator it = m_list.begin();
      bool breakIteration = false;
      do
      {
        if (!(*it).m_deleted)
        {
          FunctionReturn 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 for_each(Function function) const
  {
    Iteration iteration(*this);

    if (!m_list.empty())
    {
      std::list<Wrapper>::const_iterator stop = m_list.end();
      --stop;
      std::list<Wrapper>::const_iterator it = m_list.begin();
      bool breakIteration = false;
      do
      {
        if (!(*it).m_deleted)
        {
          ConstFunctionReturn result = function((*it).m_t);
          breakIteration = result.breakIteration;
        }
      } while (!breakIteration && it++ != stop);
    }

    return function;
  }

  void erase(iterator position)
  {
    assert(!(*position).m_deleted);
    (*position).m_deleted = true;
    --m_size;
    if (m_nbCurrentIterations == 0)
    {
      m_list.erase(position);
    }
  }

  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;
  }

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

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

  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;

  void iterationStarted(Iteration& iteration) const
  {
    unused(iteration);

    ++m_nbCurrentIterations;
  }

  void iterationEnded(Iteration& iteration) const
  {
    unused(iteration);

    if (--m_nbCurrentIterations == 0)
    {
      std::list<Wrapper>::iterator it = m_list.begin();
      while (it != m_list.end())
      {
        std::list<Wrapper>::iterator next = it;
        ++next;
        if ((*it).m_deleted)
        {
          m_list.erase(it);
        }
        it = next;
      }
    }
  }

  mutable std::list<Wrapper> m_list;
  mutable size_t m_nbCurrentIterations;
  size_t m_size;
};