use std::collections::HashMap;
use std::hash::Hash;
use std::iter::Peekable;
pub trait Layer: Send + Sync {
fn name(&self) -> [u32; 5];
fn names(&self) -> Vec<[u32; 5]>;
fn parent(&self) -> Option<&dyn Layer>;
fn node_and_value_count(&self) -> usize;
fn predicate_count(&self) -> usize;
fn predicate_dict_get(&self, id: usize) -> Option<String>;
fn predicate_dict_len(&self) -> usize;
fn predicate_dict_id(&self, predicate: &str) -> Option<u64>;
fn node_dict_id(&self, subject: &str) -> Option<u64>;
fn node_dict_get(&self, id: usize) -> Option<String>;
fn node_dict_len(&self) -> usize;
fn value_dict_id(&self, value: &str) -> Option<u64>;
fn value_dict_len(&self) -> usize;
fn value_dict_get(&self, id: usize) -> Option<String>;
fn subject_id(&self, subject: &str) -> Option<u64>;
fn predicate_id(&self, predicate: &str) -> Option<u64>;
fn object_node_id(&self, object: &str) -> Option<u64>;
fn object_value_id(&self, object: &str) -> Option<u64>;
fn id_subject(&self, id: u64) -> Option<String>;
fn id_predicate(&self, id: u64) -> Option<String>;
fn id_object(&self, id: u64) -> Option<ObjectType>;
fn subjects(&self) -> Box<dyn Iterator<Item = Box<dyn SubjectLookup>>> {
let mut layers = Vec::new();
layers.push((
self.subject_additions().peekable(),
self.subject_removals().peekable(),
));
let mut cur = self.parent();
while cur.is_some() {
layers.push((
cur.unwrap().subject_additions().peekable(),
cur.unwrap().subject_removals().peekable(),
));
cur = cur.unwrap().parent();
}
let it = GenericSubjectIterator { layers };
Box::new(it.map(|s| Box::new(s) as Box<dyn SubjectLookup>))
}
fn subject_additions(&self) -> Box<dyn Iterator<Item = Box<dyn LayerSubjectLookup>>>;
fn subject_additions_generic(&self) -> Box<dyn Iterator<Item = Box<dyn SubjectLookup>>> {
Box::new(
GenericSubjectIterator::from_layer_iterator(self.subject_additions())
.map(|lookup| Box::new(lookup) as Box<dyn SubjectLookup>),
)
}
fn subject_removals(&self) -> Box<dyn Iterator<Item = Box<dyn LayerSubjectLookup>>>;
fn subject_removals_generic(&self) -> Box<dyn Iterator<Item = Box<dyn SubjectLookup>>> {
Box::new(
GenericSubjectIterator::from_layer_iterator(self.subject_removals())
.map(|lookup| Box::new(lookup) as Box<dyn SubjectLookup>),
)
}
fn lookup_subject(&self, subject: u64) -> Option<Box<dyn SubjectLookup>> {
let mut lookups = Vec::new();
let addition = self.lookup_subject_addition(subject);
let removal = self.lookup_subject_removal(subject);
if addition.is_some() || removal.is_some() {
lookups.push((addition, removal));
}
let mut cur = self.parent();
while cur.is_some() {
let addition = cur.unwrap().lookup_subject_addition(subject);
let removal = cur.unwrap().lookup_subject_removal(subject);
if addition.is_some() || removal.is_some() {
lookups.push((addition, removal));
}
cur = cur.unwrap().parent();
}
if lookups.iter().any(|(pos, _neg)| pos.is_some()) {
Some(Box::new(GenericSubjectLookup {
subject: subject,
lookups: lookups,
}) as Box<dyn SubjectLookup>)
} else {
None
}
}
fn lookup_subject_addition(&self, subject: u64) -> Option<Box<dyn LayerSubjectLookup>>;
fn lookup_subject_addition_generic(&self, subject: u64) -> Option<Box<dyn SubjectLookup>> {
self.lookup_subject_addition(subject).map(|lookup| {
Box::new(GenericSubjectLookup::from_layer_lookup(lookup)) as Box<dyn SubjectLookup>
})
}
fn lookup_subject_removal(&self, subject: u64) -> Option<Box<dyn LayerSubjectLookup>>;
fn lookup_subject_removal_generic(&self, subject: u64) -> Option<Box<dyn SubjectLookup>> {
self.lookup_subject_removal(subject).map(|lookup| {
Box::new(GenericSubjectLookup::from_layer_lookup(lookup)) as Box<dyn SubjectLookup>
})
}
fn objects(&self) -> Box<dyn Iterator<Item = Box<dyn ObjectLookup>>> {
let mut layers = Vec::new();
layers.push((
self.object_additions().peekable(),
self.object_removals().peekable(),
));
let mut cur = self.parent();
while cur.is_some() {
layers.push((
cur.unwrap().object_additions().peekable(),
cur.unwrap().object_removals().peekable(),
));
cur = cur.unwrap().parent();
}
let it = GenericObjectIterator { layers };
Box::new(it.map(|s| Box::new(s) as Box<dyn ObjectLookup>))
}
fn object_additions(&self) -> Box<dyn Iterator<Item = Box<dyn LayerObjectLookup>>>;
fn object_additions_generic(&self) -> Box<dyn Iterator<Item = Box<dyn ObjectLookup>>> {
Box::new(
GenericObjectIterator::from_layer_iterator(self.object_additions())
.map(|lookup| Box::new(lookup) as Box<dyn ObjectLookup>),
)
}
fn object_removals(&self) -> Box<dyn Iterator<Item = Box<dyn LayerObjectLookup>>>;
fn object_removals_generic(&self) -> Box<dyn Iterator<Item = Box<dyn ObjectLookup>>> {
Box::new(
GenericObjectIterator::from_layer_iterator(self.object_removals())
.map(|lookup| Box::new(lookup) as Box<dyn ObjectLookup>),
)
}
fn lookup_object(&self, object: u64) -> Option<Box<dyn ObjectLookup>> {
let mut lookups = Vec::new();
let addition = self.lookup_object_addition(object);
let removal = self.lookup_object_removal(object);
if addition.is_some() || removal.is_some() {
lookups.push((addition, removal));
}
let mut cur = self.parent();
while cur.is_some() {
let addition = cur.unwrap().lookup_object_addition(object);
let removal = cur.unwrap().lookup_object_removal(object);
if addition.is_some() || removal.is_some() {
lookups.push((addition, removal));
}
cur = cur.unwrap().parent();
}
if lookups.iter().any(|(pos, _neg)| pos.is_some()) {
Some(Box::new(GenericObjectLookup { object, lookups }))
} else {
None
}
}
fn lookup_object_addition(&self, object: u64) -> Option<Box<dyn LayerObjectLookup>>;
fn lookup_object_addition_generic(&self, object: u64) -> Option<Box<dyn ObjectLookup>> {
self.lookup_object_addition(object).map(|lookup| {
Box::new(GenericObjectLookup::from_layer_lookup(lookup)) as Box<dyn ObjectLookup>
})
}
fn lookup_object_removal(&self, object: u64) -> Option<Box<dyn LayerObjectLookup>>;
fn lookup_object_removal_generic(&self, object: u64) -> Option<Box<dyn ObjectLookup>> {
self.lookup_object_removal(object).map(|lookup| {
Box::new(GenericObjectLookup::from_layer_lookup(lookup)) as Box<dyn ObjectLookup>
})
}
fn lookup_predicate(&self, predicate: u64) -> Option<Box<dyn PredicateLookup>> {
let mut lookups = Vec::new();
let addition = self.lookup_predicate_addition(predicate);
let removal = self.lookup_predicate_removal(predicate);
if addition.is_some() || removal.is_some() {
lookups.push((addition, removal));
}
let mut cur = self.parent();
while cur.is_some() {
let addition = cur.unwrap().lookup_predicate_addition(predicate);
let removal = cur.unwrap().lookup_predicate_removal(predicate);
if addition.is_some() || removal.is_some() {
lookups.push((addition, removal));
}
cur = cur.unwrap().parent();
}
if lookups.iter().any(|(pos, _neg)| pos.is_some()) {
Some(Box::new(GenericPredicateLookup {
predicate: predicate,
lookups: lookups,
}) as Box<dyn PredicateLookup>)
} else {
None
}
}
fn lookup_predicate_addition(&self, predicate: u64) -> Option<Box<dyn LayerPredicateLookup>>;
fn lookup_predicate_addition_generic(
&self,
predicate: u64,
) -> Option<Box<dyn PredicateLookup>> {
self.lookup_predicate_addition(predicate).map(|lookup| {
Box::new(GenericPredicateLookup::from_layer_lookup(lookup)) as Box<dyn PredicateLookup>
})
}
fn lookup_predicate_removal(&self, predicate: u64) -> Option<Box<dyn LayerPredicateLookup>>;
fn lookup_predicate_removal_generic(&self, predicate: u64) -> Option<Box<dyn PredicateLookup>> {
self.lookup_predicate_removal(predicate).map(|lookup| {
Box::new(GenericPredicateLookup::from_layer_lookup(lookup)) as Box<dyn PredicateLookup>
})
}
fn all_counts(&self) -> LayerCounts {
let mut node_count = self.node_dict_len();
let mut predicate_count = self.predicate_dict_len();
let mut value_count = self.value_dict_len();
let mut parent_option = self.parent();
while let Some(parent) = parent_option {
node_count += parent.node_dict_len();
predicate_count += parent.predicate_dict_len();
value_count += parent.value_dict_len();
parent_option = parent.parent();
}
LayerCounts {
node_count,
predicate_count,
value_count,
}
}
fn predicates(&self) -> Box<dyn Iterator<Item = Box<dyn PredicateLookup>>> {
let cloned = self.clone_boxed();
Box::new(
(1..=self.predicate_count())
.map(move |p| cloned.lookup_predicate(p as u64))
.flatten(),
)
}
fn predicate_additions(&self) -> Box<dyn Iterator<Item = Box<dyn LayerPredicateLookup>>> {
let cloned = self.clone_boxed();
Box::new(
(1..=self.predicate_count())
.map(move |p| cloned.lookup_predicate_addition(p as u64))
.flatten(),
)
}
fn predicate_additions_generic(&self) -> Box<dyn Iterator<Item = Box<dyn PredicateLookup>>> {
Box::new(self.predicate_additions().map(|lookup| {
Box::new(GenericPredicateLookup::from_layer_lookup(lookup)) as Box<dyn PredicateLookup>
}))
}
fn predicate_removals(&self) -> Box<dyn Iterator<Item = Box<dyn LayerPredicateLookup>>> {
let cloned = self.clone_boxed();
Box::new(
(1..=self.predicate_count())
.map(move |p| cloned.lookup_predicate_removal(p as u64))
.flatten(),
)
}
fn predicate_removals_generic(&self) -> Box<dyn Iterator<Item = Box<dyn PredicateLookup>>> {
Box::new(self.predicate_removals().map(|lookup| {
Box::new(GenericPredicateLookup::from_layer_lookup(lookup)) as Box<dyn PredicateLookup>
}))
}
fn clone_boxed(&self) -> Box<dyn Layer>;
fn triple_exists(&self, subject: u64, predicate: u64, object: u64) -> bool {
self.lookup_subject(subject)
.and_then(|pairs| pairs.lookup_predicate(predicate))
.and_then(|objects| objects.triple(object))
.is_some()
}
fn id_triple_exists(&self, triple: IdTriple) -> bool {
self.triple_exists(triple.subject, triple.predicate, triple.object)
}
fn string_triple_exists(&self, triple: &StringTriple) -> bool {
self.string_triple_to_id(triple)
.map(|t| self.id_triple_exists(t))
.unwrap_or(false)
}
fn triples(&self) -> Box<dyn Iterator<Item = IdTriple>> {
Box::new(
self.subjects()
.map(|s| s.predicates())
.flatten()
.map(|p| p.triples())
.flatten(),
)
}
fn string_triple_to_id(&self, triple: &StringTriple) -> Option<IdTriple> {
self.subject_id(&triple.subject).and_then(|subject| {
self.predicate_id(&triple.predicate).and_then(|predicate| {
match &triple.object {
ObjectType::Node(node) => self.object_node_id(&node),
ObjectType::Value(value) => self.object_value_id(&value),
}
.map(|object| IdTriple {
subject,
predicate,
object,
})
})
})
}
fn string_triple_to_partially_resolved(
&self,
triple: &StringTriple,
) -> PartiallyResolvedTriple {
PartiallyResolvedTriple {
subject: self
.subject_id(&triple.subject)
.map(|id| PossiblyResolved::Resolved(id))
.unwrap_or(PossiblyResolved::Unresolved(triple.subject.clone())),
predicate: self
.predicate_id(&triple.predicate)
.map(|id| PossiblyResolved::Resolved(id))
.unwrap_or(PossiblyResolved::Unresolved(triple.predicate.clone())),
object: match &triple.object {
ObjectType::Node(node) => self
.object_node_id(&node)
.map(|id| PossiblyResolved::Resolved(id))
.unwrap_or(PossiblyResolved::Unresolved(triple.object.clone())),
ObjectType::Value(value) => self
.object_value_id(&value)
.map(|id| PossiblyResolved::Resolved(id))
.unwrap_or(PossiblyResolved::Unresolved(triple.object.clone())),
},
}
}
fn id_triple_to_string(&self, triple: &IdTriple) -> Option<StringTriple> {
self.id_subject(triple.subject).and_then(|subject| {
self.id_predicate(triple.predicate).and_then(|predicate| {
self.id_object(triple.object).map(|object| StringTriple {
subject,
predicate,
object,
})
})
})
}
fn is_ancestor_of(&self, other: &dyn Layer) -> bool {
match other.parent() {
None => false,
Some(parent) => parent.name() == self.name() || self.is_ancestor_of(&*parent),
}
}
fn triple_addition_count(&self) -> usize {
let mut additions = self.triple_layer_addition_count();
let mut parent = self.parent();
while parent.is_some() {
additions += parent.unwrap().triple_layer_addition_count();
parent = parent.unwrap().parent();
}
additions
}
fn triple_removal_count(&self) -> usize {
let mut removals = self.triple_layer_removal_count();
let mut parent = self.parent();
while parent.is_some() {
removals += parent.unwrap().triple_layer_removal_count();
parent = parent.unwrap().parent();
}
removals
}
fn triple_count(&self) -> usize {
self.triple_addition_count() - self.triple_removal_count()
}
fn triple_layer_addition_count(&self) -> usize;
fn triple_layer_removal_count(&self) -> usize;
}
pub struct LayerCounts {
pub node_count: usize,
pub predicate_count: usize,
pub value_count: usize,
}
#[derive(Clone, Copy)]
pub enum LayerType {
Base,
Child,
}
struct GenericSubjectIterator {
layers: Vec<(
Peekable<Box<dyn Iterator<Item = Box<dyn LayerSubjectLookup>>>>,
Peekable<Box<dyn Iterator<Item = Box<dyn LayerSubjectLookup>>>>,
)>,
}
impl GenericSubjectIterator {
fn from_layer_iterator(iter: Box<dyn Iterator<Item = Box<dyn LayerSubjectLookup>>>) -> Self {
let empty =
Box::new(std::iter::empty()) as Box<dyn Iterator<Item = Box<dyn LayerSubjectLookup>>>;
Self {
layers: vec![(iter.peekable(), empty.peekable())],
}
}
}
impl Iterator for GenericSubjectIterator {
type Item = GenericSubjectLookup;
fn next(&mut self) -> Option<GenericSubjectLookup> {
let mut min = None;
for (pos, _neg) in self.layers.iter_mut() {
let pos_subject = pos.peek().map(|lookup| lookup.subject());
if pos_subject.is_some() && (min.is_none() || pos_subject < min) {
min = pos_subject;
}
}
if min.is_none() {
return None;
}
let min = min.unwrap();
let lookups = self
.layers
.iter_mut()
.map(|(pos, neg)| {
let pos_subject = match pos
.peek()
.map(|lookup| min == lookup.subject())
.unwrap_or(false)
{
true => pos.next(),
false => None,
};
let neg_subject = match neg
.peek()
.map(|lookup| min == lookup.subject())
.unwrap_or(false)
{
true => neg.next(),
false => None,
};
(pos_subject, neg_subject)
})
.filter(|(pos, neg)| pos.is_some() || neg.is_some())
.collect();
Some(GenericSubjectLookup {
subject: min,
lookups: lookups,
})
}
}
pub trait LayerSubjectLookup {
fn subject(&self) -> u64;
fn predicates(&self) -> Box<dyn Iterator<Item = Box<dyn LayerSubjectPredicateLookup>>>;
fn lookup_predicate(&self, predicate: u64) -> Option<Box<dyn LayerSubjectPredicateLookup>>;
fn triples(&self) -> Box<dyn Iterator<Item = IdTriple>> {
Box::new(self.predicates().map(|p| p.triples()).flatten())
}
}
pub fn layer_subject_lookup_into_generic(
lookup: Box<dyn LayerSubjectLookup>,
) -> Box<dyn SubjectLookup> {
Box::new(GenericSubjectLookup {
subject: lookup.subject(),
lookups: vec![(Some(lookup), None)],
})
}
pub trait LayerSubjectPredicateLookup {
fn subject(&self) -> u64;
fn predicate(&self) -> u64;
fn objects(&self) -> Box<dyn Iterator<Item = u64>>;
fn has_object(&self, object: u64) -> bool;
fn triples(&self) -> Box<dyn Iterator<Item = IdTriple>> {
let subject = self.subject();
let predicate = self.predicate();
Box::new(
self.objects()
.map(move |o| IdTriple::new(subject, predicate, o)),
)
}
fn triple(&self, object: u64) -> Option<IdTriple> {
if self.has_object(object) {
Some(IdTriple::new(self.subject(), self.predicate(), object))
} else {
None
}
}
}
pub trait SubjectLookup {
fn subject(&self) -> u64;
fn predicates(&self) -> Box<dyn Iterator<Item = Box<dyn SubjectPredicateLookup>>>;
fn lookup_predicate(&self, predicate: u64) -> Option<Box<dyn SubjectPredicateLookup>>;
fn triples(&self) -> Box<dyn Iterator<Item = IdTriple>> {
Box::new(self.predicates().map(|p| p.triples()).flatten())
}
}
pub struct GenericSubjectLookup {
subject: u64,
lookups: Vec<(
Option<Box<dyn LayerSubjectLookup>>,
Option<Box<dyn LayerSubjectLookup>>,
)>,
}
impl GenericSubjectLookup {
fn from_layer_lookup(lookup: Box<dyn LayerSubjectLookup>) -> GenericSubjectLookup {
GenericSubjectLookup {
subject: lookup.subject(),
lookups: vec![(Some(lookup), None)],
}
}
}
impl SubjectLookup for GenericSubjectLookup {
fn subject(&self) -> u64 {
self.subject
}
fn predicates(&self) -> Box<dyn Iterator<Item = Box<dyn SubjectPredicateLookup>>> {
let layers = self
.lookups
.iter()
.map(|(pos, neg)| {
(
pos.as_ref()
.map(|p| {
Box::new(p.predicates())
as Box<dyn Iterator<Item = Box<dyn LayerSubjectPredicateLookup>>>
})
.unwrap_or(Box::new(std::iter::empty()))
.peekable(),
neg.as_ref()
.map(|n| {
Box::new(n.predicates())
as Box<dyn Iterator<Item = Box<dyn LayerSubjectPredicateLookup>>>
})
.unwrap_or(Box::new(std::iter::empty()))
.peekable(),
)
})
.collect();
Box::new(
GenericSubjectPredicateIterator {
subject: self.subject,
layers: layers,
}
.map(|lookup| Box::new(lookup) as Box<dyn SubjectPredicateLookup>),
)
}
fn lookup_predicate(&self, predicate: u64) -> Option<Box<dyn SubjectPredicateLookup>> {
let lookups: Vec<_> = self
.lookups
.iter()
.map(|(pos, neg)| {
(
pos.as_ref().and_then(|p| p.lookup_predicate(predicate)),
neg.as_ref().and_then(|n| n.lookup_predicate(predicate)),
)
})
.filter(|(pos, neg)| pos.is_some() || neg.is_some())
.collect();
if lookups.iter().find(|(pos, _neg)| pos.is_some()).is_some() {
Some(Box::new(GenericSubjectPredicateLookup {
subject: self.subject,
predicate: predicate,
lookups: lookups,
}))
} else {
None
}
}
}
struct GenericSubjectPredicateIterator {
subject: u64,
layers: Vec<(
Peekable<Box<dyn Iterator<Item = Box<dyn LayerSubjectPredicateLookup>>>>,
Peekable<Box<dyn Iterator<Item = Box<dyn LayerSubjectPredicateLookup>>>>,
)>,
}
impl Iterator for GenericSubjectPredicateIterator {
type Item = GenericSubjectPredicateLookup;
fn next(&mut self) -> Option<GenericSubjectPredicateLookup> {
let mut min = None;
for (pos, _neg) in self.layers.iter_mut() {
let pos_predicate = pos.peek().map(|lookup| lookup.predicate());
if pos_predicate.is_some() && (min.is_none() || pos_predicate < min) {
min = pos_predicate;
}
}
if min.is_none() {
return None;
}
let min = min.unwrap();
let lookups = self
.layers
.iter_mut()
.map(|(pos, neg)| {
let pos_predicate = match pos
.peek()
.map(|lookup| min == lookup.predicate())
.unwrap_or(false)
{
true => pos.next(),
false => None,
};
let neg_predicate = match neg
.peek()
.map(|lookup| min == lookup.predicate())
.unwrap_or(false)
{
true => neg.next(),
false => None,
};
(pos_predicate, neg_predicate)
})
.filter(|(pos, neg)| pos.is_some() || neg.is_some())
.collect();
Some(GenericSubjectPredicateLookup {
subject: self.subject,
predicate: min,
lookups: lookups,
})
}
}
pub trait SubjectPredicateLookup {
fn subject(&self) -> u64;
fn predicate(&self) -> u64;
fn objects(&self) -> Box<dyn Iterator<Item = u64>>;
fn has_pos_object_in_lookup(&self, object: u64) -> bool;
fn has_neg_object_in_lookup(&self, object: u64) -> bool;
fn has_object(&self, object: u64) -> bool;
fn triples(&self) -> Box<dyn Iterator<Item = IdTriple>> {
let subject = self.subject();
let predicate = self.predicate();
Box::new(
self.objects()
.map(move |o| IdTriple::new(subject, predicate, o)),
)
}
fn triple(&self, object: u64) -> Option<IdTriple> {
if self.has_object(object) {
Some(IdTriple::new(self.subject(), self.predicate(), object))
} else {
None
}
}
}
struct GenericSubjectPredicateLookup {
subject: u64,
predicate: u64,
lookups: Vec<(
Option<Box<dyn LayerSubjectPredicateLookup>>,
Option<Box<dyn LayerSubjectPredicateLookup>>,
)>,
}
impl SubjectPredicateLookup for GenericSubjectPredicateLookup {
fn subject(&self) -> u64 {
self.subject
}
fn predicate(&self) -> u64 {
self.predicate
}
fn objects(&self) -> Box<dyn Iterator<Item = u64>> {
let layers = self
.lookups
.iter()
.map(|(pos, neg)| {
(
pos.as_ref()
.map(|p| Box::new(p.objects()) as Box<dyn Iterator<Item = u64>>)
.unwrap_or(Box::new(std::iter::empty()))
.peekable(),
neg.as_ref()
.map(|n| Box::new(n.objects()) as Box<dyn Iterator<Item = u64>>)
.unwrap_or(Box::new(std::iter::empty()))
.peekable(),
)
})
.collect();
Box::new(GenericSubjectPredicateObjectIterator { layers })
}
fn has_pos_object_in_lookup(&self, object: u64) -> bool {
self.lookups
.first()
.and_then(|last| last.0.as_ref())
.map(|pos| pos.has_object(object))
.unwrap_or(false)
}
fn has_neg_object_in_lookup(&self, object: u64) -> bool {
self.lookups
.first()
.and_then(|last| last.1.as_ref())
.map(|pos| pos.has_object(object))
.unwrap_or(false)
}
fn has_object(&self, object: u64) -> bool {
for (pos, neg) in self.lookups.iter() {
if pos.as_ref().map(|p| p.has_object(object)).unwrap_or(false) {
return true;
}
if neg.as_ref().map(|p| p.has_object(object)).unwrap_or(false) {
return false;
}
}
false
}
}
struct GenericSubjectPredicateObjectIterator {
layers: Vec<(
Peekable<Box<dyn Iterator<Item = u64>>>,
Peekable<Box<dyn Iterator<Item = u64>>>,
)>,
}
impl Iterator for GenericSubjectPredicateObjectIterator {
type Item = u64;
fn next(&mut self) -> Option<u64> {
let mut min;
loop {
min = None;
let mut deleted = false;
for (pos, neg) in self.layers.iter_mut().rev() {
let pos_object = pos.peek().map(|o| *o);
let neg_object = neg.peek().map(|o| *o);
if pos_object.is_some() && (min.is_none() || pos_object < min) {
deleted = false;
min = pos_object;
} else if deleted && pos_object.is_some() && pos_object == min {
deleted = false;
} else if neg_object == min {
deleted = true;
}
}
for (pos, neg) in self.layers.iter_mut() {
while pos.peek().is_some()
&& (min.is_none() || pos.peek().map(|o| *o).unwrap() <= min.unwrap())
{
pos.next().unwrap();
}
while neg.peek().is_some()
&& (min.is_none() || neg.peek().map(|o| *o).unwrap() <= min.unwrap())
{
neg.next().unwrap();
}
}
if min.is_none() || !deleted {
break;
}
}
min
}
}
pub trait LayerObjectLookup {
fn object(&self) -> u64;
fn subject_predicate_pairs(&self) -> Box<dyn Iterator<Item = (u64, u64)>>;
fn has_subject_predicate_pair(&self, subject: u64, predicate: u64) -> bool {
for (s, p) in self.subject_predicate_pairs() {
if s == subject && p == predicate {
return true;
}
if s > subject || (s == subject && p > predicate) {
return false;
}
}
false
}
fn triple(&self, subject: u64, predicate: u64) -> Option<IdTriple> {
if self.has_subject_predicate_pair(subject, predicate) {
Some(IdTriple::new(subject, predicate, self.object()))
} else {
None
}
}
fn triples(&self) -> Box<dyn Iterator<Item = IdTriple>> {
let object = self.object();
Box::new(
self.subject_predicate_pairs()
.map(move |(s, p)| IdTriple::new(s, p, object)),
)
}
}
pub trait ObjectLookup {
fn object(&self) -> u64;
fn subject_predicate_pairs(&self) -> Box<dyn Iterator<Item = (u64, u64)>>;
fn has_subject_predicate_pair(&self, subject: u64, predicate: u64) -> bool {
for (s, p) in self.subject_predicate_pairs() {
if s == subject && p == predicate {
return true;
}
if s > subject || (s == subject && p > predicate) {
return false;
}
}
false
}
fn triple(&self, subject: u64, predicate: u64) -> Option<IdTriple> {
if self.has_subject_predicate_pair(subject, predicate) {
Some(IdTriple::new(subject, predicate, self.object()))
} else {
None
}
}
fn triples(&self) -> Box<dyn Iterator<Item = IdTriple>> {
let object = self.object();
Box::new(
self.subject_predicate_pairs()
.map(move |(s, p)| IdTriple::new(s, p, object)),
)
}
}
struct GenericObjectIterator {
layers: Vec<(
Peekable<Box<dyn Iterator<Item = Box<dyn LayerObjectLookup>>>>,
Peekable<Box<dyn Iterator<Item = Box<dyn LayerObjectLookup>>>>,
)>,
}
impl GenericObjectIterator {
fn from_layer_iterator(iter: Box<dyn Iterator<Item = Box<dyn LayerObjectLookup>>>) -> Self {
let empty =
Box::new(std::iter::empty()) as Box<dyn Iterator<Item = Box<dyn LayerObjectLookup>>>;
GenericObjectIterator {
layers: vec![(iter.peekable(), empty.peekable())],
}
}
}
impl Iterator for GenericObjectIterator {
type Item = GenericObjectLookup;
fn next(&mut self) -> Option<GenericObjectLookup> {
let mut min = None;
for (pos, _neg) in self.layers.iter_mut() {
let pos_object = pos.peek().map(|lookup| lookup.object());
if pos_object.is_some() && (min.is_none() || pos_object < min) {
min = pos_object;
}
}
if min.is_none() {
return None;
}
let min = min.unwrap();
let lookups = self
.layers
.iter_mut()
.map(|(pos, neg)| {
let pos_object = match pos
.peek()
.map(|lookup| min == lookup.object())
.unwrap_or(false)
{
true => pos.next(),
false => None,
};
let neg_object = match neg
.peek()
.map(|lookup| min == lookup.object())
.unwrap_or(false)
{
true => neg.next(),
false => None,
};
(pos_object, neg_object)
})
.filter(|(pos, neg)| pos.is_some() || neg.is_some())
.collect();
Some(GenericObjectLookup {
object: min,
lookups: lookups,
})
}
}
struct GenericObjectLookup {
object: u64,
lookups: Vec<(
Option<Box<dyn LayerObjectLookup>>,
Option<Box<dyn LayerObjectLookup>>,
)>,
}
impl GenericObjectLookup {
fn from_layer_lookup(lookup: Box<dyn LayerObjectLookup>) -> Self {
Self {
object: lookup.object(),
lookups: vec![(Some(lookup), None)],
}
}
}
impl ObjectLookup for GenericObjectLookup {
fn object(&self) -> u64 {
self.object
}
fn subject_predicate_pairs(&self) -> Box<dyn Iterator<Item = (u64, u64)>> {
let layers: Vec<_> = self
.lookups
.iter()
.map(|(pos, neg)| {
(
pos.as_ref()
.map(|p| p.subject_predicate_pairs())
.unwrap_or(Box::new(std::iter::empty()))
.peekable(),
neg.as_ref()
.map(|p| p.subject_predicate_pairs())
.unwrap_or(Box::new(std::iter::empty()))
.peekable(),
)
})
.collect();
Box::new(ObjectSubjectPredicatePairIterator { layers })
}
}
struct ObjectSubjectPredicatePairIterator {
layers: Vec<(
Peekable<Box<dyn Iterator<Item = (u64, u64)>>>,
Peekable<Box<dyn Iterator<Item = (u64, u64)>>>,
)>,
}
impl Iterator for ObjectSubjectPredicatePairIterator {
type Item = (u64, u64);
fn next(&mut self) -> Option<(u64, u64)> {
let mut min;
loop {
min = None;
let mut deleted = false;
for (pos, neg) in self.layers.iter_mut().rev() {
let pos_sp = pos.peek().map(|s| *s);
let neg_sp = neg.peek().map(|s| *s);
if pos_sp.is_some() && (min.is_none() || pos_sp < min) {
deleted = false;
min = pos_sp;
} else if deleted && pos_sp.is_some() && pos_sp == min {
deleted = false;
} else if neg_sp == min {
deleted = true;
}
}
for (pos, neg) in self.layers.iter_mut() {
while pos.peek().is_some()
&& (min.is_none() || pos.peek().map(|s| *s).unwrap() <= min.unwrap())
{
pos.next().unwrap();
}
while neg.peek().is_some()
&& (min.is_none() || neg.peek().map(|s| *s).unwrap() <= min.unwrap())
{
neg.next().unwrap();
}
}
if min.is_none() || !deleted {
break;
}
}
min
}
}
pub trait LayerPredicateLookup {
fn predicate(&self) -> u64;
fn subject_predicate_pairs(
&self,
) -> Box<dyn Iterator<Item = Box<dyn LayerSubjectPredicateLookup>>>;
fn triples(&self) -> Box<dyn Iterator<Item = IdTriple>> {
Box::new(
self.subject_predicate_pairs()
.map(move |sp| sp.triples())
.flatten(),
)
}
}
pub trait PredicateLookup {
fn predicate(&self) -> u64;
fn subject_predicate_pairs(&self) -> Box<dyn Iterator<Item = Box<dyn SubjectPredicateLookup>>>;
fn triples(&self) -> Box<dyn Iterator<Item = IdTriple>> {
Box::new(
self.subject_predicate_pairs()
.map(move |sp| sp.triples())
.flatten(),
)
}
}
struct GenericPredicateLookup {
predicate: u64,
lookups: Vec<(
Option<Box<dyn LayerPredicateLookup>>,
Option<Box<dyn LayerPredicateLookup>>,
)>,
}
impl GenericPredicateLookup {
fn from_layer_lookup(lookup: Box<dyn LayerPredicateLookup>) -> Self {
Self {
predicate: lookup.predicate(),
lookups: vec![(Some(lookup), None)],
}
}
}
impl PredicateLookup for GenericPredicateLookup {
fn predicate(&self) -> u64 {
self.predicate
}
fn subject_predicate_pairs(&self) -> Box<dyn Iterator<Item = Box<dyn SubjectPredicateLookup>>> {
let layers: Vec<_> = self
.lookups
.iter()
.map(|(pos, neg)| {
(
pos.as_ref()
.map(|p| p.subject_predicate_pairs())
.unwrap_or(Box::new(std::iter::empty()))
.peekable(),
neg.as_ref()
.map(|n| n.subject_predicate_pairs())
.unwrap_or(Box::new(std::iter::empty()))
.peekable(),
)
})
.collect();
Box::new(
GenericSubjectPredicatePairIterator {
predicate: self.predicate,
layers: layers,
}
.map(|l| Box::new(l) as Box<dyn SubjectPredicateLookup>),
)
}
}
struct GenericSubjectPredicatePairIterator {
predicate: u64,
layers: Vec<(
Peekable<Box<dyn Iterator<Item = Box<dyn LayerSubjectPredicateLookup>>>>,
Peekable<Box<dyn Iterator<Item = Box<dyn LayerSubjectPredicateLookup>>>>,
)>,
}
impl Iterator for GenericSubjectPredicatePairIterator {
type Item = GenericSubjectPredicateLookup;
fn next(&mut self) -> Option<GenericSubjectPredicateLookup> {
let mut min = None;
for (pos, _neg) in self.layers.iter_mut() {
let subject = pos.peek().map(|l| l.subject());
if subject.is_some() && (min.is_none() || subject < min) {
min = subject;
}
}
if min.is_none() {
return None;
}
let mut lookups = Vec::with_capacity(self.layers.len());
for (pos, neg) in self.layers.iter_mut() {
let mut pos_lookup = None;
if pos.peek().map(|l| l.subject()) == min {
pos_lookup = pos.next();
}
let mut neg_lookup = None;
if neg.peek().map(|l| l.subject()) == min {
neg_lookup = neg.next();
}
if pos_lookup.is_some() || neg_lookup.is_some() {
lookups.push((pos_lookup, neg_lookup));
}
}
Some(GenericSubjectPredicateLookup {
subject: min.unwrap(),
predicate: self.predicate,
lookups: lookups,
})
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct IdTriple {
pub subject: u64,
pub predicate: u64,
pub object: u64,
}
impl IdTriple {
pub fn new(subject: u64, predicate: u64, object: u64) -> Self {
IdTriple {
subject,
predicate,
object,
}
}
pub fn to_resolved(&self) -> PartiallyResolvedTriple {
PartiallyResolvedTriple {
subject: PossiblyResolved::Resolved(self.subject),
predicate: PossiblyResolved::Resolved(self.predicate),
object: PossiblyResolved::Resolved(self.object),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct StringTriple {
pub subject: String,
pub predicate: String,
pub object: ObjectType,
}
impl StringTriple {
pub fn new_node(subject: &str, predicate: &str, object: &str) -> StringTriple {
StringTriple {
subject: subject.to_owned(),
predicate: predicate.to_owned(),
object: ObjectType::Node(object.to_owned()),
}
}
pub fn new_value(subject: &str, predicate: &str, object: &str) -> StringTriple {
StringTriple {
subject: subject.to_owned(),
predicate: predicate.to_owned(),
object: ObjectType::Value(object.to_owned()),
}
}
pub fn to_unresolved(&self) -> PartiallyResolvedTriple {
PartiallyResolvedTriple {
subject: PossiblyResolved::Unresolved(self.subject.clone()),
predicate: PossiblyResolved::Unresolved(self.predicate.clone()),
object: PossiblyResolved::Unresolved(self.object.clone()),
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum PossiblyResolved<T: Clone + PartialEq + Eq + PartialOrd + Ord + Hash> {
Unresolved(T),
Resolved(u64),
}
impl<T: Clone + PartialEq + Eq + PartialOrd + Ord + Hash> PossiblyResolved<T> {
pub fn is_resolved(&self) -> bool {
match self {
Self::Unresolved(_) => false,
Self::Resolved(_) => true,
}
}
pub fn as_ref(&self) -> PossiblyResolved<&T> {
match self {
Self::Unresolved(u) => PossiblyResolved::Unresolved(&u),
Self::Resolved(id) => PossiblyResolved::Resolved(*id),
}
}
pub fn unwrap_unresolved(self) -> T {
match self {
Self::Unresolved(u) => u,
Self::Resolved(_) => panic!("tried to unwrap unresolved, but got a resolved"),
}
}
pub fn unwrap_resolved(self) -> u64 {
match self {
Self::Unresolved(_) => panic!("tried to unwrap resolved, but got an unresolved"),
Self::Resolved(id) => id,
}
}
}
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct PartiallyResolvedTriple {
pub subject: PossiblyResolved<String>,
pub predicate: PossiblyResolved<String>,
pub object: PossiblyResolved<ObjectType>,
}
impl PartiallyResolvedTriple {
pub fn resolve_with(
&self,
node_map: &HashMap<String, u64>,
predicate_map: &HashMap<String, u64>,
value_map: &HashMap<String, u64>,
) -> Option<IdTriple> {
let subject = match self.subject.as_ref() {
PossiblyResolved::Unresolved(s) => *node_map.get(s)?,
PossiblyResolved::Resolved(id) => id,
};
let predicate = match self.predicate.as_ref() {
PossiblyResolved::Unresolved(p) => *predicate_map.get(p)?,
PossiblyResolved::Resolved(id) => id,
};
let object = match self.object.as_ref() {
PossiblyResolved::Unresolved(ObjectType::Node(n)) => *node_map.get(n)?,
PossiblyResolved::Unresolved(ObjectType::Value(v)) => *value_map.get(v)?,
PossiblyResolved::Resolved(id) => id,
};
Some(IdTriple {
subject,
predicate,
object,
})
}
}
#[derive(Debug, Clone, PartialOrd, PartialEq, Eq, Ord, Hash)]
pub enum ObjectType {
Node(String),
Value(String),
}
#[cfg(test)]
mod tests {
use super::*;
use crate::layer::base::tests::base_layer_files;
use crate::layer::base::BaseLayer;
use crate::layer::builder::{LayerBuilder, SimpleLayerBuilder};
use crate::layer::child::tests::child_layer_files;
use crate::layer::child::ChildLayer;
use futures::prelude::*;
use std::sync::Arc;
#[test]
fn find_triple_after_adjacent_removal() {
let files = base_layer_files();
let mut builder = SimpleLayerBuilder::new([1, 2, 3, 4, 5], files.clone());
builder.add_string_triple(&StringTriple::new_value("cow", "says", "moo"));
builder.add_string_triple(&StringTriple::new_value("cow", "says", "sniff"));
builder.commit().wait().unwrap();
let base = Arc::new(
BaseLayer::load_from_files([1, 2, 3, 4, 5], &files)
.wait()
.unwrap(),
) as Arc<dyn Layer>;
let files = child_layer_files();
let mut builder =
SimpleLayerBuilder::from_parent([5, 4, 3, 2, 1], base.clone(), files.clone());
builder.remove_string_triple(&StringTriple::new_value("cow", "says", "moo"));
builder.commit().wait().unwrap();
let child = Arc::new(
ChildLayer::load_from_files([5, 4, 3, 2, 1], base, &files)
.wait()
.unwrap(),
) as Arc<dyn Layer>;
let triples: Vec<_> = child
.triples()
.map(|t| child.id_triple_to_string(&t).unwrap())
.collect();
assert_eq!(
vec![StringTriple::new_value("cow", "says", "sniff")],
triples
);
}
#[test]
fn find_triple_after_removal_and_readdition() {
let files = base_layer_files();
let mut builder = SimpleLayerBuilder::new([1, 2, 3, 4, 5], files.clone());
builder.add_string_triple(&StringTriple::new_value("cow", "says", "moo"));
builder.commit().wait().unwrap();
let base = Arc::new(
BaseLayer::load_from_files([1, 2, 3, 4, 5], &files)
.wait()
.unwrap(),
) as Arc<dyn Layer>;
let files = child_layer_files();
let mut builder =
SimpleLayerBuilder::from_parent([5, 4, 3, 2, 1], base.clone(), files.clone());
builder.remove_string_triple(&StringTriple::new_value("cow", "says", "moo"));
builder.commit().wait().unwrap();
let child = Arc::new(
ChildLayer::load_from_files([5, 4, 3, 2, 1], base, &files)
.wait()
.unwrap(),
) as Arc<dyn Layer>;
let files = child_layer_files();
let mut builder =
SimpleLayerBuilder::from_parent([5, 4, 3, 2, 2], child.clone(), files.clone());
builder.add_string_triple(&StringTriple::new_value("cow", "says", "moo"));
builder.commit().wait().unwrap();
let child = Arc::new(
ChildLayer::load_from_files([5, 4, 3, 2, 2], child, &files)
.wait()
.unwrap(),
) as Arc<dyn Layer>;
let triples: Vec<_> = child
.triples()
.map(|t| child.id_triple_to_string(&t).unwrap())
.collect();
assert_eq!(vec![StringTriple::new_value("cow", "says", "moo")], triples);
}
#[test]
fn find_triple_by_object_after_adjacent_removal() {
let files = base_layer_files();
let mut builder = SimpleLayerBuilder::new([1, 2, 3, 4, 5], files.clone());
builder.add_string_triple(&StringTriple::new_value("cow", "hears", "moo"));
builder.add_string_triple(&StringTriple::new_value("cow", "says", "moo"));
builder.commit().wait().unwrap();
let base = Arc::new(
BaseLayer::load_from_files([1, 2, 3, 4, 5], &files)
.wait()
.unwrap(),
) as Arc<dyn Layer>;
let files = child_layer_files();
let mut builder =
SimpleLayerBuilder::from_parent([5, 4, 3, 2, 1], base.clone(), files.clone());
builder.remove_string_triple(&StringTriple::new_value("cow", "hears", "moo"));
builder.commit().wait().unwrap();
let child = Arc::new(
ChildLayer::load_from_files([5, 4, 3, 2, 1], base, &files)
.wait()
.unwrap(),
) as Arc<dyn Layer>;
let triples: Vec<_> = child
.objects()
.map(|o| o.triples())
.flatten()
.map(|t| child.id_triple_to_string(&t).unwrap())
.collect();
assert_eq!(vec![StringTriple::new_value("cow", "says", "moo")], triples);
}
#[test]
fn find_triple_by_object_after_removal_and_readdition() {
let files = base_layer_files();
let mut builder = SimpleLayerBuilder::new([1, 2, 3, 4, 5], files.clone());
builder.add_string_triple(&StringTriple::new_value("cow", "says", "moo"));
builder.commit().wait().unwrap();
let base = Arc::new(
BaseLayer::load_from_files([1, 2, 3, 4, 5], &files)
.wait()
.unwrap(),
) as Arc<dyn Layer>;
let files = child_layer_files();
let mut builder =
SimpleLayerBuilder::from_parent([5, 4, 3, 2, 1], base.clone(), files.clone());
builder.remove_string_triple(&StringTriple::new_value("cow", "says", "moo"));
builder.commit().wait().unwrap();
let child = Arc::new(
ChildLayer::load_from_files([5, 4, 3, 2, 1], base, &files)
.wait()
.unwrap(),
) as Arc<dyn Layer>;
let files = child_layer_files();
let mut builder =
SimpleLayerBuilder::from_parent([5, 4, 3, 2, 2], child.clone(), files.clone());
builder.add_string_triple(&StringTriple::new_value("cow", "says", "moo"));
builder.commit().wait().unwrap();
let child = Arc::new(
ChildLayer::load_from_files([5, 4, 3, 2, 2], child, &files)
.wait()
.unwrap(),
) as Arc<dyn Layer>;
let triples: Vec<_> = child
.objects()
.map(|o| o.triples())
.flatten()
.map(|t| child.id_triple_to_string(&t).unwrap())
.collect();
assert_eq!(vec![StringTriple::new_value("cow", "says", "moo")], triples);
}
}