tf_idf_vectorizer/utils/datastruct/map/
mod.rs

1use hashbrown::HashTable;
2use std::borrow::Borrow;
3use std::fmt::Debug;
4use std::hash::Hasher;
5use std::iter::FusedIterator;
6
7pub mod serde;
8
9/// IndexMap
10/// 連続領域を保証するHashMap
11/// 
12/// # Safety
13/// table, hashes は table_* メソッドが責任をもつこと 更新とか
14/// 
15/// O(1) operations for:
16/// - key -> value
17/// - key -> index
18/// - index -> key
19/// - index -> value
20/// - insert
21/// - swap_remove
22#[derive(Clone, Debug)]
23pub struct IndexMap<K, V, S = ahash::RandomState> {
24    values: Vec<V>,
25    index_set: IndexSet<K, S>,
26}
27
28impl<K, V, S> IndexMap<K, V, S>
29where
30    K: Eq + std::hash::Hash + Clone,
31    S: std::hash::BuildHasher,
32{
33    pub fn with_hasher(hash_builder: S) -> Self {
34        IndexMap {
35            values: Vec::new(),
36            index_set: IndexSet::with_hasher(hash_builder),
37        }
38    }
39
40    pub fn with_capacity(capacity: usize) -> Self
41    where
42        S: Default,
43    {
44        IndexMap {
45            values: Vec::with_capacity(capacity),
46            index_set: IndexSet::with_capacity(capacity),
47        }
48    }
49
50    pub fn new() -> Self
51    where
52        S: Default,
53    {
54        IndexMap {
55            values: Vec::new(),
56            index_set: IndexSet::new(),
57        }
58    }
59
60    pub fn with_hasher_capacity(hash_builder: S, capacity: usize) -> Self {
61        IndexMap {
62            values: Vec::with_capacity(capacity),
63            index_set: IndexSet::with_hasher_capacity(hash_builder, capacity),
64        }
65    }
66
67    pub fn shrink_to_fit(&mut self) {
68        self.values.shrink_to_fit();
69        self.index_set.shrink_to_fit();
70    }
71
72    #[inline]
73    pub fn len(&self) -> usize {
74        self.values.len()
75    }
76
77    #[inline]
78    pub fn iter_values(&self) -> std::slice::Iter<'_, V> {
79        self.values.iter()
80    }
81
82    #[inline]
83    pub fn iter_keys(&self) -> std::slice::Iter<'_, K> {
84        self.index_set.keys.iter()
85    }
86
87    #[inline]
88    pub fn iter(&self) -> IndexMapIter<'_, K, V, S> {
89        IndexMapIter {
90            map: self,
91            index: 0,
92            end: self.len(),
93        }
94    }
95
96    #[inline]
97    pub fn values(&self) -> &Vec<V> {
98        &self.values
99    }
100
101    #[inline]
102    pub fn keys(&self) -> &Vec<K> {
103        &self.index_set.keys()
104    }
105
106    #[inline]
107    pub fn as_index_set(&self) -> &IndexSet<K, S> {
108        &self.index_set
109    }
110
111    #[inline]
112    pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> 
113    where 
114        K: Borrow<Q>,
115        Q: std::hash::Hash + Eq,
116    {
117        if let Some(idx) = self.index_set.table_get(key) {
118            unsafe {
119                Some(self.values.get_unchecked(idx))
120            }
121        } else {
122            None
123        }
124    }
125
126    #[inline]
127    pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> 
128    where 
129        K: Borrow<Q>,
130        Q: std::hash::Hash + Eq,
131    {
132        if let Some(idx) = self.index_set.table_get(key) {
133            unsafe {
134                Some(self.values.get_unchecked_mut(idx))
135            }
136        } else {
137            None
138        }
139    }
140
141    #[inline]
142    pub fn get_with_index(&self, index: usize) -> Option<&V> {
143        self.values.get(index)
144    }
145
146    #[inline]
147    pub fn get_with_index_mut(&mut self, index: usize) -> Option<&mut V> {
148        self.values.get_mut(index)
149    }
150
151    #[inline]
152    pub fn get_key_with_index(&self, index: usize) -> Option<&K> {
153        self.index_set.get_with_index(index)
154    }
155
156    #[inline]
157    pub fn get_key_value_with_index(&self, index: usize) -> Option<(&K, &V)> {
158        if index < self.len() {
159            unsafe {
160                Some((
161                    self.index_set.keys.get_unchecked(index),
162                    self.values.get_unchecked(index),
163                ))
164            }
165        } else {
166            None
167        }
168    }
169
170    #[inline]
171    pub fn get_index<Q: ?Sized>(&self, key: &Q) -> Option<usize> 
172    where 
173        K: Borrow<Q>,
174        Q: std::hash::Hash + Eq,
175    {
176        self.index_set.table_get(key)
177    }
178
179    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool 
180    where 
181        K: Borrow<Q>,
182        Q: std::hash::Hash + Eq,
183    {
184        self.index_set.contains_key(key)
185    }
186
187    #[inline]
188    pub fn insert(&mut self, key: K, value: V) -> Option<InsertResult<K, V>> {
189        if let Some(idx) = self.index_set.table_get(&key) {
190            // K が Rc の場合を考慮して すべて差し替える
191            unsafe {
192                self.index_set.table_override(&key, &idx);
193            }
194            let old_value = Some(std::mem::replace(&mut self.values[idx], value));
195            let old_key = Some(std::mem::replace(&mut self.index_set.keys[idx], key.clone()));
196            Some(InsertResult {
197                old_value: old_value.unwrap(),
198                old_key:  old_key.unwrap(),
199            })
200        } else {
201            // New key, insert entry
202            let idx = self.values.len();
203            unsafe {
204                self.index_set.table_append(&key, &idx);
205            }
206            self.index_set.keys.push(key.clone());
207            self.values.push(value);
208            None
209        }
210    }
211
212    #[inline]
213    pub fn entry_mut<'a>(&'a mut self, key: K) -> EntryMut<'a, K, V, S> {
214        if let Some(idx) = self.index_set.table_get(&key) {
215            unsafe {
216                EntryMut::Occupied {
217                    key: key,
218                    value: self.values.get_unchecked_mut(idx),
219                    index: idx,
220                }
221            }
222        } else {
223            EntryMut::Vacant { key , map: self }
224        }
225    }
226
227    #[inline]
228    pub fn swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> 
229    where 
230        K: Borrow<Q>,
231        Q: std::hash::Hash + Eq,
232    {
233        if let Some(idx) = self.index_set.table_get(key) {
234            let last_idx = self.values.len() - 1;
235            if idx == last_idx {
236                // 最後の要素を削除する場合
237                unsafe {
238                    self.index_set.table_swap_remove(key);
239                }
240                self.index_set.keys.pop();
241                return Some(self.values.pop().unwrap());
242            } else {
243                let last_idx_key = self.index_set.keys[last_idx].clone();
244                unsafe {
245                    // keyとの整合性があるうちに削除予定のをtableから消す ここでhashesがswap_removeされる
246                    // last_idxの要素がswapで移動してくる
247                    self.index_set.table_swap_remove(key);
248                    // 移動させられた要素のtableを再登録
249                    // 登録されていた前のidxに対するkeyはまだ整合性が取れているので問題ない
250                    self.index_set.table_override(last_idx_key.borrow(), &idx);
251                }
252                // swap_remove ここで実際にtableのidxとvalues, keys, hashesの整合性が回復
253                let value = self.values.swap_remove(idx);
254                self.index_set.keys.swap_remove(idx);
255                Some(value)
256            }
257        } else {
258            None
259        }
260    }
261
262    #[inline]
263    pub fn from_kv_vec(k_vec: Vec<K>, v_vec: Vec<V>) -> Self
264    where
265        S: std::hash::BuildHasher + Default,
266    {
267        let hash_builder = S::default();
268        let mut map = IndexMap::with_hasher(hash_builder);
269        for (k, v) in k_vec.into_iter().zip(v_vec.into_iter()) {
270            let idx = map.values.len();
271            unsafe {
272                map.index_set.table_append(&k, &idx);
273            }
274            map.index_set.keys.push(k);
275            map.values.push(v);
276        }
277        map
278    }
279}
280
281pub struct IndexMapIter<'a, K, V, S> {
282    pub map: &'a IndexMap<K, V, S>,
283    pub index: usize,
284    pub end: usize, // exclusive
285}
286
287impl<'a, K, V, S> Iterator for IndexMapIter<'a, K, V, S>
288where
289    K: Eq + std::hash::Hash,
290    S: std::hash::BuildHasher,
291{
292    type Item = (&'a K, &'a V);
293
294    #[inline]
295    fn next(&mut self) -> Option<Self::Item> {
296        if self.index < self.end {
297            unsafe {
298                let i = self.index;
299                self.index += 1;
300                let k = self.map.index_set.keys.get_unchecked(i);
301                let v = self.map.values.get_unchecked(i);
302                Some((k, v))
303            }
304        } else {
305            None
306        }
307    }
308
309    #[inline]
310    fn size_hint(&self) -> (usize, Option<usize>) {
311        let remaining = self.end - self.index;
312        (remaining, Some(remaining))
313    }
314
315    #[inline]
316    fn nth(&mut self, n: usize) -> Option<Self::Item> {
317        // n 個スキップ
318        let new = self.index.saturating_add(n);
319        self.index = new.min(self.end);
320        self.next()
321    }
322}
323
324impl<'a, K, V, S> ExactSizeIterator for IndexMapIter<'a, K, V, S>
325where
326    K: Eq + std::hash::Hash,
327    S: std::hash::BuildHasher,
328{
329    #[inline]
330    fn len(&self) -> usize {
331        self.end - self.index
332    }
333}
334
335impl<'a, K, V, S> DoubleEndedIterator for IndexMapIter<'a, K, V, S>
336where
337    K: Eq + std::hash::Hash,
338    S: std::hash::BuildHasher,
339{
340    #[inline]
341    fn next_back(&mut self) -> Option<Self::Item> {
342        if self.index < self.end {
343            unsafe {
344                self.end -= 1;
345                let i = self.end;
346                let k = self.map.index_set.keys.get_unchecked(i);
347                let v = self.map.values.get_unchecked(i);
348                Some((k, v))
349            }
350        } else {
351            None
352        }
353    }
354}
355
356impl<'a, K, V, S> FusedIterator for IndexMapIter<'a, K, V, S>
357where
358    K: Eq + std::hash::Hash,
359    S: std::hash::BuildHasher,
360{}
361
362pub enum EntryMut<'a, K, V, S> {
363    Occupied { key: K, value: &'a mut V, index: usize },
364    Vacant { key: K , map: &'a mut IndexMap<K, V, S> },
365}
366
367impl<'a, K, V, S> EntryMut<'a, K, V, S>
368where 
369    K: Eq + std::hash::Hash + Clone,
370    S: std::hash::BuildHasher,
371{
372    #[inline]
373    pub fn is_occupied(&self) -> bool {
374        matches!(self, EntryMut::Occupied { .. })
375    }
376
377    #[inline]
378    pub fn or_insert_with<F>(self, value: F) -> &'a mut V
379    where
380        F: FnOnce() -> V,
381        K: Clone,
382    {
383        match self {
384            EntryMut::Occupied { value: v, .. } => v,
385            EntryMut::Vacant { key, map } => {
386                map.insert(key.clone(), value());
387                map.get_mut(&key).unwrap()
388            }
389        }
390    }
391}
392
393#[derive(Debug, PartialEq)]
394pub struct InsertResult<K, V> {
395    pub old_value: V,
396    pub old_key: K,
397}
398
399#[derive(Clone, Debug)]
400pub struct IndexSet<K, S = ahash::RandomState> {
401    keys: Vec<K>,
402    hashes: Vec<u64>,
403    table: HashTable<usize>,
404    hash_builder: S,
405}
406
407impl<K, S> IndexSet<K, S>
408where
409    K: Eq + std::hash::Hash + Clone,
410    S: std::hash::BuildHasher,
411{
412    pub fn with_hasher(hash_builder: S) -> Self {
413        IndexSet {
414            keys: Vec::new(),
415            hashes: Vec::new(),
416            table: HashTable::new(),
417            hash_builder,
418        }
419    }
420
421    pub fn new() -> Self
422    where
423        S: Default,
424    {
425        IndexSet {
426            keys: Vec::new(),
427            hashes: Vec::new(),
428            table: HashTable::new(),
429            hash_builder: S::default(),
430        }
431    }
432
433    pub fn with_capacity(capacity: usize) -> Self
434    where
435        S: Default,
436    {
437        IndexSet {
438            keys: Vec::with_capacity(capacity),
439            hashes: Vec::with_capacity(capacity),
440            table: HashTable::with_capacity(capacity),
441            hash_builder: S::default(),
442        }
443    }
444
445    pub fn with_hasher_capacity(hash_builder: S, capacity: usize) -> Self {
446        IndexSet {
447            keys: Vec::with_capacity(capacity),
448            hashes: Vec::with_capacity(capacity),
449            table: HashTable::with_capacity(capacity),
450            hash_builder,
451        }
452    }
453
454    pub fn capacity(&self) -> usize {
455        self.keys.capacity()
456    }
457
458    pub fn shrink_to_fit(&mut self) {
459        self.keys.shrink_to_fit();
460        self.hashes.shrink_to_fit();
461    }
462
463    /// hash util
464    #[inline]
465    fn hash_key<Q: ?Sized>(&self, key: &Q) -> u64 
466    where 
467        K: Borrow<Q>,
468        Q: std::hash::Hash + Eq,
469    {
470        let mut hasher = self.hash_builder.build_hasher();
471        key.hash(&mut hasher);
472        hasher.finish()
473    }
474
475    /// override
476    /// 完全な整合性が必要
477    /// keyに対するidxを更新し、更新したidxを返す
478    /// 存在しない場合はNone
479    #[inline]
480    unsafe fn table_override<Q: ?Sized>(&mut self, key: &Q, idx: &usize) -> Option<usize> 
481    where 
482        K: Borrow<Q>,
483        Q: std::hash::Hash + Eq,
484    {
485        let hash = self.hash_key(key);
486        match self.table.find_entry(hash, |&i| self.keys[i].borrow() == key) {
487            Ok(mut occ) => {
488                // idxの上書きだけ
489                *occ.get_mut() = *idx;
490                Some(*idx)
491            }
492            Err(_) => {
493                None
494            }
495        }
496    }
497
498    /// append
499    /// 完全な整合性が必要
500    /// hashesとtableを更新する
501    #[inline]
502    unsafe fn table_append<Q: ?Sized>(&mut self, key: &Q, idx: &usize) 
503    where 
504        K: Borrow<Q>,
505        Q: std::hash::Hash + Eq,
506    {
507        let hash = self.hash_key(key);
508        self.hashes.push(hash);
509        self.table.insert_unique(
510            hash,
511            *idx,
512            |&i| self.hashes[i]
513        );
514    }
515
516    /// get
517    /// とくに注意なし 不可変参照なので
518    #[inline]
519    fn table_get<Q: ?Sized>(&self, key: &Q) -> Option<usize> 
520    where 
521        K: Borrow<Q>,
522        Q: std::hash::Hash + Eq,
523    {
524        let hash = self.hash_key(key);
525        self.table.find(
526            hash, 
527            |&i| self.keys[i].borrow() == key
528        ).copied()
529    }
530
531    /// remove
532    /// 完全な整合性が必要
533    /// hashesはswap_removeされます
534    #[inline]
535    unsafe fn table_swap_remove<Q: ?Sized>(&mut self, key: &Q) -> Option<usize> 
536    where 
537        K: Borrow<Q>,
538        Q: std::hash::Hash + Eq,
539    {
540        let hash = self.hash_key(key);
541        if let Ok(entry) = self.table.find_entry(
542            hash,
543            |&i| self.keys[i].borrow() == key
544        ) {
545            let (odl_idx, _) = entry.remove();
546            self.hashes.swap_remove(odl_idx);
547            Some(odl_idx)
548        } else {
549            None
550        }
551    }
552
553    #[inline]
554    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool 
555    where 
556        K: Borrow<Q>,
557        Q: std::hash::Hash + Eq,
558    {
559        self.table_get(key).is_some()
560    }
561
562    #[inline]
563    pub fn len(&self) -> usize {
564        self.keys.len()
565    }
566
567    #[inline]
568    pub fn get_index<Q: ?Sized>(&self, key: &Q) -> Option<usize> 
569    where 
570        K: Borrow<Q>,
571        Q: std::hash::Hash + Eq,
572    {
573        self.table_get(key)
574    }
575
576    #[inline]
577    pub fn iter(&self) -> std::slice::Iter<'_, K> {
578        self.keys.iter()
579    }
580
581    #[inline]
582    pub fn keys(&self) -> &Vec<K> {
583        &self.keys
584    }
585
586    #[inline]
587    pub fn get_with_index(&self, index: usize) -> Option<&K> {
588        self.keys.get(index)
589    }
590}
591
592
593
594#[cfg(test)]
595mod tests {
596    use super::*;
597    use std::collections::HashMap;
598
599    // まずは比較しやすい型でテスト
600    type M = IndexMap<u64, i64>;
601
602    fn assert_internal_invariants(map: &M) {
603        // 長さが揃っていること
604        assert_eq!(map.values.len(), map.index_set.keys.len(), "values/keys len mismatch");
605        assert_eq!(map.values.len(), map.index_set.hashes.len(), "values/hashes len mismatch");
606
607        // table_get が返す idx が範囲内で、keys/values と一致すること
608        for (i, k) in map.index_set.keys.iter().enumerate() {
609            let idx = map.index_set.table_get(k).expect("table_get must find existing key");
610            assert_eq!(idx, i, "table idx mismatch for key");
611        }
612
613        // 逆方向も確認
614        // 重複キー禁止 + contains/get の整合
615        for i in 0..map.len() {
616            let k = &map.index_set.keys[i];
617            assert!(map.contains_key(k), "contains_key false for existing key");
618            let v = map.get(k).expect("get must return for existing key");
619            assert_eq!(*v, map.values[i], "get value mismatch");
620        }
621
622        // キー重複が無いこと
623        // O(n^2) だけどユニットテストならOK
624        for i in 0..map.index_set.keys.len() {
625            for j in (i + 1)..map.index_set.keys.len() {
626                assert!(map.index_set.keys[i] != map.index_set.keys[j], "duplicate keys detected");
627            }
628        }
629    }
630
631    fn assert_equals_oracle(map: &M, oracle: &HashMap<u64, i64>) {
632        assert_eq!(map.len(), oracle.len(), "len mismatch");
633
634        // 全キーが一致し、値も一致すること
635        for (k, v) in oracle.iter() {
636            let got = map.get(k).copied();
637            assert_eq!(got, Some(*v), "value mismatch for key={k}");
638        }
639
640        // map 側に余計なキーがないこと（oracle で確認）
641        for (k, v) in map.iter() {
642            assert_eq!(oracle.get(k).copied(), Some(*v), "extra/mismatch entry key={k}");
643        }
644    }
645
646    #[test]
647    fn basic_insert_get_overwrite() {
648        let mut m = M::new();
649
650        assert_eq!(m.insert(1, 10), None);
651        assert_eq!(m.insert(2, 20), None);
652        assert_eq!(m.get(&1).copied(), Some(10));
653        assert_eq!(m.get(&2).copied(), Some(20));
654
655        // overwrite
656        let old = m.insert(1, 99).unwrap();
657        assert_eq!(old.old_key, 1);
658        assert_eq!(old.old_value, 10);
659        assert_eq!(m.get(&1).copied(), Some(99));
660
661        assert_internal_invariants(&m);
662    }
663
664    #[test]
665    fn swap_remove_last_and_middle() {
666        let mut m = M::new();
667        for i in 0..10 {
668            m.insert(i, (i as i64) * 10);
669        }
670
671        // last remove
672        let v = m.swap_remove(&9);
673        assert_eq!(v, Some(90));
674        assert!(m.get(&9).is_none());
675
676        // middle remove
677        let v = m.swap_remove(&3);
678        assert_eq!(v, Some(30));
679        assert!(m.get(&3).is_none());
680
681        assert_internal_invariants(&m);
682    }
683
684    #[test]
685    fn entry_or_insert_with_works() {
686        let mut m = M::new();
687
688        let v = m.entry_mut(7).or_insert_with(|| 123);
689        assert_eq!(*v, 123);
690
691        // 2回目は既存参照が返る
692        let v2 = m.entry_mut(7).or_insert_with(|| 999);
693        assert_eq!(*v2, 123);
694
695        assert_internal_invariants(&m);
696    }
697
698    #[test]
699    fn compare_with_std_hashmap_small_scripted() {
700        let mut m = M::new();
701        let mut o = HashMap::<u64, i64>::new();
702
703        // 混ぜた操作を固定シナリオで
704        for i in 0..50u64 {
705            m.insert(i, i as i64);
706            o.insert(i, i as i64);
707        }
708
709        for i in 0..50u64 {
710            if i % 3 == 0 {
711                let a = m.swap_remove(&i);
712                let b = o.remove(&i);
713                assert_eq!(a, b);
714            }
715        }
716
717        for i in 0..50u64 {
718            if i % 5 == 0 {
719                m.insert(i, (i as i64) * 100);
720                o.insert(i, (i as i64) * 100);
721            }
722        }
723
724        assert_internal_invariants(&m);
725        assert_equals_oracle(&m, &o);
726    }
727
728    #[test]
729    fn randomized_ops_compare_with_oracle() {
730        use rand::{rngs::StdRng, Rng, SeedableRng};
731
732        let mut rng = StdRng::seed_from_u64(0xC0FFEE);
733        let mut m = M::new();
734        let mut o = HashMap::<u64, i64>::new();
735
736        // ある程度衝突や削除を踏む
737        const STEPS: usize = 30_000;
738        const KEY_SPACE: u64 = 2_000;
739
740        for _ in 0..STEPS {
741            let op = rng.gen_range(0..100);
742            let k = rng.gen_range(0..KEY_SPACE);
743            match op {
744                // insert (多め)
745                0..=59 => {
746                    let v = rng.gen_range(-1_000_000..=1_000_000);
747                    let a = m.insert(k, v);
748                    let b = o.insert(k, v);
749
750                    match (a, b) {
751                        (None, None) => {}
752                        (Some(ir), Some(old)) => {
753                            assert_eq!(ir.old_key, k);
754                            assert_eq!(ir.old_value, old);
755                        }
756                        _ => panic!("insert mismatch"),
757                    }
758                }
759                // swap_remove
760                60..=79 => {
761                    let a = m.swap_remove(&k);
762                    let b = o.remove(&k);
763                    assert_eq!(a, b);
764                }
765                // get
766                80..=94 => {
767                    let a = m.get(&k).copied();
768                    let b = o.get(&k).copied();
769                    assert_eq!(a, b);
770                }
771                // contains
772                _ => {
773                    let a = m.contains_key(&k);
774                    let b = o.contains_key(&k);
775                    assert_eq!(a, b);
776                }
777            }
778
779            // たまに内部整合をチェック（重いので間引く）
780            if rng.gen_ratio(1, 200) {
781                assert_internal_invariants(&m);
782                assert_equals_oracle(&m, &o);
783            }
784        }
785
786        // 最後に必ず一致
787        assert_internal_invariants(&m);
788        assert_equals_oracle(&m, &o);
789    }
790
791    #[test]
792    fn empty_map_basics() {
793        let m = M::new();
794
795        assert_eq!(m.len(), 0);
796        assert!(m.get(&123).is_none());
797        assert!(!m.contains_key(&123));
798        // 空でも長さ整合は成立
799        assert_eq!(m.values.len(), 0);
800        assert_eq!(m.index_set.keys.len(), 0);
801        assert_eq!(m.index_set.hashes.len(), 0);
802    }
803
804    #[test]
805    fn swap_remove_single_element_roundtrip() {
806        let mut m = M::new();
807        m.insert(42, -7);
808        assert_internal_invariants(&m);
809
810        let v = m.swap_remove(&42);
811        assert_eq!(v, Some(-7));
812        assert_eq!(m.len(), 0);
813        assert!(m.get(&42).is_none());
814        assert!(!m.contains_key(&42));
815
816        assert_internal_invariants(&m);
817    }
818
819    #[test]
820    fn remove_then_reinsert_same_key() {
821        let mut m = M::new();
822
823        m.insert(1, 10);
824        m.insert(2, 20);
825        m.insert(3, 30);
826        assert_internal_invariants(&m);
827
828        assert_eq!(m.swap_remove(&2), Some(20));
829        assert!(m.get(&2).is_none());
830        assert_internal_invariants(&m);
831
832        // 同じキーを再挿入しても table が壊れないこと
833        assert_eq!(m.insert(2, 200), None);
834        assert_eq!(m.get(&2).copied(), Some(200));
835        assert_internal_invariants(&m);
836    }
837
838    #[test]
839    fn from_kv_vec_builds_valid_map() {
840        let keys = vec![1u64, 2u64, 3u64, 10u64];
841        let values = vec![10i64, 20i64, 30i64, 100i64];
842
843        let m = M::from_kv_vec(keys.clone(), values.clone());
844        assert_eq!(m.len(), 4);
845
846        // 順序と内容が一致
847        assert_eq!(m.index_set.keys, keys);
848        assert_eq!(m.values, values);
849
850        assert_internal_invariants(&m);
851    }
852
853    #[test]
854    fn iter_order_matches_internal_storage_even_after_removes() {
855        let mut m = M::new();
856        for i in 0..8u64 {
857            m.insert(i, (i as i64) + 100);
858        }
859        assert_internal_invariants(&m);
860
861        // いくつか消して、内部順序が変わっても iter が keys/values と整合すること
862        assert_eq!(m.swap_remove(&0), Some(100));
863        assert_eq!(m.swap_remove(&5), Some(105));
864        assert_internal_invariants(&m);
865
866        let collected: Vec<(u64, i64)> = m.iter().map(|(k, v)| (*k, *v)).collect();
867        let expected: Vec<(u64, i64)> = m.index_set.keys.iter().copied().zip(m.values.iter().copied()).collect();
868        assert_eq!(collected, expected);
869    }
870
871    #[test]
872    fn num_23257_issue() {
873        const ITER_NUM: u64 = 223259;
874        let mut map: IndexMap<u64, Vec<u64>> = IndexMap::new();
875        for i in 0..ITER_NUM {
876            map.entry_mut(0).or_insert_with(Vec::new).push(i);
877        }
878        assert_eq!(map.len(), 1);
879        assert_eq!(map.get(&0).unwrap().len() as u64, ITER_NUM);
880    }
881}
tf_idf_vectorizer/utils/datastruct/map/mod.rs

tf_idf_vectorizer/utils/datastruct/map/
mod.rs
