Predator  [unstable] git snapshot
id_mapper.hh
Go to the documentation of this file.
1 /*
2  * Copyright (C) 2013 Kamil Dudka <kdudka@redhat.com>
3  *
4  * This file is part of predator.
5  *
6  * predator is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 3 of the License, or
9  * any later version.
10  *
11  * predator is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with predator. If not, see <http://www.gnu.org/licenses/>.
18  */
19 
20 #ifndef H_GUARD_ID_MAPPER_H
21 #define H_GUARD_ID_MAPPER_H
22 
23 #include "config.h"
24 
25 #include <iostream>
26 #include <limits>
27 #include <set>
28 #include <vector>
29 
30 #include <boost/foreach.hpp>
31 #include <boost/static_assert.hpp>
32 
33 enum EDirection {
36 };
37 
38 template <typename TId,
39  TId MIN = std::numeric_limits<TId>::min(),
40  TId MAX = std::numeric_limits<TId>::max()>
41 class IdMapper {
42  public:
43  typedef std::vector<TId> TVector;
44 
45  /// do not change the order, composite() relies on it
50  };
51 
52  public:
55  {
56  }
57 
59  nfa_(nfa)
60  {
61  }
62 
64  {
65  nfa_ = nfa;
66  }
67 
68  void clear()
69  {
71  biSearch_[0].clear();
72  biSearch_[1].clear();
73  }
74 
75  void flip()
76  {
77  biSearch_[0].swap(biSearch_[1]);
78  }
79 
80  bool empty() const
81  {
83  return biSearch_[D_LEFT_TO_RIGHT].empty();
84  }
85 
86  unsigned size() const
87  {
88  CL_BREAK_IF(biSearch_[0].size() != biSearch_[1].size());
89  return biSearch_[D_LEFT_TO_RIGHT].size();
90  }
91 
92  bool isTrivial() const
93  {
94  return this->empty()
96  }
97 
98  bool /* changed */ insert(TId left, TId right);
99 
100  template <EDirection>
101  void query(TVector *pDst, TId id) const;
102 
103  template <EDirection>
104  void composite(const IdMapper &by);
105 
106  void prettyPrint(std::ostream &) const;
107 
108  private:
109  typedef std::pair<TId, TId> TPair;
110  typedef std::set<TPair> TSearch;
111  typedef TSearch TBidirSearch[2];
112  typedef typename TSearch::const_iterator TIter;
113 
116 
117  public:
118  /// STL iterator, always D_LEFT_TO_RIGHT
119  typedef typename TSearch::const_iterator const_iterator;
120 
121  /// needed for BOOST_FOREACH
122  typedef typename TSearch::const_reference const_reference;
123 
124  /// needed for BOOST_FOREACH
125  const_iterator begin() const { return biSearch_[0].begin(); }
126 
127  /// needed for BOOST_FOREACH
128  const_iterator end() const { return biSearch_[0].end(); }
129 };
130 
131 template <EDirection DIR, typename TBiMap, class TDst, class TSrc>
132 void project(
133  const TBiMap &biMap,
134  TDst *pDstCont,
135  const TSrc &srcCont)
136 {
137  BOOST_FOREACH(typename TSrc::value_type src, srcCont) {
138  typename TBiMap::TVector dstVect;
139  biMap.template query<DIR>(&dstVect, src);
140  BOOST_FOREACH(const typename TDst::value_type dst, dstVect)
141  pDstCont->insert(dst);
142  }
143 }
144 
145 template <typename TId, TId MIN, TId MAX>
146 bool IdMapper<TId, MIN, MAX>::insert(const TId left, const TId right)
147 {
148  const TPair itemL(left, right);
149  const TPair itemR(right, left);
150  CL_BREAK_IF(hasKey(biSearch_[0], itemL) != hasKey(biSearch_[1], itemR));
151 
152  const bool changed = biSearch_[D_LEFT_TO_RIGHT].insert(itemL).second;
153  if (!changed)
154  return false;
155 
156  biSearch_[D_RIGHT_TO_LEFT].insert(itemR);
157  return true;
158 }
159 
160 template <typename TId, TId MIN, TId MAX>
161 template <EDirection DIR>
162 void IdMapper<TId, MIN, MAX>::query(TVector *pDst, const TId id) const
163 {
164  BOOST_STATIC_ASSERT(MIN < MAX);
165 
166  const TSearch &search = biSearch_[DIR];
167 
168  const TPair begItem(id, MIN);
169  const TIter beg = search.lower_bound(begItem);
170  if (beg == search.end() || beg->first != id) {
171  // not found
172  switch (nfa_) {
173  case NFA_TRAP_TO_DEBUGGER:
174  CL_BREAK_IF("IdMapper failed to resolve the requested ID");
175  // fall through!
176 
177  case NFA_RETURN_NOTHING:
178  return;
179 
180  case NFA_RETURN_IDENTITY:
181  pDst->push_back(id);
182  return;
183  }
184  }
185 
186  // find last (end points one item _beyond_ the last one)
187  const TPair endItem(id, MAX);
188  const TIter end = search.upper_bound(endItem);
189  CL_BREAK_IF(beg == end);
190 
191  // copy the image to the given vector
192  for (TIter it = beg; it != end; ++it) {
193  CL_BREAK_IF(id != it->first);
194  pDst->push_back(it->second);
195  }
196 }
197 
198 template <typename TId, TId MIN, TId MAX>
199 template <EDirection DIR>
201 {
203 
204  // iterate through the mapping of 'this'
205  const TSearch &m = biSearch_[DIR];
206  BOOST_FOREACH(typename TSearch::const_reference item, m) {
207  const TId a = item.first;
208  const TId b = item.second;
209  TVector cList;
210  by.query<DIR>(&cList, b);
211  BOOST_FOREACH(const TId c, cList)
212  result.insert(a, c);
213  }
214 
215  if (NFA_RETURN_IDENTITY == nfa_) {
216  // iterate through the mapping of 'by'
217  const TSearch &mBy = by.biSearch_[DIR];
218  BOOST_FOREACH(typename TSearch::const_reference item, mBy) {
219  const TId b = item.first;
220  const TId c = item.second;
221 
222  // reverse lookup
223  TVector aList;
224  if (D_LEFT_TO_RIGHT == DIR)
225  this->query<D_RIGHT_TO_LEFT>(&aList, b);
226  else
227  this->query<D_LEFT_TO_RIGHT>(&aList, b);
228 
229  BOOST_FOREACH(const TId a, aList)
230  result.insert(a, c);
231  }
232  }
233 
234  if (by.nfa_ < nfa_)
235  nfa_ = by.nfa_;
236 
237  // finally replace the mapping of 'this' by the result
238  biSearch_[0].swap(result.biSearch_[D_RIGHT_TO_LEFT == DIR]);
239  biSearch_[1].swap(result.biSearch_[D_LEFT_TO_RIGHT == DIR]);
240 }
241 
242 template <typename TId, TId MIN, TId MAX>
243 void IdMapper<TId, MIN, MAX>::prettyPrint(std::ostream &str) const
244 {
245  unsigned i = 0U;
246  const TSearch &m = biSearch_[D_LEFT_TO_RIGHT];
247  BOOST_FOREACH(typename TSearch::const_reference item, m) {
248  if (i++)
249  str << ", ";
250 
251  str << item.first << " -> " << item.second;
252  }
253 }
254 
255 #endif /* H_GUARD_ID_MAPPER_H */