tilesort 0.2.0

A sorting algorithm optimized for datasets with pre-sorted contiguous blocks (tiles)
Documentation 
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

use crate::tile_index::{Tile, TileIndex};
use crate::KeyExtractor;

fn process_tile_boundaries<K: Ord>(
    tile_index: &mut TileIndex,
    tile_start_idx: &mut Option<usize>,
    idx: usize,
    element_keys: &[K],
    reverse: bool,
) {
    if let Some(start_idx) = tile_start_idx {
        let prev_index: usize = if idx == 0 {
            // First element always starts a new tile
            0
        } else {
            idx - 1
        };

        let prev_key = &element_keys[prev_index];

        // Check if out of order
        let finish_tile = if reverse {
            &element_keys[idx] > prev_key // For descending sort
        } else {
            &element_keys[idx] < prev_key // For ascending sort
        };

        if finish_tile {
            let count = idx - *start_idx;
            let new_tile = Tile::new(*start_idx, count);
            tile_index.insert_tile(new_tile, element_keys, reverse);
            *tile_start_idx = None;
        }
    }

    if tile_start_idx.is_none() {
        *tile_start_idx = Some(idx);
    }
}

fn add_last_tile<K: Ord>(
    tile_index: &mut TileIndex,
    tile_start_idx: &Option<usize>,
    element_keys: &[K],
    reverse: bool,
) {
    let start_idx =
        tile_start_idx.expect("There should be at least one tile index before the end of the data");
    let elements_count = element_keys.len();
    let count = elements_count - start_idx;
    let new_tile = Tile::new(start_idx, count);
    tile_index.insert_tile(new_tile, element_keys, reverse);
}

/// Phase 1: Scan through the data and build the tile index.
pub fn scan_phase<T, K, E>(data: &[T], key_extractor: E, reverse: bool) -> TileIndex
where
    K: Ord,
    E: KeyExtractor<T, K>,
{
    let mut tile_index = TileIndex::new();
    let mut element_keys: Vec<K> = Vec::with_capacity(data.len());
    let mut tile_start_idx: Option<usize> = None;

    for (idx, element) in data.iter().enumerate() {
        let key = key_extractor.extract_key(element);
        element_keys.push(key);

        process_tile_boundaries(
            &mut tile_index,
            &mut tile_start_idx,
            idx,
            &element_keys,
            reverse,
        );
    }

    // Add the last tile
    add_last_tile(&mut tile_index, &tile_start_idx, &element_keys, reverse);

    tile_index
}

pub fn scan_phase_without_key<T>(data: &[T], reverse: bool) -> TileIndex
where
    T: Ord,
{
    let mut tile_index = TileIndex::new();
    let mut tile_start_idx: Option<usize> = None;

    for (idx, _) in data.iter().enumerate() {
        process_tile_boundaries(&mut tile_index, &mut tile_start_idx, idx, data, reverse);
    }

    // Add the last tile
    add_last_tile(&mut tile_index, &tile_start_idx, data, reverse);

    tile_index
}