1 files changed, 80 insertions, 0 deletions

diff --git a/src/stable_vec.rs b/src/stable_vec.rs
index 38eb162..4d25e0e 100644
--- a/src/stable_vec.rs
+++ b/src/stable_vec.rs
@@ -1,11 +1,13 @@
 //! Stable vec is a vector that guarantees its content access position does not change.
 
+use serde::{Deserialize, Serialize};
 use std::ops::Deref;
 use std::slice::IterMut;
 
 /// Works like Vec, but with an additional field, where the position information is saved. Does not
 /// support inserting elements in arbitrary positions, since that may shift the data. Removing data
 /// in the middle is fine, however.
+#[derive(Clone, Debug, Deserialize, Serialize)]
 pub struct StableVec<T> {
     data: Vec<(usize, T)>,
 }
@@ -22,6 +24,12 @@ impl<T> StableVec<T> {
         Self { data: Vec::new() }
     }
 
+    /// Create a stable vec from a sorted (by id, T.0) vector. Don't use if you're
+    /// not absolutely sure the data is valid.
+    pub fn from_raw_unchecked(data: Vec<(usize, T)>) -> Self {
+        Self { data }
+    }
+
     /// Add an item to the end of the vector. Returns its stable id. (`len()-1 != last_element_id`)
     pub fn push(&mut self, item: T) -> usize {
         if self.data.is_empty() {
@@ -34,6 +42,72 @@ impl<T> StableVec<T> {
         }
     }
 
+    /// Remove all data from this vec, leaving it like a StableVec created with `new` datawise.
+    pub fn clear(&mut self) {
+        self.data.clear()
+    }
+
+    /// Find the next free space in the vec. If there is space at the end, this will be preferred,
+    /// otherwise low ids are. After checking this, `try_insert` will not fail and the returned
+    /// id can be used to insert an item at that position.
+    pub fn next_free(&self) -> usize {
+        // Check if the item can be pushed at the end.
+        if self.data.is_empty() {
+            0
+        } else if self.data.last().unwrap().0 < usize::MAX {
+            self.data.last().unwrap().0 + 1
+        } else {
+            // Try to find a position in the vector that is still free, starting at the bottom.
+            let mut prev_id = self.data.first().unwrap().0;
+            for (_, (id, _)) in self.data.iter().enumerate().skip(1) {
+                if *id > prev_id + 1 {
+                    return *id - 1;
+                }
+
+                prev_id = *id;
+            }
+
+            panic!("There is no free space in the vector. This should never happen.");
+        }
+    }
+
+    /// Attempts to insert the item at the given position. If there is no free space, an Err value
+    /// will be returned.
+    pub fn try_insert(&mut self, id: usize, item: T) -> Result<(), ()> {
+        match self.find_pos(id) {
+            // The item already exists, this is an error.
+            Ok(_) => Err(()),
+            Err(pos) => {
+                self.data.insert(pos, (id, item));
+                Ok(())
+            }
+        }
+    }
+
+    /// Tries to push the item into the vector, but if it doesn't work, it searches for an opening in
+    /// the vector where no item currently is and places it there, favouring low ids (low ids contain
+    /// potentially older changes).
+    pub fn insert_anywhere(&mut self, item: T) -> usize {
+        // Check if the item can be pushed at the end and do so if possible.
+        if self.data.is_empty() || self.data.last().unwrap().0 < usize::MAX {
+            self.push(item)
+        } else {
+            // Try to find a position in the vector that is still free, starting at the bottom.
+            let mut prev_id = self.data.first().unwrap().0;
+            for (place, (id, _)) in self.data.iter().enumerate().skip(1) {
+                if *id > prev_id + 1 {
+                    let id = *id - 1;
+                    self.data.insert(place, (id, item));
+                    return id;
+                }
+
+                prev_id = *id;
+            }
+
+            panic!("Unable to insert element. No space left in the vector.");
+        }
+    }
+
     // Find the internal position of the given id in `O(log n)`
     fn find_pos(&self, id: usize) -> Result<usize, usize> {
         self.data.binary_search_by(|x| x.0.cmp(&id))
@@ -84,6 +158,12 @@ impl<T> Deref for StableVec<T> {
     }
 }
 
+impl<T> Into<Vec<(usize, T)>> for StableVec<T> {
+    fn into(self) -> Vec<(usize, T)> {
+        self.data
+    }
+}
+
 impl<'a, T> IdIterMut<'a, T> {
     pub(super) fn new(id_vec: &'a mut [(usize, T)]) -> Self {
         Self {