HashedRange

competitive::string::rolling_hash

Struct HashedRange 

Source 
pub struct HashedRange<'a, Hasher>
where
    Hasher: RollingHasher + ?Sized,
{
    hashed: &'a [Hasher::Hash],
    _marker: PhantomData<fn() -> Hasher>,
}

Fields§

§hashed: &'a [Hasher::Hash]§_marker: PhantomData<fn() -> Hasher>

Implementations§

Source§

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

Source

fn new(hashed: &'a [Hasher::Hash]) -> Self

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    }
Source

pub fn len(&self) -> usize

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

pub fn is_empty(&self) -> bool

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

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

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

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<Hash: PartialOrd> + ?Sized,

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.