Merge pull request #82 from lamweilun/dev/weilun/stack_and_queue

Stack and Queue implementation, with unit tests

5 files changed, 222 insertions, 0 deletions

diff --git a/std.zc b/std.zc
index 4843f47..b2b1bf1 100644
--- a/std.zc
+++ b/std.zc
@@ -14,3 +14,5 @@ import "./std/map.zc"
 import "./std/json.zc"
 import "./std/path.zc"
 import "./std/mem.zc"
+import "./std/stack.zc"
+import "./std/queue.zc"
diff --git a/std/queue.zc b/std/queue.zc
new file mode 100644
index 0000000..2bbcfaa
--- /dev/null
+++ b/std/queue.zc
@@ -0,0 +1,65 @@
+import "./option.zc"
+import "./mem.zc"
+
+struct Queue<T> {
+  data: T*;
+  len: usize;
+  cap: usize;
+}
+
+impl Queue<T> {
+  fn new() -> Queue<T> {
+    return Queue<T>{data: NULL, len: 0, cap: 0};
+  }
+
+  fn free(self) {
+    if (self.data) {
+      free(self.data);
+      self.data = NULL;
+    }
+    self.len = 0;
+  }
+
+  fn clone(self) -> Queue<T> {
+    var new_queue = Queue<T>::new();
+    new_queue.len = self.len;
+    new_queue.cap = self.cap;
+    new_queue.data = malloc(sizeof(T) * new_queue.cap);
+    memcpy(new_queue.data, self.data, sizeof(T) * new_queue.cap);
+    return new_queue;
+  }
+
+  fn push(self, value: T) {
+    if (!self.data) {
+      self.cap = 8;
+      self.data = malloc(sizeof(T) * self.cap);
+    }
+    if (self.len == self.cap) {
+      self.cap = self.cap * 2;
+      self.data = realloc(self.data, sizeof(T) * self.cap);
+    }
+
+    // Assigns it at the back of 
+    self.data[self.len] = value;
+    self.len = self.len + 1;
+  }
+
+  fn pop(self) -> Option<T> {
+    if (self.len > 0) {
+      var value = self.data[0];
+      self.len = self.len - 1;
+
+      // Shifts the data in the queue "forward"
+      memcpy(self.data, self.data + 1, sizeof(T) * self.len);
+
+      return Option<T>::Some(value);
+    }
+    return Option<T>::None();
+  }
+}
+
+impl Drop for Queue<T> {
+  fn drop(self) {
+    self.free();
+  }
+}
diff --git a/std/stack.zc b/std/stack.zc
new file mode 100644
index 0000000..3d7c3c5
--- /dev/null
+++ b/std/stack.zc
@@ -0,0 +1,59 @@
+import "./option.zc"
+import "./mem.zc"
+
+struct Stack<T> {
+  data: T*;
+  len: usize;
+  cap: usize;
+}
+
+impl Stack<T> {
+  fn new() -> Stack<T> {
+    return Stack<T>{data: NULL, len: 0, cap: 0};
+  }
+
+  fn free(self) {
+    if (self.data) {
+      free(self.data);
+      self.data = NULL;
+    }
+    self.len = 0;
+  }
+
+  fn clone(self) -> Stack<T> {
+    var new_stack = Stack<T>::new();
+    new_stack.len = self.len;
+    new_stack.cap = self.cap;
+    new_stack.data = malloc(sizeof(T) * new_stack.cap);
+    memcpy(new_stack.data, self.data, sizeof(T) * new_stack.cap);
+    return new_stack;
+  }
+
+  fn push(self, value: T) {
+    if (!self.data) {
+      self.cap = 8;
+      self.data = malloc(sizeof(T) * self.cap);
+    }
+    if (self.len == self.cap) {
+      self.cap = self.cap * 2;
+      self.data = realloc(self.data, sizeof(T) * self.cap);
+    }
+    self.data[self.len] = value;
+    self.len = self.len + 1;
+  }
+
+  fn pop(self) -> Option<T> {
+    if (self.len > 0) {
+      var value = self.data[self.len - 1];
+      self.len = self.len - 1;
+      return Option<T>::Some(value);
+    }
+    return Option<T>::None();
+  }
+}
+
+impl Drop for Stack<T> {
+  fn drop(self) {
+    self.free();
+  }
+}
diff --git a/tests/std/test_queue.zc b/tests/std/test_queue.zc
new file mode 100644
index 0000000..4d40c42
--- /dev/null
+++ b/tests/std/test_queue.zc
@@ -0,0 +1,48 @@
+import "std/queue.zc"
+
+test "Queue Push/Pop" {
+  print "Testing Queue Push/Pop";
+  var queue = Queue<i32>::new();
+  defer queue.free();
+
+  print "Popping on an empty queue without pushing anything prior"
+  var v = queue.pop();
+  assert(v.is_none(), "v should not have a valid value");
+
+  print "Pushing in three values..."
+  queue.push(123);
+  queue.push(456);
+  queue.push(789);
+  
+  v = queue.pop();
+  assert(v.is_some() && v.unwrap() == 123, "v's value should be 123");
+
+  v = queue.pop();
+  assert(v.is_some() && v.unwrap() == 456, "v's value should be 456");
+
+  v = queue.pop();
+  assert(v.is_some() && v.unwrap() == 789, "v's value should be 789");
+
+  print "Popping on an empty queue after pushing and popping three values"
+  v = queue.pop();
+  assert(v.is_none(), "v should not have a valid value");
+}
+
+test "Queue Clone" {
+  print "Testing Queue Cloning";
+  var queue = Queue<i32>::new();
+  defer queue.free();
+  queue.push(123);
+  var queue2 = queue.clone();
+  defer queue2.free();
+
+  var v = queue2.pop();
+  assert(v.is_some() && v.unwrap() == 123, "v's value should be 123");
+  v = queue2.pop();
+  assert(v.is_none(), "v should not have a valid value");
+
+  v = queue.pop();
+  assert(v.is_some() && v.unwrap() == 123, "v's value should be 123");
+  v = queue.pop();
+  assert(v.is_none(), "v should not have a valid value");
+}
diff --git a/tests/std/test_stack.zc b/tests/std/test_stack.zc
new file mode 100644
index 0000000..ecc9d3c
--- /dev/null
+++ b/tests/std/test_stack.zc
@@ -0,0 +1,48 @@
+import "std/stack.zc"
+
+test "Stack Push/Pop" {
+  print "Testing Stack Push/Pop";
+  var stack = Stack<i32>::new();
+  defer stack.free();
+
+  print "Popping on an empty stack without pushing anything prior"
+  var v = stack.pop();
+  assert(v.is_none(), "v should not have a valid value");
+
+  print "Pushing in three values..."
+  stack.push(123);
+  stack.push(456);
+  stack.push(789);
+  
+  v = stack.pop();
+  assert(v.is_some() && v.unwrap() == 789, "v's value should be 789");
+
+  v = stack.pop();
+  assert(v.is_some() && v.unwrap() == 456, "v's value should be 456");
+
+  v = stack.pop();
+  assert(v.is_some() && v.unwrap() == 123, "v's value should be 123");
+
+  print "Popping on an empty stack after pushing and popping three values"
+  v = stack.pop();
+  assert(v.is_none(), "v should not have a valid value");
+}
+
+test "Stack Clone" {
+  print "Testing Stack Cloning";
+  var stack = Stack<i32>::new();
+  defer stack.free();
+  stack.push(123);
+  var stack2 = stack.clone();
+  defer stack2.free();
+
+  var v = stack2.pop();
+  assert(v.is_some() && v.unwrap() == 123, "v's value should be 123");
+  v = stack2.pop();
+  assert(v.is_none(), "v should not have a valid value");
+
+  v = stack.pop();
+  assert(v.is_some() && v.unwrap() == 123, "v's value should be 123");
+  v = stack.pop();
+  assert(v.is_none(), "v should not have a valid value");
+}