Test the deque more and fix uncovered off-by-one bug.

2 files changed, 43 insertions, 18 deletions

diff --git a/src/lib/deque.rs b/src/lib/deque.rs
index 24a03ed0..bd42d7cb 100644
--- a/src/lib/deque.rs
+++ b/src/lib/deque.rs
@@ -79,7 +79,7 @@ fn create[T]() -> t[T] {
       if (lo == hi) {
         elts = grow[T](nelts, oldlo, elts);
         lo = _vec.len[cell[T]](elts) - 1u;
-        hi = nelts - 1u;
+        hi = nelts;
       }
 
       elts.(lo as int) = util.some[T](t);
@@ -87,15 +87,14 @@ fn create[T]() -> t[T] {
     }
 
     fn add_back(&T t) {
-      hi = (hi + 1u) % _vec.len[cell[T]](elts);
-
-      if (lo == hi) {
+      if (lo == hi && nelts != 0u) {
         elts = grow[T](nelts, lo, elts);
         lo = 0u;
         hi = nelts;
       }
 
       elts.(hi as int) = util.some[T](t);
+      hi = (hi + 1u) % _vec.len[cell[T]](elts);
       nelts += 1u;
     }
 
@@ -111,15 +110,14 @@ fn create[T]() -> t[T] {
     }
 
     fn pop_back() -> T {
-      let T t = get[T](elts, hi);
-      elts.(hi as int) = util.none[T]();
-
       if (hi == 0u) {
         hi = _vec.len[cell[T]](elts) - 1u;
       } else {
         hi -= 1u;
       }
 
+      let T t = get[T](elts, hi);
+      elts.(hi as int) = util.none[T]();
       ret t;
     }
 
@@ -128,7 +126,7 @@ fn create[T]() -> t[T] {
     }
 
     fn peek_back() -> T {
-      ret get[T](elts, hi);
+      ret get[T](elts, hi - 1u);
     }
 
     fn get(int i) -> T {
diff --git a/src/test/run-pass/lib-deque.rs b/src/test/run-pass/lib-deque.rs
index 244092da..003fb9a2 100644
--- a/src/test/run-pass/lib-deque.rs
+++ b/src/test/run-pass/lib-deque.rs
@@ -3,15 +3,42 @@
 use std;
 import std.deque;
 
+fn test_simple() {
+  let deque.t[int] d = deque.create[int]();
+  check (d.size() == 0u);
+  d.add_front(17);
+  d.add_front(42);
+  d.add_back(137);
+  check (d.size() == 3u);
+  d.add_back(137);
+  check (d.size() == 4u);
+
+  log d.peek_front();
+  check (d.peek_front() == 42);
+
+  log d.peek_back();
+  check (d.peek_back() == 137);
+
+  let int i = d.pop_front();
+  log i;
+  check (i == 42);
+
+  i = d.pop_back();
+  log i;
+  check (i == 137);
+
+  i = d.pop_back();
+  log i;
+  check (i == 137);
+
+  i = d.pop_back();
+  log i;
+  check (i == 17);
+
+  /* FIXME (issue #138):  Test d.get() once it no longer causes
+   * segfault. */
+}
+
 fn main() {
-  let deque.t[int] d1 = deque.create[int]();
-  check (d1.size() == 0u);
-  d1.add_front(17);
-  d1.add_front(42);
-  d1.add_back(137);
-  check (d1.size() == 3u);
-  d1.add_back(137);
-  check (d1.size() == 4u);
-  /* FIXME (issue #133):  We should check that the numbers come back
-   * to us correctly once the deque stops zeroing them out. */
+  test_simple();
 }