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