1///|2/// One trie level: a table split into fixed-size blocks with duplicates3/// removed.4pub struct DedupedBlocks {5 /// For each block of the input, the index of its copy in `blocks`.6 ids : Array[Int32]7 /// The distinct blocks, concatenated. Block `i` starts at8 /// `i * block_size`.9 blocks : Array[Int32]10}1112///|13/// Split `values` into blocks of `block_size` and keep one copy of each14/// distinct block, so `values[k]` is15/// `blocks[ids[k / block_size] * block_size + k % block_size]`.16pub fn deduplicate_blocks(17 values : Array[Int32],18 block_size : Int32,19) -> DedupedBlocks {20 let seen : Map[ArrayView[Int32], Int32] = Map([])21 let ids = []22 let blocks = []23 for start = 0; start < values.length(); start = start + block_size {24 let block = values[start:start + block_size]25 let id = match seen.get(block) {26 Some(id) => id27 None => {28 let id = seen.length()29 seen[block] = id30 blocks.append(block)31 id32 }33 }34 ids.push(id)35 }36 { ids, blocks, }37}38
///|
/// One trie level: a table split into fixed-size blocks with duplicates
/// removed.
pub struct DedupedBlocks {
/// For each block of the input, the index of its copy in `blocks`.
ids : Array[Int32]
/// The distinct blocks, concatenated. Block `i` starts at
/// `i * block_size`.
blocks : Array[Int32]
}
///|
/// Split `values` into blocks of `block_size` and keep one copy of each
/// distinct block, so `values[k]` is
/// `blocks[ids[k / block_size] * block_size + k % block_size]`.
pub fn deduplicate_blocks(
values : Array[Int32],
block_size : Int32,
) -> DedupedBlocks {
let seen : Map[ArrayView[Int32], Int32] = Map([])
let ids = []
let blocks = []
for start = 0; start < values.length(); start = start + block_size {
let block = values[start:start + block_size]
let id = match seen.get(block) {
Some(id) => id
None => {
let id = seen.length()
seen[block] = id
blocks.append(block)
id
}
}
ids.push(id)
}
{ ids, blocks, }
}