Frequency Analysis — Letter Distribution

use std::collections::HashMap;

pub fn frequency(s: &str) -> HashMap<char, usize> {
    s.chars()
        .filter(|c| c.is_ascii_alphabetic())
        .map(|c| c.to_ascii_lowercase())
        .fold(HashMap::new(), |mut map, c| {
            *map.entry(c).or_insert(0) += 1;
            map
        })
}

pub fn sorted_freq(s: &str) -> Vec<(char, usize)> {
    let mut pairs: Vec<(char, usize)> = frequency(s).into_iter().collect();
    pairs.sort_by(|(c1, n1), (c2, n2)| n2.cmp(n1).then(c1.cmp(c2)));
    pairs
}

module CMap = Map.Make(Char)

let frequency s =
  String.fold_left (fun m c ->
    let c = Char.lowercase_ascii c in
    if c >= 'a' && c <= 'z' then
      CMap.update c (function None -> Some 1 | Some n -> Some (n+1)) m
    else m
  ) CMap.empty s

let sorted_freq s =
  frequency s |> CMap.bindings
  |> List.sort (fun (_, a) (_, b) -> compare b a)

#![allow(clippy::all)]
use std::collections::{BTreeMap, HashMap};

/// Solution 1: Idiomatic Rust — HashMap with fold
/// Uses entry API for efficient in-place counting
pub fn frequency(s: &str) -> HashMap<char, usize> {
    s.chars()
        .filter(|c| c.is_ascii_alphabetic())
        .map(|c| c.to_ascii_lowercase())
        .fold(HashMap::new(), |mut map, c| {
            *map.entry(c).or_insert(0) += 1;
            map
        })
}

/// Solution 2: BTreeMap — mirrors OCaml's Map.Make(Char), keys stay sorted
/// Equivalent to OCaml's `CMap.update c (function None -> Some 1 | Some n -> Some (n+1)) m`
pub fn frequency_btree(s: &str) -> BTreeMap<char, usize> {
    s.chars()
        .filter(|c| c.is_ascii_alphabetic())
        .map(|c| c.to_ascii_lowercase())
        .fold(BTreeMap::new(), |mut map, c| {
            *map.entry(c).or_insert(0) += 1;
            map
        })
}

/// Solution 3: Sorted by frequency descending, ties broken alphabetically
/// Mirrors OCaml's `List.sort (fun (_, a) (_, b) -> compare b a)`
pub fn sorted_freq(s: &str) -> Vec<(char, usize)> {
    let mut pairs: Vec<(char, usize)> = frequency(s).into_iter().collect();
    pairs.sort_by(|(c1, n1), (c2, n2)| n2.cmp(n1).then(c1.cmp(c2)));
    pairs
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_empty_string() {
        assert_eq!(frequency(""), HashMap::new());
        assert!(sorted_freq("").is_empty());
    }

    #[test]
    fn test_single_character() {
        let freq = frequency("a");
        assert_eq!(freq[&'a'], 1);
        assert_eq!(freq.len(), 1);
    }

    #[test]
    fn test_case_insensitive() {
        let freq = frequency("AaAa");
        assert_eq!(freq[&'a'], 4);
        assert_eq!(freq.len(), 1);
    }

    #[test]
    fn test_non_alpha_ignored() {
        let freq = frequency("a1b2c! a");
        assert_eq!(freq[&'a'], 2);
        assert_eq!(freq[&'b'], 1);
        assert_eq!(freq[&'c'], 1);
        assert_eq!(freq.len(), 3);
    }

    #[test]
    fn test_pangram_all_letters_present() {
        let text = "The quick brown fox jumps over the lazy dog";
        let freq = frequency(text);
        // All 26 letters appear at least once in a pangram
        assert_eq!(freq.len(), 26);
        // 'e' and 'o' appear most in this pangram
        assert_eq!(freq[&'e'], 3);
        assert_eq!(freq[&'o'], 4);
    }

    #[test]
    fn test_btree_sorted_by_key() {
        let freq = frequency_btree("bac");
        let keys: Vec<char> = freq.keys().copied().collect();
        assert_eq!(keys, vec!['a', 'b', 'c']);
    }

    #[test]
    fn test_sorted_freq_descending() {
        let result = sorted_freq("aaabbc");
        assert_eq!(result[0], ('a', 3));
        assert_eq!(result[1], ('b', 2));
        assert_eq!(result[2], ('c', 1));
    }

    #[test]
    fn test_sorted_freq_ties_broken_alphabetically() {
        // 'a' and 'b' both appear twice — 'a' should come first
        let result = sorted_freq("aabb");
        assert_eq!(result[0], ('a', 2));
        assert_eq!(result[1], ('b', 2));
    }
}

module CMap = Map.Make(Char)

(* Idiomatic OCaml — fold over string, update map with lowercase letters *)
let frequency s =
  String.fold_left (fun m c ->
    let c = Char.lowercase_ascii c in
    if c >= 'a' && c <= 'z' then
      CMap.update c (function None -> Some 1 | Some n -> Some (n+1)) m
    else m
  ) CMap.empty s

(* Sorted by frequency descending — bindings gives (key, value) list *)
let sorted_freq s =
  frequency s |> CMap.bindings
  |> List.sort (fun (_, a) (_, b) -> compare b a)

(* Recursive variant — explicit pattern matching on char list *)
let frequency_rec s =
  let rec go m = function
    | [] -> m
    | c :: rest ->
      let c = Char.lowercase_ascii c in
      let m' =
        if c >= 'a' && c <= 'z' then
          CMap.update c (function None -> Some 1 | Some n -> Some (n+1)) m
        else m
      in
      go m' rest
  in
  go CMap.empty (List.of_seq (String.to_seq s))

let () =
  (* Basic frequency tests *)
  let f = frequency "aabb" in
  assert (CMap.find 'a' f = 2);
  assert (CMap.find 'b' f = 2);

  (* Case insensitive *)
  let f2 = frequency "AaAa" in
  assert (CMap.find 'a' f2 = 4);

  (* Non-alpha ignored *)
  let f3 = frequency "a1b!" in
  assert (CMap.find 'a' f3 = 1);
  assert (CMap.find 'b' f3 = 1);
  assert (not (CMap.mem '1' f3));

  (* Sorted descending *)
  let s = sorted_freq "aaabbc" in
  assert (s = [('a', 3); ('b', 2); ('c', 1)]);

  (* Recursive variant matches fold variant *)
  let text = "Hello World" in
  assert (frequency text = frequency_rec text);

  (* Pangram has all 26 letters *)
  let pangram = "The quick brown fox jumps over the lazy dog" in
  assert (CMap.cardinal (frequency pangram) = 26);

  print_endline "ok"