use mem
use gc

+ class Array[T: PROP_TYPE] {
    ~ size: uint
    ~ length: uint (0)
    ~ data: gc:GcPtr

    + static fn new(start_size: uint (2)) SELF {
        if start_size < 2 {
            start_size = 2
        }
        let d = gc:alloc(start_size * size_of(T))

        let res = SELF {
            size: start_size
            data: d
        }
        return res
    }

    ////////////////
    // Macros
    ////////////////

    + macro "{" suggest(T) repeat(items, V:v1 ws optional(","), "}") <{
        let a = SELF.new()
        #loop macro_values items as item
        a.append(item.v1)
        #end
        return a
    }

    ////////////////
    // Append
    ////////////////

    + mut fn append_copy(item: T, unique: bool (false)) SELF {
        return this.copy().append(item, unique)
    }

    + mut fn append(item: T, unique: bool (false)) SELF {
        if unique {
            this.index_of(item) ! {
                return this.append(item, false)
            }
            return this
        }

        let size = this.size
        let length = this.length
        this.fit_index(length)
        let data = this.data

        @property_init(this, @ptrv(data, T, length), item)

        this.length = length + 1

        return this
    }

    + mut fn append_many_copy(items: SELF) SELF {
        return this.copy().append_many(items)
    }

    + mut fn append_many(items: SELF) SELF {
        each items as item {
            this.append(item)
        }
        return this
    }

    ////////////////
    // Prepend
    ////////////////

    + mut fn prepend_copy(item: T, unique: bool (false)) SELF {
        return this.copy().prepend(item, unique)
    }

    + mut fn prepend(item: T, unique: bool (false)) SELF {
        if unique {
            this.index_of(item) ! {
                return this.prepend(item, false)
            }
            return this
        }

        let size = this.size
        let length = this.length
        this.fit_index(length)
        let data = this.data

        let to_pos = length
        while to_pos > 0 {
            @ptrv(data, T, to_pos) = @ptrv(data, T, to_pos - 1)
            to_pos--
        }

        @property_init(this, @ptrv(data, T, 0), item)

        this.length = length + 1
        return this
    }

    + fn prepend_many_copy(items: SELF) SELF {
        return items.copy().append_many(this)
    }

    + mut fn prepend_many(items: SELF) SELF {
        let ilen = items.length
        if ilen == 0 : return this
        // Adjust size
        let new_len = this.length + ilen
        this.fit_index(new_len - 1)
        let data = this.data
        let items_data = items.data

        let bytes = ilen * size_of(T)
        mem:copy(data, @offset(data, u8, bytes), bytes)

        let i : uint = 0
        while i < ilen {
            @property_init(this, @ptrv(data, T, i), @ptrv(items_data, T, i))
            i++
        }

        this.length += ilen
        return this
    }

    ////////////////
    // 
    ////////////////

    + fn merge(items: SELF) SELF $add {
        return this.copy().append_many(items)
    }

    + fn intersect(with: SELF) SELF {
        let len = this.length
        if with.length < len : len = with.length
        let result = SELF.new(len)
        each this as item {
            if with.contains(item) : result.append(item, true)
        }
        return result
    }

    + fn range(start: uint, end: uint, inclusive: bool (true)) SELF {
        end = end + (inclusive).to(uint)
        if start >= end : return SELF.new()
        return this.part(start, end-start)
    }

    + fn part(start: uint, amount: uint) SELF {
        if start >= this.length : return SELF.new()
        let remain = this.length - start
        if amount > remain : amount = remain
        let new = SELF.new(amount)
        let from = this.data.@cast(ptr) + start * size_of(T)
        mem:copy(from, new.data, amount * size_of(T))
        new.length = amount
        #if is_gc_type(T)
        each new as v, i {
            @property_init(new, @ptrv(new.data, T, i), v)
        }
        #end
        return new
    }

    + mut fn fit_index(index: uint) {
        let size = this.size
        if index >= size {
            while index >= size : size *= 2
            this.increase_size(size)
        }
    }

    + mut fn increase_size(new_size: uint) gc:GcPtr {
        let data = this.data
        let size = this.size
        if size >= new_size : return data

        let new_data = gc:alloc(new_size * size_of(T))
        mem:copy(data, new_data, size * size_of(T))

        this.data = new_data
        this.size = new_size

        return new_data
    }

    + fn get(index: uint) T !not_found $offset {
        if index >= this.length : throw not_found
        return @property_get(@ptrv(this.data, T, index))
    }

    + mut fn set(index: uint, value: T) !out_of_range $offset_assign {
        if index > this.length : throw out_of_range
        if index == this.length { this.append(value); return }
        @property_update(this, @ptrv(this.data, T, index), value)
    }

    + mut fn set_expand(index: uint, value: T, filler_value: T) {
        this.fit_index(index)
        let len = this.length
        if index >= len : this.length = index + 1
        let data = this.data

        // fill
        let i = len
        while i < index {
            @property_init(this, @ptrv(data, T, i++), filler_value)
        }

        // Set index
        if index < len {
            @property_update(this, @ptrv(data, T, index), value)
        } else {
            @property_init(this, @ptrv(data, T, index), value)
        }
    }

    + fn contains(value: T) bool {
        this.index_of(value) ! return false
        return true
    }

    + fn remove_copy(index: uint) SELF {
        return this.copy().remove(index)
    }

    + mut fn remove(index: uint) SELF {
        let len = this.length
        if index >= len : return this
        let data : ptr = this.data
        let after_count = len - (index + 1)

        @property_clear(this, @ptrv(data, T, index))

        if after_count > 0 {
            mem:copy(data + (index + 1) * size_of(T), data + index * size_of(T), after_count * size_of(T))
        }

        this.length--
        return this
    }

    + mut fn remove_value_copy(value: T) SELF {
        let copy = this.copy()
        return copy.remove_value(value) ! return copy
    }

    + mut fn remove_value(value: T) SELF {
        let index = this.index_of(value) ! return this
        this.remove(index)
        return this
    }

    + mut fn pop_last() T !empty {
        if this.length > 0 {

            let index = --this.length
            let data = this.data

            let item = @property_get(@ptrv(data, T, index))
            @property_clear(this, @ptrv(data, T, index))

            return item
        }
        throw empty
    }
    + mut fn pop_first() T !empty {
        if this.length > 0 {

            let data : ptr = this.data

            let item = @property_get(@ptrv(data, T, 0))
            @property_clear(this, @ptrv(data, T, 0))

            this.length--
            mem:copy(data + size_of(T), data, this.length * size_of(T))

            return item
        }
        throw empty
    }

    + mut fn swap(index_a: uint, index_b: uint) {
        let len = this.length
        if index_a >= len {
            return
        }
        if index_b >= len {
            return
        }
        let data = this.data
        let a = @ptrv(data, T, index_a)
        let b = @ptrv(data, T, index_b)
        @ptrv(data, T, index_a) = b
        @ptrv(data, T, index_b) = a
    }

    + fn index_of(item: T) uint !not_found {
        let index : uint = 0
        let adr = this.data
        let len = this.length
        while index < len {
            let x = @property_get(@ptrv(adr, T, index))
            if x == item : return index
            index++
        }
        throw not_found
    }

    + mut fn clear() SELF {
        #if is_gc_type(T)
        let data = this.data
        let i = this.length
        while i-- > 0 : @property_clear(this, @ptrv(data, T, i))
        #end

        this.length = 0
        this.data = gc:alloc(2 * size_of(T))
        this.size = 2
        return this
    }

    + fn sort_copy(func: ?fn(T, T)(bool) (null)) SELF {
        return this.copy().sort(func)
    }

    + mut fn sort(func: ?fn(T, T)(bool) (null)) SELF {
        let len_ = this.length
        if len_ < 2 : return this

        let v = true
        let i : uint = 0
        let len = len_ - 1
        while i < len && v {
            v = false
            let j : uint = 0
            let until = len - i
            while j < until {
                let item = this.get(j) ! { break }
                let next = this.get(j + 1) ! { break }
                if isset(func) {
                    if func(item, next) {
                        this.swap(j, j + 1)
                        v = true
                    }
                } else if item > next {
                    this.swap(j, j + 1)
                    v = true
                }
                j++
            }
            i++
        }
        return this
    }

    + mut fn reverse_copy() SELF {
        return this.copy().reverse()
    }

    + mut fn reverse() SELF {
        let len_ = this.length
        if len_ < 2 : return this
        let last = len_ - 1
        let first : uint = 0
        while len_ > 1 {
            this.swap(first, last)
            first++
            last--
            len_ -= 2
        }
        return this
    }

    + fn equal(array: SELF) bool $eq {
        if this.length != array.length : return false
        each this as v, i {
            let v2 = array.get(i) ! return false
            if v != v2 : return false
        }
        return true
    }

    + fn equal_ignore_order(array: SELF) bool {
        if this.length != array.length : return false
        let copy = array.copy()
        each this as v, i {
            let i2 = copy.index_of(v) ! return false
            copy.remove(i2)
        }
        return true
    }

    ////////////////
    // Filtering
    ////////////////

    #if is_nullable_type(T)
    - static fn filter_null(i: T) bool {
        return !isset(i)
    }
    #end

    + fn filter_copy(func: ?fn(T)(bool) (null)) SELF {
        return this.copy().filter(func)
    }

    + fn filter(func: ?fn(T)(bool) (null)) SELF {
        if this.length == 0 : return this
        if !isset(func) {
            #if type_has_method(T, default_array_filter)
            func = T.default_array_filter
            #elif is_nullable_type(T)
            func = SELF.filter_null
            #else
            return this
            #end
        }

        let result : ?SELF = null
        let removals : uint = 0
        each this as v, i {
            if func(v) {
                if !isset(result) : result = this.copy()
                result.remove(i - removals++)
            }
        }
        if !isset(result) : return this
        return result
    }

    + fn unique_copy() SELF {
        let result = SELF.new()
        each this as item : if !result.contains(item) : result.append(item)
        return result
    }

    + fn unique() SELF {
        let insert_i : uint = 0
        let data = this.data
        each this as find, i {
            let found = false
            each this as item, o {
                if o == insert_i : break
                if find == item {
                    found = true
                    break
                }
            }
            if found : @property_clear(this, @ptrv(data, T, i))
            else : @ptrv(data, T, insert_i++) = find
        }
        this.length = insert_i
        return this
    }

    ////////////////
    // Exceptions
    ////////////////

    #if is_type_of_class(T, String)
    + fn join(divider: String) String {
        let str = ""
        let count : uint = 0
        each this as part, i {
            #if is_nullable_type(T)
            if !isset(part) : continue
            #end
            if count++ > 0 : str += divider
            str += part
        }
        return str
    }
    #end

    ////////////////
    // Internals
    ////////////////

    + fn copy() SELF {
        let arr = SELF.new(this.length)
        each this as item {
            arr.append(item)
        }
        return arr
    }

    fn each_get(index: uint) T !end {
        let v = this.get(index) ! throw end
        return v
    }

    ////////////////
    // Gc
    ////////////////

    #if is_gc_type(T)

        fn gc_action(action: fnRef(ptr, ptr)()) {
            let data = this.data
            let x = this.length
            while x-- > 0 {
                action(this, @offset(data, ptr, x))
            }
        }

    #end

    fn clone() SELF {
        let new = SELF.new(this.size)
        each this as item, i {
            new.append(item)
        }
        return new.@cast(SELF)
    }
}
