1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// Copyright (c) Cole Frederick. All rights reserved.
// The use and distribution terms for this software are covered by the
// Eclipse Public License 1.0 (https://opensource.org/licenses/eclipse-1.0.php)
// which can be found in the file epl-v10.html at the root of this distribution.
// By using this software in any fashion, you are agreeing to be bound by the terms of this license.
// You must not remove this notice, or any other, from this software.

use super::*;

// Accesses an item based on index
pub fn nth(prism: AnchoredLine, idx: u32) -> AnchoredLine {
    let guide = Guide::hydrate(prism);
    if idx >= guide.count {
        panic!("Index out of bounds: {} in vector of count {}", idx, guide.count);
    }
    if guide.count <= TAIL_CAP {
        guide.root.offset(idx as i32)
    } else {
        nth_tailed(guide, idx)
    }
}

// Traverses down the tree using the index, digit by digit
fn nth_tailed(guide: Guide, idx: u32) -> AnchoredLine {
    let tailoff = tailoff(guide.count);
    if idx >= tailoff {
        guide.root[-1].segment().line_at(idx - tailoff)
    } else {
        let digit_count = digit_count(tailoff - 1);
        let mut shift = digit_count * BITS;
        let mut curr = {
            shift -= BITS;
            guide.root.offset(last_digit(idx >> shift) as i32)
        };
        for _ in 0..(digit_count - 1) {
            let digit = {
                shift -= BITS;
                last_digit(idx >> shift)
            };
            curr = curr[0].segment().line_at(digit);
        }
        assert_eq!(shift, 0);
        curr
    }
}