index_table_builder/
lib.rs

1// Copyright 2025 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use std::cmp::Eq;
6use std::collections::HashMap;
7use std::hash::Hash;
8
9/// Deduplicate values, returning the index to the unique occurrence in an array.
10pub struct IndexTableBuilder<T>
11where
12    T: Eq + Hash + Default + 'static,
13{
14    index: HashMap<T, usize>,
15}
16
17impl<T> Default for IndexTableBuilder<T>
18where
19    T: Eq + Hash + Default + 'static,
20{
21    fn default() -> IndexTableBuilder<T> {
22        IndexTableBuilder { index: HashMap::new() }
23    }
24}
25
26impl<T> IndexTableBuilder<T>
27where
28    T: Eq + Hash + Default + 'static,
29{
30    /// Inserts a value, if not present yet, and returns its index.
31    pub fn intern(&mut self, value: impl Into<T>) -> usize {
32        let next_index = self.index.len();
33        *self.index.entry(value.into()).or_insert(next_index)
34    }
35
36    /// Consumes this builder and returns all the values that were interned.
37    pub fn build(mut self) -> Vec<T> {
38        let mut table = Vec::default();
39        table.resize_with(self.index.len(), Default::default);
40        self.index.drain().for_each(|(element, index)| {
41            table[index] = element;
42        });
43        table
44    }
45}
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50    use std::iter::zip;
51
52    #[test]
53    fn test_starts_with_empty_string() {
54        let result = IndexTableBuilder::default().build();
55        assert_eq!(vec![], result);
56    }
57
58    #[test]
59    fn test_mostly_empty() {
60        let b = IndexTableBuilder::default();
61        assert_eq!(0, b.intern("singleton"));
62        assert_eq!(vec!["singleton"], b.build());
63    }
64
65    /// Ensure the table can intern unique words.
66    #[test]
67    fn test_interns_unique_words() {
68        let mut b = IndexTableBuilder::default();
69        let words = vec!["Those", "are", "unique", "words"];
70        let indices: Vec<i64> = words.iter().map(|w| b.intern(w)).collect();
71        let result = b.build();
72
73        for (index, word) in zip(indices, words.iter()) {
74            assert_eq!(*word, result[index as usize]);
75        }
76    }
77
78    /// Ensure the table can intern repeated words, and reuses
79    /// the same entries.
80    #[test]
81    fn test_interns_repeated_words() {
82        let mut b = IndexTableBuilder::default();
83        let words = vec!["word", "word", "word", "word"];
84        let indices: Vec<i64> = words.iter().map(|w| b.intern(w)).collect();
85        let result = b.build();
86
87        let repeated = indices[0];
88        for (index, word) in zip(indices, words.iter()) {
89            assert_eq!(*word, result[index as usize]);
90            assert_eq!(repeated, index);
91        }
92    }
93}
index_table_builder/lib.rs

index_table_builder/
lib.rs
