acacia 0.2.0

A spatial partitioning and tree library.
Documentation 
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

//! Abstraction of spatial partitioning schemes

pub use partition::interval::Interval;
pub use partition::boxes::{Box2, Box3};
pub use partition::ncube::Ncube;
pub use partition::unitquad::UnitQuad;

#[cfg(any(test, feature = "arbitrary"))]
use quickcheck::TestResult;


/// A type that can be subdivided
pub trait Subdivide: Sized {
    /// Subdivide into smaller partitions
    fn subdivide(&self) -> Vec<Self>;
}


/// A type describing a partition of some space
///
/// In addition to this trait signature an implementation is required to satisfy
/// `prop_is_total`.
pub trait Partition<T>: Subdivide + Sized {
    /// Does the partition contain an element?
    fn contains(&self, elem: &T) -> bool;

    /// Dispatch an element to the correct subpartition
    ///
    /// The default implementation works, if the totality proposition is
    /// fulfilled. However, note that its performance is not optimal, as it
    /// checks for all subpartitions whether they contain the element, until one
    /// is found that does.
    fn dispatch(&self, elem: &T) -> usize {
        for (i, part) in self.subdivide().iter().enumerate() {
            if part.contains(elem) {
                return i;
            }
        }
        panic!("partition dispatch impossible");
    }
}


/// Totality proposition (contained)
///
/// Any element contained in the partition will be contained in exactly one of
/// its subpartitions.
#[cfg(any(test, feature = "arbitrary"))]
pub fn prop_is_total_elem<P: Partition<T>, T>(partition: P, elem: T) -> TestResult {
    if partition.contains(&elem) {
        TestResult::from_bool(
            partition.subdivide().iter()
                .filter(|sub| sub.contains(&elem)).count()
            == 1
        )
    }
    else {
        TestResult::discard()
    }
}


/// Totality proposition (not contained)
///
/// If a partition does not contain an element, none of its subpartitions
/// contain it either.
#[cfg(any(test, feature = "arbitrary"))]
pub fn prop_is_total_non_elem<P: Partition<T>, T>(partition: P, elem: T) -> TestResult {
    if partition.contains(&elem) {
        TestResult::discard()
    }
    else {
        TestResult::from_bool(
            partition.subdivide().iter()
                .all(|sub| !sub.contains(&elem))
        )
    }
}


/// Consistency of dispatch mechanism
///
/// An element contained in the partition must be dispatched consistently, i.e.
/// the subpartition to which it is dispatched must contain it.
#[cfg(any(test, feature = "arbitrary"))]
pub fn prop_consistent_dispatch<P: Partition<T>, T>(partition: P, elem: T) -> TestResult {
    if partition.contains(&elem) {
        TestResult::from_bool(partition.subdivide()[partition.dispatch(&elem)].contains(&elem))
    }
    else {
        TestResult::discard()
    }
}


#[cfg(test)]
macro_rules! partition_quickcheck (
    ($testfn: ident, $p: ty, $t: ty) => (
        mod $testfn {
            use $crate::partition::{
                prop_is_total_elem, prop_is_total_non_elem,
                prop_consistent_dispatch
            };
            use quickcheck::{quickcheck, TestResult};
            use super::*;

            #[test]
            fn is_total_elem() {
                quickcheck(prop_is_total_elem::<$p, $t> as fn($p, $t) -> TestResult);
            }

            #[test]
            fn is_total_non_elem() {
                quickcheck(prop_is_total_non_elem::<$p, $t> as fn($p, $t) -> TestResult);
            }

            #[test]
            fn consistent_dispatch() {
                quickcheck(prop_consistent_dispatch::<$p, $t> as fn($p, $t) -> TestResult);
            }
        }
    )
);


/// The notion of a mid point between two inputs
pub trait Mid {
    /// Return the mid between this point and another
    fn mid(&self, other: &Self) -> Self;
}

impl Mid for f64 {
    fn mid(&self, other: &f64) -> f64 { (*self + *other) / 2.0 }
}

impl Mid for f32 {
    fn mid(&self, other: &f32) -> f32 { (*self + *other) / 2.0 }
}


mod interval;
mod boxes;
mod ncube;
mod unitquad;
pub mod cubemap;