I failed to test for the empty case:
diff --git a/src/algebra/bags.spad b/src/algebra/bags.spad
index cda2d62..8237ecf 100644
--- a/src/algebra/bags.spad
+++ b/src/algebra/bags.spad
@@ -135,7 +135,8 @@ Queue(S : SetCategory) : QueueAggregate S with
-- QueueAggregate's exclusive operations
enqueue!(e, q) ==
- q.rear := cons(e, q.rear)
+ if empty? q then q.front := [e]
+ else q.rear := cons(e, q.rear)
e
dequeue! q ==
@@ -240,9 +241,9 @@ Dequeue(S : SetCategory) : DequeueAggregate S with
first d.rear
reverse! d ==
- tmp := d.front
- d.front := d.rear
- d.rear := tmp
+ empty? d => d
+ empty? d.rear => d
+ (d.front, d.rear) := (d.rear, d.front)
d
-- StackAggregate's exclusive operations
> but it is not clear if we will get any practical gain in speed
> (but extractBottom! in Dequeue is still O(n)).
As you said, for small numbers of elements, my version
will not get more slower; for large numbers of elements,
my version is O(1) for insertion and extraction for both
ends while current version is O(n) for some operations.
What's the point of Dequeue if it can't inset/extract in O(1)?
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
