yimi_rutool/algorithms/bitmap.rs
1//! BitMap utilities for efficient bit manipulation
2//!
3//! This module provides efficient bit manipulation utilities used by bloom filters
4//! and other algorithms that need to manage bit arrays.
5
6use std::ops::Index;
7
8/// A memory-efficient bitmap implementation
9///
10/// Provides efficient bit manipulation operations for use in bloom filters
11/// and other data structures that require bit-level operations.
12///
13/// # Examples
14///
15/// ```
16/// use yimi_rutool::algorithms::BitMap;
17///
18/// let mut bitmap = BitMap::new(100);
19/// bitmap.set(42, true);
20/// assert!(bitmap.get(42));
21/// assert_eq!(bitmap.count_ones(), 1);
22/// ```
23#[derive(Debug, Clone)]
24pub struct BitMap {
25 data: Vec<u64>,
26 size: usize,
27}
28
29impl BitMap {
30 /// Create a new bitmap with the specified number of bits
31 ///
32 /// # Arguments
33 ///
34 /// * `size` - Number of bits in the bitmap
35 ///
36 /// # Examples
37 ///
38 /// ```
39 /// use yimi_rutool::algorithms::BitMap;
40 ///
41 /// let bitmap = BitMap::new(1000);
42 /// assert_eq!(bitmap.len(), 1000);
43 /// ```
44 pub fn new(size: usize) -> Self {
45 let data_size = (size + 63) / 64; // Round up to nearest 64-bit boundary
46 BitMap {
47 data: vec![0u64; data_size],
48 size,
49 }
50 }
51
52 /// Create a bitmap filled with ones
53 ///
54 /// # Arguments
55 ///
56 /// * `size` - Number of bits in the bitmap
57 ///
58 /// # Examples
59 ///
60 /// ```
61 /// use yimi_rutool::algorithms::BitMap;
62 ///
63 /// let bitmap = BitMap::filled(8);
64 /// assert_eq!(bitmap.count_ones(), 8);
65 /// ```
66 pub fn filled(size: usize) -> Self {
67 let mut bitmap = Self::new(size);
68 bitmap.fill(true);
69 bitmap
70 }
71
72 /// Get the value of a bit at the specified index
73 ///
74 /// # Arguments
75 ///
76 /// * `index` - Bit index (0-based)
77 ///
78 /// # Panics
79 ///
80 /// Panics if index is out of bounds
81 ///
82 /// # Examples
83 ///
84 /// ```
85 /// use yimi_rutool::algorithms::BitMap;
86 ///
87 /// let mut bitmap = BitMap::new(100);
88 /// bitmap.set(42, true);
89 /// assert!(bitmap.get(42));
90 /// assert!(!bitmap.get(43));
91 /// ```
92 pub fn get(&self, index: usize) -> bool {
93 assert!(
94 index < self.size,
95 "Index {} out of bounds for size {}",
96 index,
97 self.size
98 );
99
100 let word_index = index / 64;
101 let bit_index = index % 64;
102 (self.data[word_index] & (1u64 << bit_index)) != 0
103 }
104
105 /// Set the value of a bit at the specified index
106 ///
107 /// # Arguments
108 ///
109 /// * `index` - Bit index (0-based)
110 /// * `value` - Value to set (true for 1, false for 0)
111 ///
112 /// # Panics
113 ///
114 /// Panics if index is out of bounds
115 ///
116 /// # Examples
117 ///
118 /// ```
119 /// use yimi_rutool::algorithms::BitMap;
120 ///
121 /// let mut bitmap = BitMap::new(100);
122 /// bitmap.set(42, true);
123 /// assert!(bitmap.get(42));
124 ///
125 /// bitmap.set(42, false);
126 /// assert!(!bitmap.get(42));
127 /// ```
128 pub fn set(&mut self, index: usize, value: bool) {
129 assert!(
130 index < self.size,
131 "Index {} out of bounds for size {}",
132 index,
133 self.size
134 );
135
136 let word_index = index / 64;
137 let bit_index = index % 64;
138
139 if value {
140 self.data[word_index] |= 1u64 << bit_index;
141 } else {
142 self.data[word_index] &= !(1u64 << bit_index);
143 }
144 }
145
146 /// Toggle the bit at the specified index
147 ///
148 /// # Arguments
149 ///
150 /// * `index` - Bit index (0-based)
151 ///
152 /// # Examples
153 ///
154 /// ```
155 /// use yimi_rutool::algorithms::BitMap;
156 ///
157 /// let mut bitmap = BitMap::new(100);
158 /// bitmap.toggle(42);
159 /// assert!(bitmap.get(42));
160 /// bitmap.toggle(42);
161 /// assert!(!bitmap.get(42));
162 /// ```
163 pub fn toggle(&mut self, index: usize) {
164 assert!(
165 index < self.size,
166 "Index {} out of bounds for size {}",
167 index,
168 self.size
169 );
170
171 let word_index = index / 64;
172 let bit_index = index % 64;
173 self.data[word_index] ^= 1u64 << bit_index;
174 }
175
176 /// Fill all bits with the specified value
177 ///
178 /// # Arguments
179 ///
180 /// * `value` - Value to set all bits to
181 ///
182 /// # Examples
183 ///
184 /// ```
185 /// use yimi_rutool::algorithms::BitMap;
186 ///
187 /// let mut bitmap = BitMap::new(100);
188 /// bitmap.fill(true);
189 /// assert_eq!(bitmap.count_ones(), 100);
190 ///
191 /// bitmap.fill(false);
192 /// assert_eq!(bitmap.count_ones(), 0);
193 /// ```
194 pub fn fill(&mut self, value: bool) {
195 let fill_value = if value { u64::MAX } else { 0 };
196 self.data.fill(fill_value);
197
198 // Handle partial last word
199 if value && self.size % 64 != 0 {
200 let last_word_bits = self.size % 64;
201 let mask = (1u64 << last_word_bits) - 1;
202 if let Some(last_word) = self.data.last_mut() {
203 *last_word = mask;
204 }
205 }
206 }
207
208 /// Clear all bits (set to 0)
209 ///
210 /// # Examples
211 ///
212 /// ```
213 /// use yimi_rutool::algorithms::BitMap;
214 ///
215 /// let mut bitmap = BitMap::filled(100);
216 /// bitmap.clear();
217 /// assert_eq!(bitmap.count_ones(), 0);
218 /// ```
219 pub fn clear(&mut self) {
220 self.fill(false);
221 }
222
223 /// Count the number of bits set to 1
224 ///
225 /// # Examples
226 ///
227 /// ```
228 /// use yimi_rutool::algorithms::BitMap;
229 ///
230 /// let mut bitmap = BitMap::new(100);
231 /// bitmap.set(10, true);
232 /// bitmap.set(20, true);
233 /// bitmap.set(30, true);
234 /// assert_eq!(bitmap.count_ones(), 3);
235 /// ```
236 pub fn count_ones(&self) -> usize {
237 let mut count = 0;
238
239 // Count full words
240 for &word in &self.data[..self.data.len().saturating_sub(1)] {
241 count += word.count_ones() as usize;
242 }
243
244 // Handle the last word (might be partial)
245 if let Some(&last_word) = self.data.last() {
246 let bits_in_last_word = if self.size % 64 == 0 {
247 64
248 } else {
249 self.size % 64
250 };
251 let mask = (1u64 << bits_in_last_word) - 1;
252 count += (last_word & mask).count_ones() as usize;
253 }
254
255 count
256 }
257
258 /// Count the number of bits set to 0
259 ///
260 /// # Examples
261 ///
262 /// ```
263 /// use yimi_rutool::algorithms::BitMap;
264 ///
265 /// let mut bitmap = BitMap::new(100);
266 /// bitmap.set(10, true);
267 /// assert_eq!(bitmap.count_zeros(), 99);
268 /// ```
269 pub fn count_zeros(&self) -> usize {
270 self.size - self.count_ones()
271 }
272
273 /// Get the number of bits in the bitmap
274 ///
275 /// # Examples
276 ///
277 /// ```
278 /// use yimi_rutool::algorithms::BitMap;
279 ///
280 /// let bitmap = BitMap::new(1000);
281 /// assert_eq!(bitmap.len(), 1000);
282 /// ```
283 pub fn len(&self) -> usize {
284 self.size
285 }
286
287 /// Check if the bitmap is empty (size 0)
288 ///
289 /// # Examples
290 ///
291 /// ```
292 /// use yimi_rutool::algorithms::BitMap;
293 ///
294 /// let empty_bitmap = BitMap::new(0);
295 /// assert!(empty_bitmap.is_empty());
296 ///
297 /// let bitmap = BitMap::new(100);
298 /// assert!(!bitmap.is_empty());
299 /// ```
300 pub fn is_empty(&self) -> bool {
301 self.size == 0
302 }
303
304 /// Check if all bits are set to 0
305 ///
306 /// # Examples
307 ///
308 /// ```
309 /// use yimi_rutool::algorithms::BitMap;
310 ///
311 /// let mut bitmap = BitMap::new(100);
312 /// assert!(bitmap.all_zeros());
313 ///
314 /// bitmap.set(50, true);
315 /// assert!(!bitmap.all_zeros());
316 /// ```
317 pub fn all_zeros(&self) -> bool {
318 self.count_ones() == 0
319 }
320
321 /// Check if all bits are set to 1
322 ///
323 /// # Examples
324 ///
325 /// ```
326 /// use yimi_rutool::algorithms::BitMap;
327 ///
328 /// let mut bitmap = BitMap::new(100);
329 /// assert!(!bitmap.all_ones());
330 ///
331 /// bitmap.fill(true);
332 /// assert!(bitmap.all_ones());
333 /// ```
334 pub fn all_ones(&self) -> bool {
335 self.count_ones() == self.size
336 }
337
338 /// Perform bitwise AND operation with another bitmap
339 ///
340 /// # Arguments
341 ///
342 /// * `other` - The other bitmap to AND with
343 ///
344 /// # Panics
345 ///
346 /// Panics if the bitmaps have different sizes
347 ///
348 /// # Examples
349 ///
350 /// ```
351 /// use yimi_rutool::algorithms::BitMap;
352 ///
353 /// let mut bitmap1 = BitMap::new(100);
354 /// let mut bitmap2 = BitMap::new(100);
355 ///
356 /// bitmap1.set(10, true);
357 /// bitmap1.set(20, true);
358 /// bitmap2.set(10, true);
359 /// bitmap2.set(30, true);
360 ///
361 /// bitmap1.and(&bitmap2);
362 /// assert!(bitmap1.get(10)); // Both had this bit set
363 /// assert!(!bitmap1.get(20)); // Only bitmap1 had this bit set
364 /// assert!(!bitmap1.get(30)); // Only bitmap2 had this bit set
365 /// ```
366 pub fn and(&mut self, other: &BitMap) {
367 assert_eq!(
368 self.size, other.size,
369 "BitMap sizes must match for AND operation"
370 );
371
372 for (a, &b) in self.data.iter_mut().zip(&other.data) {
373 *a &= b;
374 }
375 }
376
377 /// Perform bitwise OR operation with another bitmap
378 ///
379 /// # Arguments
380 ///
381 /// * `other` - The other bitmap to OR with
382 ///
383 /// # Panics
384 ///
385 /// Panics if the bitmaps have different sizes
386 ///
387 /// # Examples
388 ///
389 /// ```
390 /// use yimi_rutool::algorithms::BitMap;
391 ///
392 /// let mut bitmap1 = BitMap::new(100);
393 /// let mut bitmap2 = BitMap::new(100);
394 ///
395 /// bitmap1.set(10, true);
396 /// bitmap2.set(20, true);
397 ///
398 /// bitmap1.or(&bitmap2);
399 /// assert!(bitmap1.get(10)); // From bitmap1
400 /// assert!(bitmap1.get(20)); // From bitmap2
401 /// ```
402 pub fn or(&mut self, other: &BitMap) {
403 assert_eq!(
404 self.size, other.size,
405 "BitMap sizes must match for OR operation"
406 );
407
408 for (a, &b) in self.data.iter_mut().zip(&other.data) {
409 *a |= b;
410 }
411 }
412
413 /// Perform bitwise XOR operation with another bitmap
414 ///
415 /// # Arguments
416 ///
417 /// * `other` - The other bitmap to XOR with
418 ///
419 /// # Panics
420 ///
421 /// Panics if the bitmaps have different sizes
422 ///
423 /// # Examples
424 ///
425 /// ```
426 /// use yimi_rutool::algorithms::BitMap;
427 ///
428 /// let mut bitmap1 = BitMap::new(100);
429 /// let mut bitmap2 = BitMap::new(100);
430 ///
431 /// bitmap1.set(10, true);
432 /// bitmap1.set(20, true);
433 /// bitmap2.set(10, true);
434 /// bitmap2.set(30, true);
435 ///
436 /// bitmap1.xor(&bitmap2);
437 /// assert!(!bitmap1.get(10)); // Both had this bit set
438 /// assert!(bitmap1.get(20)); // Only bitmap1 had this bit set
439 /// assert!(bitmap1.get(30)); // Only bitmap2 had this bit set
440 /// ```
441 pub fn xor(&mut self, other: &BitMap) {
442 assert_eq!(
443 self.size, other.size,
444 "BitMap sizes must match for XOR operation"
445 );
446
447 for (a, &b) in self.data.iter_mut().zip(&other.data) {
448 *a ^= b;
449 }
450 }
451
452 /// Perform bitwise NOT operation (invert all bits)
453 ///
454 /// # Examples
455 ///
456 /// ```
457 /// use yimi_rutool::algorithms::BitMap;
458 ///
459 /// let mut bitmap = BitMap::new(100);
460 /// bitmap.set(10, true);
461 ///
462 /// bitmap.not();
463 /// assert!(!bitmap.get(10));
464 /// assert_eq!(bitmap.count_ones(), 99);
465 /// ```
466 pub fn not(&mut self) {
467 for word in &mut self.data {
468 *word = !*word;
469 }
470
471 // Clear any bits beyond our size in the last word
472 if self.size % 64 != 0 {
473 let last_word_bits = self.size % 64;
474 let mask = (1u64 << last_word_bits) - 1;
475 if let Some(last_word) = self.data.last_mut() {
476 *last_word &= mask;
477 }
478 }
479 }
480
481 /// Get an iterator over all set bit indices
482 ///
483 /// # Examples
484 ///
485 /// ```
486 /// use yimi_rutool::algorithms::BitMap;
487 ///
488 /// let mut bitmap = BitMap::new(100);
489 /// bitmap.set(10, true);
490 /// bitmap.set(20, true);
491 /// bitmap.set(30, true);
492 ///
493 /// let set_bits: Vec<usize> = bitmap.iter_ones().collect();
494 /// assert_eq!(set_bits, vec![10, 20, 30]);
495 /// ```
496 pub fn iter_ones(&self) -> impl Iterator<Item = usize> + '_ {
497 (0..self.size).filter(move |&i| self.get(i))
498 }
499
500 /// Get an iterator over all unset bit indices
501 ///
502 /// # Examples
503 ///
504 /// ```
505 /// use yimi_rutool::algorithms::BitMap;
506 ///
507 /// let mut bitmap = BitMap::new(5);
508 /// bitmap.set(1, true);
509 /// bitmap.set(3, true);
510 ///
511 /// let unset_bits: Vec<usize> = bitmap.iter_zeros().collect();
512 /// assert_eq!(unset_bits, vec![0, 2, 4]);
513 /// ```
514 pub fn iter_zeros(&self) -> impl Iterator<Item = usize> + '_ {
515 (0..self.size).filter(move |&i| !self.get(i))
516 }
517
518 /// Resize the bitmap to a new size
519 ///
520 /// If the new size is larger, new bits are set to false.
521 /// If the new size is smaller, excess bits are discarded.
522 ///
523 /// # Arguments
524 ///
525 /// * `new_size` - New size in bits
526 ///
527 /// # Examples
528 ///
529 /// ```
530 /// use yimi_rutool::algorithms::BitMap;
531 ///
532 /// let mut bitmap = BitMap::new(100);
533 /// bitmap.set(50, true);
534 ///
535 /// bitmap.resize(200);
536 /// assert_eq!(bitmap.len(), 200);
537 /// assert!(bitmap.get(50)); // Existing data preserved
538 ///
539 /// bitmap.resize(25);
540 /// assert_eq!(bitmap.len(), 25);
541 /// // bit 50 is now out of bounds
542 /// ```
543 pub fn resize(&mut self, new_size: usize) {
544 let new_data_size = (new_size + 63) / 64;
545
546 if new_data_size > self.data.len() {
547 // Growing: add new words filled with zeros
548 self.data.resize(new_data_size, 0);
549 } else if new_data_size < self.data.len() {
550 // Shrinking: remove excess words
551 self.data.truncate(new_data_size);
552 }
553
554 self.size = new_size;
555
556 // Clear any bits beyond our new size in the last word
557 if new_size % 64 != 0 {
558 let last_word_bits = new_size % 64;
559 let mask = (1u64 << last_word_bits) - 1;
560 if let Some(last_word) = self.data.last_mut() {
561 *last_word &= mask;
562 }
563 }
564 }
565}
566
567impl Index<usize> for BitMap {
568 type Output = bool;
569
570 fn index(&self, index: usize) -> &Self::Output {
571 // This is a bit tricky since we need to return a reference to a bool
572 // We'll use a static reference approach
573 if self.get(index) { &true } else { &false }
574 }
575}
576
577// Note: IndexMut is not implemented because we can't return a mutable reference
578// to a bit within a word. Use set() method instead.
579
580impl PartialEq for BitMap {
581 fn eq(&self, other: &Self) -> bool {
582 if self.size != other.size {
583 return false;
584 }
585
586 // Compare full words
587 for (a, b) in self.data.iter().zip(&other.data) {
588 if a != b {
589 return false;
590 }
591 }
592
593 true
594 }
595}
596
597impl Eq for BitMap {}
598
599#[cfg(test)]
600mod tests {
601 use super::*;
602
603 #[test]
604 fn test_bitmap_creation() {
605 let bitmap = BitMap::new(100);
606 assert_eq!(bitmap.len(), 100);
607 assert!(!bitmap.is_empty());
608 assert!(bitmap.all_zeros());
609 assert!(!bitmap.all_ones());
610 assert_eq!(bitmap.count_ones(), 0);
611 assert_eq!(bitmap.count_zeros(), 100);
612 }
613
614 #[test]
615 fn test_bitmap_filled() {
616 let bitmap = BitMap::filled(100);
617 assert_eq!(bitmap.len(), 100);
618 assert!(bitmap.all_ones());
619 assert!(!bitmap.all_zeros());
620 assert_eq!(bitmap.count_ones(), 100);
621 assert_eq!(bitmap.count_zeros(), 0);
622 }
623
624 #[test]
625 fn test_bitmap_empty() {
626 let bitmap = BitMap::new(0);
627 assert_eq!(bitmap.len(), 0);
628 assert!(bitmap.is_empty());
629 assert!(bitmap.all_zeros());
630 assert!(bitmap.all_ones()); // Vacuously true for empty set
631 }
632
633 #[test]
634 fn test_set_and_get() {
635 let mut bitmap = BitMap::new(100);
636
637 bitmap.set(42, true);
638 assert!(bitmap.get(42));
639 assert!(!bitmap.get(41));
640 assert!(!bitmap.get(43));
641
642 bitmap.set(42, false);
643 assert!(!bitmap.get(42));
644 }
645
646 #[test]
647 fn test_toggle() {
648 let mut bitmap = BitMap::new(100);
649
650 bitmap.toggle(42);
651 assert!(bitmap.get(42));
652
653 bitmap.toggle(42);
654 assert!(!bitmap.get(42));
655 }
656
657 #[test]
658 fn test_fill_and_clear() {
659 let mut bitmap = BitMap::new(100);
660
661 bitmap.fill(true);
662 assert!(bitmap.all_ones());
663 assert_eq!(bitmap.count_ones(), 100);
664
665 bitmap.clear();
666 assert!(bitmap.all_zeros());
667 assert_eq!(bitmap.count_ones(), 0);
668 }
669
670 #[test]
671 fn test_count_operations() {
672 let mut bitmap = BitMap::new(100);
673
674 bitmap.set(10, true);
675 bitmap.set(20, true);
676 bitmap.set(30, true);
677
678 assert_eq!(bitmap.count_ones(), 3);
679 assert_eq!(bitmap.count_zeros(), 97);
680 }
681
682 #[test]
683 fn test_bitwise_operations() {
684 let mut bitmap1 = BitMap::new(100);
685 let mut bitmap2 = BitMap::new(100);
686
687 bitmap1.set(10, true);
688 bitmap1.set(20, true);
689 bitmap2.set(10, true);
690 bitmap2.set(30, true);
691
692 // Test AND
693 let mut and_bitmap = bitmap1.clone();
694 and_bitmap.and(&bitmap2);
695 assert!(and_bitmap.get(10)); // Both had this
696 assert!(!and_bitmap.get(20)); // Only bitmap1 had this
697 assert!(!and_bitmap.get(30)); // Only bitmap2 had this
698
699 // Test OR
700 let mut or_bitmap = bitmap1.clone();
701 or_bitmap.or(&bitmap2);
702 assert!(or_bitmap.get(10)); // Both had this
703 assert!(or_bitmap.get(20)); // bitmap1 had this
704 assert!(or_bitmap.get(30)); // bitmap2 had this
705
706 // Test XOR
707 let mut xor_bitmap = bitmap1.clone();
708 xor_bitmap.xor(&bitmap2);
709 assert!(!xor_bitmap.get(10)); // Both had this (cancel out)
710 assert!(xor_bitmap.get(20)); // Only bitmap1 had this
711 assert!(xor_bitmap.get(30)); // Only bitmap2 had this
712 }
713
714 #[test]
715 fn test_not_operation() {
716 let mut bitmap = BitMap::new(5);
717 bitmap.set(1, true);
718 bitmap.set(3, true);
719
720 bitmap.not();
721 assert!(bitmap.get(0));
722 assert!(!bitmap.get(1));
723 assert!(bitmap.get(2));
724 assert!(!bitmap.get(3));
725 assert!(bitmap.get(4));
726 }
727
728 #[test]
729 fn test_iterators() {
730 let mut bitmap = BitMap::new(10);
731 bitmap.set(1, true);
732 bitmap.set(3, true);
733 bitmap.set(7, true);
734
735 let ones: Vec<usize> = bitmap.iter_ones().collect();
736 assert_eq!(ones, vec![1, 3, 7]);
737
738 let zeros: Vec<usize> = bitmap.iter_zeros().collect();
739 assert_eq!(zeros, vec![0, 2, 4, 5, 6, 8, 9]);
740 }
741
742 #[test]
743 fn test_resize() {
744 let mut bitmap = BitMap::new(10);
745 bitmap.set(5, true);
746 bitmap.set(9, true);
747
748 // Grow
749 bitmap.resize(20);
750 assert_eq!(bitmap.len(), 20);
751 assert!(bitmap.get(5)); // Preserved
752 assert!(bitmap.get(9)); // Preserved
753 assert!(!bitmap.get(15)); // New bits are false
754
755 // Shrink
756 bitmap.resize(8);
757 assert_eq!(bitmap.len(), 8);
758 assert!(bitmap.get(5)); // Still preserved
759 // bitmap.get(9) would panic now (out of bounds)
760 }
761
762 #[test]
763 fn test_equality() {
764 let mut bitmap1 = BitMap::new(100);
765 let mut bitmap2 = BitMap::new(100);
766
767 assert_eq!(bitmap1, bitmap2);
768
769 bitmap1.set(42, true);
770 assert_ne!(bitmap1, bitmap2);
771
772 bitmap2.set(42, true);
773 assert_eq!(bitmap1, bitmap2);
774 }
775
776 #[test]
777 fn test_edge_cases() {
778 // Test bitmap sizes that aren't multiples of 64
779 let mut bitmap = BitMap::new(65);
780 bitmap.set(64, true);
781 assert!(bitmap.get(64));
782 assert_eq!(bitmap.count_ones(), 1);
783
784 // Test large indices
785 let mut large_bitmap = BitMap::new(10000);
786 large_bitmap.set(9999, true);
787 assert!(large_bitmap.get(9999));
788 }
789
790 #[test]
791 #[should_panic(expected = "Index 100 out of bounds for size 100")]
792 fn test_out_of_bounds_get() {
793 let bitmap = BitMap::new(100);
794 bitmap.get(100);
795 }
796
797 #[test]
798 #[should_panic(expected = "Index 100 out of bounds for size 100")]
799 fn test_out_of_bounds_set() {
800 let mut bitmap = BitMap::new(100);
801 bitmap.set(100, true);
802 }
803
804 #[test]
805 #[should_panic(expected = "BitMap sizes must match for AND operation")]
806 fn test_mismatched_sizes_and() {
807 let mut bitmap1 = BitMap::new(100);
808 let bitmap2 = BitMap::new(200);
809 bitmap1.and(&bitmap2);
810 }
811}