vdj_pipe
pipeline for processing DNA sequence data
id_bimap.hpp
Go to the documentation of this file.
1 
7 #ifndef ID_BIMAP_HPP_
8 #define ID_BIMAP_HPP_
9 #include <vector>
10 #include "boost/assert.hpp"
11 #include "boost/foreach.hpp"
12 #include "boost/functional/hash_fwd.hpp"
13 #include "boost/unordered_set.hpp"
15 #include "vdj_pipe/exception.hpp"
16 
17 namespace vdj_pipe{ namespace detail{
18 
21 template<class Id, class Obj> class Id_bimap{
22 public:
24  typedef Obj obj_type;
25  typedef Id id_type;
26 
27 private:
28  class Hash_id : std::unary_function<id_type, std::size_t> {
29  public:
30  explicit Hash_id(self_type const& v) : m_(v) {}
31 
32  std::size_t operator()(const id_type id) const {
33  using boost::hash_value;
34  return hash_value(m_[id]);
35  }
36 
37  std::size_t operator()(obj_type const& obj) const {
38  using boost::hash_value;
39  return hash_value(obj);
40  }
41 
42  private:
43  self_type const& m_;
44  };
45 
46  class Equal_id : public std::binary_function<id_type, id_type, bool>{
47  public:
48  explicit Equal_id(self_type const& m) : m_(m) {}
49 
50  bool operator()(id_type id1, id_type id2) const{
51  return m_[id1] == m_[id2];
52  }
53 
54  template<class ObjCompat>
55  bool operator()(id_type id1, ObjCompat const& obj) const{
56  return m_[id1] == obj;
57  }
58 
59  template<class ObjCompat>
60  bool operator()(ObjCompat const& obj, id_type id2) const{
61  return obj == m_[id2];
62  }
63 
64  private:
65  self_type const& m_;
66  };
67 
68  template<class ObjCompat> class Equal_obj {
69  public:
70  explicit Equal_obj(self_type const& m) : m_(m) {}
71 
72  bool operator()(id_type id1, ObjCompat const& obj) const{
73  return m_[id1] == obj;
74  }
75 
76  bool operator()(ObjCompat const& obj, id_type id2) const{
77  return obj == m_[id2];
78  }
79 
80  private:
81  self_type const& m_;
82  };
83 
84  typedef boost::unordered_set<id_type, Hash_id, Equal_id> map_t;
85  typedef std::vector<obj_type> vector_t;
86 
87 public:
88  typedef typename map_t::value_type value_type;
89  typedef typename map_t::iterator iterator;
90  typedef typename map_t::const_iterator const_iterator;
92 
93  explicit Id_bimap(const id_type id0)
94  : vid_(),
95  map_(boost::unordered::detail::default_bucket_count, Hash_id(*this), Equal_id(*this)),
96  erased_(),
97  id0_(id0)
98  {}
99 
100  explicit Id_bimap(self_type const& bm)
101  : vid_(bm.vid_.size()),
102  map_(boost::unordered::detail::default_bucket_count, Hash_id(*this), Equal_id(*this)),
103  erased_(bm.erased_.size()),
104  id0_(bm.id0_)
105  {
106  copy(bm);
107  }
108 
109  self_type& operator=(self_type const& bm) {
110  clear();
111  copy(bm);
112  return *this;
113  }
114 
115  std::size_t size() const { return map_.size(); }
116  const_iterator begin() const {return map_.begin();}
117  const_iterator end() const {return map_.end();}
118  bool empty() const {return map_.empty();}
119  id_type min_id() const {return id0_;}
120  id_type max_id() const {return pos2id(vid_.size()-1);}
121 
122  obj_type const& operator[](const id_type id) const {
123  BOOST_ASSERT( vpos(id) < vid_.size() );
124  return vid_[vpos(id)];
125  }
126 
127  obj_type& operator[](const id_type id) {
128  BOOST_ASSERT( vpos(id) < vid_.size() );
129  return vid_[vpos(id)];
130  }
131 
132  obj_type const& at(const id_type id) const {
133  if( id < id0_ || vpos(id) >= vid_.size() ) BOOST_THROW_EXCEPTION(
134  Err()
135  << Err::msg_t("invalid ID")
136  << Err::int1_t(id())
137  );
138  return vid_[vpos(id)];
139  }
140 
141  obj_type& at(const id_type id) {
142  if( id < id0_ || vpos(id) >= vid_.size() ) BOOST_THROW_EXCEPTION(
143  Err()
144  << Err::msg_t("invalid ID")
145  << Err::int1_t(id())
146  );
147  return vid_[vpos(id)];
148  }
149 
150  template<class ObjCompat>
151  id_type const* find(ObjCompat const& obj) const {
152  const const_iterator i = map_.find(
153  obj,
154  boost::hash<ObjCompat>(),
155  Equal_obj<ObjCompat>(*this)
156  );
157  return i == map_.end() ? 0 : &(*i);
158  }
159 
160  std::pair<id_type, bool> insert(obj_type const& obj) {
161  if( id_type const* idp = find(obj) ) return std::make_pair(*idp, false);
162  if( erased_.empty() ) {
163  const id_type id = pos2id(vid_.size());
164  vid_.push_back(obj);
165  map_.insert(id);
166  return std::make_pair(id, true);
167  }
168 
169  const id_type id = erased_.back();
170  erased_.pop_back();
171  const std::size_t n = vpos(id);
172  BOOST_ASSERT(vid_.size() > n);
173  vid_[n] = obj;
174  map_.insert(id);
175  return std::make_pair(id, true);
176  }
177 
178  void erase(const id_type id) {
179  BOOST_ASSERT( vpos(id) < vid_.size() );
180  const std::size_t pos = vpos(id);
181  map_.erase(id);
182  erased_.push_back(id);
183  vid_[pos] = obj_type();
184  }
185 
186  void clear() {
187  erased_.clear();
188  map_.clear();
189  vid_.clear();
190  }
191 
192 private:
193  vector_t vid_;
194  map_t map_;
195  std::vector<id_type> erased_;
196  id_type id0_;
197 
198  std::size_t vpos(const id_type id) const {
199  BOOST_ASSERT(id >= id0_ && "invalid ID");
200  return id() - id0_();
201  }
202 
203  id_type pos2id(const std::size_t n) const {return id_type(n + id0_());}
204 
205  void copy(self_type const& bm) {
206  vid_.resize(bm.vid_.size());
207  id0_ = bm.id0_;
208  erased_ = bm.erased_;
209  BOOST_FOREACH(const id_type id, bm) {
210  (*this)[id] = bm[id];
211  map_.insert(id);
212  }
213  }
214 
215 };
216 
217 }//namespace detail
218 }//namespace vdj_pipe
219 #endif /* ID_BIMAP_HPP_ */
bool operator()(id_type id1, ObjCompat const &obj) const
Definition: id_bimap.hpp:55
std::pair< id_type, bool > insert(obj_type const &obj)
Definition: id_bimap.hpp:160
std::size_t operator()(const id_type id) const
Definition: id_bimap.hpp:32
Definition: sanitize_string.cpp:15
id_type min_id() const
Definition: id_bimap.hpp:119
Equal_id(self_type const &m)
Definition: id_bimap.hpp:48
Definition: id_bimap.hpp:28
std::vector< obj_type > vector_t
Definition: id_bimap.hpp:85
obj_type & at(const id_type id)
Definition: id_bimap.hpp:141
Definition: id_bimap.hpp:46
boost::unordered_set< id_type, Hash_id, Equal_id > map_t
Definition: id_bimap.hpp:84
bool operator()(ObjCompat const &obj, id_type id2) const
Definition: id_bimap.hpp:60
bool empty() const
Definition: id_bimap.hpp:118
void erase(const id_type id)
Definition: id_bimap.hpp:178
map_t map_
Definition: id_bimap.hpp:194
bool operator()(id_type id1, id_type id2) const
Definition: id_bimap.hpp:50
obj_type const & operator[](const id_type id) const
Definition: id_bimap.hpp:122
id_type pos2id(const std::size_t n) const
Definition: id_bimap.hpp:203
Hash_id(self_type const &v)
Definition: id_bimap.hpp:30
Definition: id_bimap.hpp:21
bool operator()(id_type id1, ObjCompat const &obj) const
Definition: id_bimap.hpp:72
map_t::value_type value_type
Definition: id_bimap.hpp:88
Id_bimap(self_type const &bm)
Definition: id_bimap.hpp:100
boost::error_info< struct errinfo_int1_, int > int1_t
Definition: exception.hpp:28
const_iterator end() const
Definition: id_bimap.hpp:117
std::size_t hash_value(Base_id< S, V > const &id)
Definition: object_id_base.hpp:55
base_exception Err
Definition: id_bimap.hpp:91
std::size_t vpos(const id_type id) const
Definition: id_bimap.hpp:198
id_type max_id() const
Definition: id_bimap.hpp:120
vector_t vid_
Definition: id_bimap.hpp:193
Obj obj_type
Definition: id_bimap.hpp:24
self_type const & m_
Definition: id_bimap.hpp:81
id_type const * find(ObjCompat const &obj) const
Definition: id_bimap.hpp:151
Main namespace of vdj_pipe library.
Definition: keywords_variable.hpp:11
self_type const & m_
Definition: id_bimap.hpp:43
std::size_t hash_value(basic_string_ref< charT, traits > const &str)
Definition: string_ref.hpp:15
bool operator()(ObjCompat const &obj, id_type id2) const
Definition: id_bimap.hpp:76
const std::string id1
Definition: file_ostream_variant_run.cpp:21
id_type id0_
Definition: id_bimap.hpp:196
const std::size_t n
Definition: vector_set_test.cpp:26
Id id_type
Definition: id_bimap.hpp:25
self_type const & m_
Definition: id_bimap.hpp:65
obj_type & operator[](const id_type id)
Definition: id_bimap.hpp:127
std::vector< id_type > erased_
Definition: id_bimap.hpp:195
Definition: exception.hpp:23
void clear()
Definition: id_bimap.hpp:186
boost::error_info< struct errinfo_message_, std::string > msg_t
Definition: exception.hpp:24
Equal_obj(self_type const &m)
Definition: id_bimap.hpp:70
map_t::iterator iterator
Definition: id_bimap.hpp:89
self_type & operator=(self_type const &bm)
Definition: id_bimap.hpp:109
Id_bimap self_type
Definition: id_bimap.hpp:23
std::size_t size() const
Definition: id_bimap.hpp:115
const_iterator begin() const
Definition: id_bimap.hpp:116
const std::string id2
Definition: file_ostream_variant_run.cpp:25
Id_bimap(const id_type id0)
Definition: id_bimap.hpp:93
std::size_t operator()(obj_type const &obj) const
Definition: id_bimap.hpp:37
obj_type const & at(const id_type id) const
Definition: id_bimap.hpp:132
map_t::const_iterator const_iterator
Definition: id_bimap.hpp:90
void copy(self_type const &bm)
Definition: id_bimap.hpp:205
Definition: id_bimap.hpp:68