1 use crate::coord::ranged1d::{
2     AsRangedCoord, DiscreteRanged, KeyPointHint, NoDefaultFormatting, Ranged, ValueFormatter,
3 };
4 use std::ops::Range;
5 
6 /// Describe a value for a nested coordinate
7 #[derive(PartialEq, Eq, Clone, Debug)]
8 pub enum NestedValue<C, V> {
9     /// Category value
10     Category(C),
11     /// One exact nested value
12     Value(C, V),
13 }
14 
15 impl<C, V> NestedValue<C, V> {
16     /// Get the category of current nest value
category(&self) -> &C17     pub fn category(&self) -> &C {
18         match self {
19             NestedValue::Category(cat) => cat,
20             NestedValue::Value(cat, _) => cat,
21         }
22     }
23     /// Get the nested value from this value
nested_value(&self) -> Option<&V>24     pub fn nested_value(&self) -> Option<&V> {
25         match self {
26             NestedValue::Category(_) => None,
27             NestedValue::Value(_, val) => Some(val),
28         }
29     }
30 }
31 
32 impl<C, V> From<(C, V)> for NestedValue<C, V> {
from((cat, val): (C, V)) -> NestedValue<C, V>33     fn from((cat, val): (C, V)) -> NestedValue<C, V> {
34         NestedValue::Value(cat, val)
35     }
36 }
37 
38 impl<C, V> From<C> for NestedValue<C, V> {
from(cat: C) -> NestedValue<C, V>39     fn from(cat: C) -> NestedValue<C, V> {
40         NestedValue::Category(cat)
41     }
42 }
43 
44 /// A nested coordinate spec which is a discrete coordinate on the top level and
45 /// for each value in discrete value, there is a secondary coordinate system.
46 /// And the value is defined as a tuple of primary coordinate value and secondary
47 /// coordinate value
48 pub struct NestedRange<Primary: DiscreteRanged, Secondary: Ranged> {
49     primary: Primary,
50     secondary: Vec<Secondary>,
51 }
52 
53 impl<PT, ST, P, S> ValueFormatter<NestedValue<PT, ST>> for NestedRange<P, S>
54 where
55     P: Ranged<ValueType = PT> + DiscreteRanged,
56     S: Ranged<ValueType = ST>,
57     P: ValueFormatter<PT>,
58     S: ValueFormatter<ST>,
59 {
format(value: &NestedValue<PT, ST>) -> String60     fn format(value: &NestedValue<PT, ST>) -> String {
61         match value {
62             NestedValue::Category(cat) => P::format(cat),
63             NestedValue::Value(_, val) => S::format(val),
64         }
65     }
66 }
67 
68 impl<P: DiscreteRanged, S: Ranged> Ranged for NestedRange<P, S> {
69     type FormatOption = NoDefaultFormatting;
70     type ValueType = NestedValue<P::ValueType, S::ValueType>;
71 
range(&self) -> Range<Self::ValueType>72     fn range(&self) -> Range<Self::ValueType> {
73         let primary_range = self.primary.range();
74 
75         let secondary_left = self.secondary[0].range().start;
76         let secondary_right = self.secondary[self.primary.size() - 1].range().end;
77 
78         NestedValue::Value(primary_range.start, secondary_left)
79             ..NestedValue::Value(primary_range.end, secondary_right)
80     }
81 
map(&self, value: &Self::ValueType, limit: (i32, i32)) -> i3282     fn map(&self, value: &Self::ValueType, limit: (i32, i32)) -> i32 {
83         let idx = self.primary.index_of(value.category()).unwrap_or(0);
84         let total = self.primary.size();
85 
86         let bucket_size = (limit.1 - limit.0) / total as i32;
87         let mut residual = (limit.1 - limit.0) % total as i32;
88 
89         if residual < 0 {
90             residual += total as i32;
91         }
92 
93         let s_left = limit.0 + bucket_size * idx as i32 + residual.min(idx as i32);
94         let s_right = s_left + bucket_size + if (residual as usize) < idx { 1 } else { 0 };
95 
96         if let Some(secondary_value) = value.nested_value() {
97             self.secondary[idx].map(secondary_value, (s_left, s_right))
98         } else {
99             (s_left + s_right) / 2
100         }
101     }
102 
key_points<Hint: KeyPointHint>(&self, hint: Hint) -> Vec<Self::ValueType>103     fn key_points<Hint: KeyPointHint>(&self, hint: Hint) -> Vec<Self::ValueType> {
104         if !hint.weight().allow_light_points() || hint.max_num_points() < self.primary.size() * 2 {
105             self.primary
106                 .key_points(hint)
107                 .into_iter()
108                 .map(NestedValue::Category)
109                 .collect()
110         } else {
111             let secondary_size =
112                 (hint.max_num_points() - self.primary.size()) / self.primary.size();
113             self.primary
114                 .values()
115                 .enumerate()
116                 .map(|(idx, val)| {
117                     std::iter::once(NestedValue::Category(val)).chain(
118                         self.secondary[idx]
119                             .key_points(secondary_size)
120                             .into_iter()
121                             .map(move |v| {
122                                 NestedValue::Value(self.primary.from_index(idx).unwrap(), v)
123                             }),
124                     )
125                 })
126                 .flatten()
127                 .collect()
128         }
129     }
130 }
131 
132 impl<P: DiscreteRanged, S: DiscreteRanged> DiscreteRanged for NestedRange<P, S> {
size(&self) -> usize133     fn size(&self) -> usize {
134         self.secondary.iter().map(|x| x.size()).sum::<usize>()
135     }
136 
index_of(&self, value: &Self::ValueType) -> Option<usize>137     fn index_of(&self, value: &Self::ValueType) -> Option<usize> {
138         let p_idx = self.primary.index_of(value.category())?;
139         let s_idx = self.secondary[p_idx].index_of(value.nested_value()?)?;
140         Some(
141             s_idx
142                 + self.secondary[..p_idx]
143                     .iter()
144                     .map(|x| x.size())
145                     .sum::<usize>(),
146         )
147     }
148 
from_index(&self, mut index: usize) -> Option<Self::ValueType>149     fn from_index(&self, mut index: usize) -> Option<Self::ValueType> {
150         for (p_idx, snd) in self.secondary.iter().enumerate() {
151             if snd.size() > index {
152                 return Some(NestedValue::Value(
153                     self.primary.from_index(p_idx).unwrap(),
154                     snd.from_index(index).unwrap(),
155                 ));
156             }
157             index -= snd.size();
158         }
159         None
160     }
161 }
162 
163 pub trait BuildNestedCoord: AsRangedCoord
164 where
165     Self::CoordDescType: DiscreteRanged,
166 {
nested_coord<S: AsRangedCoord>( self, builder: impl Fn(<Self::CoordDescType as Ranged>::ValueType) -> S, ) -> NestedRange<Self::CoordDescType, S::CoordDescType>167     fn nested_coord<S: AsRangedCoord>(
168         self,
169         builder: impl Fn(<Self::CoordDescType as Ranged>::ValueType) -> S,
170     ) -> NestedRange<Self::CoordDescType, S::CoordDescType> {
171         let primary: Self::CoordDescType = self.into();
172         assert!(primary.size() > 0);
173 
174         let secondary = primary
175             .values()
176             .map(|value| builder(value).into())
177             .collect();
178 
179         NestedRange { primary, secondary }
180     }
181 }
182 
183 impl<T: AsRangedCoord> BuildNestedCoord for T where T::CoordDescType: DiscreteRanged {}
184 
185 #[cfg(test)]
186 mod test {
187     use super::*;
188 
189     #[test]
test_nested_coord()190     fn test_nested_coord() {
191         let coord = (0..10).nested_coord(|x| 0..(x + 1));
192 
193         let range = coord.range();
194 
195         assert_eq!(NestedValue::Value(0, 0)..NestedValue::Value(10, 11), range);
196         assert_eq!(coord.map(&NestedValue::Category(0), (0, 1100)), 50);
197         assert_eq!(coord.map(&NestedValue::Value(0, 0), (0, 1100)), 0);
198         assert_eq!(coord.map(&NestedValue::Value(5, 4), (0, 1100)), 567);
199 
200         assert_eq!(coord.size(), (2 + 12) * 11 / 2);
201         assert_eq!(coord.index_of(&NestedValue::Value(5, 4)), Some(24));
202         assert_eq!(coord.from_index(24), Some(NestedValue::Value(5, 4)));
203     }
204 }
205