quantized_density_fields/qdf/mod.rs
1pub mod simulate;
2pub mod space;
3pub mod state;
4mod tests;
5
6pub use self::simulate::*;
7pub use self::space::*;
8pub use self::state::*;
9use error::*;
10use id::*;
11use petgraph::algo::astar;
12use petgraph::graphmap::UnGraphMap;
13use rayon::prelude::*;
14use std::collections::hash_set::Iter;
15use std::collections::{HashMap, HashSet};
16
17/// Short hand type alias for space graph.
18pub type SpaceGraph = UnGraphMap<ID, ()>;
19/// Short hand type alias for space map.
20pub type SpaceMap<S> = HashMap<ID, Space<S>>;
21
22/// Object that represents quantized density fields.
23///
24/// # Concept
25/// QDF does not exists in any space - it IS the space, it defines it,
26/// it describes it so there are no space coordinates and it is your responsibility to deliver it.
27/// In future releases this crate will have module for projecting QDF into Euclidean space
28/// and will have a satelite crate to easlyy traverse and visualize space.
29///
30/// To sample specified region you have to know some space ID and gather the rest of information
31/// based on it neighbors spaces.
32/// It gives the ability to cotrol space density at specified locations, which can be used
33/// for example to simulate space curvature based on gravity.
34#[derive(Debug)]
35pub struct QDF<S>
36where
37 S: State,
38{
39 id: ID,
40 graph: SpaceGraph,
41 spaces: SpaceMap<S>,
42 space_ids: HashSet<ID>,
43 dimensions: usize,
44}
45
46impl<S> QDF<S>
47where
48 S: State,
49{
50 /// Creates new QDF information universe.
51 ///
52 /// # Arguments
53 /// * `dimensions` - Number of dimensions space contains.
54 /// * `state` - State of space.
55 ///
56 /// # Returns
57 /// Tuple of new QDF object and space id.
58 ///
59 /// # Examples
60 /// ```
61 /// use quantized_density_fields::QDF;
62 ///
63 /// // Creates 2d space with `9` as root state.
64 /// let (qdf, root) = QDF::new(2, 9);
65 /// assert_eq!(*qdf.space(root).state(), 9);
66 /// ```
67 pub fn new(dimensions: usize, state: S) -> (Self, ID) {
68 let mut graph = UnGraphMap::new();
69 let mut spaces = HashMap::new();
70 let mut space_ids = HashSet::new();
71 let id = ID::new();
72 graph.add_node(id);
73 spaces.insert(id, Space::new(id, state));
74 space_ids.insert(id);
75 let qdf = Self {
76 id: ID::new(),
77 graph,
78 spaces,
79 space_ids,
80 dimensions,
81 };
82 (qdf, id)
83 }
84
85 /// Creates new QDF information universe and increase its levels of density.
86 ///
87 /// # Arguments
88 /// * `dimensions` - Number of dimensions which space contains.
89 /// * `state` - State of space.
90 /// * `levels` - Number of levels of uniform density.
91 ///
92 /// # Returns
93 /// Tuple of new QDF object and vector of space ids.
94 ///
95 /// # Examples
96 /// ```
97 /// use quantized_density_fields::{QDF, State};
98 ///
99 /// // Creates 2d space with `27` as root state and 2 levels of uniform density.
100 /// let (qdf, spaces) = QDF::with_levels(2, 27, 2);
101 /// assert_eq!(spaces.len(), (qdf.dimensions() + 1).pow(2));
102 /// assert_eq!(*qdf.space(spaces[0]).state(), 3);
103 /// assert_eq!(
104 /// State::merge(&qdf.spaces().map(|id| *qdf.space(*id).state()).collect::<Vec<i32>>()),
105 /// 27,
106 /// );
107 /// ```
108 pub fn with_levels(dimensions: usize, state: S, levels: usize) -> (Self, Vec<ID>) {
109 let (mut qdf, _) = Self::new(dimensions, state);
110 for _ in 0..levels {
111 let spaces = qdf.spaces().cloned().collect::<Vec<ID>>();
112 for id in spaces {
113 qdf.increase_space_density(id).unwrap();
114 }
115 }
116 let spaces = qdf.spaces().cloned().collect();
117 (qdf, spaces)
118 }
119
120 /// Creates new QDF information universe and increase its levels of density and state applied
121 /// to lowest space lavel.
122 ///
123 /// # Arguments
124 /// * `dimensions` - Number of dimensions which space contains.
125 /// * `state` - State of space at lowest level.
126 /// * `levels` - Number of levels of uniform density.
127 ///
128 /// # Returns
129 /// Tuple of new QDF object and vector of space ids.
130 ///
131 /// # Examples
132 /// ```
133 /// use quantized_density_fields::{QDF, State};
134 ///
135 /// // Creates 2d space with `3` as lowest level state and 2 levels of uniform density.
136 /// let (qdf, spaces) = QDF::with_levels_and_minimum_state(2, 3, 2);
137 /// assert_eq!(spaces.len(), (qdf.dimensions() + 1).pow(2));
138 /// assert_eq!(*qdf.space(spaces[0]).state(), 3);
139 /// assert_eq!(
140 /// State::merge(&qdf.spaces().map(|id| *qdf.space(*id).state()).collect::<Vec<i32>>()),
141 /// 27,
142 /// );
143 /// ```
144 #[inline]
145 pub fn with_levels_and_minimum_state(
146 dimensions: usize,
147 state: S,
148 levels: usize,
149 ) -> (Self, Vec<ID>) {
150 Self::with_levels(dimensions, state.super_state_at_level(dimensions, levels), levels)
151 }
152
153 /// Gets QDF id.
154 #[inline]
155 pub fn id(&self) -> ID {
156 self.id
157 }
158
159 /// Gets QDF dimensions number.
160 ///
161 /// # Returns
162 /// Number of dimensions (axes) space has.
163 ///
164 /// # Examples
165 /// ```
166 /// use quantized_density_fields::QDF;
167 ///
168 /// let (qdf, _) = QDF::new(2, 9);
169 /// assert_eq!(qdf.dimensions(), 2);
170 /// ```
171 #[inline]
172 pub fn dimensions(&self) -> usize {
173 self.dimensions
174 }
175
176 /// Tells if space with given id exists in QDF.
177 ///
178 /// # Arguments
179 /// * `id` - space id.
180 ///
181 /// # Returns
182 /// `true` if given space exists, `false` otherwise.
183 ///
184 /// # Examples
185 /// ```
186 /// use quantized_density_fields::QDF;
187 ///
188 /// let (qdf, root) = QDF::new(2, 9);
189 /// assert!(qdf.space_exists(root));
190 /// ```
191 #[inline]
192 pub fn space_exists(&self, id: ID) -> bool {
193 self.spaces.contains_key(&id)
194 }
195
196 /// Gets iterator over all spaces IDs.
197 ///
198 /// # Returns
199 /// Iterator over all space ids.
200 ///
201 /// # Examples
202 /// ```
203 /// use quantized_density_fields::{QDF, ID};
204 ///
205 /// let (mut qdf, root) = QDF::new(2, 9);
206 /// assert_eq!(qdf.spaces().count(), 1);
207 /// assert_eq!(*qdf.spaces().nth(0).unwrap(), root);
208 /// let (_, mut subs, _) = qdf.increase_space_density(root).unwrap();
209 /// subs.sort();
210 /// assert_eq!(qdf.spaces().count(), 3);
211 /// let mut spaces = qdf.spaces().cloned().collect::<Vec<ID>>();
212 /// spaces.sort();
213 /// assert_eq!(spaces, subs);
214 /// ```
215 #[inline]
216 pub fn spaces(&self) -> Iter<ID> {
217 self.space_ids.iter()
218 }
219
220 /// Try to get given space.
221 ///
222 /// # Arguments
223 /// * `id` - space id.
224 ///
225 /// # Returns
226 /// `Some` reference to given `Space` data or `None` if space does not exists.
227 ///
228 /// # Examples
229 /// ```
230 /// use quantized_density_fields::QDF;
231 ///
232 /// let (qdf, root) = QDF::new(2, 9);
233 /// if let Some(space) = qdf.try_get_space(root) {
234 /// assert_eq!(*space.state(), 9);
235 /// }
236 /// ```
237 #[inline]
238 pub fn try_get_space(&self, id: ID) -> Option<&Space<S>> {
239 self.spaces.get(&id)
240 }
241
242 /// Get given space or throw error if space does not exists.
243 ///
244 /// # Arguments
245 /// * `id` - space id.
246 ///
247 /// # Returns
248 /// `Ok` with reference to given `Space` data or `Err` if space does not exists.
249 ///
250 /// # Examples
251 /// ```
252 /// use quantized_density_fields::QDF;
253 ///
254 /// let (qdf, root) = QDF::new(2, 9);
255 /// if let Ok(space) = qdf.get_space(root) {
256 /// assert_eq!(*space.state(), 9);
257 /// }
258 /// ```
259 #[inline]
260 pub fn get_space(&self, id: ID) -> Result<&Space<S>> {
261 if let Some(space) = self.spaces.get(&id) {
262 Ok(space)
263 } else {
264 Err(QDFError::SpaceDoesNotExists(id))
265 }
266 }
267
268 /// Get given space or panic if space does not exists.
269 ///
270 /// # Arguments
271 /// * `id` - space id.
272 ///
273 /// # Returns
274 /// Reference to `Space` data.
275 ///
276 /// # Panics
277 /// When given space does not exists.
278 ///
279 /// # Examples
280 /// ```
281 /// use quantized_density_fields::QDF;
282 ///
283 /// let (qdf, root) = QDF::new(2, 9);
284 /// assert_eq!(*qdf.space(root).state(), 9);
285 /// ```
286 #[inline]
287 pub fn space(&self, id: ID) -> &Space<S> {
288 &self.spaces[&id]
289 }
290
291 /// Try to set given space state.
292 ///
293 /// # Arguments
294 /// * `id` - space id.
295 /// * `state` - state.
296 ///
297 /// # Returns
298 /// `true` if space exists and state was successfuly set, `false` otherwise.
299 ///
300 /// # Examples
301 /// ```
302 /// use quantized_density_fields::QDF;
303 ///
304 /// let (mut qdf, root) = QDF::new(2, 9);
305 /// assert!(qdf.try_set_space_state(root, 3));
306 /// ```
307 #[inline]
308 pub fn try_set_space_state(&mut self, id: ID, state: S) -> bool {
309 self.set_space_state(id, state).is_ok()
310 }
311
312 /// Set given space state or throw error if space does not exists.
313 ///
314 /// # Arguments
315 /// * `id` - space id.
316 /// * `state` - state.
317 ///
318 /// # Returns
319 /// `Ok` if space exists and state was successfuly set, `Err` otherwise.
320 ///
321 /// # Examples
322 /// ```
323 /// use quantized_density_fields::QDF;
324 ///
325 /// let (mut qdf, root) = QDF::new(2, 9);
326 /// assert!(qdf.set_space_state(root, 3).is_ok());
327 /// ```
328 #[inline]
329 pub fn set_space_state(&mut self, id: ID, state: S) -> Result<()> {
330 if self.space_exists(id) {
331 self.spaces.get_mut(&id).unwrap().apply_state(state);
332 Ok(())
333 } else {
334 Err(QDFError::SpaceDoesNotExists(id))
335 }
336 }
337
338 /// Get list of IDs of given space neighbors or throws error if space does not exists.
339 ///
340 /// # Arguments
341 /// * `id` - space id.
342 ///
343 /// # Returns
344 /// `Ok` with vector of space neighbors if space exists, `Err` otherwise.
345 ///
346 /// # Examples
347 /// ```
348 /// use quantized_density_fields::QDF;
349 ///
350 /// let (mut qdf, root) = QDF::new(2, 9);
351 /// let (_, subs, _) = qdf.increase_space_density(root).unwrap();
352 /// assert_eq!(qdf.find_space_neighbors(subs[0]).unwrap(), vec![subs[1], subs[2]]);
353 /// ```
354 #[inline]
355 pub fn find_space_neighbors(&self, id: ID) -> Result<Vec<ID>> {
356 if self.graph.contains_node(id) {
357 Ok(self.graph.neighbors(id).collect())
358 } else {
359 Err(QDFError::SpaceDoesNotExists(id))
360 }
361 }
362
363 /// Gets list of space IDs that defines shortest path between two spaces,
364 /// or throws error if space does not exists.
365 ///
366 /// # Arguments
367 /// * `from` - source space id.
368 /// * `to` - target space id.
369 ///
370 /// # Returns
371 /// `Ok` with space ids that builds shortest path between two points, `Err` if path cannot be
372 /// found or spaces does not exists.
373 ///
374 /// # Examples
375 /// ```
376 /// use quantized_density_fields::QDF;
377 ///
378 /// let (mut qdf, root) = QDF::new(2, 9);
379 /// let (_, subs, _) = qdf.increase_space_density(root).unwrap();
380 /// let (_, subs2, _) = qdf.increase_space_density(subs[0]).unwrap();
381 /// assert_eq!(qdf.find_path(subs2[0], subs[2]).unwrap(), vec![subs2[0], subs2[1], subs[2]]);
382 /// ```
383 pub fn find_path(&self, from: ID, to: ID) -> Result<Vec<ID>> {
384 if !self.space_exists(from) {
385 return Err(QDFError::SpaceDoesNotExists(from));
386 }
387 if !self.space_exists(to) {
388 return Err(QDFError::SpaceDoesNotExists(to));
389 }
390 if let Some((_, spaces)) = astar(&self.graph, from, |f| f == to, |_| 0, |_| 0) {
391 Ok(spaces)
392 } else {
393 Ok(vec![])
394 }
395 }
396
397 /// Increases given space density (subdivide space and rebind it properly to its neighbors),
398 /// and returns process information (source space id, subdivided space ids, connections pairs)
399 /// or throws error if space does not exists.
400 ///
401 /// # Arguments
402 /// * `id` - space id.
403 ///
404 /// # Returns
405 /// `Ok` with tuple of source space id, vector of subdivided space ids and vector of
406 /// connections pairs or `Err` if space does not exists.
407 ///
408 /// # Examples
409 /// ```
410 /// use quantized_density_fields::QDF;
411 ///
412 /// let (mut qdf, root) = QDF::new(2, 9);
413 /// let (_, subs, _) = qdf.increase_space_density(root).unwrap();
414 /// assert_eq!(subs.len(), 3);
415 /// ```
416 pub fn increase_space_density(&mut self, id: ID) -> Result<(ID, Vec<ID>, Vec<(ID, ID)>)> {
417 if self.space_exists(id) {
418 let space = self.spaces[&id].clone();
419 let subs = self.dimensions + 1;
420 let substates = space.state().subdivide(subs);
421 let spaces = substates
422 .iter()
423 .map(|substate| Space::new(ID::new(), substate.clone()))
424 .collect::<Vec<Space<S>>>();
425 for s in &spaces {
426 let id = s.id();
427 self.spaces.insert(id, s.clone());
428 self.graph.add_node(id);
429 self.space_ids.insert(id);
430 }
431 for a in &spaces {
432 let aid = a.id();
433 for b in &spaces {
434 let bid = b.id();
435 if aid != bid {
436 self.graph.add_edge(aid, bid, ());
437 }
438 }
439 }
440 let neighbors = self.graph.neighbors(id).collect::<Vec<ID>>();
441 let pairs = neighbors
442 .iter()
443 .enumerate()
444 .map(|(i, n)| {
445 let t = spaces[i].id();
446 self.graph.remove_edge(*n, id);
447 self.graph.add_edge(*n, t, ());
448 (*n, t)
449 })
450 .collect::<Vec<(ID, ID)>>();
451 self.space_ids.remove(&id);
452 self.spaces.remove(&id);
453 let space_ids = spaces.iter().map(|s| s.id()).collect::<Vec<ID>>();
454 Ok((id, space_ids, pairs))
455 } else {
456 Err(QDFError::SpaceDoesNotExists(id))
457 }
458 }
459
460 /// Decreases given space density (merge space children and rebind them properly to theirs
461 /// neighbors if space has 1 level of subdivision, otherwise perform this operation on its
462 /// subspaces), and returns process information (source space ids, merged space id) or throws
463 /// error if space does not exists.
464 ///
465 /// # Arguments
466 /// * `id` - space id.
467 ///
468 /// # Returns
469 /// `Ok` with `Some` tuple of vector of merged space ids and created space id, or `Ok` with
470 /// `None` if space cannot be merged or `Err` if given space does not exists.
471 ///
472 /// # Examples
473 /// ```
474 /// use quantized_density_fields::QDF;
475 ///
476 /// let (mut qdf, root) = QDF::new(2, 9);
477 /// let (_, subs, _) = qdf.increase_space_density(root).unwrap();
478 /// assert_eq!(subs.len(), 3);
479 /// let (_, root) = qdf.decrease_space_density(subs[0]).unwrap().unwrap();
480 /// assert_eq!(qdf.spaces().len(), 1);
481 /// assert_eq!(*qdf.spaces().nth(0).unwrap(), root);
482 /// ```
483 pub fn decrease_space_density(&mut self, id: ID) -> Result<Option<(Vec<ID>, ID)>> {
484 if self.space_exists(id) {
485 let neighbor = self.graph.neighbors(id).collect::<Vec<ID>>();
486 let mut connected = neighbor
487 .iter()
488 .filter(|a| {
489 neighbor
490 .iter()
491 .any(|b| **a != *b && self.graph.edge_weight(**a, *b).is_some())
492 }).cloned()
493 .collect::<Vec<ID>>();
494 if connected.len() != self.dimensions {
495 Ok(None)
496 } else {
497 connected.push(id);
498 let states = connected
499 .iter()
500 .map(|i| self.spaces[&i].state())
501 .cloned()
502 .collect::<Vec<S>>();
503 let id = ID::new();
504 self.graph.add_node(id);
505 self.space_ids.insert(id);
506 self.spaces
507 .insert(id, Space::new(id, State::merge(&states)));
508 for i in &connected {
509 let outsiders = self
510 .graph
511 .neighbors(*i)
512 .filter(|n| !connected.contains(n))
513 .collect::<Vec<ID>>();
514 for n in outsiders {
515 self.graph.add_edge(id, n, ());
516 }
517 }
518 let space_ids = connected
519 .iter()
520 .map(|i| {
521 self.graph.remove_node(*i);
522 self.spaces.remove(i);
523 self.space_ids.remove(i);
524 *i
525 })
526 .collect::<Vec<ID>>();
527 Ok(Some((space_ids, id)))
528 }
529 } else {
530 Err(QDFError::SpaceDoesNotExists(id))
531 }
532 }
533
534 /// Performs simulation step (go through all platonic spaces and modifies its states based on
535 /// neighbor states). Actual state simulation is performed by your struct that implements
536 /// `Simulation` trait.
537 pub fn simulation_step<M>(&mut self)
538 where
539 M: Simulate<S>,
540 {
541 let states = self.simulate_states::<M>();
542 for (id, state) in states {
543 self.spaces.get_mut(&id).unwrap().apply_state(state);
544 }
545 }
546
547 /// Does the same as `simulation_step()` but in parallel manner (it may or may not increase
548 /// simulation performance if simulation is very complex).
549 pub fn simulation_step_parallel<M>(&mut self)
550 where
551 M: Simulate<S>,
552 {
553 let states = self.simulate_states_parallel::<M>();
554 for (id, state) in states {
555 self.spaces.get_mut(&id).unwrap().apply_state(state);
556 }
557 }
558
559 /// Performs simulation on QDF like `simulation_step()` but instead of applying results to QDF,
560 /// it returns simulated platonic space states along with their space ID.
561 ///
562 /// # Returns
563 /// Vector of tuples of id and its updated space that were simulated.
564 pub fn simulate_states<M>(&self) -> Vec<(ID, S)>
565 where
566 M: Simulate<S>,
567 {
568 self.space_ids
569 .iter()
570 .map(|id| {
571 let neighbor_states = self
572 .graph
573 .neighbors(*id)
574 .map(|i| self.spaces[&i].state())
575 .collect::<Vec<&S>>();
576 (*id, M::simulate(self.spaces[id].state(), &neighbor_states))
577 }).collect()
578 }
579
580 /// Performs simulation on QDF like `simulation_step_parallel()` but instead of applying
581 /// results to QDF, it returns simulated platonic space states along with their space ID.
582 ///
583 /// # Returns
584 /// Vector of tuples of id and its updated space that were simulated.
585 pub fn simulate_states_parallel<M>(&self) -> Vec<(ID, S)>
586 where
587 M: Simulate<S>,
588 {
589 let spaces = &self.spaces;
590 let space_ids = &self.space_ids;
591 let graph = &self.graph;
592 space_ids
593 .par_iter()
594 .map(|id| {
595 let neighbor_states = graph
596 .neighbors(*id)
597 .map(|i| spaces[&i].state())
598 .collect::<Vec<&S>>();
599 (*id, M::simulate(spaces[id].state(), &neighbor_states))
600 }).collect()
601 }
602}