uqa-core 0.4.0

Document sets, finite-support relations, posting storage, and value types for UQA
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

//
// Unified Query Algebra
//
// Copyright (c) 2023-2026 Cognica, Inc.
//

//! Immutable ordered roots share entries and unchanged subtrees under one allowance.

#[cfg(test)]
mod tests;
mod tree;

use std::{borrow::Borrow, cmp::Ordering, ops::Bound, sync::Arc};

use super::{Budgeted, MemoryBudget, MemoryError, MAX_HEIGHT};

type Entry<K, V> = Arc<Budgeted<(K, V)>>;
type SharedNode<K, V> = Arc<Budgeted<Node<K, V>>>;
type Link<K, V> = Option<SharedNode<K, V>>;

struct Node<K, V> {
    entry: Entry<K, V>,
    left: Link<K, V>,
    right: Link<K, V>,
    height: u8,
}

/// A persistent ordered map with logarithmic lookup and insertion. Cloning shares a root without copying entries or allocating. Updates reserve the complete insertion before mutation, reuse unique nodes and copy shared paths; unchanged entries and subtrees keep their original reservations until their last root is dropped. Keys and values retain their separately owned payloads.
pub struct BudgetedSharedMap<K, V> {
    root: Link<K, V>,
    len: usize,
    memory: MemoryBudget,
}

impl<K, V> Clone for BudgetedSharedMap<K, V> {
    fn clone(&self) -> Self {
        Self {
            root: self.root.clone(),
            len: self.len,
            memory: self.memory.clone(),
        }
    }
}

impl<K, V> BudgetedSharedMap<K, V> {
    pub fn new(memory: &MemoryBudget) -> Self {
        Self {
            root: None,
            len: 0,
            memory: memory.clone(),
        }
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn budget(&self) -> &MemoryBudget {
        &self.memory
    }

    pub fn iter(&self) -> BudgetedSharedMapIter<'_, K, V> {
        let mut iter = BudgetedSharedMapIter::empty();
        iter.push_left(self.root.as_ref().map(|node| &***node));
        iter
    }
}

impl<K: Ord, V> BudgetedSharedMap<K, V> {
    pub fn get<Q: Ord + ?Sized>(&self, key: &Q) -> Option<&V>
    where
        K: Borrow<Q>,
    {
        let mut link = &self.root;
        while let Some(node) = link {
            match key.cmp(node.entry.0.borrow()) {
                Ordering::Less => link = &node.left,
                Ordering::Greater => link = &node.right,
                Ordering::Equal => return Some(&node.entry.1),
            }
        }
        None
    }

    /// Return a new root containing the supplied key and value, leaving this root unchanged even if reservation fails. Matching keys are replaced together with their values; neither type needs to implement `Clone`.
    pub fn with_insert(&self, key: K, value: V) -> Result<Self, MemoryError> {
        let mut candidate = self.clone();
        candidate.try_insert(key, value)?;
        Ok(candidate)
    }

    /// Reserve the complete insertion before changing this root, reusing unique nodes and copying only shared paths. Reservation failure preserves this root; existing clones remain unchanged. Matching keys and values are replaced together without requiring `Clone`.
    pub fn try_insert(&mut self, key: K, value: V) -> Result<(), MemoryError> {
        let added = tree::insert(&mut self.root, key, value, &self.memory)?;
        self.len += usize::from(added);
        Ok(())
    }

    /// Visit keys in order, seeking the lower bound without traversing earlier entries or allocating a traversal buffer.
    pub fn range_from<Q: Ord + ?Sized>(&self, start: Bound<&Q>) -> BudgetedSharedMapIter<'_, K, V>
    where
        K: Borrow<Q>,
    {
        let mut iter = BudgetedSharedMapIter::empty();
        let mut link = &self.root;
        while let Some(node) = link {
            let included = match start {
                Bound::Unbounded => true,
                Bound::Included(key) => node.entry.0.borrow() >= key,
                Bound::Excluded(key) => node.entry.0.borrow() > key,
            };
            if included {
                iter.stack[iter.depth] = Some(node);
                iter.depth += 1;
                link = &node.left;
            } else {
                link = &node.right;
            }
        }
        iter
    }
}

pub struct BudgetedSharedMapIter<'a, K, V> {
    stack: [Option<&'a Node<K, V>>; MAX_HEIGHT],
    depth: usize,
}

impl<'a, K, V> BudgetedSharedMapIter<'a, K, V> {
    fn empty() -> Self {
        Self {
            stack: [None; MAX_HEIGHT],
            depth: 0,
        }
    }

    fn push_left(&mut self, mut node: Option<&'a Node<K, V>>) {
        while let Some(current) = node {
            self.stack[self.depth] = Some(current);
            self.depth += 1;
            node = current.left.as_ref().map(|node| &***node);
        }
    }
}

impl<'a, K, V> Iterator for BudgetedSharedMapIter<'a, K, V> {
    type Item = (&'a K, &'a V);

    fn next(&mut self) -> Option<Self::Item> {
        self.depth = self.depth.checked_sub(1)?;
        let node = self.stack[self.depth].take().expect("retained map node");
        self.push_left(node.right.as_ref().map(|node| &***node));
        Some((&node.entry.0, &node.entry.1))
    }
}

impl<K, V> std::iter::FusedIterator for BudgetedSharedMapIter<'_, K, V> {}

impl<'a, K, V> IntoIterator for &'a BudgetedSharedMap<K, V> {
    type Item = (&'a K, &'a V);
    type IntoIter = BudgetedSharedMapIter<'a, K, V>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}