projects.mako.cc - wikiq/blob - dtl/Diff3.hpp

   1 /**
   2    dtl-1.12 -- Diff Template Library
   3
   4    In short, Diff Template Library is distributed under so called "BSD license",
   5
   6    Copyright (c) 2008-2011 Tatsuhiko Kubo <cubicdaiya@gmail.com>
   7    All rights reserved.
   8
   9    Redistribution and use in source and binary forms, with or without modification,
  10    are permitted provided that the following conditions are met:
  11
  12    * Redistributions of source code must retain the above copyright notice,
  13    this list of conditions and the following disclaimer.
  14
  15    * Redistributions in binary form must reproduce the above copyright notice,
  16    this list of conditions and the following disclaimer in the documentation
  17    and/or other materials provided with the distribution.
  18
  19    * Neither the name of the authors nor the names of its contributors
  20    may be used to endorse or promote products derived from this software
  21    without specific prior written permission.
  22
  23    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27    OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28    SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29    TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34 */
  35
  36 /* If you use this library, you must include dtl.hpp only. */
  37
  38 #ifndef DTL_DIFF3_H
  39 #define DTL_DIFF3_H
  40
  41 namespace dtl {
  42
  43     /**
  44      * diff3 class template
  45      * sequence must support random_access_iterator.
  46      */
  47     template <typename elem, typename sequence = vector< elem >, typename comparator = Compare< elem > >
  48     class Diff3
  49     {
  50     private:
  51         dtl_typedefs(elem, sequence)
  52         sequence                           A;
  53         sequence                           B;
  54         sequence                           C;
  55         sequence                           S;
  56         Diff< elem, sequence, comparator > diff_ba;
  57         Diff< elem, sequence, comparator > diff_bc;
  58         bool                               conflict;
  59         elem                               csepabegin;
  60         elem                               csepa;
  61         elem                               csepaend;
  62     public :
  63         Diff3 () {}
  64         Diff3 (const sequence& a,
  65                const sequence& b,
  66                const sequence& c) : A(a), B(b), C(c),
  67                                     diff_ba(b, a), diff_bc(b, c),
  68                                     conflict(false) {}
  69
  70         ~Diff3 () {}
  71
  72         bool isConflict () const {
  73             return conflict;
  74         }
  75
  76         sequence getMergedSequence () const {
  77             return S;
  78         }
  79
  80         /**
  81          * merge changes B and C to A
  82          */
  83         bool merge () {
  84             if (diff_ba.getEditDistance() == 0) {     // A == B
  85                 if (diff_bc.getEditDistance() == 0) { // A == B == C
  86                     S = B;
  87                     return true;
  88                 }
  89                 S = C;
  90                 return true;
  91             } else {                                  // A != B
  92                 if (diff_bc.getEditDistance() == 0) { // A != B == C
  93                     S = A;
  94                     return true;
  95                 } else {                              // A != B != C
  96                     S = merge_();
  97                     if (isConflict()) {               // conflict occured
  98                         return false;
  99                     }
 100                 }
 101             }
 102             return true;
 103         }
 104
 105         /**
 106          * compose differences
 107          */
 108         void compose () {
 109             diff_ba.compose();
 110             diff_bc.compose();
 111         }
 112
 113     private :
 114         /**
 115          * merge implementation
 116          */
 117         sequence merge_ () {
 118             elemVec         seq;
 119             Ses< elem >     ses_ba   = diff_ba.getSes();
 120             Ses< elem >     ses_bc   = diff_bc.getSes();
 121             sesElemVec      ses_ba_v = ses_ba.getSequence();
 122             sesElemVec      ses_bc_v = ses_bc.getSequence();
 123             sesElemVec_iter ba_it    = ses_ba_v.begin();
 124             sesElemVec_iter bc_it    = ses_bc_v.begin();
 125             sesElemVec_iter ba_end   = ses_ba_v.end();
 126             sesElemVec_iter bc_end   = ses_bc_v.end();
 127
 128             while (!isEnd(ba_end, ba_it) || !isEnd(bc_end, bc_it)) {
 129                 while (true) {
 130                     if (!isEnd(ba_end, ba_it)            &&
 131                         !isEnd(bc_end, bc_it)            &&
 132                         ba_it->first == bc_it->first     &&
 133                         ba_it->second.type == SES_COMMON &&
 134                         bc_it->second.type == SES_COMMON) {
 135                         // do nothing
 136                     } else {
 137                         break;
 138                     }
 139                     if      (!isEnd(ba_end, ba_it)) seq.push_back(ba_it->first);
 140                     else if (!isEnd(bc_end, bc_it)) seq.push_back(bc_it->first);
 141                     forwardUntilEnd(ba_end, ba_it);
 142                     forwardUntilEnd(bc_end, bc_it);
 143                 }
 144                 if (isEnd(ba_end, ba_it) || isEnd(bc_end, bc_it)) break;
 145                 if (   ba_it->second.type == SES_COMMON
 146                        && bc_it->second.type == SES_DELETE) {
 147                     forwardUntilEnd(ba_end, ba_it);
 148                     forwardUntilEnd(bc_end, bc_it);
 149                 } else if (ba_it->second.type == SES_COMMON &&
 150                            bc_it->second.type == SES_ADD) {
 151                     seq.push_back(bc_it->first);
 152                     forwardUntilEnd(bc_end, bc_it);
 153                 } else if (ba_it->second.type == SES_DELETE &&
 154                            bc_it->second.type == SES_COMMON) {
 155                     forwardUntilEnd(ba_end, ba_it);
 156                     forwardUntilEnd(bc_end, bc_it);
 157                 } else if (ba_it->second.type == SES_DELETE &&
 158                            bc_it->second.type == SES_DELETE) {
 159                     if (ba_it->first == bc_it->first) {
 160                         forwardUntilEnd(ba_end, ba_it);
 161                         forwardUntilEnd(bc_end, bc_it);
 162                     } else {
 163                         // conflict
 164                         conflict = true;
 165                         return B;
 166                     }
 167                 } else if (ba_it->second.type == SES_DELETE &&
 168                            bc_it->second.type == SES_ADD) {
 169                     // conflict
 170                     conflict = true;
 171                     return B;
 172                 } else if (ba_it->second.type == SES_ADD &&
 173                            bc_it->second.type == SES_COMMON) {
 174                     seq.push_back(ba_it->first);
 175                     forwardUntilEnd(ba_end, ba_it);
 176                 } else if (ba_it->second.type == SES_ADD &&
 177                            bc_it->second.type == SES_DELETE) {
 178                     // conflict
 179                     conflict = true;
 180                     return B;
 181                 } else if (ba_it->second.type == SES_ADD &&
 182                            bc_it->second.type == SES_ADD) {
 183                     if (ba_it->first == bc_it->first) {
 184                         seq.push_back(ba_it->first);
 185                         forwardUntilEnd(ba_end, ba_it);
 186                         forwardUntilEnd(bc_end, bc_it);
 187                     } else {
 188                         // conflict
 189                         conflict = true;
 190                         return B;
 191                     }
 192                 }
 193             }
 194
 195             if (isEnd(ba_end, ba_it)) {
 196                 addDecentSequence(bc_end, bc_it, seq);
 197             } else if (isEnd(bc_end, bc_it)) {
 198                 addDecentSequence(ba_end, ba_it, seq);
 199             }
 200
 201             sequence mergedSeq(seq.begin(), seq.end());
 202             return mergedSeq;
 203         }
 204
 205         /**
 206          * join elem vectors
 207          */
 208         void inline joinElemVec (elemVec& s1, elemVec& s2) const {
 209             if (!s2.empty()) {
 210                 for (elemVec_iter vit=s2.begin();vit!=s2.end();++vit) {
 211                     s1.push_back(*vit);
 212                 }
 213             }
 214         }
 215
 216         /**
 217          * check sequence is end
 218          */
 219         template <typename T_iter>
 220         bool inline isEnd (const T_iter& end, const T_iter& it) const {
 221             return it == end ? true : false;
 222         }
 223
 224         /**
 225          * increment iterator until iterator is end
 226          */
 227         template <typename T_iter>
 228         void inline forwardUntilEnd (const T_iter& end, T_iter& it) const {
 229             if (!isEnd(end, it)) ++it;
 230         }
 231
 232         /**
 233          * add elements which SES's type is ADD
 234          */
 235         void inline addDecentSequence (const sesElemVec_iter& end, sesElemVec_iter& it, elemVec& seq) const {
 236             while (!isEnd(end, it)) {
 237                 if (it->second.type == SES_ADD) seq.push_back(it->first);
 238                 ++it;
 239             }
 240         }
 241
 242     };
 243 }
 244
 245 #endif // DTL_DIFF3_H