id_map.hpp

Go to the documentation of this file.

#ifndef ID_MAP_HPP_
#define ID_MAP_HPP_
#include <vector>
#include "boost/assert.hpp"
#include "vdj_pipe/detail/disable_warnings.hpp"
#include "vdj_pipe/detail/vector_set.hpp"
#include "vdj_pipe/exception.hpp"

namespace vdj_pipe{ namespace detail{

template<class Id, class Obj, template<class,class> class Stor = std::vector >
class Id_map{
   typedef Stor<Obj, std::allocator<Obj> > vector_t;

public:
   typedef Id_map self_type;
   typedef Id id_type;
   typedef Obj value_type;
   typedef typename vector_t::iterator iterator;
   typedef typename vector_t::const_iterator const_iterator;
   typedef base_exception Err;

   explicit Id_map(const id_type id0)
   : vid_(),
     erased_(),
     id0_(id0)
   {}

   std::size_t size() const { return vid_.size() - erased_.size(); }
   const_iterator begin() const {return vid_.begin();}
   const_iterator end() const {return vid_.end();}
   bool empty() const {return !(vid_.size() - erased_.size());}
   id_type min_id() const {return id0_;}
   id_type max_id() const {return pos2id(vid_.size()-1);}
   void reserve(const id_type id) {vid_.reserve(vpos(id) + 1);}

   value_type const& operator[](const id_type id) const {
      BOOST_ASSERT( check_range(id) && "invalid ID" );
      return vid_[vpos(id)];
   }

   value_type& operator[](const id_type id) {
      BOOST_ASSERT( check_range(id) && "invalid ID" );
      return vid_[vpos(id)];
   }

   value_type const& at(const id_type id) const {
      if( ! check_range(id) ) BOOST_THROW_EXCEPTION(
               Err()
               << Err::msg_t("invalid ID")
               << Err::int1_t(id())
      );
      return vid_[vpos(id)];
   }

   value_type& at(const id_type id) {
      if( ! check_range(id) ) BOOST_THROW_EXCEPTION(
               Err()
               << Err::msg_t("invalid ID")
               << Err::int1_t(id())
      );
      return vid_[vpos(id)];
   }

   value_type const* find(const id_type id) const {
      if( check_range(id) ) return & this->operator[](id);
      return 0;
   }

   value_type* find(const id_type id) {
      if( check_range(id) ) return & this->operator[](id);
      return 0;
   }

   id_type insert(value_type const& obj) {
      if( erased_.empty() ) {
         const id_type id = pos2id(vid_.size());
         vid_.push_back(obj);
         return id;
      }
      const id_type id = erased_.back();
      erased_.pop_back();
      const std::size_t n = vpos(id);
      BOOST_ASSERT(vid_.size() > n);
      vid_[n] = obj;
      return id;
   }

   value_type& insert(const id_type id) {
      const std::size_t n = vpos(id);
      if( (! erased_.erase(id)) && (n >= vid_.size()) ) {
         vid_.resize(n + 1);
      }
      return vid_[n];
   }

   void erase(const id_type id) {
      BOOST_ASSERT( check_range(id) );
      const std::size_t pos = vpos(id);
      erased_.insert(id);
      vid_[pos] = value_type();
   }

   void clear() {
      erased_.clear();
      vid_.clear();
   }

private:
   vector_t vid_;
   Vector_set<id_type> erased_;
   id_type id0_;

   std::size_t vpos(const id_type id) const {
      BOOST_ASSERT(id >= id0_ && "invalid ID");
      return id() - id0_();
   }

   id_type pos2id(const std::size_t n) const {return id_type(n + id0_());}

   bool check_range(const id_type id) const {
      return id >= id0_ && vpos(id) < vid_.size();
   }
};

}//namespace detail
}//namespace vdj_pipe
#endif /* ID_MAP_HPP_ */