base95/
lib.rs

1//! Textual representation of base 95 fractional numbers with arbitrary precision,
2//! intended to be used in real-time collaborative applications.
3//!
4//! It can only represent numbers between 0 and 1, exclusive.
5//! The leading `0.` is omitted.
6//!
7//! Heavily inspired by [this article](https://www.figma.com/blog/realtime-editing-of-ordered-sequences/).
8//!
9//! ## Why 95?
10//!
11//! - UTF-8, the most popular Unicode encoding scheme, can encode ASCII as is. (1 byte per character)
12//! - ASCII has 95 printable characters in total, from space to tilde.
13//!
14//! ## Example
15//!
16//! ```
17//! use base95::Base95;
18//! use std::str::FromStr;
19//!
20//! let n1 = Base95::mid();
21//! assert_eq!(n1.to_string(), "O");
22//! assert_eq!(n1.raw_digits(), vec![47]);
23//!
24//! let n2 = Base95::avg_with_zero(&n1);
25//! assert_eq!(n2.to_string(), "7");
26//! assert_eq!(n2.raw_digits(), vec![23]);
27//!
28//! let n3 = Base95::avg_with_one(&n1);
29//! assert_eq!(n3.to_string(), "g");
30//! assert_eq!(n3.raw_digits(), vec![71]);
31//!
32//! let n4 = Base95::avg(&n1, &n2);
33//! assert_eq!(n4.to_string(), "C");
34//! assert_eq!(n4.raw_digits(), vec![35]);
35//!
36//! let n5 = Base95::from_str("j>Z= 4").unwrap();
37//! assert_eq!(n5.raw_digits(), vec![74, 30, 58, 29, 0, 20]);
38//! ```
39//!
40//! ## Why is `avg` imprecise?
41//!
42//! One of main considerations of this representation is storage efficiency of fractional index.
43//! So it is better to have a little imprecise, shorter string, than perfectly precise, longer string.
44//!
45//! Of course, the result is deterministic, i.e., if the input is same, the output will always be same.
46
47mod digits;
48
49use crate::digits::Digits;
50
51const ASCII_MIN: u8 = 32; // space
52
53#[derive(Debug, Clone, Ord, PartialOrd, Eq, PartialEq)]
54pub struct Base95(String);
55
56#[derive(Debug, Eq, PartialEq)]
57pub enum ParseError {
58    InvalidChar,
59    EmptyNotAllowed,
60}
61
62impl Base95 {
63    /// Create a fractional number of base 95, which represents `47 / 95`.
64    /// The only way to create Base95 instance without any arguments.
65    pub fn mid() -> Self {
66        Digits::mid().into()
67    }
68
69    pub fn avg(lhs: &Self, rhs: &Self) -> Self {
70        Digits::avg(&lhs.into(), &rhs.into()).into()
71    }
72
73    pub fn avg_with_zero(n: &Self) -> Self {
74        Digits::avg(&Digits::zero(), &n.into()).into()
75    }
76
77    pub fn avg_with_one(n: &Self) -> Self {
78        Digits::avg(&Digits::one(), &n.into()).into()
79    }
80
81    pub fn raw_digits(&self) -> Vec<u8> {
82        Digits::from(self).0
83    }
84}
85
86impl ToString for Base95 {
87    fn to_string(&self) -> String {
88        self.0.clone()
89    }
90}
91
92impl std::str::FromStr for Base95 {
93    type Err = ParseError;
94
95    fn from_str(s: &str) -> Result<Self, Self::Err> {
96        if s.is_empty() {
97            Err(ParseError::EmptyNotAllowed)
98        } else if s.chars().any(|c| !c.is_ascii() || c.is_ascii_control()) {
99            Err(ParseError::InvalidChar)
100        } else {
101            Ok(Base95(s.to_owned()))
102        }
103    }
104}
105
106impl From<Digits> for Base95 {
107    fn from(digits: Digits) -> Self {
108        Self(String::from_utf8(digits.0.iter().map(|x| x + ASCII_MIN).collect()).unwrap())
109    }
110}
111
112impl From<&Base95> for Digits {
113    fn from(base95: &Base95) -> Self {
114        Self(base95.0.as_bytes().iter().map(|x| x - ASCII_MIN).collect())
115    }
116}
117
118impl From<Base95> for String {
119    fn from(base95: Base95) -> Self {
120        base95.0
121    }
122}
123
124#[cfg(test)]
125mod tests {
126    use super::*;
127    use std::str::FromStr;
128
129    #[test]
130    fn it_works() {
131        assert_eq!(Base95::from_str(""), Err(ParseError::EmptyNotAllowed));
132        assert_eq!(Base95::from_str("한글"), Err(ParseError::InvalidChar));
133        assert_eq!(Base95::from_str("O").unwrap(), Base95::mid());
134    }
135}
base95/lib.rs

base95/
lib.rs
