dpm_model/
order.rs

1//! Fractional sibling positions independent of task names and identifiers.
2
3use serde::{Deserialize, Serialize};
4use thiserror::Error;
5
6/// Lexicographic fractional position. Concurrent equal positions use the work ID as a tie-breaker.
7/// Digits may contain zero internally; a nonzero final digit leaves room before every position.
8#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
9#[serde(transparent)]
10pub struct SiblingOrder(pub Vec<u16>);
11
12/// A requested insertion cannot be represented between its supplied bounds.
13#[derive(Debug, Clone, PartialEq, Eq, Error)]
14pub enum OrderError {
15    /// Bounds must be valid and the left one strictly precede the right one.
16    #[error("sibling order bounds must be valid and strictly increasing")]
17    InvalidBounds,
18    /// A pathological sequence of insertions exhausted the bounded portable representation.
19    #[error("sibling order exceeds 128 digits")]
20    Exhausted,
21}
22
23impl Default for SiblingOrder {
24    fn default() -> Self {
25        Self(vec![32768])
26    }
27}
28
29impl SiblingOrder {
30    /// Whether the position has a portable representation with room on either side.
31    #[must_use]
32    pub fn is_valid(&self) -> bool {
33        !self.0.is_empty() && self.0.len() <= 128 && self.0.last() != Some(&0)
34    }
35
36    /// Allocate a position between two siblings without renumbering any existing position.
37    /// An absent bound means the beginning or end of the sibling list.
38    pub fn between(left: Option<&Self>, right: Option<&Self>) -> Result<Self, OrderError> {
39        if left.is_some_and(|v| !v.is_valid())
40            || right.is_some_and(|v| !v.is_valid())
41            || left.zip(right).is_some_and(|(a, b)| a >= b)
42        {
43            return Err(OrderError::InvalidBounds);
44        }
45        let mut digits = Vec::new();
46        let mut upper = right;
47        for i in 0..128 {
48            let low = left.and_then(|v| v.0.get(i)).copied().map_or(0, u32::from);
49            let high = upper
50                .and_then(|v| v.0.get(i))
51                .copied()
52                .map_or(65536, u32::from);
53            if high > low + 1 {
54                let digit = if right.is_none() && left.is_some() {
55                    low + 1
56                } else {
57                    low + (high - low) / 2
58                };
59                digits.push(digit as u16);
60                return Ok(Self(digits));
61            }
62            digits.push(low as u16);
63            if low < high {
64                upper = None;
65            }
66        }
67        Err(OrderError::Exhausted)
68    }
69}
70
71#[cfg(test)]
72mod tests;
dpm_model/order.rs

dpm_model/
order.rs
