/** 1. Arrays - Fixed-size, indexed collection of elements of the same type.
* No import needed; always available.
* O(1) get, O(n) search (iterate), O(1) insert+delete, O(n) storage
*/
int[] arr = {1, 2, 3};

/** 2. ArrayList - Resizable array implementation.
* same as array except O(1) insert/delete at tail
* insert/delete at head requires shifting all elements so O(n)
*/
import java.util.ArrayList;
ArrayList<Integer> list = new ArrayList<>(); list.add(1);

/** 3. LinkedList - Doubly-linked list implementation, efficient for insertions/deletions.
* get is O(n) since it requires sequential ordered iteration.
* insert/delete at head and tail is O(1) 
*/
import java.util.LinkedList;
LinkedList<String> linkedList = new LinkedList<>(); linkedList.add("A");

/** 4. Stack - Last In, First Out (LIFO) structure.
* O(1) push/pop, O(n) search/iterate
*/
import java.util.Stack;
Stack<Integer> stack = new Stack<>(); stack.push(1);

/** 5. Queue - First In, First Out (FIFO) structure.
* O(1) add;enqueue/remove;dequeue, O(n) search/iterate
*/
import java.util.Queue;
Queue<String> queue = new LinkedList<>(); queue.add("A");

/** 6. Deque - Double-ended queue; supports insertion/removal at both ends. It's like a LinkedList and Queue had a baby.
* O(1) add/remove head/tail, O(n) search/iterate
*/
import java.util.Deque;
Deque<Integer> deque = new LinkedList<>(); deque.addFirst(1);

/** 7. HashMap - Key-value pairs; allows fast retrieval by key.
* O(1) get/search(contains)/update/remove, O(n) if there is a collision
* storage is based on natural hashcode/equals of object which is overridable
*/
import java.util.HashMap; // ConcurrentHashMap if multi-threading
HashMap<String, Integer> map = new HashMap<>(); map.put("A", 1);

/** 8.LinkedHashMap - HashMap which maintains insertion order when iterating with some overhead to maintain index for order.
* same as hashmap with 2n storage
*/
import java.util.LinkedHashMap;
LinkedHashMap<String, Integer> lMap = new LinkedHashMap<>(); lMap.put("A", 1);

/** 9. TreeMap - Key-value pairs sorted by key
* this maintains a self-balancing binary search tree (red-black tree)
* implements the generic interface SortedMap
* sorting is based on comparator order which can be overridden for custom logic and not on natural hashcode/equals of objects.
* or override compareTo
* O(logn) get/search(contains)/insert/delete
*/
import java.util.TreeMap;
TreeMap<Integer, String> tMap = new TreeMap<>(); tMap.put(1, "A");

/** 10. HashSet - Unordered collection of unique elements.
* O(1) get/add/deleted/search(contains check), O(n) collisions
*/
import java.util.HashSet;
HashSet<String> set = new HashSet<>(); set.add("A");

/** 11. LinkedHashSet - HashSet which maintains insertion order when iterating.
* O(1) get/add/deleted/search(contains check), O(n) collisions
*/
import java.util.LinkedHashSet;
LinkedHashSet<String> lSet = new LinkedHashSet<>(); lSet.add("A");

/** 12. TreeSet - Sorted set of unique elements.
* implements the generic interface SortedSet
* O(logn) get/search(contains)/insert/delete
*/
import java.util.TreeSet;
TreeSet<Integer> tSet = new TreeSet<>(); tSet.add(1);

/** 13. PriorityQueue (min-heap)
import java.util.PriorityQueue;
* Internal binary-tree; min-heap by default
* Elements ordered by natural/comparator priority.
 O(logn) add(rebalances)/pop(rebalances)/search(contains), O(1) peek
*/
PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(1);
pq.peek();//show 1; pq.poll();

/** 14. BitSet
import java.util.BitSet;
* Efficient storage of bits (boolean values).
* O(1) get/set/clear, O(n) Logical operations (AND/OR/XOR)
*/ 
BitSet bitSet = new BitSet(); bitSet.set(0);

/** Notable mentions:
* java.util.Hashtable - legacy HashMap which did not allow null keys or values and was synchronized by default for multi-threading. Essentially replaced by ConcurrentHashMap.
*/

// Max-heap and custom heaps use PriorityQueue and provide a custom Comparer
 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.add(10);
maxHeap.add(20);
maxHeap.add(5);
System.out.println(maxHeap.poll()); // 20
System.out.println(maxHeap.poll()); // 10
System.out.println(maxHeap.poll()); // 5

/** Bloom filter; probabilistic storage
false positives - returns True if element may exist, guarantees no false negatives - if if element does not exist

/** Basic sorting using built-in libs
* implements dual-pivot quicksort for primitives
* arrays and lists of objects use Timsort
*/ 
import java.util.Arrays;
import java.util.Collections;
Integer[] arr = {10, 7, 8, 9, 1, 5};

Arrays.sort(arr); // sort ascending by default or
Arrays.sort(arr, Collections.reverseOrder()); // for descending and
Collections.sort(yourList); // for list

/** Bubblesort and/or MergeSort are less common, but worth understanding how they work in case you run into it.
* Bubblesort - quadratic-N^2; repeatedly compares adjacent elements, swapping them if they are in the wrong order, until fully sorted.
* Mergesort - nlogn; divides the list into halves, recursively sorts them, and merges the sorted halves into a single sorted list.
*/

// Custom sorting on a treemap
TreeMap<String, Integer> treeMap = new TreeMap<>((a, b) -> b.length() - a.length());
treeMap.put("short", 1);
treeMap.put("longer", 2);
treeMap.put("tiny", 3);
TreeMap<CustomKey, Integer> treeMap = new TreeMap<>();
treeMap.put(new CustomKey("short"), 1);
treeMap.put(new CustomKey("longer"), 2);

class CustomKey implements Comparable<CustomKey> {
    String value;

    CustomKey(String value) {
        this.value = value;
    }

    @Override
    public int compareTo(CustomKey o) {
        return Integer.compare(this.value.length(), o.value.length());
    }
}


// Binary search
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // Avoids overflow compared to (left + right) / 2

            // Check if the target is present at mid
            if (arr[mid] == target) {
                return mid;
            }

            // If target is greater, ignore the left half
            if (arr[mid] < target) {
                left = mid + 1;
            }
            // If target is smaller, ignore the right half
            else {
                right = mid - 1;
            }
        }

        // Target is not present in the array
        return -1;
    }

// Cartesian Product of Two Lists
// you can put this into matrix etc go ham
import java.util.ArrayList;
import java.util.List;

/** for suits = List.of('K', 'Q', 'J'), colors = List.of('R','B')
* cartesianProduct(suits, colors) returns
* [[K,R], [Q,R], [J,R], [K,B], [Q,B], [J,B]]
*/
List<Integer> iterableB = List.of(4, 5, 6);
public List<List<String>> cartesianProduct(List<String>aIter,List<String>bIter) {
        List<List<Integer>> result = new ArrayList<>();

        for (String a : aIter) {
            for (Integer b : bIter) {
                // can also import apache commons pair or use Entry
                List<Integer> pair = List.of(a, b);
                result.add(pair);
            }
        }

    return result;
    }
}

import java.util.Arrays;
import java.util.Stack; // you can also use an array as stack but not as clean
import java.util.stream.Collectors;

//import org.springframework.lang.NonNull; // remove before committing

public final class QuickSort {

    // Utility method to swap two elements in an array
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    //@NonNull - don't commit this; I put these here commented for illustrative discussion to point out ints cannot be null
    private int partition(int a[], int start, int end) {
        final int pivot = a[start];
        int nextStart = start - 1;
        int nextEnd = end + 1;
        
        // I prefer Hoare's scheme to Lomuto's
        while (true) {
            // Move nextStart to the right until an element >= pivot is found
            do {
                nextStart++;
            } while (nextStart <= end && a[nextStart] < pivot); // boundary check prevents edge cases like {5, 5, 5, 5, 5}

            // Move nextEnd to the left until an element <= pivot is found
            do {
                nextEnd--;
            } while (nextEnd >= start && a[nextEnd] > pivot);

            // If nextStart and nextEnd pointers cross, return the partition index
            if (nextStart >= nextEnd) {
                return nextEnd;
            }
        swap(a, nextStart, nextEnd);
        }
    }

    /** Simple quicksort implementation. Add return type if not mutating input array.
     * 
      * @param mutableArray[] - The array to sort.
      * @param start  - Left boundary; start index.
      * @param end - Right boundary; end index .
      */
    public void sort(int mutableArray[], int start, int end) {
        final Stack<int[]> stack = new Stack<>(); // using stack avoids overflow
        
        // Store the starting indexes to kickoff, you can also pass in the stack
        stack.push(new int[] {start, end});

        while (!stack.isEmpty()) {
            // Pop left,right bounds from the stack
            int[] bounds = stack.pop();
            int nextStart = bounds[0];
            int nextEnd = bounds[1];

            // simple base case to skip invalid ranges
            if (nextStart < nextEnd) {
                // get the pivotIndex to partition the array into two subarrays
                int pivotIndex = partition(mutableArray, nextStart, nextEnd);

                // push the two subarrays on the stack, recursive looks similar
stack.push(new int[] { nextStart, pivotIndex}); // note Lomuto's is -1 here!
                stack.push(new int[] { pivotIndex + 1, nextEnd });
            }
        }
    }

public static void main(String args[]) {
        int mutableArray[] = {10, 7, 8, 9, 1, 5};

        // note in a recursive approach this method signature also works.
        // copying the array is also an option using extra O(n) space.
        new QuickSort().sort(mutableArray, 0, mutableArray.length-1);

        String result = Arrays.stream(mutableArray)
                              .mapToObj(String::valueOf)
                              .collect(Collectors.joining(","));
        System.out.println(result);
    }
}