1#![allow(rustdoc::private_intra_doc_links)]
16
17#[cfg(test)]
32macro_rules! assert_items_eq {
33 ( @_ [ $iterator:ident ] { [-] $( $rest:tt )* } { $( $accumulator:tt )* } ) => {
34 assert_items_eq!(
35 @_
36 [ $iterator ]
37 { $( $rest )* }
38 {
39 $( $accumulator )*
40 {
41 let chunk = $iterator .next().expect("next chunk (expect gap)");
42 assert!(chunk.is_gap(), "chunk should be a gap");
43 }
44 }
45 )
46 };
47
48 ( @_ [ $iterator:ident ] { [ $( $item:expr ),* ] $( $rest:tt )* } { $( $accumulator:tt )* } ) => {
49 assert_items_eq!(
50 @_
51 [ $iterator ]
52 { $( $rest )* }
53 {
54 $( $accumulator )*
55 {
56 let chunk = $iterator .next().expect("next chunk (expect items)");
57 assert!(chunk.is_items(), "chunk should contain items");
58
59 let $crate::linked_chunk::ChunkContent::Items(items) = chunk.content() else {
60 unreachable!()
61 };
62
63 let mut items_iterator = items.iter();
64
65 $(
66 assert_eq!(items_iterator.next(), Some(& $item ));
67 )*
68
69 assert!(items_iterator.next().is_none(), "no more items");
70 }
71 }
72 )
73 };
74
75 ( @_ [ $iterator:ident ] {} { $( $accumulator:tt )* } ) => {
76 {
77 $( $accumulator )*
78 assert!( $iterator .next().is_none(), "no more chunks");
79 }
80 };
81
82 ( $linked_chunk:expr, $( $all:tt )* ) => {
83 assert_items_eq!(
84 @_
85 [ iterator ]
86 { $( $all )* }
87 {
88 let mut iterator = $linked_chunk.chunks();
89 }
90 )
91 }
92}
93
94mod as_vector;
95pub mod lazy_loader;
96mod order_tracker;
97pub mod relational;
98mod updates;
99
100use std::{
101 fmt::{self, Display},
102 marker::PhantomData,
103 ptr::NonNull,
104 sync::atomic::{self, AtomicU64},
105};
106
107pub use as_vector::*;
108pub use order_tracker::OrderTracker;
109use ruma::{EventId, OwnedEventId, OwnedRoomId, RoomId};
110use serde::{Deserialize, Serialize};
111pub use updates::*;
112
113#[derive(Debug, Clone, Copy, PartialEq)]
115pub enum LinkedChunkId<'a> {
116 Room(&'a RoomId),
117 Thread(&'a RoomId, &'a EventId),
118}
119
120impl Display for LinkedChunkId<'_> {
121 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
122 match self {
123 Self::Room(room_id) => write!(f, "{room_id}"),
124 Self::Thread(room_id, thread_root) => {
125 write!(f, "{room_id}:thread:{thread_root}")
126 }
127 }
128 }
129}
130
131impl LinkedChunkId<'_> {
132 pub fn storage_key(&self) -> impl '_ + AsRef<[u8]> {
133 match self {
134 LinkedChunkId::Room(room_id) => room_id.to_string(),
135 LinkedChunkId::Thread(room_id, event_id) => format!("t:{room_id}:{event_id}"),
136 }
137 }
138
139 pub fn to_owned(&self) -> OwnedLinkedChunkId {
140 match self {
141 LinkedChunkId::Room(room_id) => OwnedLinkedChunkId::Room((*room_id).to_owned()),
142 LinkedChunkId::Thread(room_id, event_id) => {
143 OwnedLinkedChunkId::Thread((*room_id).to_owned(), (*event_id).to_owned())
144 }
145 }
146 }
147}
148
149impl<'a> From<&'a OwnedLinkedChunkId> for LinkedChunkId<'a> {
150 fn from(value: &'a OwnedLinkedChunkId) -> Self {
151 value.as_ref()
152 }
153}
154
155impl PartialEq<&OwnedLinkedChunkId> for LinkedChunkId<'_> {
156 fn eq(&self, other: &&OwnedLinkedChunkId) -> bool {
157 match (self, other) {
158 (LinkedChunkId::Room(a), OwnedLinkedChunkId::Room(b)) => *a == b,
159 (LinkedChunkId::Thread(r, ev), OwnedLinkedChunkId::Thread(r2, ev2)) => {
160 r == r2 && ev == ev2
161 }
162 (LinkedChunkId::Room(..), OwnedLinkedChunkId::Thread(..))
163 | (LinkedChunkId::Thread(..), OwnedLinkedChunkId::Room(..)) => false,
164 }
165 }
166}
167
168impl PartialEq<LinkedChunkId<'_>> for OwnedLinkedChunkId {
169 fn eq(&self, other: &LinkedChunkId<'_>) -> bool {
170 other.eq(&self)
171 }
172}
173
174#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
176pub enum OwnedLinkedChunkId {
177 Room(OwnedRoomId),
178 Thread(OwnedRoomId, OwnedEventId),
179}
180
181impl Display for OwnedLinkedChunkId {
182 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
183 self.as_ref().fmt(f)
184 }
185}
186
187impl OwnedLinkedChunkId {
188 pub fn as_ref(&self) -> LinkedChunkId<'_> {
189 match self {
190 OwnedLinkedChunkId::Room(room_id) => LinkedChunkId::Room(room_id.as_ref()),
191 OwnedLinkedChunkId::Thread(room_id, event_id) => {
192 LinkedChunkId::Thread(room_id.as_ref(), event_id.as_ref())
193 }
194 }
195 }
196
197 pub fn room_id(&self) -> &RoomId {
198 match self {
199 OwnedLinkedChunkId::Room(room_id) => room_id,
200 OwnedLinkedChunkId::Thread(room_id, ..) => room_id,
201 }
202 }
203}
204
205impl From<LinkedChunkId<'_>> for OwnedLinkedChunkId {
206 fn from(value: LinkedChunkId<'_>) -> Self {
207 value.to_owned()
208 }
209}
210
211#[derive(thiserror::Error, Debug)]
213pub enum Error {
214 #[error("The chunk identifier is invalid: `{identifier:?}`")]
216 InvalidChunkIdentifier {
217 identifier: ChunkIdentifier,
219 },
220
221 #[error("The chunk is a gap: `{identifier:?}`")]
223 ChunkIsAGap {
224 identifier: ChunkIdentifier,
226 },
227
228 #[error("The chunk is an item: `{identifier:?}`")]
230 ChunkIsItems {
231 identifier: ChunkIdentifier,
233 },
234
235 #[error("The chunk is a non-empty item chunk: `{identifier:?}`")]
237 RemovingNonEmptyItemsChunk {
238 identifier: ChunkIdentifier,
240 },
241
242 #[error("Trying to remove the only chunk, but a linked chunk can't be empty")]
245 RemovingLastChunk,
246
247 #[error("The item index is invalid: `{index}`")]
249 InvalidItemIndex {
250 index: usize,
252 },
253}
254
255struct Ends<const CHUNK_CAPACITY: usize, Item, Gap> {
260 first: NonNull<Chunk<CHUNK_CAPACITY, Item, Gap>>,
262 last: Option<NonNull<Chunk<CHUNK_CAPACITY, Item, Gap>>>,
264}
265
266impl<const CAP: usize, Item, Gap> Ends<CAP, Item, Gap> {
267 fn first_chunk(&self) -> &Chunk<CAP, Item, Gap> {
269 unsafe { self.first.as_ref() }
270 }
271
272 fn first_chunk_mut(&mut self) -> &mut Chunk<CAP, Item, Gap> {
274 unsafe { self.first.as_mut() }
275 }
276
277 fn latest_chunk(&self) -> &Chunk<CAP, Item, Gap> {
279 unsafe { self.last.unwrap_or(self.first).as_ref() }
280 }
281
282 fn latest_chunk_mut(&mut self) -> &mut Chunk<CAP, Item, Gap> {
284 unsafe { self.last.as_mut().unwrap_or(&mut self.first).as_mut() }
285 }
286
287 fn chunk(&self, identifier: ChunkIdentifier) -> Option<&Chunk<CAP, Item, Gap>> {
289 let mut chunk = self.latest_chunk();
290
291 loop {
292 if chunk.identifier() == identifier {
293 return Some(chunk);
294 }
295
296 chunk = chunk.previous()?;
297 }
298 }
299
300 fn chunk_mut(&mut self, identifier: ChunkIdentifier) -> Option<&mut Chunk<CAP, Item, Gap>> {
302 let mut chunk = self.latest_chunk_mut();
303
304 loop {
305 if chunk.identifier() == identifier {
306 return Some(chunk);
307 }
308
309 chunk = chunk.previous_mut()?;
310 }
311 }
312
313 unsafe fn clear(&mut self) {
320 let mut current_chunk_ptr = self.last.or(Some(self.first));
323
324 while let Some(chunk_ptr) = current_chunk_ptr {
326 let previous_ptr = unsafe { chunk_ptr.as_ref() }.previous;
328
329 let _chunk_boxed = unsafe { Box::from_raw(chunk_ptr.as_ptr()) };
331
332 current_chunk_ptr = previous_ptr;
334 }
335
336 self.first = NonNull::dangling();
338 self.last = None;
339 }
340
341 fn replace_with(&mut self, first_chunk: NonNull<Chunk<CAP, Item, Gap>>) {
344 unsafe {
346 self.clear();
347 }
348
349 self.first = first_chunk;
351 }
352
353 fn reset(&mut self) {
358 self.replace_with(Chunk::new_items_leaked(ChunkIdentifierGenerator::FIRST_IDENTIFIER));
359 }
360}
361
362pub struct LinkedChunk<const CHUNK_CAPACITY: usize, Item, Gap> {
369 links: Ends<CHUNK_CAPACITY, Item, Gap>,
371
372 chunk_identifier_generator: ChunkIdentifierGenerator,
374
375 updates: Option<ObservableUpdates<Item, Gap>>,
379
380 marker: PhantomData<Box<Chunk<CHUNK_CAPACITY, Item, Gap>>>,
382}
383
384impl<const CAP: usize, Item, Gap> Default for LinkedChunk<CAP, Item, Gap> {
385 fn default() -> Self {
386 Self::new()
387 }
388}
389
390impl<const CAP: usize, Item, Gap> LinkedChunk<CAP, Item, Gap> {
391 pub fn new() -> Self {
393 Self {
394 links: Ends {
395 first: Chunk::new_items_leaked(ChunkIdentifierGenerator::FIRST_IDENTIFIER),
396 last: None,
397 },
398 chunk_identifier_generator: ChunkIdentifierGenerator::new_from_scratch(),
399 updates: None,
400 marker: PhantomData,
401 }
402 }
403
404 pub fn new_with_update_history() -> Self {
410 let first_chunk_identifier = ChunkIdentifierGenerator::FIRST_IDENTIFIER;
411
412 let mut updates = ObservableUpdates::new();
413 updates.push(Update::NewItemsChunk {
414 previous: None,
415 new: first_chunk_identifier,
416 next: None,
417 });
418
419 Self {
420 links: Ends { first: Chunk::new_items_leaked(first_chunk_identifier), last: None },
421 chunk_identifier_generator: ChunkIdentifierGenerator::new_from_scratch(),
422 updates: Some(updates),
423 marker: PhantomData,
424 }
425 }
426
427 pub fn clear(&mut self) {
429 self.links.reset();
431
432 self.chunk_identifier_generator = ChunkIdentifierGenerator::new_from_scratch();
434
435 if let Some(updates) = self.updates.as_mut() {
437 updates.clear_pending();
440 updates.push(Update::Clear);
441 updates.push(Update::NewItemsChunk {
442 previous: None,
443 new: ChunkIdentifierGenerator::FIRST_IDENTIFIER,
444 next: None,
445 })
446 }
447 }
448
449 pub fn push_items_back<I>(&mut self, items: I)
455 where
456 Item: Clone,
457 Gap: Clone,
458 I: IntoIterator<Item = Item>,
459 I::IntoIter: ExactSizeIterator,
460 {
461 let items = items.into_iter();
462
463 let last_chunk = self.links.latest_chunk_mut();
464
465 let last_chunk =
467 last_chunk.push_items(items, &self.chunk_identifier_generator, &mut self.updates);
468
469 debug_assert!(last_chunk.is_last_chunk(), "`last_chunk` must be… the last chunk");
470
471 if !last_chunk.is_first_chunk() {
475 self.links.last = Some(last_chunk.as_ptr());
478 }
479 }
480
481 pub fn push_gap_back(&mut self, content: Gap)
484 where
485 Item: Clone,
486 Gap: Clone,
487 {
488 let last_chunk = self.links.latest_chunk_mut();
489 last_chunk.insert_next(
490 Chunk::new_gap_leaked(self.chunk_identifier_generator.next(), content),
491 &mut self.updates,
492 );
493
494 self.links.last = last_chunk.next;
495 }
496
497 pub fn insert_items_at<I>(&mut self, position: Position, items: I) -> Result<(), Error>
502 where
503 Item: Clone,
504 Gap: Clone,
505 I: IntoIterator<Item = Item>,
506 I::IntoIter: ExactSizeIterator,
507 {
508 let chunk_identifier = position.chunk_identifier();
509 let item_index = position.index();
510
511 let chunk = self
512 .links
513 .chunk_mut(chunk_identifier)
514 .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
515
516 let chunk = match &mut chunk.content {
517 ChunkContent::Gap(..) => {
518 return Err(Error::ChunkIsAGap { identifier: chunk_identifier });
519 }
520
521 ChunkContent::Items(current_items) => {
522 let current_items_length = current_items.len();
523
524 if item_index > current_items_length {
525 return Err(Error::InvalidItemIndex { index: item_index });
526 }
527
528 let items = items.into_iter();
530
531 if item_index == current_items_length {
533 chunk
534 .push_items(items, &self.chunk_identifier_generator, &mut self.updates)
536 }
537 else {
539 if let Some(updates) = self.updates.as_mut() {
540 updates.push(Update::DetachLastItems {
541 at: Position(chunk_identifier, item_index),
542 });
543 }
544
545 let detached_items = current_items.split_off(item_index);
547
548 let chunk = chunk
549 .push_items(items, &self.chunk_identifier_generator, &mut self.updates);
551
552 if let Some(updates) = self.updates.as_mut() {
553 updates.push(Update::StartReattachItems);
554 }
555
556 let chunk = chunk
557 .push_items(
559 detached_items.into_iter(),
560 &self.chunk_identifier_generator,
561 &mut self.updates,
562 );
563
564 if let Some(updates) = self.updates.as_mut() {
565 updates.push(Update::EndReattachItems);
566 }
567
568 chunk
569 }
570 }
571 };
572
573 if !chunk.is_first_chunk() && chunk.is_last_chunk() {
576 self.links.last = Some(chunk.as_ptr());
579 }
580
581 Ok(())
582 }
583
584 pub fn remove_item_at(&mut self, position: Position) -> Result<Item, Error> {
592 let chunk_identifier = position.chunk_identifier();
593 let item_index = position.index();
594
595 let mut chunk_ptr = None;
596 let removed_item;
597
598 {
599 let chunk = self
600 .links
601 .chunk_mut(chunk_identifier)
602 .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
603
604 let current_items = match &mut chunk.content {
605 ChunkContent::Gap(..) => {
606 return Err(Error::ChunkIsAGap { identifier: chunk_identifier });
607 }
608 ChunkContent::Items(current_items) => current_items,
609 };
610
611 if item_index > current_items.len() {
612 return Err(Error::InvalidItemIndex { index: item_index });
613 }
614
615 removed_item = current_items.remove(item_index);
616 if let Some(updates) = self.updates.as_mut() {
617 updates.push(Update::RemoveItem { at: Position(chunk_identifier, item_index) })
618 }
619
620 if current_items.is_empty() && !chunk.is_first_chunk() {
622 chunk.unlink(self.updates.as_mut());
624
625 chunk_ptr = Some(chunk.as_ptr());
626
627 if chunk.is_last_chunk() {
630 self.links.last = chunk.previous;
631 }
632 }
633
634 }
636
637 if let Some(chunk_ptr) = chunk_ptr {
638 let _chunk_boxed = unsafe { Box::from_raw(chunk_ptr.as_ptr()) };
645 }
646
647 Ok(removed_item)
648 }
649
650 pub fn replace_item_at(&mut self, position: Position, item: Item) -> Result<(), Error>
655 where
656 Item: Clone,
657 {
658 let chunk_identifier = position.chunk_identifier();
659 let item_index = position.index();
660
661 let chunk = self
662 .links
663 .chunk_mut(chunk_identifier)
664 .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
665
666 match &mut chunk.content {
667 ChunkContent::Gap(..) => {
668 return Err(Error::ChunkIsAGap { identifier: chunk_identifier });
669 }
670
671 ChunkContent::Items(current_items) => {
672 if item_index >= current_items.len() {
673 return Err(Error::InvalidItemIndex { index: item_index });
674 }
675
676 if let Some(updates) = self.updates.as_mut() {
678 updates.push(Update::ReplaceItem {
679 at: Position(chunk_identifier, item_index),
680 item: item.clone(),
681 });
682 }
683
684 current_items[item_index] = item;
685 }
686 }
687
688 Ok(())
689 }
690
691 pub fn insert_gap_at(&mut self, content: Gap, position: Position) -> Result<(), Error>
696 where
697 Item: Clone,
698 Gap: Clone,
699 {
700 let chunk_identifier = position.chunk_identifier();
701 let item_index = position.index();
702
703 let chunk = self
704 .links
705 .chunk_mut(chunk_identifier)
706 .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
707
708 let chunk = match &mut chunk.content {
709 ChunkContent::Gap(..) => {
710 return Err(Error::ChunkIsAGap { identifier: chunk_identifier });
711 }
712
713 ChunkContent::Items(current_items) => {
714 if item_index == 0 {
718 let chunk_was_first = chunk.is_first_chunk();
719 let chunk_was_last = chunk.is_last_chunk();
720
721 let new_chunk = chunk.insert_before(
722 Chunk::new_gap_leaked(self.chunk_identifier_generator.next(), content),
723 self.updates.as_mut(),
724 );
725
726 let new_chunk_ptr = new_chunk.as_ptr();
727 let chunk_ptr = chunk.as_ptr();
728
729 if chunk_was_first {
734 self.links.first = new_chunk_ptr;
735
736 if chunk_was_last {
738 self.links.last = Some(chunk_ptr);
739 }
740 }
741
742 return Ok(());
743 }
744
745 let current_items_length = current_items.len();
746
747 if item_index >= current_items_length {
748 return Err(Error::InvalidItemIndex { index: item_index });
749 }
750
751 if let Some(updates) = self.updates.as_mut() {
752 updates.push(Update::DetachLastItems {
753 at: Position(chunk_identifier, item_index),
754 });
755 }
756
757 let detached_items = current_items.split_off(item_index);
759
760 let chunk = chunk
761 .insert_next(
763 Chunk::new_gap_leaked(self.chunk_identifier_generator.next(), content),
764 &mut self.updates,
765 );
766
767 if let Some(updates) = self.updates.as_mut() {
768 updates.push(Update::StartReattachItems);
769 }
770
771 let chunk = chunk
772 .insert_next(
774 Chunk::new_items_leaked(self.chunk_identifier_generator.next()),
775 &mut self.updates,
776 )
777 .push_items(
779 detached_items.into_iter(),
780 &self.chunk_identifier_generator,
781 &mut self.updates,
782 );
783
784 if let Some(updates) = self.updates.as_mut() {
785 updates.push(Update::EndReattachItems);
786 }
787
788 chunk
789 }
790 };
791
792 if !chunk.is_first_chunk() && chunk.is_last_chunk() {
795 self.links.last = Some(chunk.as_ptr());
798 }
799
800 Ok(())
801 }
802
803 pub fn remove_empty_chunk_at(
812 &mut self,
813 chunk_identifier: ChunkIdentifier,
814 ) -> Result<Option<Position>, Error> {
815 if self.links.first_chunk().is_last_chunk() {
817 return Err(Error::RemovingLastChunk);
818 }
819
820 let chunk = self
821 .links
822 .chunk_mut(chunk_identifier)
823 .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
824
825 if chunk.num_items() > 0 {
826 return Err(Error::RemovingNonEmptyItemsChunk { identifier: chunk_identifier });
827 }
828
829 let chunk_was_first = chunk.is_first_chunk();
830 let chunk_was_last = chunk.is_last_chunk();
831 let next_ptr = chunk.next;
832 let previous_ptr = chunk.previous;
833 let position_of_next = chunk.next().map(|next| next.first_position());
834
835 chunk.unlink(self.updates.as_mut());
836
837 let chunk_ptr = chunk.as_ptr();
838
839 if chunk_was_first {
841 if let Some(next_ptr) = next_ptr {
843 self.links.first = next_ptr;
844 }
845 }
846
847 if chunk_was_last {
848 self.links.last = previous_ptr;
849 }
850
851 let _chunk_boxed = unsafe { Box::from_raw(chunk_ptr.as_ptr()) };
854
855 Ok(position_of_next)
857 }
858
859 pub fn replace_gap_at<I>(
867 &mut self,
868 items: I,
869 chunk_identifier: ChunkIdentifier,
870 ) -> Result<&Chunk<CAP, Item, Gap>, Error>
871 where
872 Item: Clone,
873 Gap: Clone,
874 I: IntoIterator<Item = Item>,
875 I::IntoIter: ExactSizeIterator,
876 {
877 let chunk_ptr;
878 let new_chunk_ptr;
879
880 {
881 let chunk = self
882 .links
883 .chunk_mut(chunk_identifier)
884 .ok_or(Error::InvalidChunkIdentifier { identifier: chunk_identifier })?;
885
886 if chunk.is_items() {
887 return Err(Error::ChunkIsItems { identifier: chunk_identifier });
888 }
889
890 let chunk_was_first = chunk.is_first_chunk();
891
892 let maybe_last_chunk_ptr = {
893 let items = items.into_iter();
894
895 let last_inserted_chunk = chunk
896 .insert_next(
898 Chunk::new_items_leaked(self.chunk_identifier_generator.next()),
899 &mut self.updates,
900 )
901 .push_items(items, &self.chunk_identifier_generator, &mut self.updates);
903
904 last_inserted_chunk.is_last_chunk().then(|| last_inserted_chunk.as_ptr())
905 };
906
907 new_chunk_ptr = chunk
908 .next
909 .unwrap();
911
912 chunk.unlink(self.updates.as_mut());
914
915 chunk_ptr = chunk.as_ptr();
917
918 if chunk_was_first {
920 self.links.first = new_chunk_ptr;
921 }
922
923 if let Some(last_chunk_ptr) = maybe_last_chunk_ptr {
926 self.links.last = Some(last_chunk_ptr);
927 }
928
929 }
931
932 let _chunk_boxed = unsafe { Box::from_raw(chunk_ptr.as_ptr()) };
937
938 Ok(
939 unsafe { new_chunk_ptr.as_ref() },
943 )
944 }
945
946 pub fn chunk_identifier<'a, P>(&'a self, mut predicate: P) -> Option<ChunkIdentifier>
948 where
949 P: FnMut(&'a Chunk<CAP, Item, Gap>) -> bool,
950 {
951 self.rchunks().find_map(|chunk| predicate(chunk).then(|| chunk.identifier()))
952 }
953
954 pub fn item_position<'a, P>(&'a self, mut predicate: P) -> Option<Position>
956 where
957 P: FnMut(&'a Item) -> bool,
958 {
959 self.ritems().find_map(|(item_position, item)| predicate(item).then_some(item_position))
960 }
961
962 pub fn rchunks(&self) -> IterBackward<'_, CAP, Item, Gap> {
966 IterBackward::new(self.links.latest_chunk())
967 }
968
969 pub fn chunks(&self) -> Iter<'_, CAP, Item, Gap> {
973 Iter::new(self.links.first_chunk())
974 }
975
976 pub fn rchunks_from(
981 &self,
982 identifier: ChunkIdentifier,
983 ) -> Result<IterBackward<'_, CAP, Item, Gap>, Error> {
984 Ok(IterBackward::new(
985 self.links.chunk(identifier).ok_or(Error::InvalidChunkIdentifier { identifier })?,
986 ))
987 }
988
989 pub fn chunks_from(
994 &self,
995 identifier: ChunkIdentifier,
996 ) -> Result<Iter<'_, CAP, Item, Gap>, Error> {
997 Ok(Iter::new(
998 self.links.chunk(identifier).ok_or(Error::InvalidChunkIdentifier { identifier })?,
999 ))
1000 }
1001
1002 pub fn ritems(&self) -> impl Iterator<Item = (Position, &Item)> {
1006 self.ritems_from(self.links.latest_chunk().last_position())
1007 .expect("`ritems_from` cannot fail because at least one empty chunk must exist")
1008 }
1009
1010 pub fn items(&self) -> impl Iterator<Item = (Position, &Item)> {
1014 let first_chunk = self.links.first_chunk();
1015
1016 self.items_from(first_chunk.first_position())
1017 .expect("`items` cannot fail because at least one empty chunk must exist")
1018 }
1019
1020 pub fn ritems_from(
1024 &self,
1025 position: Position,
1026 ) -> Result<impl Iterator<Item = (Position, &Item)>, Error> {
1027 Ok(self
1028 .rchunks_from(position.chunk_identifier())?
1029 .filter_map(|chunk| match &chunk.content {
1030 ChunkContent::Gap(..) => None,
1031 ChunkContent::Items(items) => {
1032 let identifier = chunk.identifier();
1033
1034 Some(
1035 items.iter().enumerate().rev().map(move |(item_index, item)| {
1036 (Position(identifier, item_index), item)
1037 }),
1038 )
1039 }
1040 })
1041 .flatten()
1042 .skip_while({
1043 let expected_index = position.index();
1044
1045 move |(Position(chunk_identifier, item_index), _item)| {
1046 *chunk_identifier == position.chunk_identifier()
1047 && *item_index != expected_index
1048 }
1049 }))
1050 }
1051
1052 pub fn items_from(
1056 &self,
1057 position: Position,
1058 ) -> Result<impl Iterator<Item = (Position, &Item)>, Error> {
1059 Ok(self
1060 .chunks_from(position.chunk_identifier())?
1061 .filter_map(|chunk| match &chunk.content {
1062 ChunkContent::Gap(..) => None,
1063 ChunkContent::Items(items) => {
1064 let identifier = chunk.identifier();
1065
1066 Some(
1067 items.iter().enumerate().map(move |(item_index, item)| {
1068 (Position(identifier, item_index), item)
1069 }),
1070 )
1071 }
1072 })
1073 .flatten()
1074 .skip(position.index()))
1075 }
1076
1077 #[must_use]
1089 pub fn updates(&mut self) -> Option<&mut ObservableUpdates<Item, Gap>> {
1090 self.updates.as_mut()
1091 }
1092
1093 pub fn as_vector(&mut self) -> Option<AsVector<Item, Gap>> {
1100 let (updates, token) = self
1101 .updates
1102 .as_mut()
1103 .map(|updates| (updates.inner.clone(), updates.new_reader_token()))?;
1104 let chunk_iterator = self.chunks();
1105
1106 Some(AsVector::new(updates, token, chunk_iterator))
1107 }
1108
1109 pub fn order_tracker(
1117 &mut self,
1118 all_chunks: Option<Vec<ChunkMetadata>>,
1119 ) -> Option<OrderTracker<Item, Gap>>
1120 where
1121 Item: Clone,
1122 {
1123 let (updates, token) = self
1124 .updates
1125 .as_mut()
1126 .map(|updates| (updates.inner.clone(), updates.new_reader_token()))?;
1127
1128 Some(OrderTracker::new(
1129 updates,
1130 token,
1131 all_chunks.unwrap_or_else(|| {
1132 self.chunks()
1134 .map(|chunk| ChunkMetadata {
1135 identifier: chunk.identifier(),
1136 num_items: chunk.num_items(),
1137 previous: chunk.previous().map(|prev| prev.identifier()),
1138 next: chunk.next().map(|next| next.identifier()),
1139 })
1140 .collect()
1141 }),
1142 ))
1143 }
1144
1145 pub fn num_items(&self) -> usize {
1147 self.items().count()
1148 }
1149}
1150
1151impl<const CAP: usize, Item, Gap> Drop for LinkedChunk<CAP, Item, Gap> {
1152 fn drop(&mut self) {
1153 unsafe {
1163 self.links.clear();
1164 }
1165 }
1166}
1167
1168unsafe impl<const CAP: usize, Item: Send, Gap: Send> Send for LinkedChunk<CAP, Item, Gap> {}
1172
1173unsafe impl<const CAP: usize, Item: Sync, Gap: Sync> Sync for LinkedChunk<CAP, Item, Gap> {}
1177
1178#[derive(Debug)]
1188pub struct ChunkIdentifierGenerator {
1189 next: AtomicU64,
1190}
1191
1192impl ChunkIdentifierGenerator {
1193 const FIRST_IDENTIFIER: ChunkIdentifier = ChunkIdentifier(0);
1195
1196 pub fn new_from_scratch() -> Self {
1199 Self { next: AtomicU64::new(Self::FIRST_IDENTIFIER.0) }
1200 }
1201
1202 pub fn new_from_previous_chunk_identifier(last_chunk_identifier: ChunkIdentifier) -> Self {
1205 Self { next: AtomicU64::new(last_chunk_identifier.0) }
1206 }
1207
1208 fn next(&self) -> ChunkIdentifier {
1213 let previous = self.next.fetch_add(1, atomic::Ordering::Relaxed);
1214
1215 if previous == u64::MAX {
1218 panic!(
1219 "No more chunk identifiers available. Congrats, you did it. \
1220 2^64 identifiers have been consumed."
1221 )
1222 }
1223
1224 ChunkIdentifier(previous + 1)
1225 }
1226
1227 #[doc(hidden)]
1231 pub fn current(&self) -> ChunkIdentifier {
1232 ChunkIdentifier(self.next.load(atomic::Ordering::Relaxed))
1233 }
1234}
1235
1236#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
1242#[repr(transparent)]
1243pub struct ChunkIdentifier(u64);
1244
1245impl ChunkIdentifier {
1246 pub fn new(identifier: u64) -> Self {
1248 Self(identifier)
1249 }
1250
1251 pub fn index(&self) -> u64 {
1253 self.0
1254 }
1255}
1256
1257impl PartialEq<u64> for ChunkIdentifier {
1258 fn eq(&self, other: &u64) -> bool {
1259 self.0 == *other
1260 }
1261}
1262
1263#[derive(Copy, Clone, Debug, PartialEq)]
1267pub struct Position(ChunkIdentifier, usize);
1268
1269impl Position {
1270 pub fn new(chunk_identifier: ChunkIdentifier, index: usize) -> Self {
1272 Self(chunk_identifier, index)
1273 }
1274
1275 pub fn chunk_identifier(&self) -> ChunkIdentifier {
1277 self.0
1278 }
1279
1280 pub fn index(&self) -> usize {
1282 self.1
1283 }
1284
1285 pub fn decrement_index(&mut self) {
1291 self.1 = self.1.checked_sub(1).expect("Cannot decrement the index because it's already 0");
1292 }
1293
1294 pub fn increment_index(&mut self) {
1301 self.1 = self.1.checked_add(1).expect("Cannot increment the index because it's too large");
1302 }
1303}
1304
1305#[derive(Debug)]
1308pub struct IterBackward<'a, const CAP: usize, Item, Gap> {
1309 chunk: Option<&'a Chunk<CAP, Item, Gap>>,
1310}
1311
1312impl<'a, const CAP: usize, Item, Gap> IterBackward<'a, CAP, Item, Gap> {
1313 fn new(from_chunk: &'a Chunk<CAP, Item, Gap>) -> Self {
1315 Self { chunk: Some(from_chunk) }
1316 }
1317}
1318
1319impl<'a, const CAP: usize, Item, Gap> Iterator for IterBackward<'a, CAP, Item, Gap> {
1320 type Item = &'a Chunk<CAP, Item, Gap>;
1321
1322 fn next(&mut self) -> Option<Self::Item> {
1323 self.chunk.inspect(|chunk| self.chunk = chunk.previous())
1324 }
1325}
1326
1327#[derive(Debug)]
1330pub struct Iter<'a, const CAP: usize, Item, Gap> {
1331 chunk: Option<&'a Chunk<CAP, Item, Gap>>,
1332}
1333
1334impl<'a, const CAP: usize, Item, Gap> Iter<'a, CAP, Item, Gap> {
1335 fn new(from_chunk: &'a Chunk<CAP, Item, Gap>) -> Self {
1337 Self { chunk: Some(from_chunk) }
1338 }
1339}
1340
1341impl<'a, const CAP: usize, Item, Gap> Iterator for Iter<'a, CAP, Item, Gap> {
1342 type Item = &'a Chunk<CAP, Item, Gap>;
1343
1344 fn next(&mut self) -> Option<Self::Item> {
1345 self.chunk.inspect(|chunk| self.chunk = chunk.next())
1346 }
1347}
1348
1349#[derive(Clone, Debug)]
1351pub enum ChunkContent<Item, Gap> {
1352 Gap(Gap),
1355
1356 Items(Vec<Item>),
1358}
1359
1360pub struct Chunk<const CAPACITY: usize, Item, Gap> {
1362 previous: Option<NonNull<Chunk<CAPACITY, Item, Gap>>>,
1364
1365 lazy_previous: Option<ChunkIdentifier>,
1370
1371 next: Option<NonNull<Chunk<CAPACITY, Item, Gap>>>,
1373
1374 identifier: ChunkIdentifier,
1376
1377 content: ChunkContent<Item, Gap>,
1379}
1380
1381impl<const CAPACITY: usize, Item, Gap> Chunk<CAPACITY, Item, Gap> {
1382 fn new_gap(identifier: ChunkIdentifier, content: Gap) -> Self {
1384 Self::new(identifier, ChunkContent::Gap(content))
1385 }
1386
1387 fn new_items(identifier: ChunkIdentifier) -> Self {
1389 Self::new(identifier, ChunkContent::Items(Vec::with_capacity(CAPACITY)))
1390 }
1391
1392 fn new(identifier: ChunkIdentifier, content: ChunkContent<Item, Gap>) -> Self {
1393 Self { previous: None, lazy_previous: None, next: None, identifier, content }
1394 }
1395
1396 fn new_leaked(identifier: ChunkIdentifier, content: ChunkContent<Item, Gap>) -> NonNull<Self> {
1398 let chunk = Self::new(identifier, content);
1399 let chunk_box = Box::new(chunk);
1400
1401 NonNull::from(Box::leak(chunk_box))
1402 }
1403
1404 fn new_gap_leaked(identifier: ChunkIdentifier, content: Gap) -> NonNull<Self> {
1406 let chunk = Self::new_gap(identifier, content);
1407 let chunk_box = Box::new(chunk);
1408
1409 NonNull::from(Box::leak(chunk_box))
1410 }
1411
1412 fn new_items_leaked(identifier: ChunkIdentifier) -> NonNull<Self> {
1414 let chunk = Self::new_items(identifier);
1415 let chunk_box = Box::new(chunk);
1416
1417 NonNull::from(Box::leak(chunk_box))
1418 }
1419
1420 pub fn as_ptr(&self) -> NonNull<Self> {
1422 NonNull::from(self)
1423 }
1424
1425 pub fn is_gap(&self) -> bool {
1427 matches!(self.content, ChunkContent::Gap(..))
1428 }
1429
1430 pub fn is_items(&self) -> bool {
1432 !self.is_gap()
1433 }
1434
1435 pub fn is_definitive_head(&self) -> bool {
1438 self.previous.is_none() && self.lazy_previous.is_none()
1439 }
1440
1441 fn is_first_chunk(&self) -> bool {
1443 self.previous.is_none()
1444 }
1445
1446 fn is_last_chunk(&self) -> bool {
1448 self.next.is_none()
1449 }
1450
1451 #[doc(hidden)]
1455 pub fn lazy_previous(&self) -> Option<ChunkIdentifier> {
1456 self.lazy_previous
1457 }
1458
1459 pub fn identifier(&self) -> ChunkIdentifier {
1461 self.identifier
1462 }
1463
1464 pub fn content(&self) -> &ChunkContent<Item, Gap> {
1466 &self.content
1467 }
1468
1469 pub fn first_position(&self) -> Position {
1473 Position(self.identifier(), 0)
1474 }
1475
1476 pub fn last_position(&self) -> Position {
1480 let identifier = self.identifier();
1481
1482 match &self.content {
1483 ChunkContent::Gap(..) => Position(identifier, 0),
1484 ChunkContent::Items(items) => Position(identifier, items.len().saturating_sub(1)),
1485 }
1486 }
1487
1488 pub fn num_items(&self) -> usize {
1492 match &self.content {
1493 ChunkContent::Gap(..) => 0,
1494 ChunkContent::Items(items) => items.len(),
1495 }
1496 }
1497
1498 fn push_items<I>(
1510 &mut self,
1511 mut new_items: I,
1512 chunk_identifier_generator: &ChunkIdentifierGenerator,
1513 updates: &mut Option<ObservableUpdates<Item, Gap>>,
1514 ) -> &mut Self
1515 where
1516 I: Iterator<Item = Item> + ExactSizeIterator,
1517 Item: Clone,
1518 Gap: Clone,
1519 {
1520 if new_items.len() == 0 {
1522 return self;
1523 }
1524
1525 let identifier = self.identifier();
1526 let prev_num_items = self.num_items();
1527
1528 match &mut self.content {
1529 ChunkContent::Gap(..) => {
1532 self
1533 .insert_next(Self::new_items_leaked(chunk_identifier_generator.next()), updates)
1535 .push_items(new_items, chunk_identifier_generator, updates)
1538 }
1539
1540 ChunkContent::Items(items) => {
1541 let free_space = CAPACITY.saturating_sub(prev_num_items);
1543
1544 if new_items.len() <= free_space {
1546 let start = items.len();
1547 items.extend(new_items);
1548
1549 if let Some(updates) = updates.as_mut() {
1550 updates.push(Update::PushItems {
1551 at: Position(identifier, start),
1552 items: items[start..].to_vec(),
1553 });
1554 }
1555
1556 self
1558 } else {
1559 if free_space > 0 {
1560 let start = items.len();
1562 items.extend(new_items.by_ref().take(free_space));
1563
1564 if let Some(updates) = updates.as_mut() {
1565 updates.push(Update::PushItems {
1566 at: Position(identifier, start),
1567 items: items[start..].to_vec(),
1568 });
1569 }
1570 }
1571
1572 self
1573 .insert_next(
1575 Self::new_items_leaked(chunk_identifier_generator.next()),
1576 updates,
1577 )
1578 .push_items(new_items, chunk_identifier_generator, updates)
1581 }
1582 }
1583 }
1584 }
1585
1586 fn insert_next(
1591 &mut self,
1592 mut new_chunk_ptr: NonNull<Self>,
1593 updates: &mut Option<ObservableUpdates<Item, Gap>>,
1594 ) -> &mut Self
1595 where
1596 Gap: Clone,
1597 {
1598 let new_chunk = unsafe { new_chunk_ptr.as_mut() };
1599
1600 if let Some(next_chunk) = self.next_mut() {
1602 next_chunk.previous = Some(new_chunk_ptr);
1604
1605 new_chunk.next = self.next;
1607 }
1608
1609 self.next = Some(new_chunk_ptr);
1611 new_chunk.previous = Some(self.as_ptr());
1613
1614 if let Some(updates) = updates.as_mut() {
1615 let previous = new_chunk.previous().map(Chunk::identifier);
1616 let new = new_chunk.identifier();
1617 let next = new_chunk.next().map(Chunk::identifier);
1618
1619 match new_chunk.content() {
1620 ChunkContent::Gap(gap) => {
1621 updates.push(Update::NewGapChunk { previous, new, next, gap: gap.clone() })
1622 }
1623
1624 ChunkContent::Items(..) => {
1625 updates.push(Update::NewItemsChunk { previous, new, next })
1626 }
1627 }
1628 }
1629
1630 new_chunk
1631 }
1632
1633 fn insert_before(
1638 &mut self,
1639 mut new_chunk_ptr: NonNull<Self>,
1640 updates: Option<&mut ObservableUpdates<Item, Gap>>,
1641 ) -> &mut Self
1642 where
1643 Gap: Clone,
1644 {
1645 let new_chunk = unsafe { new_chunk_ptr.as_mut() };
1646
1647 if let Some(previous_chunk) = self.previous_mut() {
1649 previous_chunk.next = Some(new_chunk_ptr);
1651
1652 new_chunk.previous = self.previous;
1654 }
1655 else {
1658 new_chunk.lazy_previous = self.lazy_previous.take();
1659 }
1660
1661 self.previous = Some(new_chunk_ptr);
1663 new_chunk.next = Some(self.as_ptr());
1665
1666 if let Some(updates) = updates {
1667 let previous = new_chunk.previous().map(Chunk::identifier).or(new_chunk.lazy_previous);
1668 let new = new_chunk.identifier();
1669 let next = new_chunk.next().map(Chunk::identifier);
1670
1671 match new_chunk.content() {
1672 ChunkContent::Gap(gap) => {
1673 updates.push(Update::NewGapChunk { previous, new, next, gap: gap.clone() })
1674 }
1675
1676 ChunkContent::Items(..) => {
1677 updates.push(Update::NewItemsChunk { previous, new, next })
1678 }
1679 }
1680 }
1681
1682 new_chunk
1683 }
1684
1685 fn unlink(&mut self, updates: Option<&mut ObservableUpdates<Item, Gap>>) {
1690 let previous_ptr = self.previous;
1691 let next_ptr = self.next;
1692 let lazy_previous = self.lazy_previous.take();
1696
1697 if let Some(previous) = self.previous_mut() {
1698 previous.next = next_ptr;
1699 }
1700
1701 if let Some(next) = self.next_mut() {
1702 next.previous = previous_ptr;
1703 next.lazy_previous = lazy_previous;
1704 }
1705
1706 if let Some(updates) = updates {
1707 updates.push(Update::RemoveChunk(self.identifier()));
1708 }
1709 }
1710
1711 fn previous(&self) -> Option<&Self> {
1713 self.previous.map(|non_null| unsafe { non_null.as_ref() })
1714 }
1715
1716 fn previous_mut(&mut self) -> Option<&mut Self> {
1718 self.previous.as_mut().map(|non_null| unsafe { non_null.as_mut() })
1719 }
1720
1721 fn next(&self) -> Option<&Self> {
1723 self.next.map(|non_null| unsafe { non_null.as_ref() })
1724 }
1725
1726 fn next_mut(&mut self) -> Option<&mut Self> {
1728 self.next.as_mut().map(|non_null| unsafe { non_null.as_mut() })
1729 }
1730}
1731
1732impl<const CAP: usize, Item, Gap> fmt::Debug for LinkedChunk<CAP, Item, Gap>
1733where
1734 Item: fmt::Debug,
1735 Gap: fmt::Debug,
1736{
1737 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
1738 formatter
1739 .debug_struct("LinkedChunk")
1740 .field("first (deref)", unsafe { self.links.first.as_ref() })
1741 .field("last", &self.links.last)
1742 .finish_non_exhaustive()
1743 }
1744}
1745
1746impl<const CAP: usize, Item, Gap> fmt::Debug for Chunk<CAP, Item, Gap>
1747where
1748 Item: fmt::Debug,
1749 Gap: fmt::Debug,
1750{
1751 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
1752 formatter
1753 .debug_struct("Chunk")
1754 .field("identifier", &self.identifier)
1755 .field("content", &self.content)
1756 .field("previous", &self.previous)
1757 .field("ptr", &std::ptr::from_ref(self))
1758 .field("next", &self.next)
1759 .field("next (deref)", &self.next.as_ref().map(|non_null| unsafe { non_null.as_ref() }))
1760 .finish()
1761 }
1762}
1763
1764#[derive(Clone, Debug)]
1770pub struct RawChunk<Item, Gap> {
1771 pub content: ChunkContent<Item, Gap>,
1773
1774 pub previous: Option<ChunkIdentifier>,
1776
1777 pub identifier: ChunkIdentifier,
1779
1780 pub next: Option<ChunkIdentifier>,
1782}
1783
1784#[derive(Clone, Debug)]
1787pub struct ChunkMetadata {
1788 pub num_items: usize,
1792
1793 pub previous: Option<ChunkIdentifier>,
1795
1796 pub identifier: ChunkIdentifier,
1798
1799 pub next: Option<ChunkIdentifier>,
1801}
1802
1803#[cfg(test)]
1804mod tests {
1805 use std::{
1806 ops::Not,
1807 sync::{Arc, atomic::Ordering},
1808 };
1809
1810 use assert_matches::assert_matches;
1811
1812 use super::{
1813 Chunk, ChunkContent, ChunkIdentifier, ChunkIdentifierGenerator, Error, LinkedChunk,
1814 Position,
1815 };
1816
1817 #[test]
1818 fn test_chunk_identifier_generator() {
1819 let generator = ChunkIdentifierGenerator::new_from_scratch();
1820
1821 assert_eq!(generator.next(), ChunkIdentifier(1));
1822 assert_eq!(generator.next(), ChunkIdentifier(2));
1823 assert_eq!(generator.next(), ChunkIdentifier(3));
1824 assert_eq!(generator.next(), ChunkIdentifier(4));
1825
1826 let generator =
1827 ChunkIdentifierGenerator::new_from_previous_chunk_identifier(ChunkIdentifier(42));
1828
1829 assert_eq!(generator.next(), ChunkIdentifier(43));
1830 assert_eq!(generator.next(), ChunkIdentifier(44));
1831 assert_eq!(generator.next(), ChunkIdentifier(45));
1832 assert_eq!(generator.next(), ChunkIdentifier(46));
1833 }
1834
1835 #[test]
1836 fn test_empty() {
1837 let items = LinkedChunk::<3, char, ()>::new();
1838
1839 assert_eq!(items.num_items(), 0);
1840
1841 }
1844
1845 #[test]
1846 fn test_updates() {
1847 assert!(LinkedChunk::<3, char, ()>::new().updates().is_none());
1848 assert!(LinkedChunk::<3, char, ()>::new_with_update_history().updates().is_some());
1849 }
1850
1851 #[test]
1852 fn test_new_with_initial_update() {
1853 use super::Update::*;
1854
1855 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
1856
1857 assert_eq!(
1858 linked_chunk.updates().unwrap().take(),
1859 &[NewItemsChunk { previous: None, new: ChunkIdentifier(0), next: None }]
1860 );
1861 }
1862
1863 #[test]
1864 fn test_push_items() {
1865 use super::Update::*;
1866
1867 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
1868
1869 let _ = linked_chunk.updates().unwrap().take();
1871
1872 linked_chunk.push_items_back(['a']);
1873
1874 assert_items_eq!(linked_chunk, ['a']);
1875 assert_eq!(
1876 linked_chunk.updates().unwrap().take(),
1877 &[PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a'] }]
1878 );
1879
1880 linked_chunk.push_items_back(['b', 'c']);
1881 assert_items_eq!(linked_chunk, ['a', 'b', 'c']);
1882 assert_eq!(
1883 linked_chunk.updates().unwrap().take(),
1884 &[PushItems { at: Position(ChunkIdentifier(0), 1), items: vec!['b', 'c'] }]
1885 );
1886
1887 linked_chunk.push_items_back(['d', 'e']);
1888 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e']);
1889 assert_eq!(
1890 linked_chunk.updates().unwrap().take(),
1891 &[
1892 NewItemsChunk {
1893 previous: Some(ChunkIdentifier(0)),
1894 new: ChunkIdentifier(1),
1895 next: None
1896 },
1897 PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e'] }
1898 ]
1899 );
1900
1901 linked_chunk.push_items_back(['f', 'g', 'h', 'i', 'j']);
1902 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f'] ['g', 'h', 'i'] ['j']);
1903 assert_eq!(
1904 linked_chunk.updates().unwrap().take(),
1905 &[
1906 PushItems { at: Position(ChunkIdentifier(1), 2), items: vec!['f'] },
1907 NewItemsChunk {
1908 previous: Some(ChunkIdentifier(1)),
1909 new: ChunkIdentifier(2),
1910 next: None,
1911 },
1912 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['g', 'h', 'i'] },
1913 NewItemsChunk {
1914 previous: Some(ChunkIdentifier(2)),
1915 new: ChunkIdentifier(3),
1916 next: None,
1917 },
1918 PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['j'] },
1919 ]
1920 );
1921
1922 assert_eq!(linked_chunk.num_items(), 10);
1923 }
1924
1925 #[test]
1926 fn test_push_gap() {
1927 use super::Update::*;
1928
1929 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
1930
1931 let _ = linked_chunk.updates().unwrap().take();
1933
1934 linked_chunk.push_items_back(['a']);
1935 assert_items_eq!(linked_chunk, ['a']);
1936 assert_eq!(
1937 linked_chunk.updates().unwrap().take(),
1938 &[PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a'] }]
1939 );
1940
1941 linked_chunk.push_gap_back(());
1942 assert_items_eq!(linked_chunk, ['a'] [-]);
1943 assert_eq!(
1944 linked_chunk.updates().unwrap().take(),
1945 &[NewGapChunk {
1946 previous: Some(ChunkIdentifier(0)),
1947 new: ChunkIdentifier(1),
1948 next: None,
1949 gap: (),
1950 }]
1951 );
1952
1953 linked_chunk.push_items_back(['b', 'c', 'd', 'e']);
1954 assert_items_eq!(linked_chunk, ['a'] [-] ['b', 'c', 'd'] ['e']);
1955 assert_eq!(
1956 linked_chunk.updates().unwrap().take(),
1957 &[
1958 NewItemsChunk {
1959 previous: Some(ChunkIdentifier(1)),
1960 new: ChunkIdentifier(2),
1961 next: None,
1962 },
1963 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['b', 'c', 'd'] },
1964 NewItemsChunk {
1965 previous: Some(ChunkIdentifier(2)),
1966 new: ChunkIdentifier(3),
1967 next: None,
1968 },
1969 PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['e'] },
1970 ]
1971 );
1972
1973 linked_chunk.push_gap_back(());
1974 linked_chunk.push_gap_back(()); assert_items_eq!(linked_chunk, ['a'] [-] ['b', 'c', 'd'] ['e'] [-] [-]);
1976 assert_eq!(
1977 linked_chunk.updates().unwrap().take(),
1978 &[
1979 NewGapChunk {
1980 previous: Some(ChunkIdentifier(3)),
1981 new: ChunkIdentifier(4),
1982 next: None,
1983 gap: (),
1984 },
1985 NewGapChunk {
1986 previous: Some(ChunkIdentifier(4)),
1987 new: ChunkIdentifier(5),
1988 next: None,
1989 gap: (),
1990 }
1991 ]
1992 );
1993
1994 linked_chunk.push_items_back(['f', 'g', 'h', 'i']);
1995 assert_items_eq!(linked_chunk, ['a'] [-] ['b', 'c', 'd'] ['e'] [-] [-] ['f', 'g', 'h'] ['i']);
1996 assert_eq!(
1997 linked_chunk.updates().unwrap().take(),
1998 &[
1999 NewItemsChunk {
2000 previous: Some(ChunkIdentifier(5)),
2001 new: ChunkIdentifier(6),
2002 next: None,
2003 },
2004 PushItems { at: Position(ChunkIdentifier(6), 0), items: vec!['f', 'g', 'h'] },
2005 NewItemsChunk {
2006 previous: Some(ChunkIdentifier(6)),
2007 new: ChunkIdentifier(7),
2008 next: None,
2009 },
2010 PushItems { at: Position(ChunkIdentifier(7), 0), items: vec!['i'] },
2011 ]
2012 );
2013
2014 assert_eq!(linked_chunk.num_items(), 9);
2015 }
2016
2017 #[test]
2018 fn test_identifiers_and_positions() {
2019 let mut linked_chunk = LinkedChunk::<3, char, ()>::new();
2020 linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f']);
2021 linked_chunk.push_gap_back(());
2022 linked_chunk.push_items_back(['g', 'h', 'i', 'j']);
2023 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f'] [-] ['g', 'h', 'i'] ['j']);
2024
2025 assert_eq!(linked_chunk.chunk_identifier(Chunk::is_gap), Some(ChunkIdentifier(2)));
2026 assert_eq!(
2027 linked_chunk.item_position(|item| *item == 'e'),
2028 Some(Position(ChunkIdentifier(1), 1))
2029 );
2030 }
2031
2032 #[test]
2033 fn test_rchunks() {
2034 let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2035 linked_chunk.push_items_back(['a', 'b']);
2036 linked_chunk.push_gap_back(());
2037 linked_chunk.push_items_back(['c', 'd', 'e']);
2038
2039 let mut iterator = linked_chunk.rchunks();
2040
2041 assert_matches!(
2042 iterator.next(),
2043 Some(Chunk { identifier: ChunkIdentifier(3), content: ChunkContent::Items(items), .. }) => {
2044 assert_eq!(items, &['e']);
2045 }
2046 );
2047 assert_matches!(
2048 iterator.next(),
2049 Some(Chunk { identifier: ChunkIdentifier(2), content: ChunkContent::Items(items), .. }) => {
2050 assert_eq!(items, &['c', 'd']);
2051 }
2052 );
2053 assert_matches!(
2054 iterator.next(),
2055 Some(Chunk { identifier: ChunkIdentifier(1), content: ChunkContent::Gap(..), .. })
2056 );
2057 assert_matches!(
2058 iterator.next(),
2059 Some(Chunk { identifier: ChunkIdentifier(0), content: ChunkContent::Items(items), .. }) => {
2060 assert_eq!(items, &['a', 'b']);
2061 }
2062 );
2063 assert_matches!(iterator.next(), None);
2064 }
2065
2066 #[test]
2067 fn test_chunks() {
2068 let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2069 linked_chunk.push_items_back(['a', 'b']);
2070 linked_chunk.push_gap_back(());
2071 linked_chunk.push_items_back(['c', 'd', 'e']);
2072
2073 let mut iterator = linked_chunk.chunks();
2074
2075 assert_matches!(
2076 iterator.next(),
2077 Some(Chunk { identifier: ChunkIdentifier(0), content: ChunkContent::Items(items), .. }) => {
2078 assert_eq!(items, &['a', 'b']);
2079 }
2080 );
2081 assert_matches!(
2082 iterator.next(),
2083 Some(Chunk { identifier: ChunkIdentifier(1), content: ChunkContent::Gap(..), .. })
2084 );
2085 assert_matches!(
2086 iterator.next(),
2087 Some(Chunk { identifier: ChunkIdentifier(2), content: ChunkContent::Items(items), .. }) => {
2088 assert_eq!(items, &['c', 'd']);
2089 }
2090 );
2091 assert_matches!(
2092 iterator.next(),
2093 Some(Chunk { identifier: ChunkIdentifier(3), content: ChunkContent::Items(items), .. }) => {
2094 assert_eq!(items, &['e']);
2095 }
2096 );
2097 assert_matches!(iterator.next(), None);
2098 }
2099
2100 #[test]
2101 fn test_rchunks_from() -> Result<(), Error> {
2102 let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2103 linked_chunk.push_items_back(['a', 'b']);
2104 linked_chunk.push_gap_back(());
2105 linked_chunk.push_items_back(['c', 'd', 'e']);
2106
2107 let mut iterator = linked_chunk.rchunks_from(
2108 linked_chunk.item_position(|item| *item == 'c').unwrap().chunk_identifier(),
2109 )?;
2110
2111 assert_matches!(
2112 iterator.next(),
2113 Some(Chunk { identifier: ChunkIdentifier(2), content: ChunkContent::Items(items), .. }) => {
2114 assert_eq!(items, &['c', 'd']);
2115 }
2116 );
2117 assert_matches!(
2118 iterator.next(),
2119 Some(Chunk { identifier: ChunkIdentifier(1), content: ChunkContent::Gap(..), .. })
2120 );
2121 assert_matches!(
2122 iterator.next(),
2123 Some(Chunk { identifier: ChunkIdentifier(0), content: ChunkContent::Items(items), .. }) => {
2124 assert_eq!(items, &['a', 'b']);
2125 }
2126 );
2127 assert_matches!(iterator.next(), None);
2128
2129 Ok(())
2130 }
2131
2132 #[test]
2133 fn test_chunks_from() -> Result<(), Error> {
2134 let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2135 linked_chunk.push_items_back(['a', 'b']);
2136 linked_chunk.push_gap_back(());
2137 linked_chunk.push_items_back(['c', 'd', 'e']);
2138
2139 let mut iterator = linked_chunk.chunks_from(
2140 linked_chunk.item_position(|item| *item == 'c').unwrap().chunk_identifier(),
2141 )?;
2142
2143 assert_matches!(
2144 iterator.next(),
2145 Some(Chunk { identifier: ChunkIdentifier(2), content: ChunkContent::Items(items), .. }) => {
2146 assert_eq!(items, &['c', 'd']);
2147 }
2148 );
2149 assert_matches!(
2150 iterator.next(),
2151 Some(Chunk { identifier: ChunkIdentifier(3), content: ChunkContent::Items(items), .. }) => {
2152 assert_eq!(items, &['e']);
2153 }
2154 );
2155 assert_matches!(iterator.next(), None);
2156
2157 Ok(())
2158 }
2159
2160 #[test]
2161 fn test_ritems() {
2162 let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2163 linked_chunk.push_items_back(['a', 'b']);
2164 linked_chunk.push_gap_back(());
2165 linked_chunk.push_items_back(['c', 'd', 'e']);
2166
2167 let mut iterator = linked_chunk.ritems();
2168
2169 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(3), 0), 'e')));
2170 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 1), 'd')));
2171 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 0), 'c')));
2172 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 1), 'b')));
2173 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 0), 'a')));
2174 assert_matches!(iterator.next(), None);
2175 }
2176
2177 #[test]
2178 fn test_ritems_with_final_gap() -> Result<(), Error> {
2179 let mut linked_chunk = LinkedChunk::<3, char, ()>::new();
2180 linked_chunk.push_items_back(['a', 'b']);
2181 linked_chunk.push_gap_back(());
2182 linked_chunk.push_items_back(['c', 'd', 'e']);
2183 linked_chunk.push_gap_back(());
2184
2185 let mut iterator = linked_chunk.ritems();
2186
2187 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 2), 'e')));
2188 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 1), 'd')));
2189 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 0), 'c')));
2190 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 1), 'b')));
2191 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 0), 'a')));
2192 assert_matches!(iterator.next(), None);
2193
2194 Ok(())
2195 }
2196
2197 #[test]
2198 fn test_ritems_empty() {
2199 let linked_chunk = LinkedChunk::<2, char, ()>::new();
2200 let mut iterator = linked_chunk.ritems();
2201
2202 assert_matches!(iterator.next(), None);
2203 }
2204
2205 #[test]
2206 fn test_items() {
2207 let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2208 linked_chunk.push_items_back(['a', 'b']);
2209 linked_chunk.push_gap_back(());
2210 linked_chunk.push_items_back(['c', 'd', 'e']);
2211
2212 let mut iterator = linked_chunk.items();
2213
2214 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 0), 'a')));
2215 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 1), 'b')));
2216 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 0), 'c')));
2217 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 1), 'd')));
2218 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(3), 0), 'e')));
2219 assert_matches!(iterator.next(), None);
2220 }
2221
2222 #[test]
2223 fn test_items_empty() {
2224 let linked_chunk = LinkedChunk::<2, char, ()>::new();
2225 let mut iterator = linked_chunk.items();
2226
2227 assert_matches!(iterator.next(), None);
2228 }
2229
2230 #[test]
2231 fn test_ritems_from() -> Result<(), Error> {
2232 let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2233 linked_chunk.push_items_back(['a', 'b']);
2234 linked_chunk.push_gap_back(());
2235 linked_chunk.push_items_back(['c', 'd', 'e']);
2236
2237 let mut iterator =
2238 linked_chunk.ritems_from(linked_chunk.item_position(|item| *item == 'c').unwrap())?;
2239
2240 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 0), 'c')));
2241 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 1), 'b')));
2242 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(0), 0), 'a')));
2243 assert_matches!(iterator.next(), None);
2244
2245 Ok(())
2246 }
2247
2248 #[test]
2249 fn test_items_from() -> Result<(), Error> {
2250 let mut linked_chunk = LinkedChunk::<2, char, ()>::new();
2251 linked_chunk.push_items_back(['a', 'b']);
2252 linked_chunk.push_gap_back(());
2253 linked_chunk.push_items_back(['c', 'd', 'e']);
2254
2255 let mut iterator =
2256 linked_chunk.items_from(linked_chunk.item_position(|item| *item == 'c').unwrap())?;
2257
2258 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 0), 'c')));
2259 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(2), 1), 'd')));
2260 assert_matches!(iterator.next(), Some((Position(ChunkIdentifier(3), 0), 'e')));
2261 assert_matches!(iterator.next(), None);
2262
2263 Ok(())
2264 }
2265
2266 #[test]
2267 fn test_insert_items_at() -> Result<(), Error> {
2268 use super::Update::*;
2269
2270 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2271
2272 let _ = linked_chunk.updates().unwrap().take();
2274
2275 linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f']);
2276 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f']);
2277 assert_eq!(
2278 linked_chunk.updates().unwrap().take(),
2279 &[
2280 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2281 NewItemsChunk {
2282 previous: Some(ChunkIdentifier(0)),
2283 new: ChunkIdentifier(1),
2284 next: None,
2285 },
2286 PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e', 'f'] },
2287 ]
2288 );
2289
2290 {
2292 let pos_e = linked_chunk.item_position(|item| *item == 'e').unwrap();
2293
2294 linked_chunk.insert_items_at(pos_e, ['w', 'x', 'y', 'z'])?;
2297
2298 assert_items_eq!(
2299 linked_chunk,
2300 ['a', 'b', 'c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f']
2301 );
2302 assert_eq!(linked_chunk.num_items(), 10);
2303 assert_eq!(
2304 linked_chunk.updates().unwrap().take(),
2305 &[
2306 DetachLastItems { at: Position(ChunkIdentifier(1), 1) },
2307 PushItems { at: Position(ChunkIdentifier(1), 1), items: vec!['w', 'x'] },
2308 NewItemsChunk {
2309 previous: Some(ChunkIdentifier(1)),
2310 new: ChunkIdentifier(2),
2311 next: None,
2312 },
2313 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['y', 'z'] },
2314 StartReattachItems,
2315 PushItems { at: Position(ChunkIdentifier(2), 2), items: vec!['e'] },
2316 NewItemsChunk {
2317 previous: Some(ChunkIdentifier(2)),
2318 new: ChunkIdentifier(3),
2319 next: None,
2320 },
2321 PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['f'] },
2322 EndReattachItems,
2323 ]
2324 );
2325 }
2326
2327 {
2329 let pos_a = linked_chunk.item_position(|item| *item == 'a').unwrap();
2330 linked_chunk.insert_items_at(pos_a, ['l', 'm', 'n', 'o'])?;
2331
2332 assert_items_eq!(
2333 linked_chunk,
2334 ['l', 'm', 'n'] ['o', 'a', 'b'] ['c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f']
2335 );
2336 assert_eq!(linked_chunk.num_items(), 14);
2337 assert_eq!(
2338 linked_chunk.updates().unwrap().take(),
2339 &[
2340 DetachLastItems { at: Position(ChunkIdentifier(0), 0) },
2341 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['l', 'm', 'n'] },
2342 NewItemsChunk {
2343 previous: Some(ChunkIdentifier(0)),
2344 new: ChunkIdentifier(4),
2345 next: Some(ChunkIdentifier(1)),
2346 },
2347 PushItems { at: Position(ChunkIdentifier(4), 0), items: vec!['o'] },
2348 StartReattachItems,
2349 PushItems { at: Position(ChunkIdentifier(4), 1), items: vec!['a', 'b'] },
2350 NewItemsChunk {
2351 previous: Some(ChunkIdentifier(4)),
2352 new: ChunkIdentifier(5),
2353 next: Some(ChunkIdentifier(1)),
2354 },
2355 PushItems { at: Position(ChunkIdentifier(5), 0), items: vec!['c'] },
2356 EndReattachItems,
2357 ]
2358 );
2359 }
2360
2361 {
2363 let pos_c = linked_chunk.item_position(|item| *item == 'c').unwrap();
2364 linked_chunk.insert_items_at(pos_c, ['r', 's'])?;
2365
2366 assert_items_eq!(
2367 linked_chunk,
2368 ['l', 'm', 'n'] ['o', 'a', 'b'] ['r', 's', 'c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f']
2369 );
2370 assert_eq!(linked_chunk.num_items(), 16);
2371 assert_eq!(
2372 linked_chunk.updates().unwrap().take(),
2373 &[
2374 DetachLastItems { at: Position(ChunkIdentifier(5), 0) },
2375 PushItems { at: Position(ChunkIdentifier(5), 0), items: vec!['r', 's'] },
2376 StartReattachItems,
2377 PushItems { at: Position(ChunkIdentifier(5), 2), items: vec!['c'] },
2378 EndReattachItems,
2379 ]
2380 );
2381 }
2382
2383 {
2385 let pos_f = linked_chunk.item_position(|item| *item == 'f').unwrap();
2386 let pos_f = Position(pos_f.chunk_identifier(), pos_f.index() + 1);
2387
2388 linked_chunk.insert_items_at(pos_f, ['p', 'q'])?;
2389 assert_items_eq!(
2390 linked_chunk,
2391 ['l', 'm', 'n'] ['o', 'a', 'b'] ['r', 's', 'c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f', 'p', 'q']
2392 );
2393 assert_eq!(
2394 linked_chunk.updates().unwrap().take(),
2395 &[PushItems { at: Position(ChunkIdentifier(3), 1), items: vec!['p', 'q'] }]
2396 );
2397 assert_eq!(linked_chunk.num_items(), 18);
2398 }
2399
2400 {
2402 assert_matches!(
2403 linked_chunk.insert_items_at(Position(ChunkIdentifier(128), 0), ['u', 'v'],),
2404 Err(Error::InvalidChunkIdentifier { identifier: ChunkIdentifier(128) })
2405 );
2406 assert!(linked_chunk.updates().unwrap().take().is_empty());
2407 }
2408
2409 {
2411 assert_matches!(
2412 linked_chunk.insert_items_at(Position(ChunkIdentifier(0), 128), ['u', 'v'],),
2413 Err(Error::InvalidItemIndex { index: 128 })
2414 );
2415 assert!(linked_chunk.updates().unwrap().take().is_empty());
2416 }
2417
2418 {
2420 linked_chunk.push_gap_back(());
2422 assert_items_eq!(
2423 linked_chunk,
2424 ['l', 'm', 'n'] ['o', 'a', 'b'] ['r', 's', 'c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f', 'p', 'q'] [-]
2425 );
2426 assert_eq!(
2427 linked_chunk.updates().unwrap().take(),
2428 &[NewGapChunk {
2429 previous: Some(ChunkIdentifier(3)),
2430 new: ChunkIdentifier(6),
2431 next: None,
2432 gap: ()
2433 }]
2434 );
2435
2436 assert_matches!(
2437 linked_chunk.insert_items_at(Position(ChunkIdentifier(6), 0), ['u', 'v'],),
2438 Err(Error::ChunkIsAGap { identifier: ChunkIdentifier(6) })
2439 );
2440 }
2441
2442 assert_eq!(linked_chunk.num_items(), 18);
2443
2444 Ok(())
2445 }
2446
2447 #[test]
2448 fn test_insert_items_at_last_chunk() -> Result<(), Error> {
2449 use super::Update::*;
2450
2451 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2452
2453 let _ = linked_chunk.updates().unwrap().take();
2455
2456 linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f']);
2457 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f']);
2458 assert_eq!(
2459 linked_chunk.updates().unwrap().take(),
2460 &[
2461 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2462 NewItemsChunk {
2463 previous: Some(ChunkIdentifier(0)),
2464 new: ChunkIdentifier(1),
2465 next: None,
2466 },
2467 PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e', 'f'] },
2468 ]
2469 );
2470
2471 let pos_e = linked_chunk.item_position(|item| *item == 'e').unwrap();
2473
2474 linked_chunk.insert_items_at(pos_e, ['w', 'x', 'y', 'z'])?;
2477
2478 assert_items_eq!(
2479 linked_chunk,
2480 ['a', 'b', 'c'] ['d', 'w', 'x'] ['y', 'z', 'e'] ['f']
2481 );
2482 assert_eq!(linked_chunk.num_items(), 10);
2483 assert_eq!(
2484 linked_chunk.updates().unwrap().take(),
2485 &[
2486 DetachLastItems { at: Position(ChunkIdentifier(1), 1) },
2487 PushItems { at: Position(ChunkIdentifier(1), 1), items: vec!['w', 'x'] },
2488 NewItemsChunk {
2489 previous: Some(ChunkIdentifier(1)),
2490 new: ChunkIdentifier(2),
2491 next: None,
2492 },
2493 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['y', 'z'] },
2494 StartReattachItems,
2495 PushItems { at: Position(ChunkIdentifier(2), 2), items: vec!['e'] },
2496 NewItemsChunk {
2497 previous: Some(ChunkIdentifier(2)),
2498 new: ChunkIdentifier(3),
2499 next: None,
2500 },
2501 PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['f'] },
2502 EndReattachItems,
2503 ]
2504 );
2505
2506 Ok(())
2507 }
2508
2509 #[test]
2510 fn test_insert_items_at_first_chunk() -> Result<(), Error> {
2511 use super::Update::*;
2512
2513 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2514
2515 let _ = linked_chunk.updates().unwrap().take();
2517
2518 linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f']);
2519 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f']);
2520 assert_eq!(
2521 linked_chunk.updates().unwrap().take(),
2522 &[
2523 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2524 NewItemsChunk {
2525 previous: Some(ChunkIdentifier(0)),
2526 new: ChunkIdentifier(1),
2527 next: None,
2528 },
2529 PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e', 'f'] },
2530 ]
2531 );
2532
2533 let pos_a = linked_chunk.item_position(|item| *item == 'a').unwrap();
2535 linked_chunk.insert_items_at(pos_a, ['l', 'm', 'n', 'o'])?;
2536
2537 assert_items_eq!(
2538 linked_chunk,
2539 ['l', 'm', 'n'] ['o', 'a', 'b'] ['c'] ['d', 'e', 'f']
2540 );
2541 assert_eq!(linked_chunk.num_items(), 10);
2542 assert_eq!(
2543 linked_chunk.updates().unwrap().take(),
2544 &[
2545 DetachLastItems { at: Position(ChunkIdentifier(0), 0) },
2546 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['l', 'm', 'n'] },
2547 NewItemsChunk {
2548 previous: Some(ChunkIdentifier(0)),
2549 new: ChunkIdentifier(2),
2550 next: Some(ChunkIdentifier(1)),
2551 },
2552 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['o'] },
2553 StartReattachItems,
2554 PushItems { at: Position(ChunkIdentifier(2), 1), items: vec!['a', 'b'] },
2555 NewItemsChunk {
2556 previous: Some(ChunkIdentifier(2)),
2557 new: ChunkIdentifier(3),
2558 next: Some(ChunkIdentifier(1)),
2559 },
2560 PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['c'] },
2561 EndReattachItems,
2562 ]
2563 );
2564
2565 Ok(())
2566 }
2567
2568 #[test]
2569 fn test_insert_items_at_middle_chunk() -> Result<(), Error> {
2570 use super::Update::*;
2571
2572 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2573
2574 let _ = linked_chunk.updates().unwrap().take();
2576
2577 linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']);
2578 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f'] ['g', 'h']);
2579 assert_eq!(
2580 linked_chunk.updates().unwrap().take(),
2581 &[
2582 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2583 NewItemsChunk {
2584 previous: Some(ChunkIdentifier(0)),
2585 new: ChunkIdentifier(1),
2586 next: None,
2587 },
2588 PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e', 'f'] },
2589 NewItemsChunk {
2590 previous: Some(ChunkIdentifier(1)),
2591 new: ChunkIdentifier(2),
2592 next: None,
2593 },
2594 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['g', 'h'] },
2595 ]
2596 );
2597
2598 let pos_d = linked_chunk.item_position(|item| *item == 'd').unwrap();
2599 linked_chunk.insert_items_at(pos_d, ['r', 's'])?;
2600
2601 assert_items_eq!(
2602 linked_chunk,
2603 ['a', 'b', 'c'] ['r', 's', 'd'] ['e', 'f'] ['g', 'h']
2604 );
2605 assert_eq!(linked_chunk.num_items(), 10);
2606 assert_eq!(
2607 linked_chunk.updates().unwrap().take(),
2608 &[
2609 DetachLastItems { at: Position(ChunkIdentifier(1), 0) },
2610 PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['r', 's'] },
2611 StartReattachItems,
2612 PushItems { at: Position(ChunkIdentifier(1), 2), items: vec!['d'] },
2613 NewItemsChunk {
2614 previous: Some(ChunkIdentifier(1)),
2615 new: ChunkIdentifier(3),
2616 next: Some(ChunkIdentifier(2)),
2617 },
2618 PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['e', 'f'] },
2619 EndReattachItems,
2620 ]
2621 );
2622
2623 Ok(())
2624 }
2625
2626 #[test]
2627 fn test_insert_items_at_end_of_chunk() -> Result<(), Error> {
2628 use super::Update::*;
2629
2630 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2631
2632 let _ = linked_chunk.updates().unwrap().take();
2634
2635 linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e']);
2636 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e']);
2637 assert_eq!(
2638 linked_chunk.updates().unwrap().take(),
2639 &[
2640 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2641 NewItemsChunk {
2642 previous: Some(ChunkIdentifier(0)),
2643 new: ChunkIdentifier(1),
2644 next: None,
2645 },
2646 PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e'] },
2647 ]
2648 );
2649
2650 let pos_e = linked_chunk.item_position(|item| *item == 'e').unwrap();
2652 let pos_after_e = Position(pos_e.chunk_identifier(), pos_e.index() + 1);
2653
2654 linked_chunk.insert_items_at(pos_after_e, ['p', 'q'])?;
2655 assert_items_eq!(
2656 linked_chunk,
2657 ['a', 'b', 'c'] ['d', 'e', 'p'] ['q']
2658 );
2659 assert_eq!(
2660 linked_chunk.updates().unwrap().take(),
2661 &[
2662 PushItems { at: Position(ChunkIdentifier(1), 2), items: vec!['p'] },
2663 NewItemsChunk {
2664 previous: Some(ChunkIdentifier(1)),
2665 new: ChunkIdentifier(2),
2666 next: None
2667 },
2668 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['q'] }
2669 ]
2670 );
2671 assert_eq!(linked_chunk.num_items(), 7);
2672
2673 Ok(())
2674 }
2675
2676 #[test]
2677 fn test_insert_items_at_errs() -> Result<(), Error> {
2678 use super::Update::*;
2679
2680 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2681
2682 let _ = linked_chunk.updates().unwrap().take();
2684
2685 linked_chunk.push_items_back(['a', 'b', 'c']);
2686 linked_chunk.push_gap_back(());
2687 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] [-]);
2688 assert_eq!(
2689 linked_chunk.updates().unwrap().take(),
2690 &[
2691 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2692 NewGapChunk {
2693 previous: Some(ChunkIdentifier(0)),
2694 new: ChunkIdentifier(1),
2695 next: None,
2696 gap: (),
2697 },
2698 ]
2699 );
2700
2701 {
2703 assert_matches!(
2704 linked_chunk.insert_items_at(Position(ChunkIdentifier(128), 0), ['u', 'v'],),
2705 Err(Error::InvalidChunkIdentifier { identifier: ChunkIdentifier(128) })
2706 );
2707 assert!(linked_chunk.updates().unwrap().take().is_empty());
2708 }
2709
2710 {
2712 assert_matches!(
2713 linked_chunk.insert_items_at(Position(ChunkIdentifier(0), 128), ['u', 'v'],),
2714 Err(Error::InvalidItemIndex { index: 128 })
2715 );
2716 assert!(linked_chunk.updates().unwrap().take().is_empty());
2717 }
2718
2719 {
2721 assert_matches!(
2722 linked_chunk.insert_items_at(Position(ChunkIdentifier(1), 0), ['u', 'v'],),
2723 Err(Error::ChunkIsAGap { identifier: ChunkIdentifier(1) })
2724 );
2725 }
2726
2727 Ok(())
2728 }
2729
2730 #[test]
2731 fn test_remove_item_at() -> Result<(), Error> {
2732 use super::Update::*;
2733
2734 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2735
2736 let _ = linked_chunk.updates().unwrap().take();
2738
2739 linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']);
2740 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f'] ['g', 'h', 'i'] ['j', 'k']);
2741 assert_eq!(linked_chunk.num_items(), 11);
2742
2743 let _ = linked_chunk.updates().unwrap().take();
2745
2746 {
2749 let position_of_f = linked_chunk.item_position(|item| *item == 'f').unwrap();
2750 let removed_item = linked_chunk.remove_item_at(position_of_f)?;
2751
2752 assert_eq!(removed_item, 'f');
2753 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e'] ['g', 'h', 'i'] ['j', 'k']);
2754 assert_eq!(linked_chunk.num_items(), 10);
2755
2756 let position_of_e = linked_chunk.item_position(|item| *item == 'e').unwrap();
2757 let removed_item = linked_chunk.remove_item_at(position_of_e)?;
2758
2759 assert_eq!(removed_item, 'e');
2760 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d'] ['g', 'h', 'i'] ['j', 'k']);
2761 assert_eq!(linked_chunk.num_items(), 9);
2762
2763 let position_of_d = linked_chunk.item_position(|item| *item == 'd').unwrap();
2764 let removed_item = linked_chunk.remove_item_at(position_of_d)?;
2765
2766 assert_eq!(removed_item, 'd');
2767 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['g', 'h', 'i'] ['j', 'k']);
2768 assert_eq!(linked_chunk.num_items(), 8);
2769
2770 assert_eq!(
2771 linked_chunk.updates().unwrap().take(),
2772 &[
2773 RemoveItem { at: Position(ChunkIdentifier(1), 2) },
2774 RemoveItem { at: Position(ChunkIdentifier(1), 1) },
2775 RemoveItem { at: Position(ChunkIdentifier(1), 0) },
2776 RemoveChunk(ChunkIdentifier(1)),
2777 ]
2778 );
2779 }
2780
2781 {
2784 let first_position = linked_chunk.item_position(|item| *item == 'a').unwrap();
2785 let removed_item = linked_chunk.remove_item_at(first_position)?;
2786
2787 assert_eq!(removed_item, 'a');
2788 assert_items_eq!(linked_chunk, ['b', 'c'] ['g', 'h', 'i'] ['j', 'k']);
2789 assert_eq!(linked_chunk.num_items(), 7);
2790
2791 let removed_item = linked_chunk.remove_item_at(first_position)?;
2792
2793 assert_eq!(removed_item, 'b');
2794 assert_items_eq!(linked_chunk, ['c'] ['g', 'h', 'i'] ['j', 'k']);
2795 assert_eq!(linked_chunk.num_items(), 6);
2796
2797 let removed_item = linked_chunk.remove_item_at(first_position)?;
2798
2799 assert_eq!(removed_item, 'c');
2800 assert_items_eq!(linked_chunk, [] ['g', 'h', 'i'] ['j', 'k']);
2801 assert_eq!(linked_chunk.num_items(), 5);
2802
2803 assert_eq!(
2804 linked_chunk.updates().unwrap().take(),
2805 &[
2806 RemoveItem { at: Position(ChunkIdentifier(0), 0) },
2807 RemoveItem { at: Position(ChunkIdentifier(0), 0) },
2808 RemoveItem { at: Position(ChunkIdentifier(0), 0) },
2809 ]
2810 );
2811 }
2812
2813 {
2816 let first_position = linked_chunk.item_position(|item| *item == 'g').unwrap();
2817 let removed_item = linked_chunk.remove_item_at(first_position)?;
2818
2819 assert_eq!(removed_item, 'g');
2820 assert_items_eq!(linked_chunk, [] ['h', 'i'] ['j', 'k']);
2821 assert_eq!(linked_chunk.num_items(), 4);
2822
2823 let removed_item = linked_chunk.remove_item_at(first_position)?;
2824
2825 assert_eq!(removed_item, 'h');
2826 assert_items_eq!(linked_chunk, [] ['i'] ['j', 'k']);
2827 assert_eq!(linked_chunk.num_items(), 3);
2828
2829 let removed_item = linked_chunk.remove_item_at(first_position)?;
2830
2831 assert_eq!(removed_item, 'i');
2832 assert_items_eq!(linked_chunk, [] ['j', 'k']);
2833 assert_eq!(linked_chunk.num_items(), 2);
2834
2835 assert_eq!(
2836 linked_chunk.updates().unwrap().take(),
2837 &[
2838 RemoveItem { at: Position(ChunkIdentifier(2), 0) },
2839 RemoveItem { at: Position(ChunkIdentifier(2), 0) },
2840 RemoveItem { at: Position(ChunkIdentifier(2), 0) },
2841 RemoveChunk(ChunkIdentifier(2)),
2842 ]
2843 );
2844 }
2845
2846 {
2849 let position_of_k = linked_chunk.item_position(|item| *item == 'k').unwrap();
2850 let removed_item = linked_chunk.remove_item_at(position_of_k)?;
2851
2852 assert_eq!(removed_item, 'k');
2853 #[rustfmt::skip]
2854 assert_items_eq!(linked_chunk, [] ['j']);
2855 assert_eq!(linked_chunk.num_items(), 1);
2856
2857 let position_of_j = linked_chunk.item_position(|item| *item == 'j').unwrap();
2858 let removed_item = linked_chunk.remove_item_at(position_of_j)?;
2859
2860 assert_eq!(removed_item, 'j');
2861 assert_items_eq!(linked_chunk, []);
2862 assert_eq!(linked_chunk.num_items(), 0);
2863
2864 assert_eq!(
2865 linked_chunk.updates().unwrap().take(),
2866 &[
2867 RemoveItem { at: Position(ChunkIdentifier(3), 1) },
2868 RemoveItem { at: Position(ChunkIdentifier(3), 0) },
2869 RemoveChunk(ChunkIdentifier(3)),
2870 ]
2871 );
2872 }
2873
2874 {
2876 linked_chunk.push_items_back(['a', 'b', 'c', 'd']);
2877
2878 #[rustfmt::skip]
2879 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d']);
2880 assert_eq!(linked_chunk.num_items(), 4);
2881
2882 let position_of_c = linked_chunk.item_position(|item| *item == 'c').unwrap();
2883 linked_chunk.insert_gap_at((), position_of_c)?;
2884
2885 assert_items_eq!(linked_chunk, ['a', 'b'] [-] ['c'] ['d']);
2886 assert_eq!(linked_chunk.num_items(), 4);
2887
2888 let _ = linked_chunk.updates().unwrap().take();
2890
2891 let position_of_c = linked_chunk.item_position(|item| *item == 'c').unwrap();
2892 let removed_item = linked_chunk.remove_item_at(position_of_c)?;
2893
2894 assert_eq!(removed_item, 'c');
2895 assert_items_eq!(linked_chunk, ['a', 'b'] [-] ['d']);
2896 assert_eq!(linked_chunk.num_items(), 3);
2897
2898 let position_of_d = linked_chunk.item_position(|item| *item == 'd').unwrap();
2899 let removed_item = linked_chunk.remove_item_at(position_of_d)?;
2900
2901 assert_eq!(removed_item, 'd');
2902 assert_items_eq!(linked_chunk, ['a', 'b'] [-]);
2903 assert_eq!(linked_chunk.num_items(), 2);
2904
2905 let first_position = linked_chunk.item_position(|item| *item == 'a').unwrap();
2906 let removed_item = linked_chunk.remove_item_at(first_position)?;
2907
2908 assert_eq!(removed_item, 'a');
2909 assert_items_eq!(linked_chunk, ['b'] [-]);
2910 assert_eq!(linked_chunk.num_items(), 1);
2911
2912 let removed_item = linked_chunk.remove_item_at(first_position)?;
2913
2914 assert_eq!(removed_item, 'b');
2915 assert_items_eq!(linked_chunk, [] [-]);
2916 assert_eq!(linked_chunk.num_items(), 0);
2917
2918 assert_eq!(
2919 linked_chunk.updates().unwrap().take(),
2920 &[
2921 RemoveItem { at: Position(ChunkIdentifier(6), 0) },
2922 RemoveChunk(ChunkIdentifier(6)),
2923 RemoveItem { at: Position(ChunkIdentifier(4), 0) },
2924 RemoveChunk(ChunkIdentifier(4)),
2925 RemoveItem { at: Position(ChunkIdentifier(0), 0) },
2926 RemoveItem { at: Position(ChunkIdentifier(0), 0) },
2927 ]
2928 );
2929 }
2930
2931 Ok(())
2932 }
2933
2934 #[test]
2935 fn test_insert_gap_at() -> Result<(), Error> {
2936 use super::Update::*;
2937
2938 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
2939
2940 let _ = linked_chunk.updates().unwrap().take();
2942
2943 linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f']);
2944 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e', 'f']);
2945 assert_eq!(
2946 linked_chunk.updates().unwrap().take(),
2947 &[
2948 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b', 'c'] },
2949 NewItemsChunk {
2950 previous: Some(ChunkIdentifier(0)),
2951 new: ChunkIdentifier(1),
2952 next: None
2953 },
2954 PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['d', 'e', 'f'] },
2955 ]
2956 );
2957
2958 {
2960 let position_of_b = linked_chunk.item_position(|item| *item == 'b').unwrap();
2961 linked_chunk.insert_gap_at((), position_of_b)?;
2962
2963 assert_items_eq!(linked_chunk, ['a'] [-] ['b', 'c'] ['d', 'e', 'f']);
2964 assert_eq!(
2965 linked_chunk.updates().unwrap().take(),
2966 &[
2967 DetachLastItems { at: Position(ChunkIdentifier(0), 1) },
2968 NewGapChunk {
2969 previous: Some(ChunkIdentifier(0)),
2970 new: ChunkIdentifier(2),
2971 next: Some(ChunkIdentifier(1)),
2972 gap: (),
2973 },
2974 StartReattachItems,
2975 NewItemsChunk {
2976 previous: Some(ChunkIdentifier(2)),
2977 new: ChunkIdentifier(3),
2978 next: Some(ChunkIdentifier(1)),
2979 },
2980 PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['b', 'c'] },
2981 EndReattachItems,
2982 ]
2983 );
2984 }
2985
2986 {
2989 let position_of_a = linked_chunk.item_position(|item| *item == 'a').unwrap();
2990 linked_chunk.insert_gap_at((), position_of_a)?;
2991
2992 assert_items_eq!(linked_chunk, [-] ['a'] [-] ['b', 'c'] ['d', 'e', 'f']);
2995 assert_eq!(
2996 linked_chunk.updates().unwrap().take(),
2997 &[NewGapChunk {
2998 previous: None,
2999 new: ChunkIdentifier(4),
3000 next: Some(ChunkIdentifier(0)),
3001 gap: (),
3002 },]
3003 );
3004 }
3005
3006 {
3009 let position_of_d = linked_chunk.item_position(|item| *item == 'd').unwrap();
3010 linked_chunk.insert_gap_at((), position_of_d)?;
3011
3012 assert_items_eq!(linked_chunk, [-] ['a'] [-] ['b', 'c'] [-] ['d', 'e', 'f']);
3016 assert_eq!(
3017 linked_chunk.updates().unwrap().take(),
3018 &[NewGapChunk {
3019 previous: Some(ChunkIdentifier(3)),
3020 new: ChunkIdentifier(5),
3021 next: Some(ChunkIdentifier(1)),
3022 gap: (),
3023 }]
3024 );
3025 }
3026
3027 {
3029 let gap_identifier = linked_chunk.chunk_identifier(Chunk::is_gap).unwrap();
3031 let position = linked_chunk.replace_gap_at([], gap_identifier)?.first_position();
3032
3033 assert_items_eq!(linked_chunk, [-] ['a'] [-] ['b', 'c'] [] ['d', 'e', 'f']);
3034
3035 assert_eq!(
3036 linked_chunk.updates().unwrap().take(),
3037 &[
3038 NewItemsChunk {
3039 previous: Some(ChunkIdentifier(5)),
3040 new: ChunkIdentifier(6),
3041 next: Some(ChunkIdentifier(1)),
3042 },
3043 RemoveChunk(ChunkIdentifier(5)),
3044 ]
3045 );
3046
3047 linked_chunk.insert_gap_at((), position)?;
3048
3049 assert_items_eq!(linked_chunk, [-] ['a'] [-] ['b', 'c'] [-] [] ['d', 'e', 'f']);
3050 assert_eq!(
3051 linked_chunk.updates().unwrap().take(),
3052 &[NewGapChunk {
3053 previous: Some(ChunkIdentifier(3)),
3054 new: ChunkIdentifier(7),
3055 next: Some(ChunkIdentifier(6)),
3056 gap: (),
3057 }]
3058 );
3059 }
3060
3061 {
3063 assert_matches!(
3064 linked_chunk.insert_items_at(Position(ChunkIdentifier(128), 0), ['u', 'v'],),
3065 Err(Error::InvalidChunkIdentifier { identifier: ChunkIdentifier(128) })
3066 );
3067 assert!(linked_chunk.updates().unwrap().take().is_empty());
3068 }
3069
3070 {
3072 assert_matches!(
3073 linked_chunk.insert_items_at(Position(ChunkIdentifier(0), 128), ['u', 'v'],),
3074 Err(Error::InvalidItemIndex { index: 128 })
3075 );
3076 assert!(linked_chunk.updates().unwrap().take().is_empty());
3077 }
3078
3079 {
3081 let position_of_a_gap = Position(ChunkIdentifier(2), 0);
3084 assert_matches!(
3085 linked_chunk.insert_gap_at((), position_of_a_gap),
3086 Err(Error::ChunkIsAGap { identifier: ChunkIdentifier(2) })
3087 );
3088 assert!(linked_chunk.updates().unwrap().take().is_empty());
3089 }
3090
3091 assert_eq!(linked_chunk.num_items(), 6);
3092
3093 Ok(())
3094 }
3095
3096 #[test]
3097 fn test_replace_gap_at_middle() -> Result<(), Error> {
3098 use super::Update::*;
3099
3100 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3101
3102 let _ = linked_chunk.updates().unwrap().take();
3104
3105 linked_chunk.push_items_back(['a', 'b']);
3106 linked_chunk.push_gap_back(());
3107 linked_chunk.push_items_back(['l', 'm']);
3108 assert_items_eq!(linked_chunk, ['a', 'b'] [-] ['l', 'm']);
3109 assert_eq!(
3110 linked_chunk.updates().unwrap().take(),
3111 &[
3112 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b'] },
3113 NewGapChunk {
3114 previous: Some(ChunkIdentifier(0)),
3115 new: ChunkIdentifier(1),
3116 next: None,
3117 gap: (),
3118 },
3119 NewItemsChunk {
3120 previous: Some(ChunkIdentifier(1)),
3121 new: ChunkIdentifier(2),
3122 next: None,
3123 },
3124 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['l', 'm'] }
3125 ]
3126 );
3127
3128 let gap_identifier = linked_chunk.chunk_identifier(Chunk::is_gap).unwrap();
3130 assert_eq!(gap_identifier, ChunkIdentifier(1));
3131
3132 let new_chunk = linked_chunk.replace_gap_at(['d', 'e', 'f', 'g', 'h'], gap_identifier)?;
3133 assert_eq!(new_chunk.identifier(), ChunkIdentifier(3));
3134 assert_items_eq!(
3135 linked_chunk,
3136 ['a', 'b'] ['d', 'e', 'f'] ['g', 'h'] ['l', 'm']
3137 );
3138 assert_eq!(
3139 linked_chunk.updates().unwrap().take(),
3140 &[
3141 NewItemsChunk {
3142 previous: Some(ChunkIdentifier(1)),
3143 new: ChunkIdentifier(3),
3144 next: Some(ChunkIdentifier(2)),
3145 },
3146 PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['d', 'e', 'f'] },
3147 NewItemsChunk {
3148 previous: Some(ChunkIdentifier(3)),
3149 new: ChunkIdentifier(4),
3150 next: Some(ChunkIdentifier(2)),
3151 },
3152 PushItems { at: Position(ChunkIdentifier(4), 0), items: vec!['g', 'h'] },
3153 RemoveChunk(ChunkIdentifier(1)),
3154 ]
3155 );
3156
3157 assert_eq!(linked_chunk.num_items(), 9);
3158
3159 Ok(())
3160 }
3161
3162 #[test]
3163 fn test_replace_gap_at_end() -> Result<(), Error> {
3164 use super::Update::*;
3165
3166 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3167
3168 let _ = linked_chunk.updates().unwrap().take();
3170
3171 linked_chunk.push_items_back(['a', 'b']);
3172 linked_chunk.push_gap_back(());
3173 assert_items_eq!(linked_chunk, ['a', 'b'] [-]);
3174 assert_eq!(
3175 linked_chunk.updates().unwrap().take(),
3176 &[
3177 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b'] },
3178 NewGapChunk {
3179 previous: Some(ChunkIdentifier(0)),
3180 new: ChunkIdentifier(1),
3181 next: None,
3182 gap: (),
3183 },
3184 ]
3185 );
3186
3187 let gap_identifier = linked_chunk.chunk_identifier(Chunk::is_gap).unwrap();
3189 assert_eq!(gap_identifier, ChunkIdentifier(1));
3190
3191 let new_chunk = linked_chunk.replace_gap_at(['w', 'x', 'y', 'z'], gap_identifier)?;
3192 assert_eq!(new_chunk.identifier(), ChunkIdentifier(2));
3193 assert_items_eq!(
3194 linked_chunk,
3195 ['a', 'b'] ['w', 'x', 'y'] ['z']
3196 );
3197 assert_eq!(
3198 linked_chunk.updates().unwrap().take(),
3199 &[
3200 NewItemsChunk {
3201 previous: Some(ChunkIdentifier(1)),
3202 new: ChunkIdentifier(2),
3203 next: None,
3204 },
3205 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['w', 'x', 'y'] },
3206 NewItemsChunk {
3207 previous: Some(ChunkIdentifier(2)),
3208 new: ChunkIdentifier(3),
3209 next: None,
3210 },
3211 PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['z'] },
3212 RemoveChunk(ChunkIdentifier(1)),
3213 ]
3214 );
3215
3216 assert_eq!(linked_chunk.num_items(), 6);
3217
3218 Ok(())
3219 }
3220
3221 #[test]
3222 fn test_replace_gap_at_beginning() -> Result<(), Error> {
3223 use super::Update::*;
3224
3225 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3226
3227 let _ = linked_chunk.updates().unwrap().take();
3229
3230 linked_chunk.push_items_back(['a', 'b']);
3231 assert_items_eq!(linked_chunk, ['a', 'b']);
3232 assert_eq!(
3233 linked_chunk.updates().unwrap().take(),
3234 &[PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b'] },]
3235 );
3236
3237 let position_of_a = linked_chunk.item_position(|item| *item == 'a').unwrap();
3239 linked_chunk.insert_gap_at((), position_of_a).unwrap();
3240 assert_items_eq!(
3241 linked_chunk,
3242 [-] ['a', 'b']
3243 );
3244 assert_eq!(
3245 linked_chunk.updates().unwrap().take(),
3246 &[NewGapChunk {
3247 previous: None,
3248 new: ChunkIdentifier(1),
3249 next: Some(ChunkIdentifier(0)),
3250 gap: (),
3251 }]
3252 );
3253
3254 let gap_identifier = linked_chunk.chunk_identifier(Chunk::is_gap).unwrap();
3255 assert_eq!(gap_identifier, ChunkIdentifier(1));
3256
3257 let new_chunk = linked_chunk.replace_gap_at(['x'], gap_identifier)?;
3258 assert_eq!(new_chunk.identifier(), ChunkIdentifier(2));
3259 assert_items_eq!(
3260 linked_chunk,
3261 ['x'] ['a', 'b']
3262 );
3263 assert_eq!(
3264 linked_chunk.updates().unwrap().take(),
3265 &[
3266 NewItemsChunk {
3267 previous: Some(ChunkIdentifier(1)),
3268 new: ChunkIdentifier(2),
3269 next: Some(ChunkIdentifier(0)),
3270 },
3271 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['x'] },
3272 RemoveChunk(ChunkIdentifier(1)),
3273 ]
3274 );
3275
3276 assert_eq!(linked_chunk.num_items(), 3);
3277
3278 Ok(())
3279 }
3280
3281 #[test]
3282 fn test_remove_empty_chunk_at() -> Result<(), Error> {
3283 use super::Update::*;
3284
3285 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3286
3287 let _ = linked_chunk.updates().unwrap().take();
3289
3290 linked_chunk.insert_gap_at((), Position(ChunkIdentifier(0), 0)).unwrap();
3291 linked_chunk.push_items_back(['a', 'b']);
3292 linked_chunk.push_gap_back(());
3293 linked_chunk.push_items_back(['l', 'm']);
3294 linked_chunk.push_gap_back(());
3295 assert_items_eq!(linked_chunk, [-] ['a', 'b'] [-] ['l', 'm'] [-]);
3296 assert_eq!(
3297 linked_chunk.updates().unwrap().take(),
3298 &[
3299 NewGapChunk {
3300 previous: None,
3301 new: ChunkIdentifier(1),
3302 next: Some(ChunkIdentifier(0)),
3303 gap: (),
3304 },
3305 PushItems { at: Position(ChunkIdentifier(0), 0), items: vec!['a', 'b'] },
3306 NewGapChunk {
3307 previous: Some(ChunkIdentifier(0)),
3308 new: ChunkIdentifier(2),
3309 next: None,
3310 gap: (),
3311 },
3312 NewItemsChunk {
3313 previous: Some(ChunkIdentifier(2)),
3314 new: ChunkIdentifier(3),
3315 next: None,
3316 },
3317 PushItems { at: Position(ChunkIdentifier(3), 0), items: vec!['l', 'm'] },
3318 NewGapChunk {
3319 previous: Some(ChunkIdentifier(3)),
3320 new: ChunkIdentifier(4),
3321 next: None,
3322 gap: (),
3323 },
3324 ]
3325 );
3326
3327 let err = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(0)).unwrap_err();
3329 assert_matches!(err, Error::RemovingNonEmptyItemsChunk { .. });
3330
3331 let err = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(42)).unwrap_err();
3333 assert_matches!(err, Error::InvalidChunkIdentifier { .. });
3334
3335 let maybe_next = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(2)).unwrap();
3337 let next = maybe_next.unwrap();
3338 assert_eq!(next.chunk_identifier(), ChunkIdentifier(3));
3340 assert_eq!(next.index(), 0);
3341 assert_items_eq!(linked_chunk, [-] ['a', 'b'] ['l', 'm'] [-]);
3342 assert_eq!(linked_chunk.updates().unwrap().take(), &[RemoveChunk(ChunkIdentifier(2))]);
3343
3344 let next = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(4)).unwrap();
3346 assert!(next.is_none());
3348 assert_items_eq!(linked_chunk, [-] ['a', 'b'] ['l', 'm']);
3349 assert_eq!(linked_chunk.updates().unwrap().take(), &[RemoveChunk(ChunkIdentifier(4))]);
3350
3351 let maybe_next = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(1)).unwrap();
3353 let next = maybe_next.unwrap();
3354 assert_eq!(next.chunk_identifier(), ChunkIdentifier(0));
3355 assert_eq!(next.index(), 0);
3356 assert_items_eq!(linked_chunk, ['a', 'b'] ['l', 'm']);
3357 assert_eq!(linked_chunk.updates().unwrap().take(), &[RemoveChunk(ChunkIdentifier(1))]);
3358
3359 Ok(())
3360 }
3361
3362 #[test]
3363 fn test_remove_empty_last_chunk() {
3364 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3365
3366 let _ = linked_chunk.updates().unwrap().take();
3368
3369 assert_items_eq!(linked_chunk, []);
3370 assert!(linked_chunk.updates().unwrap().take().is_empty());
3371
3372 let err = linked_chunk.remove_empty_chunk_at(ChunkIdentifier(0)).unwrap_err();
3374 assert_matches!(err, Error::RemovingLastChunk);
3375 }
3376
3377 #[test]
3378 fn test_chunk_item_positions() {
3379 let mut linked_chunk = LinkedChunk::<3, char, ()>::new();
3380 linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e']);
3381 linked_chunk.push_gap_back(());
3382 linked_chunk.push_items_back(['f']);
3383
3384 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] ['d', 'e'] [-] ['f']);
3385
3386 let mut iterator = linked_chunk.chunks();
3387
3388 {
3390 let chunk = iterator.next().unwrap();
3391 assert_eq!(chunk.first_position(), Position(ChunkIdentifier(0), 0));
3392 assert_eq!(chunk.last_position(), Position(ChunkIdentifier(0), 2));
3393 }
3394
3395 {
3397 let chunk = iterator.next().unwrap();
3398 assert_eq!(chunk.first_position(), Position(ChunkIdentifier(1), 0));
3399 assert_eq!(chunk.last_position(), Position(ChunkIdentifier(1), 1));
3400 }
3401
3402 {
3404 let chunk = iterator.next().unwrap();
3405 assert_eq!(chunk.first_position(), Position(ChunkIdentifier(2), 0));
3406 assert_eq!(chunk.last_position(), Position(ChunkIdentifier(2), 0));
3407 }
3408
3409 {
3411 let chunk = iterator.next().unwrap();
3412 assert_eq!(chunk.first_position(), Position(ChunkIdentifier(3), 0));
3413 assert_eq!(chunk.last_position(), Position(ChunkIdentifier(3), 0));
3414 }
3415 }
3416
3417 #[test]
3418 fn test_is_first_and_last_chunk() {
3419 let mut linked_chunk = LinkedChunk::<3, char, ()>::new();
3420
3421 let mut chunks = linked_chunk.chunks().peekable();
3422 assert!(chunks.peek().unwrap().is_first_chunk());
3423 assert!(chunks.next().unwrap().is_last_chunk());
3424 assert!(chunks.next().is_none());
3425
3426 linked_chunk.push_items_back(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']);
3427
3428 let mut chunks = linked_chunk.chunks().peekable();
3429 assert!(chunks.next().unwrap().is_first_chunk());
3430 assert!(chunks.peek().unwrap().is_first_chunk().not());
3431 assert!(chunks.next().unwrap().is_last_chunk().not());
3432 assert!(chunks.next().unwrap().is_last_chunk());
3433 assert!(chunks.next().is_none());
3434 }
3435
3436 #[test]
3441 fn test_clear() {
3442 let mut linked_chunk = LinkedChunk::<3, Arc<char>, Arc<()>>::new();
3443
3444 let item = Arc::new('a');
3445 let gap = Arc::new(());
3446
3447 linked_chunk.push_items_back([
3448 item.clone(),
3449 item.clone(),
3450 item.clone(),
3451 item.clone(),
3452 item.clone(),
3453 ]);
3454 linked_chunk.push_gap_back(gap.clone());
3455 linked_chunk.push_items_back([item.clone()]);
3456
3457 assert_eq!(Arc::strong_count(&item), 7);
3458 assert_eq!(Arc::strong_count(&gap), 2);
3459 assert_eq!(linked_chunk.num_items(), 6);
3460 assert_eq!(linked_chunk.chunk_identifier_generator.next.load(Ordering::SeqCst), 3);
3461
3462 linked_chunk.clear();
3464
3465 assert_eq!(Arc::strong_count(&item), 1);
3466 assert_eq!(Arc::strong_count(&gap), 1);
3467 assert_eq!(linked_chunk.num_items(), 0);
3468 assert_eq!(linked_chunk.chunk_identifier_generator.next.load(Ordering::SeqCst), 0);
3469 }
3470
3471 #[test]
3472 fn test_clear_emit_an_update_clear() {
3473 use super::Update::*;
3474
3475 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3476
3477 assert_eq!(
3478 linked_chunk.updates().unwrap().take(),
3479 &[NewItemsChunk {
3480 previous: None,
3481 new: ChunkIdentifierGenerator::FIRST_IDENTIFIER,
3482 next: None
3483 }]
3484 );
3485
3486 linked_chunk.clear();
3487
3488 assert_eq!(
3489 linked_chunk.updates().unwrap().take(),
3490 &[
3491 Clear,
3492 NewItemsChunk {
3493 previous: None,
3494 new: ChunkIdentifierGenerator::FIRST_IDENTIFIER,
3495 next: None
3496 }
3497 ]
3498 );
3499 }
3500
3501 #[test]
3502 fn test_replace_item() {
3503 use super::Update::*;
3504
3505 let mut linked_chunk = LinkedChunk::<3, char, ()>::new_with_update_history();
3506
3507 linked_chunk.push_items_back(['a', 'b', 'c']);
3508 linked_chunk.push_gap_back(());
3509 assert_items_eq!(linked_chunk, ['a', 'b', 'c'] [-]);
3511
3512 let _ = linked_chunk.updates().unwrap().take();
3514
3515 linked_chunk.replace_item_at(Position(ChunkIdentifier(0), 1), 'B').unwrap();
3517 assert_items_eq!(linked_chunk, ['a', 'B', 'c'] [-]);
3518
3519 assert_eq!(
3520 linked_chunk.updates().unwrap().take(),
3521 &[ReplaceItem { at: Position(ChunkIdentifier(0), 1), item: 'B' }]
3522 );
3523
3524 assert_matches!(
3526 linked_chunk.replace_item_at(Position(ChunkIdentifier(0), 3), 'Z'),
3527 Err(Error::InvalidItemIndex { index: 3 })
3528 );
3529
3530 assert_matches!(
3532 linked_chunk.replace_item_at(Position(ChunkIdentifier(1), 0), 'Z'),
3533 Err(Error::ChunkIsAGap { .. })
3534 );
3535 }
3536
3537 #[test]
3538 fn test_lazy_previous() {
3539 use std::marker::PhantomData;
3540
3541 use super::{Ends, ObservableUpdates, Update::*};
3542
3543 let first_chunk_identifier = ChunkIdentifier(0);
3545 let mut first_loaded_chunk = Chunk::new_items_leaked(ChunkIdentifier(1));
3546 unsafe { first_loaded_chunk.as_mut() }.lazy_previous = Some(first_chunk_identifier);
3547
3548 let mut linked_chunk = LinkedChunk::<3, char, ()> {
3549 links: Ends { first: first_loaded_chunk, last: None },
3550 chunk_identifier_generator:
3551 ChunkIdentifierGenerator::new_from_previous_chunk_identifier(ChunkIdentifier(1)),
3552 updates: Some(ObservableUpdates::new()),
3553 marker: PhantomData,
3554 };
3555
3556 {
3559 linked_chunk.push_items_back(['a', 'b', 'c', 'd']);
3560
3561 assert_items_eq!(linked_chunk, ['a', 'b', 'c']['d']);
3562
3563 {
3565 let mut chunks = linked_chunk.chunks();
3566
3567 assert_matches!(chunks.next(), Some(chunk) => {
3568 assert_eq!(chunk.identifier(), 1);
3569 assert_eq!(chunk.lazy_previous, Some(ChunkIdentifier(0)));
3570 });
3571 assert_matches!(chunks.next(), Some(chunk) => {
3572 assert_eq!(chunk.identifier(), 2);
3573 assert!(chunk.lazy_previous.is_none());
3574 });
3575 assert!(chunks.next().is_none());
3576 }
3577
3578 assert_eq!(
3580 linked_chunk.updates().unwrap().take(),
3581 &[
3582 PushItems { at: Position(ChunkIdentifier(1), 0), items: vec!['a', 'b', 'c'] },
3583 NewItemsChunk {
3584 previous: Some(ChunkIdentifier(1)),
3585 new: ChunkIdentifier(2),
3586 next: None,
3587 },
3588 PushItems { at: Position(ChunkIdentifier(2), 0), items: vec!['d'] }
3589 ]
3590 );
3591 }
3592
3593 {
3595 linked_chunk.insert_gap_at((), Position(ChunkIdentifier(1), 0)).unwrap();
3596
3597 assert_items_eq!(linked_chunk, [-] ['a', 'b', 'c'] ['d']);
3598
3599 {
3601 let mut chunks = linked_chunk.chunks();
3602
3603 assert_matches!(chunks.next(), Some(chunk) => {
3604 assert_eq!(chunk.identifier(), 3);
3605 assert_eq!(chunk.lazy_previous, Some(ChunkIdentifier(0)));
3607 });
3608 assert_matches!(chunks.next(), Some(chunk) => {
3609 assert_eq!(chunk.identifier(), 1);
3610 assert!(chunk.lazy_previous.is_none());
3612 });
3613 assert_matches!(chunks.next(), Some(chunk) => {
3614 assert_eq!(chunk.identifier(), 2);
3615 assert!(chunk.lazy_previous.is_none());
3616 });
3617 assert!(chunks.next().is_none());
3618 }
3619
3620 assert_eq!(
3622 linked_chunk.updates().unwrap().take(),
3623 &[NewGapChunk {
3624 previous: Some(ChunkIdentifier(0)),
3626 new: ChunkIdentifier(3),
3627 next: Some(ChunkIdentifier(1)),
3628 gap: ()
3629 }]
3630 );
3631 }
3632
3633 {
3635 linked_chunk.replace_gap_at(['w', 'x', 'y', 'z'], ChunkIdentifier(3)).unwrap();
3636
3637 assert_items_eq!(linked_chunk, ['w', 'x', 'y'] ['z'] ['a', 'b', 'c'] ['d']);
3638
3639 {
3641 let mut chunks = linked_chunk.chunks();
3642
3643 assert_matches!(chunks.next(), Some(chunk) => {
3644 assert_eq!(chunk.identifier(), 4);
3645 assert_eq!(chunk.lazy_previous, Some(ChunkIdentifier(0)));
3647 });
3648 assert_matches!(chunks.next(), Some(chunk) => {
3649 assert_eq!(chunk.identifier(), 5);
3650 assert!(chunk.lazy_previous.is_none());
3651 });
3652 assert_matches!(chunks.next(), Some(chunk) => {
3653 assert_eq!(chunk.identifier(), 1);
3654 assert!(chunk.lazy_previous.is_none());
3655 });
3656 assert_matches!(chunks.next(), Some(chunk) => {
3657 assert_eq!(chunk.identifier(), 2);
3658 assert!(chunk.lazy_previous.is_none());
3659 });
3660 assert!(chunks.next().is_none());
3661 }
3662
3663 assert_eq!(
3665 linked_chunk.updates().unwrap().take(),
3666 &[
3667 NewItemsChunk {
3669 previous: Some(ChunkIdentifier(3)),
3670 new: ChunkIdentifier(4),
3671 next: Some(ChunkIdentifier(1)),
3672 },
3673 PushItems { at: Position(ChunkIdentifier(4), 0), items: vec!['w', 'x', 'y'] },
3675 NewItemsChunk {
3677 previous: Some(ChunkIdentifier(4)),
3678 new: ChunkIdentifier(5),
3679 next: Some(ChunkIdentifier(1)),
3680 },
3681 PushItems { at: Position(ChunkIdentifier(5), 0), items: vec!['z'] },
3683 RemoveChunk(ChunkIdentifier(3)),
3685 ]
3686 );
3687 }
3688
3689 {
3693 linked_chunk.insert_gap_at((), Position(ChunkIdentifier(4), 0)).unwrap();
3694
3695 assert_items_eq!(linked_chunk, [-] ['w', 'x', 'y'] ['z'] ['a', 'b', 'c'] ['d']);
3696
3697 {
3699 let mut chunks = linked_chunk.chunks();
3700
3701 assert_matches!(chunks.next(), Some(chunk) => {
3702 assert_eq!(chunk.identifier(), 6);
3703 assert_eq!(chunk.lazy_previous, Some(ChunkIdentifier(0)));
3705 });
3706 assert_matches!(chunks.next(), Some(chunk) => {
3707 assert_eq!(chunk.identifier(), 4);
3708 assert!(chunk.lazy_previous.is_none());
3710 });
3711 assert_matches!(chunks.next(), Some(chunk) => {
3712 assert_eq!(chunk.identifier(), 5);
3713 assert!(chunk.lazy_previous.is_none());
3714 });
3715 assert_matches!(chunks.next(), Some(chunk) => {
3716 assert_eq!(chunk.identifier(), 1);
3717 assert!(chunk.lazy_previous.is_none());
3718 });
3719 assert_matches!(chunks.next(), Some(chunk) => {
3720 assert_eq!(chunk.identifier(), 2);
3721 assert!(chunk.lazy_previous.is_none());
3722 });
3723 assert!(chunks.next().is_none());
3724 }
3725
3726 assert_eq!(
3728 linked_chunk.updates().unwrap().take(),
3729 &[NewGapChunk {
3730 previous: Some(ChunkIdentifier(0)),
3732 new: ChunkIdentifier(6),
3733 next: Some(ChunkIdentifier(4)),
3734 gap: ()
3735 }]
3736 );
3737 }
3738 }
3739}