uqa_core/
posting_list.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Payload-bearing posting storage and merge operations.
8//!
9//! `PostingList` is an ordered sequence of `(doc_id, payload)` pairs sorted
10//! ascending by `doc_id` with no duplicate `doc_id`. Its document support is
11//! projected explicitly as [`DocSet`], which is the carrier of the Boolean
12//! algebra.
13//!
14//! # Equality semantics
15//!
16//! Derived `PartialEq` on `PostingList` compares full entries (doc id +
17//! payload). [`PostingList::merge_union`] and
18//! [`PostingList::merge_intersection`] select union/intersection support while
19//! applying a payload merge policy: positions are unioned, scores are added,
20//! and fields use the right-hand value on collision. Consequently those
21//! operations are generally neither idempotent nor commutative under full
22//! `PostingList` equality.
23//!
24//! Projecting a posting list to [`DocSet`] loses payloads. Reconstructing a
25//! posting list from that support therefore creates default payloads and is
26//! not equal to the original decorated posting list in general.
27
28use std::collections::{BTreeMap, BTreeSet};
29
30use crate::types::{
31    DocId, GeneralizedPostingEntry, GraphPhiEnvelope, GraphPhiPayload, Payload, PostingEntry,
32    Value, GRAPH_PHI_EDGES_FIELD, GRAPH_PHI_FIELD, GRAPH_PHI_VERTICES_FIELD,
33};
34use crate::{DocSet, RankedView};
35
36/// Ordered sequence of `(doc_id, payload)` pairs.
37///
38/// Invariant: `entries` is sorted by `doc_id` ascending and contains no
39/// duplicate `doc_id`s.
40#[derive(Debug, Clone, Default, PartialEq)]
41pub struct PostingList {
42    entries: Vec<PostingEntry>,
43}
44
45// Pinned by `posting_list_intersect_consuming_inputs`: below this input size a small result allocation is cheaper than in-place compaction, while larger lists benefit from reusing the left buffer.
46const INTERSECT_REUSE_MIN_ENTRIES: usize = 4_096;
47
48impl PostingList {
49    /// Construct an empty posting list.
50    pub fn new() -> Self {
51        Self::default()
52    }
53
54    /// Construct from possibly unsorted, possibly duplicated entries.
55    ///
56    /// Sorts by `doc_id` ascending and keeps the first occurrence on
57    /// duplicate `doc_id`s.
58    pub fn from_unsorted(mut entries: Vec<PostingEntry>) -> Self {
59        entries.sort_by_key(|e| e.doc_id);
60        entries.dedup_by_key(|e| e.doc_id);
61        Self { entries }
62    }
63
64    /// Construct from entries that are already sorted by `doc_id` ascending
65    /// and contain no duplicate `doc_id`s.
66    ///
67    /// In debug builds this checks the invariant. In release builds it is
68    /// O(1) — the caller is responsible for upholding the invariant. Used
69    /// by internal merges that produce sorted output by construction.
70    pub fn from_sorted_unchecked(entries: Vec<PostingEntry>) -> Self {
71        debug_assert!(
72            entries.windows(2).all(|w| w[0].doc_id < w[1].doc_id),
73            "PostingList::from_sorted_unchecked invariant violated"
74        );
75        Self { entries }
76    }
77
78    /// Keep the union of both supports and merge payloads on a shared
79    /// `doc_id`.
80    ///
81    /// This is not Boolean join on full posting values: scores add and fields
82    /// from `other` take precedence on collision. Use [`Self::support`] when a
83    /// Boolean-algebra value is required.
84    pub fn merge_union(&self, other: &Self) -> Self {
85        let (a, b) = (&self.entries, &other.entries);
86        let mut out = Vec::with_capacity(a.len() + b.len());
87        let (mut i, mut j) = (0, 0);
88        while i < a.len() && j < b.len() {
89            match a[i].doc_id.cmp(&b[j].doc_id) {
90                std::cmp::Ordering::Equal => {
91                    out.push(PostingEntry {
92                        doc_id: a[i].doc_id,
93                        payload: merge_payloads(&a[i].payload, &b[j].payload),
94                    });
95                    i += 1;
96                    j += 1;
97                }
98                std::cmp::Ordering::Less => {
99                    out.push(a[i].clone());
100                    i += 1;
101                }
102                std::cmp::Ordering::Greater => {
103                    out.push(b[j].clone());
104                    j += 1;
105                }
106            }
107        }
108        out.extend_from_slice(&a[i..]);
109        out.extend_from_slice(&b[j..]);
110        Self::from_sorted_unchecked(out)
111    }
112
113    /// Keep the intersection of both supports and merge payloads on each
114    /// shared `doc_id`.
115    ///
116    /// This is not Boolean meet on full posting values. Its payload policy is
117    /// the same as [`Self::merge_union`].
118    pub fn merge_intersection(&self, other: &Self) -> Self {
119        let (a, b) = (&self.entries, &other.entries);
120        let mut out = Vec::with_capacity(a.len().min(b.len()));
121        let (mut i, mut j) = (0, 0);
122        while i < a.len() && j < b.len() {
123            match a[i].doc_id.cmp(&b[j].doc_id) {
124                std::cmp::Ordering::Equal => {
125                    out.push(PostingEntry {
126                        doc_id: a[i].doc_id,
127                        payload: merge_payloads(&a[i].payload, &b[j].payload),
128                    });
129                    i += 1;
130                    j += 1;
131                }
132                std::cmp::Ordering::Less => i += 1,
133                std::cmp::Ordering::Greater => j += 1,
134            }
135        }
136        Self::from_sorted_unchecked(out)
137    }
138
139    /// Consuming intersection merge that avoids a result allocation for large
140    /// inputs by reusing the left posting buffer. Small inputs retain the
141    /// lower-overhead allocating path. Payload semantics are identical to
142    /// [`PostingList::merge_intersection`], including right-hand field
143    /// precedence.
144    #[inline]
145    pub fn merge_intersection_owned(self, other: &Self) -> Self {
146        if self.entries.len().min(other.entries.len()) < INTERSECT_REUSE_MIN_ENTRIES {
147            return self.merge_intersection(other);
148        }
149        self.merge_intersection_reusing_left(other)
150    }
151
152    /// Intersect document support and reconstruct every retained entry with a
153    /// default payload. This is the physical meet for membership-only operator
154    /// subtrees; unlike [`Self::merge_intersection_owned`], it deliberately
155    /// does not observe or combine scores, positions, or fields.
156    pub fn merge_support_intersection_owned(mut self, other: &Self) -> Self {
157        let mut other_index = 0;
158        self.entries.retain_mut(|entry| {
159            while other_index < other.entries.len()
160                && other.entries[other_index].doc_id < entry.doc_id
161            {
162                other_index += 1;
163            }
164            if other_index >= other.entries.len()
165                || other.entries[other_index].doc_id != entry.doc_id
166            {
167                return false;
168            }
169            entry.payload = Payload::default();
170            other_index += 1;
171            true
172        });
173        self
174    }
175
176    #[inline(never)]
177    fn merge_intersection_reusing_left(mut self, other: &Self) -> Self {
178        let mut other_index = 0;
179        self.entries.retain_mut(|entry| {
180            while other_index < other.entries.len()
181                && other.entries[other_index].doc_id < entry.doc_id
182            {
183                other_index += 1;
184            }
185            if other_index >= other.entries.len()
186                || other.entries[other_index].doc_id != entry.doc_id
187            {
188                return false;
189            }
190            entry.payload = merge_payloads(&entry.payload, &other.entries[other_index].payload);
191            other_index += 1;
192            true
193        });
194        self
195    }
196
197    /// `A - B`: entries of `A` whose `doc_id` does not appear in `B`.
198    ///
199    /// A membership filter preserves left payloads and the sorted invariant;
200    /// the temporary `BTreeSet` provides deterministic `O(log |B|)` probes.
201    pub fn exclude(&self, other: &Self) -> Self {
202        let other_ids: BTreeSet<DocId> = other.entries.iter().map(|e| e.doc_id).collect();
203        let out: Vec<PostingEntry> = self
204            .entries
205            .iter()
206            .filter(|e| !other_ids.contains(&e.doc_id))
207            .cloned()
208            .collect();
209        Self::from_sorted_unchecked(out)
210    }
211
212    /// Build a score-ordered view without changing posting storage order.
213    pub fn ranked(&self) -> RankedView<'_> {
214        RankedView::new(self)
215    }
216
217    /// Apply a scoring function to every entry, returning a new posting list.
218    pub fn with_scores<F>(&self, score_fn: F) -> Self
219    where
220        F: Fn(&PostingEntry) -> f64,
221    {
222        let entries = self
223            .entries
224            .iter()
225            .map(|e| PostingEntry {
226                doc_id: e.doc_id,
227                payload: Payload {
228                    positions: e.payload.positions.clone(),
229                    score: score_fn(e),
230                    fields: e.payload.fields.clone(),
231                },
232            })
233            .collect();
234        Self::from_sorted_unchecked(entries)
235    }
236
237    /// Look up an entry by `doc_id`. O(log n) via binary search.
238    pub fn get_entry(&self, doc_id: DocId) -> Option<&PostingEntry> {
239        self.entries
240            .binary_search_by_key(&doc_id, |e| e.doc_id)
241            .ok()
242            .map(|i| &self.entries[i])
243    }
244
245    pub fn entries(&self) -> &[PostingEntry] {
246        &self.entries
247    }
248
249    pub fn doc_ids(&self) -> impl Iterator<Item = DocId> + '_ {
250        self.entries.iter().map(|e| e.doc_id)
251    }
252
253    /// Project this payload-bearing relation onto its document-id support.
254    pub fn support(&self) -> DocSet {
255        DocSet::from_sorted_unchecked(self.doc_ids().collect())
256    }
257
258    /// Create document-id-ordered posting storage with a default payload for
259    /// every id in `support`.
260    pub fn from_support(support: &DocSet) -> Self {
261        let entries = support
262            .iter()
263            .map(|doc_id| PostingEntry::new(doc_id, Payload::default()))
264            .collect();
265        Self::from_sorted_unchecked(entries)
266    }
267
268    pub fn len(&self) -> usize {
269        self.entries.len()
270    }
271
272    pub fn is_empty(&self) -> bool {
273        self.entries.is_empty()
274    }
275
276    pub fn iter(&self) -> std::slice::Iter<'_, PostingEntry> {
277        self.entries.iter()
278    }
279}
280
281impl IntoIterator for PostingList {
282    type Item = PostingEntry;
283    type IntoIter = std::vec::IntoIter<PostingEntry>;
284
285    fn into_iter(self) -> Self::IntoIter {
286        self.entries.into_iter()
287    }
288}
289
290impl<'a> IntoIterator for &'a PostingList {
291    type Item = &'a PostingEntry;
292    type IntoIter = std::slice::Iter<'a, PostingEntry>;
293
294    fn into_iter(self) -> Self::IntoIter {
295        self.entries.iter()
296    }
297}
298
299impl FromIterator<PostingEntry> for PostingList {
300    fn from_iter<I: IntoIterator<Item = PostingEntry>>(iter: I) -> Self {
301        Self::from_unsorted(iter.into_iter().collect())
302    }
303}
304
305impl From<&DocSet> for PostingList {
306    fn from(support: &DocSet) -> Self {
307        Self::from_support(support)
308    }
309}
310
311impl From<DocSet> for PostingList {
312    fn from(support: DocSet) -> Self {
313        Self::from_support(&support)
314    }
315}
316
317impl From<&PostingList> for DocSet {
318    fn from(posting_list: &PostingList) -> Self {
319        posting_list.support()
320    }
321}
322
323/// Merge two payloads when their parent entries collide on `doc_id`.
324///
325/// - positions: union, sorted ascending, deduped
326/// - score: added (so `merge_union(a, a)` generally differs from `a`)
327/// - fields: right-hand side wins on key collision
328fn merge_payloads(a: &Payload, b: &Payload) -> Payload {
329    let a_score_only = a.positions.is_empty() && a.fields.is_empty();
330    let b_score_only = b.positions.is_empty() && b.fields.is_empty();
331    if a_score_only && b_score_only {
332        return Payload::with_score(a.score + b.score);
333    }
334    if a_score_only {
335        let mut merged = b.clone();
336        merged.score = a.score + b.score;
337        return merged;
338    }
339    if b_score_only {
340        let mut merged = a.clone();
341        merged.score = a.score + b.score;
342        return merged;
343    }
344
345    let a_phi = GraphPhiEnvelope::decode(a.fields.get(GRAPH_PHI_FIELD));
346    let b_phi = GraphPhiEnvelope::decode(b.fields.get(GRAPH_PHI_FIELD));
347    if a_phi.is_some() || b_phi.is_some() {
348        return merge_phi_payloads(a, b, a_phi, b_phi);
349    }
350
351    let mut positions: Vec<u32> = Vec::with_capacity(a.positions.len() + b.positions.len());
352    positions.extend_from_slice(&a.positions);
353    positions.extend_from_slice(&b.positions);
354    positions.sort_unstable();
355    positions.dedup();
356
357    let mut fields: BTreeMap<String, Value> = a.fields.clone();
358    for (k, v) in &b.fields {
359        fields.insert(k.clone(), v.clone());
360    }
361
362    Payload {
363        positions,
364        score: a.score + b.score,
365        fields,
366    }
367}
368
369fn merge_phi_payloads(
370    a: &Payload,
371    b: &Payload,
372    a_phi: Option<GraphPhiEnvelope>,
373    b_phi: Option<GraphPhiEnvelope>,
374) -> Payload {
375    let (a_base_score, a_graph, a_override, a_fields) = decode_phi_payload(a, a_phi);
376    let (b_base_score, b_graph, b_override, b_fields) = decode_phi_payload(b, b_phi);
377
378    let mut positions: Vec<u32> = Vec::with_capacity(a.positions.len() + b.positions.len());
379    positions.extend_from_slice(&a.positions);
380    positions.extend_from_slice(&b.positions);
381    positions.sort_unstable();
382    positions.dedup();
383
384    let mut fields = a_fields;
385    fields.extend(b_fields);
386    let original_reserved = fields.remove(GRAPH_PHI_FIELD);
387    let original_vertices = fields.remove(GRAPH_PHI_VERTICES_FIELD);
388    let original_edges = fields.remove(GRAPH_PHI_EDGES_FIELD);
389
390    let graph_payload = b_graph.or(a_graph);
391    let merged_score = a.score + b.score;
392    let score_override =
393        if graph_payload.is_some() && (a_override.is_some() || b_override.is_some()) {
394            Some(merged_score)
395        } else {
396            None
397        };
398
399    if let Some(graph) = &graph_payload {
400        fields.insert(
401            GRAPH_PHI_VERTICES_FIELD.to_string(),
402            graph.encoded_vertices(),
403        );
404        fields.insert(GRAPH_PHI_EDGES_FIELD.to_string(), graph.encoded_edges());
405    } else {
406        restore_field(
407            &mut fields,
408            GRAPH_PHI_VERTICES_FIELD,
409            original_vertices.clone(),
410        );
411        restore_field(&mut fields, GRAPH_PHI_EDGES_FIELD, original_edges.clone());
412    }
413
414    fields.insert(
415        GRAPH_PHI_FIELD.to_string(),
416        GraphPhiEnvelope {
417            base_score: a_base_score + b_base_score,
418            graph_payload,
419            score_override,
420            original_reserved,
421            original_vertices,
422            original_edges,
423        }
424        .encode(),
425    );
426
427    Payload {
428        positions,
429        score: merged_score,
430        fields,
431    }
432}
433
434fn decode_phi_payload(
435    payload: &Payload,
436    envelope: Option<GraphPhiEnvelope>,
437) -> (
438    f64,
439    Option<GraphPhiPayload>,
440    Option<f64>,
441    BTreeMap<String, Value>,
442) {
443    let Some(envelope) = envelope else {
444        return (payload.score, None, None, payload.fields.clone());
445    };
446
447    let mut fields = payload.fields.clone();
448    fields.remove(GRAPH_PHI_FIELD);
449    fields.remove(GRAPH_PHI_VERTICES_FIELD);
450    fields.remove(GRAPH_PHI_EDGES_FIELD);
451    restore_field(&mut fields, GRAPH_PHI_FIELD, envelope.original_reserved);
452    restore_field(
453        &mut fields,
454        GRAPH_PHI_VERTICES_FIELD,
455        envelope.original_vertices,
456    );
457    restore_field(&mut fields, GRAPH_PHI_EDGES_FIELD, envelope.original_edges);
458    (
459        envelope.base_score,
460        envelope.graph_payload,
461        envelope.score_override,
462        fields,
463    )
464}
465
466fn restore_field(fields: &mut BTreeMap<String, Value>, key: &str, value: Option<Value>) {
467    if let Some(value) = value {
468        fields.insert(key.to_string(), value);
469    }
470}
471
472/// Payload-bearing, multi-document tuple storage for join results.
473///
474/// Invariant: `entries` sorted by the `doc_ids` tuple, no duplicates.
475#[derive(Debug, Clone, Default, PartialEq, Eq)]
476pub struct GeneralizedPostingList {
477    entries: Vec<GeneralizedPostingEntry>,
478}
479
480impl GeneralizedPostingList {
481    pub fn new() -> Self {
482        Self::default()
483    }
484
485    pub fn from_unsorted(mut entries: Vec<GeneralizedPostingEntry>) -> Self {
486        entries.sort();
487        entries.dedup_by(|a, b| a.doc_ids == b.doc_ids);
488        Self { entries }
489    }
490
491    pub fn from_sorted_unchecked(entries: Vec<GeneralizedPostingEntry>) -> Self {
492        debug_assert!(
493            entries.windows(2).all(|w| w[0].doc_ids < w[1].doc_ids),
494            "GeneralizedPostingList::from_sorted_unchecked invariant violated"
495        );
496        Self { entries }
497    }
498
499    /// Select the union of tuple support, preserving the left payload when a
500    /// tuple occurs on both sides.
501    pub fn merge_union(&self, other: &Self) -> Self {
502        let (a, b) = (&self.entries, &other.entries);
503        let mut out = Vec::with_capacity(a.len() + b.len());
504        let (mut i, mut j) = (0, 0);
505        while i < a.len() && j < b.len() {
506            match a[i].doc_ids.cmp(&b[j].doc_ids) {
507                std::cmp::Ordering::Equal => {
508                    out.push(a[i].clone());
509                    i += 1;
510                    j += 1;
511                }
512                std::cmp::Ordering::Less => {
513                    out.push(a[i].clone());
514                    i += 1;
515                }
516                std::cmp::Ordering::Greater => {
517                    out.push(b[j].clone());
518                    j += 1;
519                }
520            }
521        }
522        out.extend_from_slice(&a[i..]);
523        out.extend_from_slice(&b[j..]);
524        Self::from_sorted_unchecked(out)
525    }
526
527    /// Select the intersection of tuple support, preserving left payloads.
528    pub fn merge_intersection(&self, other: &Self) -> Self {
529        let (a, b) = (&self.entries, &other.entries);
530        let mut out = Vec::with_capacity(a.len().min(b.len()));
531        let (mut i, mut j) = (0, 0);
532        while i < a.len() && j < b.len() {
533            match a[i].doc_ids.cmp(&b[j].doc_ids) {
534                std::cmp::Ordering::Equal => {
535                    out.push(a[i].clone());
536                    i += 1;
537                    j += 1;
538                }
539                std::cmp::Ordering::Less => i += 1,
540                std::cmp::Ordering::Greater => j += 1,
541            }
542        }
543        Self::from_sorted_unchecked(out)
544    }
545
546    /// Preserve left entries whose tuple support is absent from `other`.
547    pub fn exclude(&self, other: &Self) -> Self {
548        let other_ids: BTreeSet<&Vec<DocId>> = other.entries.iter().map(|e| &e.doc_ids).collect();
549        let out: Vec<GeneralizedPostingEntry> = self
550            .entries
551            .iter()
552            .filter(|e| !other_ids.contains(&e.doc_ids))
553            .cloned()
554            .collect();
555        Self::from_sorted_unchecked(out)
556    }
557
558    pub fn entries(&self) -> &[GeneralizedPostingEntry] {
559        &self.entries
560    }
561
562    /// Materialize tuple support without payloads.
563    pub fn doc_ids_set(&self) -> BTreeSet<Vec<DocId>> {
564        self.entries.iter().map(|e| e.doc_ids.clone()).collect()
565    }
566
567    pub fn len(&self) -> usize {
568        self.entries.len()
569    }
570
571    pub fn is_empty(&self) -> bool {
572        self.entries.is_empty()
573    }
574}
575
576impl FromIterator<GeneralizedPostingEntry> for GeneralizedPostingList {
577    fn from_iter<I: IntoIterator<Item = GeneralizedPostingEntry>>(iter: I) -> Self {
578        Self::from_unsorted(iter.into_iter().collect())
579    }
580}
581
582#[cfg(test)]
583mod tests {
584    use super::*;
585    use crate::types::{GeneralizedPayload, Payload};
586
587    fn pl_of(ids: &[DocId]) -> PostingList {
588        PostingList::from_unsorted(
589            ids.iter()
590                .map(|id| PostingEntry::new(*id, Payload::default()))
591                .collect(),
592        )
593    }
594
595    fn ids(pl: &PostingList) -> Vec<DocId> {
596        pl.doc_ids().collect()
597    }
598
599    #[test]
600    fn empty_list_is_empty() {
601        let pl = PostingList::new();
602        assert!(pl.is_empty());
603        assert_eq!(pl.len(), 0);
604    }
605
606    #[test]
607    fn from_unsorted_sorts_and_dedups() {
608        let pl = pl_of(&[3, 1, 2, 1]);
609        assert_eq!(ids(&pl), vec![1, 2, 3]);
610    }
611
612    #[test]
613    fn union_merges_two_pointer() {
614        let a = pl_of(&[1, 3, 5]);
615        let b = pl_of(&[2, 3, 4]);
616        assert_eq!(ids(&a.merge_union(&b)), vec![1, 2, 3, 4, 5]);
617    }
618
619    #[test]
620    fn intersect_keeps_common() {
621        let a = pl_of(&[1, 3, 5]);
622        let b = pl_of(&[2, 3, 4, 5]);
623        assert_eq!(ids(&a.merge_intersection(&b)), vec![3, 5]);
624    }
625
626    #[test]
627    fn difference_excludes_other_ids() {
628        let a = pl_of(&[1, 2, 3, 4]);
629        let b = pl_of(&[2, 4]);
630        assert_eq!(ids(&a.exclude(&b)), vec![1, 3]);
631    }
632
633    #[test]
634    fn complement_uses_universal() {
635        let a = pl_of(&[2, 4]);
636        let universal = pl_of(&[1, 2, 3, 4, 5]);
637        assert_eq!(ids(&universal.exclude(&a)), vec![1, 3, 5]);
638    }
639
640    #[test]
641    fn payload_operations_are_explicit_methods() {
642        let a = pl_of(&[1, 2, 3]);
643        let b = pl_of(&[2, 3, 4]);
644        assert_eq!(ids(&a.merge_union(&b)), vec![1, 2, 3, 4]);
645        assert_eq!(ids(&a.merge_intersection(&b)), vec![2, 3]);
646        assert_eq!(ids(&a.exclude(&b)), vec![1]);
647    }
648
649    #[test]
650    fn top_k_keeps_highest_scores() {
651        let entries = vec![
652            PostingEntry::new(1, Payload::with_score(0.1)),
653            PostingEntry::new(2, Payload::with_score(0.9)),
654            PostingEntry::new(3, Payload::with_score(0.5)),
655            PostingEntry::new(4, Payload::with_score(0.7)),
656        ];
657        let pl = PostingList::from_unsorted(entries);
658        let top2 = pl.ranked().select_top_k(2);
659        assert_eq!(ids(&top2), vec![2, 4]); // re-sorted by doc_id ascending
660    }
661
662    #[test]
663    fn get_entry_uses_binary_search() {
664        let pl = pl_of(&[10, 20, 30, 40, 50]);
665        assert!(pl.get_entry(30).is_some());
666        assert!(pl.get_entry(35).is_none());
667    }
668
669    #[test]
670    fn merge_payloads_combines_positions_and_scores() {
671        let a = Payload {
672            positions: vec![1, 3],
673            score: 1.0,
674            ..Payload::default()
675        };
676        let b = Payload {
677            positions: vec![2, 3],
678            score: 2.5,
679            ..Payload::default()
680        };
681        let merged = merge_payloads(&a, &b);
682        assert_eq!(merged.positions, vec![1, 2, 3]);
683        assert!((merged.score - 3.5).abs() < f64::EPSILON);
684    }
685
686    #[test]
687    fn consuming_intersection_matches_borrowed_payload_semantics() {
688        let left = PostingList::from_sorted_unchecked(vec![
689            PostingEntry::new(1, Payload::with_score(1.0)),
690            PostingEntry::new(
691                3,
692                Payload {
693                    positions: vec![1, 4],
694                    score: 2.0,
695                    fields: BTreeMap::from([
696                        ("left".into(), Value::Bool(true)),
697                        ("shared".into(), Value::Str("left".into())),
698                    ]),
699                },
700            ),
701            PostingEntry::new(5, Payload::default()),
702        ]);
703        let right = PostingList::from_sorted_unchecked(vec![
704            PostingEntry::new(2, Payload::default()),
705            PostingEntry::new(
706                3,
707                Payload {
708                    positions: vec![2, 4],
709                    score: 4.0,
710                    fields: BTreeMap::from([
711                        ("right".into(), Value::Bool(true)),
712                        ("shared".into(), Value::Str("right".into())),
713                    ]),
714                },
715            ),
716            PostingEntry::new(5, Payload::with_score(8.0)),
717        ]);
718
719        assert_eq!(
720            left.clone().merge_intersection_owned(&right),
721            left.merge_intersection(&right)
722        );
723    }
724
725    #[test]
726    fn support_intersection_discards_payloads() {
727        let left = PostingList::from_sorted_unchecked(vec![
728            PostingEntry::new(1, Payload::with_score(3.0)),
729            PostingEntry::new(2, Payload::with_score(4.0)),
730        ]);
731        let right = PostingList::from_sorted_unchecked(vec![
732            PostingEntry::new(2, Payload::with_score(5.0)),
733            PostingEntry::new(3, Payload::with_score(6.0)),
734        ]);
735
736        assert_eq!(left.merge_support_intersection_owned(&right), pl_of(&[2]));
737    }
738
739    #[test]
740    fn generalized_list_lex_orders_tuples() {
741        let mk = |t: Vec<DocId>| GeneralizedPostingEntry {
742            doc_ids: t,
743            payload: GeneralizedPayload::default(),
744        };
745        let gpl = GeneralizedPostingList::from_unsorted(vec![
746            mk(vec![2, 1]),
747            mk(vec![1, 1]),
748            mk(vec![1, 2]),
749        ]);
750        let want: Vec<Vec<DocId>> = gpl.entries().iter().map(|e| e.doc_ids.clone()).collect();
751        assert_eq!(want, vec![vec![1, 1], vec![1, 2], vec![2, 1]]);
752    }
753
754    #[test]
755    fn generalized_intersect_two_pointer() {
756        let mk = |t: Vec<DocId>| GeneralizedPostingEntry {
757            doc_ids: t,
758            payload: GeneralizedPayload::default(),
759        };
760        let a = GeneralizedPostingList::from_unsorted(vec![
761            mk(vec![1, 1]),
762            mk(vec![1, 2]),
763            mk(vec![2, 3]),
764        ]);
765        let b = GeneralizedPostingList::from_unsorted(vec![mk(vec![1, 2]), mk(vec![2, 3])]);
766        let inter = a.merge_intersection(&b);
767        let want: Vec<Vec<DocId>> = inter.entries().iter().map(|e| e.doc_ids.clone()).collect();
768        assert_eq!(want, vec![vec![1, 2], vec![2, 3]]);
769    }
770}
uqa_core/posting_list.rs

uqa_core/
posting_list.rs
