1#[cfg(feature = "rayon")]
2use rayon::prelude::*;
3
4use std::collections::HashSet;
5
6use crate::{Error, Fuse, Link};
7use data::{Flow, LinkReference, LinksConstants, ToQuery};
8
9pub type ReadHandler<'a, T> = &'a mut dyn FnMut(Link<T>) -> Flow;
11
12pub type WriteHandler<'a, T> = &'a mut dyn FnMut(Link<T>, Link<T>) -> Flow;
14
15pub trait Links<T: LinkReference>: Send + Sync {
20 fn constants(&self) -> &LinksConstants<T>;
22
23 fn count_links(&self, query: &[T]) -> T;
25
26 fn create_links(&mut self, query: &[T], handler: WriteHandler<'_, T>)
28 -> Result<Flow, Error<T>>;
29
30 fn each_links(&self, query: &[T], handler: ReadHandler<'_, T>) -> Flow;
32
33 fn update_links(
35 &mut self,
36 query: &[T],
37 change: &[T],
38 handler: WriteHandler<'_, T>,
39 ) -> Result<Flow, Error<T>>;
40
41 fn delete_links(&mut self, query: &[T], handler: WriteHandler<'_, T>)
47 -> Result<Flow, Error<T>>;
48}
49
50pub trait Doublets<T: LinkReference>: Links<T> {
54 fn count_by(&self, query: impl ToQuery<T>) -> T
56 where
57 Self: Sized,
58 {
59 self.count_links(&query.to_query()[..])
60 }
61
62 fn count(&self) -> T
64 where
65 Self: Sized,
66 {
67 self.count_by([])
68 }
69
70 fn create_by_with<F>(
72 &mut self,
73 query: impl ToQuery<T>,
74 mut handler: F,
75 ) -> Result<Flow, Error<T>>
76 where
77 F: FnMut(Link<T>, Link<T>) -> Flow,
78 Self: Sized,
79 {
80 let query = query.to_query();
81 self.create_links(&query[..], &mut handler)
82 }
83
84 fn create_by(&mut self, query: impl ToQuery<T>) -> Result<T, Error<T>>
86 where
87 Self: Sized,
88 {
89 let mut index = T::from_byte(0);
90 self.create_by_with(query, |_before, link| {
91 index = link.index;
92 Flow::Continue
93 })
94 .map(|_| index)
95 }
96
97 fn create_with<F>(&mut self, handler: F) -> Result<Flow, Error<T>>
99 where
100 F: FnMut(Link<T>, Link<T>) -> Flow,
101 Self: Sized,
102 {
103 self.create_by_with([], handler)
104 }
105
106 fn create(&mut self) -> Result<T, Error<T>>
108 where
109 Self: Sized,
110 {
111 self.create_by([])
112 }
113
114 fn each_by<F>(&self, query: impl ToQuery<T>, mut handler: F) -> Flow
116 where
117 F: FnMut(Link<T>) -> Flow,
118 Self: Sized,
119 {
120 let query = query.to_query();
121 self.each_links(&query[..], &mut handler)
122 }
123
124 fn each<F>(&self, handler: F) -> Flow
126 where
127 F: FnMut(Link<T>) -> Flow,
128 Self: Sized,
129 {
130 self.each_by([], handler)
131 }
132
133 fn update_by_with<H>(
135 &mut self,
136 query: impl ToQuery<T>,
137 change: impl ToQuery<T>,
138 mut handler: H,
139 ) -> Result<Flow, Error<T>>
140 where
141 H: FnMut(Link<T>, Link<T>) -> Flow,
142 Self: Sized,
143 {
144 let query = query.to_query();
145 let change = change.to_query();
146 self.update_links(&query[..], &change[..], &mut handler)
147 }
148
149 fn update_by(&mut self, query: impl ToQuery<T>, change: impl ToQuery<T>) -> Result<T, Error<T>>
151 where
152 Self: Sized,
153 {
154 let mut result = T::from_byte(0);
155 self.update_by_with(query, change, |_, after| {
156 result = after.index;
157 Flow::Continue
158 })
159 .map(|_| result)
160 }
161
162 fn update_with<F>(
164 &mut self,
165 index: T,
166 source: T,
167 target: T,
168 handler: F,
169 ) -> Result<Flow, Error<T>>
170 where
171 F: FnMut(Link<T>, Link<T>) -> Flow,
172 Self: Sized,
173 {
174 self.update_by_with([index], [index, source, target], handler)
175 }
176
177 fn update(&mut self, index: T, source: T, target: T) -> Result<T, Error<T>>
179 where
180 Self: Sized,
181 {
182 self.update_by([index], [index, source, target])
183 }
184
185 fn delete_by_with<F>(
187 &mut self,
188 query: impl ToQuery<T>,
189 mut handler: F,
190 ) -> Result<Flow, Error<T>>
191 where
192 F: FnMut(Link<T>, Link<T>) -> Flow,
193 Self: Sized,
194 {
195 let query = query.to_query();
196 self.delete_links(&query[..], &mut handler)
197 }
198
199 fn delete_by(&mut self, query: impl ToQuery<T>) -> Result<T, Error<T>>
201 where
202 Self: Sized,
203 {
204 let mut result = T::from_byte(0);
205 self.delete_by_with(query, |before, _after| {
206 result = before.index;
207 Flow::Continue
208 })
209 .map(|_| result)
210 }
211
212 fn delete_with<F>(&mut self, index: T, handler: F) -> Result<Flow, Error<T>>
214 where
215 F: FnMut(Link<T>, Link<T>) -> Flow,
216 Self: Sized,
217 {
218 self.delete_by_with([index], handler)
219 }
220
221 fn delete(&mut self, index: T) -> Result<T, Error<T>>
223 where
224 Self: Sized,
225 {
226 self.delete_by([index])
227 }
228
229 fn try_get_link(&self, index: T) -> Result<Link<T>, Error<T>> {
231 self.get_link(index).ok_or(Error::NotExists(index))
232 }
233
234 fn get_link(&self, index: T) -> Option<Link<T>>;
236
237 fn delete_all(&mut self) -> Result<(), Error<T>>
240 where
241 Self: Sized,
242 {
243 let indices: Vec<_> = self.each_iter([]).map(|link| link.index).collect();
244 for index in indices.into_iter().rev() {
245 if self.exist(index) {
246 self.delete(index)?;
247 }
248 }
249 Ok(())
250 }
251
252 fn delete_query_with<F>(&mut self, query: impl ToQuery<T>, handler: F) -> Result<(), Error<T>>
255 where
256 F: FnMut(Link<T>, Link<T>) -> Flow,
257 Self: Sized,
258 {
259 let query = query.to_query();
260 let len = self.count_by(query.to_query()).as_();
261 let mut vec = Vec::with_capacity(len);
262 let mut seen = HashSet::with_capacity(len);
263
264 self.each_by(query, |link| {
265 if seen.insert(link.index) {
266 vec.push(link.index);
267 }
268 Flow::Continue
269 });
270
271 let mut handler = Fuse::new(handler);
272 for index in vec.into_iter().rev() {
273 self.delete_links(&[index], &mut |before, after| handler.call(before, after))?;
274 }
275 Ok(())
276 }
277
278 fn delete_usages_with<F>(&mut self, index: T, handler: F) -> Result<(), Error<T>>
281 where
282 F: FnMut(Link<T>, Link<T>) -> Flow,
283 Self: Sized,
284 {
285 let any = self.constants().any;
286 let mut to_delete = Vec::with_capacity(
287 self.count_by([any, index, any]).as_() + self.count_by([any, any, index]).as_(),
288 );
289 self.each_by([any, index, any], |link| {
290 if link.index != index {
291 to_delete.push(link.index);
292 }
293 Flow::Continue
294 });
295
296 self.each_by([any, any, index], |link| {
297 if link.index != index && link.source != index {
298 to_delete.push(link.index);
299 }
300 Flow::Continue
301 });
302
303 let mut handler = Fuse::new(handler);
304 for index in to_delete.into_iter().rev() {
305 self.delete_links(&[index], &mut |before, after| handler.call(before, after))?;
306 }
307 Ok(())
308 }
309
310 fn delete_usages(&mut self, index: T) -> Result<(), Error<T>>
312 where
313 Self: Sized,
314 {
315 self.delete_usages_with(index, |_, _| Flow::Continue)
316 }
317
318 fn create_point(&mut self) -> Result<T, Error<T>>
320 where
321 Self: Sized,
322 {
323 let new = self.create()?;
324 self.update(new, new, new)
325 }
326
327 fn create_link_with<F>(&mut self, source: T, target: T, handler: F) -> Result<Flow, Error<T>>
332 where
333 F: FnMut(Link<T>, Link<T>) -> Flow,
334 Self: Sized,
335 {
336 let mut new = T::from_byte(0);
337 let mut handler = Fuse::new(handler);
338 self.create_with(|before, after| {
339 new = after.index;
340 handler.call(before, after);
341 Flow::Continue
342 })?;
343
344 let flow = self.update_links(&[new], &[new, source, target], &mut |before, after| {
345 handler.call(before, after)
346 })?;
347 Ok(if handler.flow().is_break() {
348 Flow::Break
349 } else {
350 flow
351 })
352 }
353
354 fn create_link(&mut self, source: T, target: T) -> Result<T, Error<T>>
356 where
357 Self: Sized,
358 {
359 let mut result = T::from_byte(0);
360 self.create_link_with(source, target, |_, link| {
361 result = link.index;
362 Flow::Continue
363 })
364 .map(|_| result)
365 }
366
367 fn found(&self, query: impl ToQuery<T>) -> bool
369 where
370 Self: Sized,
371 {
372 self.count_by(query) != T::from_byte(0)
373 }
374
375 fn find(&self, query: impl ToQuery<T>) -> Option<Link<T>>
377 where
378 Self: Sized,
379 {
380 let mut result = None;
381 self.each_by(query, |link| {
382 result = Some(link);
383 Flow::Break
384 });
385 result
386 }
387
388 fn search(&self, source: T, target: T) -> Option<T>
390 where
391 Self: Sized,
392 {
393 self.find([self.constants().any, source, target])
394 .map(|link| link.index)
395 }
396
397 #[deprecated(note = "use `search` instead")]
398 fn search_or(&self, source: T, target: T, default: T) -> T
399 where
400 Self: Sized,
401 {
402 self.search(source, target).unwrap_or(default)
403 }
404
405 fn single(&self, query: impl ToQuery<T>) -> Option<Link<T>>
407 where
408 Self: Sized,
409 {
410 let mut result = None;
411 self.each_by(query, |link| {
412 if result.is_none() {
413 result = Some(link);
414 Flow::Continue
415 } else {
416 result = None;
417 Flow::Break
418 }
419 });
420 result
421 }
422
423 fn get_or_create(&mut self, source: T, target: T) -> Result<T, Error<T>>
425 where
426 Self: Sized,
427 {
428 if let Some(link) = self.search(source, target) {
429 Ok(link)
430 } else {
431 self.create_link(source, target)
432 }
433 }
434
435 fn count_usages(&self, index: T) -> Result<T, Error<T>>
437 where
438 Self: Sized,
439 {
440 let any = self.constants().any;
441
442 let link = self.try_get_link(index)?;
443
444 let usage_source = self.count_by([any, index, any]);
445 let usage_target = self.count_by([any, any, index]);
446 let usage_both = self.count_by([any, index, index]);
447 let mut usages = usage_source + (usage_target - usage_both);
449 if index == link.source || index == link.target {
450 usages = usages - T::from_byte(1);
451 }
452
453 Ok(usages)
454 }
455
456 fn usages(&self, index: T) -> Result<Vec<T>, Error<T>>
458 where
459 Self: Sized,
460 {
461 let any = self.constants().any;
462 let mut usages = Vec::with_capacity(self.count_usages(index)?.as_());
463
464 self.each_by([any, index, any], |link| {
465 if link.index != index {
466 usages.push(link.index);
467 }
468 Flow::Continue
469 });
470
471 self.each_by([any, any, index], |link| {
472 if link.index != index && link.source != index {
473 usages.push(link.index);
474 }
475 Flow::Continue
476 });
477 Ok(usages)
478 }
479
480 fn exist(&self, link: T) -> bool
482 where
483 Self: Sized,
484 {
485 let constants = self.constants();
486 if constants.is_external(link) {
487 true
488 } else {
489 constants.is_internal(link) && self.count_by([link]) != T::from_byte(0)
490 }
491 }
492
493 fn has_usages(&self, link: T) -> bool
495 where
496 Self: Sized,
497 {
498 self.count_usages(link)
499 .is_ok_and(|link| link != T::from_byte(0))
500 }
501
502 fn rebase_with<F>(&mut self, old: T, new: T, handler: F) -> Result<(), Error<T>>
507 where
508 F: FnMut(Link<T>, Link<T>) -> Flow,
509 Self: Sized,
510 {
511 let _ = self.try_get_link(old)?;
512
513 if old == new {
514 return Ok(());
515 }
516
517 let any = self.constants().any;
518
519 let mut handler = Fuse::new(handler);
520
521 let usages: Vec<_> = self
522 .each_iter([any, old, any])
523 .chain(
525 self.each_iter([any, any, old])
526 .filter(|usage| usage.source != old),
527 )
528 .filter(|usage| usage.index != old)
529 .collect();
530 for usage in usages {
531 let source = if usage.source == old {
532 new
533 } else {
534 usage.source
535 };
536 let target = if usage.target == old {
537 new
538 } else {
539 usage.target
540 };
541 self.update_links(
542 &[usage.index],
543 &[usage.index, source, target],
544 &mut |before, after| handler.call(before, after),
545 )?;
546 }
547 Ok(())
548 }
549
550 fn rebase(&mut self, old: T, new: T) -> Result<T, Error<T>>
552 where
553 Self: Sized,
554 {
555 self.rebase_with(old, new, |_, _| Flow::Continue)
556 .map(|()| new)
557 }
558
559 fn rebase_and_delete(&mut self, old: T, new: T) -> Result<T, Error<T>>
561 where
562 Self: Sized,
563 {
564 if old == new {
565 Ok(new)
566 } else {
567 self.rebase(old, new)?;
568 self.delete(old).map(|_| new)
569 }
570 }
571}
572
573impl<T: LinkReference, All: Doublets<T> + ?Sized> Links<T> for Box<All> {
574 fn constants(&self) -> &LinksConstants<T> {
575 (**self).constants()
576 }
577
578 fn count_links(&self, query: &[T]) -> T {
579 (**self).count_links(query)
580 }
581
582 fn create_links(
583 &mut self,
584 query: &[T],
585 handler: WriteHandler<'_, T>,
586 ) -> Result<Flow, Error<T>> {
587 (**self).create_links(query, handler)
588 }
589
590 fn each_links(&self, query: &[T], handler: ReadHandler<'_, T>) -> Flow {
591 (**self).each_links(query, handler)
592 }
593
594 fn update_links(
595 &mut self,
596 query: &[T],
597 change: &[T],
598 handler: WriteHandler<'_, T>,
599 ) -> Result<Flow, Error<T>> {
600 (**self).update_links(query, change, handler)
601 }
602
603 fn delete_links(
604 &mut self,
605 query: &[T],
606 handler: WriteHandler<'_, T>,
607 ) -> Result<Flow, Error<T>> {
608 (**self).delete_links(query, handler)
609 }
610}
611
612impl<T: LinkReference, All: Doublets<T> + ?Sized> Doublets<T> for Box<All> {
613 fn get_link(&self, index: T) -> Option<Link<T>> {
614 (**self).get_link(index)
615 }
616}
617
618pub trait DoubletsExt<T: LinkReference>: Sized + Doublets<T> {
622 #[cfg(feature = "rayon")]
624 type IdxParIter: IndexedParallelIterator<Item = Link<T>>;
625
626 #[cfg(feature = "rayon")]
628 fn par_iter(&self) -> Self::IdxParIter;
629
630 #[cfg(feature = "rayon")]
632 fn par_each_iter(&self, query: impl ToQuery<T>) -> Self::IdxParIter;
633
634 fn iter(&self) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator;
636
637 fn each_iter(
639 &self,
640 query: impl ToQuery<T>,
641 ) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator;
642
643 #[cfg(feature = "small-search")]
645 fn iter_small(&self)
646 -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator;
647
648 #[cfg(feature = "small-search")]
650 fn each_iter_small(
651 &self,
652 query: impl ToQuery<T>,
653 ) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator;
654}
655
656impl<T: LinkReference, All: Doublets<T> + Sized> DoubletsExt<T> for All {
657 #[cfg(feature = "rayon")]
658 type IdxParIter = rayon::vec::IntoIter<Link<T>>;
659
660 #[cfg(feature = "rayon")]
661 fn par_iter(&self) -> Self::IdxParIter {
662 self.par_each_iter([self.constants().any; 3])
663 }
664
665 #[cfg(feature = "rayon")]
666 fn par_each_iter(&self, query: impl ToQuery<T>) -> Self::IdxParIter {
667 let mut vec = Vec::with_capacity(self.count_by(query.to_query()).as_());
668 self.each_by(query, |link| {
669 vec.push(link);
670 Flow::Continue
671 });
672 vec.into_par_iter()
673 }
674
675 #[inline]
676 fn iter(&self) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator {
677 self.each_iter([self.constants().any; 3])
678 }
679
680 #[cfg_attr(feature = "more-inline", inline)]
681 fn each_iter(
682 &self,
683 query: impl ToQuery<T>,
684 ) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator {
685 let cap = self.count_by(query.to_query()).as_();
686
687 let mut vec = Vec::with_capacity(cap);
688 self.each_by(query, &mut |link| {
689 vec.push(link);
690 Flow::Continue
691 });
692 vec.into_iter()
693 }
694
695 #[inline]
696 #[cfg(feature = "small-search")]
697 fn iter_small(
698 &self,
699 ) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator {
700 self.each_iter_small([self.constants().any; 3])
701 }
702
703 #[cfg(feature = "small-search")]
704 #[cfg_attr(feature = "more-inline", inline)]
705 fn each_iter_small(
706 &self,
707 query: impl ToQuery<T>,
708 ) -> impl Iterator<Item = Link<T>> + ExactSizeIterator + DoubleEndedIterator {
709 const SIZE_HINT: usize = 2;
710
711 let mut vec = smallvec::SmallVec::<[Link<_>; SIZE_HINT]>::with_capacity(
712 self.count_by(query.to_query()).as_(),
713 );
714 self.each_by(query, |link| {
715 vec.push(link);
716 Flow::Continue
717 });
718 vec.into_iter()
719 }
720}