aboutsummaryrefslogtreecommitdiff
path: root/src/algebra/bags.spad.pamphlet
diff options
context:
space:
mode:
Diffstat (limited to 'src/algebra/bags.spad.pamphlet')
-rw-r--r--src/algebra/bags.spad.pamphlet52
1 files changed, 26 insertions, 26 deletions
diff --git a/src/algebra/bags.spad.pamphlet b/src/algebra/bags.spad.pamphlet
index 9474a267..c00704a4 100644
--- a/src/algebra/bags.spad.pamphlet
+++ b/src/algebra/bags.spad.pamphlet
@@ -55,18 +55,18 @@ Stack(S: Type): StackAggregate S with
copy s == ref copy deref s
depth s == # deref s
# s == depth s
- pop_! (s:%):S ==
+ pop! (s:%):S ==
empty? s => error "empty stack"
e := first deref s
setref(s,rest deref s)
e
- extract_! (s:%):S == pop_! s
+ extract! (s:%):S == pop! s
top (s:%):S ==
empty? s => error "empty stack"
first deref s
inspect s == top s
- push_!(e,s) == (setref(s,cons(e,deref s));e)
- insert_!(e:S,s:%):% == (push_!(e,s);s)
+ push!(e,s) == (setref(s,cons(e,deref s));e)
+ insert!(e:S,s:%):% == (push!(e,s);s)
empty() == ref nil()$List(S)
empty? s == null deref s
stack s == ref copy s
@@ -108,14 +108,14 @@ ArrayStack(S:SetCategory): StackAggregate(S) with
-- stack operations
depth s == # s
empty? s == empty?(s)$Rep
- extract_! s == pop_! s
- insert_!(e,s) == (push_!(e,s);s)
- push_!(e,s) == (concat(e,s); e)
- pop_! s ==
+ extract! s == pop! s
+ insert!(e,s) == (push!(e,s);s)
+ push!(e,s) == (concat(e,s); e)
+ pop! s ==
if empty? s then error "empty stack"
m := maxIndex s
r := s.m
- delete_!(s,m)
+ delete!(s,m)
r
top s == if empty? s then error "empty stack" else s.maxIndex(s)
arrayStack l == construct(l)$Rep
@@ -147,18 +147,18 @@ Queue(S:SetCategory): QueueAggregate S with
== Stack S add
Rep := Reference List S
lastTail==> LAST$Lisp
- enqueue_!(e,q) ==
+ enqueue!(e,q) ==
if null deref q then setref(q, list e)
else lastTail.(deref q).rest := list e
e
- insert_!(e,q) == (enqueue_!(e,q);q)
- dequeue_! q ==
+ insert!(e,q) == (enqueue!(e,q);q)
+ dequeue! q ==
empty? q => error "empty queue"
e := first deref q
setref(q,rest deref q)
e
- extract_! q == dequeue_! q
- rotate_! q == if empty? q then q else (enqueue_!(dequeue_! q,q); q)
+ extract! q == dequeue! q
+ rotate! q == if empty? q then q else (enqueue!(dequeue! q,q); q)
length q == # deref q
front q == if empty? q then error "empty queue" else first deref q
inspect q == front q
@@ -190,10 +190,10 @@ Dequeue(S:SetCategory): DequeueAggregate S with
++ element x, second element y,...,and last (bottom or back) element z.
== Queue S add
Rep := Reference List S
- bottom_! d ==
+ bottom! d ==
if empty? d then error "empty dequeue" else last deref d
dequeue d == ref copy d
- extractBottom_! d ==
+ extractBottom! d ==
if empty? d then error "empty dequeue"
p := deref d
n := maxIndex p
@@ -205,19 +205,19 @@ Dequeue(S:SetCategory): DequeueAggregate S with
r := first rest q
q.rest := []
r
- extractTop_! d ==
+ extractTop! d ==
e := top d
setref(d,rest deref d)
e
height d == # deref d
- insertTop_!(e,d) == (setref(d,cons(e,deref d)); e)
+ insertTop!(e,d) == (setref(d,cons(e,deref d)); e)
lastTail==> LAST$Lisp
- insertBottom_!(e,d) ==
+ insertBottom!(e,d) ==
if empty? d then setref(d, list e)
else lastTail.(deref d).rest := list e
e
top d == if empty? d then error "empty dequeue" else first deref d
- reverse_! d == (setref(d,reverse deref d); d)
+ reverse! d == (setref(d,reverse deref d); d)
@
\section{domain HEAP Heap}
@@ -251,7 +251,7 @@ Heap(S:OrderedSet): Exports == Implementation where
n := #l
h := empty()
n = 0 => h
- for x in l repeat insert_!(x,h)
+ for x in l repeat insert!(x,h)
h
siftUp: (%,Integer,Integer) -> Void
siftUp(r,i,n) ==
@@ -261,21 +261,21 @@ Heap(S:OrderedSet): Exports == Implementation where
if (k := j+1) < n and r.j < r.k then j := k
if t < r.j then (r.i := r.j; r.j := t; i := j) else leave
- extract_! r ==
+ extract! r ==
-- extract the maximum from the heap O(log n)
n := #r :: Integer
n = 0 => error "empty heap"
t := r(0)
r(0) := r(n-1)
- delete_!(r,n-1)
+ delete!(r,n-1)
n = 1 => t
siftUp(r,0,n-1)
t
- insert_!(x,r) ==
+ insert!(x,r) ==
-- Williams' insertion algorithm O(log n)
j := (#r) :: Integer
- r:=concat_!(r,concat(x,empty()$Rep))
+ r:=concat!(r,concat(x,empty()$Rep))
while j > 0 repeat
i := (j-1) quo 2
if r(i) >= x then leave
@@ -294,7 +294,7 @@ Heap(S:OrderedSet): Exports == Implementation where
r
bag l == makeHeap construct(l)$Rep
merge(a,b) == makeHeap concat(a,b)
- merge_!(a,b) == makeHeap concat_!(a,b)
+ merge!(a,b) == makeHeap concat!(a,b)
@
\section{License}