Collections Framework — List, Set, Queue

// ❌ Với mảng: thêm một phần tử là cả một thủ tục
String[] ds = new String[3];
ds[0] = "a"; ds[1] = "b"; ds[2] = "c";
// Muốn thêm "d"? Phải tạo mảng mới và chép lại toàn bộ:
String[] moi = Arrays.copyOf(ds, 4);
moi[3] = "d";
// Muốn xoá phần tử giữa? Tự dịch chuyển mọi phần tử phía sau.
// Muốn kiểm tra "đã có chưa"? Tự viết vòng lặp.
// Muốn sắp xếp theo tiêu chí riêng? Tự cài thuật toán.

// ✅ Với Collections: tất cả đã có sẵn
List<String> ds2 = new ArrayList<>();
ds2.add("a"); ds2.add("b"); ds2.add("c");
ds2.add("d");                     // tự nới rộng
ds2.remove("b");                  // tự dịch chuyển
ds2.contains("c");                // có sẵn
Collections.sort(ds2);            // có sẵn
System.out.println(ds2);           // [a, c, d] — toString() tử tế

// ⭐ Khai báo theo INTERFACE, khởi tạo bằng CLASS cụ thể
List<String> ds = new ArrayList<>();
// Nhờ vậy đổi sang LinkedList sau này chỉ cần sửa MỘT dòng

// --- Thêm ---
ds.add("b");                    // thêm vào cuối
ds.add(0, "a");                 // chèn vào vị trí 0 (dịch chuyển phần còn lại)
ds.addAll(List.of("c", "d"));  // thêm nhiều

// --- Đọc / sửa ---
ds.get(0);                     // "a"
ds.set(0, "A");                 // thay thế, trả về giá trị cũ
ds.size();                     // 4
ds.isEmpty();                  // false

// --- Tìm ---
ds.contains("c");              // true  — O(n), duyệt tuần tự
ds.indexOf("c");               // 2     — -1 nếu không có
ds.lastIndexOf("c");

// --- Xoá: CẨN THẬN với List<Integer> ---
ds.remove(0);                  // xoá theo CHỈ SỐ
ds.remove("c");                // xoá theo GIÁ TRỊ
ds.removeIf(s -> s.startsWith("x"));   // ⭐ Java 8+, an toàn khi duyệt
ds.clear();

// --- Khung nhìn con (view) — chia sẻ dữ liệu với list gốc! ---
List<String> con = ds.subList(1, 3);   // [1, 3) — sửa `con` là sửa `ds`

// --- Sắp xếp ---
ds.sort(null);                       // thứ tự tự nhiên
ds.sort(Comparator.reverseOrder());
Collections.sort(ds);                 // cách cũ, tương đương

// ✅ Java 9+: List.of() — BẤT BIẾN hoàn toàn
List<String> a = List.of("a", "b", "c");
// a.add("d");        // UnsupportedOperationException
// a.set(0, "x");     // UnsupportedOperationException
// List.of("a", null) // NullPointerException — KHÔNG cho null!

// ⚠️ Arrays.asList() — KÍCH THƯỚC cố định nhưng SỬA được phần tử
List<String> b = Arrays.asList("a", "b", "c");
b.set(0, "x");       // ✅ được — nó là KHUNG NHÌN của mảng gốc
// b.add("d");     // UnsupportedOperationException

// ✅ Muốn list sửa được từ giá trị có sẵn
List<String> c = new ArrayList<>(List.of("a", "b"));
c.add("c");          // ✅

// ✅ Bản sao bất biến từ list đang có (Java 10+)
List<String> d = List.copyOf(c);

// ⚠️ unmodifiableList chỉ là KHUNG NHÌN chỉ đọc, không phải bản sao
List<String> goc = new ArrayList<>(List.of("a"));
List<String> view = Collections.unmodifiableList(goc);
goc.add("b");                          // sửa list GỐC
System.out.println(view);              // [a, b] ⚠️ view thấy thay đổi!

Set<String> s = new HashSet<>();

s.add("a");          // true  — thêm thành công
s.add("a");          // false — đã có, không thêm nữa
s.contains("a");     // true  — O(1) ⚡ đây là lý do dùng Set
s.remove("a");       // true

// --- Phép toán tập hợp ---
Set<Integer> A = new HashSet<>(List.of(1, 2, 3, 4));
Set<Integer> B = new HashSet<>(List.of(3, 4, 5, 6));

Set<Integer> hop = new HashSet<>(A);
hop.addAll(B);                        // A ∪ B = [1,2,3,4,5,6]

Set<Integer> giao = new HashSet<>(A);
giao.retainAll(B);                    // A ∩ B = [3,4]

Set<Integer> hieu = new HashSet<>(A);
hieu.removeAll(B);                    // A \ B = [1,2]

// Ứng dụng thường gặp nhất: loại trùng lặp
List<String> coTrung = List.of("a", "b", "a", "c", "b");
List<String> duyNhat = new ArrayList<>(new LinkedHashSet<>(coTrung));
System.out.println(duyNhat);   // [a, b, c] — giữ nguyên thứ tự xuất hiện

TreeSet<Integer> t = new TreeSet<>(List.of(10, 20, 30, 40, 50));

// Truy vấn thứ tự — HashSet KHÔNG làm được
t.first();            // 10
t.last();             // 50
t.floor(35);         // 30 — phần tử lớn nhất ≤ 35
t.ceiling(35);       // 40 — phần tử nhỏ nhất ≥ 35
t.lower(30);         // 20 — nhỏ hơn hẳn
t.higher(30);        // 40 — lớn hơn hẳn

// Khoảng giá trị
t.headSet(30);       // [10, 20]     — nhỏ hơn 30
t.tailSet(30);       // [30, 40, 50] — từ 30 trở lên
t.subSet(20, 40);    // [20, 30]     — [20, 40)
t.descendingSet();   // [50, 40, 30, 20, 10]

// Sắp xếp theo tiêu chí riêng
TreeSet<SinhVien> theoDiem =
    new TreeSet<>(Comparator.comparingDouble(SinhVien::getDiem).reversed());

// ⭐ ArrayDeque — dùng làm CẢ hàng đợi lẫn ngăn xếp, nhanh nhất cho cả hai

// --- Dùng như QUEUE (FIFO — vào trước ra trước) ---
Queue<String> q = new ArrayDeque<>();
q.offer("A");          // thêm vào cuối (add() cũng được nhưng ném lỗi khi đầy)
q.offer("B");
q.offer("C");
q.peek();              // "A" — xem đầu, KHÔNG xoá
q.poll();              // "A" — lấy và XOÁ khỏi đầu
System.out.println(q);  // [B, C]

// --- Dùng như STACK (LIFO — vào sau ra trước) ---
Deque<String> st = new ArrayDeque<>();
st.push("A");           // thêm vào ĐẦU
st.push("B");
st.push("C");
st.peek();             // "C"
st.pop();              // "C"
System.out.println(st); // [B, A]

// --- Hai đầu đầy đủ ---
Deque<Integer> d = new ArrayDeque<>();
d.offerFirst(1);  d.offerLast(2);
d.peekFirst();     d.peekLast();
d.pollFirst();     d.pollLast();

// PriorityQueue — luôn lấy ra phần tử "nhỏ nhất" theo thứ tự sắp xếp
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30); pq.offer(10); pq.offer(20);
pq.poll();   // 10 — nhỏ nhất trước
pq.poll();   // 20

// ⚠️ toString() KHÔNG theo thứ tự sắp xếp — nó in cấu trúc heap bên trong
System.out.println(pq);   // đừng tin cái này

// Ưu tiên ngược (lớn nhất trước)
PriorityQueue<Integer> maxPq = new PriorityQueue<>(Comparator.reverseOrder());

// Ứng dụng thật: hàng đợi công việc theo độ ưu tiên
record CongViec(String ten, int uuTien) { }
PriorityQueue<CongViec> hangDoi =
    new PriorityQueue<>(Comparator.comparingInt(CongViec::uuTien));
hangDoi.offer(new CongViec("Sao lưu", 5));
hangDoi.offer(new CongViec("Khẩn cấp", 1));
hangDoi.poll();    // CongViec[ten=Khẩn cấp, uuTien=1]

// Mẫu "top K phần tử lớn nhất" — chỉ giữ K phần tử trong bộ nhớ
PriorityQueue<Integer> topK = new PriorityQueue<>();   // min-heap
for (int x : duLieuRatLon) {
    topK.offer(x);
    if (topK.size() > K) topK.poll();   // loại phần tử nhỏ nhất
}   // Bộ nhớ O(K) thay vì O(n) — quan trọng với dữ liệu hàng tỷ phần tử

List<String> ds = new ArrayList<>(List.of("a", "b", "c", "d"));

// ❌ Xoá khi đang duyệt bằng for-each
for (String s : ds) {
    if (s.equals("b")) ds.remove(s);
}
// 💥 ConcurrentModificationException

// ✅ Cách 1: Iterator.remove() — cách chuẩn từ Java 1.2
Iterator<String> it = ds.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) it.remove();
}

// ✅ Cách 2: removeIf() — ngắn gọn nhất (Java 8+)
ds.removeIf(s -> s.equals("b"));

// ✅ Cách 3: duyệt ngược bằng chỉ số
for (int i = ds.size() - 1; i >= 0; i--) {
    if (ds.get(i).equals("b")) ds.remove(i);
}

// ✅ Cách 4: gom vào list mới rồi xoá một lượt
List<String> canXoa = ds.stream().filter(s -> s.equals("b")).toList();
ds.removeAll(canXoa);

// --- Comparable: thứ tự tự nhiên, gắn liền với lớp ---
record SinhVien(String ma, String ten, double diem, int tuoi)
        implements Comparable<SinhVien> {
    @Override
    public int compareTo(SinhVien khac) {
        return ma.compareTo(khac.ma);     // mặc định sắp theo mã
    }
}
Collections.sort(danhSach);        // dùng compareTo()

// --- Comparator: nhiều cách sắp xếp khác nhau ---
danhSach.sort(Comparator.comparing(SinhVien::ten));
danhSach.sort(Comparator.comparingDouble(SinhVien::diem).reversed());

// ⭐ Nhiều tiêu chí: điểm giảm dần, cùng điểm thì tên tăng dần, rồi tới tuổi
danhSach.sort(
    Comparator.comparingDouble(SinhVien::diem).reversed()
        .thenComparing(SinhVien::ten)
        .thenComparingInt(SinhVien::tuoi)
);

// Xử lý null an toàn
Comparator<SinhVien> anToan =
    Comparator.nullsFirst(Comparator.comparing(SinhVien::ten));

// Không phân biệt hoa thường
danhSach.sort(Comparator.comparing(SinhVien::ten, String.CASE_INSENSITIVE_ORDER));

import java.util.Collections;

List<Integer> ds = new ArrayList<>(List.of(3, 1, 4, 1, 5, 9));

Collections.sort(ds);                  // sắp xếp tại chỗ
Collections.reverse(ds);               // đảo ngược
Collections.shuffle(ds);               // xáo trộn ngẫu nhiên
Collections.swap(ds, 0, 1);          // hoán đổi hai vị trí
Collections.max(ds);                   // 9
Collections.min(ds);                   // 1
Collections.frequency(ds, 1);         // 2 — số lần xuất hiện
Collections.nCopies(3, "x");         // [x, x, x] — bất biến
Collections.binarySearch(ds, 4);      // ⚠️ list PHẢI đã sắp xếp
Collections.disjoint(ds1, ds2);       // true nếu KHÔNG có phần tử chung

// Collection rỗng bất biến — tránh trả về null
List<String> rong = Collections.emptyList();
Set<String>  rong2 = Collections.emptySet();

// Khung nhìn chỉ đọc
List<Integer> chiDoc = Collections.unmodifiableList(ds);

// Bọc đồng bộ — thô sơ; chương 12 có lựa chọn tốt hơn
List<Integer> dongBo = Collections.synchronizedList(ds);

// ❌ Dùng List để kiểm tra tồn tại — O(n) cho MỖI lần kiểm tra
List<String> daThay = new ArrayList<>();
for (String url : 100_000 URL) {
    if (!daThay.contains(url)) {   // O(n) — duyệt cả list
        daThay.add(url);
        xuLy(url);
    }
}
// Tổng: O(n²) = 10 tỷ phép so sánh → khoảng vài phút

// ✅ Dùng Set — O(1) cho mỗi lần kiểm tra
Set<String> daThay2 = new HashSet<>();
for (String url : 100_000 URL) {
    if (daThay2.add(url)) {       // add trả false nếu đã có — gộp 2 bước làm 1
        xuLy(url);
    }
}
// Tổng: O(n) = 100 nghìn phép → vài mili giây
// Chênh lệch: hàng NGHÌN lần, chỉ vì đổi một từ khoá.

Dữ liệu là cặp KHOÁ → GIÁ TRỊ?
├── CÓ  →  Map (Chương 8)
│         ├── Cần sắp theo khoá?      → TreeMap
│         ├── Cần giữ thứ tự thêm?    → LinkedHashMap
│         └── Còn lại                 → HashMap ⭐
│
└── KHÔNG  →  Cần loại trùng lặp?
    ├── CÓ  →  Set
    │         ├── Cần sắp xếp / tìm khoảng?  → TreeSet
    │         ├── Cần giữ thứ tự thêm?       → LinkedHashSet
    │         └── Còn lại                    → HashSet ⭐
    │
    └── KHÔNG  →  Xử lý theo thứ tự vào/ra?
        ├── CÓ  →  Cần độ ưu tiên?
        │         ├── CÓ     → PriorityQueue
        │         └── KHÔNG  → ArrayDeque ⭐ (cả FIFO lẫn LIFO)
        │
        └── KHÔNG  →  List
                  └── ArrayList ⭐ (gần như luôn luôn)