fn to_range<R>(range: R, ub: usize) -> RangeInclusive<usize>where
R: RangeBounds<usize>,Examples found in repository?
crates/competitive/src/string/rolling_hash.rs (line 55)
51 pub fn range<R>(&self, range: R) -> HashedRange<'_, Hasher>
52 where
53 R: RangeBounds<usize>,
54 {
55 HashedRange::new(&self.hashed[to_range(range, self.len())])
56 }
57 pub fn hash_range<R>(&self, range: R) -> Hashed<Hasher>
58 where
59 R: RangeBounds<usize>,
60 {
61 self.range(range).hash()
62 }
63}
64
65#[derive(Debug)]
66pub struct HashedRange<'a, Hasher>
67where
68 Hasher: RollingHasher + ?Sized,
69{
70 hashed: &'a [Hasher::Hash],
71 _marker: PhantomData<fn() -> Hasher>,
72}
73
74impl<Hasher> Clone for HashedRange<'_, Hasher>
75where
76 Hasher: RollingHasher + ?Sized,
77{
78 fn clone(&self) -> Self {
79 *self
80 }
81}
82
83impl<Hasher> Copy for HashedRange<'_, Hasher> where Hasher: RollingHasher + ?Sized {}
84
85impl<Hasher> PartialEq for HashedRange<'_, Hasher>
86where
87 Hasher: RollingHasher + ?Sized,
88{
89 fn eq(&self, other: &Self) -> bool {
90 self.hash() == other.hash()
91 }
92}
93
94impl<Hasher> Eq for HashedRange<'_, Hasher> where Hasher: RollingHasher + ?Sized {}
95
96impl<Hasher> PartialOrd for HashedRange<'_, Hasher>
97where
98 Hasher: RollingHasher<Hash: PartialOrd> + ?Sized,
99{
100 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
101 let n = self.longest_common_prefix(other);
102 match (self.len() > n, other.len() > n) {
103 (true, true) => {
104 let x = self.hash_range(n..=n);
105 let y = other.hash_range(n..=n);
106 x.hash.partial_cmp(&y.hash)
107 }
108 (x, y) => Some(x.cmp(&y)),
109 }
110 }
111}
112
113impl<Hasher> Ord for HashedRange<'_, Hasher>
114where
115 Hasher: RollingHasher<Hash: Ord> + ?Sized,
116{
117 fn cmp(&self, other: &Self) -> Ordering {
118 let n = self.longest_common_prefix(other);
119 match (self.len() > n, other.len() > n) {
120 (true, true) => {
121 let x = self.hash_range(n..=n);
122 let y = other.hash_range(n..=n);
123 x.hash.cmp(&y.hash)
124 }
125 (x, y) => x.cmp(&y),
126 }
127 }
128}
129
130impl<'a, Hasher> HashedRange<'a, Hasher>
131where
132 Hasher: RollingHasher + ?Sized,
133{
134 fn new(hashed: &'a [Hasher::Hash]) -> Self {
135 Self {
136 hashed,
137 _marker: PhantomData,
138 }
139 }
140 pub fn len(&self) -> usize {
141 self.hashed.len() - 1
142 }
143 pub fn is_empty(&self) -> bool {
144 self.len() == 0
145 }
146 pub fn range<R>(&self, range: R) -> HashedRange<'a, Hasher>
147 where
148 R: RangeBounds<usize>,
149 {
150 HashedRange::new(&self.hashed[to_range(range, self.len())])
151 }