grdf/impl/
btree_dataset.rs

1//! Dataset implementation based on `BTreeMap` and `BTreeSet`.
2use crate::utils::BTreeBijection;
3use crate::{Quad, Triple, View};
4use educe::Educe;
5use rdf_types::{AsRdfTerm, FromBlankId, IntoBlankId, MaybeBlankId};
6use std::borrow::Borrow;
7use std::collections::{BTreeMap, BTreeSet};
8use std::fmt;
9use std::hash::Hash;
10
11mod graph;
12
13pub use graph::*;
14
15#[derive(Educe, Clone)]
16#[educe(PartialEq(bound = "S: Ord, P: Ord, O: Ord, G: Ord"))]
17#[educe(Eq(bound = "S: Ord, P: Ord, O: Ord, G: Ord"))]
18#[educe(Ord(bound = "S: Ord, P: Ord, O: Ord, G: Ord"))]
19#[educe(Hash(bound = "S: Ord + Hash, P: Ord + Hash, O: Ord + Hash, G: Ord + Hash"))]
20#[educe(Default)]
21pub struct BTreeDataset<S = rdf_types::Term, P = S, O = S, G = S> {
22	default: BTreeGraph<S, P, O>,
23	named: BTreeMap<G, BTreeGraph<S, P, O>>,
24}
25
26impl<S: Ord, P: Ord, O: Ord, G: Ord> PartialOrd for BTreeDataset<S, P, O, G> {
27	fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
28		Some(self.cmp(other))
29	}
30}
31
32impl<S, P, O, G> BTreeDataset<S, P, O, G> {
33	pub fn new() -> Self {
34		Self::default()
35	}
36
37	/// Returns the number of quads in the dataset.
38	#[inline(always)]
39	pub fn is_empty(&self) -> bool {
40		self.default.is_empty() && self.named.iter().all(|(_, g)| g.is_empty())
41	}
42
43	/// Returns the number of quads in the dataset.
44	#[inline(always)]
45	pub fn len(&self) -> usize {
46		self.named
47			.iter()
48			.fold(self.default.len(), |x, (_, g)| g.len() + x)
49	}
50
51	pub fn graph<W>(&self, id: Option<&W>) -> Option<&BTreeGraph<S, P, O>>
52	where
53		G: Borrow<W> + Ord,
54		W: ?Sized + Ord,
55	{
56		match id {
57			Some(id) => self.named.get(id),
58			None => Some(&self.default),
59		}
60	}
61
62	#[allow(clippy::type_complexity)]
63	pub fn graph_entry<W>(&self, id: Option<&W>) -> Option<(Option<&G>, &BTreeGraph<S, P, O>)>
64	where
65		G: Borrow<W> + Ord,
66		W: ?Sized + Ord,
67	{
68		match id {
69			Some(id) => self.named.get_key_value(id).map(|(k, v)| (Some(k), v)),
70			None => Some((None, &self.default)),
71		}
72	}
73
74	pub fn graphs(&self) -> Graphs<'_, S, P, O, G> {
75		Graphs {
76			default: Some(&self.default),
77			it: self.named.iter(),
78		}
79	}
80
81	pub fn quads(&self) -> Quads<'_, S, P, O, G> {
82		Quads {
83			graphs: self.graphs(),
84			graph: None,
85			triples: None,
86		}
87	}
88
89	pub fn graph_mut<W: ?Sized + Ord>(&mut self, id: Option<&W>) -> Option<&mut BTreeGraph<S, P, O>>
90	where
91		G: Ord + Borrow<W>,
92	{
93		match id {
94			Some(id) => self.named.get_mut(id),
95			None => Some(&mut self.default),
96		}
97	}
98
99	pub fn graphs_mut(&mut self) -> GraphsMut<S, P, O, G> {
100		GraphsMut {
101			default: Some(&mut self.default),
102			it: self.named.iter_mut(),
103		}
104	}
105
106	pub fn insert_graph(&mut self, id: G, graph: BTreeGraph<S, P, O>) -> Option<BTreeGraph<S, P, O>>
107	where
108		G: Ord,
109	{
110		self.named.insert(id, graph)
111	}
112
113	pub fn into_graph(mut self, id: Option<&G>) -> Option<BTreeGraph<S, P, O>>
114	where
115		G: Ord,
116	{
117		match id {
118			Some(id) => self.named.remove(id),
119			None => Some(self.default),
120		}
121	}
122
123	pub fn into_graphs(self) -> IntoGraphs<S, P, O, G> {
124		IntoGraphs {
125			default: Some(self.default),
126			it: self.named.into_iter(),
127		}
128	}
129
130	pub fn into_quads(self) -> IntoQuads<S, P, O, G> {
131		IntoQuads {
132			graphs: self.into_graphs(),
133			graph: None,
134			triples: None,
135		}
136	}
137}
138
139impl<S: Ord, P: Ord, O: Ord, G: Ord> BTreeDataset<S, P, O, G> {
140	pub fn insert(&mut self, quad: Quad<S, P, O, G>) -> bool {
141		let (subject, predicate, object, graph_name) = quad.into_parts();
142		match self.graph_mut(graph_name.as_ref()) {
143			Some(g) => g.insert(Triple(subject, predicate, object)),
144			None => {
145				let mut g = BTreeGraph::new();
146				g.insert(Triple(subject, predicate, object));
147				self.insert_graph(graph_name.unwrap(), g);
148				true
149			}
150		}
151	}
152
153	pub fn remove<T: ?Sized + Ord, U: ?Sized + Ord, V: ?Sized + Ord, W: ?Sized + Ord>(
154		&mut self,
155		Quad(s, p, o, g): Quad<&T, &U, &V, &W>,
156	) where
157		S: Borrow<T>,
158		P: Borrow<U>,
159		O: Borrow<V>,
160		G: Borrow<W>,
161	{
162		if let Some(graph) = self.graph_mut(g) {
163			graph.remove(Triple(s, p, o))
164		}
165	}
166
167	pub fn remove_graph<W: ?Sized + Ord>(&mut self, g: &W) -> Option<BTreeGraph<S, P, O>>
168	where
169		G: Borrow<W>,
170	{
171		self.named.remove(g)
172	}
173
174	pub fn take<T: ?Sized + Ord, U: ?Sized + Ord, V: ?Sized + Ord, W: ?Sized + Ord>(
175		&mut self,
176		Quad(s, p, o, g): Quad<&T, &U, &V, &W>,
177	) -> Option<Quad<S, P, O, G>>
178	where
179		S: Clone + Borrow<T>,
180		P: Clone + Borrow<U>,
181		O: Borrow<V>,
182		G: Clone + Borrow<W>,
183	{
184		let graph = self.graph_mut(g)?;
185		let Triple(s, p, o) = graph.take(Triple(s, p, o))?;
186
187		let is_graph_empty = graph.is_empty();
188		let g = g.map(|g| {
189			if is_graph_empty {
190				self.named.remove_entry(g).unwrap().0
191			} else {
192				self.named.get_key_value(g).unwrap().0.clone()
193			}
194		});
195
196		Some(Quad(s, p, o, g))
197	}
198
199	pub fn take_match<T: ?Sized + Ord, U: ?Sized + Ord, V: ?Sized + Ord, W: ?Sized + Ord>(
200		&mut self,
201		Quad(s, p, o, g): Quad<Option<&T>, Option<&U>, Option<&V>, Option<&W>>,
202	) -> Option<Quad<S, P, O, G>>
203	where
204		S: Clone + Borrow<T>,
205		P: Clone + Borrow<U>,
206		O: Borrow<V>,
207		G: Clone + Borrow<W>,
208	{
209		match g {
210			Some(g) => {
211				let graph = self.graph_mut(g)?;
212				let Triple(s, p, o) = graph.take_match(Triple(s, p, o))?;
213
214				let is_graph_empty = graph.is_empty();
215				let g = g.map(|g| {
216					if is_graph_empty {
217						self.named.remove_entry(g).unwrap().0
218					} else {
219						self.named.get_key_value(g).unwrap().0.clone()
220					}
221				});
222
223				Some(Quad(s, p, o, g))
224			}
225			None => {
226				for (g, graph) in self.graphs_mut() {
227					if let Some(Triple(s, p, o)) = graph.take_match(Triple(s, p, o)) {
228						return Some(Quad(s, p, o, g.cloned()));
229					}
230				}
231
232				None
233			}
234		}
235	}
236
237	pub fn absorb<D: crate::SizedDataset<Subject = S, Predicate = P, Object = O, GraphLabel = G>>(
238		&mut self,
239		other: D,
240	) where
241		D::Graph: crate::SizedGraph,
242	{
243		for (id, graph) in other.into_graphs() {
244			match self.graph_mut(id.as_ref()) {
245				Some(g) => g.absorb(graph),
246				None => {
247					self.insert_graph(id.unwrap(), BTreeGraph::from_graph(graph));
248				}
249			}
250		}
251	}
252
253	/// Substitutes the blank node identifiers in the dataset.
254	pub fn substitute_blank_ids<B>(self, f: impl Fn(B) -> B) -> Self
255	where
256		S: Clone + MaybeBlankId<BlankId = B> + IntoBlankId + FromBlankId,
257		P: Clone + MaybeBlankId<BlankId = B> + IntoBlankId + FromBlankId,
258		O: MaybeBlankId<BlankId = B> + IntoBlankId + FromBlankId,
259		G: Clone + MaybeBlankId<BlankId = B> + IntoBlankId + FromBlankId,
260	{
261		let mut result = Self::new();
262
263		fn substitute_term<T: IntoBlankId + FromBlankId>(
264			term: T,
265			f: impl Fn(T::BlankId) -> T::BlankId,
266		) -> T {
267			match term.try_into_blank() {
268				Ok(b) => T::from_blank(f(b)),
269				Err(term) => term,
270			}
271		}
272
273		fn substitute_quad<B, S, P, O, G>(
274			Quad(s, p, o, g): Quad<S, P, O, G>,
275			f: impl Fn(B) -> B,
276		) -> Quad<S, P, O, G>
277		where
278			S: MaybeBlankId<BlankId = B> + IntoBlankId + FromBlankId,
279			P: MaybeBlankId<BlankId = B> + IntoBlankId + FromBlankId,
280			O: MaybeBlankId<BlankId = B> + IntoBlankId + FromBlankId,
281			G: MaybeBlankId<BlankId = B> + IntoBlankId + FromBlankId,
282		{
283			Quad(
284				substitute_term(s, &f),
285				substitute_term(p, &f),
286				substitute_term(o, &f),
287				g.map(|g| substitute_term(g, f)),
288			)
289		}
290
291		for quad in self.into_quads() {
292			result.insert(substitute_quad(quad, &f));
293		}
294
295		result
296	}
297
298	pub fn view<'a, A>(
299		&'a self,
300		graph_label: Option<&'a G>,
301		subject: &'a S,
302		access: A,
303	) -> View<'a, Self, A> {
304		crate::Dataset::view(self, graph_label, subject, access)
305	}
306}
307
308impl<S: Ord, P: Ord, O: Ord, G: Ord> BTreeDataset<S, P, O, G> {
309	/// Checks that there is an isomorphism between this dataset and `other`.
310	///
311	/// There is an isomorphism if there exists a blank node identifier bijection
312	/// between `self` and `other`.
313	/// This is equivalent to `self.find_blank_id_bijection(other).is_some()`.
314	pub fn is_isomorphic_to<I, B, L>(&self, other: &Self) -> bool
315	where
316		S: AsRdfTerm<I, B, L>,
317		P: AsRdfTerm<I, B, L>,
318		O: AsRdfTerm<I, B, L>,
319		G: AsRdfTerm<I, B, L>,
320		I: PartialEq,
321		L: PartialEq,
322		B: Ord,
323	{
324		self.find_blank_id_bijection(other).is_some()
325	}
326
327	/// Finds a blank node identifier bijection between from `self` to `other`.
328	/// If such bijection exists,
329	/// there is an isomorphism between `self` and `other`.
330	pub fn find_blank_id_bijection<'u, 'v, I: 'u + 'v, B, L: 'u + 'v>(
331		&'u self,
332		other: &'v Self,
333	) -> Option<BTreeBijection<'u, 'v, B, B>>
334	where
335		S: AsRdfTerm<I, B, L>,
336		P: AsRdfTerm<I, B, L>,
337		O: AsRdfTerm<I, B, L>,
338		G: AsRdfTerm<I, B, L>,
339		I: PartialEq,
340		L: PartialEq,
341		B: Ord,
342	{
343		use crate::utils::isomorphism::btree::FindBTreeBlankIdBijection;
344
345		fn has_no_blank<I, B, L, S, P, O, G>(Quad(s, p, o, g): &Quad<&S, &P, &O, &G>) -> bool
346		where
347			S: AsRdfTerm<I, B, L>,
348			P: AsRdfTerm<I, B, L>,
349			O: AsRdfTerm<I, B, L>,
350			G: AsRdfTerm<I, B, L>,
351		{
352			!s.as_rdf_term().is_blank()
353				&& !p.as_rdf_term().is_blank()
354				&& !o.as_rdf_term().is_blank()
355				&& !g.map(|g| g.as_rdf_term().is_blank()).unwrap_or(false)
356		}
357
358		let a_non_blank: BTreeSet<_> = self.quads().filter(has_no_blank).collect();
359		let b_non_blank: BTreeSet<_> = other.quads().filter(has_no_blank).collect();
360
361		if a_non_blank == b_non_blank {
362			Self::find_btree_blank_id_bijection(self, other)
363		} else {
364			None
365		}
366	}
367}
368
369impl<S: Ord, P: Ord, O: Ord, G: Ord> crate::Dataset for BTreeDataset<S, P, O, G> {
370	type Subject = S;
371	type Predicate = P;
372	type Object = O;
373	type GraphLabel = G;
374
375	type Graph = BTreeGraph<S, P, O>;
376	type Graphs<'a>
377	= Graphs<'a, S, P, O, G> where
378	Self: 'a,
379	S: 'a,
380	P: 'a,
381	O: 'a,
382	G: 'a,;
383	type Quads<'a>
384	= Quads<'a, S, P, O, G> where
385	Self: 'a,
386	S: 'a,
387	P: 'a,
388	O: 'a,;
389
390	type PatternMatching<'a, 'p> = PatternMatching<'a, 'p, S, P, O, G> where Self: 'a,
391	S: 'a + 'p,
392	P: 'a + 'p,
393	O: 'a + 'p,
394	G: 'a + 'p;
395
396	fn graph(&self, id: Option<&G>) -> Option<&BTreeGraph<S, P, O>> {
397		self.graph(id)
398	}
399
400	fn graphs(&self) -> Graphs<'_, S, P, O, G> {
401		self.graphs()
402	}
403
404	fn quads(&self) -> Quads<'_, S, P, O, G> {
405		self.quads()
406	}
407
408	fn pattern_matching<'p>(
409		&self,
410		Quad(s, p, o, g): Quad<
411			Option<&'p Self::Subject>,
412			Option<&'p Self::Predicate>,
413			Option<&'p Self::Object>,
414			Option<&'p Self::GraphLabel>,
415		>,
416	) -> Self::PatternMatching<'_, 'p> {
417		let pattern = Triple(s, p, o);
418
419		match g {
420			Some(g) => PatternMatching {
421				pattern,
422				graphs: None,
423				current_graph: self
424					.graph_entry(g)
425					.map(|(g, graph)| (g, GraphPatternMatching::new(graph, pattern))),
426			},
427			None => PatternMatching {
428				pattern,
429				graphs: Some(self.graphs()),
430				current_graph: None,
431			},
432		}
433	}
434}
435
436impl<S: Ord, P: Ord, O: Ord, G: Ord> BTreeDataset<S, P, O, G> {
437	crate::macros::reflect_dataset_impl!();
438}
439
440impl<S: fmt::Debug, P: fmt::Debug, O: fmt::Debug, G: fmt::Debug> fmt::Debug
441	for BTreeDataset<S, P, O, G>
442{
443	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
444		write!(f, "{{")?;
445
446		for (i, rdf_types::Quad(s, p, o, g)) in self.quads().enumerate() {
447			if i > 0 {
448				write!(f, ",")?;
449			}
450
451			match g {
452				Some(g) => write!(f, " {s:?} {p:?} {o:?} {g:?}")?,
453				None => write!(f, " {s:?} {p:?} {o:?}")?,
454			}
455		}
456
457		write!(f, "  }}")
458	}
459}
460
461#[allow(clippy::type_complexity)]
462pub struct PatternMatching<'a, 'p, S, P, O, G> {
463	pattern: Triple<Option<&'p S>, Option<&'p P>, Option<&'p O>>,
464	graphs: Option<Graphs<'a, S, P, O, G>>,
465	current_graph: Option<(Option<&'a G>, GraphPatternMatching<'a, 'p, S, P, O>)>,
466}
467
468impl<'a, 'p, S: Ord, P: Ord, O: Ord, G: Ord> Iterator for PatternMatching<'a, 'p, S, P, O, G> {
469	type Item = Quad<&'a S, &'a P, &'a O, &'a G>;
470
471	fn next(&mut self) -> Option<Self::Item> {
472		loop {
473			match &mut self.current_graph {
474				Some((g, m)) => match m.next() {
475					Some(Triple(s, p, o)) => break Some(Quad(s, p, o, *g)),
476					None => self.current_graph = None,
477				},
478				None => match &mut self.graphs {
479					Some(graphs) => match graphs.next() {
480						Some((g, graph)) => {
481							self.current_graph =
482								Some((g, GraphPatternMatching::new(graph, self.pattern)))
483						}
484						None => break None,
485					},
486					None => break None,
487				},
488			}
489		}
490	}
491}
492
493pub struct GraphPatternMatching<'a, 'p, S, P, O> {
494	predicate_pattern: Option<&'p P>,
495	object_pattern: Option<&'p O>,
496	subjects: Option<std::collections::btree_map::Iter<'a, S, BTreeMap<P, BTreeSet<O>>>>,
497	current_subject: Option<(&'a S, SubjectPatternMatching<'a, 'p, P, O>)>,
498}
499
500impl<'a, 'p, S: Ord, P: Ord, O: Ord> GraphPatternMatching<'a, 'p, S, P, O> {
501	fn new(
502		graph: &'a BTreeGraph<S, P, O>,
503		pattern: Triple<Option<&'p S>, Option<&'p P>, Option<&'p O>>,
504	) -> Self {
505		match pattern.into_subject() {
506			Some(s) => Self {
507				predicate_pattern: pattern.into_predicate(),
508				object_pattern: pattern.into_object(),
509				subjects: None,
510				current_subject: graph.table.get_key_value(s).map(|(s, subject)| {
511					(
512						s,
513						SubjectPatternMatching::new(
514							subject,
515							pattern.into_predicate(),
516							pattern.into_object(),
517						),
518					)
519				}),
520			},
521			None => Self {
522				predicate_pattern: pattern.into_predicate(),
523				object_pattern: pattern.into_object(),
524				subjects: Some(graph.table.iter()),
525				current_subject: None,
526			},
527		}
528	}
529}
530
531impl<'a, 'p, S: Ord, P: Ord, O: Ord> Iterator for GraphPatternMatching<'a, 'p, S, P, O> {
532	type Item = Triple<&'a S, &'a P, &'a O>;
533
534	fn next(&mut self) -> Option<Self::Item> {
535		loop {
536			match &mut self.current_subject {
537				Some((s, m)) => match m.next() {
538					Some((p, o)) => break Some(Triple(s, p, o)),
539					None => self.current_subject = None,
540				},
541				None => match &mut self.subjects {
542					Some(subjects) => match subjects.next() {
543						Some((s, subject)) => {
544							self.current_subject = Some((
545								s,
546								SubjectPatternMatching::new(
547									subject,
548									self.predicate_pattern,
549									self.object_pattern,
550								),
551							))
552						}
553						None => break None,
554					},
555					None => break None,
556				},
557			}
558		}
559	}
560}
561
562struct SubjectPatternMatching<'a, 'p, P, O> {
563	object_pattern: Option<&'p O>,
564	predicates: Option<std::collections::btree_map::Iter<'a, P, BTreeSet<O>>>,
565	current_predicate: Option<(&'a P, PredicatePatternMatching<'a, O>)>,
566}
567
568impl<'a, 'p, P: Ord, O: Ord> SubjectPatternMatching<'a, 'p, P, O> {
569	fn new(
570		subject: &'a BTreeMap<P, BTreeSet<O>>,
571		predicate_pattern: Option<&'p P>,
572		object_pattern: Option<&'p O>,
573	) -> Self {
574		match predicate_pattern {
575			Some(p) => Self {
576				object_pattern,
577				predicates: None,
578				current_predicate: subject
579					.get_key_value(p)
580					.map(|(p, pred)| (p, PredicatePatternMatching::new(pred, object_pattern))),
581			},
582			None => Self {
583				object_pattern,
584				predicates: Some(subject.iter()),
585				current_predicate: None,
586			},
587		}
588	}
589}
590
591impl<'a, 'p, P: Ord, O: Ord> Iterator for SubjectPatternMatching<'a, 'p, P, O> {
592	type Item = (&'a P, &'a O);
593
594	fn next(&mut self) -> Option<Self::Item> {
595		loop {
596			match &mut self.current_predicate {
597				Some((p, m)) => match m.next() {
598					Some(o) => break Some((p, o)),
599					None => self.current_predicate = None,
600				},
601				None => match &mut self.predicates {
602					Some(predicates) => match predicates.next() {
603						Some((p, pred)) => {
604							self.current_predicate =
605								Some((p, PredicatePatternMatching::new(pred, self.object_pattern)))
606						}
607						None => break None,
608					},
609					None => break None,
610				},
611			}
612		}
613	}
614}
615
616enum PredicatePatternMatching<'a, O> {
617	One(Option<&'a O>),
618	Any(std::collections::btree_set::Iter<'a, O>),
619}
620
621impl<'a, O: Ord> PredicatePatternMatching<'a, O> {
622	fn new(predicate: &'a BTreeSet<O>, object_pattern: Option<&O>) -> Self {
623		match object_pattern {
624			Some(o) => Self::One(predicate.get(o)),
625			None => Self::Any(predicate.iter()),
626		}
627	}
628}
629
630impl<'a, O: Ord> Iterator for PredicatePatternMatching<'a, O> {
631	type Item = &'a O;
632
633	fn next(&mut self) -> Option<Self::Item> {
634		match self {
635			Self::One(o) => o.take(),
636			Self::Any(iter) => iter.next(),
637		}
638	}
639}
640
641#[derive(Educe)]
642#[educe(Clone)]
643pub struct Graphs<'a, S, P, O, G> {
644	default: Option<&'a BTreeGraph<S, P, O>>,
645	it: std::collections::btree_map::Iter<'a, G, BTreeGraph<S, P, O>>,
646}
647
648impl<'a, S, P, O, G> Iterator for Graphs<'a, S, P, O, G> {
649	type Item = (Option<&'a G>, &'a BTreeGraph<S, P, O>);
650
651	fn next(&mut self) -> Option<Self::Item> {
652		if let Some(default) = self.default {
653			self.default = None;
654			Some((None, default))
655		} else {
656			self.it.next().map(|(id, graph)| (Some(id), graph))
657		}
658	}
659}
660
661pub struct GraphsMut<'a, S, P, O, G> {
662	default: Option<&'a mut BTreeGraph<S, P, O>>,
663	it: std::collections::btree_map::IterMut<'a, G, BTreeGraph<S, P, O>>,
664}
665
666impl<'a, S, P, O, G> Iterator for GraphsMut<'a, S, P, O, G> {
667	type Item = (Option<&'a G>, &'a mut BTreeGraph<S, P, O>);
668
669	fn next(&mut self) -> Option<Self::Item> {
670		let mut default = None;
671		std::mem::swap(&mut default, &mut self.default);
672		if let Some(default) = default {
673			self.default = None;
674			Some((None, default))
675		} else {
676			self.it.next().map(|(id, graph)| (Some(id), graph))
677		}
678	}
679}
680
681#[derive(Educe)]
682#[educe(Clone)]
683pub struct Quads<'a, S, P, O, G> {
684	graphs: Graphs<'a, S, P, O, G>,
685	graph: Option<&'a G>,
686	triples: Option<Iter<'a, S, P, O>>,
687}
688
689impl<'a, S, P, O, G> Iterator for Quads<'a, S, P, O, G> {
690	type Item = Quad<&'a S, &'a P, &'a O, &'a G>;
691
692	fn next(&mut self) -> Option<Quad<&'a S, &'a P, &'a O, &'a G>> {
693		loop {
694			match &mut self.triples {
695				Some(triples) => match triples.next() {
696					Some(triple) => return Some(Quad(triple.0, triple.1, triple.2, self.graph)),
697					None => {
698						self.triples = None;
699					}
700				},
701				None => match self.graphs.next() {
702					Some((id, graph)) => {
703						self.graph = id;
704						self.triples = Some(graph.triples())
705					}
706					None => return None,
707				},
708			}
709		}
710	}
711}
712
713impl<S: Clone + Ord, P: Clone + Ord, O: Ord, G: Clone + Ord> crate::SizedDataset
714	for BTreeDataset<S, P, O, G>
715{
716	type IntoGraphs = IntoGraphs<S, P, O, G>;
717	type IntoQuads = IntoQuads<S, P, O, G>;
718
719	fn into_graph(self, id: Option<&G>) -> Option<Self::Graph> {
720		self.into_graph(id)
721	}
722
723	fn into_graphs(self) -> Self::IntoGraphs {
724		self.into_graphs()
725	}
726
727	fn into_quads(self) -> Self::IntoQuads {
728		self.into_quads()
729	}
730}
731
732impl<S: Clone + Ord, P: Clone + Ord, O: Ord, G: Clone + Ord> BTreeDataset<S, P, O, G> {
733	crate::macros::reflect_sized_dataset_impl!();
734}
735
736pub struct IntoGraphs<S, P, O, G> {
737	default: Option<BTreeGraph<S, P, O>>,
738	it: std::collections::btree_map::IntoIter<G, BTreeGraph<S, P, O>>,
739}
740
741impl<S, P, O, G> Iterator for IntoGraphs<S, P, O, G> {
742	type Item = (Option<G>, BTreeGraph<S, P, O>);
743
744	fn next(&mut self) -> Option<Self::Item> {
745		let mut default = None;
746		std::mem::swap(&mut default, &mut self.default);
747		if let Some(default) = default {
748			self.default = None;
749			Some((None, default))
750		} else {
751			self.it.next().map(|(id, graph)| (Some(id), graph))
752		}
753	}
754}
755
756pub struct IntoQuads<S = rdf_types::Term, P = S, O = S, G = S> {
757	graphs: IntoGraphs<S, P, O, G>,
758	graph: Option<G>,
759	triples: Option<IntoIter<S, P, O>>,
760}
761
762impl<S: Clone, P: Clone, O, G: Clone> Iterator for IntoQuads<S, P, O, G> {
763	type Item = Quad<S, P, O, G>;
764
765	fn next(&mut self) -> Option<Quad<S, P, O, G>> {
766		loop {
767			match &mut self.triples {
768				Some(triples) => match triples.next() {
769					Some(triple) => {
770						return Some(Quad(triple.0, triple.1, triple.2, self.graph.clone()))
771					}
772					None => {
773						self.triples = None;
774					}
775				},
776				None => match self.graphs.next() {
777					Some((id, graph)) => {
778						self.graph = id;
779						self.triples = Some(graph.into_triples())
780					}
781					None => return None,
782				},
783			}
784		}
785	}
786}
787
788impl<S: Ord, P: Ord, O: Ord, G: Ord> crate::MutableDataset for BTreeDataset<S, P, O, G> {
789	type GraphsMut<'a>
790	= GraphsMut<'a, S, P, O, G> where
791	Self: 'a,
792	S: 'a,
793	P: 'a,
794	O: 'a,
795	G: 'a,;
796
797	fn graph_mut(&mut self, id: Option<&G>) -> Option<&mut Self::Graph> {
798		self.graph_mut(id)
799	}
800
801	fn graphs_mut(&mut self) -> Self::GraphsMut<'_> {
802		self.graphs_mut()
803	}
804
805	fn insert_graph(&mut self, id: G, graph: Self::Graph) -> Option<Self::Graph> {
806		self.named.insert(id, graph)
807	}
808
809	fn insert(&mut self, quad: Quad<S, P, O, G>) -> bool {
810		self.insert(quad)
811	}
812
813	fn remove(&mut self, quad: Quad<&S, &P, &O, &G>) {
814		self.remove(quad)
815	}
816
817	fn absorb<D: crate::SizedDataset<Subject = S, Predicate = P, Object = O, GraphLabel = G>>(
818		&mut self,
819		other: D,
820	) where
821		D::Graph: crate::SizedGraph,
822	{
823		self.absorb(other)
824	}
825}
826
827impl<S: Ord, P: Ord, O: Ord, G: Ord> BTreeDataset<S, P, O, G> {
828	crate::macros::reflect_mutable_dataset_impl!();
829}
830
831impl<
832		S: Clone + Borrow<T> + Ord,
833		P: Clone + Borrow<U> + Ord,
834		O: Borrow<V> + Ord,
835		G: Clone + Borrow<W> + Ord,
836		T: ?Sized + Ord,
837		U: ?Sized + Ord,
838		V: ?Sized + Ord,
839		W: ?Sized + Ord,
840	> crate::DatasetTake<T, U, V, W> for BTreeDataset<S, P, O, G>
841{
842	fn take(
843		&mut self,
844		quad: Quad<&T, &U, &V, &W>,
845	) -> Option<Quad<Self::Subject, Self::Predicate, Self::Object, Self::GraphLabel>> {
846		self.take(quad)
847	}
848
849	fn take_match(
850		&mut self,
851		quad: Quad<Option<&T>, Option<&U>, Option<&V>, Option<&W>>,
852	) -> Option<Quad<Self::Subject, Self::Predicate, Self::Object, Self::GraphLabel>> {
853		self.take_match(quad)
854	}
855}
856
857impl<'a, S, P, O, G> IntoIterator for &'a BTreeDataset<S, P, O, G> {
858	type Item = Quad<&'a S, &'a P, &'a O, &'a G>;
859	type IntoIter = Quads<'a, S, P, O, G>;
860
861	fn into_iter(self) -> Self::IntoIter {
862		self.quads()
863	}
864}
865
866impl<S: Clone, P: Clone, O, G: Clone> IntoIterator for BTreeDataset<S, P, O, G> {
867	type Item = Quad<S, P, O, G>;
868	type IntoIter = IntoQuads<S, P, O, G>;
869
870	fn into_iter(self) -> Self::IntoIter {
871		self.into_quads()
872	}
873}
874
875impl<S: Ord, P: Ord, O: Ord, G: Ord> std::iter::FromIterator<Quad<S, P, O, G>>
876	for BTreeDataset<S, P, O, G>
877{
878	fn from_iter<I: IntoIterator<Item = Quad<S, P, O, G>>>(iter: I) -> Self {
879		let mut ds = Self::new();
880		ds.extend(iter);
881		ds
882	}
883}
884
885impl<S: Ord, P: Ord, O: Ord, G: Ord> std::iter::Extend<Quad<S, P, O, G>>
886	for BTreeDataset<S, P, O, G>
887{
888	fn extend<I: IntoIterator<Item = Quad<S, P, O, G>>>(&mut self, iter: I) {
889		for quad in iter {
890			self.insert(quad);
891		}
892	}
893}
894
895#[cfg(feature = "serde")]
896impl<S, P, O, G> serde::Serialize for BTreeDataset<S, P, O, G>
897where
898	S: serde::Serialize,
899	P: serde::Serialize,
900	O: serde::Serialize,
901	G: serde::Serialize,
902{
903	fn serialize<E>(&self, serializer: E) -> Result<E::Ok, E::Error>
904	where
905		E: serde::Serializer,
906	{
907		use serde::ser::SerializeSeq;
908		let mut seq = serializer.serialize_seq(Some(self.len()))?;
909
910		for quad in self.quads() {
911			seq.serialize_element(&quad)?
912		}
913
914		seq.end()
915	}
916}
917
918#[cfg(feature = "serde")]
919impl<'de, S, P, O, G> serde::Deserialize<'de> for BTreeDataset<S, P, O, G>
920where
921	S: Ord + serde::Deserialize<'de>,
922	P: Ord + serde::Deserialize<'de>,
923	O: Ord + serde::Deserialize<'de>,
924	G: Ord + serde::Deserialize<'de>,
925{
926	fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
927	where
928		D: serde::Deserializer<'de>,
929	{
930		pub struct Visitor<S, P, O, G>(std::marker::PhantomData<(S, P, O, G)>);
931
932		impl<'de, S, P, O, G> serde::de::Visitor<'de> for Visitor<S, P, O, G>
933		where
934			S: Ord + serde::Deserialize<'de>,
935			P: Ord + serde::Deserialize<'de>,
936			O: Ord + serde::Deserialize<'de>,
937			G: Ord + serde::Deserialize<'de>,
938		{
939			type Value = BTreeDataset<S, P, O, G>;
940
941			fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
942				write!(formatter, "an RDF dataset")
943			}
944
945			fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
946			where
947				A: serde::de::SeqAccess<'de>,
948			{
949				let mut result = BTreeDataset::new();
950
951				while let Some(quad) = seq.next_element()? {
952					result.insert(quad);
953				}
954
955				Ok(result)
956			}
957		}
958
959		deserializer.deserialize_seq(Visitor(std::marker::PhantomData))
960	}
961}
grdf/impl/btree_dataset.rs

grdf/impl/
btree_dataset.rs
