michael@0: // Copyright 2013 Google Inc. All Rights Reserved.
michael@0: //
michael@0: // Licensed under the Apache License, Version 2.0 (the "License");
michael@0: // you may not use this file except in compliance with the License.
michael@0: // You may obtain a copy of the License at
michael@0: //
michael@0: //     http://www.apache.org/licenses/LICENSE-2.0
michael@0: //
michael@0: // Unless required by applicable law or agreed to in writing, software
michael@0: // distributed under the License is distributed on an "AS IS" BASIS,
michael@0: // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
michael@0: // See the License for the specific language governing permissions and
michael@0: // limitations under the License.
michael@0: 
michael@0: //
michael@0: // Author: dsites@google.com (Dick Sites)
michael@0: //
michael@0: //
michael@0: 
michael@0: #include "offsetmap.h"
michael@0: 
michael@0: #include <string.h>                     // for strcmp
michael@0: #include <stdio.h>                      // for fprintf, stderr, fclose, etc
michael@0: #include <algorithm>                    // for min
michael@0: 
michael@0: using namespace std;
michael@0: 
michael@0: namespace CLD2 {
michael@0: 
michael@0: // Constructor, destructor
michael@0: OffsetMap::OffsetMap() {
michael@0:   Clear();
michael@0: }
michael@0: 
michael@0: OffsetMap::~OffsetMap() {
michael@0: }
michael@0: 
michael@0: // Clear the map
michael@0: // After:
michael@0: //   next_diff_sub_ is 0
michael@0: //   Windows are the a and a' ranges covered by diffs_[next_diff_sub_-1]
michael@0: //   which is a fake range of width 0 mapping 0=>0
michael@0: void OffsetMap::Clear() {
michael@0:   diffs_.clear();
michael@0:   pending_op_ = COPY_OP;
michael@0:   pending_length_ = 0;
michael@0:   next_diff_sub_ = 0;
michael@0:   current_lo_aoffset_ = 0;
michael@0:   current_hi_aoffset_ = 0;
michael@0:   current_lo_aprimeoffset_ = 0;
michael@0:   current_hi_aprimeoffset_ = 0;
michael@0:   current_diff_ = 0;
michael@0:   max_aoffset_ = 0;           // Largest seen so far
michael@0:   max_aprimeoffset_ = 0;      // Largest seen so far
michael@0: }
michael@0: 
michael@0: static inline char OpPart(const char c) {
michael@0:   return (c >> 6) & 3;
michael@0: }
michael@0: static inline char LenPart(const char c) {
michael@0:   return c & 0x3f;
michael@0: }
michael@0: 
michael@0: // Print map to file, for debugging
michael@0: void OffsetMap::Printmap(const char* filename) {
michael@0:   FILE* fout;
michael@0:   bool needs_close = false;
michael@0:   if (strcmp(filename, "stdout") == 0) {
michael@0:     fout = stdout;
michael@0:   } else if (strcmp(filename, "stderr") == 0) {
michael@0:     fout = stderr;
michael@0:   } else {
michael@0:     fout = fopen(filename, "w");
michael@0:     needs_close = true;
michael@0:   }
michael@0:   if (fout == NULL) {
michael@0:     fprintf(stderr, "%s did not open\n", filename);
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   Flush();    // Make sure any pending entry gets printed
michael@0:   fprintf(fout, "Offsetmap: %ld bytes\n", diffs_.size());
michael@0:   for (int i = 0; i < static_cast<int>(diffs_.size()); ++i) {
michael@0:     fprintf(fout, "%c%02d ", "&=+-"[OpPart(diffs_[i])], LenPart(diffs_[i]));
michael@0:     if ((i % 20) == 19) {fprintf(fout, "\n");}
michael@0:   }
michael@0:   fprintf(fout, "\n");
michael@0:   if (needs_close) {
michael@0:     fclose(fout);
michael@0:   }
michael@0: }
michael@0: 
michael@0: // Reset to offset 0
michael@0: void OffsetMap::Reset() {
michael@0:   MaybeFlushAll();
michael@0: 
michael@0:   next_diff_sub_ = 0;
michael@0:   current_lo_aoffset_ = 0;
michael@0:   current_hi_aoffset_ = 0;
michael@0:   current_lo_aprimeoffset_ = 0;
michael@0:   current_hi_aprimeoffset_ = 0;
michael@0:   current_diff_ = 0;
michael@0: }
michael@0: 
michael@0: // Add to  mapping from A to A', specifying how many next bytes are
michael@0: // identical in A and A'
michael@0: void OffsetMap::Copy(int bytes) {
michael@0:   if (bytes == 0) {return;}
michael@0:   max_aoffset_ += bytes;           // Largest seen so far
michael@0:   max_aprimeoffset_ += bytes;      // Largest seen so far
michael@0:   if (pending_op_ == COPY_OP) {
michael@0:     pending_length_ += bytes;
michael@0:   } else {
michael@0:     Flush();
michael@0:     pending_op_ = COPY_OP;
michael@0:     pending_length_ = bytes;
michael@0:   }
michael@0: }
michael@0: 
michael@0: // Add to mapping from A to A', specifying how many next bytes are
michael@0: // inserted in A' while not advancing in A at all
michael@0: void OffsetMap::Insert(int bytes){
michael@0:   if (bytes == 0) {return;}
michael@0:   max_aprimeoffset_ += bytes;      // Largest seen so far
michael@0:   if (pending_op_ == INSERT_OP) {
michael@0:     pending_length_ += bytes;
michael@0:   } else if ((bytes == 1) &&
michael@0:              (pending_op_ == DELETE_OP) && (pending_length_ == 1)) {
michael@0:     // Special-case exactly delete(1) insert(1) +> copy(1);
michael@0:     // all others backmap inserts to after deletes
michael@0:     pending_op_ = COPY_OP;
michael@0:   } else {
michael@0:     Flush();
michael@0:     pending_op_ = INSERT_OP;
michael@0:     pending_length_ = bytes;
michael@0:   }
michael@0: }
michael@0: 
michael@0: // Add to mapping from A to A', specifying how many next bytes are
michael@0: // deleted from A while not advancing in A' at all
michael@0: void OffsetMap::Delete(int bytes){
michael@0:   if (bytes == 0) {return;}
michael@0:   max_aoffset_ += bytes;           // Largest seen so far
michael@0:   if (pending_op_ == DELETE_OP) {
michael@0:     pending_length_ += bytes;
michael@0:     } else if ((bytes == 1) &&
michael@0:                (pending_op_ == INSERT_OP) && (pending_length_ == 1)) {
michael@0:       // Special-case exactly insert(1) delete(1) => copy(1);
michael@0:       // all others backmap deletes to after insertss
michael@0:       pending_op_ = COPY_OP;
michael@0:   } else {
michael@0:     Flush();
michael@0:     pending_op_ = DELETE_OP;
michael@0:     pending_length_ = bytes;
michael@0:   }
michael@0: }
michael@0: 
michael@0: void OffsetMap::Flush() {
michael@0:   if (pending_length_ == 0) {
michael@0:     return;
michael@0:   }
michael@0:   // We may be emitting a copy op just after a copy op because +1 -1 cancelled
michael@0:   // inbetween. If the lengths don't need a prefix byte, combine them
michael@0:   if ((pending_op_ == COPY_OP) && !diffs_.empty()) {
michael@0:     char c = diffs_[diffs_.size() - 1];
michael@0:     MapOp prior_op = static_cast<MapOp>(OpPart(c));
michael@0:     int prior_len = LenPart(c);
michael@0:     if ((prior_op == COPY_OP) && ((prior_len + pending_length_) <= 0x3f)) {
michael@0:       diffs_[diffs_.size() - 1] += pending_length_;
michael@0:       pending_length_ = 0;
michael@0:       return;
michael@0:     }
michael@0:   }
michael@0:   if (pending_length_ > 0x3f) {
michael@0:     bool non_zero_emitted = false;
michael@0:     for (int shift = 30; shift > 0; shift -= 6) {
michael@0:       int prefix = (pending_length_ >> shift) & 0x3f;
michael@0:       if ((prefix > 0) || non_zero_emitted) {
michael@0:         Emit(PREFIX_OP, prefix);
michael@0:         non_zero_emitted = true;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0:   Emit(pending_op_, pending_length_ & 0x3f);
michael@0:   pending_length_ = 0;
michael@0: }
michael@0: 
michael@0: 
michael@0: // Add one more entry to copy one byte off the end, then flush
michael@0: void OffsetMap::FlushAll() {
michael@0:   Copy(1);
michael@0:   Flush();
michael@0: }
michael@0: 
michael@0: // Flush all if necessary
michael@0: void OffsetMap::MaybeFlushAll() {
michael@0:   if ((0 < pending_length_) || diffs_.empty()) {
michael@0:     FlushAll();
michael@0:   }
michael@0: }
michael@0: 
michael@0: // Len may be 0, for example as the low piece of length=64
michael@0: void OffsetMap::Emit(MapOp op, int len) {
michael@0:   char c = (static_cast<char>(op) << 6) | (len & 0x3f);
michael@0:   diffs_.push_back(c);
michael@0: }
michael@0: 
michael@0: void OffsetMap::DumpString() {
michael@0:   for (int i = 0; i < static_cast<int>(diffs_.size()); ++i) {
michael@0:     fprintf(stderr, "%c%02d ", "&=+-"[OpPart(diffs_[i])], LenPart(diffs_[i]));
michael@0:   }
michael@0:   fprintf(stderr, "\n");
michael@0: 
michael@0:   // Print running table of correspondences
michael@0:   fprintf(stderr, "       op      A =>  A'     (A forward-maps to A')\n");
michael@0:   int aoffset = 0;
michael@0:   int aprimeoffset = 0;
michael@0:   int length = 0;
michael@0:   for (int i = 0; i < static_cast<int>(diffs_.size()); ++i) {
michael@0:     char c = diffs_[i];
michael@0:     MapOp op = static_cast<MapOp>(OpPart(c));
michael@0:     int len = LenPart(c);
michael@0:     length = (length << 6) + len;
michael@0:     if (op == COPY_OP) {
michael@0:       aoffset += length;
michael@0:       aprimeoffset += length;
michael@0:       length = 0;
michael@0:     } else if (op == INSERT_OP) {
michael@0:       aoffset += 0;
michael@0:       aprimeoffset += length;
michael@0:       length = 0;
michael@0:     } else if (op == DELETE_OP) {
michael@0:       aoffset += length;
michael@0:       aprimeoffset += 0;
michael@0:       length = 0;
michael@0:     } else {              // (op == PREFIX_OP)
michael@0:       // Do nothing else
michael@0:     }
michael@0:     fprintf(stderr, "[%3d] %c%02d %6d %6d%s\n",
michael@0:             i, "&=+-"[op], len,
michael@0:             aoffset, aprimeoffset,
michael@0:             (next_diff_sub_ == i) ? " <==next_diff_sub_" : "");
michael@0: 
michael@0:   }
michael@0:   fprintf(stderr, "\n");
michael@0: }
michael@0: 
michael@0: void OffsetMap::DumpWindow() {
michael@0:   fprintf(stderr, "DumpWindow(A => A'): max_aoffset_ = %d, "
michael@0:                   "max_aprimeoffset_ = %d, next_diff_sub_ = %d<br>\n",
michael@0:           max_aoffset_, max_aprimeoffset_, next_diff_sub_);
michael@0:   fprintf(stderr, "A  [%u..%u)\n",
michael@0:           current_lo_aoffset_, current_hi_aoffset_);
michael@0:   fprintf(stderr, "A' [%u..%u)\n",
michael@0:           current_lo_aprimeoffset_, current_hi_aprimeoffset_);
michael@0:   fprintf(stderr, "  diff = %d\n", current_diff_);
michael@0:   DumpString();
michael@0: }
michael@0: 
michael@0: //----------------------------------------------------------------------------//
michael@0: // The guts of the 2013 design                                                //
michael@0: // If there are three ranges a b c in  diffs_, we can be in one of five       //
michael@0: // states: LEFT of a, in ranges a b c, or RIGHT of c                          //
michael@0: // In each state, there are windows A[Alo..Ahi), A'[A'lo..A'hi) and diffs_    //
michael@0: // position next_diff_sub_                                                    //
michael@0: // There also are mapping constants max_aoffset_ and max_aprimeoffset_        //
michael@0: // If LEFT, Alo=Ahi=0, A'lo=A'hi=0 and next_diff_sub_=0                       //
michael@0: // If RIGHT, Alo=Ahi=max_aoffset_, A'lo=A'hi=max_aprimeoffset_ and            //
michael@0: //   next_diff_sub_=diffs_.size()                                             //
michael@0: // Otherwise, at least one of A[) and A'[) is non-empty and the first bytes   //
michael@0: //   correspond to each other. If range i is active, next_diff_sub_ is at     //
michael@0: //   the first byte of range i+1. Because of the length-prefix operator,      //
michael@0: //   an individual range item in diffs_ may be multiple bytes                 //
michael@0: // In all cases aprimeoffset = aoffset + current_diff_                        //
michael@0: //   i.e. current_diff_ = aprimeoffset - aoffset                              //
michael@0: //                                                                            //
michael@0: // In the degenerate case of diffs_.empty(), there are only two states        //
michael@0: //   LEFT and RIGHT and the mapping is the identity mapping.                  //
michael@0: // The initial state is LEFT.                                                 //
michael@0: // It is an error to move left into LEFT or right into RIGHT, but the code    //
michael@0: //   below is robust in these cases.                                          //
michael@0: //----------------------------------------------------------------------------//
michael@0: 
michael@0: void OffsetMap::SetLeft() {
michael@0:    current_lo_aoffset_ = 0;
michael@0:    current_hi_aoffset_ = 0;
michael@0:    current_lo_aprimeoffset_ = 0;
michael@0:    current_hi_aprimeoffset_ = 0;
michael@0:    current_diff_ = 0;
michael@0:    next_diff_sub_ = 0;
michael@0: }
michael@0: 
michael@0: void OffsetMap::SetRight() {
michael@0:    current_lo_aoffset_ = max_aoffset_;
michael@0:    current_hi_aoffset_ = max_aoffset_;
michael@0:    current_lo_aprimeoffset_ = max_aprimeoffset_;
michael@0:    current_hi_aprimeoffset_ = max_aprimeoffset_;
michael@0:    current_diff_ = max_aprimeoffset_ - max_aoffset_;
michael@0:    next_diff_sub_ = 0;
michael@0: }
michael@0: 
michael@0: // Back up over previous range, 1..5 bytes
michael@0: // Return subscript at the beginning of that. Pins at 0
michael@0: int OffsetMap::Backup(int sub) {
michael@0:   if (sub <= 0) {return 0;}
michael@0:   --sub;
michael@0:   while ((0 < sub) &&
michael@0:          (static_cast<MapOp>(OpPart(diffs_[sub - 1]) == PREFIX_OP))) {
michael@0:     --sub;
michael@0:   }
michael@0:   return sub;
michael@0: }
michael@0: 
michael@0: // Parse next range, 1..5 bytes
michael@0: // Return subscript just off the end of that
michael@0: int OffsetMap::ParseNext(int sub, MapOp* op, int* length) {
michael@0:    *op = PREFIX_OP;
michael@0:    *length = 0;
michael@0:    char c;
michael@0:    while ((sub < static_cast<int>(diffs_.size())) && (*op == PREFIX_OP)) {
michael@0:      c = diffs_[sub++];
michael@0:      *op = static_cast<MapOp>(OpPart(c));
michael@0:      int len = LenPart(c);
michael@0:      *length = (*length << 6) + len;
michael@0:    }
michael@0:    // If mal-formed or in RIGHT, this will return with op = PREFIX_OP
michael@0:    // Mal-formed can include a trailing prefix byte with no following op
michael@0:    return sub;
michael@0: }
michael@0: 
michael@0: // Parse previous range, 1..5 bytes
michael@0: // Return current subscript
michael@0: int OffsetMap::ParsePrevious(int sub, MapOp* op, int* length) {
michael@0:   sub = Backup(sub);
michael@0:   return ParseNext(sub, op, length);
michael@0: }
michael@0: 
michael@0: // Quick debugging dump; does not parse multi-byte items, so just length & 0x3f
michael@0: void OffsetMap::PrintPosition(const char* str) {
michael@0:   MapOp op = PREFIX_OP;
michael@0:   int length = 0;
michael@0:   if ((0 < next_diff_sub_) && (next_diff_sub_ <= static_cast<int>(diffs_.size()))) {
michael@0:     op = static_cast<MapOp>(OpPart(diffs_[next_diff_sub_ - 1]));
michael@0:     length = LenPart(diffs_[next_diff_sub_ - 1]);
michael@0:   }
michael@0:   fprintf(stderr, "%s[%d] %c%02d = A[%d..%d) ==> A'[%d..%d)\n",
michael@0:           str,
michael@0:           next_diff_sub_, "&=+-"[op], length,
michael@0:           current_lo_aoffset_, current_hi_aoffset_,
michael@0:           current_lo_aprimeoffset_, current_hi_aprimeoffset_);
michael@0: }
michael@0: 
michael@0: // Move active window one range to the right
michael@0: // Return true if move was OK
michael@0: bool OffsetMap::MoveRight() {
michael@0:   // If at last range or RIGHT, set to RIGHT, return error
michael@0:   if (next_diff_sub_ >= static_cast<int>(diffs_.size())) {
michael@0:     SetRight();
michael@0:     return false;
michael@0:   }
michael@0:   // Actually OK to move right
michael@0:   MapOp op;
michael@0:   int length;
michael@0:   bool retval = true;
michael@0:   // If mal-formed or in RIGHT, this will return with op = PREFIX_OP
michael@0:   next_diff_sub_ = ParseNext(next_diff_sub_, &op, &length);
michael@0: 
michael@0:   current_lo_aoffset_ = current_hi_aoffset_;
michael@0:   current_lo_aprimeoffset_ = current_hi_aprimeoffset_;
michael@0:   if (op == COPY_OP) {
michael@0:     current_hi_aoffset_ = current_lo_aoffset_ + length;
michael@0:     current_hi_aprimeoffset_ = current_lo_aprimeoffset_ + length;
michael@0:   } else if (op == INSERT_OP) {
michael@0:     current_hi_aoffset_ = current_lo_aoffset_ + 0;
michael@0:     current_hi_aprimeoffset_ = current_lo_aprimeoffset_ + length;
michael@0:   } else if (op == DELETE_OP) {
michael@0:     current_hi_aoffset_ = current_lo_aoffset_ + length;
michael@0:     current_hi_aprimeoffset_ = current_lo_aprimeoffset_ + 0;
michael@0:   } else {
michael@0:     SetRight();
michael@0:     retval = false;
michael@0:   }
michael@0:   current_diff_ = current_lo_aprimeoffset_ - current_lo_aoffset_;
michael@0:   return retval;
michael@0: }
michael@0: 
michael@0: // Move active window one range to the left
michael@0: // Return true if move was OK
michael@0: bool OffsetMap::MoveLeft() {
michael@0:   // If at first range or LEFT, set to LEFT, return error
michael@0:   if (next_diff_sub_ <= 0) {
michael@0:     SetLeft();
michael@0:     return false;
michael@0:   }
michael@0:   // Back up over current active window
michael@0:   next_diff_sub_ = Backup(next_diff_sub_);
michael@0:   if (next_diff_sub_ <= 0) {
michael@0:     SetLeft();
michael@0:     return false;
michael@0:   }
michael@0:   // Actually OK to move left
michael@0:   MapOp op;
michael@0:   int length;
michael@0:   bool retval = true;
michael@0:   // If mal-formed or in LEFT, this will return with op = PREFIX_OP
michael@0:   next_diff_sub_ = ParsePrevious(next_diff_sub_, &op, &length);
michael@0: 
michael@0:   current_hi_aoffset_ = current_lo_aoffset_;
michael@0:   current_hi_aprimeoffset_ = current_lo_aprimeoffset_;
michael@0:   if (op == COPY_OP) {
michael@0:     current_lo_aoffset_ = current_hi_aoffset_ - length;
michael@0:     current_lo_aprimeoffset_ = current_hi_aprimeoffset_ - length;
michael@0:   } else if (op == INSERT_OP) {
michael@0:     current_lo_aoffset_ = current_hi_aoffset_ - 0;
michael@0:     current_lo_aprimeoffset_ = current_hi_aprimeoffset_ - length;
michael@0:   } else if (op == DELETE_OP) {
michael@0:     current_lo_aoffset_ = current_hi_aoffset_ - length;
michael@0:     current_lo_aprimeoffset_ = current_hi_aprimeoffset_ - 0;
michael@0:   } else {
michael@0:     SetLeft();
michael@0:     retval = false;
michael@0:   }
michael@0:   current_diff_ = current_lo_aprimeoffset_ - current_lo_aoffset_;
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: // Map an offset in A' to the corresponding offset in A
michael@0: int OffsetMap::MapBack(int aprimeoffset){
michael@0:   MaybeFlushAll();
michael@0:   if (aprimeoffset < 0) {return 0;}
michael@0:   if (max_aprimeoffset_ <= aprimeoffset) {
michael@0:      return (aprimeoffset - max_aprimeoffset_) + max_aoffset_;
michael@0:   }
michael@0: 
michael@0:   // If current_lo_aprimeoffset_ <= aprimeoffset < current_hi_aprimeoffset_,
michael@0:   // use current mapping, else move window left/right
michael@0:   bool ok = true;
michael@0:   while (ok && (aprimeoffset < current_lo_aprimeoffset_)) {
michael@0:     ok = MoveLeft();
michael@0:   }
michael@0:   while (ok && (current_hi_aprimeoffset_ <= aprimeoffset)) {
michael@0:     ok = MoveRight();
michael@0:   }
michael@0:   // So now current_lo_aprimeoffset_ <= aprimeoffset < current_hi_aprimeoffset_
michael@0: 
michael@0:   int aoffset = aprimeoffset - current_diff_;
michael@0:   if (aoffset >= current_hi_aoffset_) {
michael@0:     // A' is in an insert region, all bytes of which backmap to A=hi_aoffset_
michael@0:     aoffset = current_hi_aoffset_;
michael@0:   }
michael@0:   return aoffset;
michael@0: }
michael@0: 
michael@0: // Map an offset in A to the corresponding offset in A'
michael@0: int OffsetMap::MapForward(int aoffset){
michael@0:   MaybeFlushAll();
michael@0:   if (aoffset < 0) {return 0;}
michael@0:   if (max_aoffset_ <= aoffset) {
michael@0:      return (aoffset - max_aoffset_) + max_aprimeoffset_;
michael@0:   }
michael@0: 
michael@0:   // If current_lo_aoffset_ <= aoffset < current_hi_aoffset_,
michael@0:   // use current mapping, else move window left/right
michael@0:   bool ok = true;
michael@0:   while (ok && (aoffset < current_lo_aoffset_)) {
michael@0:     ok = MoveLeft();
michael@0:   }
michael@0:   while (ok && (current_hi_aoffset_ <= aoffset)) {
michael@0:     ok = MoveRight();
michael@0:   }
michael@0: 
michael@0:   int aprimeoffset = aoffset + current_diff_;
michael@0:   if (aprimeoffset >= current_hi_aprimeoffset_) {
michael@0:     // A is in a delete region, all bytes of which map to A'=hi_aprimeoffset_
michael@0:     aprimeoffset = current_hi_aprimeoffset_;
michael@0:   }
michael@0:   return aprimeoffset;
michael@0: }
michael@0: 
michael@0: 
michael@0: // static
michael@0: bool OffsetMap::CopyInserts(OffsetMap* source, OffsetMap* dest) {
michael@0:   bool ok = true;
michael@0:   while (ok && (source->next_diff_sub_ != source->diffs_.size())) {
michael@0:     ok = source->MoveRight();
michael@0:     if (source->current_lo_aoffset_ != source->current_hi_aoffset_) {
michael@0:       return false;
michael@0:     }
michael@0:     dest->Insert(
michael@0:         source->current_hi_aprimeoffset_ - source->current_lo_aprimeoffset_);
michael@0:   }
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: // static
michael@0: bool OffsetMap::CopyDeletes(OffsetMap* source, OffsetMap* dest) {
michael@0:   bool ok = true;
michael@0:   while (ok && (source->next_diff_sub_ != source->diffs_.size())) {
michael@0:     ok = source->MoveRight();
michael@0:     if (source->current_lo_aprimeoffset_ != source->current_hi_aprimeoffset_) {
michael@0:       return false;
michael@0:     }
michael@0:     dest->Delete(source->current_hi_aoffset_ - source->current_lo_aoffset_);
michael@0:   }
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: // static
michael@0: void OffsetMap::ComposeOffsetMap(
michael@0:     OffsetMap* g, OffsetMap* f, OffsetMap* h) {
michael@0:   h->Clear();
michael@0:   f->Reset();
michael@0:   g->Reset();
michael@0: 
michael@0:   int lo = 0;
michael@0:   for (;;) {
michael@0:      // Consume delete operations in f. This moves A without moving
michael@0:      // A' and A''.
michael@0:      if (lo >= g->current_hi_aoffset_ && CopyInserts(g, h)) {
michael@0:        if (lo >= f->current_hi_aprimeoffset_ && CopyDeletes(f, h)) {
michael@0:           // fprintf(stderr,
michael@0:           //         "ComposeOffsetMap ERROR, f is longer than g.<br>\n");
michael@0:        }
michael@0: 
michael@0:        // FlushAll(), called by Reset(), MapForward() or MapBack(), has
michael@0:        // added an extra COPY_OP to f and g, so this function has
michael@0:        // composed an extra COPY_OP in h from those. To avoid
michael@0:        // FlushAll() adds one more extra COPY_OP to h later, dispatch
michael@0:        // Flush() right now.
michael@0:        h->Flush();
michael@0:        return;
michael@0:      }
michael@0: 
michael@0:      // Consume insert operations in g. This moves A'' without moving A
michael@0:      // and A'.
michael@0:      if (lo >= f->current_hi_aprimeoffset_) {
michael@0:        if (!CopyDeletes(f, h)) {
michael@0:           // fprintf(stderr,
michael@0:           //         "ComposeOffsetMap ERROR, g is longer than f.<br>\n");
michael@0:        }
michael@0:      }
michael@0: 
michael@0:      // Compose one operation which moves A' from lo to hi.
michael@0:      int hi = min(f->current_hi_aprimeoffset_, g->current_hi_aoffset_);
michael@0:      if (f->current_lo_aoffset_ != f->current_hi_aoffset_ &&
michael@0:          g->current_lo_aprimeoffset_ != g->current_hi_aprimeoffset_) {
michael@0:        h->Copy(hi - lo);
michael@0:      } else if (f->current_lo_aoffset_ != f->current_hi_aoffset_) {
michael@0:        h->Delete(hi - lo);
michael@0:      } else if (g->current_lo_aprimeoffset_ != g->current_hi_aprimeoffset_) {
michael@0:        h->Insert(hi - lo);
michael@0:      }
michael@0: 
michael@0:      lo = hi;
michael@0:   }
michael@0: }
michael@0: 
michael@0: // For testing only -- force a mapping
michael@0: void OffsetMap::StuffIt(const string& diffs,
michael@0:                         int max_aoffset, int max_aprimeoffset) {
michael@0:   Clear();
michael@0:   diffs_ = diffs;
michael@0:   max_aoffset_ = max_aoffset;
michael@0:   max_aprimeoffset_ = max_aprimeoffset;
michael@0: }
michael@0: 
michael@0: 
michael@0: }  // namespace CLD2
michael@0: