from memory.unsafe_pointer import (
    UnsafePointer,
    move_pointee,
    move_from_pointee,
    initialize_pointee_copy,
    initialize_pointee_move,
    destroy_pointee,
)
from testing import assert_true, assert_false


trait QType(
    CollectionElement,
    EqualityComparable,
    RepresentableCollectionElement,
):
    pass


struct Queue[T: QType]:
    var data: UnsafePointer[T]
    var size: Int
    var capacity: Int

    fn __init__(inout self):
        self.data = UnsafePointer[T]()
        self.size = 0
        self.capacity = 0

    fn __copyinit__(inout self, existing: Self):
        self = Self()
        for i in range(len(existing)):
            self.enqueue(existing.data[i])

    fn __moveinit__(inout self, owned existing: Self):
        self.data = existing.data
        self.size = existing.size
        self.capacity = existing.capacity

    fn __del__(owned self):
        for i in range(len(self)):
            destroy_pointee(self.data   i)
        self.data.free()  # free will be called on an advanced pointer

    fn enqueue(inout self, owned value: T):
        if self.size >= self.capacity:
            self._realloc(max(1, self.capacity * 2))
        initialize_pointee_move(self.data   self.size, value^)
        self.size  = 1

    fn dequeue(inout self) raises -> T:
        if not self:
            raise "Dequeuing empty queue, aborting..."

        var value = move_from_pointee(self.data)
        if self.data:
            self.data.free()
        self.data = self.data   1  # this is also troublesome
        self.size -= 1
        return value^

    fn __len__(self) -> Int:
        return self.size

    fn __bool__(self) -> Bool:
        return len(self) > 0

    fn __str__(self) -> String:
        var result: String = "[ "
        for i in range(len(self)):
            result  = repr(self.data[i])   ", "
        result  = "]"
        return result

    fn __repr__(self) -> String:
        return str(self)

    fn _realloc(inout self, new_capcity: Int):
        var new_data = UnsafePointer[T].alloc(new_capcity)
        for i in range(self.size):
            move_pointee(src=self.data   i, dst=new_data   i)
        self.data.free()
        self.data = new_data
        self.capacity = new_capcity


def main():
    var p = Queue[Int]()
    p.enqueue(0)
    p.enqueue(1)
    _ = p.dequeue()

    var q = Queue[Int]()
    for i in range(10):
        q.enqueue(i)
    print(q)  # prints [ 0, 1, [ 03, 4, 5, 6, 7, 8, 9, ]