[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Axiom-developer] 20090225.01.tpd.patch (bookvol10.3 Add .... Heap docum
|
From: |
daly |
|
Subject: |
[Axiom-developer] 20090225.01.tpd.patch (bookvol10.3 Add .... Heap documentation) |
|
Date: |
Wed, 25 Feb 2009 09:31:53 -0600 |
Add regression tests for Heap.
Update help page for Heap.
Add Examples for Heap.
======================================================================
diff --git a/books/bookvol10.3.pamphlet b/books/bookvol10.3.pamphlet
index bff1070..69c7c2e 100644
--- a/books/bookvol10.3.pamphlet
+++ b/books/bookvol10.3.pamphlet
@@ -41392,74 +41392,387 @@ HashTable(Key, Entry, hashfn): Exports ==
Implementation where
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{domain HEAP Heap}
<<Heap.input>>=
--- bags.spad.pamphlet Heap.input
)sys rm -f Heap.output
)spool Heap.output
)set message test on
)set message auto off
)clear all
---S 1 of 8
-h := heap [-4,9,11,2,7,-7]
+
+--S 1 of 42
+a:Heap INT:= heap [1,2,3,4,5]
--R
--R
---R (1) [11,7,9,- 4,2,- 7]
+--R (1) [5,4,2,1,3]
--R Type: Heap
Integer
--E 1
---S 2 of 8
-insert!(3,h)
+--S 2 of 42
+bag([1,2,3,4,5])$Heap(INT)
--R
--R
---R (2) [11,7,9,- 4,2,- 7,3]
+--R (2) [5,4,3,1,2]
--R Type: Heap
Integer
--E 2
---S 3 of 8
-extract! h
+--S 3 of 42
+c:=copy a
--R
--R
---R (3) 11
---R Type:
PositiveInteger
+--R (3) [5,4,2,1,3]
+--R Type: Heap
Integer
--E 3
---S 4 of 8
-h
+--S 4 of 42
+empty? a
--R
--R
---R (4) [9,7,3,- 4,2,- 7]
---R Type: Heap
Integer
+--R (4) false
+--R Type:
Boolean
--E 4
---S 5 of 8
+--S 5 of 42
+b:=empty()$(Heap INT)
+--R
+--R
+--R (5) []
+--R Type: Heap
Integer
+--E 5
+
+--S 6 of 42
+empty? b
+--R
+--R
+--R (6) true
+--R Type:
Boolean
+--E 6
+
+--S 7 of 42
+eq?(a,c)
+--R
+--R
+--R (7) false
+--R Type:
Boolean
+--E 7
+
+--S 8 of 42
+extract! a
+--R
+--R
+--R (8) 5
+--R Type:
PositiveInteger
+--E 8
+
+--S 8 of 42
+h:=heap [17,-4,9,-11,2,7,-7]
+--R
+--R
+--R (9) [17,2,9,- 11,- 4,7,- 7]
+--R Type: Heap
Integer
+--E 8
+
+--S 9 of 42
[extract!(h) while not empty?(h)]
--R
--R
---R (5) [9,7,3,2,- 4,- 7]
+--R (10) [17,9,7,2,- 4,- 7,- 11]
--R Type: List
Integer
---E 5
+--E 9
---S 6 of 8
+--S 10 of 42
heapsort(x) == (empty? x => []; cons(extract!(x),heapsort x))
--R
--R Type:
Void
---E 6
+--E 10
---S 7 of 8
-h1 := heap [17,-4,9,-11,2,7,-7]
+--S 11 of 42
+h1 := heapsort heap [17,-4,9,-11,2,7,-7]
+--R
+--R Compiling function heapsort with type Heap Integer -> List Integer
+--R
+--R (12) [17,9,7,2,- 4,- 7,- 11]
+--R Type: List
Integer
+--E 11
+
+--S 12 of 42
+(a=c)@Boolean
+--R
+--R
+--R (13) false
+--R Type:
Boolean
+--E 12
+
+--S 13 of 42
+(a~=c)
+--R
+--R
+--R (14) true
+--R Type:
Boolean
+--E 13
+
+--S 14 of 42
+a
--R
--R
---R (7) [17,2,9,- 11,- 4,7,- 7]
+--R (15) [4,3,2,1]
--R Type: Heap
Integer
---E 7
+--E 14
---S 8 of 8
-heapsort h1
+--S 15 of 42
+inspect a
+--R
+--R
+--R (16) 4
+--R Type:
PositiveInteger
+--E 15
+
+--S 16 of 42
+insert!(9,a)
+--R
+--R
+--R (17) [9,4,2,1,3]
+--R Type: Heap
Integer
+--E 16
+
+--S 17 of 42
+map(x+->x+10,a)
+--R
+--R
+--R (18) [19,14,12,11,13]
+--R Type: Heap
Integer
+--E 17
+
+--S 18 of 42
+a
+--R
+--R
+--R (19) [9,4,2,1,3]
+--R Type: Heap
Integer
+--E 18
+
+--S 19 of 42
+map!(x+->x+10,a)
+--R
+--R
+--R (20) [19,14,12,11,13]
+--R Type: Heap
Integer
+--E 19
+
+--S 20 of 42
+a
--R
---R Compiling function heapsort with type Heap Integer -> List Integer
--R
---R (8) [17,9,7,2,- 4,- 7,- 11]
+--R (21) [19,14,12,11,13]
+--R Type: Heap
Integer
+--E 20
+
+--S 21 of 42
+max a
+--R
+--R
+--R (22) 19
+--R Type:
PositiveInteger
+--E 21
+
+--S 22 of 42
+merge(a,c)
+--R
+--R
+--R (23) [19,14,12,11,13,5,4,2,1,3]
+--R Type: Heap
Integer
+--E 22
+
+--S 23 of 42
+a
+--R
+--R
+--R (24) [19,14,12,11,13]
+--R Type: Heap
Integer
+--E 23
+
+--S 24 of 42
+merge!(a,c)
+--R
+--R
+--R (25) [19,14,12,11,13,5,4,2,1,3]
+--R Type: Heap
Integer
+--E 24
+
+--S 25 of 42
+a
+--R
+--R
+--R (26) [19,14,12,11,13,5,4,2,1,3]
+--R Type: Heap
Integer
+--E 25
+
+--S 26 of 42
+c
+--R
+--R
+--R (27) [5,4,2,1,3]
+--R Type: Heap
Integer
+--E 26
+
+--S 27 of 42
+sample()$Heap(INT)
+--R
+--R
+--R (28) []
+--R Type: Heap
Integer
+--E 27
+
+--S 28 of 42
+#a
+--R
+--R
+--R (29) 10
+--R Type:
PositiveInteger
+--E 28
+
+--S 29 of 42
+any?(x+->(x=14),a)
+--R
+--R
+--R (30) true
+--R Type:
Boolean
+--E 29
+
+--S 30 of 42
+every?(x+->(x=11),a)
+--R
+--R
+--R (31) false
+--R Type:
Boolean
+--E 30
+
+--S 31 of 42
+parts a
+--R
+--R
+--R (32) [19,14,12,11,13,5,4,2,1,3]
--R Type: List
Integer
---E 8
+--E 31
+
+--S 32 of 42
+size?(a,9)
+--R
+--R
+--R (33) false
+--R Type:
Boolean
+--E 32
+
+--S 33 of 42
+more?(a,9)
+--R
+--R
+--R (34) true
+--R Type:
Boolean
+--E 33
+
+--S 34 of 42
+less?(a,9)
+--R
+--R
+--R (35) false
+--R Type:
Boolean
+--E 34
+
+--S 35 of 42
+members a
+--R
+--R
+--R (36) [19,14,12,11,13,5,4,2,1,3]
+--R Type: List
Integer
+--E 35
+
+--S 36 of 42
+member?(14,a)
+--R
+--R
+--R (37) true
+--R Type:
Boolean
+--E 36
+
+--S 37 of 42
+latex a
+--R
+--R
+--R (38) "\mbox{\bf Unimplemented}"
+--R Type:
String
+--E 37
+
+--S 38 of 42
+hash a
+--R
+--R
+--R (39) 0
+--R Type:
SingleInteger
+--E 38
+
+--S 39 of 42
+count(14,a)
+--R
+--R
+--R (40) 1
+--R Type:
PositiveInteger
+--E 39
+
+--S 40 of 42
+count(x+->(x>13),a)
+--R
+--R
+--R (41) 2
+--R Type:
PositiveInteger
+--E 40
+
+--S 41 of 42
+coerce a
+--R
+--R
+--R (42) [19,14,12,11,13,5,4,2,1,3]
+--R Type:
OutputForm
+--E 41
+
+--S 42 of 42
+)show Heap
+--R
+--R Heap S: OrderedSet is a domain constructor
+--R Abbreviation for Heap is HEAP
+--R This constructor is exposed in this frame.
+--R Issue )edit bookvol10.3.spad.pamphlet to see algebra source code for HEAP
+--R
+--R------------------------------- Operations --------------------------------
+--R bag : List S -> % copy : % -> %
+--R empty : () -> % empty? : % -> Boolean
+--R eq? : (%,%) -> Boolean extract! : % -> S
+--R heap : List S -> % insert! : (S,%) -> %
+--R inspect : % -> S map : ((S -> S),%) -> %
+--R max : % -> S merge : (%,%) -> %
+--R merge! : (%,%) -> % sample : () -> %
+--R #? : % -> NonNegativeInteger if $ has finiteAggregate
+--R ?=? : (%,%) -> Boolean if S has SETCAT
+--R any? : ((S -> Boolean),%) -> Boolean if $ has finiteAggregate
+--R coerce : % -> OutputForm if S has SETCAT
+--R count : (S,%) -> NonNegativeInteger if $ has finiteAggregate and S has
SETCAT
+--R count : ((S -> Boolean),%) -> NonNegativeInteger if $ has finiteAggregate
+--R eval : (%,List S,List S) -> % if S has EVALAB S and S has SETCAT
+--R eval : (%,S,S) -> % if S has EVALAB S and S has SETCAT
+--R eval : (%,Equation S) -> % if S has EVALAB S and S has SETCAT
+--R eval : (%,List Equation S) -> % if S has EVALAB S and S has SETCAT
+--R every? : ((S -> Boolean),%) -> Boolean if $ has finiteAggregate
+--R hash : % -> SingleInteger if S has SETCAT
+--R latex : % -> String if S has SETCAT
+--R less? : (%,NonNegativeInteger) -> Boolean
+--R map! : ((S -> S),%) -> % if $ has shallowlyMutable
+--R member? : (S,%) -> Boolean if $ has finiteAggregate and S has SETCAT
+--R members : % -> List S if $ has finiteAggregate
+--R more? : (%,NonNegativeInteger) -> Boolean
+--R parts : % -> List S if $ has finiteAggregate
+--R size? : (%,NonNegativeInteger) -> Boolean
+--R ?~=? : (%,%) -> Boolean if S has SETCAT
+--R
+--E 42
+
)spool
)lisp (bye)
@
@@ -41474,29 +41787,45 @@ element. The implementation represents heaps as
flexible arrays The
representation and algorithms give complexity of O(log(n)) for
insertion and extractions, and O(n) for construction.
-Create a heap of six elements.
+Create a heap of five elements:
- h := heap [-4,9,11,2,7,-7]
- [11,7,9,- 4,2,- 7]
- Type: Heap Integer
+ a:Heap INT:= heap [1,2,3,4,5]
+ [5,4,2,1,3]
-Use insert! to add an element.
+Use bag to convert a Bag into a Heap:
- insert!(3,h)
- [11,7,9,- 4,2,- 7,3]
- Type: Heap Integer
+ bag([1,2,3,4,5])$Heap(INT)
+ [5,4,3,1,2]
-The operation extract! removes and returns the maximum element.
+The operation copy can be used to copy a Heap:
- extract! h
- 11
- Type: PositiveInteger
+ c:=copy a
+ [5,4,2,1,3]
-The internal structure of h has been appropriately adjusted.
+Use empty? to check if the heap is empty:
- h
- [9,7,3,- 4,2,- 7]
- Type: Heap Integer
+ empty? a
+ false
+
+Use empty to create a new, empty heap:
+
+ b:=empty()$(Heap INT)
+ []
+
+and we can see that the newly created heap is empty:
+
+ empty? b
+ true
+
+The eq? function compares the reference of one heap to another:
+
+ eq?(a,c)
+ false
+
+The extract! function removes largest element of the heap:
+
+ extract! a
+ 5
Now extract! elements repeatedly until none are left, collecting
the elements in a list.
@@ -41522,9 +41851,151 @@ Apply heapsort to present elements in order.
[17,9,7,2,- 4,- 7,- 11]
Type: List Integer
+Heaps can be compared with =
+
+ (a=c)@Boolean
+ false
+
+and ~=
+
+ (a~=c)
+ true
+
+The inspect function shows the largest element in the heap:
+
+ inspect a
+ 4
+
+The insert! function adds an element to the heap:
+
+ insert!(9,a)
+ [9,4,2,1,3]
+
+The map function applies a function to every element of the heap
+and returns a new heap:
+
+ map(x+->x+10,a)
+ [19,14,12,11,13]
+
+The original heap is unchanged:
+
+ a
+ [9,4,2,1,3]
+
+The map! function applies a function to every element of the heap
+and returns the original heap with modifications:
+
+ map!(x+->x+10,a)
+ [19,14,12,11,13]
+
+The original heap has been modified:
+
+ a
+ [19,14,12,11,13]
+
+The max function returns the largest element in the heap:
+
+ max a
+ 19
+
+The merge function takes two heaps and creates a new heap with
+all of the elements:
+
+ merge(a,c)
+ [19,14,12,11,13,5,4,2,1,3]
+
+Notice that the original heap is unchanged:
+
+ a
+ [19,14,12,11,13]
+
+The merge! function takes two heaps and modifies the first heap
+argument to contain all of the elements:
+
+ merge!(a,c)
+ [19,14,12,11,13,5,4,2,1,3]
+
+Notice that the first argument was modified:
+
+ a
+ [19,14,12,11,13,5,4,2,1,3]
+
+but the second argument was not:
+
+ c
+ [5,4,2,1,3]
+
+A new, empty heap can be created with sample:
+
+ sample()$Heap(INT)
+ []
+
+The # function gives the size of the heap:
+
+ #a
+ 10
+
+The any? function tests each element against a predicate function
+and returns true if any pass:
+
+ any?(x+->(x=14),a)
+ true
+
+The every? function tests each element against a predicate function
+and returns true if they all pass:
+
+ every?(x+->(x=11),a)
+ false
+
+The parts function returns a list of the elements in the heap:
+
+ parts a
+ [19,14,12,11,13,5,4,2,1,3]
+
+The size? predicate compares the size of the heap to a value:
+
+ size?(a,9)
+ false
+
+The more? predicate asks if the heap size is larger than a value:
+
+ more?(a,9)
+ true
+
+The less? predicate asks if the heap size is smaller than a value:
+
+ less?(a,9)
+ false
+
+The members function returns a list of the elements of the heap:
+
+ members a
+ [19,14,12,11,13,5,4,2,1,3]
+
+The member? predicate asks if an element is in the heap:
+
+ member?(14,a)
+ true
+
+The count function has two forms, one of which counts the number
+of copies of an element in the heap:
+
+ count(14,a)
+ 1
+
+The second form of the count function accepts a predicate to test
+against each member of the heap and counts the number of true results:
+
+ count(x+->(x>13),a)
+ 2
+
See Also:
-o )help FlexibleArray
+o )show Stack
+o )show ArrayStack
+o )show Queue
+o )show Dequeue
o )show Heap
+o )show BagAggregate
@
\pagehead{Heap}{HEAP}
@@ -41596,6 +42067,141 @@ Heap(S:OrderedSet): Exports == Implementation where
++
++E i:Heap INT := heap [1,6,3,7,5,2,4]
+ -- Inherited Signatures repeated for examples documentation
+
+ bag : List S -> %
+ ++
+ ++X bag([1,2,3,4,5])$Heap(INT)
+ copy : % -> %
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X copy a
+ empty? : % -> Boolean
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X empty? a
+ empty : () -> %
+ ++
+ ++X b:=empty()$(Heap INT)
+ eq? : (%,%) -> Boolean
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X b:=copy a
+ ++X eq?(a,b)
+ extract_! : % -> S
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X extract! a
+ ++X a
+ insert_! : (S,%) -> %
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X insert!(8,a)
+ ++X a
+ inspect : % -> S
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X inspect a
+ map : ((S -> S),%) -> %
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X map(x+->x+10,a)
+ ++X a
+ max : % -> S
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X max a
+ merge : (%,%) -> %
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X b:Heap INT:= heap [6,7,8,9,10]
+ ++X merge(a,b)
+ merge! : (%,%) -> %
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X b:Heap INT:= heap [6,7,8,9,10]
+ ++X merge!(a,b)
+ ++X a
+ ++X b
+ sample : () -> %
+ ++
+ ++X sample()$Heap(INT)
+ less? : (%,NonNegativeInteger) -> Boolean
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X less?(a,9)
+ more? : (%,NonNegativeInteger) -> Boolean
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X more?(a,9)
+ size? : (%,NonNegativeInteger) -> Boolean
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X size?(a,5)
+ if $ has shallowlyMutable then
+ map! : ((S -> S),%) -> %
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X map!(x+->x+10,a)
+ ++X a
+ if S has SetCategory then
+ latex : % -> String
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X latex a
+ hash : % -> SingleInteger
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X hash a
+ coerce : % -> OutputForm
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X coerce a
+ "=": (%,%) -> Boolean
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X b:Heap INT:= heap [1,2,3,4,5]
+ ++X (a=b)@Boolean
+ "~=" : (%,%) -> Boolean
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X b:=copy a
+ ++X (a~=b)
+ if % has finiteAggregate then
+ every? : ((S -> Boolean),%) -> Boolean
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X every?(x+->(x=4),a)
+ any? : ((S -> Boolean),%) -> Boolean
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X any?(x+->(x=4),a)
+ count : ((S -> Boolean),%) -> NonNegativeInteger
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X count(x+->(x>2),a)
+ _# : % -> NonNegativeInteger
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X #a
+ parts : % -> List S
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X parts a
+ members : % -> List S
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X members a
+ if % has finiteAggregate and S has SetCategory then
+ member? : (S,%) -> Boolean
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X member?(3,a)
+ count : (S,%) -> NonNegativeInteger
+ ++
+ ++X a:Heap INT:= heap [1,2,3,4,5]
+ ++X count(4,a)
+
Implementation == IndexedFlexibleArray(S,0) add
Rep := IndexedFlexibleArray( S,0)
empty() == empty()$Rep
diff --git a/changelog b/changelog
index ec8432f..b994693 100644
--- a/changelog
+++ b/changelog
@@ -1,3 +1,6 @@
+20090225 tpd src/axiom-website/patches.html 20090225.01.tpd.patch
+20090225 tpd src/interp/Makefile add regression, help for Heap
+20090225 tpd books/bookvol10.3 add regression, help, examples for Heap
20090224 tpd src/axiom-website/patches.html 20090224.01.tpd.patch
20090224 tpd src/interp/Makefile add regression, help for Dequeue
20090224 tpd books/bookvol10.3 add regression, help, examples for Dequeue
diff --git a/src/algebra/Makefile.pamphlet b/src/algebra/Makefile.pamphlet
index bcf1252..ed8052e 100644
--- a/src/algebra/Makefile.pamphlet
+++ b/src/algebra/Makefile.pamphlet
@@ -16420,11 +16420,12 @@ SPADHELP=\
${HELP}/Complex.help ${HELP}/ContinuedFraction.help \
${HELP}/CycleIndicators.help ${HELP}/DeRhamComplex.help \
${HELP}/DecimalExpansion.help ${HELP}/Dequeue.help \
+ ${HELP}/DistributedMultivariatePolynomial.help \
${HELP}/DoubleFloat.help \
${HELP}/EqTable.help ${HELP}/Equation.help \
${HELP}/Expression.help \
- ${HELP}/DistributedMultivariatePolynomial.help \
${HELP}/EuclideanGroebnerBasisPackage.help \
+ ${HELP}/Heap.help \
${HELP}/Factored.help ${HELP}/FactoredFunctions2.help \
${HELP}/File.help ${HELP}/FileName.help \
${HELP}/FlexibleArray.help ${HELP}/Float.help \
diff --git a/src/axiom-website/patches.html b/src/axiom-website/patches.html
index 564aaaf..c668b7b 100644
--- a/src/axiom-website/patches.html
+++ b/src/axiom-website/patches.html
@@ -965,5 +965,7 @@ bookvol10.3 add regression, help, examples for
ArrayStack<br/>
bookvol10.3 add regression, help, examples for Queue<br/>
<a href="patches/20090224.01.tpd.patch">20090224.01.tpd.patch</a>
bookvol10.3 add regression, help, examples for Dequeue<br/>
+<a href="patches/20090225.01.tpd.patch">20090225.01.tpd.patch</a>
+bookvol10.3 add regression, help, examples for Heap<br/>
</body>
</html>
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Axiom-developer] 20090225.01.tpd.patch (bookvol10.3 Add .... Heap documentation),
daly <=