pcp/variable/memory/
mod.rs

1// Copyright 2016 Pierre Talbot (IRCAM)
2
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6
7//     http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15pub mod copy_memory;
16pub mod concept;
17pub mod trail_memory;
18pub mod trail;
19pub mod ops;
20
21pub use variable::memory::copy_memory::*;
22pub use variable::memory::trail_memory::*;
23pub use variable::memory::trail::*;
24
25pub type SingleTrailMemory<Dom> = TrailMemory<SingleValueTrail<Dom>, Dom>;
26pub type TimestampTrailMemory<Dom> = TrailMemory<TimestampTrail<Dom>, Dom>;
27
28#[cfg(test)]
29mod test {
30  use super::*;
31  use kernel::*;
32  use variable::concept::*;
33  use interval::interval::*;
34  use gcollections::ops::*;
35  use gcollections::*;
36  use std::ops::{Deref, DerefMut, Range};
37
38  type Domain = Interval<i32>;
39
40  struct Test {
41    pub tree_depth: usize,
42    pub memory_config: String,
43    pub queue_config: String,
44    tree: Tree
45  }
46
47  impl Test {
48    pub fn new(depth: usize, shape: &TreeShape) -> Self {
49      Test {
50        tree_depth: depth,
51        memory_config: String::new(),
52        queue_config: String::new(),
53        tree: Tree::new(depth, shape)
54      }
55    }
56
57    pub fn assert_node_equality(&self, real: Domain, expected: Domain, from: Domain) {
58      if real != expected {
59        println!("\nRestoration from `{}` to `{}` failed.",
60          from, expected);
61        println!("We obtained the node `{}` instead of the expected `{}`.",
62          real, expected);
63        println!("Configuration:");
64        println!("  Depth of the tree: {}", self.tree_depth);
65        println!("  Memory: {}", self.memory_config);
66        println!("  Queue (exploration): {}\n", self.queue_config);
67        assert!(false);
68      }
69    }
70  }
71
72  // Used for describing a tree more easily. It is later transformed to `Tree` that used a index-based representation.
73  #[derive(Clone)]
74  enum TreeShape {
75    Node(Range<i32>, Vec<TreeShape>),
76    Leaf(Range<i32>)
77  }
78
79  fn tree_depth_4() -> TreeShape {
80    use self::TreeShape::*;
81    //                         [1..10]
82    //            [1..5]                     [6..10]
83    //     [1..2]       [3..5]        [6..7]        [8..10]
84    // [1..1] [2..2] [3..3] [4..5] [6..6] [7..7] [8..8] [9..10]
85    //                   [4..4] [5..5]               [9..9] [10..10]
86    Node(1..10, vec![
87      Node(1..5, vec![
88        Node(1..2, vec![
89          Leaf(1..1), Leaf(2..2)]),
90        Node(3..5, vec![
91          Leaf(3..3),
92          Node(4..5, vec![
93            Leaf(4..4), Leaf(5..5)])])]),
94      Node(6..10, vec![
95        Node(6..7, vec![
96          Leaf(6..6), Leaf(7..7)]),
97        Node(8..10, vec![
98          Leaf(8..8),
99          Node(9..10, vec![
100            Leaf(9..9), Leaf(10..10)])])])])
101  }
102
103  #[test]
104  fn restoration_strategies() {
105    configure_depth();
106  }
107
108  fn configure_depth() {
109    let tree_shape = tree_depth_4();
110    for depth in 2..3 {//0..5 {
111      let mut test = Test::new(depth, &tree_shape);
112      configure_memory(&mut test);
113    }
114  }
115
116  fn configure_memory(test: &mut Test)
117  {
118    type MCopy = CopyMemory<Domain>;
119    type MSingleTrail = SingleTrailMemory<Domain>;
120    type MTimestampTrail = TimestampTrailMemory<Domain>;
121
122    test.memory_config = String::from("CopyMemory");
123    configure_queue::<MCopy>(test);
124    test.memory_config = String::from("TrailMemory with SingleValueTrail");
125    configure_dfs_queue::<MSingleTrail>(test);
126    test.memory_config = String::from("TrailMemory with TimestampTrail");
127    configure_dfs_queue::<MTimestampTrail>(test);
128  }
129
130  fn configure_queue<Mem>(test: &mut Test) where
131    Mem: MemoryConcept,
132    Mem: Collection<Item=Domain>
133  {
134    configure_dfs_queue::<Mem>(test);
135    configure_bfs_queue::<Mem>(test);
136  }
137
138  fn configure_dfs_queue<Mem>(test: &mut Test) where
139    Mem: MemoryConcept,
140    Mem: Collection<Item=Domain>
141  {
142    type Stack<Label> = VectorStack<QueueItem<Label>>;
143    test.queue_config = String::from("VectorStack (Depth-first search)");
144    test_restoration::<Mem, Stack<_>>(test);
145  }
146
147  fn configure_bfs_queue<Mem>(test: &mut Test) where
148    Mem: MemoryConcept,
149    Mem: Collection<Item=Domain>
150  {
151    type Queue<Label> = DequeFrontBackQueue<QueueItem<Label>>;
152    test.queue_config = String::from("DequeFrontBackQueue (Breadth-first search)");
153    test_restoration::<Mem, Queue<_>>(test);
154  }
155
156  // Given `(parent, child, label)`, `parent` is the node index associated to the label to restore (for comparing real and expected values) and `child` is the index of the node to apply in the memory after restoration.
157  type QueueItem<Label> = (usize, usize, Label);
158
159  // We simulate the updates in the memory `M` according to the exploration `Q` of a static tree (in `test.tree`).
160  // Since the tree is already fully built, we can test the values when restoring a node.
161  fn test_restoration<M, Q>(test: &Test) where
162   M: MemoryConcept,
163   M: Collection<Item=Domain>,
164   Q: Multiset,
165   Q: Collection<Item=QueueItem<
166     <M::FrozenState as Snapshot>::Label>>,
167  {
168    let tree = &test.tree;
169    let mut queue = Q::empty();
170    let mut mem = M::empty();
171    mem.push(tree.root_value());
172    let mut current = tree.root;
173    let mut frozen = mem.freeze();
174    for child in tree.children(tree.root) {
175      println!("test_restoration: label");
176      queue.insert((tree.root, child, frozen.label()));
177    }
178    while let Some((parent, child, label)) = queue.extract() {
179      mem = frozen.restore(label);
180      println!("test_restoration: restore to {}", mem[0]);
181      test.assert_node_equality(mem[0], tree[parent].value, tree[current].value);
182      println!("replace: {} with {}", mem[0], tree[child].value);
183      mem.replace(0, tree[child].value);
184      current = child;
185      frozen = mem.freeze();
186      for grandchild in tree.children(child) {
187        println!("test_restoration: label");
188        queue.insert((child, grandchild, frozen.label()));
189      }
190    }
191  }
192
193  #[derive(Clone)]
194  struct Node {
195    value: Domain,
196    children: Vec<usize>
197  }
198
199  impl Node {
200    pub fn new(value: Domain, children: Vec<usize>) -> Self {
201      Node {
202        value: value,
203        children: children
204      }
205    }
206  }
207
208  #[derive(Clone)]
209  struct Tree {
210    pub root: usize,
211    nodes: Vec<Node>
212  }
213
214  impl Tree {
215    pub fn new(depth: usize, shape: &TreeShape) -> Self {
216      let mut tree = Tree {
217        root: 0,
218        nodes: vec![]
219      };
220      tree.root = tree.from_shape(depth, &shape);
221      tree
222    }
223
224    pub fn root_value(&self) -> Domain {
225      self.nodes[self.root].value
226    }
227
228    pub fn children(&self, node: usize) -> Vec<usize> {
229      self[node].children.clone()
230    }
231
232    fn from_shape(&mut self, depth: usize, shape: &TreeShape) -> usize {
233      use self::TreeShape::*;
234      match shape {
235        &Node(ref value, ref children) if depth > 0 => {
236          let children = children.iter()
237            .map(|child| self.from_shape(depth-1, child))
238            .collect();
239          self.alloc(value.clone(), children)
240        }
241        &Node(ref value, _)
242      | &Leaf(ref value) => {
243          self.leaf(value.clone())
244        }
245      }
246    }
247
248    fn alloc(&mut self, value: Range<i32>, children: Vec<usize>) -> usize {
249      let node = Node::new((value.start, value.end).to_interval(), children);
250      self.push(node);
251      self.len() - 1
252    }
253
254    fn leaf(&mut self, value: Range<i32>) -> usize {
255      self.alloc(value, vec![])
256    }
257  }
258
259  impl Deref for Tree
260  {
261    type Target = Vec<Node>;
262    fn deref(&self) -> &Self::Target {
263      &self.nodes
264    }
265  }
266
267  impl DerefMut for Tree
268  {
269    fn deref_mut(&mut self) -> &mut Self::Target {
270      &mut self.nodes
271    }
272  }
273}
pcp/variable/memory/mod.rs

pcp/variable/memory/
mod.rs
