list-diff-detector.hpp

Go to the documentation of this file.

/*
  LIST-DIFF-DETECTOR.hpp  -  language to describe differences in linearised form

  Copyright (C)         Lumiera.org
    2015,               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_DIFF_LIST_DIFF_DETECTOR_H
#define LIB_DIFF_LIST_DIFF_DETECTOR_H


#include "lib/diff/list-diff.hpp"
#include "lib/diff/index-table.hpp"
#include "lib/iter-adapter.hpp"
#include "lib/nocopy.hpp"

#include <utility>


namespace lib {
namespace diff{
  
  using util::unConst;
  using std::move;
  using std::swap;
  
  
  template<class SEQ>
  class DiffDetector
    : util::NonCopyable
    {
      using Val = typename SEQ::value_type;
      using Idx = IndexTable<Val>;
      
      Idx refIdx_;
      SEQ const& currentData_;
      
      
      using DiffStep = typename ListDiffLanguage<Val>::DiffStep;
      
      class DiffFrame;
      
      
      
      
    public:
      explicit
      DiffDetector(SEQ const& refSeq)
        : refIdx_(refSeq)
        , currentData_(refSeq)
        { }
      
      
      bool
      isChanged()  const
        {
          auto snapshot = refIdx_.begin();
          for (auto const& elm : currentData_)
            if (snapshot != refIdx_.end() && elm != *snapshot++)
              return true;
          
          return false;
        }
      
      
      using Diff = lib::IterStateWrapper<DiffStep, DiffFrame>;
      
      Diff
      pullUpdate()
        {
          Idx mark (currentData_);
          swap (mark, refIdx_);  // mark now refers to old reference point
          return Diff(DiffFrame(refIdx_, move(mark)));
        }
    };
  
  
  
  
  template<class SEQ>
  class DiffDetector<SEQ>::DiffFrame
    {
      Idx old_;
      Idx* new_;
      size_t oldHead_=0,
             newHead_=0;
      
      static ListDiffLanguage<Val> token;
      
      DiffStep currentStep_;
      
      
    public:
      DiffFrame(Idx& current, Idx&& refPoint)
        : old_(refPoint)
        , new_(&current)
        , currentStep_(establishNextState())
        { }
      
      
      /* === Iteration control API for IterStateWrapper === */
      
      bool
      checkPoint()  const
        {
          return token.NIL != currentStep_;
        }
      
      DiffStep&
      yield()  const
        {
          REQUIRE (checkPoint());
          return unConst(this)->currentStep_;
        }
      
      void
      iterNext()
        {
          currentStep_ = this->establishNextState();
        }
      
    private:
      DiffStep
      establishNextState()
        {
          if (canPick())
            {
              consumeOld();
              return token.pick (consumeNew());
            }
          if (canDelete())
            return token.del (consumeOld());
          if (canInsert())
            return token.ins (consumeNew());
          if (needFetch())
            return token.find (consumeNew());
          if (obsoleted())
            return token.skip (consumeOld());
          
          return token.NIL;
        }
      
      bool hasOld()    const { return oldHead_ < old_.size(); }
      bool hasNew()    const { return newHead_ < new_->size(); }
      bool canPick()   const { return hasOld() && hasNew() && oldElm()==newElm(); }
      bool canDelete() const { return hasOld() && !new_->contains(oldElm());      }
      bool canInsert() const { return hasNew() && !old_.contains(newElm());       }
      bool needFetch() const { return hasNew() && oldHead_ < old_.pos(newElm());  }
      bool obsoleted() const { return hasOld() && newHead_ > new_->pos(oldElm()); }
      
      Val const& oldElm()     const { return old_.getElement (oldHead_); }
      Val const& newElm()     const { return new_->getElement (newHead_); }
      Val const& consumeOld()       { return old_.getElement (oldHead_++); }
      Val const& consumeNew()       { return new_->getElement (newHead_++); }
    };
  
  
  template<class SEQ>
  ListDiffLanguage<typename DiffDetector<SEQ>::Val> DiffDetector<SEQ>::DiffFrame::token;
  
  
  
  
}} // namespace lib::diff
#endif /*LIB_DIFF_LIST_DIFF_DETECTOR_H*/