🦀 Rust 集合与迭代器

// 方式一：new + push
let mut v = Vec::new();
v.push(1);
v.push(2);
v.push(3);

// 方式二：vec! 宏（最常用）
let v = vec![1, 2, 3];
let zeros = vec![0; 100];       // 100 个 0
let nested = vec![vec![1, 2], vec![3, 4]];

// 方式三：从迭代器收集
let v: Vec<i32> = (1..=5).collect();

// 方式四：with_capacity（性能关键路径）
let mut v = Vec::with_capacity(1000);
// 此时 v.len() == 0, v.capacity() == 1000
for i in 0..1000 {
    v.push(i); // 不会触发任何重新分配！
}

let mut v = vec![10, 20, 30, 40, 50];

// 索引访问（可能 panic）
let first = v[0];           // 10
let oob = v[100];           // ❌ panic! 索引越界

// get 方法（安全，返回 Option）
let third = v.get(2);       // Some(&30)
let oob = v.get(100);       // None

// 可变访问
v[1] = 25;
if let Some(elem) = v.get_mut(3) {
    *elem = 45;
}

// 首尾操作
let last = v.pop();          // Some(50)，Vec 变为 [10, 25, 30, 45]
v.push(99);                  // [10, 25, 30, 45, 99]

let v = vec!["rust", "is", "awesome"];

// 1. for 循环（最常用，获取 &T）
for s in &v {
    println!("{}", s);
}

// 2. 可变遍历
let mut nums = vec![1, 2, 3];
for n in &mut nums {
    *n *= 2;  // [2, 4, 6]
}

// 3. 消费遍历（获取 T，v 之后不可用）
for s in v {
    println!("{}", s);  // s 是 String，不是 &String
}
// v 在这里已被移动！

// 4. enumerate（同时获取索引）
for (i, s) in v.iter().enumerate() {
    println!("{}: {}", i, s);
}

// 5. 迭代器方法链
let sum: i32 = nums.iter().sum();
let doubled: Vec<i32> = nums.iter().map(|x| x * 2).collect();

let mut v = Vec::with_capacity(8);
v.extend([1, 2, 3]);

println!("len: {}", v.len());           // 3 — 实际元素数
println!("capacity: {}", v.capacity()); // 8 — 分配的内存容量

v.shrink_to_fit();  // 释放多余内存，capacity 变为 3
v.reserve(100);     // 确保至少还有 100 的剩余容量
v.reserve_exact(100); // 精确分配 100 的额外容量（不多给）

let mut v = vec![1, 2, 3, 4, 5, 6, 7, 8];

// 1. pop — 删除最后一个
let last = v.pop(); // Some(8)

// 2. remove — 删除指定索引（O(n)，后面元素前移）
v.remove(0); // 删除 1，变为 [2, 3, 4, 5, 6, 7]

// 3. swap_remove — 与末尾交换后删除（O(1)，不保序）
v.swap_remove(0); // 删除 2（与末尾 7 交换），变为 [7, 3, 4, 5, 6]

// 4. retain — 保留满足条件的元素
let mut v = vec![1, 2, 3, 4, 5, 6];
v.retain(|&x| x % 2 == 0); // [2, 4, 6]

// 5. drain — 删除范围内的元素，返回迭代器
let mut v: Vec<_> = (1..=10).collect();
let drained: Vec<_> = v.drain(2..5).collect(); // [3, 4, 5]
// v 现在是 [1, 2, 6, 7, 8, 9, 10]

// 6. truncate — 截断到指定长度
let mut v = vec![1, 2, 3, 4, 5];
v.truncate(3); // [1, 2, 3]

// &str — 字符串字面量，编译期嵌入二进制
let greeting: &'static str = "Hello, Rust!";

// String — 堆上拥有所有权
let mut s = String::from("Hello");
s.push_str(", Rust!");
s.push('!');

// &str 从 String 借用
let slice: &str = &s;

// String 从 &str 创建
let owned = slice.to_string();
let owned2 = slice.to_owned();
let owned3 = String::from(slice);

let s = "Rust🦀";

// ❌ 编译错误！Rust 不允许直接索引字符串
// let c = s[0];

// ✅ 按字节切片（需要自己保证边界合法）
let rust_part = &s[0..4];   // "Rust" — 前4字节恰好是 ASCII
let emoji_part = &s[4..8];  // "🦀" — 4字节 UTF-8
// let broken = &s[0..5];  // ❌ 运行时 panic！截断了多字节字符

// ✅ 按字符迭代
for c in s.chars() {
    println!("{}", c);  // R, u, s, t, 🦀
}

// ✅ 获取第 N 个字符（需要遍历）
let third_char = s.chars().nth(2);  // Some('s')

// ✅ 按字符索引截取（推荐写法）
let char_indices: Vec<(usize, char)> = s.char_indices().collect();
// [(0, 'R'), (1, 'u'), (2, 's'), (3, 't'), (4, '🦀')]

// 1. + 运算符（左侧必须 String，右侧可以是 &str）
let hello = String::from("Hello, ");
let world = String::from("World!");
let result = hello + &world;  // hello 被消费！之后不可用

// 2. format! 宏（不消费任何参数）
let s1 = String::from("tic");
let s2 = String::from("tac");
let s3 = String::from("toe");
let res = format!("{s1}-{s2}-{s3}");  // s1/s2/s3 仍可用

// 3. push / push_str / extend
let mut s = String::new();
s.push_str("hello");
s.push('!');
s.extend(" world".chars());

// 4. 迭代器收集
let words = ["hello", "world"].join(" "); // "hello world"

// 5. 重复
let rep = "ha".repeat(3); // "hahaha"

use std::collections::HashMap;

// 创建
let mut scores: HashMap<String, i32> = HashMap::new();
let mut scores = HashMap::with_capacity(100);

// 插入
scores.insert(String::from("Alice"), 100);
scores.insert(String::from("Bob"), 95);

// 查询
let alice_score = scores.get(&String::from("Alice")); // Some(&100)
let unknown = scores.get("Charlie");                    // None

// 查询并获取可变引用
if let Some(score) = scores.get_mut("Alice") {
    *score += 10;
}

// 检查存在
if scores.contains_key("Bob") {
    println!("Bob's score: {}", scores["Bob"]);
}

// 删除
scores.remove("Bob");

// 长度
println!("{} players", scores.len());

use std::collections::HashMap;

let mut scores: HashMap<String, i32> = HashMap::new();

// or_insert — 键不存在时插入默认值
scores.entry(String::from("Alice")).or_insert(0);
scores.entry(String::from("Alice")).or_insert(100); // 已存在，不覆盖

// or_insert_with — 惰性计算默认值（避免不必要的分配）
let mut map: HashMap<String, Vec<i32>> = HashMap::new();
map.entry("key".to_string())
   .or_insert_with(Vec::new)
   .push(42);

// or_default — 使用 Default trait
let mut map: HashMap<String, Vec<i32>> = HashMap::new();
map.entry("key".to_string()).or_default().push(42);

// and_modify — 键存在时修改
scores.entry(String::from("Alice"))
      .and_modify(|v| *v += 10)
      .or_insert(100);

// 经典模式：词频统计
let text = "hello world hello rust world hello";
let mut word_count: HashMap<&str, i32> = HashMap::new();
for word in text.split_whitespace() {
    *word_count.entry(word).or_insert(0) += 1;
}
// {"hello": 3, "world": 2, "rust": 1}

let mut scores = HashMap::new();
scores.insert("Alice", 100);
scores.insert("Bob", 95);

// 遍历键值对（顺序不确定！）
for (name, score) in &scores {
    println!("{}: {}", name, score);
}

// 仅遍历键
for name in scores.keys() {
    println!("{}", name);
}

// 仅遍历值
for score in scores.values() {
    println!("{}", score);
}

// 可变遍历值
for score in scores.values_mut() {
    *score += 5;
}

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(3, "c");
map.insert(1, "a");
map.insert(2, "b");

// 自动按键排序遍历
for (k, v) in &map {
    println!("{}: {}", k, v); // 1:a, 2:b, 3:c
}

// 范围查询 — HashMap 做不到！
for (&k, &v) in map.range(2..=3) {
    println!("{}: {}", k, v); // 2:b, 3:c
}

// 最小/最大键
println!("min: {:?}", map.first_key_value()); // Some((&1, &"a"))
println!("max: {:?}", map.last_key_value());  // Some((&3, &"c"))

use std::collections::HashSet;

let mut set = HashSet::new();
set.insert("rust");
set.insert("python");
set.insert("rust"); // 重复插入，返回 false

println!("contains: {}", set.contains("rust")); // true
println!("len: {}", set.len()); // 2

set.remove("python");
set.insert("go");

// 从迭代器创建
let set: HashSet<_> = [1, 2, 3, 2, 1].into_iter().collect();
// {1, 2, 3} — 自动去重

use std::collections::HashSet;

let a: HashSet<_> = [1, 2, 3, 4].into_iter().collect();
let b: HashSet<_> = [3, 4, 5, 6].into_iter().collect();

// 交集 — 同时在 a 和 b 中的元素
let intersection: HashSet<_> = a.intersection(&b).collect();
// {3, 4}

// 并集 — 在 a 或 b 中的元素
let union: HashSet<_> = a.union(&b).collect();
// {1, 2, 3, 4, 5, 6}

// 差集 — 在 a 中但不在 b 中的元素
let difference: HashSet<_> = a.difference(&b).collect();
// {1, 2}

// 对称差集 — 在 a 或 b 中但不同时在两者中
let sym_diff: HashSet<_> = a.symmetric_difference(&b).collect();
// {1, 2, 5, 6}

// 判断子集/超集
let c: HashSet<_> = [1, 2].into_iter().collect();
println!("c ⊆ a: {}", c.is_subset(&a));      // true
println!("a ⊇ c: {}", a.is_superset(&c));    // true
println!("c ∩ a ≠ ∅: {}", c.is_disjoint(&a)); // false（有交集）

// 模式一：Vec 去重（保留首次出现）
let mut seen = HashSet::new();
let items = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
let deduped: Vec<i32> = items.into_iter()
    .filter(|x| seen.insert(*x))  // insert 返回 true 表示首次插入
    .collect();
// [3, 1, 4, 5, 9, 2, 6] — 保留原始顺序！

// 模式二：Vec 去重（不需要保序）
let items = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
let unique: HashSet<i32> = items.into_iter().collect();
// 顺序不确定

// 模式三：迭代器链中去重
use itertools::unique; // 需要 itertools crate
let deduped: Vec<i32> = vec![3, 1, 4, 1, 5].into_iter().unique().collect();

use std::collections::VecDeque;

let mut dq = VecDeque::new();

// 前端操作
dq.push_front(1);   // [1]
dq.push_front(2);   // [2, 1]
let front = dq.pop_front(); // Some(2)，[1]

// 后端操作
dq.push_back(3);    // [1, 3]
dq.push_back(4);    // [1, 3, 4]
let back = dq.pop_back();   // Some(4)，[1, 3]

// 典型用法：BFS 队列
let mut queue = VecDeque::new();
queue.push_back(start);
while let Some(node) = queue.pop_front() {
    for neighbor in node.neighbors() {
        queue.push_back(neighbor);
    }
}

use std::collections::BinaryHeap;
use std::cmp::Reverse;

// 最大堆（默认）
let mut max_heap = BinaryHeap::new();
max_heap.push(3);
max_heap.push(1);
max_heap.push(5);
max_heap.push(2);
println!("{:?}", max_heap.pop()); // Some(5)

// 最小堆 — 用 Reverse 包装
let mut min_heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
min_heap.push(Reverse(3));
min_heap.push(Reverse(1));
min_heap.push(Reverse(5));
println!("{:?}", min_heap.pop()); // Some(Reverse(1))

// 优先队列 — 复杂类型
#[derive(Eq, PartialEq)]
struct Task {
    priority: i32,
    name: String,
}
impl Ord for Task {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.priority.cmp(&other.priority)
    }
}
impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

let mut tasks = BinaryHeap::new();
tasks.push(Task { priority: 3, name: "写文档".into() });
tasks.push(Task { priority: 1, name: "修 bug".into() });
tasks.push(Task { priority: 5, name: "上线".into() });

// 按优先级从高到低处理
while let Some(task) = tasks.pop() {
    println!("处理: {} (优先级 {})", task.name, task.priority);
}

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;

    // 提供了几十个默认方法！
    // map, filter, fold, collect, for_each,
    // take, skip, zip, chain, enumerate, ...
}

let v = vec![1, 2, 3];

// iter() — 不可变引用 (&T)
for x in v.iter() {
    // x: &i32
}
// v 仍可用

// iter_mut() — 可变引用 (&mut T)
let mut v = vec![1, 2, 3];
for x in v.iter_mut() {
    // x: &mut i32
    *x += 10;
}
// v: [11, 12, 13]

// into_iter() — 获取所有权 (T)
for x in v.into_iter() {
    // x: i32（值被移出）
}
// v 已被消费，不可再用！

// for 循环语法糖
for x in &v { ... }     // 等价于 v.iter()
for x in &mut v { ... } // 等价于 v.iter_mut()
for x in v { ... }       // 等价于 v.into_iter()

let v = vec![1, 2, 3, 4, 5];

// collect — 收集到集合
let list: Vec<i32> = v.iter().cloned().collect();
let set: HashSet<i32> = v.iter().cloned().collect();
let map: HashMap<i32, i32> = v.iter()
    .map(|&x| (x, x * x))
    .collect();

// fold — 左折叠，累加器
let sum = v.iter().fold(0, |acc, &x| acc + x); // 15

// 更常用的 sum / product
let sum: i32 = v.iter().sum();            // 15
let product: i32 = v.iter().product();     // 120

// for_each — 对每个元素执行副作用
v.iter().for_each(|x| println!("{}", x));

// count — 计数
let count = v.iter().count(); // 5

// any / all — 存在性/全称判断
let has_even = v.iter().any(|x| x % 2 == 0);   // true
let all_pos = v.iter().all(|x| x > &0);        // true

// find — 找到第一个满足条件的
let first_even = v.iter().find(|&&x| x % 2 == 0); // Some(&2)

// position — 找到第一个满足条件的索引
let pos = v.iter().position(|&x| x == &3); // Some(2)

// max / min
let max = v.iter().max(); // Some(&5)
let min_key = v.iter().min_by_key(|&&x| x % 3); // Some(&3)

// partition — 分成两个集合
let (even, odd): (Vec<_>, Vec<_>) = v.iter()
    .partition(|&&x| x % 2 == 0);

// unzip — 拆分元组迭代器为两个集合
let pairs = vec![(1, "a"), (2, "b"), (3, "c")];
let (nums, chars): (Vec<_>, Vec<_>) = pairs.into_iter().unzip();

// reduce — 不需要初始值的 fold
let max = v.iter().cloned().reduce(i32::max); // Some(5)

let v = vec![1, 2, 3];
let doubled: Vec<i32> = v.iter().map(|x| x * 2).collect(); // [2, 4, 6]

// map 返回新迭代器，不消费原集合
// 常见错误：忘记 collect！
let iter = v.iter().map(|x| x * 2); // 这只是一个迭代器，还没执行

let v = vec![1, 2, 3, 4, 5, 6];
let evens: Vec<&i32> = v.iter().filter(|x| *x % 2 == 0).collect(); // [&2, &4, &6]

// filter_map — filter + map 合体
let results: Vec<i32> = v.iter()
    .filter_map(|&x| if x % 2 == 0 { Some(x * 10) } else { None })
    .collect();
// [20, 40, 60]

let v = vec![1, 2, 3, 4, 5];

let first_three: Vec<_> = v.iter().take(3).collect();    // [&1, &2, &3]
let skip_two: Vec<_> = v.iter().skip(2).collect();       // [&3, &4, &5]
let middle: Vec<_> = v.iter().skip(1).take(3).collect(); // [&2, &3, &4]

// take_while / skip_while — 按条件截取/跳过
let v = vec![1, 2, 3, 4, 1, 2];
let prefix: Vec<_> = v.iter().take_while(|&&x| x < 4).collect(); // [&1, &2, &3]
let suffix: Vec<_> = v.iter().skip_while(|&&x| x < 4).collect(); // [&4, &1, &2]

// chain — 顺序连接两个迭代器
let a = vec![1, 2, 3];
let b = vec![4, 5, 6];
let combined: Vec<_> = a.iter().chain(&b).collect(); // [&1..&6]

// zip — 配对两个迭代器
let names = vec!["Alice", "Bob", "Charlie"];
let scores = vec![100, 95, 88];
let pairs: Vec<_> = names.iter().zip(scores.iter()).collect();
// [(&"Alice", &100), (&"Bob", &95), (&"Charlie", &88)]

// zip 实战：同时遍历索引和值
for (i, val) in v.iter().enumerate() { ... }
// 等价于 (0..).zip(v.iter())

// flatten — 展开嵌套迭代器
let nested = vec![vec![1, 2], vec![3, 4], vec![5]];
let flat: Vec<_> = nested.iter().flatten().collect();
// [&1, &2, &3, &4, &5]

// flat_map — map + flatten
let words = vec!["hello world", "rust is great"];
let all_words: Vec<&str> = words.iter()
    .flat_map(|s| s.split_whitespace())
    .collect();
// ["hello", "world", "rust", "is", "great"]

// 处理 Option 的 flatten
let opts = vec![Some(1), None, Some(3), None, Some(5)];
let values: Vec<_> = opts.into_iter().flatten().collect();
// [1, 3, 5]

let v = vec!["a", "b", "c"];
for (i, val) in v.iter().enumerate() {
    println!("{}: {}", i, val);
}
// 0: a, 1: b, 2: c

// enumerate + map 模式
let indexed: Vec<(usize, &str)> = v.iter().enumerate()
    .map(|(i, s)| (i, *s))
    .collect();

struct Fibonacci {
    curr: u64,
    next: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { curr: 0, next: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let current = self.curr;
        self.curr = self.next;
        self.next = current + self.next;
        Some(current)
    }
}

// 使用
let fib_10: Vec<u64> = Fibonacci::new().take(10).collect();
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

let sum: u64 = Fibonacci::new()
    .take_while(|&x| x < 1_000_000)
    .filter(|&x| x % 2 == 0)
    .sum(); // 斐波那契数列中 < 1000000 的偶数之和

/// 生成 [start, start+step, start+2*step, ...] 直到超过 max
struct RangeStep {
    current: i32,
    step: i32,
    max: i32,
}

impl RangeStep {
    fn new(start: i32, step: i32, max: i32) -> Self {
        RangeStep { current: start, step, max }
    }
}

impl Iterator for RangeStep {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.max {
            None
        } else {
            let result = self.current;
            self.current += self.step;
            Some(result)
        }
    }
}

// 使用
for x in RangeStep::new(0, 5, 20) {
    print!("{} ", x); // 0 5 10 15
}

enum TreeNode {
    Leaf(i32),
    Branch { left: Box<TreeNode>, right: Box<TreeNode> },
}

/// 中序遍历迭代器
struct InOrderIter {
    stack: Vec<&TreeNode>,
}

impl InOrderIter {
    fn new(root: &TreeNode) -> Self {
        let mut iter = InOrderIter { stack: vec![] };
        iter.push_left(root);
        iter
    }

    fn push_left(&mut self, mut node: &TreeNode) {
        while let TreeNode::Branch { left, right: _ } = node {
            self.stack.push(node);
            node = left;
        }
        self.stack.push(node);
    }
}

impl<'a> Iterator for InOrderIter {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        let node = self.stack.pop()?;
        match node {
            TreeNode::Leaf(val) => Some(*val),
            TreeNode::Branch { left: _, right } => {
                self.push_left(right);
                // 实际需要返回左子树或当前节点值
                // 这里简化了，完整实现需要更复杂的状态管理
                self.next()
            }
        }
    }
}

// 普通 Iterator：第一次返回 None 后，再次调用 next() 行为未定义
// FusedIterator：第一次返回 None 后，永远返回 None

use std::iter::FusedIterator;

struct Countdown {
    count: u32,
}

impl Iterator for Countdown {
    type Item = u32;
    fn next(&mut self) -> Option<u32> {
        if self.count == 0 {
            None
        } else {
            self.count -= 1;
            Some(self.count)
        }
    }
}

impl FusedIterator for Countdown {}

// FusedIterator 的好处：
// 1. 安全：不用关心耗尽后再调用 next() 的行为
// 2. 优化：某些适配器可以对 FusedIterator 做特殊优化
// 3. 规范：表明你的迭代器是"干净终止"的

// 1. 已知大小的迭代器可以预分配
let v: Vec<i32> = (0..1000).collect();  // 一次分配，精确大小

// 2. 未知大小时，使用启发式增长策略（类似 Vec 的 push）
let v: Vec<i32> = some_iter.filter(|x| x > 0).collect();
// 会先分配一小块，不够时 2x 增长

// 3. 可以用 SizeHint 帮助优化
// Iterator trait 有一个 size_hint() 方法
// 返回 (lower_bound, Option<upper_bound>)
impl Iterator for MyIter {
    type Item = i32;
    fn next(&mut self) -> Option<i32> { ... }
    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining)) // 精确大小
    }
}

// ❌ 性能差：不知道大小，频繁重分配
let mut v = Vec::new();
for i in 0..10_000 {
    v.push(i); // 可能触发 ~14 次重分配
}

// ✅ 性能好：预分配容量
let mut v = Vec::with_capacity(10_000);
for i in 0..10_000 {
    v.push(i); // 0 次重分配
}

// ✅ 最优：从迭代器收集
let v: Vec<i32> = (0..10_000).collect(); // 一次精确分配

use std::collections::HashMap;

/// 文本分析器
struct TextAnalyzer<'a> {
    text: &'a str,
}

impl<'a> TextAnalyzer<'a> {
    fn new(text: &'a str) -> Self {
        TextAnalyzer { text }
    }

    /// 分词 — 返回单词迭代器
    fn words(&self) -> impl Iterator<Item = &'a str> {
        self.text
            .split_whitespace()
            .map(|w| w.trim_matches(|c: char| !c.is_alphanumeric()))
            .filter(|w| !w.is_empty())
    }

    /// 词频统计
    fn word_frequencies(&self) -> HashMap<&'a str, usize> {
        self.words()
            .fold(HashMap::new(), |mut freqs, word| {
                *freqs.entry(word).or_insert(0) += 1;
                freqs
            })
    }

    /// TOP-N 高频词
    fn top_words(&self, n: usize) -> Vec<(&'a str, usize)> {
        let freqs = self.word_frequencies();
        let mut sorted: Vec<_> = freqs.into_iter().collect();
        sorted.sort_by(|a, b| b.1.cmp(&a.1));
        sorted.into_iter().take(n).collect()
    }

    /// 唯一词数
    fn unique_word_count(&self) -> usize {
        // 用 HashSet 去重
        use std::collections::HashSet;
        self.words().collect::<HashSet<_>>().len()
    }

    /// 总词数
    fn total_word_count(&self) -> usize {
        self.words().count()
    }

    /// 平均词长
    fn average_word_length(&self) -> f64 {
        let (total_len, count) = self.words()
            .fold((0usize, 0usize), |(len, cnt), word| {
                (len + word.len(), cnt + 1)
            });
        if count == 0 { 0.0 } else { total_len as f64 / count as f64 }
    }

    /// 文本摘要 — 按句子评分
    fn summarize(&self, n_sentences: usize) -> Vec<&'a str> {
        let freqs = self.word_frequencies();

        self.text
            .split(|c: char| c == '.' || c == '!' || c == '?')
            .map(|s| s.trim())
            .filter(|s| !s.is_empty())
            .map(|sentence| {
                // 句子评分 = 其单词词频之和
                let score: usize = sentence
                    .split_whitespace()
                    .map(|w| w.trim_matches(|c: char| !c.is_alphanumeric()))
                    .filter_map(|w| freqs.get(w))
                    .sum();
                (sentence, score)
            })
            .collect::<Vec<_>>()
            .into_iter()
            .sorted_by(|a, b| b.1.cmp(&a.1))  // 需要 itertools
            .take(n_sentences)
            .map(|(s, _)| s)
            .collect()
    }

    /// 长词统计（长度 >= threshold）
    fn long_words(&self, threshold: usize) -> Vec<&'a str> {
        self.words()
            .filter(|w| w.len() >= threshold)
            .collect()
    }

    /// 词长分布
    fn word_length_distribution(&self) -> HashMap<usize, usize> {
        self.words()
            .fold(HashMap::new(), |mut dist, word| {
                *dist.entry(word.len()).or_insert(0) += 1;
                dist
            })
    }
}

fn main() {
    let text = r#"
        Rust is a systems programming language that runs blazingly fast,
        prevents segfaults, and guarantees thread safety. Rust is designed
        to be memory safe without needing a garbage collector. The Rust
        programming language empowers everyone to build reliable and
        efficient software. Rust provides zero cost abstractions and
        guarantees memory safety. Programming in Rust is productive and fun.
    "#;

    let analyzer = TextAnalyzer::new(text);

    println!("📊 文本统计");
    println!("  总词数: {}", analyzer.total_word_count());
    println!("  唯一词数: {}", analyzer.unique_word_count());
    println!("  平均词长: {:.1}", analyzer.average_word_length());

    println!("\n🏆 TOP 5 高频词");
    for (word, count) in analyzer.top_words(5) {
        println!("  {:15} {}", word, "█".repeat(count));
    }

    println!("\n📏 词长分布");
    let dist = analyzer.word_length_distribution();
    let mut sorted: Vec<_> = dist.into_iter().collect();
    sorted.sort_by_key(|&(len, _)| len);
    for (len, count) in sorted {
        println!("  {} 字母: {}", len, "●".repeat(count));
    }

    println!("\n📝 长词 (>=8 字母)");
    println!("  {:?}", analyzer.long_words(8));
}

// 1. peekable — 预览下一个元素而不消费
let mut iter = vec![1, 2, 3].into_iter().peekable();
if iter.peek() == Some(&1) {
    println!("第一个元素是 1");
}
// iter 还可以从头消费

// 2. scan — 带状态的 map
let iter = vec![1, 2, 3, 4].into_iter();
let running_sum: Vec<i32> = iter
    .scan(0, |state, x| {
        *state += x;
        Some(*state)
    })
    .collect();
// [1, 3, 6, 10] — 累积和

// 3. windows — 滑动窗口（切片方法，不是迭代器方法）
let v = vec![1, 2, 3, 4, 5];
for window in v.windows(3) {
    println!("{:?}", window); // [1,2,3], [2,3,4], [3,4,5]
}

// 4. chunks — 固定大小分组
for chunk in v.chunks(2) {
    println!("{:?}", chunk); // [1,2], [3,4], [5]
}

// 5. group_by — itertools 提供的分组
use itertools::Itertools;
let data = vec![1, 1, 1, 2, 2, 3, 3, 3, 3];
for (key, group) in &data.into_iter().group_by(|&x| x) {
    println!("{}: {:?}", key, group.collect::<Vec<_>>());
}

// 6. 交错迭代 — interleave / intersperse
use itertools::Itertools;
let v = vec!["a", "b", "c"];
let joined: String = v.iter().intersperse(&", ").collect();
// "a, b, c"

// 7. 归并排序用迭代器
fn merge_sort<T: Ord + Clone>(mut v: Vec<T>) -> Vec<T> {
    if v.len() <= 1 { return v; }
    let mid = v.len() / 2;
    let right = v.split_off(mid);
    let left = merge_sort(v);
    let right = merge_sort(right);
    left.into_iter().merge(right.into_iter()).collect()
}

use std::collections::HashMap;

/// 高性能词频统计 — 预分配 HashMap
fn fast_word_count(text: &str) -> HashMap<&str, usize> {
    // 估算唯一词数（粗略），减少重分配
    let estimated_unique = text.split_whitespace().count() / 3;
    let mut freqs = HashMap::with_capacity(estimated_unique);

    for word in text.split_whitespace() {
        // 比 entry().or_insert(0) 更快：
        // 直接查找 + 插入，避免 entry 的开销
        *freqs.entry(word).or_insert(0) += 1;
    }

    freqs
}

/// TOP-N 不需要完整排序 — 用 BinaryHeap 只维护前 N 个
use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn top_n_words<'a>(freqs: &HashMap<&'a str, usize>, n: usize) -> Vec<(&'a str, usize)> {
    // 方法一：小顶堆维护 TOP-N（O(n log k)，k = n）
    let mut heap: BinaryHeap<Reverse<(usize, &'a str)>> = BinaryHeap::with_capacity(n);

    for (&word, &count) in freqs {
        if heap.len() < n {
            heap.push(Reverse((count, word)));
        } else if let Some(Reverse((min_count, _))) = heap.peek() {
            if count > *min_count {
                heap.pop();
                heap.push(Reverse((count, word)));
            }
        }
    }

    let mut result: Vec<_> = heap.into_iter()
        .map(|Reverse((count, word))| (word, count))
        .collect();
    result.sort_by(|a, b| b.1.cmp(&a.1));
    result
}

fn main() {
    let text = "the quick brown fox jumps over the lazy dog the fox is quick";
    let freqs = fast_word_count(text);

    println!("词频: {:?}", freqs);
    println!("TOP 3: {:?}", top_n_words(&freqs, 3));
}