tree_edit_distance/
lib.rs

1//! # Overview
2//!
3//! This crate provides an implementation of a recursive generalized version of the
4//! [Levenshtein distance][levenshtein] for arbitrary sequences that finds the smallest possible
5//! diff between two trees, according to a user-defined measure for the cost of inserting and
6//! removing nodes. The smallest possible diff is defined by the the lowest cost sequence of edits
7//! that transforms one tree into the other.
8//!
9//! [levenshtein]:  https://en.wikipedia.org/wiki/Levenshtein_distance
10//!
11//! # Example
12//!
13//! ```rust
14//! use tree_edit_distance::*;
15//! use std::mem::{discriminant, Discriminant};
16//! use std::iter::empty;
17//!
18//! enum Json {
19//!     Null,
20//!     Bool(bool),
21//!     Number(f64),
22//!     String(String),
23//!     Array(Vec<Json>),
24//!     Map(Vec<(String, Json)>),
25//! }
26//!
27//! impl Node for Json {
28//!     type Kind = Discriminant<Json>;
29//!     fn kind(&self) -> Self::Kind {
30//!         discriminant(self)
31//!     }
32//!
33//!     type Weight = u64;
34//!     fn weight(&self) -> Self::Weight {
35//!         1
36//!     }
37//! }
38//!
39//! impl Tree for Json {
40//!     type Children<'c> = Box<dyn Iterator<Item = &'c Self> + 'c>
41//!     where
42//!         Self: 'c;
43//!
44//!     fn children(&self) -> Self::Children<'_> {
45//!         match self {
46//!             Json::Array(a) => Box::new(a.iter()),
47//!             Json::Map(m) => Box::new(m.iter().map(|(_, v)| v)),
48//!             _ => Box::new(empty()),
49//!         }
50//!     }
51//! }
52//! #
53//! # impl From<serde_json::Value> for Json {
54//! #     fn from(obj: serde_json::Value) -> Self {
55//! #         use serde_json::Value::*;
56//! #         match obj {
57//! #             Null => Json::Null,
58//! #             Bool(b) => Json::Bool(b),
59//! #             Number(n) => Json::Number(n.as_i64().unwrap() as f64),
60//! #             String(s) => Json::String(s),
61//! #             Array(a) => Json::Array(a.into_iter().map(Into::into).collect()),
62//! #             Object(m) => Json::Map(
63//! #                 m.into_iter()
64//! #                     .map(|(k, v)| (k, v.into()))
65//! #                     .collect(),
66//! #             ),
67//! #         }
68//! #     }
69//! # }
70//!
71//! macro_rules! json {
72//!     ($( $tokens:tt )*) => {
73//!         // ...
74//! #         Json::from(::serde_json::json!({$($tokens)*}))
75//!     };
76//! }
77//!
78//! let john = json! {
79//!     "name": "John Doe",
80//!     "age": 43,
81//!     "phones": [
82//!         "+44 1234567",
83//!         "+44 2345678"
84//!     ]
85//! };
86//!
87//! let jane = json! {
88//!     "name": "Jane Doe",
89//!     "maiden name": "Smith",
90//!     "age": 40,
91//!     "phones": [
92//!         "+44 7654321",
93//!     ]
94//! };
95//!
96//! let (edits, cost) = diff(&john, &jane);
97//!
98//! assert_eq!(cost, 2);
99//!
100//! assert_eq!(&*edits, &[
101//!     Edit::Replace(Box::new([
102//!         Edit::Replace(Box::default()),      // "name"
103//!         Edit::Insert,                       // "maiden name"
104//!         Edit::Replace(Box::default()),      // "age"
105//!         Edit::Replace(Box::new([            // "phones"
106//!             Edit::Remove,
107//!             Edit::Replace(Box::default()),
108//!         ])),
109//!     ]))
110//! ]);
111//! ```
112
113mod diff;
114mod edit;
115mod tree;
116
117pub use diff::*;
118pub use edit::*;
119pub use tree::*;
120
121mod cost;
122mod fold;
123mod memoize;
124
125pub(crate) use cost::*;
126pub(crate) use fold::*;
127pub(crate) use memoize::*;
tree_edit_distance/lib.rs

tree_edit_distance/
lib.rs
