Lumiera  0.pre.03
»edit your freedom«
index.hpp
Go to the documentation of this file.
1 /*
2  INDEX.hpp - data structure for organising advice solutions and matching
3 
4  Copyright (C) Lumiera.org
5  2010, Hermann Vosseler <Ichthyostega@web.de>
6 
7  This program is free software; you can redistribute it and/or
8  modify it under the terms of the GNU General Public License as
9  published by the Free Software Foundation; either version 2 of
10  the License, or (at your option) any later version.
11 
12  This program is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU General Public License for more details.
16 
17  You should have received a copy of the GNU General Public License
18  along with this program; if not, write to the Free Software
19  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 
21 */
22 
23 
86 #ifndef LUMIERA_ADVICE_INDEX_H
87 #define LUMIERA_ADVICE_INDEX_H
88 
89 
90 #include "lib/error.hpp"
91 #include "lib/symbol.hpp"
92 #include "include/logging.h"
93 #include "lib/iter-adapter-stl.hpp"
94 #include "lib/format-obj.hpp"
95 #include "lib/util-foreach.hpp"
96 #include "lib/util.hpp"
98 
99 #include <boost/operators.hpp>
100 #include <unordered_map>
101 #include <string>
102 
103 namespace lumiera{
104 namespace advice {
105 
106  namespace error = lumiera::error;
107 
108  using std::placeholders::_1;
109  using std::unordered_map;
112  using util::toString;
113  using util::for_each;
114  using util::contains;
115  using util::unConst;
116  using lib::Literal;
117  using std::string;
118  using std::vector;
119  using std::pair;
120 
121 
122 
123 
124 
149  template<class POA>
150  class Index
151  {
152 
153 
154  struct Entry
155  : pair<Binding::Matcher, POA*>
156  , boost::equality_comparable<Entry, POA,
157  boost::equality_comparable<Entry>
158  >
159  {
160  explicit
161  Entry (POA& elm)
162  : pair<Binding::Matcher, POA*> (elm.getMatcher(), &elm)
163  { }
164 
165  // using default-copy, thus assuming copy is NO_THROW
166 
167 
168  operator string() const
169  {
170  return "E-" +hash_value(this->first) +"--> "+ this->second ;
171  }
172 
173  friend bool
174  operator== (Entry const& a, Entry const& b)
175  {
176  return a.second == b.second;
177  }
178 
179  friend bool
180  operator== (Entry const& a, POA const& p)
181  {
182  return a.second == &p;
183  }
184  };
185 
186 
187  typedef vector<Entry> EntryList;
188  typedef typename EntryList::iterator EIter;
189 
190 
191  struct Cluster
192  {
193  EntryList elms_;
194 
195  size_t
196  size() const
197  {
198  return elms_.size();
199  }
200 
201  void
202  append (POA& elm)
203  {
204  REQUIRE (!contains (elm), "Duplicate entry");
205  try { elms_.push_back (Entry(elm)); }
206 
207  catch(std::bad_alloc&)
208  {
209  throw error::Fatal("AdviceSystem failure due to exhausted memory");
210  }
211  }
212 
213  void
214  overwrite (POA const& oldRef, POA& newElm)
215  {
216  EIter pos = std::find (elms_.begin(),elms_.end(), oldRef);
217  REQUIRE (pos!=elms_.end(), "Attempt to overwrite an entry which isn't there.");
218  REQUIRE_IF (&oldRef != &newElm, !contains (newElm), "Duplicate entry");
219 
220  *pos = Entry(newElm);
221 
222  REQUIRE_IF (&oldRef != &newElm, !contains (oldRef), "Duplicate entry");
223  }
224 
225  void
226  remove (POA const& refElm)
227  {
228  EIter pos = std::find (elms_.begin(),elms_.end(), refElm);
229  if (pos!=elms_.end())
230  elms_.erase(pos);
231 
232  ENSURE (!contains (refElm), "Duplicate entry");
233  }
234 
235  bool
236  contains (POA const& refElm)
237  {
238  for (EIter i=elms_.begin(); i!=elms_.end(); ++i)
239  if (*i == refElm) return true;
240  return false;
241  }
242 
243  operator string() const
244  {
245  string dump{"elmList("+toString(elms_.size())+")\n"};
246  for (auto const& entry : elms_)
247  dump += "E...:"+entry+"\n";
248  return dump;
249  }
250 
252  allElms ()
253  {
254  return eachElm (elms_);
255  }
256  };
257 
258 
260  : Cluster
261  {
262  POA*
263  find_latest_solution (POA& requestElm)
264  {
265  typedef typename EntryList::reverse_iterator RIter;
266  Binding::Matcher pattern (requestElm.getMatcher());
267  for (RIter ii=this->elms_.rbegin();
268  ii!=this->elms_.rend();
269  ++ii )
270  if (ii->first.matches (pattern))
271  return ii->second;
272 
273  return NULL;
274  }
275 
276  void
277  publish_latest_solution (POA& requestElm)
278  {
279  POA* solution = find_latest_solution (requestElm);
280  if (solution)
281  // found the most recent advice provision satisfying the (new) request
282  // thus publish this new advice solution into the request object
283  requestElm.setSolution (solution);
284  else
285  requestElm.setSolution ( NULL );
286  // report "no solution" which causes a default solution to be used
287  }
288  };
289 
291  : Cluster
292  {
293  void
294  publish_all_solutions (POA& provisionElm)
295  {
296  Binding::Matcher pattern (provisionElm.getMatcher());
297  for (EIter ii=this->elms_.begin();
298  ii!=this->elms_.end();
299  ++ii )
300  if (pattern.matches (ii->first))
301  // the given (new) advice provision satisfies this request
302  // thus publish this new advice solution into the request object
303  ii->second->setSolution (&provisionElm);
304  }
305 
306  void
307  retract_all_solutions (POA const& oldProv, ProvisionCluster& possibleReplacementSolutions)
308  {
309  Binding::Matcher pattern (oldProv.getMatcher());
310  for (EIter ii=this->elms_.begin();
311  ii!=this->elms_.end();
312  ++ii )
313  if (pattern.matches (ii->first))
314  // the old advice provision (to be dropped) satisfied this request
315  // which thus needs to be treated anew (could cause quadratic complexity)
316  possibleReplacementSolutions.publish_latest_solution (*(ii->second));
317  }
318 
319  void
320  rewrite_all_solutions (POA const& oldProv, POA& newProv, ProvisionCluster& possibleReplacementSolutions)
321  {
322  Binding::Matcher oldPattern (oldProv.getMatcher());
323  Binding::Matcher newPattern (newProv.getMatcher ());
324  for (EIter ii=this->elms_.begin();
325  ii!=this->elms_.end();
326  ++ii )
327  if (newPattern.matches (ii->first))
328  ii->second->setSolution (&newProv);
329  else
330  if (oldPattern.matches (ii->first))
331  possibleReplacementSolutions.publish_latest_solution (*(ii->second));
332  }
333  };
334 
335 
336 
337  /* ==== Index Tables ===== */
338 
339  typedef unordered_map<HashVal, RequestCluster> RTable;
340  typedef unordered_map<HashVal, ProvisionCluster> PTable;
341 
342  mutable RTable requestEntries_;
343  mutable PTable provisionEntries_;
344 
345 
346 
347  public:
348 
349  void
350  addRequest (POA& entry)
351  {
352  HashVal key (hash_value(entry));
353  requestEntries_[key].append (entry); // might throw
354  provisionEntries_[key].publish_latest_solution (entry);
355  }
356 
363  void
364  modifyRequest (HashVal oKey, POA& entry)
365  {
366  HashVal nKey (hash_value(entry));
367  if (oKey != nKey)
368  {
369  requestEntries_[nKey].append (entry); // might throw
370  requestEntries_[oKey].remove (entry);
371  }
372  else
373  { // rewrite Entry to include the new binding
374  requestEntries_[nKey].overwrite (entry, entry);
375  }
376  provisionEntries_[nKey].publish_latest_solution (entry);
377  }
378 
379  void
380  removeRequest (POA const& refEntry)
381  {
382  HashVal oKey (hash_value(refEntry));
383  requestEntries_[oKey].remove (refEntry);
384  }
385 
386 
387  void
388  addProvision (POA& entry)
389  {
390  HashVal key (hash_value(entry));
391  provisionEntries_[key].append (entry); // might throw
392  requestEntries_[key].publish_all_solutions (entry);
393  }
394 
395  void
396  modifyProvision (POA const& oldRef, POA& newEntry)
397  {
398  HashVal oKey (hash_value(oldRef));
399  HashVal nKey (hash_value(newEntry));
400  if (oKey != nKey)
401  {
402  provisionEntries_[nKey].append (newEntry); // might throw, in which case it has no effect
403  provisionEntries_[oKey].remove (oldRef);
404  requestEntries_[nKey].publish_all_solutions (newEntry);
405  requestEntries_[oKey].retract_all_solutions (oldRef, provisionEntries_[oKey]);
406  }
407  else
408  {
409  provisionEntries_[nKey].overwrite (oldRef, newEntry);
410  requestEntries_[nKey].rewrite_all_solutions (oldRef,newEntry, provisionEntries_[nKey]);
411  }
412  }
413 
414  void
415  removeProvision (POA const& refEntry)
416  {
417  HashVal key (hash_value(refEntry));
418  provisionEntries_[key].remove (refEntry); // NO_THROW
419  requestEntries_[key].retract_all_solutions (refEntry, provisionEntries_[key]);
420  }
421 
422 
427  void
428  clear ()
429  {
430  WARN (library, "Purging Advice Binding Index...");
431  requestEntries_.clear();
432  provisionEntries_.clear();
433  }
434 
435 
436 
437  /* == diagnostics == */
438 
440  bool isValid() const;
441 
442  size_t
443  size() const
444  {
445  return request_count() + provision_count();
446  }
447 
448  size_t
449  request_count() const
450  {
451  return sumClusters (eachVal (requestEntries_));
452  }
453 
454  size_t
455  provision_count() const
456  {
457  return sumClusters (eachVal (provisionEntries_));
458  }
459 
460  bool
461  hasRequest (POA const& refEntry) const
462  {
463  return requestEntries_[hash_value(refEntry)].contains (refEntry);
464  }
465 
466  bool
467  hasProvision (POA const& refEntry) const
468  {
469  return provisionEntries_[hash_value(refEntry)].contains (refEntry);
470  } // note: even just lookup might create a new (empty) cluster;
471  // thus the tables are defined as mutable
472 
473 
474  private:
477  template<class IT>
478  static size_t
479  sumClusters (IT ii)
480  {
481  size_t sum=0;
482  for ( ; ii; ++ii )
483  sum += ii->size();
484  return sum;
485  }
486 
487  void verify_Entry (Entry const&, HashVal) const;
488  void verify_Request (Entry const&, HashVal) const;
489  };
490 
491 
492 
493 
494 
495 
496 
497 
498 
499 
500 
501  /* == Self-Verification == */
502 
503  namespace { // self-check implementation helpers...
504 
505  LUMIERA_ERROR_DEFINE(INDEX_CORRUPTED, "Advice-Index corrupted");
506 
508  : error::Fatal
509  {
510  SelfCheckFailure (Literal failure)
511  : error::Fatal {string("Failed test: ")+failure
512  ,LUMIERA_ERROR_INDEX_CORRUPTED}
513  { }
514  };
515  }
516 
517 
518 
519 
526  template<class POA>
527  bool
529  {
530  typedef typename RTable::const_iterator RTIter;
531  typedef typename PTable::const_iterator PTIter;
532 
533  try {
534  for (PTIter ii =provisionEntries_.begin();
535  ii != provisionEntries_.end(); ++ii)
536  {
537  HashVal hash (ii->first);
538  Cluster& clu = unConst(ii->second);
539  for_each (clu.allElms(), &Index::verify_Entry, this, _1, hash);
540  }
541  for (RTIter ii=requestEntries_.begin();
542  ii != requestEntries_.end(); ++ii)
543  {
544  HashVal hash (ii->first);
545  Cluster& clu = unConst(ii->second);
546  for_each (clu.allElms(), &Index::verify_Request, this, _1, hash);
547  }
548  return true;
549  }
550 
551  catch(SelfCheckFailure& failure)
552  {
553  lumiera_error();
554  ERROR (library, "%s", failure.what());
555  }
556  return false;
557  }
558 
559 
560 
561 #define VERIFY(_CHECK_, DESCRIPTION) \
562  if (!(_CHECK_)) \
563  throw SelfCheckFailure ((DESCRIPTION));
564 
565 
566  template<class POA>
567  void
568  Index<POA>::verify_Entry (Entry const& e, HashVal hash) const
569  {
570  VERIFY (hash == hash_value(e.first), "Wrong bucket, hash doesn't match bucket");
571  VERIFY (e.second, "Invalid Entry: back-link is NULL");
572  }
573 
574  template<class POA>
575  void
576  Index<POA>::verify_Request (Entry const& e, HashVal hash) const
577  {
578  verify_Entry (e,hash);
579  POA& request = *(e.second);
580  const POA* solution (request.getSolution());
581  if (solution && hasProvision(*solution))
582  {
583  POA* currentSolution = provisionEntries_[hash].find_latest_solution (request);
584  VERIFY (e.first.matches (solution->getMatcher()),"stored advice solution not supported by binding match");
585  VERIFY (bool(currentSolution), "unable to reproduce stored solution with the current provisions")
586  VERIFY (solution == currentSolution, "stored advice solution isn't the topmost solution for this request")
587  }
588  }
589 
590 #undef VERIFY
591 
592 
593 }} // namespace lumiera::advice
594 #endif
Functor object for matching against another Binding.
AnyPair entry(Query< TY > const &query, typename WrapReturn< TY >::Wrapper &obj)
helper to simplify creating mock table entries, wrapped correctly
inline string literal This is a marker type to indicate that
Definition: symbol.hpp:85
This header is for including and configuring NoBug.
static size_t sumClusters(IT ii)
internal: sum element count over all clusters in the given hashtable
Definition: index.hpp:479
Derived specific exceptions within Lumiera&#39;s exception hierarchy.
Definition: error.hpp:199
A pattern to define and identify a specific attachment to the Advice system.
Marker types to indicate a literal string and a Symbol.
Tiny helper functions and shortcuts to be used everywhere Consider this header to be effectively incl...
bool isValid() const
validity self-check
Definition: index.hpp:528
lumiera_err lumiera_error(void)
Get and clear current error state.
Definition: error-state.c:124
std::string toString(TY const &val) noexcept
get some string representation of any object, reliably.
Definition: format-obj.hpp:200
void for_each(CON const &elements, FUN function, P1 &&bind1, ARGS &&...args)
Accept binding for arbitrary function arguments.
_SeqT< CON >::Range eachElm(CON &coll)
Lumiera error handling (C++ interface).
Simple functions to represent objects, for debugging and diagnostics.
size_t HashVal
a STL compatible hash value
Definition: hash-value.h:56
Lumiera public interface.
Definition: advice.cpp:113
void modifyRequest(HashVal oKey, POA &entry)
Definition: index.hpp:364
Accessing a STL element range through a Lumiera forward iterator, An instance of this iterator adapte...
Preconfigured adapters for some STL container standard usage situations.
Index datastructure for organising advice solutions.
Definition: index.hpp:150
Perform operations "for each element" of a collection.
bool contains(SEQ const &cont, typename SEQ::const_reference val)
shortcut for brute-force containment test in any sequential container
Definition: util.hpp:255
_MapIterT< IT >::ValIter eachVal(IT const &begin, IT const &end)
#define LUMIERA_ERROR_DEFINE(err, msg)
Definition and initialisation of an error constant.
Definition: error.h:80