index.hpp

Go to the documentation of this file.

/*
  INDEX.hpp  -  data structure for organising advice solutions and matching

  Copyright (C)         Lumiera.org
    2010,               Hermann Vosseler <Ichthyostega@web.de>

  This program 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; either version 2 of
  the License, or (at your option) any later version.

  This program 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 this program; if not, write to the Free Software
  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.

*/


#ifndef LUMIERA_ADVICE_INDEX_H
#define LUMIERA_ADVICE_INDEX_H


#include "lib/error.hpp"
#include "lib/symbol.hpp"
#include "include/logging.h"
#include "lib/iter-adapter-stl.hpp"
#include "lib/format-obj.hpp"
#include "lib/util-foreach.hpp"
#include "lib/util.hpp"
#include "common/advice/binding.hpp"

#include <boost/operators.hpp>
#include <unordered_map>
#include <string>

namespace lumiera{
namespace advice {
  
  namespace error = lumiera::error;
  
  using std::placeholders::_1;
  using std::unordered_map;
  using lib::iter_stl::eachVal;
  using lib::iter_stl::eachElm;
  using util::toString;
  using util::for_each;
  using util::contains;
  using util::unConst;
  using lib::Literal;
  using std::string;
  using std::vector;
  using std::pair;
  
  
  
  
  
  template<class POA>
  class Index
    {
      
      
      struct Entry
        : pair<Binding::Matcher, POA*>
        , boost::equality_comparable<Entry, POA,
          boost::equality_comparable<Entry>
        >
        {
          explicit
          Entry (POA& elm)
            : pair<Binding::Matcher, POA*> (elm.getMatcher(), &elm)
            { }
          
          // using default-copy, thus assuming copy is NO_THROW
          
          
          operator string()  const  
            {
              return "E-" +hash_value(this->first) +"--> "+ this->second ;
            }
          
          friend bool
          operator== (Entry const& a, Entry const& b)
          {
            return a.second == b.second;
          }
          
          friend bool
          operator== (Entry const& a, POA const& p)
          {
            return a.second == &p;
          }
        };
      
      
      typedef vector<Entry> EntryList;
      typedef typename EntryList::iterator EIter;
      
      
      struct Cluster
        {
           EntryList elms_;
           
           size_t
           size()  const
             {
               return elms_.size();
             }
           
           void
           append (POA& elm)
             {
               REQUIRE (!contains (elm), "Duplicate entry");
               try { elms_.push_back (Entry(elm)); }
               
               catch(std::bad_alloc&)
                 {
                   throw error::Fatal("AdviceSystem failure due to exhausted memory");
                 }
             }
           
           void
           overwrite (POA const& oldRef, POA& newElm)
             {
               EIter pos = std::find (elms_.begin(),elms_.end(), oldRef);
               REQUIRE    (pos!=elms_.end(), "Attempt to overwrite an entry which isn't there.");
               REQUIRE_IF (&oldRef != &newElm, !contains (newElm), "Duplicate entry");
               
               *pos = Entry(newElm);
               
               REQUIRE_IF (&oldRef != &newElm, !contains (oldRef), "Duplicate entry");
             }
           
           void
           remove (POA const& refElm)
             {
               EIter pos = std::find (elms_.begin(),elms_.end(), refElm);
               if (pos!=elms_.end())
                 elms_.erase(pos);
               
               ENSURE (!contains (refElm), "Duplicate entry");
             }
           
           bool
           contains (POA const& refElm)
             {
               for (EIter i=elms_.begin(); i!=elms_.end(); ++i)
                 if (*i == refElm) return true;
               return false;
             }
           
           operator string()  const  
             {
               string dump{"elmList("+toString(elms_.size())+")\n"};
               for (auto const& entry : elms_)
                 dump += "E...:"+entry+"\n";
               return dump;
             }
           
           lib::RangeIter<EIter>
           allElms ()
             {
               return eachElm (elms_);
             }
        };
      
      
      struct ProvisionCluster
        : Cluster
        {
          POA*
          find_latest_solution (POA& requestElm)
            {
              typedef typename EntryList::reverse_iterator RIter;
              Binding::Matcher pattern (requestElm.getMatcher());
              for (RIter ii=this->elms_.rbegin();
                   ii!=this->elms_.rend();
                   ++ii )
                if (ii->first.matches (pattern))
                  return ii->second;
              
              return NULL;
            }
          
          void
          publish_latest_solution (POA& requestElm)
            {
              POA* solution = find_latest_solution (requestElm);
              if (solution)
                 // found the most recent advice provision satisfying the (new) request
                //  thus publish this new advice solution into the request object
                requestElm.setSolution (solution);
              else
                requestElm.setSolution ( NULL );
                //  report "no solution" which causes a default solution to be used
            }
        };
      
      struct RequestCluster
        : Cluster
        {
          void
          publish_all_solutions (POA& provisionElm)
            {
              Binding::Matcher pattern (provisionElm.getMatcher());
              for (EIter ii=this->elms_.begin();
                   ii!=this->elms_.end();
                   ++ii )
                if (pattern.matches (ii->first))
                   // the given (new) advice provision satisfies this request
                  //  thus publish this new advice solution into the request object
                  ii->second->setSolution (&provisionElm);
            }
          
          void
          retract_all_solutions (POA const& oldProv, ProvisionCluster& possibleReplacementSolutions)
            {
              Binding::Matcher pattern (oldProv.getMatcher());
              for (EIter ii=this->elms_.begin();
                   ii!=this->elms_.end();
                   ++ii )
                if (pattern.matches (ii->first))
                   // the old advice provision (to be dropped) satisfied this request
                  //  which thus needs to be treated anew (could cause quadratic complexity)
                  possibleReplacementSolutions.publish_latest_solution (*(ii->second));
            }
          
          void
          rewrite_all_solutions (POA const& oldProv, POA& newProv, ProvisionCluster& possibleReplacementSolutions)
            {
              Binding::Matcher oldPattern (oldProv.getMatcher());
              Binding::Matcher newPattern (newProv.getMatcher ());
              for (EIter ii=this->elms_.begin();
                   ii!=this->elms_.end();
                   ++ii )
                if (newPattern.matches (ii->first))
                  ii->second->setSolution (&newProv);
                else
                if (oldPattern.matches (ii->first))
                  possibleReplacementSolutions.publish_latest_solution (*(ii->second));
            }
        };
      
      
      
      /* ==== Index Tables ===== */  
      
      typedef unordered_map<HashVal, RequestCluster> RTable;
      typedef unordered_map<HashVal, ProvisionCluster> PTable;
      
      mutable RTable requestEntries_;
      mutable PTable provisionEntries_;
      
      
      
    public:
      
      void
      addRequest (POA& entry)
        {
          HashVal key (hash_value(entry));
          requestEntries_[key].append (entry);  // might throw
          provisionEntries_[key].publish_latest_solution (entry);
        }
      
      void
      modifyRequest (HashVal oKey, POA& entry)
        {
          HashVal nKey (hash_value(entry));
          if (oKey != nKey)
            {
              requestEntries_[nKey].append (entry);   // might throw
              requestEntries_[oKey].remove (entry);
            }
          else
            { // rewrite Entry to include the new binding
              requestEntries_[nKey].overwrite (entry, entry);
            }
          provisionEntries_[nKey].publish_latest_solution (entry);
        }
      
      void
      removeRequest (POA const& refEntry)
        {
          HashVal oKey (hash_value(refEntry));
          requestEntries_[oKey].remove (refEntry);
        }
      
      
      void
      addProvision (POA& entry)
        {
          HashVal key (hash_value(entry));
          provisionEntries_[key].append (entry);  // might throw
          requestEntries_[key].publish_all_solutions (entry);
        }
      
      void
      modifyProvision (POA const& oldRef, POA& newEntry)
        {
          HashVal oKey (hash_value(oldRef));
          HashVal nKey (hash_value(newEntry));
          if (oKey != nKey)
            {
              provisionEntries_[nKey].append (newEntry);  // might throw, in which case it has no effect
              provisionEntries_[oKey].remove (oldRef);
              requestEntries_[nKey].publish_all_solutions (newEntry);
              requestEntries_[oKey].retract_all_solutions (oldRef, provisionEntries_[oKey]);
            }
          else
            {
              provisionEntries_[nKey].overwrite (oldRef, newEntry);
              requestEntries_[nKey].rewrite_all_solutions (oldRef,newEntry, provisionEntries_[nKey]);
            }
        }
      
      void
      removeProvision (POA const& refEntry)
        {
          HashVal key (hash_value(refEntry));
          provisionEntries_[key].remove (refEntry);  // NO_THROW
          requestEntries_[key].retract_all_solutions (refEntry, provisionEntries_[key]);
        }
      
      
      void
      clear ()
        {
          WARN (library, "Purging Advice Binding Index...");
          requestEntries_.clear();
          provisionEntries_.clear();
        }
      
      
      
      /* == diagnostics == */
      
      bool isValid()  const;
      
      size_t
      size()  const
        {
          return request_count() + provision_count();
        }
      
      size_t
      request_count()  const
        {
          return sumClusters (eachVal (requestEntries_));
        }
      
      size_t
      provision_count()  const
        {
          return sumClusters (eachVal (provisionEntries_));
        }
      
      bool
      hasRequest (POA const& refEntry)  const
        {
          return requestEntries_[hash_value(refEntry)].contains (refEntry);
        }
      
      bool
      hasProvision (POA const& refEntry)  const
        {
          return provisionEntries_[hash_value(refEntry)].contains (refEntry);
        }                       // note: even just lookup might create a new (empty) cluster;
                               //        thus the tables are defined as mutable 
      
      
    private:
      template<class IT>
      static size_t
      sumClusters (IT ii)
        {
          size_t sum=0;
          for ( ; ii; ++ii )
              sum += ii->size();
          return sum;
        }
      
      void verify_Entry   (Entry const&, HashVal)  const;
      void verify_Request (Entry const&, HashVal)  const;
    };
  
  
  
  
  
  
  
  
  
  
  
  /* == Self-Verification == */
  
  namespace { // self-check implementation helpers...
    
    LUMIERA_ERROR_DEFINE(INDEX_CORRUPTED, "Advice-Index corrupted");
    
    struct SelfCheckFailure
      : error::Fatal
      {
        SelfCheckFailure (Literal failure)
          : error::Fatal {string("Failed test: ")+failure
                         ,LUMIERA_ERROR_INDEX_CORRUPTED}
          { }
      };
  }
  
  
  
  
  template<class POA>
  bool
  Index<POA>::isValid()  const
  {
    typedef typename RTable::const_iterator RTIter;
    typedef typename PTable::const_iterator PTIter;
    
    try {
        for (PTIter ii =provisionEntries_.begin();
             ii != provisionEntries_.end(); ++ii)
          {
            HashVal hash (ii->first);
            Cluster& clu = unConst(ii->second);
            for_each (clu.allElms(), &Index::verify_Entry, this, _1, hash);
          }
        for (RTIter ii=requestEntries_.begin();
             ii != requestEntries_.end(); ++ii)
          {
            HashVal hash (ii->first);
            Cluster& clu = unConst(ii->second);
            for_each (clu.allElms(), &Index::verify_Request, this, _1, hash);
          }
        return true;
      }
    
    catch(SelfCheckFailure& failure)
      {
        lumiera_error();
        ERROR (library, "%s", failure.what());
      }
    return false;
  }
  
  
  
#define VERIFY(_CHECK_, DESCRIPTION) \
      if (!(_CHECK_))                 \
        throw SelfCheckFailure ((DESCRIPTION));
  
  
  template<class POA>
  void
  Index<POA>::verify_Entry (Entry const& e, HashVal hash)  const
  {
    VERIFY (hash == hash_value(e.first), "Wrong bucket, hash doesn't match bucket");
    VERIFY (e.second,                    "Invalid Entry: back-link is NULL");
  }
  
  template<class POA>
  void
  Index<POA>::verify_Request (Entry const& e, HashVal hash)  const
  {
    verify_Entry (e,hash);
    POA& request = *(e.second);
    const POA* solution (request.getSolution());
    if (solution && hasProvision(*solution))
      {
        POA* currentSolution = provisionEntries_[hash].find_latest_solution (request); 
        VERIFY (e.first.matches (solution->getMatcher()),"stored advice solution not supported by binding match");
        VERIFY (bool(currentSolution),                   "unable to reproduce stored solution with the current provisions")
        VERIFY (solution == currentSolution,             "stored advice solution isn't the topmost solution for this request")
      }
  }
  
#undef VERIFY
  
  
}} // namespace lumiera::advice
#endif