yavom

Myers算法的另一种泛型容器变体（例如std::Vec）

这是一个准Myers算法的实现，用于确定两个泛型容器之间的差异。它的使用相当简单，例如

let mut a: Vec<String> = vec!["A", "W", "E", "S", "O", "M", "O"]
            .iter()
            .map(|s| s.to_string())
            .collect();
let b: Vec<String> = vec!["S", "T", "R", "A", "N", "G", "E", "S", "O", "M", "O"]
            .iter()
            .map(|s| s.to_string())
            .collect();

// Create the diff (vector of moves)
let moves = crate::yavom::myers(&a, &b);

返回值 moves 是一个包含 Move 对象的向量。您可以按照以下方式将移动应用到数组中

moves.iter().for_each(|m| { crate::yavom::apply_move(m, &mut a); });
// now a's contents are the same as b's

您可以像您认为必要的样子序列化/反序列化 Move 对象。为此，请考虑以下定义（位于 diff.h 中）

pub enum OP {
    INSERT,
    DELETE,
    _DELETE,
}

pub struct Point(pub i64, pub i64);

pub struct Move<K>(pub OP, pub Point, pub Point, pub Option<Vec<K>>);

Vec 字段存储要插入的值。例如

 let ops = myers_unfilled(&a, &b);
 let mut patch = vec![];
 for o in ops {
      let Move(op, s, t, _) = o;
      match op {
          yavomrs::yavom::OP::INSERT => {
              let from = s.1 as usize;
              let to = (s.1 + count) as usize;
              let insert_position = s.1;
              let values = &new[from..to];
              // TODO Serialize INSERT of values at insert_position
          }
          yavomrs::yavom::OP::DELETE => {
              let count = t.0 - s.0;
              let delete_position = s.1;
              // TODO Serialize DELETE of count values starting from delete_position
          }
          yavomrs::yavom::OP::_DELETE => {
              let Point(count, start) = s;
              // TODO Serialize DELETE of count values starting from start
          }
      }
  }
  

如果您想知道需要多少移动，但不希望生成完整的移动（带有完整的插入数据），则可以使用 myers_unfilled 函数

let mut moves = crate::yavom::myers_unfilled(&a, &b);
eprintln!("{} moves", moves.len());

随后您可以填充插入数据

crate::yavom::myers_fill(&b, &mut moves);

致谢 & 许可证

本代码版权所有（C）2022 Amos Brocco（[email protected]）

BSD 3-Clause许可证