Collections #

fn main() {
    // Create Vec
    let mut v: Vec<i32> = Vec::new();
    let v2 = vec![1, 2, 3, 4, 5];          // macro vec! — the most common way
    let v3: Vec<i32> = (1..=5).collect();   // of iterators
    let v4 = vec![0i32; 10];               // 10 elements have a value of 0

    // By capacity — avoid reallocation if final size is known
    let mut v5: Vec<i32> = Vec::with_capacity(100);
    println!("len: {}, capacity: {}", v5.len(), v5.capacity());  // 0.100

    // Add elements
    v.push(1);
    v.push(2);
    v.push(3);

    // Add multiple elements at once
    v.extend([4, 5, 6]);
    v.extend(v2.iter().copied());

    // Insert at a specific position — O(n), shift all elements after it
    v.insert(0, 99);  // inserts 99 at index 0
    println!("{:?}", v);  // [99, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5]

    // Delete element
    let terakhir = v.pop();          // delete and return last element: Some(5)
    let di_posisi = v.remove(0);    // delete at index 0, shift other elements: 99
    v.swap_remove(0);               // delete at index 0, fill with last element — O(1)

    // Element access
    let pertama: Option<&i32> = v.first();
    let terakhir: Option<&i32> = v.last();
    let ketiga: Option<&i32> = v.get(2);    // safe — returns Option
    let langsung: &i32 = &v[2];             // panic if outside the limit

    // ANTI-PATTERN: direct access without bounds checking
    // let x = v[100];  // panic if v has < 101 elements

    // CORRECT: use get() for secure access
    if let Some(x) = v.get(100) {
        println!("{}", x);
    }
}

fn main() {
    let mut v = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];

    // Sequencing
    v.sort();                              // ascending order: [1, 1, 2, 3, 3, 4, 5, 5, 6, 9]
    v.sort_by(|a, b| b.cmp(a));           // descending order
    v.sort_by_key(|&x| std::cmp::Reverse(x)); // another way of descending

    // For float (not implements Ord)
    let mut float_v = vec![3.1f64, 1.4, 2.7, 0.8];
    float_v.sort_by(|a, b| a.partial_cmp(b).unwrap());

    // Search — binary search only for sorted Vecs
    v.sort();
    match v.binary_search(&5) {
        Ok(idx) => println!("Ditemukan di indeks: {}", idx),
        Err(idx) => println!("Tidak ada, bisa disisipkan di indeks: {}", idx),
    }

    // Deduplication — remove sequential duplicates (effective after sort)
    v.dedup();
    println!("{:?}", v);  // [1, 2, 3, 4, 5, 6, 9]

    // Retain — retain only what meets the condition (in-place filter)
    let mut v2 = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    v2.retain(|&x| x % 2 == 0);
    println!("{:?}", v2);  // [2, 4, 6, 8, 10]

    // Reverse order
    v2.reverse();
    println!("{:?}", v2);  // [10, 8, 6, 4, 2]

    // Slice — reference to Vec section
    let v3 = vec![1, 2, 3, 4, 5];
    let tengah: &[i32] = &v3[1..4];  // [2, 3, 4]
    println!("{:?}", tengah);

    // Windows and chunks
    for window in v3.windows(3) {
        println!("{:?}", window);  // [1,2,3], [2,3,4], [3,4,5]
    }
    for chunk in v3.chunks(2) {
        println!("{:?}", chunk);   // [1,2], [3,4], [5]
    }

    // Split — splits Vec in two at certain positions
    let (kiri, kanan) = v3.split_at(2);
    println!("{:?} {:?}", kiri, kanan);  // [1, 2] [3, 4, 5]

    // Truncate and clear
    let mut v4 = vec![1, 2, 3, 4, 5];
    v4.truncate(3);   // keep only first 3 elements: [1, 2, 3]
    v4.clear();       // remove all elements, fixed capacity
}

fn main() {
    // Vec reallocates when capacity is exhausted
    // Strategy: capacity is doubled every time it runs out (amortized O(1))
    let mut v: Vec<i32> = Vec::new();
    for i in 0..10 {
        v.push(i);
        println!("len: {}, cap: {}", v.len(), v.capacity());
        // cap: 1, 2, 4, 4, 8, 8, 8, 8, 16, 16 — grows exponentially
    }

    // with_capacity if final size is known
    let n = 1000;
    let mut v_efisien: Vec<i32> = Vec::with_capacity(n);
    for i in 0..n as i32 {
        v_efisien.push(i);  // never reallocates
    }

    // shrink_to_fit — restore unused memory
    v_efisien.truncate(10);
    println!("Sebelum shrink — cap: {}", v_efisien.capacity()); // is still 1000
    v_efisien.shrink_to_fit();
    println!("Setelah shrink — cap: {}", v_efisien.capacity()); // about 10

    // drain — delete range elements, return as iterator
    let mut v5 = vec![1, 2, 3, 4, 5, 6, 7, 8];
    let diambil: Vec<i32> = v5.drain(2..5).collect();
    println!("Diambil: {:?}", diambil);  // [3, 4, 5]
    println!("Sisa: {:?}", v5);          // [1, 2, 6, 7, 8]
}

use std::collections::HashMap;

fn main() {
    // Create HashMap
    let mut skor: HashMap<String, i32> = HashMap::new();

    // Add entry
    skor.insert(String::from("Alice"), 85);
    skor.insert(String::from("Bob"), 92);
    skor.insert(String::from("Carol"), 78);

    // From array of tuples
    let map: HashMap<&str, i32> = [("satu", 1), ("dua", 2), ("tiga", 3)]
        .into_iter()
        .collect();

    // Read value
    let alice_skor = skor.get("Alice");          // Option<&i32> — safe
    let bob_skor = skor["Bob"];                  // i32 — panic if it's not there
    println!("{:?}", alice_skor);                // Some(85)

    // Key presence check
    println!("{}", skor.contains_key("Alice"));  // true
    println!("{}", skor.contains_key("Dave"));   // false

    // Delete entry
    let dihapus = skor.remove("Carol");          // returns Option<V>
    println!("{:?}", dihapus);                   // Some(78)

    // Iteration
    for (nama, nilai) in &skor {
        println!("{}: {}", nama, nilai);
    }

    // Key only or value only
    let semua_nama: Vec<&String> = skor.keys().collect();
    let semua_skor: Vec<&i32> = skor.values().collect();

    // Size
    println!("Jumlah entri: {}", skor.len());
    println!("Kosong: {}", skor.is_empty());
}

use std::collections::HashMap;

fn main() {
    let mut skor: HashMap<&str, i32> = HashMap::new();

    // ANTI-PATTERN: double lookup — check for existence then insert
    if !skor.contains_key("Alice") {
        skor.insert("Alice", 0);
    }
    *skor.get_mut("Alice").unwrap() += 10;

    // CORRECT: API entry — one lookup, more efficiency
    skor.entry("Alice").or_insert(0);
    *skor.entry("Alice").or_insert(0) += 10;

    // or_insert_with — lazy, value is only created if it doesn't already exist
    skor.entry("Bob").or_insert_with(|| {
        println!("Membuat nilai default untuk Bob");
        calculate_default_score()
    });

    // or_default — use the Default trait value
    skor.entry("Carol").or_default();  // 0 for i32

    // and_modify — modify if present, no insert if absent
    skor.entry("Alice").and_modify(|v| *v += 5);

    // Combination: modify if present, insert with default if not
    skor.entry("Dave")
        .and_modify(|v| *v += 10)
        .or_insert(50);

    println!("{:?}", skor);

    // Classic use case: calculating frequencies
    let teks = "apel pisang apel jeruk pisang apel mangga";
    let mut frekuensi: HashMap<&str, u32> = HashMap::new();

    for kata in teks.split_whitespace() {
        *frekuensi.entry(kata).or_insert(0) += 1;
    }
    println!("{:?}", frekuensi);
    // {"apples": 3, "bananas": 2, "oranges": 1, "mangoes": 1}

    // Use case: grouping — group by key
    let data = vec![
        ("backend", "Alice"),
        ("frontend", "Bob"),
        ("backend", "Carol"),
        ("frontend", "Dave"),
        ("backend", "Eve"),
    ];

    let mut per_tim: HashMap<&str, Vec<&str>> = HashMap::new();
    for (tim, nama) in &data {
        per_tim.entry(tim).or_insert_with(Vec::new).push(nama);
    }
    println!("{:?}", per_tim);
    // {"backend": ["Alice", "Carol", "Eve"], "frontend": ["Bob", "Dave"]}
}

fn calculate_default_score() -> i32 { 50 }

use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use std::collections::hash_map::DefaultHasher;

// Uses FxHashMap from the rustc-hash crate for higher performance
// Add to Cargo.toml: rustc-hash="1"
// use rustc_hash::FxHashMap;

fn main() {
    // HashMap standard — secure, performs well in most cases
    let mut map: HashMap<String, i32> = HashMap::new();
    map.insert("kunci".to_string(), 42);

    // When to consider alternative hashers:
    // - Key is a predictable integer or short string
    // - Hot path that needs maximum throughput
    // - Non-public context (does not accept external input)
}

use std::collections::HashSet;

fn main() {
    // Create HashSet
    let mut set: HashSet<i32> = HashSet::new();
    let set2: HashSet<i32> = vec![1, 2, 3, 2, 1].into_iter().collect(); // duplicate removed

    // Add and delete
    set.insert(1);
    set.insert(2);
    set.insert(2);  // ignored — already there
    set.remove(&1);

    // Checking
    println!("{}", set.contains(&2));  // true

    // Set operations — this is the main strength of HashSet
    let a: HashSet<i32> = vec![1, 2, 3, 4, 5].into_iter().collect();
    let b: HashSet<i32> = vec![3, 4, 5, 6, 7].into_iter().collect();

    // Intersection — elements present in both
    let irisan: HashSet<&i32> = a.intersection(&b).collect();
    println!("Irisan: {:?}", irisan);  // {3, 4, 5}

    // Union — all elements of both sets
    let gabungan: HashSet<&i32> = a.union(&b).collect();
    println!("Gabungan: {:?}", gabungan);  // {1, 2, 3, 4, 5, 6, 7}

    // Difference — elements in a but not in b
    let selisih: HashSet<&i32> = a.difference(&b).collect();
    println!("Selisih a-b: {:?}", selisih);  // {1, 2}

    // Symmetrical difference — elements that are present in one but not both
    let sym_diff: HashSet<&i32> = a.symmetric_difference(&b).collect();
    println!("Selisih simetris: {:?}", sym_diff);  // {1, 2, 6, 7}

    // Checking set relations
    let sub: HashSet<i32> = vec![1, 2].into_iter().collect();
    println!("sub bagian dari a: {}", sub.is_subset(&a));    // true
    println!("a superset dari sub: {}", a.is_superset(&sub)); // true
    println!("a dan b disjoint: {}", a.is_disjoint(&b));      // false

    // Use case: deduplication with sequence preservation
    let dengan_duplikat = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
    let mut seen = HashSet::new();
    let unik_berurutan: Vec<i32> = dengan_duplikat
        .into_iter()
        .filter(|x| seen.insert(*x))  // insert returns false if it already exists
        .collect();
    println!("{:?}", unik_berurutan);  // [3, 1, 4, 5, 9, 2, 6] — awake sequence
}

use std::collections::BTreeMap;

fn main() {
    let mut map: BTreeMap<String, i32> = BTreeMap::new();
    map.insert("charlie".to_string(), 3);
    map.insert("alice".to_string(), 1);
    map.insert("bob".to_string(), 2);

    // Iteration is always in key order (alphabetical for String)
    for (k, v) in &map {
        println!("{}: {}", k, v);
    }
    // alice: 1
    // bob: 2
    // charlie: 3

    // Range query — this is what HashMap can't do
    for (k, v) in map.range("alice".to_string()..="bob".to_string()) {
        println!("{}: {}", k, v);
    }
    // alice: 1
    // bob: 2

    // Smallest and largest elements
    println!("{:?}", map.first_key_value());  // Some(("alice", 1))
    println!("{:?}", map.last_key_value());   // Some(("charlie", 3))

    // Remove the smallest or largest element
    map.pop_first();  // remove "alice"
    map.pop_last();   // remove "charlie"

    // Entry API is available the same as HashMap
    map.entry("dave".to_string()).or_insert(4);
}

use std::collections::BTreeSet;

fn main() {
    let mut set: BTreeSet<i32> = BTreeSet::new();
    for x in [5, 2, 8, 1, 9, 3, 7, 4, 6] {
        set.insert(x);
    }

    // Iterations are always in sorted order
    println!("{:?}", set.iter().collect::<Vec<_>>());  // [1, 2, 3, 4, 5, 6, 7, 8, 9]

    // Range query
    let rentang: Vec<&i32> = set.range(3..=7).collect();
    println!("{:?}", rentang);  // [3, 4, 5, 6, 7]

    // Smallest and largest values
    println!("{:?}", set.first());  // Some(1)
    println!("{:?}", set.last());   // Some(9)

    // Set operations (same as HashSet)
    let a: BTreeSet<i32> = vec![1, 2, 3, 4].into_iter().collect();
    let b: BTreeSet<i32> = vec![3, 4, 5, 6].into_iter().collect();
    let irisan: BTreeSet<i32> = a.intersection(&b).copied().collect();
    println!("{:?}", irisan);  // {3, 4}
}

use std::collections::VecDeque;

fn main() {
    let mut deque: VecDeque<i32> = VecDeque::new();

    // Adds in front and rear
    deque.push_back(1);
    deque.push_back(2);
    deque.push_back(3);
    deque.push_front(0);
    deque.push_front(-1);
    println!("{:?}", deque);  // [-1, 0, 1, 2, 3]

    // Wipe from front and back
    let depan = deque.pop_front();   // Some(-1)
    let belakang = deque.pop_back(); // Some(3)
    println!("{:?}", deque);  // [0, 1, 2]

    // Access without deleting
    println!("{:?}", deque.front());  // Some(0)
    println!("{:?}", deque.back());   // Some(2)

    // Convert to Vec (ring buffer linearization)
    let sebagai_vec: Vec<i32> = Vec::from(deque.clone());
    // Or: deque.make_contiguous() to get &mut [T]

    // Use case: sliding window / buffer with fixed size
    fn rata_rata_bergerak(data: &[f64], ukuran_window: usize) -> Vec<f64> {
        let mut window: VecDeque<f64> = VecDeque::with_capacity(ukuran_window);
        let mut hasil = Vec::new();

        for &nilai in data {
            window.push_back(nilai);
            if window.len() > ukuran_window {
                window.pop_front();
            }
            if window.len() == ukuran_window {
                let rata: f64 = window.iter().sum::<f64>() / ukuran_window as f64;
                hasil.push(rata);
            }
        }
        hasil
    }

    let data = vec![1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0];
    let ma = rata_rata_bergerak(&data, 3);
    println!("{:?}", ma);  // [2.0, 3.0, 4.0, 5.0, 6.0]

    // Use case: BFS (Breadth-First Search)
    fn bfs(graf: &Vec<Vec<usize>>, mulai: usize) -> Vec<usize> {
        let n = graf.len();
        let mut dikunjungi = vec![false; n];
        let mut antrean: VecDeque<usize> = VecDeque::new();
        let mut urutan = Vec::new();

        antrean.push_back(mulai);
        dikunjungi[mulai] = true;

        while let Some(node) = antrean.pop_front() {
            urutan.push(node);
            for &tetangga in &graf[node] {
                if !dikunjungi[tetangga] {
                    dikunjungi[tetangga] = true;
                    antrean.push_back(tetangga);
                }
            }
        }
        urutan
    }
}

use std::collections::HashMap;

fn main() {
    // 1. HashMap transformation — map values
    let harga: HashMap<&str, f64> = [("apel", 5000.0), ("pisang", 3000.0)].into_iter().collect();

    let setelah_pajak: HashMap<&str, f64> = harga.iter()
        .map(|(&k, &v)| (k, v * 1.1))
        .collect();

    // 2. HashMap Filter
    let mahal: HashMap<&&str, &f64> = harga.iter()
        .filter(|(_, &v)| v > 4000.0)
        .collect();

    // 3. Invert HashMap — swap keys and values
    let kode: HashMap<&str, u32> = [("merah", 1), ("hijau", 2), ("biru", 3)].into_iter().collect();
    let terbalik: HashMap<u32, &str> = kode.iter().map(|(&k, &v)| (v, k)).collect();
    println!("{:?}", terbalik);  // {1: "red", 2: "green", 3: "blue"}

    // 4. Merge two HashMap — the value from the second map wins if there is a conflict
    let mut map1: HashMap<&str, i32> = [("a", 1), ("b", 2)].into_iter().collect();
    let map2: HashMap<&str, i32> = [("b", 20), ("c", 3)].into_iter().collect();
    map1.extend(map2);
    println!("{:?}", map1);  // {"a": 1, "b": 20, "c": 3}

    // 5. Calculate top-N of frequencies
    let teks = "apel pisang apel jeruk pisang apel mangga jeruk apel";
    let mut frekuensi: Vec<(&str, usize)> = teks.split_whitespace()
        .fold(HashMap::<&str, usize>::new(), |mut map, kata| {
            *map.entry(kata).or_insert(0) += 1;
            map
        })
        .into_iter()
        .collect();

    frekuensi.sort_by(|a, b| b.1.cmp(&a.1));  // in order of most
    let top_2: Vec<_> = frekuensi.iter().take(2).collect();
    println!("{:?}", top_2);  // [("apples", 4), ("bananas", 2)] or ("oranges", 2)

    // 6. Vec of struct — sort by field
    #[derive(Debug)]
    struct Produk { nama: String, harga: f64, stok: u32 }

    let mut produk = vec![
        Produk { nama: "Apel".to_string(), harga: 5000.0, stok: 100 },
        Produk { nama: "Pisang".to_string(), harga: 3000.0, stok: 50 },
        Produk { nama: "Jeruk".to_string(), harga: 7000.0, stok: 75 },
    ];

    // Sort by ascending price
    produk.sort_by(|a, b| a.harga.partial_cmp(&b.harga).unwrap());

    // Sort by multiple criteria
    produk.sort_by(|a, b| {
        b.stok.cmp(&a.stok)                           // descending stock
            .then(a.harga.partial_cmp(&b.harga).unwrap()) // then ascending price
    });

    // 7. Flatten and deduplication from multiple sources
    let sumber1 = vec![1, 2, 3, 4];
    let sumber2 = vec![3, 4, 5, 6];
    let sumber3 = vec![5, 6, 7, 8];

    use std::collections::HashSet;
    let semua_unik: HashSet<i32> = [sumber1, sumber2, sumber3]
        .into_iter()
        .flatten()
        .collect();
    let mut terurut: Vec<i32> = semua_unik.into_iter().collect();
    terurut.sort();
    println!("{:?}", terurut);  // [1, 2, 3, 4, 5, 6, 7, 8]
}