ankit_engine/progress.rs
1//! Progress management and card state operations.
2//!
3//! This module provides workflows for managing card progress, including
4//! resetting progress, tagging cards by performance, and bulk tag operations.
5
6use std::collections::HashSet;
7
8use crate::Result;
9use ankit::AnkiClient;
10use serde::Serialize;
11
12/// Report from resetting deck progress.
13#[derive(Debug, Clone, Default, Serialize)]
14pub struct ResetReport {
15 /// Number of cards reset to new state.
16 pub cards_reset: usize,
17 /// Deck that was reset.
18 pub deck: String,
19}
20
21/// Criteria for categorizing card performance.
22#[derive(Debug, Clone)]
23pub struct PerformanceCriteria {
24 /// Ease factor threshold for struggling (below this is struggling).
25 pub struggling_ease: i64,
26 /// Lapse count threshold for struggling (above this is struggling).
27 pub struggling_lapses: i64,
28 /// Ease factor threshold for mastered (above this is mastered).
29 pub mastered_ease: i64,
30 /// Minimum reps required for mastered status.
31 pub mastered_min_reps: i64,
32}
33
34impl Default for PerformanceCriteria {
35 fn default() -> Self {
36 Self {
37 struggling_ease: 2100, // Below 210%
38 struggling_lapses: 3, // More than 3 lapses
39 mastered_ease: 2500, // Above 250%
40 mastered_min_reps: 5, // At least 5 reviews
41 }
42 }
43}
44
45/// Report from tagging cards by performance.
46#[derive(Debug, Clone, Default, Serialize)]
47pub struct TagReport {
48 /// Number of notes tagged as struggling.
49 pub struggling_count: usize,
50 /// Number of notes tagged as mastered.
51 pub mastered_count: usize,
52 /// Tag used for struggling cards.
53 pub struggling_tag: String,
54 /// Tag used for mastered cards.
55 pub mastered_tag: String,
56}
57
58/// Criteria for suspending cards.
59#[derive(Debug, Clone)]
60pub struct SuspendCriteria {
61 /// Maximum ease factor (cards with ease below this may be suspended).
62 pub max_ease: i64,
63 /// Minimum lapse count (cards with lapses above this may be suspended).
64 pub min_lapses: i64,
65 /// Whether both conditions must be met (AND) or just one (OR).
66 pub require_both: bool,
67}
68
69impl Default for SuspendCriteria {
70 fn default() -> Self {
71 Self {
72 max_ease: 1800, // Below 180%
73 min_lapses: 5, // More than 5 lapses
74 require_both: true, // Both conditions must be met
75 }
76 }
77}
78
79/// Report from suspending cards by criteria.
80#[derive(Debug, Clone, Default, Serialize)]
81pub struct SuspendReport {
82 /// Number of cards suspended.
83 pub cards_suspended: usize,
84 /// Card IDs that were suspended.
85 pub suspended_ids: Vec<i64>,
86}
87
88/// Comprehensive health report for a deck.
89#[derive(Debug, Clone, Default, Serialize)]
90pub struct HealthReport {
91 /// Deck name.
92 pub deck: String,
93 /// Total number of cards.
94 pub total_cards: usize,
95 /// Number of new cards.
96 pub new_cards: usize,
97 /// Number of learning cards.
98 pub learning_cards: usize,
99 /// Number of review cards.
100 pub review_cards: usize,
101 /// Number of suspended cards.
102 pub suspended_cards: usize,
103 /// Number of buried cards.
104 pub buried_cards: usize,
105 /// Average ease factor (percentage * 10).
106 pub avg_ease: i64,
107 /// Average interval in days.
108 pub avg_interval: i64,
109 /// Number of leech cards (high lapses).
110 pub leech_count: usize,
111 /// Total lapses across all cards.
112 pub total_lapses: i64,
113 /// Total reviews across all cards.
114 pub total_reps: i64,
115}
116
117/// Tag operation to perform.
118#[derive(Debug, Clone)]
119pub enum TagOperation {
120 /// Add tags to notes.
121 Add(String),
122 /// Remove tags from notes.
123 Remove(String),
124 /// Replace one tag with another.
125 Replace { old: String, new: String },
126}
127
128/// Report from bulk tag operation.
129#[derive(Debug, Clone, Default, Serialize)]
130pub struct BulkTagReport {
131 /// Number of notes affected.
132 pub notes_affected: usize,
133 /// Operation performed.
134 pub operation: String,
135}
136
137/// Criteria for smart suspension based on content similarity.
138#[derive(Debug, Clone)]
139pub struct SimilarityCriteria {
140 /// Similarity threshold (0.0 - 1.0). Cards with similarity >= this are grouped.
141 pub threshold: f64,
142 /// Field to compare for similarity.
143 pub field: String,
144 /// Strategy for which card to keep in each similar group.
145 pub keep_strategy: KeepStrategy,
146 /// If true, don't actually suspend - just report what would be suspended.
147 pub dry_run: bool,
148}
149
150impl Default for SimilarityCriteria {
151 fn default() -> Self {
152 Self {
153 threshold: 0.85,
154 field: "Front".to_string(),
155 keep_strategy: KeepStrategy::MostMature,
156 dry_run: false,
157 }
158 }
159}
160
161/// Strategy for which card to keep when suspending similar cards.
162#[derive(Debug, Clone, Copy, Default)]
163pub enum KeepStrategy {
164 /// Keep the card with the highest interval (most mature).
165 #[default]
166 MostMature,
167 /// Keep the card with the lowest interval (least mature).
168 LeastMature,
169 /// Keep the card with the highest ease factor.
170 HighestEase,
171 /// Keep the card with the most reviews.
172 MostReviewed,
173}
174
175/// A group of similar cards.
176#[derive(Debug, Clone, Serialize)]
177pub struct SimilarGroup {
178 /// Card ID of the card to keep.
179 pub keep: i64,
180 /// Card IDs of cards to suspend.
181 pub suspend: Vec<i64>,
182 /// The field value these cards share (from the kept card).
183 pub field_value: String,
184 /// Similarity score within the group (minimum pairwise).
185 pub min_similarity: f64,
186}
187
188/// Report from smart suspension.
189#[derive(Debug, Clone, Default, Serialize)]
190pub struct SmartSuspendReport {
191 /// Number of cards analyzed.
192 pub cards_analyzed: usize,
193 /// Number of similar groups found.
194 pub groups_found: usize,
195 /// Number of cards suspended.
196 pub cards_suspended: usize,
197 /// Number of cards kept (one per group).
198 pub cards_kept: usize,
199 /// Details of each similar group.
200 pub groups: Vec<SimilarGroup>,
201 /// Whether this was a dry run.
202 pub dry_run: bool,
203}
204
205/// Progress management workflow engine.
206#[derive(Debug)]
207pub struct ProgressEngine<'a> {
208 client: &'a AnkiClient,
209}
210
211impl<'a> ProgressEngine<'a> {
212 pub(crate) fn new(client: &'a AnkiClient) -> Self {
213 Self { client }
214 }
215
216 /// Reset all cards in a deck to new state.
217 ///
218 /// This clears all learning progress for the deck.
219 ///
220 /// # Arguments
221 ///
222 /// * `deck` - Name of the deck to reset
223 ///
224 /// # Example
225 ///
226 /// ```no_run
227 /// # use ankit_engine::Engine;
228 /// # async fn example() -> ankit_engine::Result<()> {
229 /// let engine = Engine::new();
230 /// let report = engine.progress().reset_deck("Test Deck").await?;
231 /// println!("Reset {} cards", report.cards_reset);
232 /// # Ok(())
233 /// # }
234 /// ```
235 pub async fn reset_deck(&self, deck: &str) -> Result<ResetReport> {
236 let query = format!("deck:\"{}\"", deck);
237 let card_ids = self.client.cards().find(&query).await?;
238
239 if !card_ids.is_empty() {
240 self.client.cards().forget(&card_ids).await?;
241 }
242
243 Ok(ResetReport {
244 cards_reset: card_ids.len(),
245 deck: deck.to_string(),
246 })
247 }
248
249 /// Tag cards based on their performance.
250 ///
251 /// Cards are categorized as "struggling" or "mastered" based on
252 /// ease factor, lapse count, and review count.
253 ///
254 /// # Arguments
255 ///
256 /// * `query` - Anki search query to filter cards
257 /// * `criteria` - Criteria for categorization
258 /// * `struggling_tag` - Tag to apply to struggling cards
259 /// * `mastered_tag` - Tag to apply to mastered cards
260 ///
261 /// # Example
262 ///
263 /// ```no_run
264 /// # use ankit_engine::Engine;
265 /// # use ankit_engine::progress::PerformanceCriteria;
266 /// # async fn example() -> ankit_engine::Result<()> {
267 /// let engine = Engine::new();
268 /// let report = engine.progress()
269 /// .tag_by_performance(
270 /// "deck:Japanese",
271 /// PerformanceCriteria::default(),
272 /// "struggling",
273 /// "mastered"
274 /// )
275 /// .await?;
276 /// println!("{} struggling, {} mastered", report.struggling_count, report.mastered_count);
277 /// # Ok(())
278 /// # }
279 /// ```
280 pub async fn tag_by_performance(
281 &self,
282 query: &str,
283 criteria: PerformanceCriteria,
284 struggling_tag: &str,
285 mastered_tag: &str,
286 ) -> Result<TagReport> {
287 let card_ids = self.client.cards().find(query).await?;
288
289 if card_ids.is_empty() {
290 return Ok(TagReport {
291 struggling_tag: struggling_tag.to_string(),
292 mastered_tag: mastered_tag.to_string(),
293 ..Default::default()
294 });
295 }
296
297 let cards = self.client.cards().info(&card_ids).await?;
298
299 let mut struggling_notes = HashSet::new();
300 let mut mastered_notes = HashSet::new();
301
302 for card in cards {
303 let is_struggling = card.ease_factor > 0
304 && (card.ease_factor < criteria.struggling_ease
305 || card.lapses > criteria.struggling_lapses);
306
307 let is_mastered = card.ease_factor >= criteria.mastered_ease
308 && card.reps >= criteria.mastered_min_reps;
309
310 if is_struggling {
311 struggling_notes.insert(card.note_id);
312 } else if is_mastered {
313 mastered_notes.insert(card.note_id);
314 }
315 }
316
317 // Apply tags
318 let struggling_ids: Vec<_> = struggling_notes.into_iter().collect();
319 let mastered_ids: Vec<_> = mastered_notes.into_iter().collect();
320
321 if !struggling_ids.is_empty() {
322 self.client
323 .notes()
324 .add_tags(&struggling_ids, struggling_tag)
325 .await?;
326 }
327
328 if !mastered_ids.is_empty() {
329 self.client
330 .notes()
331 .add_tags(&mastered_ids, mastered_tag)
332 .await?;
333 }
334
335 Ok(TagReport {
336 struggling_count: struggling_ids.len(),
337 mastered_count: mastered_ids.len(),
338 struggling_tag: struggling_tag.to_string(),
339 mastered_tag: mastered_tag.to_string(),
340 })
341 }
342
343 /// Suspend cards matching performance criteria.
344 ///
345 /// # Arguments
346 ///
347 /// * `query` - Anki search query to filter cards
348 /// * `criteria` - Criteria for suspension
349 ///
350 /// # Example
351 ///
352 /// ```no_run
353 /// # use ankit_engine::Engine;
354 /// # use ankit_engine::progress::SuspendCriteria;
355 /// # async fn example() -> ankit_engine::Result<()> {
356 /// let engine = Engine::new();
357 /// let report = engine.progress()
358 /// .suspend_by_criteria("deck:Japanese", SuspendCriteria::default())
359 /// .await?;
360 /// println!("Suspended {} cards", report.cards_suspended);
361 /// # Ok(())
362 /// # }
363 /// ```
364 pub async fn suspend_by_criteria(
365 &self,
366 query: &str,
367 criteria: SuspendCriteria,
368 ) -> Result<SuspendReport> {
369 let card_ids = self.client.cards().find(query).await?;
370
371 if card_ids.is_empty() {
372 return Ok(SuspendReport::default());
373 }
374
375 let cards = self.client.cards().info(&card_ids).await?;
376
377 let mut to_suspend = Vec::new();
378
379 for card in cards {
380 // Skip already suspended cards
381 if card.queue == -1 {
382 continue;
383 }
384
385 let low_ease = card.ease_factor > 0 && card.ease_factor < criteria.max_ease;
386 let high_lapses = card.lapses >= criteria.min_lapses;
387
388 let should_suspend = if criteria.require_both {
389 low_ease && high_lapses
390 } else {
391 low_ease || high_lapses
392 };
393
394 if should_suspend {
395 to_suspend.push(card.card_id);
396 }
397 }
398
399 if !to_suspend.is_empty() {
400 self.client.cards().suspend(&to_suspend).await?;
401 }
402
403 Ok(SuspendReport {
404 cards_suspended: to_suspend.len(),
405 suspended_ids: to_suspend,
406 })
407 }
408
409 /// Get comprehensive health report for a deck.
410 ///
411 /// # Arguments
412 ///
413 /// * `deck` - Deck name to analyze
414 ///
415 /// # Example
416 ///
417 /// ```no_run
418 /// # use ankit_engine::Engine;
419 /// # async fn example() -> ankit_engine::Result<()> {
420 /// let engine = Engine::new();
421 /// let report = engine.progress().deck_health("Japanese").await?;
422 /// println!("Total: {}, Suspended: {}, Leeches: {}",
423 /// report.total_cards, report.suspended_cards, report.leech_count);
424 /// # Ok(())
425 /// # }
426 /// ```
427 pub async fn deck_health(&self, deck: &str) -> Result<HealthReport> {
428 let query = format!("deck:\"{}\"", deck);
429 let card_ids = self.client.cards().find(&query).await?;
430
431 if card_ids.is_empty() {
432 return Ok(HealthReport {
433 deck: deck.to_string(),
434 ..Default::default()
435 });
436 }
437
438 let cards = self.client.cards().info(&card_ids).await?;
439
440 let mut report = HealthReport {
441 deck: deck.to_string(),
442 total_cards: cards.len(),
443 ..Default::default()
444 };
445
446 let mut total_ease: i64 = 0;
447 let mut ease_count: usize = 0;
448 let mut total_interval: i64 = 0;
449 let mut interval_count: usize = 0;
450
451 for card in &cards {
452 // Card type: 0=new, 1=learning, 2=review, 3=relearning
453 // Queue: -1=suspended, -2=sibling buried, -3=manually buried, 0=new, 1=learning, 2=review
454 match card.queue {
455 -1 => report.suspended_cards += 1,
456 -2 | -3 => report.buried_cards += 1,
457 0 => report.new_cards += 1,
458 1 | 3 => report.learning_cards += 1,
459 2 => report.review_cards += 1,
460 _ => {}
461 }
462
463 if card.ease_factor > 0 {
464 total_ease += card.ease_factor;
465 ease_count += 1;
466 }
467
468 if card.interval > 0 {
469 total_interval += card.interval;
470 interval_count += 1;
471 }
472
473 report.total_lapses += card.lapses;
474 report.total_reps += card.reps;
475
476 // Leech threshold: 8+ lapses (Anki's default)
477 if card.lapses >= 8 {
478 report.leech_count += 1;
479 }
480 }
481
482 if ease_count > 0 {
483 report.avg_ease = total_ease / ease_count as i64;
484 }
485
486 if interval_count > 0 {
487 report.avg_interval = total_interval / interval_count as i64;
488 }
489
490 Ok(report)
491 }
492
493 /// Perform bulk tag operation on notes matching a query.
494 ///
495 /// # Arguments
496 ///
497 /// * `query` - Anki search query to filter notes
498 /// * `operation` - Tag operation to perform
499 ///
500 /// # Example
501 ///
502 /// ```no_run
503 /// # use ankit_engine::Engine;
504 /// # use ankit_engine::progress::TagOperation;
505 /// # async fn example() -> ankit_engine::Result<()> {
506 /// let engine = Engine::new();
507 ///
508 /// // Add tags
509 /// let report = engine.progress()
510 /// .bulk_tag("deck:Japanese", TagOperation::Add("needs-review".to_string()))
511 /// .await?;
512 ///
513 /// // Remove tags
514 /// let report = engine.progress()
515 /// .bulk_tag("deck:Japanese", TagOperation::Remove("old-tag".to_string()))
516 /// .await?;
517 ///
518 /// // Replace tags
519 /// let report = engine.progress()
520 /// .bulk_tag("deck:Japanese", TagOperation::Replace {
521 /// old: "v1".to_string(),
522 /// new: "v2".to_string(),
523 /// })
524 /// .await?;
525 /// # Ok(())
526 /// # }
527 /// ```
528 pub async fn bulk_tag(&self, query: &str, operation: TagOperation) -> Result<BulkTagReport> {
529 let note_ids = self.client.notes().find(query).await?;
530
531 if note_ids.is_empty() {
532 return Ok(BulkTagReport {
533 operation: format!("{:?}", operation),
534 ..Default::default()
535 });
536 }
537
538 let op_description = match &operation {
539 TagOperation::Add(tags) => {
540 self.client.notes().add_tags(¬e_ids, tags).await?;
541 format!("Added '{}'", tags)
542 }
543 TagOperation::Remove(tags) => {
544 self.client.notes().remove_tags(¬e_ids, tags).await?;
545 format!("Removed '{}'", tags)
546 }
547 TagOperation::Replace { old, new } => {
548 // Replace on specific notes
549 self.client
550 .notes()
551 .replace_tags(¬e_ids, old, new)
552 .await?;
553 format!("Replaced '{}' with '{}'", old, new)
554 }
555 };
556
557 Ok(BulkTagReport {
558 notes_affected: note_ids.len(),
559 operation: op_description,
560 })
561 }
562
563 /// Suspend similar cards to reduce interference during learning.
564 ///
565 /// This workflow analyzes cards for content similarity and suspends
566 /// all but one card from each group of similar cards.
567 ///
568 /// # Arguments
569 ///
570 /// * `query` - Anki search query to filter cards
571 /// * `criteria` - Similarity criteria and options
572 ///
573 /// # Example
574 ///
575 /// ```no_run
576 /// # use ankit_engine::Engine;
577 /// # use ankit_engine::progress::{SimilarityCriteria, KeepStrategy};
578 /// # async fn example() -> ankit_engine::Result<()> {
579 /// let engine = Engine::new();
580 ///
581 /// // First do a dry run to see what would be suspended
582 /// let report = engine.progress()
583 /// .smart_suspend("deck:Japanese", SimilarityCriteria {
584 /// threshold: 0.85,
585 /// field: "Front".to_string(),
586 /// keep_strategy: KeepStrategy::MostMature,
587 /// dry_run: true,
588 /// })
589 /// .await?;
590 ///
591 /// println!("Would suspend {} cards in {} groups",
592 /// report.cards_suspended, report.groups_found);
593 ///
594 /// // Then actually suspend
595 /// let report = engine.progress()
596 /// .smart_suspend("deck:Japanese", SimilarityCriteria {
597 /// dry_run: false,
598 /// ..SimilarityCriteria::default()
599 /// })
600 /// .await?;
601 /// # Ok(())
602 /// # }
603 /// ```
604 pub async fn smart_suspend(
605 &self,
606 query: &str,
607 criteria: SimilarityCriteria,
608 ) -> Result<SmartSuspendReport> {
609 let card_ids = self.client.cards().find(query).await?;
610
611 if card_ids.is_empty() {
612 return Ok(SmartSuspendReport {
613 dry_run: criteria.dry_run,
614 ..Default::default()
615 });
616 }
617
618 let cards = self.client.cards().info(&card_ids).await?;
619
620 // Get note info for field values
621 let note_ids: Vec<i64> = cards.iter().map(|c| c.note_id).collect();
622 let unique_note_ids: Vec<i64> = note_ids
623 .iter()
624 .copied()
625 .collect::<HashSet<_>>()
626 .into_iter()
627 .collect();
628 let notes = self.client.notes().info(&unique_note_ids).await?;
629
630 // Build card -> field value mapping
631 let note_fields: std::collections::HashMap<i64, String> = notes
632 .into_iter()
633 .filter_map(|n| {
634 n.fields
635 .get(&criteria.field)
636 .map(|f| (n.note_id, f.value.trim().to_string()))
637 })
638 .collect();
639
640 // Build list of (card_id, note_id, field_value, interval, ease, reps) for comparison
641 let mut card_data: Vec<(i64, i64, String, i64, i64, i64)> = Vec::new();
642 for card in &cards {
643 // Skip already suspended cards
644 if card.queue == -1 {
645 continue;
646 }
647
648 if let Some(field_value) = note_fields.get(&card.note_id) {
649 if !field_value.is_empty() {
650 card_data.push((
651 card.card_id,
652 card.note_id,
653 field_value.clone(),
654 card.interval,
655 card.ease_factor,
656 card.reps,
657 ));
658 }
659 }
660 }
661
662 if card_data.len() < 2 {
663 return Ok(SmartSuspendReport {
664 cards_analyzed: card_data.len(),
665 dry_run: criteria.dry_run,
666 ..Default::default()
667 });
668 }
669
670 // Find similar groups using union-find
671 let n = card_data.len();
672 let mut parent: Vec<usize> = (0..n).collect();
673
674 fn find(parent: &mut [usize], i: usize) -> usize {
675 if parent[i] != i {
676 parent[i] = find(parent, parent[i]);
677 }
678 parent[i]
679 }
680
681 fn union(parent: &mut [usize], i: usize, j: usize) {
682 let pi = find(parent, i);
683 let pj = find(parent, j);
684 if pi != pj {
685 parent[pi] = pj;
686 }
687 }
688
689 // Compare all pairs and union similar cards
690 for i in 0..n {
691 for j in (i + 1)..n {
692 let sim = string_similarity(&card_data[i].2, &card_data[j].2);
693 if sim >= criteria.threshold {
694 union(&mut parent, i, j);
695 }
696 }
697 }
698
699 // Group cards by their root
700 let mut groups_map: std::collections::HashMap<usize, Vec<usize>> =
701 std::collections::HashMap::new();
702 for i in 0..n {
703 let root = find(&mut parent, i);
704 groups_map.entry(root).or_default().push(i);
705 }
706
707 // Process groups with more than one card
708 let mut report = SmartSuspendReport {
709 cards_analyzed: card_data.len(),
710 dry_run: criteria.dry_run,
711 ..Default::default()
712 };
713
714 let mut to_suspend: Vec<i64> = Vec::new();
715
716 for indices in groups_map.values() {
717 if indices.len() < 2 {
718 continue;
719 }
720
721 // Select which card to keep based on strategy
722 let keep_idx = match criteria.keep_strategy {
723 KeepStrategy::MostMature => {
724 *indices.iter().max_by_key(|&&i| card_data[i].3).unwrap()
725 }
726 KeepStrategy::LeastMature => {
727 *indices.iter().min_by_key(|&&i| card_data[i].3).unwrap()
728 }
729 KeepStrategy::HighestEase => {
730 *indices.iter().max_by_key(|&&i| card_data[i].4).unwrap()
731 }
732 KeepStrategy::MostReviewed => {
733 *indices.iter().max_by_key(|&&i| card_data[i].5).unwrap()
734 }
735 };
736
737 let suspend_ids: Vec<i64> = indices
738 .iter()
739 .filter(|&&i| i != keep_idx)
740 .map(|&i| card_data[i].0)
741 .collect();
742
743 // Calculate minimum similarity within group
744 let mut min_sim = 1.0f64;
745 for &i in indices {
746 for &j in indices {
747 if i < j {
748 let sim = string_similarity(&card_data[i].2, &card_data[j].2);
749 min_sim = min_sim.min(sim);
750 }
751 }
752 }
753
754 to_suspend.extend(&suspend_ids);
755
756 report.groups.push(SimilarGroup {
757 keep: card_data[keep_idx].0,
758 suspend: suspend_ids,
759 field_value: card_data[keep_idx].2.clone(),
760 min_similarity: min_sim,
761 });
762 }
763
764 report.groups_found = report.groups.len();
765 report.cards_suspended = to_suspend.len();
766 report.cards_kept = report.groups_found;
767
768 // Actually suspend if not a dry run
769 if !criteria.dry_run && !to_suspend.is_empty() {
770 self.client.cards().suspend(&to_suspend).await?;
771 }
772
773 Ok(report)
774 }
775}
776
777/// Calculate string similarity using normalized Levenshtein distance.
778fn string_similarity(a: &str, b: &str) -> f64 {
779 let a_lower = a.to_lowercase();
780 let b_lower = b.to_lowercase();
781
782 if a_lower == b_lower {
783 return 1.0;
784 }
785
786 if a_lower.is_empty() || b_lower.is_empty() {
787 return 0.0;
788 }
789
790 let distance = levenshtein_distance(&a_lower, &b_lower);
791 let max_len = a_lower.chars().count().max(b_lower.chars().count());
792
793 1.0 - (distance as f64 / max_len as f64)
794}
795
796/// Calculate the Levenshtein distance between two strings.
797fn levenshtein_distance(a: &str, b: &str) -> usize {
798 let a_chars: Vec<char> = a.chars().collect();
799 let b_chars: Vec<char> = b.chars().collect();
800
801 let m = a_chars.len();
802 let n = b_chars.len();
803
804 if m == 0 {
805 return n;
806 }
807 if n == 0 {
808 return m;
809 }
810
811 let mut prev: Vec<usize> = (0..=n).collect();
812 let mut curr = vec![0; n + 1];
813
814 for i in 1..=m {
815 curr[0] = i;
816
817 for j in 1..=n {
818 let cost = if a_chars[i - 1] == b_chars[j - 1] {
819 0
820 } else {
821 1
822 };
823
824 curr[j] = (prev[j] + 1).min(curr[j - 1] + 1).min(prev[j - 1] + cost);
825 }
826
827 std::mem::swap(&mut prev, &mut curr);
828 }
829
830 prev[n]
831}