From a60b9735a2ce49d4d8389db83ed53372b7f6c413 Mon Sep 17 00:00:00 2001
From: gingerBill <bill@gingerbill.org>
Date: Sat, 1 Jan 2022 15:46:22 +0000
Subject: Add `core:container/queue`

---
 core/container/queue/queue.odin | 205 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 205 insertions(+)
 create mode 100644 core/container/queue/queue.odin

(limited to 'core/container/queue/queue.odin')

diff --git a/core/container/queue/queue.odin b/core/container/queue/queue.odin
new file mode 100644
index 000000000..ff1e85fbd
--- /dev/null
+++ b/core/container/queue/queue.odin
@@ -0,0 +1,205 @@
+package container_queue
+
+import "core:builtin"
+import "core:runtime"
+
+// Dynamically resizable double-ended queue/ring-buffer
+Queue :: struct($T: typeid) {
+	data:   [dynamic]T,
+	len:    uint,
+	offset: uint,
+}
+
+DEFAULT_CAPACITY :: 16
+
+// Procedure to initialize a queue
+init :: proc(q: ^$Q/Queue($T), capacity := DEFAULT_CAPACITY, allocator := context.allocator) -> bool {
+	if q.data.allocator.procedure == nil {
+		q.data.allocator = allocator
+	}
+	clear(q)
+	return reserve(q, capacity)
+}
+
+// Procedure to initialize a queue from a fixed backing slice
+init_from_slice :: proc(q: ^$Q/Queue($T), backing: []T) -> bool {
+	clear(q)
+	q.data = transmute([dynamic]T)runtime.Raw_Dynamic_Array{
+		data = raw_data(backing),
+		len = builtin.len(backing),
+		cap = builtin.len(backing),
+		allocator = {procedure=runtime.nil_allocator_proc, data=nil},
+	}
+	return true
+}
+
+// Procedure to destroy a queue
+destroy :: proc(q: ^$Q/Queue($T)) {
+	delete(q.data)
+}
+
+// The length of the queue
+len :: proc(q: $Q/Queue($T)) -> int {
+	return int(q.len)
+}
+
+// The current capacity of the queue
+cap :: proc(q: $Q/Queue($T)) -> int {
+	return builtin.len(q.data)
+}
+
+// Remaining space in the queue (cap-len)
+space :: proc(q: $Q/Queue($T)) -> int {
+	return builtin.len(q.data) - int(q.len)
+}
+
+// Reserve enough space for at least the specified capacity
+reserve :: proc(q: ^$Q/Queue($T), capacity: int) -> bool {
+	if uint(capacity) > q.len {
+		return _grow(q, uint(capacity)) 
+	}
+	return true
+}
+
+
+get :: proc(q: ^$Q/Queue($T), #any_int i: int, loc := #caller_location) -> T {
+	runtime.bounds_check_error_loc(loc, i, builtin.len(q.data))
+
+	idx := (uint(i)+q.offset)%builtin.len(q.data)
+	return q.data[idx]
+}
+set :: proc(q: ^$Q/Queue($T), #any_int i: int, val: T, loc := #caller_location) {
+	runtime.bounds_check_error_loc(loc, i, builtin.len(q.data))
+	
+	idx := (uint(i)+q.offset)%builtin.len(q.data)
+	q.data[idx] = val
+}
+get_ptr :: proc(q: ^$Q/Queue($T), #any_int i: int, loc := #caller_location) -> ^T {
+	runtime.bounds_check_error_loc(loc, i, builtin.len(q.data))
+	
+	idx := (uint(i)+q.offset)%builtin.len(q.data)
+	return &q.data[idx]
+}
+
+// Push an element to the back of the queue
+push_back :: proc(q: ^$Q/Queue($T), elem: T) -> bool {
+	if space(q^) == 0 {
+		_grow(q) or_return
+	}
+	q.data[q.len] = elem
+	q.len += 1
+	return true
+}
+
+// Push an element to the front of the queue
+push_front :: proc(q: ^$Q/Queue($T), elem: T) -> bool {
+	if space(q^) == 0 {
+		_grow(q) or_return
+	}	
+	q.offset = uint(q.offset - 1 + builtin.len(q.data)) % builtin.len(q.data)
+	q.len += 1
+	q.data[q.offset] = elem
+	return true
+}
+
+
+// Pop an element from the back of the queue
+pop_back :: proc(q: ^$Q/Queue($T), loc := #caller_location) -> (elem: T) {
+	assert(condition=q.len > 0, loc=loc)
+	q.len -= 1
+	idx := (q.offset+uint(q.len))%builtin.len(q.data)
+	elem = q.data[idx]
+	return
+}
+// Safely pop an element from the back of the queue
+pop_back_safe :: proc(q: ^$Q/Queue($T)) -> (elem: T, ok: bool) {
+	if q.len > 0 {
+		q.len -= 1
+		idx := (q.offset+uint(q.len))%builtin.len(q.data)
+		elem = q.data[idx]
+		ok = true
+	}
+	return
+}
+
+// Pop an element from the front of the queue
+pop_front :: proc(q: ^$Q/Queue($T), loc := #caller_location) -> (elem: T) {
+	assert(condition=q.len > 0, loc=loc)
+	elem = q.data[q.offset]
+	q.len -= 1
+	return
+}
+// Safely pop an element from the front of the queue
+pop_front_safe :: proc(q: ^$Q/Queue($T)) -> (elem: T, ok: bool) {
+	if q.len > 0 {
+		elem = q.data[q.offset]
+		q.len -= 1
+		ok = true
+	}
+	return
+}
+
+// Push multiple elements to the front of the queue
+push_back_elems :: proc(q: ^$Q/Queue($T), elems: ..T) -> bool {
+	n := uint(builtin.len(elems))
+	if space(q^) < int(n) {
+		_grow(q, q.len + n) or_return
+	}
+	
+	sz := uint(builtin.len(q.data))
+	insert_from := (q.offset + q.len) % sz
+	insert_to := n
+	if insert_from + insert_to > sz {
+		insert_to = sz - insert_from
+	}
+	copy(q.data[insert_from:], elems[:insert_to])
+	copy(q.data[:insert_from], elems[insert_to:])
+	q.len += n
+	return true
+}
+
+// Consume `n` elements from the front of the queue
+consume_front :: proc(q: ^$Q/Queue($T), n: int, loc := #caller_location) {
+	assert(condition=int(q.len) >= n, loc=loc)
+	if n > 0 {
+		nu := uint(n)
+		q.offset = (q.offset + nu) % builtin.len(q.data)
+		q.len -= nu	
+	}
+}
+
+// Consume `n` elements from the back of the queue
+consume_back :: proc(q: ^$Q/Queue($T), n: int, loc := #caller_location) {
+	assert(condition=int(q.len) >= n, loc=loc)
+	if n > 0 {
+		q.len -= uint(n)
+	}
+}
+
+
+
+append_elem  :: push_back
+append_elems :: push_back_elems
+push   :: proc{push_back, push_back_elems}
+append :: proc{push_back, push_back_elems}
+
+
+// Clear the contents of the queue
+clear :: proc(q: ^$Q/Queue($T)) {
+	q.len = 0
+	q.offset = 0
+}
+
+
+// Internal growinh procedure
+_grow :: proc(q: ^$Q/Queue($T), min_capacity: uint = 0) -> bool {
+	new_capacity := max(min_capacity, uint(8), uint(builtin.len(q.data))*2)
+	n := uint(builtin.len(q.data))
+	builtin.resize(&q.data, int(new_capacity)) or_return
+	if q.offset + q.len > n {
+		diff := n - q.offset
+		copy(q.data[new_capacity-diff:], q.data[q.offset:][:diff])
+		q.offset += new_capacity - n
+	}
+	return true
+}
-- 
cgit v1.2.3


From 6cf5371d7d55038c0d0789c240813e1be08c0107 Mon Sep 17 00:00:00 2001
From: CiD- <jkercher43@gmail.com>
Date: Fri, 14 Jan 2022 10:17:49 -0500
Subject: fix push_back and pop_front

---
 core/container/queue/queue.odin | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

(limited to 'core/container/queue/queue.odin')

diff --git a/core/container/queue/queue.odin b/core/container/queue/queue.odin
index ff1e85fbd..feca6934c 100644
--- a/core/container/queue/queue.odin
+++ b/core/container/queue/queue.odin
@@ -86,7 +86,8 @@ push_back :: proc(q: ^$Q/Queue($T), elem: T) -> bool {
 	if space(q^) == 0 {
 		_grow(q) or_return
 	}
-	q.data[q.len] = elem
+	idx := (q.offset+uint(q.len))%builtin.len(q.data)
+	q.data[idx] = elem
 	q.len += 1
 	return true
 }
@@ -126,6 +127,7 @@ pop_back_safe :: proc(q: ^$Q/Queue($T)) -> (elem: T, ok: bool) {
 pop_front :: proc(q: ^$Q/Queue($T), loc := #caller_location) -> (elem: T) {
 	assert(condition=q.len > 0, loc=loc)
 	elem = q.data[q.offset]
+	q.offset = (q.offset+1)%builtin.len(q.data)
 	q.len -= 1
 	return
 }
@@ -133,6 +135,7 @@ pop_front :: proc(q: ^$Q/Queue($T), loc := #caller_location) -> (elem: T) {
 pop_front_safe :: proc(q: ^$Q/Queue($T)) -> (elem: T, ok: bool) {
 	if q.len > 0 {
 		elem = q.data[q.offset]
+		q.offset = (q.offset+1)%builtin.len(q.data)
 		q.len -= 1
 		ok = true
 	}
-- 
cgit v1.2.3


From fb86c23dbd4c6e9dc82fcc72deb1ad59af5e07f0 Mon Sep 17 00:00:00 2001
From: gingerBill <bill@gingerbill.org>
Date: Tue, 25 Jan 2022 16:41:31 +0000
Subject: Keep -vet happy

---
 core/container/queue/queue.odin | 1 +
 1 file changed, 1 insertion(+)

(limited to 'core/container/queue/queue.odin')

diff --git a/core/container/queue/queue.odin b/core/container/queue/queue.odin
index feca6934c..8ca3a85ac 100644
--- a/core/container/queue/queue.odin
+++ b/core/container/queue/queue.odin
@@ -2,6 +2,7 @@ package container_queue
 
 import "core:builtin"
 import "core:runtime"
+_ :: runtime
 
 // Dynamically resizable double-ended queue/ring-buffer
 Queue :: struct($T: typeid) {
-- 
cgit v1.2.3