diff options
| -rw-r--r-- | src/postings/intersection.rs | 100 | ||||
| -rw-r--r-- | src/postings/mod.rs | 30 |
2 files changed, 72 insertions, 58 deletions
diff --git a/src/postings/intersection.rs b/src/postings/intersection.rs index 3f30a54..28decb0 100644 --- a/src/postings/intersection.rs +++ b/src/postings/intersection.rs @@ -16,7 +16,7 @@ impl<TDocSet: DocSet> From<Vec<TDocSet>> for IntersectionDocSet<TDocSet> { IntersectionDocSet { docsets: docsets, finished: false, - doc: DocId::max_value(), + doc: 0u32, } } } @@ -45,41 +45,37 @@ impl<TDocSet: DocSet> DocSet for IntersectionDocSet<TDocSet> { if self.finished { return false; } - let (head_arr, tail) = self.docsets.split_at_mut(1); - let head: &mut TDocSet = &mut head_arr[0]; - if !head.advance() { - self.finished = true; - return false; - } - let mut doc_candidate = head.doc(); + + let mut candidate_doc = self.doc; + let mut candidate_ord = self.docsets.len(); 'outer: loop { - for docset in tail.iter_mut() { - match docset.skip_next(doc_candidate) { - SkipResult::Reached => {} - SkipResult::OverStep => { - doc_candidate = docset.doc(); - match head.skip_next(doc_candidate) { - SkipResult::Reached => {} - SkipResult::End => { - self.finished = true; - return false; - } - SkipResult::OverStep => { - doc_candidate = head.doc(); - continue 'outer; - } + for (ord, docset) in self.docsets.iter_mut().enumerate() { + if ord != candidate_ord { + // Candidate_ord is already at the + // right position. + // + // Calling `skip_next` would advance this docset + // and miss it. + match docset.skip_next(candidate_doc) { + SkipResult::Reached => {} + SkipResult::OverStep => { + // this is not in the intersection, + // let's update our candidate. + candidate_doc = docset.doc(); + candidate_ord = ord; + continue 'outer; + } + SkipResult::End => { + self.finished = true; + return false; } - } - SkipResult::End => { - self.finished = true; - return false; } } } - self.doc = doc_candidate; + self.doc = candidate_doc; return true; } } @@ -88,3 +84,51 @@ impl<TDocSet: DocSet> DocSet for IntersectionDocSet<TDocSet> { self.doc } } + + +#[cfg(test)] +mod tests { + + use postings::{DocSet, VecPostings, IntersectionDocSet}; + + #[test] + fn test_intersection() { + { + let left = VecPostings::from(vec![1, 3, 9]); + let right = VecPostings::from(vec![3, 4, 9, 18]); + let mut intersection = IntersectionDocSet::from(vec![left, right]); + assert!(intersection.advance()); + assert_eq!(intersection.doc(), 3); + assert!(intersection.advance()); + assert_eq!(intersection.doc(), 9); + assert!(!intersection.advance()); + } + { + let a = VecPostings::from(vec![1, 3, 9]); + let b = VecPostings::from(vec![3, 4, 9, 18]); + let c = VecPostings::from(vec![1, 5, 9, 111]); + let mut intersection = IntersectionDocSet::from(vec![a, b, c]); + assert!(intersection.advance()); + assert_eq!(intersection.doc(), 9); + assert!(!intersection.advance()); + } + } + + #[test] + fn test_intersection_zero() { + let left = VecPostings::from(vec![0]); + let right = VecPostings::from(vec![0]); + let mut intersection = IntersectionDocSet::from(vec![left, right]); + assert!(intersection.advance()); + assert_eq!(intersection.doc(), 0); + } + + #[test] + fn test_intersection_empty() { + let a = VecPostings::from(vec![1, 3]); + let b = VecPostings::from(vec![1, 4]); + let c = VecPostings::from(vec![3, 9]); + let mut intersection = IntersectionDocSet::from(vec![a, b, c]); + assert!(!intersection.advance()); + } +} diff --git a/src/postings/mod.rs b/src/postings/mod.rs index ca32219..fef99d8 100644 --- a/src/postings/mod.rs +++ b/src/postings/mod.rs @@ -373,36 +373,6 @@ mod tests { } } - #[test] - fn test_intersection() { - { - let left = VecPostings::from(vec![1, 3, 9]); - let right = VecPostings::from(vec![3, 4, 9, 18]); - let mut intersection = IntersectionDocSet::from(vec![left, right]); - assert!(intersection.advance()); - assert_eq!(intersection.doc(), 3); - assert!(intersection.advance()); - assert_eq!(intersection.doc(), 9); - assert!(!intersection.advance()); - } - { - let a = VecPostings::from(vec![1, 3, 9]); - let b = VecPostings::from(vec![3, 4, 9, 18]); - let c = VecPostings::from(vec![1, 5, 9, 111]); - let mut intersection = IntersectionDocSet::from(vec![a, b, c]); - assert!(intersection.advance()); - assert_eq!(intersection.doc(), 9); - assert!(!intersection.advance()); - } - { - let a = VecPostings::from(vec![1, 3]); - let b = VecPostings::from(vec![1, 4]); - let c = VecPostings::from(vec![3, 9]); - let mut intersection = IntersectionDocSet::from(vec![a, b, c]); - assert!(!intersection.advance()); - } - } - lazy_static! { static ref TERM_A: Term = { |