SPAR/AIModule/SparAIModule/Utils/SafeMultiset.h

Go to the documentation of this file.

#pragma once
#include <set>
#include <queue>
#include <cassert>

class SafeMultisetBase
{
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 Compare = std::less<T>>
class SafeMultiset : public SafeMultisetBase
{
public:
  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; }
  protected:
    friend class SafeMultiset;
    T m_t;
    bool m_deleted;
  };

protected:
  class CompareWrapper
  {
  public:
    CompareWrapper(const Compare& compare)
      : m_compare(compare) {}
    bool operator()(const Wrapper& wrapper1, const Wrapper& wrapper2) const
    {
      return m_compare(wrapper1.m_t, wrapper2.m_t); 
    }
  private:
    const Compare& m_compare;
  };

public:
  typedef typename std::multiset<Wrapper, CompareWrapper>::iterator iterator;

  SafeMultiset(const Compare& compare = Compare())
    : m_compare(compare)
    , m_multiset(CompareWrapper(m_compare))
    , m_size(0)
    , m_first(NULL)
  {
  }

  //iterator insert(iterator position, const T& t)
  //{
  //  ++m_size;
  //  iterator it = m_multiset.insert(position, t);
  //  for (ThresholdPriorityQueue* queue = m_first; queue != NULL; queue = queue->getNext())
  //  {
  //    queue->push(&(*it));
  //  }
  //  return it;
  //}

  iterator insert(const T& t)
  {
    ++m_size;
    iterator it = m_multiset.insert(t);
    for (Iteration* iteration = m_first; iteration != NULL; iteration = iteration->getNext())
    {
      iteration->pushNewElement(&(*it));
    }
    return it;
  }
 
  template <class Function>
  Function do_while(Function function)
  {
    Iteration iteration(*this);

    bool breakIteration = false;
    for (std::multiset<Wrapper, CompareWrapper>::iterator it = m_multiset.begin(); !breakIteration && it != m_multiset.end(); ++it)
    {
      Wrapper& current = *it;
      if (!current.m_deleted)
      {
        iteration.setElementsAdditionThreshold(&current);
        FunctionReturn result = function(current);
        if (result.deleteCurrent)
        {
          current.m_deleted = true;
          --m_size;
        }
        bool breakIteration = result.breakIteration;
        // Iterate over newly created higher priority elements if any
        while (!breakIteration && iteration.hasNewElements())
        {
          Wrapper* wrapper = iteration.popNewElement();
          assert(CompareWrapper(m_compare)(*wrapper, current));
          if (!wrapper->m_deleted)
          {
            FunctionReturn result = function(*wrapper);
            if (result.deleteCurrent)
            {
              wrapper->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::multiset<Wrapper, CompareWrapper>::const_iterator it = m_multiset.begin(); !breakIteration && it != m_multiset.end(); ++it)
    {
      const Wrapper& current = *it;
      if (!current.m_deleted)
      {
        iteration.setElementsAdditionThreshold(&current);
        ConstFunctionReturn result = function(current);
        bool breakIteration = result.breakIteration;
        // Iterate over newly created higher priority elements if any
        while (!breakIteration && iteration.hasNewElements())
        {
          Wrapper* wrapper = iteration.popNewElement();
          assert(CompareWrapper(m_compare)(*wrapper, current));
          if (!wrapper->m_deleted)
          {
            ConstFunctionReturn result = function(*wrapper);
            breakIteration = result.breakIteration;
          }
        }
      }
    }
    return function;
  }

  void erase(iterator position)
  {
    assert(!(*position).m_deleted);
    (*position).m_deleted = true;
    --m_size;
    if (m_first == NULL)
    {
      m_multiset.erase(position);
    }
  }

  size_t size() const
  {
    assert(m_first != NULL || m_size == m_multiset.size());
    return m_size;
  }

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

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

  class Iteration
  {
  public:
    Iteration(const SafeMultiset& safeMultiset)
      : m_safeMultiset(safeMultiset)
      , m_compare(safeMultiset.m_compare)
      , m_newElements(ComparePtrWrapper(m_compare))
      , m_threshold(NULL)
      , m_next(NULL)
    {
      m_safeMultiset.iterationStarted(*this);
    }
    ~Iteration()
    {
      m_safeMultiset.iterationEnded(*this);
    }
    Iteration* getNext()
    {
      return m_next;
    }
    void setNext(Iteration* next)
    {
      m_next = next;
    }
    void setElementsAdditionThreshold(const Wrapper* threshold)
    {
      m_threshold = threshold;
    }
    bool hasNewElements() const
    {
      return !m_newElements.empty();
    }
    bool pushNewElement(Wrapper* element)
    {
      assert(m_threshold != NULL);
      bool add = m_compare(*element, *m_threshold); // if new >= current, the new element will be inserted after the current one
      if (add)
        m_newElements.push(element);
      return add;
    }
    Wrapper* popNewElement()
    {
      Wrapper* element = m_newElements.top();
      m_newElements.pop();
      return element;
    }
  private:
    Iteration(const Iteration&);
    Iteration& operator=(const Iteration&);

  protected:
    class ComparePtrWrapper
    {
    public:
      ComparePtrWrapper(const CompareWrapper& compare)
        : m_compare(compare) {}
      bool operator()(const Wrapper* wrapper1, const Wrapper* wrapper2) const
      {
        return !m_compare(*wrapper1, *wrapper2); 
      }
    private:
      const CompareWrapper& m_compare;
    };

    const SafeMultiset& m_safeMultiset;
    const CompareWrapper m_compare;
    std::priority_queue<Wrapper*, std::vector<Wrapper*>, ComparePtrWrapper> m_newElements;
    const Wrapper* m_threshold;
    Iteration* m_next;
  };
  friend class Iteration;

  void iterationStarted(Iteration& iteration) const
  {
    iteration.setNext(m_first);
    m_first = &iteration;
  }

  void iterationEnded(Iteration& iteration) const
  {
    m_first = iteration.getNext();
    if (m_first == NULL)
    {
      std::multiset<Wrapper, CompareWrapper>::iterator it = m_multiset.begin();
      while (it != m_multiset.end())
      {
        std::multiset<Wrapper, CompareWrapper>::iterator next = it;
        ++next;
        if ((*it).m_deleted)
        {
          m_multiset.erase(it);
        }
        it = next;
      }
    }
  }

  const Compare m_compare;
  mutable std::multiset<Wrapper, CompareWrapper> m_multiset;
  mutable Iteration* m_first;
  size_t m_size;
};