collection 0.1.1

Deterministic, copy-on-write balanced search trees
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

use seahash::SeaHasher;

use std::marker::PhantomData;
use std::hash::{Hash, Hasher};

use std::borrow::Cow;

use Val;
use meta::{Meta, SubMeta, Select, Selection};

use meta::checksum::CheckSum;

pub trait Keyed {
    type Key: Val + Ord;
    type Value: Clone;

    fn key(&self) -> &Self::Key;
    fn value(&self) -> &Self::Value;
    fn value_mut(&mut self) -> &mut Self::Value;
}

#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Key<K>(K);
#[derive(Clone, PartialEq)]
pub struct KeySum<T>(T);
#[derive(Clone, PartialEq)]
pub struct ValSum<T>(T);

impl<T> KeySum<T> {
    fn inner(&self) -> &T {
        &self.0
    }
}

impl<T> ValSum<T> {
    fn inner(&self) -> &T {
        &self.0
    }
}

impl<K> Key<K> {
    pub fn new(key: K) -> Self {
        Key(key)
    }
}

impl<T> Meta<T> for Key<T::Key>
    where T: Val + Keyed
{
    fn from_t(t: &T) -> Self {
        Key(t.key().clone())
    }
    fn merge(&mut self, other: &Self, _t: PhantomData<T>) {
        if self.0 < other.0 {
            self.0 = other.0.clone()
        }
    }
}

impl<T> Select<T> for Key<T::Key>
    where T: Val + Keyed
{
    fn select(&mut self, other: Cow<Self>) -> Selection {
        if self.0 == other.0 {
            Selection::Hit
        } else if self.0 < other.0 {
            Selection::Between
        } else {
            Selection::Miss
        }
    }
}

impl<T> Meta<T> for KeySum<u64>
    where T: Val + Keyed,
          T::Key: Hash
{
    fn from_t(t: &T) -> Self {
        let mut hasher = SeaHasher::new();
        t.key().hash(&mut hasher);
        KeySum(hasher.finish())
    }
    fn merge(&mut self, other: &Self, _t: PhantomData<T>) {
        let a = self.0;
        let b = other.0;
        self.0 = (a ^ b).wrapping_add(a);
    }
}

impl<T> Meta<T> for ValSum<u64>
    where T: Val + Keyed,
          T::Value: Hash
{
    fn from_t(t: &T) -> Self {
        let mut hasher = SeaHasher::new();
        t.value().hash(&mut hasher);
        ValSum(hasher.finish())
    }

    fn merge(&mut self, other: &Self, _t: PhantomData<T>) {
        let a = self.0;
        let b = other.0;
        self.0 = (a ^ b).wrapping_add(a);
    }
}

impl<M> SubMeta<CheckSum<u64>> for M
    where M: SubMeta<KeySum<u64>> + SubMeta<ValSum<u64>>
{
    fn submeta(&self) -> Cow<CheckSum<u64>> {
        let k: Cow<KeySum<u64>> = self.submeta();
        let v: Cow<ValSum<u64>> = self.submeta();

        let check = CheckSum::new(k.inner() ^ v.inner());
        Cow::Owned(check)
    }
}