splaylist 0.1.0

A self-balancing skip list: an ordered map/set whose node heights adapt to the access pattern, so frequently-used keys become cheaper to reach.
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

//! `serde` support for [`SplayMap`] and [`SplaySet`], gated behind the
//! `serde` feature.
//!
//! A map serializes as a serde map and a set as a serde sequence. Tower
//! heights and access counters are not part of the serialized form; they are
//! reconstructed as entries are inserted on deserialization.

use core::fmt;
use core::marker::PhantomData;

use serde::de::{MapAccess, SeqAccess, Visitor};
use serde::ser::{SerializeMap, SerializeSeq};
use serde::{Deserialize, Deserializer, Serialize, Serializer};

use crate::{SplayMap, SplaySet};

impl<K, V> Serialize for SplayMap<K, V>
where
    K: Ord + Serialize,
    V: Serialize,
{
    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        let mut map = serializer.serialize_map(Some(self.len()))?;
        for (k, v) in self {
            map.serialize_entry(k, v)?;
        }
        map.end()
    }
}

struct MapVisitor<K, V>(PhantomData<fn() -> (K, V)>);

impl<'de, K, V> Visitor<'de> for MapVisitor<K, V>
where
    K: Ord + Deserialize<'de>,
    V: Deserialize<'de>,
{
    type Value = SplayMap<K, V>;

    fn expecting(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("a map of key/value pairs")
    }

    fn visit_map<A: MapAccess<'de>>(self, mut access: A) -> Result<Self::Value, A::Error> {
        let mut out = SplayMap::with_capacity(access.size_hint().unwrap_or(0));
        while let Some((k, v)) = access.next_entry()? {
            out.insert(k, v);
        }
        Ok(out)
    }
}

impl<'de, K, V> Deserialize<'de> for SplayMap<K, V>
where
    K: Ord + Deserialize<'de>,
    V: Deserialize<'de>,
{
    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        deserializer.deserialize_map(MapVisitor(PhantomData))
    }
}

impl<T> Serialize for SplaySet<T>
where
    T: Ord + Serialize,
{
    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        let mut seq = serializer.serialize_seq(Some(self.len()))?;
        for v in self {
            seq.serialize_element(v)?;
        }
        seq.end()
    }
}

struct SetVisitor<T>(PhantomData<fn() -> T>);

impl<'de, T> Visitor<'de> for SetVisitor<T>
where
    T: Ord + Deserialize<'de>,
{
    type Value = SplaySet<T>;

    fn expecting(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.write_str("a sequence of values")
    }

    fn visit_seq<A: SeqAccess<'de>>(self, mut access: A) -> Result<Self::Value, A::Error> {
        let mut out = SplaySet::with_capacity(access.size_hint().unwrap_or(0));
        while let Some(v) = access.next_element()? {
            out.insert(v);
        }
        Ok(out)
    }
}

impl<'de, T> Deserialize<'de> for SplaySet<T>
where
    T: Ord + Deserialize<'de>,
{
    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        deserializer.deserialize_seq(SetVisitor(PhantomData))
    }
}