tf_idf_vectorizer/utils/datastruct/map/
mod.rs

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

tf_idf_vectorizer/utils/datastruct/map/
mod.rs
