is_empty :: (deque: Deque) -> bool {
    return head == tail;
}

Deque :: struct(Value_Type: Type) {
    items: []Value_Type;

    count: s64 = 0;
    head: s64 = 0;
    tail: s64 = 0;

    allocator: Allocator;

    SIZE_MIN :: 16;
}


Basic :: #import "Basic";
Hash_Table :: #import "Hash_Table";

init :: (deque: *Deque) {
    Basic.remember_allocators(deque);
    resize(deque);
}

deinit :: (deque: *Deque) {
    array_free(deque.items);
}

reset :: (deque: *Deque) {
    count = 0;
    head = 0;
    tail = 0;
}

resize :: (using deque: *Deque, elements_to_allocate: s64 = 0) {

    if elements_to_allocate == 0  elements_to_allocate = SIZE_MIN;
    n := Hash_Table.next_power_of_two(elements_to_allocate);

    deque.items = Basic.NewArray(n, deque.Value_Type, false,, deque.allocator);
}

double_capacty :: (deque: *Deque) {
    assert(deque.head == deque.tail);

    head          := deque.head;
    num_elements  := deque.items.count;
    right_of_head := num_elements - head;
    new_capacity  := num_elements << 1;

    if new_capacity <= 0  new_capacity = deque.SIZE_MIN;

    elements := Basic.NewArray(new_capacity, deque.Value_Type, false,, deque.allocator);

    if num_elements > 0 {
        memcpy(*elements[right_of_head], deque.items.data, head * size_of(deque.Value_Type));
        memcpy(elements.data, *deque.items[head], right_of_head * size_of(deque.Value_Type));
        Basic.free(deque.items.data,, deque.allocator);
    }
    deque.head = 0;
    deque.tail = num_elements;
    deque.items = elements;
}

deque_add_first :: (using deque: *Deque, item: deque.Value_Type) {
    if items.count == 0 {
        init(deque);
    }

    head = (head - 1) & (items.count - 1);
    items[head] = item;
    count += 1;

    if head == tail  double_capacty(deque);

}

deque_add_last :: (using deque: *Deque, item: deque.Value_Type) {
    if items.count == 0 {
        init(deque);
    }

    items[tail] = item;

    tail = (tail + 1) & (items.count - 1);

    count += 1;

    if tail == head  double_capacty(deque);

}

deque_remove_last :: (using deque: *Deque) -> (value: deque.Value_Type, success: bool) {
    if head == tail {
        dummy: deque.Value_Type = ---;
        return dummy, false;
    }
    tail = (tail + 1) & (items.count - 1);
    count -= 1;
    return items[tail], true;
}

deque_remove_first :: (using deque: *Deque) -> (value: deque.Value_Type, success: bool) {
    if head == tail {
        dummy: deque.Value_Type = ---;
        return dummy, false;
    }
    result := items[head];
    head = (head + 1) & (items.count - 1);
    count -= 1;

    return result, true;
}