Collections Overview

// ── Core collection interfaces and their meanings: ────────────────────
//
//  Iterable<E>                  — can be iterated with for-each loop
//    └── Collection<E>          — a group of elements
//          ├── List<E>          — ordered sequence, duplicates allowed
//          ├── Set<E>           — no duplicates
//          │     ├── SortedSet<E>    — sorted order
//          │     └── NavigableSet<E> — floor, ceiling, higher, lower
//          └── Queue<E>         — elements processed in order
//                ├── Deque<E>   — double-ended queue (stack + queue)
//                └── BlockingQueue<E> — concurrent, waits when empty/full
//
//  Map<K,V>                     — key-value pairs (NOT a Collection)
//    ├── SortedMap<K,V>         — keys in sorted order
//    └── NavigableMap<K,V>      — floor, ceiling, headMap, tailMap

// ── Programming to interfaces — not implementations: ──────────────────
// GOOD — declare as interface:
List<String>   names    = new ArrayList<>();
Set<Integer>   ids      = new HashSet<>();
Map<String,Integer> map = new HashMap<>();
Queue<Task>    tasks    = new ArrayDeque<>();

// Later, swap implementation without changing any usage code:
List<String>   names2   = new LinkedList<>();   // same List interface
Map<String,Integer> map2 = new TreeMap<>();     // same Map interface

// ── One line creates and populates a collection (Java 9+): ────────────
List<String>      immutableList = List.of("Alice", "Bob", "Charlie");
Set<Integer>      immutableSet  = Set.of(1, 2, 3, 4, 5);
Map<String,Integer> immutableMap = Map.of("a", 1, "b", 2, "c", 3);

// ── Mutable collections: ──────────────────────────────────────────────
List<String> mutableList = new ArrayList<>(List.of("Alice", "Bob"));
Set<Integer> mutableSet  = new HashSet<>(Set.of(1, 2, 3));

// ── ArrayList — default list, O(1) access: ───────────────────────────
List<String> list = new ArrayList<>();
list.add("Alice");
list.add("Bob");
list.add(0, "Zara");    // insert at index — O(n) shift
String first = list.get(0);    // O(1) random access
list.remove(1);                // O(n) shift
System.out.println(list);      // [Zara, Alice]

// ── LinkedList — O(1) head/tail insert: ───────────────────────────────
Deque<String> deque = new LinkedList<>();
deque.addFirst("first");
deque.addLast("last");
deque.addFirst("new first");
System.out.println(deque.peekFirst());  // new first
System.out.println(deque.peekLast());   // last

// ── HashMap — O(1) average: ───────────────────────────────────────────
Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 90);
scores.put("Bob",   85);
scores.put("Carol", 92);
System.out.println(scores.get("Alice"));       // 90
scores.putIfAbsent("Dave", 78);
scores.computeIfPresent("Bob", (k, v) -> v + 5); // Bob → 90
System.out.println(scores.getOrDefault("Eve", 0)); // 0

// ── TreeMap — sorted keys, O(log n): ─────────────────────────────────
Map<String, Integer> sorted = new TreeMap<>(scores);
System.out.println(sorted.firstKey());          // Alice (alphabetically first)
System.out.println(sorted.lastKey());           // Dave
System.out.println(sorted.headMap("Carol"));    // {Alice=90, Bob=90}

// ── HashSet vs TreeSet: ───────────────────────────────────────────────
Set<Integer> hashSet = new HashSet<>(List.of(5, 3, 1, 4, 2));
Set<Integer> treeSet = new TreeSet<>(List.of(5, 3, 1, 4, 2));
System.out.println(hashSet);  // [1, 2, 3, 4, 5] — may vary
System.out.println(treeSet);  // [1, 2, 3, 4, 5] — always sorted

// ── Implementation selection guide: ──────────────────────────────────
//
// Need a list?
//   Default                → ArrayList
//   Frequent head inserts  → LinkedList / ArrayDeque
//   Thread-safe            → CopyOnWriteArrayList
//
// Need a set?
//   Default                → HashSet
//   Insertion order        → LinkedHashSet
//   Sorted order           → TreeSet
//
// Need a map?
//   Default                → HashMap
//   Insertion order        → LinkedHashMap
//   Sorted keys            → TreeMap
//   Thread-safe            → ConcurrentHashMap
//
// Need a queue?
//   FIFO queue             → ArrayDeque
//   Priority order         → PriorityQueue
//   Thread-safe blocking   → LinkedBlockingQueue

import java.util.*;

List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9, 3));

// ── Sorting: ──────────────────────────────────────────────────────────
Collections.sort(numbers);
System.out.println(numbers);            // [1, 2, 3, 5, 8, 9]

// Custom comparator — sort descending:
numbers.sort(Collections.reverseOrder());
System.out.println(numbers);            // [9, 8, 5, 3, 2, 1]

// ── Binary search (requires sorted list): ─────────────────────────────
Collections.sort(numbers);              // [1, 2, 3, 5, 8, 9]
int idx = Collections.binarySearch(numbers, 5);
System.out.println("5 found at index: " + idx);  // 3

// ── shuffle, reverse, rotate: ─────────────────────────────────────────
Collections.shuffle(numbers, new Random(42));
System.out.println("Shuffled: " + numbers);

Collections.reverse(numbers);
System.out.println("Reversed: " + numbers);

Collections.rotate(numbers, 2);  // rotate right by 2 positions
System.out.println("Rotated: " + numbers);

// ── min and max: ──────────────────────────────────────────────────────
List<String> names = Arrays.asList("Charlie", "Alice", "Bob");
System.out.println(Collections.min(names));  // Alice
System.out.println(Collections.max(names));  // Charlie

// ── Immutable views: ──────────────────────────────────────────────────
List<String> mutable   = new ArrayList<>(Arrays.asList("a", "b", "c"));
List<String> immutable = Collections.unmodifiableList(mutable);
System.out.println(immutable.get(0));     // a — reads work
// immutable.add("d");                    // throws UnsupportedOperationException

mutable.add("d");                         // changing original IS reflected:
System.out.println(immutable.size());     // 4 — view shows the change

// ── Factory collections: ──────────────────────────────────────────────
List<String>  singleton    = Collections.singletonList("only");
Set<Integer>  emptySet     = Collections.emptySet();
List<String>  fiveHello    = Collections.nCopies(5, "hello");
System.out.println(fiveHello);           // [hello, hello, hello, hello, hello]

// ── frequency and disjoint: ──────────────────────────────────────────
List<String> words = Arrays.asList("cat", "dog", "cat", "bird", "cat");
System.out.println(Collections.frequency(words, "cat"));  // 3

Set<String> setA = Set.of("a", "b", "c");
Set<String> setB = Set.of("d", "e", "f");
System.out.println(Collections.disjoint(setA, setB));  // true — no overlap

import java.util.concurrent.*;
import java.util.*;

// ── Thread-unsafe — never share between threads without sync: ─────────
List<String> unsafeList = new ArrayList<>();
Map<String, Integer> unsafeMap = new HashMap<>();
// If two threads call unsafeList.add() concurrently → data corruption!

// ── Approach 1: Synchronised wrappers — simple but low concurrency: ───
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
// Individual operations are thread-safe, but iteration still needs sync:
synchronized(syncList) {
    for (String s : syncList) {  // must synchronise the iteration
        System.out.println(s);
    }
}

// ── Approach 2: Copy-on-write — best for read-heavy: ─────────────────
CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<>();
cowList.add("listener1");
cowList.add("listener2");
// Iteration is always safe — reads a snapshot:
for (String listener : cowList) {  // no synchronisation needed
    System.out.println(listener);
}

// ── Approach 3: Concurrent collections — best performance: ────────────
ConcurrentHashMap<String, Integer> concMap = new ConcurrentHashMap<>();
concMap.put("key", 1);
concMap.computeIfAbsent("key2", k -> expensiveComputation(k));
// Atomic compound operations — no external synchronisation needed:
concMap.merge("counter", 1, Integer::sum);  // thread-safe increment

// BlockingQueue — producer-consumer pattern:
BlockingQueue<String> queue = new LinkedBlockingQueue<>(100);

// Producer thread:
Thread producer = new Thread(() -> {
    try {
        queue.put("task1");    // blocks if queue is full
        queue.put("task2");
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
});

// Consumer thread:
Thread consumer = new Thread(() -> {
    try {
        String task = queue.take();  // blocks if queue is empty
        System.out.println("Processing: " + task);
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
});

producer.start(); consumer.start();