lazy_set.hh

// Copyright (C) 2007, 2008, 2009 EPITA Research and Development Laboratory (LRDE)
//
// This file is part of Olena.
//
// Olena is free software: you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation, version 2 of the License.
//
// Olena is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Olena.  If not, see <http://www.gnu.org/licenses/>.
//
// As a special exception, you may use this file as part of a free
// software project without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to produce
// an executable, this file does not by itself cause the resulting
// executable to be covered by the GNU General Public License.  This
// exception does not however invalidate any other reasons why the
// executable file might be covered by the GNU General Public License.

#ifndef MLN_UTIL_LAZY_SET_HH
# define MLN_UTIL_LAZY_SET_HH

# include <vector>
# include <set>
# include <iterator>
# include <algorithm>

# include <mln/core/internal/force_exact.hh>
# include <mln/core/contract.hh>


namespace mln
{

  namespace util
  {

    template <typename E>
    class lazy_set_
    {
    public:

      typedef E value;

      lazy_set_<E>& insert(const E& elt);


      lazy_set_<E>& remove(const E& elt);


      const E& element(unsigned i) const;

      const E& operator[](unsigned i) const;

      unsigned nelements() const;


      bool has(const E& elt) const;


      bool is_empty() const;


      void clear();


      const std::vector<E>& vect() const;

      lazy_set_();

      void set_const_mode(bool mode);

      bool get_mode() const;

    private:

      mutable std::vector<E> v_;

      std::set<E> s_;


      void update_() const;

      mutable bool needs_update_;

      bool mode_;
    };


# ifndef MLN_INCLUDE_ONLY

    template <typename E>
    inline
    lazy_set_<E>::lazy_set_()
    {
      needs_update_ = false;
      mode_ = false;
    }

    template <typename E>
    inline
    lazy_set_<E>&
    lazy_set_<E>::insert(const E& elt)
    {
      mln_assertion(!mode_);
      s_.insert(elt);
      if (needs_update_ == false)
        needs_update_ = true;
      return mln::internal::force_exact< lazy_set_<E> >(*this);
    }

    template <typename E>
    inline
    lazy_set_<E>&
    lazy_set_<E>::remove(const E& elt)
    {
      mln_assertion(!mode_);
      // FIXME : doesn't compile
      std::remove(s_.begin(), s_.end(), elt);
      if (needs_update_ == false)
        needs_update_ = true;
      return mln::internal::force_exact< lazy_set_<E> >(*this);
    }

    template <typename E>
    inline
    const E&
    lazy_set_<E>::element(unsigned i) const
    {
      assert((!mode_ && i < s_.size())
             || i < v_.size());
      if (!mode_)
        if (needs_update_)
          update_();
      return v_[i];
    }

    template <typename E>
    inline
    const E&
    lazy_set_<E>::operator[](unsigned i) const
    {
      return this->element(i);
    }

    template <typename E>
    inline
    unsigned
    lazy_set_<E>::nelements() const
    {
      if (!mode_)
        return s_.size();
      else
        return v_.size();
    }

    template <typename E>
    inline
    bool
    lazy_set_<E>::has(const E& elt) const
    {
      if (!mode_)
        return s_.find(elt) != s_.end();
      else
        return v_.find(elt) != v_.end();
    }

    template <typename E>
    inline
    bool
    lazy_set_<E>::is_empty() const
    {
      return nelements() == 0;
    }

    template <typename E>
    inline
    void
    lazy_set_<E>::clear()
    {
      v_.clear();
      s_.clear();
      needs_update_ = false;
      mode_ = false;
      mln_postcondition(is_empty());
    }

    template <typename E>
    inline
    const std::vector<E>&
    lazy_set_<E>::vect() const
    {
      if (!mode_)
        if (needs_update_)
          update_();
      return v_;
    }

    template <typename E>
    inline
    void
    lazy_set_<E>::set_const_mode(bool mode)
    {
      if (mode != mode_)
      {
        if (mode)
        {
          if (needs_update_)
            update_();
          s_.clear();
        }
        else
        {
          mln_assertion(s_.size() == 0);
          for (typename std::vector<E>::iterator it = v_.begin();
               it != v_.end(); it++)
            s_.insert(*it);
          needs_update_ = false;
        }
        mode_ = mode;
      }
    }

    template <typename E>
    inline
    bool
    lazy_set_<E>::get_mode() const
    {
      return mode_;
    }

    template <typename E>
    inline
    void
    lazy_set_<E>::update_() const
    {
      mln_precondition(needs_update_ && !mode_);
      v_.clear();
      std::copy(s_.begin(), s_.end(), std::back_inserter(v_));
      // no s_.clear() here:
      // - we want to keep information up-to-date in s_
      // - we want to save some execution time
      needs_update_ = false;
    }

    // FIXME : ambiguous with site_set operator <<
    //     template <typename E>
    //     std::ostream& operator<<(std::ostream& ostr,
    //                       const lazy_set_<E>& s)
    //     {
    //       ostr << '[';
    //       const unsigned n = s.nelements();
    //       for (unsigned i = 0; i < n; ++i)
    //  ostr << s.element(i)
    //       << (i == s.nelements() - 1 ? ']' : ',');
    //       return ostr;
    //     }

# endif // ! MLN_INCLUDE_ONLY

  } // end of namespace mln::util

} // end of namespace mln


#endif // ! MLN_UTIL_LAZY_SET_HH