Currently the Rep of Queue is List, thus enqueue! an
element into the end of list is O(n) not O(1):
(1) -> )time on
(1) -> x := queue (new(10000000,1)$List Integer);
Type:
Queue(Integer)
Time: 0.00 (IN) + 2.10 (EV) + 0.02 (OT) = 2.12
sec
(2) -> enqueue!(4,x)
(2) 4
Type:
PositiveInteger
Time: 0.07 (EV) + 0.00 (OT) = 0.07
sec
(3) -> dequeue! x
(3) 1
Type:
PositiveInteger
Time: 0.00 (IN) + 0.00 (OT) = 0.00
sec
So I changed the Rep, the patch is here for you to review.
If this patch is OK, I'll do the similar change for Dequeue.
diff --git a/src/algebra/aggcat.spad b/src/algebra/aggcat.spad
index 14395f2..81fc4cb 100644
--- a/src/algebra/aggcat.spad
+++ b/src/algebra/aggcat.spad
@@ -321,7 +321,7 @@
rotate! : % -> %
++ rotate! q rotates queue q so that the element at the front of
++ the queue goes to the back of the queue.
- ++ Note: rotate! q is equivalent to enqueue!(dequeue!(q)).
+ ++ Note: rotate! q is equivalent to insert!(dequeue!(q), q).
front : % -> S
++ front(q) returns the element at the front of the queue.
++ The queue q is unchanged by this operation.
@@ -330,6 +330,13 @@
++ back(q) returns the element at the back of the queue.
++ The queue q is unchanged by this operation.
++ Error: if q is empty.
+ add
+ insert!(e, q) == (enqueue!(e, q); q)
+ extract! q == dequeue! q
+ rotate! q ==
+ empty? q => q
+ insert!(dequeue! q, q)
+
)abbrev category DQAGG DequeueAggregate
++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks
diff --git a/src/algebra/bags.spad b/src/algebra/bags.spad
index d6365a7..e4ce733 100644
--- a/src/algebra/bags.spad
+++ b/src/algebra/bags.spad
@@ -109,33 +109,49
++ Examples:
++ References:
++ Description:
-
-++ Linked List implementation of a Queue
--% Dequeue and Heap data types
Queue(S : SetCategory) : QueueAggregate S with
queue : List S -> %
++ queue([x, y, ..., z]) creates a queue with first (top)
++ element x, second element y, ..., and last (bottom) element z.
- == Stack S add
- Rep := Reference List S
- lastTail==> LAST$Lisp
+ == add
+ Rep := Record(front: List S, rear: List S)
+ -- we'll ensure front is not empty, unless the queue is empty
+ queue q == [q, []]
+ construct q == queue q
+ empty() == [[], []]
+ empty? q == empty? q.front
+ copy q == [copy q.front, copy q.rear]
+ map(f, q) == [map(f, q.front), map(f, q.rear)]
+ map!(f, q) ==
+ q.front := map!(f, q.front)
+ q.rear := map!(f, q.rear)
+ q
+ # q == # q.front + # q.rear
+ parts q == append(q.front, reverse q.rear)
+ hashUpdate!(st, q) == hashUpdate!(st, parts q)
+
enqueue!(e, q) ==
- if null deref q then setref(q, list e)
- else lastTail.(deref q).rest := list e
+ q.rear := cons(e, q.rear)
e
- insert!(e, q) == (enqueue!(e, q);q)
dequeue! q ==
empty? q => error "empty queue"
- e := first deref q
- setref(q, rest deref q)
+ e := first q.front
+ q.front := rest q.front
+ if empty? q.front and not empty? q.rear then
+ q.front := reverse! q.rear
+ q.rear := []
e
- extract! q == dequeue! q
- rotate! q == if empty? q then q else (enqueue!(dequeue! q, q); q)
- front q == if empty? q then error "empty queue" else first deref q
+ front q ==
+ empty? q => error "empty queue"
+ first q.front
inspect q == front q
- back q == if empty? q then error "empty queue" else last deref q
- queue q == construct(q)
+ back q ==
+ if empty? q.rear then
+ if empty? q.front then error "empty queue"
+ else return last q.front
+ first q.rear
)abbrev domain DEQUEUE Dequeue
++ Author: Michael Monagan and Stephen Watt
--
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 fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
