py/objdeque: Expand implementation to be doubly-ended and support iter.

Add `pop()`, `appendleft()`, and `extend()` methods, support iteration
and indexing, and initializing from an existing sequence.

Iteration and indexing (subscription) have independent configuration flags
to enable them.  They are enabled by default at the same level that
collections.deque is enabled (the extra features level).

Also add tests for checking new behavior.

Signed-off-by: Damien George <damien@micropython.org>

4 files changed, 147 insertions, 10 deletions

diff --git a/tests/basics/deque1.py b/tests/basics/deque1.py
index 8b7874e2b..188069bcb 100644
--- a/tests/basics/deque1.py
+++ b/tests/basics/deque1.py
@@ -63,3 +63,52 @@ try:
     ~d
 except TypeError:
     print("TypeError")
+
+
+# Same tests, but now with pop() and appendleft()
+
+d = deque((), 2)
+print(len(d))
+print(bool(d))
+
+try:
+    d.popleft()
+except IndexError:
+    print("IndexError")
+
+print(d.append(1))
+print(len(d))
+print(bool(d))
+print(d.popleft())
+print(len(d))
+
+d.append(2)
+print(d.popleft())
+
+d.append(3)
+d.append(4)
+print(len(d))
+print(d.popleft(), d.popleft())
+try:
+    d.popleft()
+except IndexError:
+    print("IndexError")
+
+d.append(5)
+d.append(6)
+d.append(7)
+print(len(d))
+print(d.popleft(), d.popleft())
+print(len(d))
+try:
+    d.popleft()
+except IndexError:
+    print("IndexError")
+
+d = deque((), 2)
+d.appendleft(1)
+d.appendleft(2)
+d.appendleft(3)
+d.appendleft(4)
+d.appendleft(5)
+print(d.pop(), d.pop())
\ No newline at end of file
diff --git a/tests/basics/deque2.py b/tests/basics/deque2.py
index 80fcd6678..743c04078 100644
--- a/tests/basics/deque2.py
+++ b/tests/basics/deque2.py
@@ -6,18 +6,50 @@ except ImportError:
     print("SKIP")
     raise SystemExit
 
+# Initial sequence is supported
+d = deque([1, 2, 3], 10)
+
+# iteration over sequence
+for x in d:
+    print(x)
+
+# Iterables larger than maxlen have the beginnings removed, also tests
+# iteration through conversion to list
+d = deque([1, 2, 3, 4, 5], 3)
+print(list(d))
+
+# Empty iterables are also supported
+deque([], 10)
+
+# Extending deques with iterables
+d.extend([6, 7])
+print(list(d))
+
+# Accessing queue elements via index
+d = deque((0, 1, 2, 3), 5)
+print(d[0], d[1], d[-1])
+
+# Writing queue elements via index
+d[3] = 5
+print(d[3])
+
+# Accessing indices out of bounds raises IndexError
+try:
+    d[4]
+except IndexError:
+    print("IndexError")
 
-# Initial sequence is not supported
 try:
-    deque([1, 2, 3], 10)
-except ValueError:
-    print("ValueError")
+    d[4] = 0
+except IndexError:
+    print("IndexError")
 
-# Not even empty list, only empty tuple
+# Removing elements with del is not supported, fall back on mp_obj_subscr() error message
 try:
-    deque([], 10)
-except ValueError:
-    print("ValueError")
+    del d[0]
+except TypeError:
+    print("TypeError")
+
 
 # Only fixed-size deques are supported, so length arg is mandatory
 try:
@@ -32,6 +64,11 @@ try:
 except IndexError:
     print("IndexError")
 
+try:
+    d.pop()
+except IndexError:
+    print("IndexError")
+
 print(d.append(1))
 print(d.popleft())
 
@@ -46,6 +83,11 @@ try:
 except IndexError as e:
     print(repr(e))
 
+try:
+    d.pop()
+except IndexError as e:
+    print(repr(e))
+
 d.append(5)
 d.append(6)
 print(len(d))
@@ -53,6 +95,12 @@ try:
     d.append(7)
 except IndexError as e:
     print(repr(e))
+
+try:
+    d.appendleft(8)
+except IndexError as e:
+    print(repr(e))
+
 print(len(d))
 
 print(d.popleft(), d.popleft())
diff --git a/tests/basics/deque2.py.exp b/tests/basics/deque2.py.exp
index 3df8acf40..71f74ed6c 100644
--- a/tests/basics/deque2.py.exp
+++ b/tests/basics/deque2.py.exp
@@ -1,14 +1,25 @@
-ValueError
-ValueError
+1
+2
+3
+[3, 4, 5]
+[5, 6, 7]
+0 1 3
+5
+IndexError
+IndexError
 TypeError
+TypeError
+IndexError
 IndexError
 None
 1
 2
 3 4
 IndexError('empty',)
+IndexError('empty',)
 2
 IndexError('full',)
+IndexError('full',)
 2
 5 6
 0
diff --git a/tests/basics/deque_slice.py b/tests/basics/deque_slice.py
new file mode 100644
index 000000000..367aeea3a
--- /dev/null
+++ b/tests/basics/deque_slice.py
@@ -0,0 +1,29 @@
+try:
+    from collections import deque
+except ImportError:
+    print("SKIP")
+    raise SystemExit
+
+d = deque((), 10)
+
+d.append(1)
+d.append(2)
+d.append(3)
+
+# Index slicing for reads is not supported in CPython
+try:
+    d[0:1]
+except TypeError:
+    print("TypeError")
+
+# Index slicing for writes is not supported in CPython
+try:
+    d[0:1] = (-1, -2)
+except TypeError:
+    print("TypeError")
+
+# Index slicing for writes is not supported in CPython
+try:
+    del d[0:1]
+except TypeError:
+    print("TypeError")