leptos_sync_core/crdt/tree/
remove_wins.rs

1//! Remove-Wins Tree CRDT implementation
2
3use super::super::{CRDT, Mergeable, ReplicaId};
4use super::{config::{TreeConfig, TreeStrategy}, error::TreeError, types::{NodeId, TreeNode}};
5use serde::{Deserialize, Serialize};
6use std::collections::HashMap;
7
8/// Remove-Wins Tree CRDT implementation
9/// 
10/// This implementation completely removes deleted nodes.
11/// It's more memory-efficient but nodes cannot be recovered.
12#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
13pub struct RemoveWinsTree<T> {
14    /// Configuration
15    config: TreeConfig,
16    /// Nodes in the tree
17    nodes: HashMap<NodeId, TreeNode<T>>,
18    /// Replica ID for this instance
19    replica: ReplicaId,
20}
21
22impl<T: Clone + PartialEq + Eq + Send + Sync> RemoveWinsTree<T> {
23    /// Create a new Remove-Wins tree
24    pub fn new(replica: ReplicaId) -> Self {
25        Self {
26            config: TreeConfig {
27                strategy: TreeStrategy::RemoveWins,
28                preserve_deleted: false,
29                max_depth: None,
30                max_children: None,
31            },
32            nodes: HashMap::new(),
33            replica,
34        }
35    }
36
37    /// Create with custom configuration
38    pub fn with_config(replica: ReplicaId, config: TreeConfig) -> Self {
39        Self {
40            config,
41            nodes: HashMap::new(),
42            replica,
43        }
44    }
45
46    /// Add a root node to the tree
47    pub fn add_root(&mut self, value: T, timestamp: u64) -> NodeId {
48        let node = TreeNode::new(value, self.replica, timestamp);
49        let id = node.id.clone();
50        self.nodes.insert(id.clone(), node);
51        id
52    }
53
54    /// Add a child node
55    pub fn add_child(&mut self, parent_id: &NodeId, value: T, timestamp: u64) -> Result<NodeId, TreeError> {
56        if !self.nodes.contains_key(parent_id) {
57            return Err(TreeError::new("Parent node not found".to_string()));
58        }
59
60        let node = TreeNode::new_child(value, self.replica, timestamp, parent_id.clone());
61        let id = node.id.clone();
62        
63        // Add the child node
64        self.nodes.insert(id.clone(), node);
65        
66        // Update parent's children list
67        if let Some(parent) = self.nodes.get_mut(parent_id) {
68            parent.add_child(id.clone());
69        }
70        
71        Ok(id)
72    }
73
74    /// Update an existing node
75    pub fn update(&mut self, id: &NodeId, value: T, timestamp: u64) -> Result<(), TreeError> {
76        if let Some(node) = self.nodes.get_mut(id) {
77            node.value = value;
78            node.mark_modified(self.replica, timestamp);
79            Ok(())
80        } else {
81            Err(TreeError::new("Node not found".to_string()))
82        }
83    }
84
85    /// Remove a node completely
86    pub fn remove(&mut self, id: &NodeId) -> Result<(), TreeError> {
87        // Get the parent ID first
88        let parent_id = self.nodes.get(id).and_then(|node| node.parent.clone());
89        
90        // Remove from parent's children list
91        if let Some(parent_id) = parent_id {
92            if let Some(parent) = self.nodes.get_mut(&parent_id) {
93                parent.remove_child(id);
94            }
95        }
96        
97        // Remove the node
98        if self.nodes.remove(id).is_some() {
99            Ok(())
100        } else {
101            Err(TreeError::new("Node not found".to_string()))
102        }
103    }
104
105    /// Move a node to a new parent
106    pub fn move_node(&mut self, id: &NodeId, new_parent_id: &NodeId) -> Result<(), TreeError> {
107        if !self.nodes.contains_key(id) || !self.nodes.contains_key(new_parent_id) {
108            return Err(TreeError::new("Node not found".to_string()));
109        }
110
111        // Get the old parent ID first
112        let old_parent_id = self.nodes.get(id).and_then(|node| node.parent.clone());
113        
114        // Remove from old parent
115        if let Some(old_parent_id) = old_parent_id {
116            if let Some(old_parent) = self.nodes.get_mut(&old_parent_id) {
117                old_parent.remove_child(id);
118            }
119        }
120        
121        // Update the node's parent reference
122        if let Some(node) = self.nodes.get_mut(id) {
123            node.parent = Some(new_parent_id.clone());
124        }
125        
126        // Add to new parent
127        if let Some(new_parent) = self.nodes.get_mut(new_parent_id) {
128            new_parent.add_child(id.clone());
129        }
130        
131        Ok(())
132    }
133
134    /// Get a node by ID
135    pub fn get(&self, id: &NodeId) -> Option<&TreeNode<T>> {
136        self.nodes.get(id)
137    }
138
139    /// Get all nodes
140    pub fn nodes(&self) -> Vec<&TreeNode<T>> {
141        self.nodes.values().collect()
142    }
143
144    /// Get root nodes
145    pub fn roots(&self) -> Vec<&TreeNode<T>> {
146        self.nodes
147            .values()
148            .filter(|n| n.parent.is_none())
149            .collect()
150    }
151
152    /// Get children of a node
153    pub fn children(&self, id: &NodeId) -> Vec<&TreeNode<T>> {
154        if let Some(node) = self.nodes.get(id) {
155            node.children
156                .iter()
157                .filter_map(|child_id| self.nodes.get(child_id))
158                .collect()
159        } else {
160            Vec::new()
161        }
162    }
163
164    /// Get descendants of a node (recursive)
165    pub fn descendants(&self, id: &NodeId) -> Vec<&TreeNode<T>> {
166        let mut descendants = Vec::new();
167        self.collect_descendants(id, &mut descendants);
168        descendants
169    }
170    
171    fn collect_descendants<'a>(&'a self, id: &NodeId, descendants: &mut Vec<&'a TreeNode<T>>) {
172        if let Some(node) = self.nodes.get(id) {
173            for child_id in &node.children {
174                if let Some(child_node) = self.nodes.get(child_id) {
175                    descendants.push(child_node);
176                    self.collect_descendants(child_id, descendants);
177                }
178            }
179        }
180    }
181
182    /// Check if the tree contains a node
183    pub fn contains(&self, id: &NodeId) -> bool {
184        self.nodes.contains_key(id)
185    }
186
187    /// Get the number of nodes
188    pub fn len(&self) -> usize {
189        self.nodes.len()
190    }
191
192    /// Check if the tree is empty
193    pub fn is_empty(&self) -> bool {
194        self.nodes.is_empty()
195    }
196
197    /// Clear all nodes
198    pub fn clear(&mut self) {
199        self.nodes.clear();
200    }
201}
202
203impl<T: Clone + PartialEq + Eq + Send + Sync> CRDT for RemoveWinsTree<T> {
204    fn replica_id(&self) -> &ReplicaId {
205        &self.replica
206    }
207}
208
209impl<T: Clone + PartialEq + Eq + Send + Sync> Mergeable for RemoveWinsTree<T> {
210    type Error = TreeError;
211
212    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
213        for (id, node) in &other.nodes {
214            match self.nodes.get(id) {
215                Some(existing) => {
216                    // Conflict resolution: later timestamp wins
217                    if node.metadata.modified_at > existing.metadata.modified_at {
218                        self.nodes.insert(id.clone(), node.clone());
219                    }
220                }
221                None => {
222                    // New node, add it
223                    self.nodes.insert(id.clone(), node.clone());
224                }
225            }
226        }
227        Ok(())
228    }
229
230    fn has_conflict(&self, other: &Self) -> bool {
231        for (id, node) in &other.nodes {
232            if let Some(existing) = self.nodes.get(id) {
233                // Check for conflicts: same timestamp but different replica
234                if node.metadata.modified_at == existing.metadata.modified_at
235                    && node.metadata.last_modified_by != existing.metadata.last_modified_by
236                {
237                    return true;
238                }
239            }
240        }
241        false
242    }
243}
leptos_sync_core/crdt/tree/remove_wins.rs

leptos_sync_core/crdt/tree/
remove_wins.rs
