iter-chain-search.hpp

Go to the documentation of this file.

/*
  ITER-CHAIN-SEARCH.hpp  -  chained search with backtracking based on (bidirectional) iterator

  Copyright (C)         Lumiera.org
    2018,               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 SRC_LIB_ITER_CHAIN_SEARCH_H
#define SRC_LIB_ITER_CHAIN_SEARCH_H


#include "lib/error.hpp"
#include "lib/iter-explorer.hpp"
#include "lib/meta/util.hpp"

#include <utility>
#include <vector>
#include <string>


namespace lib {
namespace iter {
  
  using std::move;
  using std::forward;
  using std::string;
  
  using lib::meta::disable_if;
  
  
  namespace { // type construction helpers...
    
    template<class SRC>
    auto
    buildSearchFilter (SRC&& dataSource)
    {
      return explore (forward<SRC> (dataSource))
                .mutableFilter();
    }
    
    template<class SRC>
    auto
    buildChainExplorer (SRC&& dataSource)
    {
      return buildSearchFilter (forward<SRC> (dataSource))
                .expand ([](auto it){ return it; });   // child iterator starts as copy of current level iterator
    }
    
    template<class SRC>
    struct _IterChainSetup
      {
        using Filter = decltype( buildSearchFilter(std::declval<SRC>()).asIterator() );
        using Pipeline = decltype( buildChainExplorer (std::declval<SRC>()) );
        
        using StepFunctor = std::function<void(Filter&)>;
      };
    
  }//(End)type construction helpers
  
  
  
  
  
  /*********************************************************************************************************/
  template<class SRC>
  class IterChainSearch
    : public _IterChainSetup<SRC>::Pipeline
    {
      using _Trait = _IterChainSetup<SRC>;
      using _Base  = typename _Trait::Pipeline;
      
      using Value  = typename _Base::value_type;
      using Filter = typename _Trait::Filter;
      using Step   = typename _Trait::StepFunctor;
      
      std::vector<Step> stepChain_;
      
      
      bool
      needsExpansion()  const
        {
          return _Base::depth() < stepChain_.size();
        }

    public:
      template<class SEQ>
      explicit
      IterChainSearch (SEQ&& srcData)
        : _Base{buildChainExplorer (forward<SEQ> (srcData))}
        {      // mark initial pristine state
          _Base::disableFilter();
        }
      
      // inherited default ctor and standard copy operations
      using _Base::_Base;
      
      
      /* === adapted iteration control API  === */
      void
      iterNext()
        {
          _Base::__throw_if_empty();
          if (not needsExpansion())
            _Base::iterNext();
          while (needsExpansion()                                   // Backtracking loop: attempt to establish all conditions
                 and _Base::checkPoint())                           // possibly trying further combinations until success:
            {
              uint depth =_Base::depth();
              _Base::expandChildren();                              // create copy of current filter embedded into child level
              stepChain_[depth] (_Base::accessCurrentChildIter());  // invoke step functor to reconfigure this filter...
              _Base::dropExhaustedChildren();                       // which thereby might become empty
            }
        }
      
      IterChainSearch&
      operator++()
        {
          iterNext();
          return *this;
        }
      
      
      
      template<typename FUN>
      IterChainSearch&&
      addStep (FUN&& configureSearchStep)
        {
          if (not this->empty())
            {
              Step nextStep{forward<FUN> (configureSearchStep)};
              
              if (_Base::isDisabled())
                nextStep (*this);                               // apply first step immediately
              else                                             //  (implicitly enables the base filter)
                {
                  stepChain_.emplace_back (move (nextStep)); //    append all further steps into the chain...
                  this->iterNext();                         //     then establish invariant:
                }                                          //      expand to leaf and forward to first match
            }
          return move(*this);
        }
      
      template<typename FUN>
                                          disable_if<is_convertible<FUN, Value>,
      IterChainSearch&&                             >
      search (FUN&& filterPredicate)
        {
          addStep ([predicate{forward<FUN> (filterPredicate)}]
                   (Filter& filter)
                     {         // manipulate current filter configuration
                       filter.setNewFilter (predicate);
                     });
          return move(*this);
        }
      
      IterChainSearch&&
      search (Value target)
        {
          search ([target](Value const& currVal) { return currVal == target; });
          return move(*this);
        }
      
      IterChainSearch&&
      clearFilter()
        {
          stepChain_.clear();
          _Base::rootCurrent();
          _Base::disableFilter();
          return move(*this);
        }
    };
  
  
  
  
  /* ==== convenient builder free function ==== */
  
  template<class SRC>
  inline auto
  chainSearch (SRC&& srcData)
  {
    return IterChainSearch<SRC>{forward<SRC> (srcData)};
  }
  
  
  
}} // namespace lib::iter
#endif /*SRC_LIB_ITER_CHAIN_SEARCH_H*/