split-splice.hpp

/*
  SPLIT-SPLICE.hpp  -  Algorithm to integrate a new interval into an axis-segmentation.

  Copyright (C)         Lumiera.org
    2023,               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_SPLIT_SPLICE_H
#define LIB_SPLIT_SPLICE_H

#include "lib/error.hpp"
#include "lib/meta/function.hpp"
#include "lib/time/timevalue.hpp"
#include "lib/nocopy.hpp"

#include <array>


namespace lib {
  
  namespace error = lumiera::error;
  
  
  namespace splitsplice {
    
    
    template<class ORD        
            ,class POS        
            ,class START      
            ,class AFTER      
            ,class CREATE     
            ,class EMPTY      
            ,class CLONE      
            ,class DELETE     
            >
    class Algo
      : util::NonCopyable
      {
        /* ======= elementary operations ======= */
        
        ASSERT_VALID_SIGNATURE (START,  ORD(POS))
        ASSERT_VALID_SIGNATURE (AFTER,  ORD(POS))
        ASSERT_VALID_SIGNATURE (CREATE, POS(POS,ORD,ORD))
        ASSERT_VALID_SIGNATURE (EMPTY,  POS(POS,ORD,ORD))
        ASSERT_VALID_SIGNATURE (CLONE,  POS(POS,ORD,ORD,POS))
        ASSERT_VALID_SIGNATURE (DELETE, POS(POS,POS))
        
        START  getStart;
        AFTER  getAfter;
        CREATE createSeg;
        EMPTY  emptySeg;
        CLONE  cloneSeg;
        DELETE discard;
        
        using OptORD = std::optional<ORD>;
        const ORD AXIS_END;
        
        
        /* ======= working state ======= */
        
        POS pred_, succ_;
        
        struct SegBounds
          {                            // can be assigned in one step (ORD may be immutable)
            ORD start,
                after;
          } b_;
        
        enum Verb { NIL
                  , DROP
                  , TRUNC
                  , INS_NOP
                  , SEAMLESS
                  };
        
        Verb opPred_ = NIL,
             opSucc_ = NIL;
        
      public:
        Algo (START  fun_getStart
             ,AFTER  fun_getAfter
             ,CREATE fun_createSeg
             ,EMPTY  fun_emptySeg
             ,CLONE  fun_cloneSeg
             ,DELETE fun_discard
             ,const ORD axisEnd
             ,POS startAll, POS afterAll
             ,OptORD start, OptORD after)
          : getStart{fun_getStart}
          , getAfter{fun_getAfter}
          , createSeg{fun_createSeg}
          , emptySeg{fun_emptySeg}
          , cloneSeg{fun_cloneSeg}
          , discard {fun_discard}
          , AXIS_END{axisEnd}
          , pred_{}
          , succ_{}
          , b_{establishSplitPoint (startAll,afterAll, start,after)}
          {
            // Postcondition: ordered start and end times
            ENSURE (pred_ != afterAll);
            ENSURE (succ_ != afterAll);
            ENSURE (b_.start < b_.after);
            ENSURE (getStart(pred_) <= b_.start);
            ENSURE (b_.start <= getStart(succ_) or pred_ == succ_);
          }
        
        SegBounds
        establishSplitPoint (POS startAll, POS afterAll
                            ,OptORD start, OptORD after)
          { // nominal break point
            ORD sep = start? *start
                           : after? *after
                                  : AXIS_END;
            
            // find largest Predecessor with start before separator
            for (succ_ = startAll, pred_ = afterAll
                ;succ_ != afterAll and getStart(succ_) < sep
                ;++succ_)
              {
                pred_ = succ_;
              }
            REQUIRE (pred_ != succ_, "non-empty segmentation required");
            if (succ_ == afterAll) succ_=pred_;
            if (pred_ == afterAll) pred_=succ_; // separator touches bounds
            
            // Stage-2 : establish start and end point of new segment
            
            ORD startSeg = start? *start
                                : getAfter(pred_) < sep? getAfter(pred_)
                                                       : getStart(pred_);
            ORD afterSeg = after? *after
                                : getStart(succ_) > sep? getStart(succ_)
                                                       : getAfter(succ_);
            ENSURE (startSeg != afterSeg);
            if (startSeg < afterSeg)
              return {startSeg,afterSeg};
            else
              return {afterSeg,startSeg};
          }
        
        
        void
        determineRelations()
          {
            ORD startPred = getStart (pred_),
                afterPred = getAfter (pred_);
            
            if (startPred < b_.start)
              {
                if (afterPred <  b_.start) opPred_ = INS_NOP;
                else
                if (afterPred == b_.start) opPred_ = SEAMLESS;
                else
                  {
                    opPred_ = TRUNC;
                    if (afterPred  > b_.after)
                      { // predecessor actually spans the new segment
                        // thus use it also as successor and truncate both (=SPLIT)
                        succ_ = pred_;
                        opSucc_ = TRUNC;
                        return;
              }   }   }
            else
              {
                REQUIRE (startPred == b_.start, "predecessor does not precede start point");
                opPred_ = DROP;
                if (b_.after < afterPred )
                  { // predecessor coincides with start of new segment
                    // thus use it rather as successor and truncate at start
                    succ_ = pred_;
                    opSucc_ = TRUNC;
                    return;
              }   }
            
            ORD startSucc = getStart (succ_);
            if (startSucc <  b_.after)
              {
                while (getAfter(succ_) < b_.after)
                  ++succ_;
                ASSERT (getStart(succ_) < b_.after  // in case we dropped a successor completely spanned,
                       ,"seamless segmentation");  //  even the next one must start within the new segment
                
                if (b_.after == getAfter(succ_)) opSucc_ = DROP;
                else
                if (b_.after <  getAfter(succ_)) opSucc_ = TRUNC;
              }
            else
              {
                if (b_.after == startSucc) opSucc_ = SEAMLESS;
                else                       opSucc_ = INS_NOP;
              }
          }
        
        
        std::array<POS, 3>
        performSplitSplice()
          {
            POS refPred = pred_, refSucc = succ_;
            REQUIRE (opPred_ != NIL and opSucc_ != NIL);
            
            // deletions are done by skipping the complete range around the insertion point;
            // thus to retain a predecessor or successor, this range has to be reduced
            if (opPred_ == INS_NOP or opPred_ == SEAMLESS)
              ++pred_;
            if (opSucc_ == DROP or opSucc_ == TRUNC)
              ++succ_;
            
            // insert the new elements /before/ the range to be dropped, i.e. at pred_
            POS insPos = pred_;
            POS n = createSeg (insPos, b_.start, b_.after);
            POS s = n;
            //
            // possibly adapt the predecessor
            if (opPred_ == INS_NOP)
              s = emptySeg (n, getAfter(refPred), b_.start);
            else
            if (opPred_ == TRUNC)
              s = cloneSeg (n, getStart(refPred), b_.start, refPred);
            //
            // possibly adapt the successor
            if (opSucc_ == INS_NOP)
              emptySeg (insPos, b_.after, getStart(refSucc));
            else
            if (opSucc_ == TRUNC)
              cloneSeg (insPos, b_.after, getAfter(refSucc), refSucc);
            
            // finally discard superseded segments
            POS e = discard (insPos, succ_);
            
            // indicate the range where changes happened
            return {s,n,e};
          }
      };
    
  }//namespace splitsplace
} // namespace lib
#endif /*LIB_SPLIT_SPLICE_H*/