package ArrayList
import NoWurst
import ErrorHandling
import Annotations

constant int INITIAL_CAPACITY = 16
constant int MAX_FREE_SECTIONS = 256

/**
 * High-performance array-based list using static shared storage per type.
 * In most cases, a LinkedList is a better choice due to its flexibility.
 * This data structure is only recommended for performance-critical code
 * and requires careful use to avoid fragmentation.
 *
 * WHEN TO USE:
 * ===========
 * ArrayList is faster than LinkedList for:
 * - Iterating large lists (1000+ elements) - no node indirection
 * - Index based operations - O(1) vs O(n)
 * - When only appending elements to the end
 *
 * LinkedList is better for:
 * - Insertion anywhere except the end of the list
 * - Deletions while retaining order
 * - Unknown size requirements
 * - No resize performance risk
 *
 * TYPE SYSTEM IMPLICATIONS:
 * ========================
 * Each ArrayList<T> type gets its own static storage array.
 * - ArrayList<int>, ArrayList<unit>, ArrayList<string> = 3 separate arrays
 * - On the Jass target each type holds up to JASS_MAX_ARRAY_SIZE elements total across all
 *   instances (the Lua target grows dynamically and is not bounded by this)
 *
 * Choose wisely based on how many types you have.
 *
 * PERFORMANCE RULES:
 * ==================
 *
 * 1. PRESIZE, DON'T RESIZE
 *    Bad:  new ArrayList<int>()           // Might resize multiple times
 *    Good: new ArrayList<int>(maxSize)    // One allocation
 *
 *    Why: Resize operations copy ALL elements to new memory. Expensive!
 *
 * 2. REUSE, DON'T RECREATE
 *    Bad:  In loop `let temp = new ArrayList<int>() ... destroy temp`
 *    Good: `let temp = new ArrayList<int>() ... temp.clear()` in loop
 *
 *    Why: Allocation/Deallocation is moderately expensive and causes fragmentation
 *
 * 3. ORDERED REMOVAL IS SLOW
 *    Bad:  list.removeAt(i)              // O(n) - shifts all elements
 *    Good: list.removeAtUnordered(i)     // O(1) - swaps with last element
 *
 *    Only use removeAtUnordered() if order doesn't matter
 *
 * 4. ITERATE BY INDEX
 *    Good: for i = 0 to list.size()-1                // Zero allocation
 *    Good: list[i]                                   // Indexing operator
 *
 *    ArrayList has no iterator by design - index loops keep hot paths
 *    allocation-free.
 *
 * 5. AVOID FREQUENT INSERTS AT START
 *    Bad:  list.addtoStart(x)         // O(n) every time
 *    Good: Use LinkedList or add in reverse order
 *
 * PERFORMANCE TABLE:
 * ==================
 * Operation          | ArrayList | LinkedList | Notes
 * -------------------|-----------|------------|---------------------------
 * add(elem)          | O(1)*     | O(1)       | *O(n) on resize!
 * addtoStart(elem)   | O(n)      | O(1)       | Shifts all elements
 * get(index)         | O(1)      | O(n)       | Major ArrayList advantage
 * removeAt(index)    | O(n)      | O(1)       | Shifts remaining elements
 * removeAtUnordered  | O(1)      | N/A        | Doesn't preserve order
 * Iterate all        | Faster    | Fast       | LinkedList does double the work, but is still fast
 * Memory per element | 1 slot    | 3 slots    | Element + 2 pointers
 * Create/destroy     | Varies    | High       | AL might need memory management, LL needs to process Nodes
 *
 * MEMORY MANAGEMENT:
 * ==================
 * ArrayList uses section allocation in a shared static array per type.
 * Destroyed lists return sections to a free pool for reuse.
 * Reuse is first-fit and claims the whole freed section (sections are never split).
 * Adjacent free sections are merged (compacted) when the store approaches its cap or
 * when the free pool is full, so interior gaps may persist until then.
 * The free pool itself is bounded (MAX_FREE_SECTIONS): if it is full and compaction
 * cannot shrink it, a freed section's space is dropped (it leaks until the type's
 * store is reset). Element references are always cleared, so this is a space leak, not
 * a dangling-reference leak. Presize and reuse lists to avoid reaching this state.
 *
 * Fragmentation occurs when lists grow - the old section becomes a gap.
 * This is why presizing matters: growth = copy to new location = wasted space.
 *
 * Hard limit (wc3 / Jass native target): the shared store is a fixed-size array, so it is
 * bounded by JASS_MAX_ARRAY_SIZE total slots per type across all live instances; exceeding
 * it raises an error. On the Lua target the store is a dynamically growing table, so the
 * cap does not apply - allocateStorage branches on the magic isLua constant and skips the
 * error. ArrayList's added value on Lua is keeping element types static instead of relying
 * on typecasting.
 **/
public class ArrayList<T:>
    private static T array store
    private static int nextFreeIndex = 0

    // Memory management structures
    private static int array freeSectionStart
    private static int array freeSectionCapacity
    private static int freeSectionCount = 0

    private int startIndex
    private int capacity
    private int size = 0

    /** Creates a new empty list with default capacity (16) */
    construct()
        allocateStorage(INITIAL_CAPACITY)

    /** Creates a new list with specified initial capacity - RECOMMENDED for performance */
    construct(int initialCapacity)
        allocateStorage(initialCapacity > 0 ? initialCapacity : INITIAL_CAPACITY)

    /** Creates a new list by copying all elements from another list */
    construct(thistype base)
        allocateStorage(base.size > INITIAL_CAPACITY ? base.size : INITIAL_CAPACITY)
        addAll(base)


    /** Allocates storage section - tries to reuse freed sections first */
    private function allocateStorage(int cap)
        if cap <= 0
            error("ArrayList: allocateStorage capacity must be > 0")
        // Try to find a freed section that fits
        if tryReuseFreeSection(cap)
            return

        // No suitable free section, allocate new
        if nextFreeIndex + cap > JASS_MAX_ARRAY_SIZE
            // Past the native array bound - compact to merge adjacent freed sections, then
            // retry the reuse search since compaction may have produced a section that fits.
            compactFreeList()
            if tryReuseFreeSection(cap)
                return

            // The Jass target is a fixed-size array and must error here. On Lua the store
            // is a dynamically growing table, so the bound doesn't apply and we let it grow.
            if not isLua and nextFreeIndex + cap > JASS_MAX_ARRAY_SIZE
                error("ArrayList: Storage limit exceeded for type")

        startIndex = nextFreeIndex
        capacity = cap
        nextFreeIndex += cap

    /** Claims the first freed section that fits cap and returns true; false if none fit */
    private function tryReuseFreeSection(int cap) returns boolean
        for i = 0 to freeSectionCount - 1
            if freeSectionCapacity[i] >= cap
                startIndex = freeSectionStart[i]
                capacity = freeSectionCapacity[i]

                // Remove this section from free list
                for j = i to freeSectionCount - 2
                    freeSectionStart[j] = freeSectionStart[j + 1]
                    freeSectionCapacity[j] = freeSectionCapacity[j + 1]
                freeSectionCount--
                return true
        return false

    /** Compacts the free list by merging adjacent sections */
    private static function compactFreeList()
        if freeSectionCount <= 1
            return

        // Sort free sections by start index using insertion sort
        for i = 1 to freeSectionCount - 1
            let keyStart = freeSectionStart[i]
            let keyCap = freeSectionCapacity[i]
            var j = i - 1

            while j >= 0 and freeSectionStart[j] > keyStart
                freeSectionStart[j + 1] = freeSectionStart[j]
                freeSectionCapacity[j + 1] = freeSectionCapacity[j]
                j--

            freeSectionStart[j + 1] = keyStart
            freeSectionCapacity[j + 1] = keyCap

        // Merge adjacent sections
        var writeIdx = 0
        for readIdx = 0 to freeSectionCount - 1
            if writeIdx > 0 and freeSectionStart[writeIdx - 1] + freeSectionCapacity[writeIdx - 1] == freeSectionStart[readIdx]
                // Merge with previous
                freeSectionCapacity[writeIdx - 1] += freeSectionCapacity[readIdx]
            else
                // Keep as separate section
                if writeIdx != readIdx
                    freeSectionStart[writeIdx] = freeSectionStart[readIdx]
                    freeSectionCapacity[writeIdx] = freeSectionCapacity[readIdx]
                writeIdx++

        freeSectionCount = writeIdx

        // Update nextFreeIndex if last section extends to it
        if freeSectionCount > 0
            let lastIdx = freeSectionCount - 1
            if freeSectionStart[lastIdx] + freeSectionCapacity[lastIdx] == nextFreeIndex
                nextFreeIndex = freeSectionStart[lastIdx]
                freeSectionCount--

    /** Frees this list's storage section for reuse */
    private function freeStorage()
        if capacity <= 0
            return

        // Add to free list if there's space
        if freeSectionCount < MAX_FREE_SECTIONS
            freeSectionStart[freeSectionCount] = startIndex
            freeSectionCapacity[freeSectionCount] = capacity
            freeSectionCount++

            // If this was at the end, we can reclaim it immediately
            if startIndex + capacity == nextFreeIndex
                nextFreeIndex = startIndex
                freeSectionCount--
        else
            // Free list full, try to compact
            compactFreeList()

            // Try again after compaction
            if freeSectionCount < MAX_FREE_SECTIONS
                freeSectionStart[freeSectionCount] = startIndex
                freeSectionCapacity[freeSectionCount] = capacity
                freeSectionCount++

    /** Grows the capacity (doubles it) - EXPENSIVE OPERATION! */
    private function grow()
        let newCapacity = capacity * 2
        let oldStart = startIndex
        let oldCapacity = capacity

        // Try to allocate new section
        allocateStorage(newCapacity)

        // Copy elements to new location
        for i = 0 to size - 1
            store[startIndex + i] = store[oldStart + i]

        // The old section now holds duplicate references and no longer belongs to any
        // live list once freed. Clear it so the Lua GC can reclaim them (no-op on Jass).
        if isLua
            for i = 0 to size - 1
                store[oldStart + i] = null

        // Free old section
        let tempStart = startIndex
        let tempCap = capacity
        startIndex = oldStart
        capacity = oldCapacity
        freeStorage()
        startIndex = tempStart
        capacity = tempCap

    ondestroy
        // Clear references
        for i = 0 to size - 1
            store[startIndex + i] = null

        // Return storage to free pool
        freeStorage()

    // ============================================================================
    // BASIC OPERATIONS
    // ============================================================================

    /** Adds one or more elements to the end of the list (amortized O(1)) */
    function add(vararg T elems)
        for elem in elems
            if size >= capacity
                grow()
            store[startIndex + size] = elem
            size++

    /** Adds all elements from another list */
    function addAll(ArrayList<T> other)
        // Optimize: pre-grow if needed
        let needed = size + other.size
        while needed > capacity
            grow()

        for i = 0 to other.size - 1
            store[startIndex + size] = other.get(i)
            size++

    /** Returns the element at the specified index (O(1)) */
    function get(int index) returns T
        if index < 0 or index >= size
            error("ArrayList: Index out of bounds: " + index.toString())

        return store[startIndex + index]

    /** Sets the element at the specified index (O(1)) */
    function set(int index, T elem)
        if index < 0 or index >= size
            error("ArrayList: Index out of bounds: " + index.toString())
        store[startIndex + index] = elem

    /** Reads the element at the given index via the [] operator (O(1)).
        Note: for tuple element types use get()/set() instead - the [] operator on
        tuple-typed lists currently hits a compiler limitation. */
    function op_index(int index) returns T
        return get(index)

    /** Writes the element at the given index via the [] operator (O(1)).
        See op_index for the tuple element-type caveat. */
    function op_indexAssign(int index, T value)
        set(index, value)

    /** Returns the index of the specified element or -1 if it doesn't exist (O(n)) */
    function indexOf(T elem) returns int
        for i = 0 to size - 1
            if store[startIndex + i] == elem
                return i
        return -1

    /** Returns whether the list contains the specified element (O(n)) */
    function has(T elem) returns boolean
        return indexOf(elem) >= 0

    /** Removes the element at the given index and returns it, shifting the
        remaining elements left to preserve order (O(n)) */
    function removeAtOrdered(int index) returns T
        if index < 0 or index >= size
            error("ArrayList: Index out of bounds: " + index.toString())

        let elem = store[startIndex + index]

        // Shift elements left
        for i = index to size - 2
            store[startIndex + i] = store[startIndex + i + 1]

        size--
        // The last slot now holds a stale duplicate - release it for the Lua GC
        if isLua
            store[startIndex + size] = null
        return elem

    /** Removes the element at the given index and returns it (O(n) - shifts elements) */
    @Deprecated("This operation shifts elements, consider using #removeAtUnordered if order is not important.")
    function removeAt(int index) returns T
        return removeAtOrdered(index)

    /** Removes the element at the given index by swapping with last element (O(1) - DOES NOT PRESERVE ORDER!) */
    function removeAtUnordered(int index) returns T
        if index < 0 or index >= size
            error("ArrayList: Index out of bounds: " + index.toString())

        let elem = store[startIndex + index]

        // Replace with last element
        size--
        if index < size
            store[startIndex + index] = store[startIndex + size]

        // The old last slot is now vacated (or held the removed element) - release it
        if isLua
            store[startIndex + size] = null

        return elem

    /** Removes the first occurrence of the element from the list (O(n)) */
    @Deprecated("This operation shifts elements, consider using #removeUnordered if order is not important.")
    function remove(T elem) returns bool
        let index = indexOf(elem)
        if index >= 0
            removeAtOrdered(index)
            return true
        return false

    /** Removes the first occurrence of the element from the list (O(n)) */
    function removeUnordered(T elem) returns bool
        let index = indexOf(elem)
        if index >= 0
            removeAtUnordered(index)
            return true
        return false

    /** Returns the size of the list (O(1)) */
    function size() returns int
        return size

    /** Checks whether this list is empty (O(1)) */
    function isEmpty() returns boolean
        return size == 0

    /** Returns the first element in the list, or null if empty (O(1)) */
    function getFirst() returns T
        if size == 0
            return null
        return store[startIndex]

    /** Returns the last element in the list, or null if empty (O(1)) */
    function getLast() returns T
        if size == 0
            return null
        return store[startIndex + size - 1]

    /** Clears all elements from the list (reuse this list instead of creating new ones!).
        O(1) on Jass; O(n) on Lua, where the slots are nulled so the GC can reclaim them. */
    function clear()
        if isLua
            for i = 0 to size - 1
                store[startIndex + i] = null
        size = 0

    /** Returns a shallow copy of this list */
    function copy() returns ArrayList<T>
        let list = new ArrayList<T>(size)
        for i = 0 to size - 1
            list.add(store[startIndex + i])
        return list

    /** Replaces the first occurrence of 'whichElement' with 'newElement' */
    function replace(T whichElement, T newElement) returns boolean
        let index = indexOf(whichElement)
        if index >= 0
            set(index, newElement)
            return true
        return false

    /** Returns a random element from this list or null if empty */
    function getRandomElement() returns T
        if size == 0
            return null
        return get(GetRandomInt(0, size - 1))

    // ============================================================================
    // STACK OPERATIONS (LIFO)
    // ============================================================================

    /** Adds an element to the end of the list (stack push) */
    function push(T elem)
        add(elem)

    /** Returns and removes the last added element (LIFO) */
    function pop() returns T
        if size == 0
            return null
        size--
        let elem = store[startIndex + size]
        // Release the popped slot so the Lua GC can reclaim the reference
        if isLua
            store[startIndex + size] = null
        return elem

    /** Returns the lastly added element without removing it, or null if empty */
    function peek() returns T
        return getLast()

    // ============================================================================
    // QUEUE OPERATIONS (FIFO)
    // ============================================================================

    /** Adds an element to the end (queue enqueue) */
    function enqueue(T elem)
        add(elem)

    /** Returns and removes the first element (FIFO) - WARNING: O(n) operation! */
    function dequeue() returns T
        if size == 0
            return null
        return removeAtOrdered(0)

    // ============================================================================
    // INSERTION OPERATIONS
    // ============================================================================

    /** Adds element at the beginning of the list - WARNING: O(n) operation! */
    function addtoStart(T elem)
        if size >= capacity
            grow()

        // Shift all elements right
        for i = size - 1 downto 0
            store[startIndex + i + 1] = store[startIndex + i]

        store[startIndex] = elem
        size++

    /** Adds the given element at the given index - WARNING: O(n) operation! */
    function addAt(T elem, int index)
        if index < 0 or index > size
            error("ArrayList: Index out of bounds: " + index.toString())

        if size >= capacity
            grow()

        // Shift elements right
        for i = size - 1 downto index
            store[startIndex + i + 1] = store[startIndex + i]

        store[startIndex + index] = elem
        size++

    // ============================================================================
    // ITERATOR & FUNCTIONAL OPERATIONS
    // ============================================================================

    /** Removes elements that satisfy the predicate (O(n), preserves order).
        If order is not important, use #removeUnorderedIf */
    function removeIf(ArrayListPredicate<T> predicate)
        // Single pass compaction: keep elements that fail the predicate
        var writeIndex = 0
        for readIndex = 0 to size - 1
            let elem = store[startIndex + readIndex]
            if not predicate.isTrueFor(elem)
                store[startIndex + writeIndex] = elem
                writeIndex++
        // Release the compacted-away tail (still the old size here) for the Lua GC
        if isLua
            for i = writeIndex to size - 1
                store[startIndex + i] = null
        size = writeIndex
        destroy predicate

    /** Removes elements that satisfy the predicate (O(n), does NOT preserve order) */
    function removeUnorderedIf(ArrayListPredicate<T> predicate)
        var i = 0
        while i < size
            if predicate.isTrueFor(store[startIndex + i])
                // swaps the last element into i and shrinks - don't advance i
                removeAtUnordered(i)
            else
                i++
        destroy predicate

    /** Executes the closure for each element */
    function forEach(ALItrClosure<T> itr) returns ArrayList<T>
        for i = 0 to size - 1
            itr.run(store[startIndex + i])
        destroy itr
        return this

    /** Updates all elements */
    function updateAll(ArrayListUpdater<T> f)
        for i = 0 to size - 1
            store[startIndex + i] = f.update(store[startIndex + i])
        destroy f

    /** Returns the list obtained by applying the given closure to each element */
    function map<Q:>(MapClosure<T, Q> itr) returns ArrayList<Q>
        let output = new ArrayList<Q>(size)
        forEach(t -> output.add(itr.run(t)))
        destroy itr
        return output

    /** Returns a new list of elements that satisfy the predicate */
    function filter(ArrayListPredicate<T> predicate) returns ArrayList<T>
        let result = new ArrayList<T>()
        for i = 0 to size - 1
            let elem = store[startIndex + i]
            if predicate.isTrueFor(elem)
                result.add(elem)
        destroy predicate
        return result

    /** Folds this list into a single value of type Q */
    function foldl<Q:>(Q startValue, FoldClosure<T, Q> predicate) returns Q
        var result = startValue
        for i = 0 to size - 1
            result = predicate.run(store[startIndex + i], result)
        destroy predicate
        return result

    /** Returns the first element that satisfies the predicate, or null if none present */
    function find(ArrayListPredicate<T> predicate) returns T
        T result = null
        for i = 0 to size - 1
            let elem = store[startIndex + i]
            if predicate.isTrueFor(elem)
                result = elem
                break
        destroy predicate
        return result

    // ============================================================================
    // SORTING & SHUFFLING
    // ============================================================================

    /** Performs a Fisher-Yates shuffle on this list */
    function shuffle()
        for i = size - 1 downto 1
            let j = GetRandomInt(0, i)
            let tmp = store[startIndex + i]
            store[startIndex + i] = store[startIndex + j]
            store[startIndex + j] = tmp

    /** Sorts the list using optimized quicksort with median-of-three pivot.
        Unlike the other higher-order methods, the comparator is NOT destroyed so it
        can be reused; destroy it yourself if it was allocated for a single sort. */
    function sortWith(Comparator<T> comparator)
        if comparator != null and size > 1
            quicksort(comparator, 0, size - 1)

    /** Optimized quicksort with median-of-three pivot selection */
    private function quicksort(Comparator<T> comparator, int low, int high)
        if low < high
            let pivot = medianOfThree(comparator, low, low + (high - low) div 2, high)
            let p = partition(comparator, low, high, pivot)

            quicksort(comparator, low, p - 1)
            quicksort(comparator, p + 1, high)

    /** Median-of-three pivot selection */
    private function medianOfThree(Comparator<T> comparator, int a, int b, int c) returns int
        let va = store[startIndex + a]
        let vb = store[startIndex + b]
        let vc = store[startIndex + c]

        if comparator.compare(va, vb) < 0
            if comparator.compare(vb, vc) < 0
                return b
            else if comparator.compare(va, vc) < 0
                return c
            else
                return a
        else
            if comparator.compare(va, vc) < 0
                return a
            else if comparator.compare(vb, vc) < 0
                return c
            else
                return b

    /** Optimized partition with median pivot */
    private function partition(Comparator<T> comparator, int low, int high, int pivotIndex) returns int
        let pivotValue = store[startIndex + pivotIndex]

        // Move pivot to end
        let temp = store[startIndex + pivotIndex]
        store[startIndex + pivotIndex] = store[startIndex + high]
        store[startIndex + high] = temp

        var storeIndex = low

        for i = low to high - 1
            if comparator.compare(store[startIndex + i], pivotValue) < 0
                let t = store[startIndex + storeIndex]
                store[startIndex + storeIndex] = store[startIndex + i]
                store[startIndex + i] = t
                storeIndex++

        // Move pivot to final position
        let t2 = store[startIndex + storeIndex]
        store[startIndex + storeIndex] = store[startIndex + high]
        store[startIndex + high] = t2

        return storeIndex

// ============================================================================
// UTILITY FUNCTIONS
// ============================================================================

public function asArrayList<T:>(vararg T ts) returns ArrayList<T>
    let al = new ArrayList<T>()
    for t in ts
        al.add(t)
    return al

// ============================================================================
// INTERFACES
// ============================================================================

public interface ArrayListPredicate<T:>
    function isTrueFor(T t) returns boolean

public interface ALItrClosure<T:>
    function run(T t)

public interface ArrayListUpdater<T:>
    function update(T t) returns T

public interface MapClosure<T:, Q:>
    function run(T t) returns Q

public interface FoldClosure<T:, Q:>
    function run(T t, Q q) returns Q

public interface Comparator<T:>
    function compare(T o1, T o2) returns int

// ============================================================================
// SPECIALIZED SORT FUNCTIONS
// ============================================================================

constant Comparator<int> intComparator = (i1, i2) -> i1 < i2 ? -1 : (i1 > i2 ? 1 : 0)
public function ArrayList<int>.sort()
    this.sortWith(intComparator)

constant Comparator<real> realComparator = (r1, r2) -> r1 < r2 ? -1 : (r1 > r2 ? 1 : 0)
public function ArrayList<real>.sort()
    this.sortWith(realComparator)

constant Comparator<string> stringComparator = (s1, s2) -> stringCompare(s1, s2)
public function ArrayList<string>.sort()
    this.sortWith(stringComparator)

// ============================================================================
// STRING OPERATIONS
// ============================================================================

/** Joins elements from a string list into one string using a separator */
public function ArrayList<string>.joinBy(string separator) returns string
    var joined = ""
    for i = 0 to this.size() - 1
        if i > 0
            joined += separator
        joined += this.get(i)
    return joined

/** Joins elements from a string list into one string */
public function ArrayList<string>.join() returns string
    return this.joinBy("")