offset_vec/lib.rs
1#![doc = include_str!("../README.md")]
2#![no_std]
3#![cfg_attr(docsrs, feature(doc_cfg))]
4
5extern crate alloc;
6
7#[cfg(doc)]
8use alloc::{vec::Vec, string::String};
9
10use core::{
11 iter::once,
12 ops::{Bound, Deref, DerefMut, Index, IndexMut, Range, RangeBounds},
13 slice::SliceIndex,
14};
15
16mod util;
17mod slice;
18mod offset;
19mod vec_like;
20
21pub use slice::*;
22pub use offset::*;
23pub use vec_like::*;
24
25mod externs {
26 mod core_impls;
27}
28
29/// Packer for [`Vec`] and [`String`] etc
30///
31/// For all methods index add a `offset`
32///
33/// Create from [`Offset::offset`] or [`create`]
34///
35/// # Examples
36///
37/// ```
38/// use offset_vec::Offset;
39///
40/// let mut vec = vec![0, 1, 2, 3, 4];
41/// let mut vec1 = vec.offset_mut(2);
42///
43/// assert_eq!(vec1, [2, 3, 4]);
44/// assert_eq!(vec1[1], 3);
45///
46/// vec1[1] += 2;
47/// assert_eq!(vec, [0, 1, 2, 5, 4]);
48/// ```
49#[derive(Debug, Clone, Default)]
50pub struct OffsetVec<V: VecLike> {
51 vec: V,
52 offset: usize,
53}
54
55impl<V: VecLike> Deref for OffsetVec<V> {
56 type Target = V::Slice;
57
58 #[inline]
59 fn deref(&self) -> &Self::Target {
60 let offset = self.offset;
61 let slice = self.vec.as_slice();
62 &slice[offset..]
63 }
64}
65
66impl<V: VecLike> DerefMut for OffsetVec<V> {
67 #[inline]
68 fn deref_mut(&mut self) -> &mut Self::Target {
69 let offset = self.offset;
70 let slice_mut = self.vec.as_mut_slice();
71 &mut slice_mut[offset..]
72 }
73}
74
75impl<V, I> Index<I> for OffsetVec<V>
76where V: VecLike,
77 I: SliceIndex<V::Slice>,
78 V::Slice: Index<I>,
79{
80 type Output = <V::Slice as Index<I>>::Output;
81
82 #[track_caller]
83 fn index(&self, index: I) -> &Self::Output {
84 let slice = &**self;
85 &slice[index]
86 }
87}
88
89impl<V, I> IndexMut<I> for OffsetVec<V>
90where V: VecLike,
91 I: SliceIndex<V::Slice>,
92 V::Slice: IndexMut<I>,
93{
94 #[track_caller]
95 fn index_mut(&mut self, index: I) -> &mut Self::Output {
96 let slice = &mut **self;
97 &mut slice[index]
98 }
99}
100
101impl<V: VecLike> OffsetVec<V> {
102 /// Get original vector
103 ///
104 /// # Examples
105 ///
106 /// ```
107 /// use offset_vec::Offset;
108 ///
109 /// let mut vec = vec![0, 1, 2, 3, 4];
110 /// let mut vec1 = vec.offset_mut(2);
111 ///
112 /// assert_eq!(vec1, [2, 3, 4]);
113 /// assert_eq!(vec1.origin_vec(), &&mut vec![0, 1, 2, 3, 4]);
114 /// ```
115 #[inline]
116 pub fn origin_vec(&self) -> &V {
117 &self.vec
118 }
119
120 /// Get mutable original vector
121 ///
122 /// # Examples
123 ///
124 /// ```
125 /// use offset_vec::Offset;
126 ///
127 /// let mut vec = vec![0, 1, 2, 3, 4];
128 /// let mut vec1 = vec.offset_mut(2);
129 ///
130 /// assert_eq!(vec1, [2, 3, 4]);
131 /// assert_eq!(vec1.origin_vec_mut(), &mut &mut vec![0, 1, 2, 3, 4]);
132 ///
133 /// vec1.origin_vec_mut()[3] += 2;
134 /// assert_eq!(vec1, [2, 5, 4]);
135 /// ```
136 #[inline]
137 pub fn origin_vec_mut(&mut self) -> &mut V {
138 &mut self.vec
139 }
140
141 /// Consume [`OffsetVec`] into packed original vector
142 ///
143 /// # Examples
144 ///
145 /// ```
146 /// use offset_vec::Offset;
147 ///
148 /// let vec = vec![0, 1, 2, 3, 4];
149 /// let mut vec1 = vec.offset(2);
150 ///
151 /// assert_eq!(vec1, [2, 3, 4]);
152 /// assert_eq!(vec1.into_origin_vec(), vec![0, 1, 2, 3, 4]);
153 /// ```
154 #[inline]
155 pub fn into_origin_vec(self) -> V {
156 self.vec
157 }
158
159 /// Extracts a slice containing the offset vector.
160 ///
161 /// Equivalent to &s[..].
162 ///
163 /// # Examples
164 ///
165 /// ```
166 /// use offset_vec::Offset;
167 ///
168 /// let vec = vec![0, 1, 2, 3, 4];
169 /// let mut vec1 = vec.offset(2);
170 ///
171 /// assert_eq!(vec1.as_slice(), &[2, 3, 4]);
172 /// assert_eq!(&vec1[..], &[2, 3, 4]);
173 /// ```
174 #[inline]
175 pub fn as_slice(&self) -> &V::Slice {
176 self
177 }
178
179 /// Extracts a mutable slice containing the offset vector.
180 ///
181 /// Equivalent to &mut s[..].
182 ///
183 /// # Examples
184 ///
185 /// ```
186 /// use offset_vec::Offset;
187 ///
188 /// let vec = vec![0, 1, 2, 3, 4];
189 /// let mut vec1 = vec.offset(2);
190 ///
191 /// assert_eq!(vec1.as_mut_slice(), &mut [2, 3, 4]);
192 /// assert_eq!(&mut vec1[..], &mut [2, 3, 4]);
193 /// ```
194 #[inline]
195 pub fn as_mut_slice(&mut self) -> &mut V::Slice {
196 self
197 }
198
199 /// Immutable iterator
200 ///
201 /// # Examples
202 ///
203 /// ```
204 /// use offset_vec::Offset;
205 ///
206 /// let vec = vec![0, 1, 2, 3, 4];
207 /// let vec1 = vec.offset(2);
208 ///
209 /// let x: Vec<_> = vec1.iter().collect();
210 /// assert_eq!(x, [&2, &3, &4]);
211 /// ```
212 pub fn iter<'a>(&'a self) -> <&'a V::Slice as IntoIterator>::IntoIter
213 where &'a V::Slice: IntoIterator
214 {
215 self.as_slice().into_iter()
216 }
217
218 /// Mutable iterator
219 ///
220 /// # Examples
221 ///
222 /// ```
223 /// use offset_vec::Offset;
224 ///
225 /// let mut vec = vec![0, 1, 2, 3, 4];
226 /// let mut vec1 = vec.offset_mut(2);
227 ///
228 /// let mut x: Vec<_> = vec1.iter_mut().collect();
229 /// assert_eq!(x, [&mut 2, &mut 3, &mut 4]);
230 /// *x[1] += 2;
231 ///
232 /// assert_eq!(vec1, [2, 5, 4]);
233 /// assert_eq!(vec, [0, 1, 2, 5, 4]);
234 /// ```
235 pub fn iter_mut<'a>(&'a mut self) -> <&'a mut V::Slice as IntoIterator>::IntoIter
236 where &'a mut V::Slice: IntoIterator
237 {
238 self.as_mut_slice().into_iter()
239 }
240
241 /// `self.len() == 0`
242 #[inline]
243 pub fn is_empty(&self) -> bool {
244 self.len() == 0
245 }
246
247 /// Get offset vector length
248 ///
249 /// # Examples
250 ///
251 /// ```
252 /// use offset_vec::Offset;
253 ///
254 /// let vec = vec![0, 1, 2, 3, 4];
255 /// let mut vec1 = vec.offset(2);
256 ///
257 /// assert_eq!(vec1.len(), 3);
258 /// assert_eq!(vec1.origin_vec().len(), 5);
259 /// ```
260 #[inline]
261 pub fn len(&self) -> usize {
262 self.vec.len() - self.offset
263 }
264
265 /// Get offset vector capacity
266 ///
267 /// # Examples
268 ///
269 /// ```
270 /// use offset_vec::Offset;
271 ///
272 /// let mut vec = Vec::with_capacity(5);
273 /// vec.extend([0, 1, 2, 3, 4]);
274 /// let mut vec1 = vec.offset(2);
275 ///
276 /// assert_eq!(3, vec1.capacity());
277 /// assert_eq!(5, vec1.origin_vec().capacity());
278 /// ```
279 #[inline]
280 pub fn capacity(&self) -> usize {
281 self.vec.capacity() - self.offset
282 }
283
284 pub fn reserve(&mut self, additional: usize) {
285 self.vec.reserve(additional);
286 }
287
288 pub fn reserve_exact(&mut self, additional: usize) {
289 self.vec.reserve_exact(additional);
290 }
291
292 pub fn shrink_to_fit(&mut self) {
293 self.vec.shrink_to_fit();
294 }
295
296 pub fn shrink_to(&mut self, min_capacity: usize) {
297 self.vec.shrink_to(min_capacity);
298 }
299
300 /// Get offset
301 ///
302 /// # Examples
303 ///
304 /// ```
305 /// use offset_vec::Offset;
306 ///
307 /// let vec = vec![0, 1, 2, 3, 4];
308 /// let vec1 = vec.offset(2);
309 ///
310 /// assert_eq!(vec1.origin_offset(), 2);
311 ///
312 /// let vec2 = vec1.offset(1);
313 /// assert_eq!(vec2.origin_offset(), 3);
314 /// ```
315 pub fn origin_offset(&self) -> usize {
316 self.offset
317 }
318
319 /// Push a value
320 ///
321 /// # Examples
322 ///
323 /// ```
324 /// use offset_vec::Offset;
325 ///
326 /// let mut vec = vec![0, 1, 2, 3, 4];
327 /// let mut vec1 = vec.offset_mut(2);
328 ///
329 /// assert_eq!(vec1, [2, 3, 4]);
330 /// vec1.push(5);
331 /// assert_eq!(vec1, [2, 3, 4, 5]);
332 /// assert_eq!(vec, [0, 1, 2, 3, 4, 5]);
333 /// ```
334 pub fn push(&mut self, value: V::Elem) {
335 self.vec.push(value);
336 }
337
338 /// Pop a value
339 ///
340 /// # Examples
341 ///
342 /// ```
343 /// use offset_vec::Offset;
344 ///
345 /// let mut vec = vec![0, 1, 2, 3];
346 /// let mut vec1 = vec.offset_mut(2);
347 ///
348 /// assert_eq!(vec1, [2, 3]);
349 /// assert_eq!(vec1.pop(), Some(3));
350 /// assert_eq!(vec1, [2]);
351 /// assert_eq!(vec1.pop(), Some(2));
352 /// assert_eq!(vec1, []);
353 /// assert_eq!(vec1.pop(), None);
354 /// assert_eq!(vec1, []);
355 ///
356 /// assert_eq!(vec1.origin_vec(), &&mut [0, 1]);
357 /// assert_eq!(vec, [0, 1]);
358 /// ```
359 pub fn pop(&mut self) -> Option<V::Elem> {
360 if self.is_empty() {
361 return None;
362 }
363
364 self.vec.pop()
365 }
366
367 /// Remove a value at index, shifting all elements after it to the left.
368 ///
369 /// # Examples
370 ///
371 /// ```
372 /// use offset_vec::Offset;
373 ///
374 /// let mut vec = vec![0, 1, 2, 3, 4, 5];
375 /// let mut vec1 = vec.offset_mut(2);
376 ///
377 /// assert_eq!(vec1, [2, 3, 4, 5]);
378 /// assert_eq!(vec1.remove(1), 3);
379 /// assert_eq!(vec1, [2, 4, 5]);
380 ///
381 /// assert_eq!(vec, [0, 1, 2, 4, 5]);
382 /// ```
383 #[track_caller]
384 pub fn remove(&mut self, index: usize) -> V::Elem {
385 let len = self.len();
386 if index > len {
387 index_out_of_range(index, self.offset, len)
388 }
389 self.vec.remove(index + self.offset)
390 }
391
392 /// Insert a value before index, shifting all elements after it to the right.
393 ///
394 /// # Examples
395 ///
396 /// ```
397 /// use offset_vec::Offset;
398 ///
399 /// let mut vec = vec![0, 1, 2, 4, 5];
400 /// let mut vec1 = vec.offset_mut(2);
401 ///
402 /// assert_eq!(vec1, [2, 4, 5]);
403 /// vec1.insert(1, 3);
404 /// assert_eq!(vec1, [2, 3, 4, 5]);
405 /// vec1.insert(4, 6);
406 /// assert_eq!(vec1, [2, 3, 4, 5, 6]);
407 ///
408 /// assert_eq!(vec, [0, 1, 2, 3, 4, 5, 6]);
409 /// ```
410 #[track_caller]
411 pub fn insert(&mut self, index: usize, elem: V::Elem) {
412 let len = self.len();
413 if index > len {
414 index_out_of_range(index, self.offset, len)
415 }
416 self.vec.insert(index + self.offset, elem)
417 }
418
419 /// Truncate to length
420 ///
421 /// # Examples
422 ///
423 /// ```
424 /// use offset_vec::Offset;
425 ///
426 /// let mut vec = vec![0, 1, 2, 3, 4, 5];
427 /// let mut vec1 = vec.offset_mut(2);
428 ///
429 /// assert_eq!(vec1, [2, 3, 4, 5]);
430 ///
431 /// vec1.truncate(2);
432 ///
433 /// assert_eq!(vec1, [2, 3]);
434 /// assert_eq!(vec, [0, 1, 2, 3]);
435 /// ```
436 pub fn truncate(&mut self, len: usize) {
437 self.vec.truncate(len + self.offset);
438 }
439
440 /// Append and clear other collection
441 ///
442 /// # Examples
443 ///
444 /// ```
445 /// use offset_vec::Offset;
446 ///
447 /// let mut vec = vec![0, 1, 2, 3];
448 /// let mut vec1 = vec.offset_mut(2);
449 /// let mut other = vec![4, 5];
450 ///
451 /// assert_eq!(vec1, [2, 3]);
452 /// vec1.append(&mut other);
453 ///
454 /// assert_eq!(other, []);
455 /// assert_eq!(vec1, [2, 3, 4, 5]);
456 /// assert_eq!(vec, [0, 1, 2, 3, 4, 5]);
457 /// ```
458 pub fn append(&mut self, other: &mut V::Collection) {
459 self.vec.append(other);
460 }
461
462 /// Clear all elements (offset)
463 ///
464 /// # Examples
465 ///
466 /// ```
467 /// use offset_vec::Offset;
468 ///
469 /// let mut vec = vec![0, 1, 2, 3, 4];
470 /// let mut vec1 = vec.offset_mut(2);
471 ///
472 /// assert_eq!(vec1, [2, 3, 4]);
473 ///
474 /// vec1.clear();
475 ///
476 /// assert_eq!(vec1, []);
477 /// assert_eq!(vec, [0, 1]);
478 /// ```
479 pub fn clear(&mut self) {
480 self.vec.truncate(self.offset);
481 }
482
483 #[track_caller]
484 fn map_range<R: RangeBounds<usize>>(&self, range: R) -> Range<usize> {
485 let start = match range.start_bound() {
486 Bound::Included(&n) => n,
487 Bound::Excluded(&n) => n.checked_add(1).expect("start range overflow"),
488 Bound::Unbounded => 0,
489 };
490 let end = match range.end_bound() {
491 Bound::Included(&n) => n.checked_add(1).expect("end range overflow"),
492 Bound::Excluded(&n) => n,
493 Bound::Unbounded => self.len(),
494 };
495 if start > end {
496 #[cold]
497 #[track_caller]
498 #[inline(never)]
499 fn fail(index: usize, end: usize) -> ! {
500 panic!("range index starts at {index} but ends at {end}");
501 }
502 fail(start, end)
503 }
504 if end > self.len() {
505 #[cold]
506 #[track_caller]
507 #[inline(never)]
508 fn fail(index: usize, len: usize) -> ! {
509 panic!("range end index {index} out of range for slice of length {len}");
510 }
511 fail(end, self.len())
512 }
513 let offset = self.offset;
514 Range { start: start+offset, end: end+offset }
515 }
516
517 /// Drain range elements
518 ///
519 /// # Examples
520 ///
521 /// ```
522 /// use offset_vec::Offset;
523 ///
524 /// let mut vec = vec![0, 1, 2, 3, 4, 5, 6];
525 /// let mut vec1 = vec.offset_mut(2);
526 ///
527 /// assert_eq!(vec1, [2, 3, 4, 5, 6]);
528 ///
529 /// let drain = vec1.drain(2..4).collect::<Vec<_>>();
530 ///
531 /// assert_eq!(drain, [4, 5]);
532 /// assert_eq!(vec1, [2, 3, 6]);
533 /// assert_eq!(vec, [0, 1, 2, 3, 6]);
534 /// ```
535 #[track_caller]
536 pub fn drain<R: RangeBounds<usize>>(&mut self, range: R) -> V::Drain<'_> {
537 self.vec.drain(self.map_range(range))
538 }
539
540 /// Splits the collection into two at the given index.
541 ///
542 /// # Examples
543 ///
544 /// ```
545 /// use offset_vec::Offset;
546 ///
547 /// let mut vec = vec![0, 1, 2, 3, 4, 5, 6];
548 /// let mut vec1 = vec.offset_mut(2);
549 ///
550 /// assert_eq!(vec1, [2, 3, 4, 5, 6]);
551 ///
552 /// let other = vec1.split_off(3);
553 ///
554 /// assert_eq!(other, [5, 6]);
555 /// assert_eq!(vec1, [2, 3, 4]);
556 /// assert_eq!(vec, [0, 1, 2, 3, 4]);
557 /// ```
558 #[track_caller]
559 #[must_use = "use `.truncate()` if you don't need the other half"]
560 pub fn split_off(&mut self, at: usize) -> V::Collection {
561 let len = self.len();
562 if at > len {
563 index_out_of_range(at, self.offset, len)
564 }
565 self.vec.split_off(at + self.offset)
566 }
567
568 pub fn resize(&mut self, new_len: usize, value: V::Elem)
569 where V::Elem: Clone,
570 {
571 self.vec.resize(new_len+self.offset, value);
572 }
573
574 pub fn resize_with<F>(&mut self, new_len: usize, f: F)
575 where F: FnMut() -> V::Elem,
576 {
577 self.vec.resize_with(new_len+self.offset, f);
578 }
579
580 pub fn retain<F>(&mut self, mut f: F)
581 where F: FnMut(V::ElemRef<'_>) -> bool,
582 {
583 let i = self.vec.as_slice().transform_index(self.offset);
584
585 let mut i = 0..i;
586 self.vec.retain(|elem| {
587 i.next().is_some() || f(elem)
588 });
589 }
590}
591
592impl<V: VecLikeSolid> OffsetVec<V> {
593 pub fn retain_mut<F: FnMut(&mut V::Elem) -> bool>(&mut self, mut f: F) {
594 let mut i = 0..self.offset;
595 self.vec.retain_mut(|elem| {
596 i.next().is_some() || f(elem)
597 });
598 }
599
600 #[track_caller]
601 pub fn swap_remove(&mut self, index: usize) -> V::Elem {
602 let len = self.len();
603 if index > len {
604 index_out_of_range(index, self.offset, len)
605 }
606 self.vec.swap_remove(index + self.offset)
607 }
608
609 pub fn pop_if<F>(&mut self, predicate: F) -> Option<V::Elem>
610 where F: FnOnce(&mut V::Elem) -> bool,
611 {
612 if self.is_empty() {
613 return None;
614 }
615
616 self.vec.pop_if(predicate)
617 }
618}
619
620impl<V: VecLike<Slice = str>> OffsetVec<V> {
621 #[inline]
622 pub fn as_str(&self) -> &str {
623 self
624 }
625
626 #[inline]
627 pub fn as_mut_str(&mut self) -> &mut str {
628 self
629 }
630
631 pub fn push_str<'a>(&mut self, s: &'a str)
632 where V::Collection: Extend<&'a str>,
633 {
634 self.vec.as_mut_collection().extend(once(s));
635 }
636}
637
638#[cold]
639#[track_caller]
640#[inline(never)]
641fn index_out_of_range(index: usize, offset: usize, len: usize) -> ! {
642 panic!("offset index ({index} -> {}) out of length (is {len} -> {})",
643 index+offset,
644 len+offset);
645}