itertools.hpp

Go to the documentation of this file.

/*
  ITERTOOLS.hpp  -  collection of tools for building and combining iterators 

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


#include "lib/iter-adapter.hpp"
#include "lib/meta/value-type-binding.hpp"
#include "lib/meta/function.hpp"
#include "lib/meta/trait.hpp"
#include "lib/wrapper.hpp"
#include "lib/util.hpp"

#include <functional>
#include <utility>



namespace lib {
  
  using std::forward;
  using std::function;
  using util::unConst;
  
  using lib::meta::ValueTypeBinding;
  
  
  
  template<class IT>
  struct IdentityCore
    {
      IT source_;
      
      IdentityCore (IT&& orig)
        : source_{forward<IT>(orig)}
        { }
      IdentityCore (IT const& orig)
        : source_{orig}
        { }
      
      IT&
      pipe ()
        {
          return source_;
        }
      
      IT const&
      pipe ()  const
        {
          return source_;
        }
      
      void
      advance ()
        {
          ++source_;
        }
      
      bool
      evaluate () const
        {
          return bool(source_);
        }
      
      typedef typename IT::pointer pointer;
      typedef typename IT::reference reference;
      typedef typename IT::value_type value_type;
    };
  
  
  template<class CORE>
  class IterTool
    {
      
    protected: /* == iteration control == */
      CORE core_;
      
      bool
      hasData()  const
        {
          return core_.evaluate()
              || unConst(this)->iterate();
        }     // to skip irrelevant results doesn't count as "mutation"
      
      bool
      iterate ()
        {
          if (!core_.pipe()) return false;
          
          do core_.advance();
          while (core_.pipe() && !core_.evaluate());
          
          return bool{core_.pipe()};
        }
      
      void
      _maybe_throw()  const
        {
          if (!isValid())
            _throwIterExhausted();
        }
      
      
      
    public:
      typedef typename CORE::pointer pointer;
      typedef typename CORE::reference reference;
      typedef typename CORE::value_type value_type;
      
      
      IterTool (CORE&& setup)
        : core_{std::move(setup)}
        {
          hasData();
        }
      
      explicit
      operator bool() const
        {
          return isValid();
        }
      
      
      
      /* === lumiera forward iterator concept === */
      
      reference
      operator*() const
        {
          _maybe_throw();
          return *core_.pipe();
        }
      
      pointer
      operator->() const
        {
          _maybe_throw();
          return & *core_.pipe();
        }
      
      IterTool&
      operator++()
        {
          _maybe_throw();
          iterate();
          return *this;
        }
      
      bool
      isValid ()  const
        {
          return hasData();
        }
      
      bool
      empty ()    const
        {
          return not isValid();
        }
      
    };
  
  
  template<class CX>
  inline bool
  operator== (IterTool<CX> const& it1, IterTool<CX> const& it2)
  {
    return (!it1 && !it2 )
        || ( it1 &&  it2 && (*it1) == (*it2) )
        ;
  }
  
  template<class CX>
  inline bool
  operator!= (IterTool<CX> const& ito1, IterTool<CX> const& ito2)
  {
    return not (ito1 == ito2);
  }
  
  
  
  
  
  
  
  
  template<class IT>
  struct FilterCore
    : IdentityCore<IT>
    {
      using Raw = IdentityCore<IT>;
      using Val = typename IT::reference;
      
      
      function<bool(Val)> predicate_;
      
      bool
      evaluate () const
        {
          return Raw::pipe()
              && currVal_isOK();
        }
      
      
      mutable bool cached_;
      mutable bool isOK_;
      
      bool
      currVal_isOK () const  
        {
          return (cached_ && isOK_)
              || (cached_ = true
                 &&(isOK_ = predicate_(*Raw::pipe())));
        }
      
      void
      advance ()
        {
          cached_ = false;
          Raw::advance();
        }
      
      
      template<typename PRED>
      FilterCore (IT&& source, PRED prediDef)
        : Raw{forward<IT>(source)}
        , predicate_(prediDef) // induces a signature check
        , cached_(false)      //  not yet cached
        , isOK_(false)       //   not yet relevant
        { }
      
      template<typename PRED>
      FilterCore (IT const& source, PRED prediDef)
        : Raw{source}
        , predicate_(prediDef)
        , cached_(false)
        , isOK_(false)
        { }
    };
  
  
  template<class IT>
  class FilterIter
    : public IterTool<FilterCore<IT>>
    {
      typedef FilterCore<IT> _Filter;
      typedef IterTool<_Filter> _Impl;
      
    public:
      static bool acceptAll(typename _Filter::Val) { return true; }
      
      
      FilterIter ()
        : _Impl{FilterCore<IT>(IT(), acceptAll)}
        { }
      
      template<typename PRED>
      FilterIter (IT const& src, PRED filterPredicate)
        : _Impl{_Filter(src, filterPredicate)}
        { }
      
      template<typename PRED>
      FilterIter (IT&& src, PRED filterPredicate)
        : _Impl{_Filter(forward<IT>(src), filterPredicate)}
        { }
      
      ENABLE_USE_IN_STD_RANGE_FOR_LOOPS (FilterIter)
    };
  
  
  template<class IT, typename PRED>
  inline auto
  filterIterator (IT const& src, PRED filterPredicate)
  {
    return FilterIter<IT>{src, filterPredicate};
  }
  
  template<class IT, typename PRED>
  inline auto
  filterIterator (IT&& src, PRED filterPredicate)
  {
    using SrcIT  = typename std::remove_reference<IT>::type;
    return FilterIter<SrcIT>{forward<IT>(src), filterPredicate};
  }
  
  
  template<class IT>
  class ExtensibleFilterIter
    : public FilterIter<IT>
    {
      using _Filter = FilterCore<IT>;
      using     Val = typename _Filter::Val;
      
      void
      reEvaluate()
        {
          this->core_.cached_ = false;
          this->hasData(); // re-evaluate head element
        }
      
    public:
      ExtensibleFilterIter() { }
      
      template<typename PRED>
      ExtensibleFilterIter (IT&& src, PRED initialFilterPredicate)
        : FilterIter<IT>{forward<IT>(src), initialFilterPredicate}
        { }
      template<typename PRED>
      ExtensibleFilterIter (IT const& src, PRED initialFilterPredicate)
        : FilterIter<IT>{src, initialFilterPredicate}
        { }
      
      ExtensibleFilterIter (IT&& src)
        : ExtensibleFilterIter{forward<IT>(src), FilterIter<IT>::acceptAll}
        { }
      
      // standard copy operations acceptable
      
      
      IT&
      underlying()
        {
          return this->core_.source_;
        }
      
      
      template<typename COND>
      ExtensibleFilterIter&
      andFilter (COND conjunctiveClause)
        {
          function<bool(Val)>& filter = this->core_.predicate_;
          
          filter = [=](Val val)
                      {
                        return filter(val)
                           and conjunctiveClause(val);
                      };
          reEvaluate();
          return *this;
        }
      
      template<typename COND>
      ExtensibleFilterIter&
      andNotFilter (COND conjunctiveClause)
        {
          function<bool(Val)>& filter = this->core_.predicate_;
          
          filter = [=](Val val)
                      {
                        return filter(val)
                           and not conjunctiveClause(val);
                      };
          reEvaluate();
          return *this;
        }
      
      template<typename COND>
      ExtensibleFilterIter&
      orFilter (COND disjunctiveClause)
        {
          function<bool(Val)>& filter = this->core_.predicate_;
          
          filter = [=](Val val)
                      {
                        return filter(val)
                            or disjunctiveClause(val);
                      };
          reEvaluate();
          return *this;
        }
      
      template<typename COND>
      ExtensibleFilterIter&
      orNotFilter (COND disjunctiveClause)
        {
          function<bool(Val)>& filter = this->core_.predicate_;
          
          filter = [=](Val val)
                      {
                        return filter(val)
                            or not disjunctiveClause(val);
                      };
          reEvaluate();
          return *this;
        }
      
      
      template<typename COND>
      ExtensibleFilterIter&
      setNewFilter (COND entirelyDifferentPredicate)
        {
          this->core_.predicate_ = entirelyDifferentPredicate;
          reEvaluate();
          return *this;
        }
      
      ExtensibleFilterIter&
      flipFilter ()
        {
          function<bool(Val)>& filter = this->core_.predicate_;
          
          filter = [=](Val val)
                      {
                        return not filter(val);
                      };
          reEvaluate();
          return *this;
        }
    };
  
  
  
  template<typename VAL>
  class SkipRepetition
    {
      typedef wrapper::ItemWrapper<VAL> Item;
      
      Item prev_;
      
    public:
      bool
      operator() (VAL const& elm)
        {
           if (prev_ &&
              (*prev_ == elm))
             return false;
           
           // element differs from predecessor
           prev_ = elm;
           return true;
        }
      
      typedef bool result_type;
    };
  
  
  
  
  
  
  
  
  
  
  template<typename VAL>
  class SingleValCore
    {
      typedef wrapper::ItemWrapper<VAL> Item;
      
      Item theValue_;
      
    public:
      SingleValCore() { } 
      
      SingleValCore (VAL&& something)
        : theValue_{forward<VAL> (something)}
        { }
      
      Item const&
      pipe ()  const
        {
          return theValue_;
        }
      
      void
      advance ()
        {
          theValue_.reset();
        }
      
      bool
      evaluate () const
        {
          return theValue_.isValid();
        }
      
      typedef std::remove_reference_t<VAL> * pointer;
      typedef std::remove_reference_t<VAL> & reference;
      typedef std::remove_reference_t<VAL>   value_type;
    };
  
  
  template<class VAL>
  class SingleValIter
    : public IterTool<SingleValCore<VAL>>
    {
      using _ValHolder = SingleValCore<VAL>;
      using _IteratorImpl = IterTool<_ValHolder> ;
      
    public:
      SingleValIter ()
        : _IteratorImpl{_ValHolder{}}
        { }
      
      SingleValIter (VAL&& something)
        : _IteratorImpl{_ValHolder{forward<VAL>(something)}}
        { }
      
      ENABLE_USE_IN_STD_RANGE_FOR_LOOPS (SingleValIter)
    };
  
  
  
  template<class VAL>
  inline auto
  singleValIterator (VAL&& something)
  {
    return SingleValIter<VAL>{forward<VAL>(something)};
  }
  
  
  template<class VAL>
  inline auto
  nilIterator()
  {
    return SingleValIter<VAL>();
  }
  

  
  
  
  template<class IT, class VAL>
  class TransformingCore
    {
      typedef typename IT::reference InType;
      typedef wrapper::ItemWrapper<VAL> Item;
      
      function<VAL(InType)> trafo_;
      
      IT   source_;
      Item treated_;
      
      void
      processItem ()
        {
          if (source_)
            treated_ = trafo_(*source_);
          else
            treated_.reset();
        }
      
      
      
    public:
      TransformingCore () 
        : trafo_()
        , source_()
        , treated_()
        { }
      
      template<typename FUN>
      TransformingCore (IT&& orig, FUN processor)
        : trafo_(processor) // induces a signature check
        , source_(forward<IT> (orig))
        {
          processItem();
        }
      
      template<typename FUN>
      TransformingCore (IT const& orig, FUN processor)
        : trafo_(processor) // induces a signature check
        , source_(orig)
        {
          processItem();
        }
      
      Item const&
      pipe ()  const
        {
          return treated_;
        }
      
      void
      advance ()
        {
          ++source_;
          processItem();
        }
      
      bool
      evaluate () const
        {
          return bool(source_);
        }
      
      using pointer =  typename ValueTypeBinding<VAL>::pointer;
      using reference = typename ValueTypeBinding<VAL>::reference;
      using value_type = typename ValueTypeBinding<VAL>::value_type;
    };
  
  
  template<class IT, class VAL>
  class TransformIter
    : public IterTool<TransformingCore<IT,VAL>>
    {
      using _Trafo = TransformingCore<IT,VAL>;
      using _IteratorImpl = IterTool<_Trafo> ;
      
    public:
      TransformIter ()
        : _IteratorImpl(_Trafo())
        { }
      
      template<typename FUN>
      TransformIter (IT&& src, FUN trafoFunc)
        : _IteratorImpl{_Trafo(forward<IT>(src), trafoFunc)}
        { }
      template<typename FUN>
      TransformIter (IT const& src, FUN trafoFunc)
        : _IteratorImpl{_Trafo(src, trafoFunc)}
        { }
      
      ENABLE_USE_IN_STD_RANGE_FOR_LOOPS (TransformIter)
    };
  
  
  
  
  
  template<class IT, typename FUN>
  inline auto
  transformIterator (IT const& src, FUN processingFunc)
  {
    using OutVal = typename lib::meta::_Fun<FUN>::Ret;
    return TransformIter<IT,OutVal>{src,processingFunc};
  }
  
  template<class IT, typename FUN>
  inline auto
  transformIterator (IT&& src, FUN processingFunc)
  {
    using SrcIT  = typename std::remove_reference<IT>::type;
    using OutVal = typename lib::meta::_Fun<FUN>::Ret;
    return TransformIter<SrcIT,OutVal>{forward<IT>(src), processingFunc};
  }
  
  
  
  
  /* === utility functions === */
  
  template<class IT, class CON>
  inline void
  append_all (IT iter, CON& container)
  {
    for ( ; iter; ++iter )
      container.push_back (*iter);
  }
  
  
  template<class IT>
  inline typename IT::value_type
  pull_last (IT iter)
    {
      using Val = typename IT::value_type;
      using Item = wrapper::ItemWrapper<Val>;
      
      Item lastElm;
      
      while (iter)
        {
          lastElm = *iter;
          ++iter;
        }
      
      if (lastElm)
        return *lastElm;
      else
        throw lumiera::error::State ("attempt to retrieve the last element "
                                     "of an exhausted or empty iterator"
                                    ,lumiera::error::LUMIERA_ERROR_ITER_EXHAUST);
    }
  
  
  
  template<class IT>
  inline auto
  filterRepetitions (IT const& source)
  {
    using Val   = typename meta::ValueTypeBinding<IT>::value_type;
    return filterIterator (source, SkipRepetition<Val>());
  }
  
  template<class IT>
  inline auto
  filterRepetitions (IT&& source)
  {
    using Val   = typename meta::ValueTypeBinding<IT>::value_type;
    return filterIterator (forward<IT>(source), SkipRepetition<Val>() );
  }
  
  
  
  
  
} // namespace lib
#endif