tdb_succinct/
adjacencylist.rs

1//! Logic for storing, loading and using adjacency lists.
2//!
3//! An adjacency list conceptually stores pairs of u64. the numbers on
4//! the left-hand-side of this pair form a continuous range from 1 up
5//! to some maximum, while the right-hand-side can be anything.
6//!
7//! Internally, this is stored as a `LogArray` and a `BitIndex` of equal length, where the
8//! LogArray stores all the right-hand-sides, while the BitIndex
9//! stores the boundaries between left-hand-sides (storing a 0 if this
10//! left-hand-side has more pairs to follow, or 1 if this was the last
11//! pair).
12
13use std::convert::TryInto;
14use std::io;
15use std::pin::Pin;
16
17use bytes::Bytes;
18use bytes::BytesMut;
19
20use crate::storage::{FileLoad, FileStore, SyncableFile};
21
22use super::bitarray::*;
23use super::bitindex::*;
24use super::logarray::*;
25use futures::future;
26use futures::stream::{Stream, StreamExt, TryStreamExt};
27use futures::task::{Context, Poll};
28
29#[derive(Clone)]
30pub struct AdjacencyList {
31    pub nums: LogArray,
32    pub bits: BitIndex,
33}
34
35impl AdjacencyList {
36    pub fn from_parts(nums: LogArray, bits: BitIndex) -> AdjacencyList {
37        debug_assert_eq!(nums.len(), bits.len());
38        AdjacencyList { nums, bits }
39    }
40
41    pub fn from_buffers(buffers: AdjacencyListBuffers) -> AdjacencyList {
42        Self::parse(
43            buffers.nums,
44            buffers.bits,
45            buffers.bitindex_blocks,
46            buffers.bitindex_sblocks,
47        )
48    }
49
50    pub fn parse(
51        nums_slice: Bytes,
52        bits_slice: Bytes,
53        bits_block_slice: Bytes,
54        bits_sblock_slice: Bytes,
55    ) -> AdjacencyList {
56        let nums = LogArray::parse(nums_slice).unwrap();
57        let bit_array = BitArray::from_bits(bits_slice).unwrap();
58        let bits_block_array = LogArray::parse(bits_block_slice).unwrap();
59        let bits_sblock_array = LogArray::parse(bits_sblock_slice).unwrap();
60        let bits = BitIndex::from_parts(bit_array, bits_block_array, bits_sblock_array);
61
62        Self::from_parts(nums, bits)
63    }
64
65    pub fn left_count(&self) -> usize {
66        if self.bits.len() == 0 {
67            0
68        } else {
69            self.bits.rank1((self.bits.len() as u64) - 1) as usize
70        }
71    }
72
73    pub fn right_count(&self) -> usize {
74        self.bits.len()
75    }
76
77    pub fn offset_for(&self, index: u64) -> u64 {
78        if index == 1 {
79            0
80        } else {
81            self.bits.select1(index - 1).unwrap() + 1
82        }
83    }
84
85    pub fn pair_at_pos(&self, pos: u64) -> (u64, u64) {
86        let left = if pos == 0 {
87            0
88        } else {
89            self.bits.rank1(pos - 1)
90        } + 1;
91        let right = self.nums.entry(pos as usize);
92
93        (left, right)
94    }
95
96    pub fn left_at_pos(&self, pos: u64) -> u64 {
97        if pos == 0 {
98            1
99        } else {
100            self.bits.rank1(pos - 1) + 1
101        }
102    }
103
104    pub fn bit_at_pos(&self, pos: u64) -> bool {
105        self.bits.get(pos)
106    }
107
108    pub fn num_at_pos(&self, pos: u64) -> u64 {
109        self.nums.entry(pos.try_into().unwrap())
110    }
111
112    pub fn get(&self, index: u64) -> LogArray {
113        if index < 1 {
114            panic!("minimum index has to be 1");
115        }
116        if index > self.left_count() as u64 {
117            panic!(
118                "index {} too large for adjacency list of length {}",
119                index,
120                self.left_count()
121            );
122        }
123
124        let start = self.offset_for(index);
125        let end = self.bits.select1(index).unwrap();
126        let length = end - start + 1;
127
128        self.nums.slice(start as usize, length as usize)
129    }
130
131    pub fn iter(&self) -> AdjacencyListIterator {
132        AdjacencyListIterator {
133            pos: 0,
134            left: 1,
135            bits: self.bits.clone(),
136            nums: self.nums.clone(),
137        }
138    }
139
140    pub fn bits(&self) -> &BitIndex {
141        &self.bits
142    }
143
144    pub fn nums(&self) -> &LogArray {
145        &self.nums
146    }
147}
148
149pub struct AdjacencyListIterator {
150    pos: usize,
151    left: u64,
152    bits: BitIndex,
153    nums: LogArray,
154}
155
156impl Iterator for AdjacencyListIterator {
157    type Item = (u64, u64);
158
159    fn next(&mut self) -> Option<(u64, u64)> {
160        loop {
161            if self.pos >= self.bits.len() {
162                return None;
163            }
164
165            let bit = self.bits.get(self.pos as u64);
166            let num = self.nums.entry(self.pos);
167
168            let result = (self.left, num);
169            if bit {
170                self.left += 1;
171            }
172
173            self.pos += 1;
174
175            if num == 0 {
176                continue;
177            }
178
179            return Some(result);
180        }
181    }
182}
183
184pub struct AdjacencyBitCountStream<S: Stream<Item = io::Result<bool>> + Unpin> {
185    stream: S,
186    count: u64,
187}
188
189impl<S: Stream<Item = io::Result<bool>> + Unpin> AdjacencyBitCountStream<S> {
190    fn new(stream: S, offset: u64) -> Self {
191        AdjacencyBitCountStream {
192            stream,
193            count: offset,
194        }
195    }
196}
197
198impl<S: Stream<Item = io::Result<bool>> + Unpin> Stream for AdjacencyBitCountStream<S> {
199    type Item = io::Result<u64>;
200
201    fn poll_next(self: Pin<&mut Self>, cx: &mut Context) -> Poll<Option<io::Result<u64>>> {
202        let self_ = self.get_mut();
203        let next = Pin::new(&mut self_.stream).poll_next(cx);
204        next.map(|x| {
205            x.map(|x| {
206                x.map(|b| {
207                    let result = self_.count;
208
209                    if b {
210                        self_.count += 1;
211                    }
212
213                    result
214                })
215            })
216        })
217    }
218}
219
220pub async fn adjacency_list_stream_pairs<F: 'static + FileLoad>(
221    bits_file: F,
222    nums_file: F,
223) -> io::Result<impl Stream<Item = io::Result<(u64, u64)>> + Unpin + Send> {
224    Ok(
225        AdjacencyBitCountStream::new(bitarray_stream_bits(bits_file).await?, 1)
226            .zip(logarray_stream_entries(nums_file).await?)
227            .map(|(left, right)| {
228                let left = left?;
229                let right = right?;
230
231                Ok::<_, io::Error>((left, right))
232            })
233            .try_filter(|(_, right): &(u64, u64)| future::ready(*right != 0))
234            .into_stream(),
235    )
236}
237
238pub struct UnindexedAdjacencyListBufBuilder {
239    bitarray: BitArrayBufBuilder<BytesMut>,
240    nums: LogArrayBufBuilder<BytesMut>,
241    last_left: u64,
242    last_right: u64,
243}
244
245impl UnindexedAdjacencyListBufBuilder {
246    pub fn new(width: u8) -> Self {
247        Self {
248            bitarray: BitArrayBufBuilder::new(BytesMut::new()),
249            nums: LogArrayBufBuilder::new(BytesMut::new(), width),
250            last_left: 0,
251            last_right: 0,
252        }
253    }
254
255    pub fn push(&mut self, left: u64, right: u64) {
256        // the tricky thing with this code is that the bitarray lags one entry behind the logarray.
257        // The reason for this is that at push time, we do not yet know if this entry is going to be
258        // the last entry for `left`, we only know this when we push a greater `left` later on.
259        if left < self.last_left || (left == self.last_left && right <= self.last_right) {
260            panic!("tried to push an unordered adjacent pair");
261        }
262
263        // the left hand side of the adjacencylist is expected to be a continuous range from 1 up to the max
264        // but when adding entries, there may be holes. We handle holes by writing a '0' to the logarray
265        // (which is otherwise an invalid right-hand side) and pushing a 1 onto the bitarray to immediately close the segment.
266        let skip = left - self.last_left;
267
268        if self.last_left == 0 && skip == 1 {
269            // this is the first entry. we can't push a bit yet
270        } else if skip == 0 {
271            // same `left` as before. so the previous entry was not the last one, and the bitarray gets a 0 appended.
272            self.bitarray.push(false);
273        } else {
274            // if this is the first element, but we do need to skip, make sure we write one less bit than we'd usually do
275            let bitskip = if self.last_left == 0 { skip - 1 } else { skip };
276            // there's a different `left`. we push a bunch of 1s to the bitarray, and 0s to the num array.
277            for _ in 0..bitskip {
278                self.bitarray.push(true);
279            }
280            for _ in 0..(skip - 1) {
281                self.nums.push(0);
282            }
283        }
284
285        // finally push right to the logarray
286        self.nums.push(right);
287        self.last_left = left;
288        self.last_right = right;
289    }
290
291    pub fn push_all<I: Iterator<Item = (u64, u64)>>(&mut self, mut iter: I) {
292        while let Some((left, right)) = iter.next() {
293            self.push(left, right);
294        }
295    }
296
297    pub fn finalize(mut self) -> (Bytes, Bytes) {
298        if self.nums.count() != 0 {
299            // push last bit to bitarray
300            self.bitarray.push(true);
301        }
302
303        let ba = self.bitarray.finalize();
304        let nums = self.nums.finalize();
305
306        (ba.freeze(), nums.freeze())
307    }
308
309    pub fn count(&self) -> u64 {
310        self.bitarray.count()
311    }
312}
313
314pub struct UnindexedAdjacencyListBuilder<W1: SyncableFile, W2: SyncableFile> {
315    bitarray: BitArrayFileBuilder<W1>,
316    nums: LogArrayFileBuilder<W2>,
317    last_left: u64,
318    last_right: u64,
319}
320
321impl<W1: SyncableFile, W2: SyncableFile> UnindexedAdjacencyListBuilder<W1, W2> {
322    pub fn new(bits_file: W1, nums_file: W2, width: u8) -> Self {
323        Self {
324            bitarray: BitArrayFileBuilder::new(bits_file),
325            nums: LogArrayFileBuilder::new(nums_file, width),
326            last_left: 0,
327            last_right: 0,
328        }
329    }
330
331    pub async fn push(&mut self, left: u64, right: u64) -> io::Result<()> {
332        // the tricky thing with this code is that the bitarray lags one entry behind the logarray.
333        // The reason for this is that at push time, we do not yet know if this entry is going to be
334        // the last entry for `left`, we only know this when we push a greater `left` later on.
335        if left < self.last_left || (left == self.last_left && right <= self.last_right) {
336            panic!("tried to push an unordered adjacent pair");
337        }
338
339        // the left hand side of the adjacencylist is expected to be a continuous range from 1 up to the max
340        // but when adding entries, there may be holes. We handle holes by writing a '0' to the logarray
341        // (which is otherwise an invalid right-hand side) and pushing a 1 onto the bitarray to immediately close the segment.
342        let skip = left - self.last_left;
343
344        if self.last_left == 0 && skip == 1 {
345            // this is the first entry. we can't push a bit yet
346        } else if skip == 0 {
347            // same `left` as before. so the previous entry was not the last one, and the bitarray gets a 0 appended.
348            self.bitarray.push(false).await?;
349        } else {
350            // if this is the first element, but we do need to skip, make sure we write one less bit than we'd usually do
351            let bitskip = if self.last_left == 0 { skip - 1 } else { skip };
352            // there's a different `left`. we push a bunch of 1s to the bitarray, and 0s to the num array.
353            for _ in 0..bitskip {
354                self.bitarray.push(true).await?;
355            }
356            for _ in 0..(skip - 1) {
357                self.nums.push(0).await?;
358            }
359        }
360
361        // finally push right to the logarray
362        self.nums.push(right).await?;
363        self.last_left = left;
364        self.last_right = right;
365
366        Ok(())
367    }
368
369    pub async fn push_all<S: Stream<Item = io::Result<(u64, u64)>> + Unpin>(
370        &mut self,
371        mut stream: S,
372    ) -> io::Result<()> {
373        while let Some((left, right)) = stream.try_next().await? {
374            self.push(left, right).await?;
375        }
376
377        Ok(())
378    }
379
380    pub async fn finalize(mut self) -> io::Result<()> {
381        if self.nums.count() != 0 {
382            // push last bit to bitarray
383            self.bitarray.push(true).await?;
384        }
385
386        self.bitarray.finalize().await?;
387        self.nums.finalize().await?;
388
389        Ok(())
390    }
391
392    pub fn count(&self) -> u64 {
393        self.bitarray.count()
394    }
395}
396
397pub struct AdjacencyListBufBuilder {
398    builder: UnindexedAdjacencyListBufBuilder,
399    bitindex_blocks: BytesMut,
400    bitindex_sblocks: BytesMut,
401}
402
403impl AdjacencyListBufBuilder {
404    pub fn new(width: u8) -> AdjacencyListBufBuilder {
405        AdjacencyListBufBuilder {
406            builder: UnindexedAdjacencyListBufBuilder::new(width),
407            bitindex_blocks: BytesMut::new(),
408            bitindex_sblocks: BytesMut::new(),
409        }
410    }
411
412    pub fn push(&mut self, left: u64, right: u64) {
413        self.builder.push(left, right)
414    }
415
416    pub fn push_all<I: Iterator<Item = (u64, u64)>>(&mut self, iter: I) {
417        self.builder.push_all(iter)
418    }
419
420    pub fn finalize(self) -> AdjacencyListBuffers {
421        let AdjacencyListBufBuilder {
422            builder,
423            mut bitindex_blocks,
424            mut bitindex_sblocks,
425        } = self;
426        let (bitfile, nums) = builder.finalize();
427
428        build_bitindex_from_buf(&bitfile[..], &mut bitindex_blocks, &mut bitindex_sblocks);
429
430        AdjacencyListBuffers {
431            nums,
432            bits: bitfile,
433            bitindex_blocks: bitindex_blocks.freeze(),
434            bitindex_sblocks: bitindex_sblocks.freeze(),
435        }
436    }
437
438    pub fn count(&self) -> u64 {
439        self.builder.count()
440    }
441}
442
443pub struct AdjacencyListBuffers {
444    nums: Bytes,
445    bits: Bytes,
446    bitindex_blocks: Bytes,
447    bitindex_sblocks: Bytes,
448}
449
450pub struct AdjacencyListBuilder<F, W1, W2, W3>
451where
452    F: 'static + FileLoad + FileStore,
453    W1: 'static + SyncableFile,
454    W2: 'static + SyncableFile,
455    W3: 'static + SyncableFile,
456{
457    bitfile: F,
458    builder: UnindexedAdjacencyListBuilder<F::Write, W3>,
459    bitindex_blocks: W1,
460    bitindex_sblocks: W2,
461}
462
463impl<F, W1, W2, W3> AdjacencyListBuilder<F, W1, W2, W3>
464where
465    F: 'static + FileLoad + FileStore,
466    W1: 'static + SyncableFile,
467    W2: 'static + SyncableFile,
468    W3: 'static + SyncableFile,
469{
470    pub async fn new(
471        bitfile: F,
472        bitindex_blocks: W1,
473        bitindex_sblocks: W2,
474        nums_writer: W3,
475        width: u8,
476    ) -> io::Result<AdjacencyListBuilder<F, W1, W2, W3>> {
477        Ok(AdjacencyListBuilder {
478            builder: UnindexedAdjacencyListBuilder::new(
479                bitfile.open_write().await?,
480                nums_writer,
481                width,
482            ),
483            bitfile,
484            bitindex_blocks,
485            bitindex_sblocks,
486        })
487    }
488
489    pub async fn push(&mut self, left: u64, right: u64) -> io::Result<()> {
490        self.builder.push(left, right).await
491    }
492
493    pub async fn push_all<S: Stream<Item = io::Result<(u64, u64)>> + Unpin>(
494        &mut self,
495        stream: S,
496    ) -> io::Result<()> {
497        self.builder.push_all(stream).await
498    }
499
500    pub async fn finalize(self) -> io::Result<()> {
501        let AdjacencyListBuilder {
502            bitfile,
503            builder,
504            bitindex_blocks,
505            bitindex_sblocks,
506        } = self;
507        builder.finalize().await?;
508
509        build_bitindex(
510            bitfile.open_read().await?,
511            bitindex_blocks,
512            bitindex_sblocks,
513        )
514        .await?;
515
516        Ok(())
517    }
518
519    pub fn count(&self) -> u64 {
520        self.builder.count()
521    }
522}
523
524#[cfg(test)]
525mod tests {
526    use super::*;
527    use crate::{storage::memory::MemoryBackedStore, util};
528    use futures::executor::block_on;
529
530    #[tokio::test]
531    async fn can_build_and_parse_adjacencylist() {
532        let bitfile = MemoryBackedStore::new();
533        let bitindex_blocks_file = MemoryBackedStore::new();
534        let bitindex_sblocks_file = MemoryBackedStore::new();
535        let nums_file = MemoryBackedStore::new();
536
537        let mut builder = AdjacencyListBuilder::new(
538            bitfile.clone(),
539            bitindex_blocks_file.open_write().await.unwrap(),
540            bitindex_sblocks_file.open_write().await.unwrap(),
541            nums_file.open_write().await.unwrap(),
542            8,
543        )
544        .await
545        .unwrap();
546
547        builder
548            .push_all(util::stream_iter_ok(vec![(1, 1), (1, 3), (2, 5), (7, 4)]))
549            .await
550            .unwrap();
551        builder.finalize().await.unwrap();
552
553        let bitfile_contents = block_on(bitfile.map()).unwrap();
554        let bitindex_blocks_contents = block_on(bitindex_blocks_file.map()).unwrap();
555        let bitindex_sblocks_contents = block_on(bitindex_sblocks_file.map()).unwrap();
556        let nums_contents = block_on(nums_file.map()).unwrap();
557
558        let adjacencylist = AdjacencyList::parse(
559            nums_contents,
560            bitfile_contents,
561            bitindex_blocks_contents,
562            bitindex_sblocks_contents,
563        );
564
565        let slice = adjacencylist.get(1);
566        assert_eq!(2, slice.len());
567        assert_eq!(1, slice.entry(0));
568        assert_eq!(3, slice.entry(1));
569
570        let slice = adjacencylist.get(2);
571        assert_eq!(1, slice.len());
572        assert_eq!(5, slice.entry(0));
573
574        let slice = adjacencylist.get(3);
575        assert_eq!(1, slice.len());
576        assert_eq!(0, slice.entry(0));
577
578        let slice = adjacencylist.get(4);
579        assert_eq!(1, slice.len());
580        assert_eq!(0, slice.entry(0));
581
582        let slice = adjacencylist.get(5);
583        assert_eq!(1, slice.len());
584        assert_eq!(0, slice.entry(0));
585
586        let slice = adjacencylist.get(6);
587        assert_eq!(1, slice.len());
588        assert_eq!(0, slice.entry(0));
589
590        let slice = adjacencylist.get(7);
591        assert_eq!(1, slice.len());
592        assert_eq!(4, slice.entry(0));
593    }
594
595    #[tokio::test]
596    async fn empty_adjacencylist() {
597        let bitfile = MemoryBackedStore::new();
598        let bitindex_blocks_file = MemoryBackedStore::new();
599        let bitindex_sblocks_file = MemoryBackedStore::new();
600        let nums_file = MemoryBackedStore::new();
601
602        let mut builder = AdjacencyListBuilder::new(
603            bitfile.clone(),
604            bitindex_blocks_file.open_write().await.unwrap(),
605            bitindex_sblocks_file.open_write().await.unwrap(),
606            nums_file.open_write().await.unwrap(),
607            8,
608        )
609        .await
610        .unwrap();
611
612        builder
613            .push_all(util::stream_iter_ok(Vec::new()))
614            .await
615            .unwrap();
616        builder.finalize().await.unwrap();
617
618        let bitfile_contents = block_on(bitfile.map()).unwrap();
619        let bitindex_blocks_contents = block_on(bitindex_blocks_file.map()).unwrap();
620        let bitindex_sblocks_contents = block_on(bitindex_sblocks_file.map()).unwrap();
621        let nums_contents = block_on(nums_file.map()).unwrap();
622        let adjacencylist = AdjacencyList::parse(
623            nums_contents,
624            bitfile_contents,
625            bitindex_blocks_contents,
626            bitindex_sblocks_contents,
627        );
628
629        assert_eq!(0, adjacencylist.left_count());
630    }
631
632    #[tokio::test]
633    async fn adjacencylist_with_skip_at_start() {
634        let bitfile = MemoryBackedStore::new();
635        let bitindex_blocks_file = MemoryBackedStore::new();
636        let bitindex_sblocks_file = MemoryBackedStore::new();
637        let nums_file = MemoryBackedStore::new();
638
639        let mut builder = AdjacencyListBuilder::new(
640            bitfile.clone(),
641            bitindex_blocks_file.open_write().await.unwrap(),
642            bitindex_sblocks_file.open_write().await.unwrap(),
643            nums_file.open_write().await.unwrap(),
644            8,
645        )
646        .await
647        .unwrap();
648
649        builder
650            .push_all(util::stream_iter_ok(vec![(3, 2), (7, 4)]))
651            .await
652            .unwrap();
653        builder.finalize().await.unwrap();
654
655        let bitfile_contents = block_on(bitfile.map()).unwrap();
656        let bitindex_blocks_contents = block_on(bitindex_blocks_file.map()).unwrap();
657        let bitindex_sblocks_contents = block_on(bitindex_sblocks_file.map()).unwrap();
658        let nums_contents = block_on(nums_file.map()).unwrap();
659        let adjacencylist = AdjacencyList::parse(
660            nums_contents,
661            bitfile_contents,
662            bitindex_blocks_contents,
663            bitindex_sblocks_contents,
664        );
665
666        let slice = adjacencylist.get(1);
667        assert_eq!(1, slice.len());
668        assert_eq!(0, slice.entry(0));
669
670        let slice = adjacencylist.get(2);
671        assert_eq!(1, slice.len());
672        assert_eq!(0, slice.entry(0));
673
674        let slice = adjacencylist.get(3);
675        assert_eq!(1, slice.len());
676        assert_eq!(2, slice.entry(0));
677
678        let slice = adjacencylist.get(4);
679        assert_eq!(1, slice.len());
680        assert_eq!(0, slice.entry(0));
681
682        let slice = adjacencylist.get(5);
683        assert_eq!(1, slice.len());
684        assert_eq!(0, slice.entry(0));
685
686        let slice = adjacencylist.get(6);
687        assert_eq!(1, slice.len());
688        assert_eq!(0, slice.entry(0));
689
690        let slice = adjacencylist.get(7);
691        assert_eq!(1, slice.len());
692        assert_eq!(4, slice.entry(0));
693    }
694
695    #[tokio::test]
696    async fn iterate_over_adjacency_list() {
697        let bitfile = MemoryBackedStore::new();
698        let bitindex_blocks_file = MemoryBackedStore::new();
699        let bitindex_sblocks_file = MemoryBackedStore::new();
700        let nums_file = MemoryBackedStore::new();
701        let contents = vec![(1, 1), (1, 3), (2, 5), (7, 4)];
702
703        let mut builder = AdjacencyListBuilder::new(
704            bitfile.clone(),
705            bitindex_blocks_file.open_write().await.unwrap(),
706            bitindex_sblocks_file.open_write().await.unwrap(),
707            nums_file.open_write().await.unwrap(),
708            8,
709        )
710        .await
711        .unwrap();
712
713        builder
714            .push_all(util::stream_iter_ok(contents))
715            .await
716            .unwrap();
717        builder.finalize().await.unwrap();
718
719        let bitfile_contents = block_on(bitfile.map()).unwrap();
720        let bitindex_blocks_contents = block_on(bitindex_blocks_file.map()).unwrap();
721        let bitindex_sblocks_contents = block_on(bitindex_sblocks_file.map()).unwrap();
722        let nums_contents = block_on(nums_file.map()).unwrap();
723
724        let adjacencylist = AdjacencyList::parse(
725            nums_contents,
726            bitfile_contents,
727            bitindex_blocks_contents,
728            bitindex_sblocks_contents,
729        );
730
731        assert_eq!(
732            vec![(1, 1), (1, 3), (2, 5), (7, 4)],
733            adjacencylist.iter().collect::<Vec<_>>()
734        );
735    }
736
737    #[tokio::test]
738    async fn iterate_over_adjacency_list_files() {
739        let bitfile = MemoryBackedStore::new();
740        let bitindex_blocks_file = MemoryBackedStore::new();
741        let bitindex_sblocks_file = MemoryBackedStore::new();
742        let nums_file = MemoryBackedStore::new();
743        let contents = vec![(1, 1), (1, 3), (2, 5), (7, 4)];
744
745        let mut builder = AdjacencyListBuilder::new(
746            bitfile.clone(),
747            bitindex_blocks_file.open_write().await.unwrap(),
748            bitindex_sblocks_file.open_write().await.unwrap(),
749            nums_file.open_write().await.unwrap(),
750            8,
751        )
752        .await
753        .unwrap();
754
755        builder
756            .push_all(util::stream_iter_ok(contents.clone()))
757            .await
758            .unwrap();
759        builder.finalize().await.unwrap();
760
761        let result = adjacency_list_stream_pairs(bitfile, nums_file)
762            .await
763            .unwrap()
764            .try_collect::<Vec<_>>()
765            .await
766            .unwrap();
767
768        assert_eq!(result, contents);
769    }
770
771    #[tokio::test]
772    async fn pair_at_pos_starting_at_1_returns_correct_pair() {
773        let bitfile = MemoryBackedStore::new();
774        let bitindex_blocks_file = MemoryBackedStore::new();
775        let bitindex_sblocks_file = MemoryBackedStore::new();
776        let nums_file = MemoryBackedStore::new();
777
778        let contents = vec![
779            (1, 1),
780            (2, 3),
781            (2, 4),
782            (2, 6),
783            (3, 1),
784            (3, 3),
785            (3, 4),
786            (3, 8),
787            (7, 4),
788            (8, 12),
789            (11, 3),
790        ];
791
792        let mut builder = AdjacencyListBuilder::new(
793            bitfile.clone(),
794            bitindex_blocks_file.open_write().await.unwrap(),
795            bitindex_sblocks_file.open_write().await.unwrap(),
796            nums_file.open_write().await.unwrap(),
797            8,
798        )
799        .await
800        .unwrap();
801
802        builder
803            .push_all(util::stream_iter_ok(contents.clone()))
804            .await
805            .unwrap();
806        builder.finalize().await.unwrap();
807
808        let bitfile_contents = block_on(bitfile.map()).unwrap();
809        let bitindex_blocks_contents = block_on(bitindex_blocks_file.map()).unwrap();
810        let bitindex_sblocks_contents = block_on(bitindex_sblocks_file.map()).unwrap();
811        let nums_contents = block_on(nums_file.map()).unwrap();
812        let adjacencylist = AdjacencyList::parse(
813            nums_contents,
814            bitfile_contents,
815            bitindex_blocks_contents,
816            bitindex_sblocks_contents,
817        );
818
819        let result: Vec<_> = (0..adjacencylist.right_count())
820            .map(|i| adjacencylist.pair_at_pos(i as u64))
821            .collect();
822
823        assert_eq!(
824            vec![
825                (1, 1),
826                (2, 3),
827                (2, 4),
828                (2, 6),
829                (3, 1),
830                (3, 3),
831                (3, 4),
832                (3, 8),
833                (4, 0),
834                (5, 0),
835                (6, 0),
836                (7, 4),
837                (8, 12),
838                (9, 0),
839                (10, 0),
840                (11, 3)
841            ],
842            result
843        );
844    }
845
846    #[tokio::test]
847    async fn pair_at_pos_with_skip_returns_correct_pair() {
848        let bitfile = MemoryBackedStore::new();
849        let bitindex_blocks_file = MemoryBackedStore::new();
850        let bitindex_sblocks_file = MemoryBackedStore::new();
851        let nums_file = MemoryBackedStore::new();
852
853        let contents = vec![
854            (2, 3),
855            (2, 4),
856            (2, 6),
857            (3, 1),
858            (3, 3),
859            (3, 4),
860            (3, 8),
861            (7, 4),
862            (8, 12),
863            (11, 3),
864        ];
865
866        let mut builder = AdjacencyListBuilder::new(
867            bitfile.clone(),
868            bitindex_blocks_file.open_write().await.unwrap(),
869            bitindex_sblocks_file.open_write().await.unwrap(),
870            nums_file.open_write().await.unwrap(),
871            8,
872        )
873        .await
874        .unwrap();
875
876        builder
877            .push_all(util::stream_iter_ok(contents.clone()))
878            .await
879            .unwrap();
880        builder.finalize().await.unwrap();
881
882        let bitfile_contents = block_on(bitfile.map()).unwrap();
883        let bitindex_blocks_contents = block_on(bitindex_blocks_file.map()).unwrap();
884        let bitindex_sblocks_contents = block_on(bitindex_sblocks_file.map()).unwrap();
885        let nums_contents = block_on(nums_file.map()).unwrap();
886
887        let adjacencylist = AdjacencyList::parse(
888            nums_contents,
889            bitfile_contents,
890            bitindex_blocks_contents,
891            bitindex_sblocks_contents,
892        );
893
894        let result: Vec<_> = (0..adjacencylist.right_count())
895            .map(|i| adjacencylist.pair_at_pos(i as u64))
896            .collect();
897
898        assert_eq!(
899            vec![
900                (1, 0),
901                (2, 3),
902                (2, 4),
903                (2, 6),
904                (3, 1),
905                (3, 3),
906                (3, 4),
907                (3, 8),
908                (4, 0),
909                (5, 0),
910                (6, 0),
911                (7, 4),
912                (8, 12),
913                (9, 0),
914                (10, 0),
915                (11, 3)
916            ],
917            result
918        );
919    }
920
921    #[test]
922    fn adjacencylist_buf_builder_works() {
923        let adjacencies = [(1, 1), (1, 5), (2, 3), (2, 7), (4, 8)];
924        let mut builder = AdjacencyListBufBuilder::new(8);
925        builder.push_all(adjacencies.iter().copied());
926        let buffers = builder.finalize();
927        let aj = AdjacencyList::from_buffers(buffers);
928
929        let result: Vec<_> = aj.iter().collect();
930        assert_eq!(&adjacencies[..], &result[..]);
931    }
932}
tdb_succinct/adjacencylist.rs

tdb_succinct/
adjacencylist.rs
