version_sort/
lib.rs

1#![cfg_attr(test, feature(plugin))]
2#![cfg_attr(test, plugin(clippy))]
3
4use std::cmp::Ordering;
5use std::fmt::{self, Write};
6use std::num::ParseIntError;
7use std::str::FromStr;
8
9/// An unsigned integer that can be printed.
10#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
11pub struct Number {
12    value: u64,
13    leading_zeroes: u8,
14}
15impl Number {
16    /// Strips leading zeroes from this number.
17    pub fn strip_zeroes(self) -> Number {
18        Number { value: self.value, leading_zeroes: 0 }
19    }
20
21    /// Converts this `Number` into its value, discarding leading zeroes.
22    pub fn into_value(self) -> u64 {
23        self.value
24    }
25}
26impl PartialOrd for Number {
27    fn partial_cmp(&self, rhs: &Number) -> Option<Ordering> {
28        Some(self.cmp(rhs))
29    }
30}
31impl Ord for Number {
32    fn cmp(&self, rhs: &Number) -> Ordering {
33        match self.value.cmp(&rhs.value) {
34            Ordering::Equal => rhs.leading_zeroes.cmp(&self.leading_zeroes),
35            ord => ord,
36        }
37    }
38}
39impl From<u64> for Number {
40    fn from(value: u64) -> Number {
41        Number { value, leading_zeroes: 0 }
42    }
43}
44impl FromStr for Number {
45    type Err = ParseIntError;
46    fn from_str(s: &str) -> Result<Number, ParseIntError> {
47        let value = s.parse()?;
48        let leading_zeroes = s.bytes().position(|b| b != b'0').unwrap_or(0) as u8;
49        Ok(Number { value, leading_zeroes })
50    }
51}
52impl fmt::Display for Number {
53    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
54        for _ in 0..self.leading_zeroes {
55            f.write_char('0')?;
56        }
57        fmt::Display::fmt(&self.value, f)
58    }
59}
60
61/// Piece of a string, either as another string or a number.
62///
63/// This is used for the version sorting; a part of a string is
64#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
65pub enum Part<'a> {
66    /// An unsigned integer, including padded zeroes.
67    Num(Number),
68
69    /// Part of a string.
70    Str(&'a str),
71}
72impl<'a> Part<'a> {
73    /// Extracts out the next part of the given string.
74    pub fn extract_from(s: &'a str) -> Option<(Part<'a>, &'a str)> {
75        let bs = s.as_bytes();
76
77        // take the first byte
78        if let Some((&b, bs)) = bs.split_first() {
79            match b {
80                // if it's a digit, extract out an integer
81                b'0'...b'9' => {
82                    let split = bs.iter()
83                        .position(|&b| b < b'0' || b'9' < b)
84                        .map(|i| i + 1)
85                        .unwrap_or(s.len());
86                    let part = Part::Num(s[..split].parse().unwrap());
87                    let rest = &s[split..];
88                    Some((part, rest))
89                }
90                // if it's not a digit, parse until we find a digit
91                _ => {
92                    let split = bs.iter()
93                        .position(|&b| b'0' <= b && b <= b'9')
94                        .map(|i| i + 1)
95                        .unwrap_or(s.len());
96                    let part = Part::Str(&s[..split]);
97                    let rest = &s[split..];
98                    Some((part, rest))
99                }
100            }
101        // it's empty; there is none
102        } else {
103            None
104        }
105    }
106
107    /// Strips padded zeroes from this part.
108    pub fn strip_zeroes(self) -> Part<'a> {
109        match self {
110            Part::Num(num) => Part::Num(num.strip_zeroes()),
111            Part::Str(s) => Part::Str(s),
112        }
113    }
114}
115
116/// An iterator over the string as a sequence of `Part`s, which can be used to compare versions with
117/// one another.
118#[derive(Clone, Debug)]
119pub struct Version<'a> {
120    inner: &'a str,
121}
122impl<'a> Version<'a> {
123    /// Creates a `Version` from a string.
124    pub fn new(s: &'a str) -> Version<'a> {
125        Version { inner: s }
126    }
127}
128impl<'a> Iterator for Version<'a> {
129    type Item = Part<'a>;
130    fn next(&mut self) -> Option<Part<'a>> {
131        Part::extract_from(self.inner).map(|(part, rest)| {
132            self.inner = rest;
133            part
134        })
135    }
136}
137impl<'a> PartialEq for Version<'a> {
138    fn eq(&self, rhs: &Version<'a>) -> bool {
139        self.clone().eq(rhs.clone())
140    }
141}
142impl<'a> Eq for Version<'a> {}
143impl<'a> PartialOrd for Version<'a> {
144    fn partial_cmp(&self, rhs: &Version<'a>) -> Option<Ordering> {
145        self.clone().partial_cmp(rhs.clone())
146    }
147}
148impl<'a> Ord for Version<'a> {
149    fn cmp(&self, rhs: &Version<'a>) -> Ordering {
150        self.clone().cmp(rhs.clone())
151    }
152}
153
154#[cfg(test)]
155mod tests {
156    use super::{Number, Part, Version};
157
158    #[test]
159    fn lexical() {
160        assert!(Version::new("aaaaa") < Version::new("aaaaaa"));
161    }
162
163    #[test]
164    fn lexical_with_numbers() {
165        assert!(Version::new("abc123") > Version::new("abc0123"));
166    }
167
168    #[test]
169    fn nonlexical_float() {
170        assert!(Version::new("10.1") > Version::new("1.1"));
171        assert!(Version::new("1.10") > Version::new("1.1"));
172    }
173
174    #[test]
175    fn just_numbers() {
176        assert!(Version::new("2") < Version::new("10"));
177    }
178
179    #[test]
180    fn zeroes() {
181        assert!(Version::new("01") < Version::new("1"));
182    }
183
184    #[test]
185    fn mix() {
186        assert_eq!(Version::new("Is 01.01.70 the epoch?").collect::<Vec<_>>(),
187                vec![Part::Str("Is "),
188                     Part::Num(Number { value: 1, leading_zeroes: 1 }),
189                     Part::Str("."),
190                     Part::Num(Number { value: 1, leading_zeroes: 1 }),
191                     Part::Str("."),
192                     Part::Num(Number { value: 70, leading_zeroes: 0 }),
193                     Part::Str(" the epoch?")]);
194    }
195}
version_sort/lib.rs

version_sort/
lib.rs
