Struct CeilQuotientIndex

Source

pub struct CeilQuotientIndex {
    num: usize,
    sqrt: usize,
    pivot: usize,
}

Expand description

sorted({ ceil(n/k) | k in [1, n] })

Fields§

§num: usize§sqrt: usize§pivot: usize

Implementations§

Source §

impl CeilQuotientIndex

Source

pub fn new(num: usize) -> Self

Source

pub fn values( &self, ) -> impl ExactSizeIterator<Item = usize> + FusedIterator + '_

Source

pub fn key_values( &self, ) -> impl ExactSizeIterator<Item = (RangeInclusive<usize>, usize)> + FusedIterator + '_

Source

pub fn len(&self) -> usize

Examples found in repository ?

crates/competitive/src/algorithm/quotient_index.rs (line 164)

163    pub fn values(&self) -> impl ExactSizeIterator<Item = usize> + FusedIterator + '_ {
164        let len = self.len();
165        (0..len).map(move |index| unsafe { self.index_to_value_unchecked(index) })
166    }
167
168    pub fn key_values(
169        &self,
170    ) -> impl ExactSizeIterator<Item = (RangeInclusive<usize>, usize)> + FusedIterator + '_ {
171        let len = self.len();
172        (0..len).map(move |index| unsafe {
173            (
174                self.index_to_key_unchecked(index),
175                self.index_to_value_unchecked(index),
176            )
177        })
178    }
179
180    #[allow(clippy::len_without_is_empty)]
181    pub fn len(&self) -> usize {
182        self.sqrt + self.pivot - 1
183    }
184
185    pub fn contains_key(&self, key: usize) -> bool {
186        (1..=self.num).contains(&key)
187    }
188
189    pub fn contains_value(&self, value: usize) -> bool {
190        if value == 0 || value > self.num {
191            return false;
192        }
193        if value == 1 {
194            return true;
195        }
196        let start = self.num.div_ceil(value);
197        let end = (self.num - 1) / (value - 1);
198        start <= end
199    }
200
201    pub fn index_to_key(&self, index: usize) -> RangeInclusive<usize> {
202        assert!(index < self.len(), "index out of bounds");
203        unsafe { self.index_to_key_unchecked(index) }
204    }
205
206    pub fn index_to_value(&self, index: usize) -> usize {
207        assert!(index < self.len(), "index out of bounds");
208        unsafe { self.index_to_value_unchecked(index) }
209    }
210
211    pub fn value_to_index(&self, value: usize) -> usize {
212        assert!(self.contains_value(value), "value is not present");
213        unsafe { self.value_to_index_unchecked(value) }
214    }
215
216    pub fn value_to_key(&self, value: usize) -> RangeInclusive<usize> {
217        assert!(self.contains_value(value), "value is not present");
218        unsafe { self.value_to_key_unchecked(value) }
219    }
220
221    pub fn key_to_index(&self, key: usize) -> usize {
222        assert!(self.contains_key(key), "key out of bounds");
223        let value = self.key_to_value(key);
224        unsafe { self.value_to_index_unchecked(value) }
225    }
226
227    pub fn key_to_value(&self, key: usize) -> usize {
228        assert!(self.contains_key(key), "key out of bounds");
229        unsafe { self.key_to_value_unchecked(key) }
230    }
231
232    /// # Safety
233    /// `index` must satisfy `index < self.len()`.
234    pub unsafe fn index_to_key_unchecked(&self, index: usize) -> RangeInclusive<usize> {
235        if index < self.pivot {
236            if index == 0 {
237                return self.num..=self.num;
238            }
239            let start = self.num.div_ceil(index + 1);
240            let end = (self.num - 1) / index;
241            start..=end
242        } else {
243            let key = self.len() - index;
244            key..=key
245        }
246    }
247
248    /// # Safety
249    /// `index` must satisfy `index < self.len()`.
250    pub unsafe fn index_to_value_unchecked(&self, index: usize) -> usize {
251        if index < self.pivot {
252            index + 1
253        } else {
254            self.num.div_ceil(self.len() - index)
255        }
256    }
257
258    /// # Safety
259    /// `value` must satisfy `self.contains_value(value)`.
260    pub unsafe fn value_to_index_unchecked(&self, value: usize) -> usize {
261        if value <= self.pivot {
262            value - 1
263        } else {
264            self.len() - (self.num - 1) / (value - 1)
265        }
266    }
267
268    /// # Safety
269    /// `value` must satisfy `self.contains_value(value)`.
270    pub unsafe fn value_to_key_unchecked(&self, value: usize) -> RangeInclusive<usize> {
271        if value == 1 {
272            return self.num..=self.num;
273        }
274        let start = self.num.div_ceil(value);
275        let end = (self.num - 1) / (value - 1);
276        start..=end
277    }
278
279    /// # Safety
280    /// `key` must satisfy `1 <= key && key <= self.num`.
281    pub unsafe fn key_to_index_unchecked(&self, key: usize) -> usize {
282        if key < self.sqrt {
283            self.len() - key
284        } else {
285            self.num.div_ceil(key) - 1
286        }
287    }

Source

pub fn contains_key(&self, key: usize) -> bool

Examples found in repository ?

crates/competitive/src/algorithm/quotient_index.rs (line 222)

221    pub fn key_to_index(&self, key: usize) -> usize {
222        assert!(self.contains_key(key), "key out of bounds");
223        let value = self.key_to_value(key);
224        unsafe { self.value_to_index_unchecked(value) }
225    }
226
227    pub fn key_to_value(&self, key: usize) -> usize {
228        assert!(self.contains_key(key), "key out of bounds");
229        unsafe { self.key_to_value_unchecked(key) }
230    }

Source

pub fn contains_value(&self, value: usize) -> bool

Examples found in repository ?

crates/competitive/src/algorithm/quotient_index.rs (line 212)

211    pub fn value_to_index(&self, value: usize) -> usize {
212        assert!(self.contains_value(value), "value is not present");
213        unsafe { self.value_to_index_unchecked(value) }
214    }
215
216    pub fn value_to_key(&self, value: usize) -> RangeInclusive<usize> {
217        assert!(self.contains_value(value), "value is not present");
218        unsafe { self.value_to_key_unchecked(value) }
219    }

Source

pub fn key_to_value(&self, key: usize) -> usize

Examples found in repository ?

crates/competitive/src/algorithm/quotient_index.rs (line 223)

221    pub fn key_to_index(&self, key: usize) -> usize {
222        assert!(self.contains_key(key), "key out of bounds");
223        let value = self.key_to_value(key);
224        unsafe { self.value_to_index_unchecked(value) }
225    }

Source

pub unsafe fn index_to_key_unchecked( &self, index: usize, ) -> RangeInclusive<usize>

§Safety

index must satisfy index < self.len().

Examples found in repository ?

crates/competitive/src/algorithm/quotient_index.rs (line 174)

168    pub fn key_values(
169        &self,
170    ) -> impl ExactSizeIterator<Item = (RangeInclusive<usize>, usize)> + FusedIterator + '_ {
171        let len = self.len();
172        (0..len).map(move |index| unsafe {
173            (
174                self.index_to_key_unchecked(index),
175                self.index_to_value_unchecked(index),
176            )
177        })
178    }
179
180    #[allow(clippy::len_without_is_empty)]
181    pub fn len(&self) -> usize {
182        self.sqrt + self.pivot - 1
183    }
184
185    pub fn contains_key(&self, key: usize) -> bool {
186        (1..=self.num).contains(&key)
187    }
188
189    pub fn contains_value(&self, value: usize) -> bool {
190        if value == 0 || value > self.num {
191            return false;
192        }
193        if value == 1 {
194            return true;
195        }
196        let start = self.num.div_ceil(value);
197        let end = (self.num - 1) / (value - 1);
198        start <= end
199    }
200
201    pub fn index_to_key(&self, index: usize) -> RangeInclusive<usize> {
202        assert!(index < self.len(), "index out of bounds");
203        unsafe { self.index_to_key_unchecked(index) }
204    }

Source

pub unsafe fn index_to_value_unchecked(&self, index: usize) -> usize

§Safety

index must satisfy index < self.len().

Examples found in repository ?

crates/competitive/src/algorithm/quotient_index.rs (line 165)

163    pub fn values(&self) -> impl ExactSizeIterator<Item = usize> + FusedIterator + '_ {
164        let len = self.len();
165        (0..len).map(move |index| unsafe { self.index_to_value_unchecked(index) })
166    }
167
168    pub fn key_values(
169        &self,
170    ) -> impl ExactSizeIterator<Item = (RangeInclusive<usize>, usize)> + FusedIterator + '_ {
171        let len = self.len();
172        (0..len).map(move |index| unsafe {
173            (
174                self.index_to_key_unchecked(index),
175                self.index_to_value_unchecked(index),
176            )
177        })
178    }
179
180    #[allow(clippy::len_without_is_empty)]
181    pub fn len(&self) -> usize {
182        self.sqrt + self.pivot - 1
183    }
184
185    pub fn contains_key(&self, key: usize) -> bool {
186        (1..=self.num).contains(&key)
187    }
188
189    pub fn contains_value(&self, value: usize) -> bool {
190        if value == 0 || value > self.num {
191            return false;
192        }
193        if value == 1 {
194            return true;
195        }
196        let start = self.num.div_ceil(value);
197        let end = (self.num - 1) / (value - 1);
198        start <= end
199    }
200
201    pub fn index_to_key(&self, index: usize) -> RangeInclusive<usize> {
202        assert!(index < self.len(), "index out of bounds");
203        unsafe { self.index_to_key_unchecked(index) }
204    }
205
206    pub fn index_to_value(&self, index: usize) -> usize {
207        assert!(index < self.len(), "index out of bounds");
208        unsafe { self.index_to_value_unchecked(index) }
209    }

Source

pub unsafe fn value_to_index_unchecked(&self, value: usize) -> usize

§Safety

value must satisfy self.contains_value(value).

Examples found in repository ?

crates/competitive/src/algorithm/quotient_index.rs (line 213)

211    pub fn value_to_index(&self, value: usize) -> usize {
212        assert!(self.contains_value(value), "value is not present");
213        unsafe { self.value_to_index_unchecked(value) }
214    }
215
216    pub fn value_to_key(&self, value: usize) -> RangeInclusive<usize> {
217        assert!(self.contains_value(value), "value is not present");
218        unsafe { self.value_to_key_unchecked(value) }
219    }
220
221    pub fn key_to_index(&self, key: usize) -> usize {
222        assert!(self.contains_key(key), "key out of bounds");
223        let value = self.key_to_value(key);
224        unsafe { self.value_to_index_unchecked(value) }
225    }

Source

pub unsafe fn value_to_key_unchecked( &self, value: usize, ) -> RangeInclusive<usize>

§Safety

value must satisfy self.contains_value(value).

Examples found in repository ?

crates/competitive/src/algorithm/quotient_index.rs (line 218)

216    pub fn value_to_key(&self, value: usize) -> RangeInclusive<usize> {
217        assert!(self.contains_value(value), "value is not present");
218        unsafe { self.value_to_key_unchecked(value) }
219    }

Source

pub unsafe fn key_to_index_unchecked(&self, key: usize) -> usize

§Safety

key must satisfy 1 <= key && key <= self.num.

Source

pub unsafe fn key_to_value_unchecked(&self, key: usize) -> usize

§Safety

key must satisfy 1 <= key && key <= self.num.

Examples found in repository ?

crates/competitive/src/algorithm/quotient_index.rs (line 229)

227    pub fn key_to_value(&self, key: usize) -> usize {
228        assert!(self.contains_key(key), "key out of bounds");
229        unsafe { self.key_to_value_unchecked(key) }
230    }