main.rs

use core::fmt;
use std::fmt::{Error, Formatter};
use std::option::Iter;

use crate::DeltaType::{CHANGE, DELETE, INSERT};

fn main() {
    for x in create_patch("abc", "def") {
        println!("{}", x.to_string())
    }
    ()
}

enum DeltaType {
    CHANGE,
    DELETE,
    INSERT,
}

impl fmt::Display for DeltaType {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let s = match self {
            CHANGE => "CHANGE",
            DELETE => "DELETE",
            INSERT => "INSERT"
        };
        write!(f, "{}", s)
    }
}

#[derive(Clone, Copy)]
struct DiffChain {
    x: i32,
    y: i32,
    prev: Option<Box<DiffChain>>,
}

impl Iterator for DiffChain {
    type Item = Box<DiffChain>;

    fn next(&mut self) -> Option<Self::Item> {
        return match self.prev {
            Some(_) => self.prev,
            _ => None
        };
    }
}

struct Change {
    delta_type: DeltaType,
    start_original: i32,
    end_original: i32,
    start_revised: i32,
    end_revised: i32,
}

impl fmt::Display for Change {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
        write!(f, "Change{{ delta_type:{}, start_original:{}, end_original:{}, start_revised:{}, end_revised: {} }}",
               self.delta_type,
               self.start_original,
               self.end_original,
               self.start_revised,
               self.end_revised)
    }
}

fn create_patch(source: &str, rev: &str) -> Vec<Change> {
    let mut result: Vec<Change> = Vec::new();
    let path = find_path(source, rev);
    let first = Box::new(DiffChain {
        x: source.len() as i32,
        y: rev.len() as i32,
        prev: None,
    });
    let mut i = -1;
    let mut j = -1;
    buildChanges(&mut result, i, j, &first);
    for chain in path {
        buildChanges(&mut result, i, j, chain);
    }
    return result;
}

fn buildChanges(result: &mut Vec<Change>, mut i: i32, mut j: i32, chain: &Box<DiffChain>) {
    let x = chain.x;
    let y = chain.y;
    let source_delta = x - 1;
    let rev_delta = y - j;
    if source_delta != -1 || rev_delta != -1 {
        let change;
        if rev_delta > 1 && source_delta > 1 { change = CHANGE } else if rev_delta > 1 { change = INSERT } else { change = DELETE; };
        result.push(Change {
            delta_type: change,
            start_original: i + 1,
            end_original: x,
            start_revised: j + 1,
            end_revised: y,
        });
    }
    i = x;
    j = y;
}

fn find_path(source: &str, rev: &str) -> Iter<Box<DiffChain>> {
    let mut source_chars = source.chars();
    let mut rev_chars = rev.chars();
    let N = source.len() as i32;
    let M = rev.len() as i32;
    let MAX = N + M;
    let size = 2 * (MAX + 1);
    let mut diagonal = vec![-1; size as usize];
    let mut pretendents: Vec<Option<&Box<DiffChain>>> = vec![None; size as usize];

    for D in 0..MAX {
        let mut k = -D;
        while k <= D {
            let index: i32;
            let mut x;
            if k == -D || (k != D && diagonal[(MAX + k - 1) as usize] < diagonal[(MAX + k + 1) as usize]) {
                index = MAX + k + 1;
                x = diagonal[index as usize]
            } else {
                index = MAX + k - 1;
                x = diagonal[index as usize] + 1;
            }
            let mut y = x - k;
            let mut chain: Option<Box<DiffChain>> = pretendents[index as usize].map(|a| *a);
            let mut next: Box<DiffChain>;
            while x < N && y < M && source_chars.nth(x as usize) == rev_chars.nth(y as usize) {
                next = Box::new(DiffChain { x, y, prev: chain });
                chain = Some(next);
                x = x + 1;
                y = y + 1;
            }
            if x >= N && y >= M {
                let temp: Iter<Box<DiffChain>> = chain.iter();
                return temp;
            }
            diagonal[(MAX + k) as usize] = x;
            pretendents[(MAX + k) as usize] = chain.map(|a| &a);
            k = k + 2;
        }
    }
    panic!("oops");
}