competitive::string::rolling_hash

Struct HashedRange

Source 
pub struct HashedRange<'a, Hasher>
where
    Hasher: RollingHasher + ?Sized,
{ /* private fields */ }

Implementations§

Source§

impl<'a, Hasher> HashedRange<'a, Hasher>
where Hasher: RollingHasher + ?Sized,

Source

pub fn len(&self) -> usize

Examples found in repository?
crates/competitive/src/string/rolling_hash.rs (line 103)
101    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
102        let n = self.longest_common_prefix(other);
103        match (self.len() > n, other.len() > n) {
104            (true, true) => {
105                let x = self.hash_range(n..=n);
106                let y = other.hash_range(n..=n);
107                x.hash.partial_cmp(&y.hash)
108            }
109            (x, y) => Some(x.cmp(&y)),
110        }
111    }
112}
113
114impl<Hasher> Ord for HashedRange<'_, Hasher>
115where
116    Hasher: RollingHasher + ?Sized,
117    Hasher::Hash: Ord,
118{
119    fn cmp(&self, other: &Self) -> Ordering {
120        let n = self.longest_common_prefix(other);
121        match (self.len() > n, other.len() > n) {
122            (true, true) => {
123                let x = self.hash_range(n..=n);
124                let y = other.hash_range(n..=n);
125                x.hash.cmp(&y.hash)
126            }
127            (x, y) => x.cmp(&y),
128        }
129    }
130}
131
132impl<'a, Hasher> HashedRange<'a, Hasher>
133where
134    Hasher: RollingHasher + ?Sized,
135{
136    fn new(hashed: &'a [Hasher::Hash]) -> Self {
137        Self {
138            hashed,
139            _marker: PhantomData,
140        }
141    }
142    pub fn len(&self) -> usize {
143        self.hashed.len() - 1
144    }
145    pub fn is_empty(&self) -> bool {
146        self.len() == 0
147    }
148    pub fn range<R>(&self, range: R) -> HashedRange<'a, Hasher>
149    where
150        R: RangeBounds<usize>,
151    {
152        HashedRange::new(&self.hashed[to_range(range, self.len())])
153    }
154    pub fn hash_range<R>(&self, range: R) -> Hashed<Hasher>
155    where
156        R: RangeBounds<usize>,
157    {
158        self.range(range).hash()
159    }
160    pub fn hash(&self) -> Hashed<Hasher> {
161        Hasher::hash_substr(self.hashed)
162    }
163    pub fn longest_common_prefix(&self, other: &Self) -> usize {
164        let n = self.len().min(other.len());
165        let mut ok = 0usize;
166        let mut err = n + 1;
167        while ok + 1 < err {
168            let mid = (ok + err) / 2;
169            if self.range(..mid).hash() == other.range(..mid).hash() {
170                ok = mid;
171            } else {
172                err = mid;
173            }
174        }
175        ok
176    }
177    pub fn chainable(self) -> HashedRangeChained<'a, Hasher> {
178        vec![self].into()
179    }
180}
181
182pub struct HashedRangeChained<'a, Hasher>
183where
184    Hasher: RollingHasher + ?Sized,
185{
186    chained: Vec<HashedRange<'a, Hasher>>,
187    _marker: PhantomData<fn() -> Hasher>,
188}
189
190impl<Hasher: Debug> Debug for HashedRangeChained<'_, Hasher>
191where
192    Hasher: RollingHasher + ?Sized,
193    Hasher::Hash: Debug,
194{
195    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
196        f.debug_struct("HashedRangeChained")
197            .field("chained", &self.chained)
198            .finish()
199    }
200}
201
202impl<Hasher: Default> Default for HashedRangeChained<'_, Hasher>
203where
204    Hasher: RollingHasher,
205{
206    fn default() -> Self {
207        Self {
208            chained: Default::default(),
209            _marker: Default::default(),
210        }
211    }
212}
213
214impl<Hasher: Clone> Clone for HashedRangeChained<'_, Hasher>
215where
216    Hasher: RollingHasher,
217{
218    fn clone(&self) -> Self {
219        Self {
220            chained: self.chained.clone(),
221            _marker: self._marker,
222        }
223    }
224}
225
226impl<Hasher> PartialEq for HashedRangeChained<'_, Hasher>
227where
228    Hasher: RollingHasher + ?Sized,
229{
230    fn eq(&self, other: &Self) -> bool {
231        let mut a = self.chained.iter().cloned();
232        let mut b = other.chained.iter().cloned();
233        macro_rules! next {
234            ($iter:expr) => {
235                loop {
236                    if let Some(x) = $iter.next() {
237                        if x.len() > 0 {
238                            break Some(x);
239                        }
240                    } else {
241                        break None;
242                    }
243                }
244            };
245        }
246        let mut x: Option<HashedRange<'_, Hasher>> = None;
247        let mut y: Option<HashedRange<'_, Hasher>> = None;
248        loop {
249            if x.map_or(true, |x| x.is_empty()) {
250                x = next!(a);
251            }
252            if y.map_or(true, |y| y.is_empty()) {
253                y = next!(b);
254            }
255            if let (Some(x), Some(y)) = (&mut x, &mut y) {
256                let k = x.len().min(y.len());
257                if x.range(..k) != y.range(..k) {
258                    return false;
259                }
260                *x = x.range(k..);
261                *y = y.range(k..);
262            } else {
263                break x.is_none() == y.is_none();
264            }
265        }
266    }
267}
268
269impl<Hasher> Eq for HashedRangeChained<'_, Hasher> where Hasher: RollingHasher + ?Sized {}
270
271impl<Hasher> PartialOrd for HashedRangeChained<'_, Hasher>
272where
273    Hasher: RollingHasher + ?Sized,
274    Hasher::Hash: PartialOrd,
275{
276    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
277        let mut a = self.chained.iter().cloned();
278        let mut b = other.chained.iter().cloned();
279        macro_rules! next {
280            ($iter:expr) => {
281                loop {
282                    if let Some(x) = $iter.next() {
283                        if x.len() > 0 {
284                            break Some(x);
285                        }
286                    } else {
287                        break None;
288                    }
289                }
290            };
291        }
292        let mut x: Option<HashedRange<'_, Hasher>> = None;
293        let mut y: Option<HashedRange<'_, Hasher>> = None;
294        loop {
295            if x.map_or(true, |x| x.is_empty()) {
296                x = next!(a);
297            }
298            if y.map_or(true, |y| y.is_empty()) {
299                y = next!(b);
300            }
301            if let (Some(x), Some(y)) = (&mut x, &mut y) {
302                let k = x.longest_common_prefix(y);
303                if x.len() > k && y.len() > k {
304                    let x = x.hash_range(k..=k);
305                    let y = y.hash_range(k..=k);
306                    break x.hash.partial_cmp(&y.hash);
307                };
308                *x = x.range(k..);
309                *y = y.range(k..);
310            } else {
311                break x.is_some().partial_cmp(&y.is_some());
312            }
313        }
314    }
315}
316
317impl<Hasher> Ord for HashedRangeChained<'_, Hasher>
318where
319    Hasher: RollingHasher + ?Sized,
320    Hasher::Hash: Ord,
321{
322    fn cmp(&self, other: &Self) -> Ordering {
323        let mut a = self.chained.iter().cloned();
324        let mut b = other.chained.iter().cloned();
325        macro_rules! next {
326            ($iter:expr) => {
327                loop {
328                    if let Some(x) = $iter.next() {
329                        if x.len() > 0 {
330                            break Some(x);
331                        }
332                    } else {
333                        break None;
334                    }
335                }
336            };
337        }
338        let mut x: Option<HashedRange<'_, Hasher>> = None;
339        let mut y: Option<HashedRange<'_, Hasher>> = None;
340        loop {
341            if x.map_or(true, |x| x.is_empty()) {
342                x = next!(a);
343            }
344            if y.map_or(true, |y| y.is_empty()) {
345                y = next!(b);
346            }
347            if let (Some(x), Some(y)) = (&mut x, &mut y) {
348                let k = x.longest_common_prefix(y);
349                if x.len() > k && y.len() > k {
350                    let x = x.hash_range(k..=k);
351                    let y = y.hash_range(k..=k);
352                    break x.hash.cmp(&y.hash);
353                };
354                *x = x.range(k..);
355                *y = y.range(k..);
356            } else {
357                break x.is_some().cmp(&y.is_some());
358            }
359        }
360    }
Source

pub fn is_empty(&self) -> bool

Examples found in repository?
crates/competitive/src/string/rolling_hash.rs (line 249)
230    fn eq(&self, other: &Self) -> bool {
231        let mut a = self.chained.iter().cloned();
232        let mut b = other.chained.iter().cloned();
233        macro_rules! next {
234            ($iter:expr) => {
235                loop {
236                    if let Some(x) = $iter.next() {
237                        if x.len() > 0 {
238                            break Some(x);
239                        }
240                    } else {
241                        break None;
242                    }
243                }
244            };
245        }
246        let mut x: Option<HashedRange<'_, Hasher>> = None;
247        let mut y: Option<HashedRange<'_, Hasher>> = None;
248        loop {
249            if x.map_or(true, |x| x.is_empty()) {
250                x = next!(a);
251            }
252            if y.map_or(true, |y| y.is_empty()) {
253                y = next!(b);
254            }
255            if let (Some(x), Some(y)) = (&mut x, &mut y) {
256                let k = x.len().min(y.len());
257                if x.range(..k) != y.range(..k) {
258                    return false;
259                }
260                *x = x.range(k..);
261                *y = y.range(k..);
262            } else {
263                break x.is_none() == y.is_none();
264            }
265        }
266    }
267}
268
269impl<Hasher> Eq for HashedRangeChained<'_, Hasher> where Hasher: RollingHasher + ?Sized {}
270
271impl<Hasher> PartialOrd for HashedRangeChained<'_, Hasher>
272where
273    Hasher: RollingHasher + ?Sized,
274    Hasher::Hash: PartialOrd,
275{
276    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
277        let mut a = self.chained.iter().cloned();
278        let mut b = other.chained.iter().cloned();
279        macro_rules! next {
280            ($iter:expr) => {
281                loop {
282                    if let Some(x) = $iter.next() {
283                        if x.len() > 0 {
284                            break Some(x);
285                        }
286                    } else {
287                        break None;
288                    }
289                }
290            };
291        }
292        let mut x: Option<HashedRange<'_, Hasher>> = None;
293        let mut y: Option<HashedRange<'_, Hasher>> = None;
294        loop {
295            if x.map_or(true, |x| x.is_empty()) {
296                x = next!(a);
297            }
298            if y.map_or(true, |y| y.is_empty()) {
299                y = next!(b);
300            }
301            if let (Some(x), Some(y)) = (&mut x, &mut y) {
302                let k = x.longest_common_prefix(y);
303                if x.len() > k && y.len() > k {
304                    let x = x.hash_range(k..=k);
305                    let y = y.hash_range(k..=k);
306                    break x.hash.partial_cmp(&y.hash);
307                };
308                *x = x.range(k..);
309                *y = y.range(k..);
310            } else {
311                break x.is_some().partial_cmp(&y.is_some());
312            }
313        }
314    }
315}
316
317impl<Hasher> Ord for HashedRangeChained<'_, Hasher>
318where
319    Hasher: RollingHasher + ?Sized,
320    Hasher::Hash: Ord,
321{
322    fn cmp(&self, other: &Self) -> Ordering {
323        let mut a = self.chained.iter().cloned();
324        let mut b = other.chained.iter().cloned();
325        macro_rules! next {
326            ($iter:expr) => {
327                loop {
328                    if let Some(x) = $iter.next() {
329                        if x.len() > 0 {
330                            break Some(x);
331                        }
332                    } else {
333                        break None;
334                    }
335                }
336            };
337        }
338        let mut x: Option<HashedRange<'_, Hasher>> = None;
339        let mut y: Option<HashedRange<'_, Hasher>> = None;
340        loop {
341            if x.map_or(true, |x| x.is_empty()) {
342                x = next!(a);
343            }
344            if y.map_or(true, |y| y.is_empty()) {
345                y = next!(b);
346            }
347            if let (Some(x), Some(y)) = (&mut x, &mut y) {
348                let k = x.longest_common_prefix(y);
349                if x.len() > k && y.len() > k {
350                    let x = x.hash_range(k..=k);
351                    let y = y.hash_range(k..=k);
352                    break x.hash.cmp(&y.hash);
353                };
354                *x = x.range(k..);
355                *y = y.range(k..);
356            } else {
357                break x.is_some().cmp(&y.is_some());
358            }
359        }
360    }
Source

pub fn range<R>(&self, range: R) -> HashedRange<'a, Hasher>
where R: RangeBounds<usize>,

Examples found in repository?
crates/competitive/src/string/rolling_hash.rs (line 158)
154    pub fn hash_range<R>(&self, range: R) -> Hashed<Hasher>
155    where
156        R: RangeBounds<usize>,
157    {
158        self.range(range).hash()
159    }
160    pub fn hash(&self) -> Hashed<Hasher> {
161        Hasher::hash_substr(self.hashed)
162    }
163    pub fn longest_common_prefix(&self, other: &Self) -> usize {
164        let n = self.len().min(other.len());
165        let mut ok = 0usize;
166        let mut err = n + 1;
167        while ok + 1 < err {
168            let mid = (ok + err) / 2;
169            if self.range(..mid).hash() == other.range(..mid).hash() {
170                ok = mid;
171            } else {
172                err = mid;
173            }
174        }
175        ok
176    }
177    pub fn chainable(self) -> HashedRangeChained<'a, Hasher> {
178        vec![self].into()
179    }
180}
181
182pub struct HashedRangeChained<'a, Hasher>
183where
184    Hasher: RollingHasher + ?Sized,
185{
186    chained: Vec<HashedRange<'a, Hasher>>,
187    _marker: PhantomData<fn() -> Hasher>,
188}
189
190impl<Hasher: Debug> Debug for HashedRangeChained<'_, Hasher>
191where
192    Hasher: RollingHasher + ?Sized,
193    Hasher::Hash: Debug,
194{
195    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
196        f.debug_struct("HashedRangeChained")
197            .field("chained", &self.chained)
198            .finish()
199    }
200}
201
202impl<Hasher: Default> Default for HashedRangeChained<'_, Hasher>
203where
204    Hasher: RollingHasher,
205{
206    fn default() -> Self {
207        Self {
208            chained: Default::default(),
209            _marker: Default::default(),
210        }
211    }
212}
213
214impl<Hasher: Clone> Clone for HashedRangeChained<'_, Hasher>
215where
216    Hasher: RollingHasher,
217{
218    fn clone(&self) -> Self {
219        Self {
220            chained: self.chained.clone(),
221            _marker: self._marker,
222        }
223    }
224}
225
226impl<Hasher> PartialEq for HashedRangeChained<'_, Hasher>
227where
228    Hasher: RollingHasher + ?Sized,
229{
230    fn eq(&self, other: &Self) -> bool {
231        let mut a = self.chained.iter().cloned();
232        let mut b = other.chained.iter().cloned();
233        macro_rules! next {
234            ($iter:expr) => {
235                loop {
236                    if let Some(x) = $iter.next() {
237                        if x.len() > 0 {
238                            break Some(x);
239                        }
240                    } else {
241                        break None;
242                    }
243                }
244            };
245        }
246        let mut x: Option<HashedRange<'_, Hasher>> = None;
247        let mut y: Option<HashedRange<'_, Hasher>> = None;
248        loop {
249            if x.map_or(true, |x| x.is_empty()) {
250                x = next!(a);
251            }
252            if y.map_or(true, |y| y.is_empty()) {
253                y = next!(b);
254            }
255            if let (Some(x), Some(y)) = (&mut x, &mut y) {
256                let k = x.len().min(y.len());
257                if x.range(..k) != y.range(..k) {
258                    return false;
259                }
260                *x = x.range(k..);
261                *y = y.range(k..);
262            } else {
263                break x.is_none() == y.is_none();
264            }
265        }
266    }
267}
268
269impl<Hasher> Eq for HashedRangeChained<'_, Hasher> where Hasher: RollingHasher + ?Sized {}
270
271impl<Hasher> PartialOrd for HashedRangeChained<'_, Hasher>
272where
273    Hasher: RollingHasher + ?Sized,
274    Hasher::Hash: PartialOrd,
275{
276    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
277        let mut a = self.chained.iter().cloned();
278        let mut b = other.chained.iter().cloned();
279        macro_rules! next {
280            ($iter:expr) => {
281                loop {
282                    if let Some(x) = $iter.next() {
283                        if x.len() > 0 {
284                            break Some(x);
285                        }
286                    } else {
287                        break None;
288                    }
289                }
290            };
291        }
292        let mut x: Option<HashedRange<'_, Hasher>> = None;
293        let mut y: Option<HashedRange<'_, Hasher>> = None;
294        loop {
295            if x.map_or(true, |x| x.is_empty()) {
296                x = next!(a);
297            }
298            if y.map_or(true, |y| y.is_empty()) {
299                y = next!(b);
300            }
301            if let (Some(x), Some(y)) = (&mut x, &mut y) {
302                let k = x.longest_common_prefix(y);
303                if x.len() > k && y.len() > k {
304                    let x = x.hash_range(k..=k);
305                    let y = y.hash_range(k..=k);
306                    break x.hash.partial_cmp(&y.hash);
307                };
308                *x = x.range(k..);
309                *y = y.range(k..);
310            } else {
311                break x.is_some().partial_cmp(&y.is_some());
312            }
313        }
314    }
315}
316
317impl<Hasher> Ord for HashedRangeChained<'_, Hasher>
318where
319    Hasher: RollingHasher + ?Sized,
320    Hasher::Hash: Ord,
321{
322    fn cmp(&self, other: &Self) -> Ordering {
323        let mut a = self.chained.iter().cloned();
324        let mut b = other.chained.iter().cloned();
325        macro_rules! next {
326            ($iter:expr) => {
327                loop {
328                    if let Some(x) = $iter.next() {
329                        if x.len() > 0 {
330                            break Some(x);
331                        }
332                    } else {
333                        break None;
334                    }
335                }
336            };
337        }
338        let mut x: Option<HashedRange<'_, Hasher>> = None;
339        let mut y: Option<HashedRange<'_, Hasher>> = None;
340        loop {
341            if x.map_or(true, |x| x.is_empty()) {
342                x = next!(a);
343            }
344            if y.map_or(true, |y| y.is_empty()) {
345                y = next!(b);
346            }
347            if let (Some(x), Some(y)) = (&mut x, &mut y) {
348                let k = x.longest_common_prefix(y);
349                if x.len() > k && y.len() > k {
350                    let x = x.hash_range(k..=k);
351                    let y = y.hash_range(k..=k);
352                    break x.hash.cmp(&y.hash);
353                };
354                *x = x.range(k..);
355                *y = y.range(k..);
356            } else {
357                break x.is_some().cmp(&y.is_some());
358            }
359        }
360    }
Source

pub fn hash_range<R>(&self, range: R) -> Hashed<Hasher>
where R: RangeBounds<usize>,

Examples found in repository?
crates/competitive/src/string/rolling_hash.rs (line 105)
101    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
102        let n = self.longest_common_prefix(other);
103        match (self.len() > n, other.len() > n) {
104            (true, true) => {
105                let x = self.hash_range(n..=n);
106                let y = other.hash_range(n..=n);
107                x.hash.partial_cmp(&y.hash)
108            }
109            (x, y) => Some(x.cmp(&y)),
110        }
111    }
112}
113
114impl<Hasher> Ord for HashedRange<'_, Hasher>
115where
116    Hasher: RollingHasher + ?Sized,
117    Hasher::Hash: Ord,
118{
119    fn cmp(&self, other: &Self) -> Ordering {
120        let n = self.longest_common_prefix(other);
121        match (self.len() > n, other.len() > n) {
122            (true, true) => {
123                let x = self.hash_range(n..=n);
124                let y = other.hash_range(n..=n);
125                x.hash.cmp(&y.hash)
126            }
127            (x, y) => x.cmp(&y),
128        }
129    }
130}
131
132impl<'a, Hasher> HashedRange<'a, Hasher>
133where
134    Hasher: RollingHasher + ?Sized,
135{
136    fn new(hashed: &'a [Hasher::Hash]) -> Self {
137        Self {
138            hashed,
139            _marker: PhantomData,
140        }
141    }
142    pub fn len(&self) -> usize {
143        self.hashed.len() - 1
144    }
145    pub fn is_empty(&self) -> bool {
146        self.len() == 0
147    }
148    pub fn range<R>(&self, range: R) -> HashedRange<'a, Hasher>
149    where
150        R: RangeBounds<usize>,
151    {
152        HashedRange::new(&self.hashed[to_range(range, self.len())])
153    }
154    pub fn hash_range<R>(&self, range: R) -> Hashed<Hasher>
155    where
156        R: RangeBounds<usize>,
157    {
158        self.range(range).hash()
159    }
160    pub fn hash(&self) -> Hashed<Hasher> {
161        Hasher::hash_substr(self.hashed)
162    }
163    pub fn longest_common_prefix(&self, other: &Self) -> usize {
164        let n = self.len().min(other.len());
165        let mut ok = 0usize;
166        let mut err = n + 1;
167        while ok + 1 < err {
168            let mid = (ok + err) / 2;
169            if self.range(..mid).hash() == other.range(..mid).hash() {
170                ok = mid;
171            } else {
172                err = mid;
173            }
174        }
175        ok
176    }
177    pub fn chainable(self) -> HashedRangeChained<'a, Hasher> {
178        vec![self].into()
179    }
180}
181
182pub struct HashedRangeChained<'a, Hasher>
183where
184    Hasher: RollingHasher + ?Sized,
185{
186    chained: Vec<HashedRange<'a, Hasher>>,
187    _marker: PhantomData<fn() -> Hasher>,
188}
189
190impl<Hasher: Debug> Debug for HashedRangeChained<'_, Hasher>
191where
192    Hasher: RollingHasher + ?Sized,
193    Hasher::Hash: Debug,
194{
195    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
196        f.debug_struct("HashedRangeChained")
197            .field("chained", &self.chained)
198            .finish()
199    }
200}
201
202impl<Hasher: Default> Default for HashedRangeChained<'_, Hasher>
203where
204    Hasher: RollingHasher,
205{
206    fn default() -> Self {
207        Self {
208            chained: Default::default(),
209            _marker: Default::default(),
210        }
211    }
212}
213
214impl<Hasher: Clone> Clone for HashedRangeChained<'_, Hasher>
215where
216    Hasher: RollingHasher,
217{
218    fn clone(&self) -> Self {
219        Self {
220            chained: self.chained.clone(),
221            _marker: self._marker,
222        }
223    }
224}
225
226impl<Hasher> PartialEq for HashedRangeChained<'_, Hasher>
227where
228    Hasher: RollingHasher + ?Sized,
229{
230    fn eq(&self, other: &Self) -> bool {
231        let mut a = self.chained.iter().cloned();
232        let mut b = other.chained.iter().cloned();
233        macro_rules! next {
234            ($iter:expr) => {
235                loop {
236                    if let Some(x) = $iter.next() {
237                        if x.len() > 0 {
238                            break Some(x);
239                        }
240                    } else {
241                        break None;
242                    }
243                }
244            };
245        }
246        let mut x: Option<HashedRange<'_, Hasher>> = None;
247        let mut y: Option<HashedRange<'_, Hasher>> = None;
248        loop {
249            if x.map_or(true, |x| x.is_empty()) {
250                x = next!(a);
251            }
252            if y.map_or(true, |y| y.is_empty()) {
253                y = next!(b);
254            }
255            if let (Some(x), Some(y)) = (&mut x, &mut y) {
256                let k = x.len().min(y.len());
257                if x.range(..k) != y.range(..k) {
258                    return false;
259                }
260                *x = x.range(k..);
261                *y = y.range(k..);
262            } else {
263                break x.is_none() == y.is_none();
264            }
265        }
266    }
267}
268
269impl<Hasher> Eq for HashedRangeChained<'_, Hasher> where Hasher: RollingHasher + ?Sized {}
270
271impl<Hasher> PartialOrd for HashedRangeChained<'_, Hasher>
272where
273    Hasher: RollingHasher + ?Sized,
274    Hasher::Hash: PartialOrd,
275{
276    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
277        let mut a = self.chained.iter().cloned();
278        let mut b = other.chained.iter().cloned();
279        macro_rules! next {
280            ($iter:expr) => {
281                loop {
282                    if let Some(x) = $iter.next() {
283                        if x.len() > 0 {
284                            break Some(x);
285                        }
286                    } else {
287                        break None;
288                    }
289                }
290            };
291        }
292        let mut x: Option<HashedRange<'_, Hasher>> = None;
293        let mut y: Option<HashedRange<'_, Hasher>> = None;
294        loop {
295            if x.map_or(true, |x| x.is_empty()) {
296                x = next!(a);
297            }
298            if y.map_or(true, |y| y.is_empty()) {
299                y = next!(b);
300            }
301            if let (Some(x), Some(y)) = (&mut x, &mut y) {
302                let k = x.longest_common_prefix(y);
303                if x.len() > k && y.len() > k {
304                    let x = x.hash_range(k..=k);
305                    let y = y.hash_range(k..=k);
306                    break x.hash.partial_cmp(&y.hash);
307                };
308                *x = x.range(k..);
309                *y = y.range(k..);
310            } else {
311                break x.is_some().partial_cmp(&y.is_some());
312            }
313        }
314    }
315}
316
317impl<Hasher> Ord for HashedRangeChained<'_, Hasher>
318where
319    Hasher: RollingHasher + ?Sized,
320    Hasher::Hash: Ord,
321{
322    fn cmp(&self, other: &Self) -> Ordering {
323        let mut a = self.chained.iter().cloned();
324        let mut b = other.chained.iter().cloned();
325        macro_rules! next {
326            ($iter:expr) => {
327                loop {
328                    if let Some(x) = $iter.next() {
329                        if x.len() > 0 {
330                            break Some(x);
331                        }
332                    } else {
333                        break None;
334                    }
335                }
336            };
337        }
338        let mut x: Option<HashedRange<'_, Hasher>> = None;
339        let mut y: Option<HashedRange<'_, Hasher>> = None;
340        loop {
341            if x.map_or(true, |x| x.is_empty()) {
342                x = next!(a);
343            }
344            if y.map_or(true, |y| y.is_empty()) {
345                y = next!(b);
346            }
347            if let (Some(x), Some(y)) = (&mut x, &mut y) {
348                let k = x.longest_common_prefix(y);
349                if x.len() > k && y.len() > k {
350                    let x = x.hash_range(k..=k);
351                    let y = y.hash_range(k..=k);
352                    break x.hash.cmp(&y.hash);
353                };
354                *x = x.range(k..);
355                *y = y.range(k..);
356            } else {
357                break x.is_some().cmp(&y.is_some());
358            }
359        }
360    }
Source

pub fn hash(&self) -> Hashed<Hasher>

Examples found in repository?
crates/competitive/src/string/rolling_hash.rs (line 61)
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 + ?Sized,
99    Hasher::Hash: PartialOrd,
100{
101    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
102        let n = self.longest_common_prefix(other);
103        match (self.len() > n, other.len() > n) {
104            (true, true) => {
105                let x = self.hash_range(n..=n);
106                let y = other.hash_range(n..=n);
107                x.hash.partial_cmp(&y.hash)
108            }
109            (x, y) => Some(x.cmp(&y)),
110        }
111    }
112}
113
114impl<Hasher> Ord for HashedRange<'_, Hasher>
115where
116    Hasher: RollingHasher + ?Sized,
117    Hasher::Hash: Ord,
118{
119    fn cmp(&self, other: &Self) -> Ordering {
120        let n = self.longest_common_prefix(other);
121        match (self.len() > n, other.len() > n) {
122            (true, true) => {
123                let x = self.hash_range(n..=n);
124                let y = other.hash_range(n..=n);
125                x.hash.cmp(&y.hash)
126            }
127            (x, y) => x.cmp(&y),
128        }
129    }
130}
131
132impl<'a, Hasher> HashedRange<'a, Hasher>
133where
134    Hasher: RollingHasher + ?Sized,
135{
136    fn new(hashed: &'a [Hasher::Hash]) -> Self {
137        Self {
138            hashed,
139            _marker: PhantomData,
140        }
141    }
142    pub fn len(&self) -> usize {
143        self.hashed.len() - 1
144    }
145    pub fn is_empty(&self) -> bool {
146        self.len() == 0
147    }
148    pub fn range<R>(&self, range: R) -> HashedRange<'a, Hasher>
149    where
150        R: RangeBounds<usize>,
151    {
152        HashedRange::new(&self.hashed[to_range(range, self.len())])
153    }
154    pub fn hash_range<R>(&self, range: R) -> Hashed<Hasher>
155    where
156        R: RangeBounds<usize>,
157    {
158        self.range(range).hash()
159    }
160    pub fn hash(&self) -> Hashed<Hasher> {
161        Hasher::hash_substr(self.hashed)
162    }
163    pub fn longest_common_prefix(&self, other: &Self) -> usize {
164        let n = self.len().min(other.len());
165        let mut ok = 0usize;
166        let mut err = n + 1;
167        while ok + 1 < err {
168            let mid = (ok + err) / 2;
169            if self.range(..mid).hash() == other.range(..mid).hash() {
170                ok = mid;
171            } else {
172                err = mid;
173            }
174        }
175        ok
176    }
Source

pub fn longest_common_prefix(&self, other: &Self) -> usize

Examples found in repository?
crates/competitive/src/string/rolling_hash.rs (line 102)
101    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
102        let n = self.longest_common_prefix(other);
103        match (self.len() > n, other.len() > n) {
104            (true, true) => {
105                let x = self.hash_range(n..=n);
106                let y = other.hash_range(n..=n);
107                x.hash.partial_cmp(&y.hash)
108            }
109            (x, y) => Some(x.cmp(&y)),
110        }
111    }
112}
113
114impl<Hasher> Ord for HashedRange<'_, Hasher>
115where
116    Hasher: RollingHasher + ?Sized,
117    Hasher::Hash: Ord,
118{
119    fn cmp(&self, other: &Self) -> Ordering {
120        let n = self.longest_common_prefix(other);
121        match (self.len() > n, other.len() > n) {
122            (true, true) => {
123                let x = self.hash_range(n..=n);
124                let y = other.hash_range(n..=n);
125                x.hash.cmp(&y.hash)
126            }
127            (x, y) => x.cmp(&y),
128        }
129    }
130}
131
132impl<'a, Hasher> HashedRange<'a, Hasher>
133where
134    Hasher: RollingHasher + ?Sized,
135{
136    fn new(hashed: &'a [Hasher::Hash]) -> Self {
137        Self {
138            hashed,
139            _marker: PhantomData,
140        }
141    }
142    pub fn len(&self) -> usize {
143        self.hashed.len() - 1
144    }
145    pub fn is_empty(&self) -> bool {
146        self.len() == 0
147    }
148    pub fn range<R>(&self, range: R) -> HashedRange<'a, Hasher>
149    where
150        R: RangeBounds<usize>,
151    {
152        HashedRange::new(&self.hashed[to_range(range, self.len())])
153    }
154    pub fn hash_range<R>(&self, range: R) -> Hashed<Hasher>
155    where
156        R: RangeBounds<usize>,
157    {
158        self.range(range).hash()
159    }
160    pub fn hash(&self) -> Hashed<Hasher> {
161        Hasher::hash_substr(self.hashed)
162    }
163    pub fn longest_common_prefix(&self, other: &Self) -> usize {
164        let n = self.len().min(other.len());
165        let mut ok = 0usize;
166        let mut err = n + 1;
167        while ok + 1 < err {
168            let mid = (ok + err) / 2;
169            if self.range(..mid).hash() == other.range(..mid).hash() {
170                ok = mid;
171            } else {
172                err = mid;
173            }
174        }
175        ok
176    }
177    pub fn chainable(self) -> HashedRangeChained<'a, Hasher> {
178        vec![self].into()
179    }
180}
181
182pub struct HashedRangeChained<'a, Hasher>
183where
184    Hasher: RollingHasher + ?Sized,
185{
186    chained: Vec<HashedRange<'a, Hasher>>,
187    _marker: PhantomData<fn() -> Hasher>,
188}
189
190impl<Hasher: Debug> Debug for HashedRangeChained<'_, Hasher>
191where
192    Hasher: RollingHasher + ?Sized,
193    Hasher::Hash: Debug,
194{
195    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
196        f.debug_struct("HashedRangeChained")
197            .field("chained", &self.chained)
198            .finish()
199    }
200}
201
202impl<Hasher: Default> Default for HashedRangeChained<'_, Hasher>
203where
204    Hasher: RollingHasher,
205{
206    fn default() -> Self {
207        Self {
208            chained: Default::default(),
209            _marker: Default::default(),
210        }
211    }
212}
213
214impl<Hasher: Clone> Clone for HashedRangeChained<'_, Hasher>
215where
216    Hasher: RollingHasher,
217{
218    fn clone(&self) -> Self {
219        Self {
220            chained: self.chained.clone(),
221            _marker: self._marker,
222        }
223    }
224}
225
226impl<Hasher> PartialEq for HashedRangeChained<'_, Hasher>
227where
228    Hasher: RollingHasher + ?Sized,
229{
230    fn eq(&self, other: &Self) -> bool {
231        let mut a = self.chained.iter().cloned();
232        let mut b = other.chained.iter().cloned();
233        macro_rules! next {
234            ($iter:expr) => {
235                loop {
236                    if let Some(x) = $iter.next() {
237                        if x.len() > 0 {
238                            break Some(x);
239                        }
240                    } else {
241                        break None;
242                    }
243                }
244            };
245        }
246        let mut x: Option<HashedRange<'_, Hasher>> = None;
247        let mut y: Option<HashedRange<'_, Hasher>> = None;
248        loop {
249            if x.map_or(true, |x| x.is_empty()) {
250                x = next!(a);
251            }
252            if y.map_or(true, |y| y.is_empty()) {
253                y = next!(b);
254            }
255            if let (Some(x), Some(y)) = (&mut x, &mut y) {
256                let k = x.len().min(y.len());
257                if x.range(..k) != y.range(..k) {
258                    return false;
259                }
260                *x = x.range(k..);
261                *y = y.range(k..);
262            } else {
263                break x.is_none() == y.is_none();
264            }
265        }
266    }
267}
268
269impl<Hasher> Eq for HashedRangeChained<'_, Hasher> where Hasher: RollingHasher + ?Sized {}
270
271impl<Hasher> PartialOrd for HashedRangeChained<'_, Hasher>
272where
273    Hasher: RollingHasher + ?Sized,
274    Hasher::Hash: PartialOrd,
275{
276    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
277        let mut a = self.chained.iter().cloned();
278        let mut b = other.chained.iter().cloned();
279        macro_rules! next {
280            ($iter:expr) => {
281                loop {
282                    if let Some(x) = $iter.next() {
283                        if x.len() > 0 {
284                            break Some(x);
285                        }
286                    } else {
287                        break None;
288                    }
289                }
290            };
291        }
292        let mut x: Option<HashedRange<'_, Hasher>> = None;
293        let mut y: Option<HashedRange<'_, Hasher>> = None;
294        loop {
295            if x.map_or(true, |x| x.is_empty()) {
296                x = next!(a);
297            }
298            if y.map_or(true, |y| y.is_empty()) {
299                y = next!(b);
300            }
301            if let (Some(x), Some(y)) = (&mut x, &mut y) {
302                let k = x.longest_common_prefix(y);
303                if x.len() > k && y.len() > k {
304                    let x = x.hash_range(k..=k);
305                    let y = y.hash_range(k..=k);
306                    break x.hash.partial_cmp(&y.hash);
307                };
308                *x = x.range(k..);
309                *y = y.range(k..);
310            } else {
311                break x.is_some().partial_cmp(&y.is_some());
312            }
313        }
314    }
315}
316
317impl<Hasher> Ord for HashedRangeChained<'_, Hasher>
318where
319    Hasher: RollingHasher + ?Sized,
320    Hasher::Hash: Ord,
321{
322    fn cmp(&self, other: &Self) -> Ordering {
323        let mut a = self.chained.iter().cloned();
324        let mut b = other.chained.iter().cloned();
325        macro_rules! next {
326            ($iter:expr) => {
327                loop {
328                    if let Some(x) = $iter.next() {
329                        if x.len() > 0 {
330                            break Some(x);
331                        }
332                    } else {
333                        break None;
334                    }
335                }
336            };
337        }
338        let mut x: Option<HashedRange<'_, Hasher>> = None;
339        let mut y: Option<HashedRange<'_, Hasher>> = None;
340        loop {
341            if x.map_or(true, |x| x.is_empty()) {
342                x = next!(a);
343            }
344            if y.map_or(true, |y| y.is_empty()) {
345                y = next!(b);
346            }
347            if let (Some(x), Some(y)) = (&mut x, &mut y) {
348                let k = x.longest_common_prefix(y);
349                if x.len() > k && y.len() > k {
350                    let x = x.hash_range(k..=k);
351                    let y = y.hash_range(k..=k);
352                    break x.hash.cmp(&y.hash);
353                };
354                *x = x.range(k..);
355                *y = y.range(k..);
356            } else {
357                break x.is_some().cmp(&y.is_some());
358            }
359        }
360    }
More examples
Hide additional examples
crates/library_checker/src/string/zalgorithm.rs (line 21)
15pub fn zalgorithm_rolling_hash(reader: impl Read, mut writer: impl Write) {
16    let s = read_all_unchecked(reader);
17    let mut scanner = Scanner::new(&s);
18    scan!(scanner, s: Bytes);
19    Mersenne61x1::init(s.len());
20    let h = Mersenne61x1::hash_sequence(s.iter().map(|&c| c as _));
21    let ans = (0..s.len()).map(|i| h.range(..).longest_common_prefix(&h.range(i..)));
22    iter_print!(writer, @it ans);
23}
Source

pub fn chainable(self) -> HashedRangeChained<'a, Hasher>

Trait Implementations§

Source§

impl<Hasher> Clone for HashedRange<'_, Hasher>
where Hasher: RollingHasher + ?Sized,

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<'a, Hasher> Debug for HashedRange<'a, Hasher>
where Hasher: RollingHasher + ?Sized + Debug, Hasher::Hash: Debug,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<Hasher> Ord for HashedRange<'_, Hasher>
where Hasher: RollingHasher + ?Sized, Hasher::Hash: Ord,

Source§

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other. Read more
1.21.0 · Source§

fn max(self, other: Self) -> Self
where Self: Sized,

Compares and returns the maximum of two values. Read more
1.21.0 · Source§

fn min(self, other: Self) -> Self
where Self: Sized,

Compares and returns the minimum of two values. Read more
1.50.0 · Source§

fn clamp(self, min: Self, max: Self) -> Self
where Self: Sized,

Restrict a value to a certain interval. Read more
Source§

impl<Hasher> PartialEq for HashedRange<'_, Hasher>
where Hasher: RollingHasher + ?Sized,

Source§

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.
1.0.0 · Source§

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.
Source§

impl<Hasher> PartialOrd for HashedRange<'_, Hasher>
where Hasher: RollingHasher + ?Sized, Hasher::Hash: PartialOrd,

Source§

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists. Read more
1.0.0 · Source§

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator. Read more
1.0.0 · Source§

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator. Read more
1.0.0 · Source§

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator. Read more
1.0.0 · Source§

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator. Read more
Source§

impl<Hasher> Copy for HashedRange<'_, Hasher>
where Hasher: RollingHasher + ?Sized,

Source§

impl<Hasher> Eq for HashedRange<'_, Hasher>
where Hasher: RollingHasher + ?Sized,

Auto Trait Implementations§

§

impl<'a, Hasher> Freeze for HashedRange<'a, Hasher>
where Hasher: ?Sized,

§

impl<'a, Hasher> RefUnwindSafe for HashedRange<'a, Hasher>
where <Hasher as RollingHasher>::Hash: RefUnwindSafe, Hasher: ?Sized,

§

impl<'a, Hasher> Send for HashedRange<'a, Hasher>
where <Hasher as RollingHasher>::Hash: Sync, Hasher: ?Sized,

§

impl<'a, Hasher> Sync for HashedRange<'a, Hasher>
where <Hasher as RollingHasher>::Hash: Sync, Hasher: ?Sized,

§

impl<'a, Hasher> Unpin for HashedRange<'a, Hasher>
where Hasher: ?Sized,

§

impl<'a, Hasher> UnwindSafe for HashedRange<'a, Hasher>
where <Hasher as RollingHasher>::Hash: RefUnwindSafe, Hasher: ?Sized,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> AsTotalOrd for T
where T: PartialOrd,

Source§

fn as_total_ord(&self) -> TotalOrd<&T>

Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> PartialOrdExt for T
where T: PartialOrd,

Source§

fn chmin(&mut self, other: T)

Source§

fn chmax(&mut self, other: T)

Source§

fn minmax(self, other: T) -> (T, T)

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.