aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/ChangeLog7
-rw-r--r--src/algebra/Makefile.am27
-rw-r--r--src/algebra/Makefile.in27
-rw-r--r--src/algebra/tree.spad.pamphlet20
4 files changed, 44 insertions, 37 deletions
diff --git a/src/ChangeLog b/src/ChangeLog
index 3b567ba2..0eb674e2 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,5 +1,12 @@
2013-05-17 Gabriel Dos Reis <gdr@integrable-solutions.net>
+ * algebra/tree.spad.pamphlet(BinaryTreeCategory): Extend
+ ShallowlyMutableAggregate S.
+ (BinarySearchTree): Remove redundant shallowlyMutable attribute.
+ (BalancedBinaryTree): Likewise.
+
+2013-05-17 Gabriel Dos Reis <gdr@integrable-solutions.net>
+
* algebra/aggcat.spad.pamphlet (ShallowlyMutableAggregate): New.
2013-05-17 Gabriel Dos Reis <gdr@integrable-solutions.net>
diff --git a/src/algebra/Makefile.am b/src/algebra/Makefile.am
index aa544fbd..f2b02a34 100644
--- a/src/algebra/Makefile.am
+++ b/src/algebra/Makefile.am
@@ -264,7 +264,7 @@ strap-0/VECTCAT.$(FASLEXT): strap-0/A1AGG.$(FASLEXT) \
strap-0/ABELMON.$(FASLEXT) strap-0/RING.$(FASLEXT) \
strap-0/MONOID.$(FASLEXT) strap-0/ABELGRP.$(FASLEXT)
-strap-0/ARR2CAT.$(FASLEXT): strap-0/FINAGG.$(FASLEXT)
+strap-0/ARR2CAT.$(FASLEXT): strap-0/FINAGG.$(FASLEXT) strap-0/SMAGG.$(FASLEXT)
strap-0/MATCAT.$(FASLEXT): strap-0/ARR2CAT.$(FASLEXT) \
strap-0/EUCDOM.$(FASLEXT) strap-0/INTDOM.$(FASLEXT) \
@@ -296,15 +296,16 @@ strap-0/TBAGG.$(FASLEXT): strap-0/KDAGG.$(FASLEXT) strap-0/FINAGG.$(FASLEXT)
strap-0/KDAGG.$(FASLEXT): strap-0/DIAGG.$(FASLEXT) strap-0/IXAGG.$(FASLEXT)
strap-0/DIAGG.$(FASLEXT): strap-0/DIOPS.$(FASLEXT)
strap-0/DIOPS.$(FASLEXT): strap-0/BGAGG.$(FASLEXT)
-strap-0/BGAGG.$(FASLEXT): strap-0/HOAGG.$(FASLEXT)
+strap-0/BGAGG.$(FASLEXT): strap-0/SMAGG.$(FASLEXT)
+strap-0/SMAGG.$(FASLEXT): strap-0/HOAGG.$(FASLEXT)
strap-0/LSAGG.$(FASLEXT): strap-0/STAGG.$(FASLEXT) \
strap-0/FLAGG.$(FASLEXT) strap-0/ELAGG.$(FASLEXT)
strap-0/STAGG.$(FASLEXT): strap-0/URAGG.$(FASLEXT)
strap-0/URAGG.$(FASLEXT): strap-0/RCAGG.$(FASLEXT)
strap-0/RCAGG.$(FASLEXT): strap-0/HOAGG.$(FASLEXT)
-strap-0/ELAGG.$(FASLEXT): strap-0/LNAGG.$(FASLEXT)
+strap-0/ELAGG.$(FASLEXT): strap-0/LNAGG.$(FASLEXT) strap-0/SMAGG.$(FASLEXT)
strap-0/SRAGG.$(FASLEXT): strap-0/A1AGG.$(FASLEXT)
-strap-0/A1AGG.$(FASLEXT): strap-0/FLAGG.$(FASLEXT)
+strap-0/A1AGG.$(FASLEXT): strap-0/FLAGG.$(FASLEXT) strap-0/SMAGG.$(FASLEXT)
strap-0/FLAGG.$(FASLEXT): strap-0/LNAGG.$(FASLEXT) strap-0/FINAGG.$(FASLEXT)
strap-0/FINAGG.$(FASLEXT): strap-0/HOAGG.$(FASLEXT)
strap-0/LNAGG.$(FASLEXT): strap-0/IXAGG.$(FASLEXT) \
@@ -605,7 +606,7 @@ strap-1/QFCAT.$(FASLEXT): strap-1/FIELD.$(FASLEXT) \
strap-1/OPERCAT.$(FASLEXT): strap-1/SETCAT.$(FASLEXT) \
strap-0/OUTFORM.$(FASLEXT) strap-0/BOOLEAN.$(FASLEXT)
-strap-1/ARR2CAT.$(FASLEXT): strap-1/FINAGG.$(FASLEXT)
+strap-1/ARR2CAT.$(FASLEXT): strap-1/FINAGG.$(FASLEXT) strap-1/SMAGG.$(FASLEXT)
strap-1/BTAGG.$(FASLEXT): strap-1/ORDSET.$(FASLEXT) \
strap-1/BOOLE.$(FASLEXT) strap-1/LOGIC.$(FASLEXT) \
@@ -624,11 +625,11 @@ strap-1/URAGG.$(FASLEXT): strap-1/RCAGG.$(FASLEXT) \
strap-1/RCAGG.$(FASLEXT): strap-1/HOAGG.$(FASLEXT)
-strap-1/ELAGG.$(FASLEXT): strap-1/LNAGG.$(FASLEXT)
+strap-1/ELAGG.$(FASLEXT): strap-1/LNAGG.$(FASLEXT) strap-1/SMAGG.$(FASLEXT)
strap-1/SRAGG.$(FASLEXT): strap-1/A1AGG.$(FASLEXT)
-strap-1/A1AGG.$(FASLEXT): strap-1/FLAGG.$(FASLEXT)
+strap-1/A1AGG.$(FASLEXT): strap-1/FLAGG.$(FASLEXT) strap-1/SMAGG.$(FASLEXT)
strap-1/FLAGG.$(FASLEXT): strap-1/LNAGG.$(FASLEXT) strap-1/FINAGG.$(FASLEXT)
@@ -986,7 +987,7 @@ strap-2/UPOLYC.$(FASLEXT): strap-2/POLYCAT.$(FASLEXT) \
strap-2/FIELD.$(FASLEXT) strap-2/ALGEBRA.$(FASLEXT)
-strap-2/ARR2CAT.$(FASLEXT): strap-2/FINAGG.$(FASLEXT)
+strap-2/ARR2CAT.$(FASLEXT): strap-2/FINAGG.$(FASLEXT) strap-2/SMAGG.$(FASLEXT)
strap-2/FSAGG.$(FASLEXT): strap-2/KDAGG.$(FASLEXT) \
strap-2/SETAGG.$(FASLEXT) strap-2/FINAGG.$(FASLEXT)
strap-2/ALAGG.$(FASLEXT): strap-2/TBAGG.$(FASLEXT) strap-2/LSAGG.$(FASLEXT)
@@ -996,13 +997,14 @@ strap-2/TBAGG.$(FASLEXT): strap-2/KDAGG.$(FASLEXT)
strap-2/KDAGG.$(FASLEXT): strap-2/DIAGG.$(FASLEXT) strap-2/IXAGG.$(FASLEXT)
strap-2/DIAGG.$(FASLEXT): strap-2/DIOPS.$(FASLEXT)
strap-2/DIOPS.$(FASLEXT): strap-2/BGAGG.$(FASLEXT) strap-2/CLAGG.$(FASLEXT)
-strap-2/BGAGG.$(FASLEXT): strap-2/HOAGG.$(FASLEXT)
+strap-2/SMAGG.$(FASLEXT): strap-2/HOAGG.$(FASLEXT)
+strap-2/BGAGG.$(FASLEXT): strap-2/SMAGG.$(FASLEXT)
strap-2/STAGG.$(FASLEXT): strap-2/URAGG.$(FASLEXT)
strap-2/URAGG.$(FASLEXT): strap-2/RCAGG.$(FASLEXT)
strap-2/RCAGG.$(FASLEXT): strap-2/HOAGG.$(FASLEXT)
-strap-2/ELAGG.$(FASLEXT): strap-2/LNAGG.$(FASLEXT)
+strap-2/ELAGG.$(FASLEXT): strap-2/LNAGG.$(FASLEXT) strap-2/SMAGG.$(FASLEXT)
strap-2/SRAGG.$(FASLEXT): strap-2/A1AGG.$(FASLEXT)
-strap-2/A1AGG.$(FASLEXT): strap-2/FLAGG.$(FASLEXT)
+strap-2/A1AGG.$(FASLEXT): strap-2/FLAGG.$(FASLEXT) strap-2/SMAGG.$(FASLEXT)
strap-2/FLAGG.$(FASLEXT): strap-2/LNAGG.$(FASLEXT) strap-2/FINAGG.$(FASLEXT)
strap-2/FINAGG.$(FASLEXT): strap-2/HOAGG.$(FASLEXT)
strap-2/LNAGG.$(FASLEXT): strap-2/IXAGG.$(FASLEXT) \
@@ -1365,7 +1367,7 @@ $(OUT)/FLAGG.$(FASLEXT): $(OUT)/BMODULE.$(FASLEXT) $(OUT)/PID.$(FASLEXT) \
$(OUT)/DIFFSPC.$(FASLEXT) $(OUT)/FINAGG.$(FASLEXT)
$(OUT)/A1AGG.$(FASLEXT): $(OUT)/SETCAT.$(FASLEXT) $(OUT)/BOOLE-.$(FASLEXT) \
$(OUT)/FLAGG.$(FASLEXT) $(OUT)/LOGIC-.$(FASLEXT) \
- $(OUT)/ORDTYPE-.$(FASLEXT)
+ $(OUT)/ORDTYPE-.$(FASLEXT) $(OUT)/SMAGG.$(FASLEXT)
$(OUT)/SRAGG.$(FASLEXT): $(OUT)/A1AGG.$(FASLEXT)
$(OUT)/STAGG.$(FASLEXT): $(OUT)/URAGG.$(FASLEXT) $(OUT)/LNAGG.$(FASLEXT)
$(OUT)/LNAGG.$(FASLEXT): $(OUT)/SEGCAT.$(FASLEXT)
@@ -1462,6 +1464,7 @@ $(OUT)/FSAGG.$(FASLEXT): $(OUT)/FINAGG.$(FASLEXT)
$(OUT)/SMAGG.$(FASLEXT): $(OUT)/HOAGG.$(FASLEXT)
$(OUT)/FINAGG.$(FASLEXT): $(OUT)/HOAGG.$(FASLEXT)
+$(OUT)/ELAGG.$(FASLEXT): $(OUT)/SMAGG.$(FASLEXT)
oa_algebra_layer_0 = \
AHYP ATTREG CFCAT ELTAB KOERCE KONVERT \
diff --git a/src/algebra/Makefile.in b/src/algebra/Makefile.in
index fe03e9c6..e871747f 100644
--- a/src/algebra/Makefile.in
+++ b/src/algebra/Makefile.in
@@ -1754,7 +1754,7 @@ strap-0/VECTCAT.$(FASLEXT): strap-0/A1AGG.$(FASLEXT) \
strap-0/ABELMON.$(FASLEXT) strap-0/RING.$(FASLEXT) \
strap-0/MONOID.$(FASLEXT) strap-0/ABELGRP.$(FASLEXT)
-strap-0/ARR2CAT.$(FASLEXT): strap-0/FINAGG.$(FASLEXT)
+strap-0/ARR2CAT.$(FASLEXT): strap-0/FINAGG.$(FASLEXT) strap-0/SMAGG.$(FASLEXT)
strap-0/MATCAT.$(FASLEXT): strap-0/ARR2CAT.$(FASLEXT) \
strap-0/EUCDOM.$(FASLEXT) strap-0/INTDOM.$(FASLEXT) \
@@ -1786,15 +1786,16 @@ strap-0/TBAGG.$(FASLEXT): strap-0/KDAGG.$(FASLEXT) strap-0/FINAGG.$(FASLEXT)
strap-0/KDAGG.$(FASLEXT): strap-0/DIAGG.$(FASLEXT) strap-0/IXAGG.$(FASLEXT)
strap-0/DIAGG.$(FASLEXT): strap-0/DIOPS.$(FASLEXT)
strap-0/DIOPS.$(FASLEXT): strap-0/BGAGG.$(FASLEXT)
-strap-0/BGAGG.$(FASLEXT): strap-0/HOAGG.$(FASLEXT)
+strap-0/BGAGG.$(FASLEXT): strap-0/SMAGG.$(FASLEXT)
+strap-0/SMAGG.$(FASLEXT): strap-0/HOAGG.$(FASLEXT)
strap-0/LSAGG.$(FASLEXT): strap-0/STAGG.$(FASLEXT) \
strap-0/FLAGG.$(FASLEXT) strap-0/ELAGG.$(FASLEXT)
strap-0/STAGG.$(FASLEXT): strap-0/URAGG.$(FASLEXT)
strap-0/URAGG.$(FASLEXT): strap-0/RCAGG.$(FASLEXT)
strap-0/RCAGG.$(FASLEXT): strap-0/HOAGG.$(FASLEXT)
-strap-0/ELAGG.$(FASLEXT): strap-0/LNAGG.$(FASLEXT)
+strap-0/ELAGG.$(FASLEXT): strap-0/LNAGG.$(FASLEXT) strap-0/SMAGG.$(FASLEXT)
strap-0/SRAGG.$(FASLEXT): strap-0/A1AGG.$(FASLEXT)
-strap-0/A1AGG.$(FASLEXT): strap-0/FLAGG.$(FASLEXT)
+strap-0/A1AGG.$(FASLEXT): strap-0/FLAGG.$(FASLEXT) strap-0/SMAGG.$(FASLEXT)
strap-0/FLAGG.$(FASLEXT): strap-0/LNAGG.$(FASLEXT) strap-0/FINAGG.$(FASLEXT)
strap-0/FINAGG.$(FASLEXT): strap-0/HOAGG.$(FASLEXT)
strap-0/LNAGG.$(FASLEXT): strap-0/IXAGG.$(FASLEXT) \
@@ -2095,7 +2096,7 @@ strap-1/QFCAT.$(FASLEXT): strap-1/FIELD.$(FASLEXT) \
strap-1/OPERCAT.$(FASLEXT): strap-1/SETCAT.$(FASLEXT) \
strap-0/OUTFORM.$(FASLEXT) strap-0/BOOLEAN.$(FASLEXT)
-strap-1/ARR2CAT.$(FASLEXT): strap-1/FINAGG.$(FASLEXT)
+strap-1/ARR2CAT.$(FASLEXT): strap-1/FINAGG.$(FASLEXT) strap-1/SMAGG.$(FASLEXT)
strap-1/BTAGG.$(FASLEXT): strap-1/ORDSET.$(FASLEXT) \
strap-1/BOOLE.$(FASLEXT) strap-1/LOGIC.$(FASLEXT) \
@@ -2114,11 +2115,11 @@ strap-1/URAGG.$(FASLEXT): strap-1/RCAGG.$(FASLEXT) \
strap-1/RCAGG.$(FASLEXT): strap-1/HOAGG.$(FASLEXT)
-strap-1/ELAGG.$(FASLEXT): strap-1/LNAGG.$(FASLEXT)
+strap-1/ELAGG.$(FASLEXT): strap-1/LNAGG.$(FASLEXT) strap-1/SMAGG.$(FASLEXT)
strap-1/SRAGG.$(FASLEXT): strap-1/A1AGG.$(FASLEXT)
-strap-1/A1AGG.$(FASLEXT): strap-1/FLAGG.$(FASLEXT)
+strap-1/A1AGG.$(FASLEXT): strap-1/FLAGG.$(FASLEXT) strap-1/SMAGG.$(FASLEXT)
strap-1/FLAGG.$(FASLEXT): strap-1/LNAGG.$(FASLEXT) strap-1/FINAGG.$(FASLEXT)
@@ -2473,7 +2474,7 @@ strap-2/UPOLYC.$(FASLEXT): strap-2/POLYCAT.$(FASLEXT) \
strap-2/COMRING.$(FASLEXT) strap-2/INTDOM.$(FASLEXT) \
strap-2/FIELD.$(FASLEXT) strap-2/ALGEBRA.$(FASLEXT)
-strap-2/ARR2CAT.$(FASLEXT): strap-2/FINAGG.$(FASLEXT)
+strap-2/ARR2CAT.$(FASLEXT): strap-2/FINAGG.$(FASLEXT) strap-2/SMAGG.$(FASLEXT)
strap-2/FSAGG.$(FASLEXT): strap-2/KDAGG.$(FASLEXT) \
strap-2/SETAGG.$(FASLEXT) strap-2/FINAGG.$(FASLEXT)
strap-2/ALAGG.$(FASLEXT): strap-2/TBAGG.$(FASLEXT) strap-2/LSAGG.$(FASLEXT)
@@ -2483,13 +2484,14 @@ strap-2/TBAGG.$(FASLEXT): strap-2/KDAGG.$(FASLEXT)
strap-2/KDAGG.$(FASLEXT): strap-2/DIAGG.$(FASLEXT) strap-2/IXAGG.$(FASLEXT)
strap-2/DIAGG.$(FASLEXT): strap-2/DIOPS.$(FASLEXT)
strap-2/DIOPS.$(FASLEXT): strap-2/BGAGG.$(FASLEXT) strap-2/CLAGG.$(FASLEXT)
-strap-2/BGAGG.$(FASLEXT): strap-2/HOAGG.$(FASLEXT)
+strap-2/SMAGG.$(FASLEXT): strap-2/HOAGG.$(FASLEXT)
+strap-2/BGAGG.$(FASLEXT): strap-2/SMAGG.$(FASLEXT)
strap-2/STAGG.$(FASLEXT): strap-2/URAGG.$(FASLEXT)
strap-2/URAGG.$(FASLEXT): strap-2/RCAGG.$(FASLEXT)
strap-2/RCAGG.$(FASLEXT): strap-2/HOAGG.$(FASLEXT)
-strap-2/ELAGG.$(FASLEXT): strap-2/LNAGG.$(FASLEXT)
+strap-2/ELAGG.$(FASLEXT): strap-2/LNAGG.$(FASLEXT) strap-2/SMAGG.$(FASLEXT)
strap-2/SRAGG.$(FASLEXT): strap-2/A1AGG.$(FASLEXT)
-strap-2/A1AGG.$(FASLEXT): strap-2/FLAGG.$(FASLEXT)
+strap-2/A1AGG.$(FASLEXT): strap-2/FLAGG.$(FASLEXT) strap-2/SMAGG.$(FASLEXT)
strap-2/FLAGG.$(FASLEXT): strap-2/LNAGG.$(FASLEXT) strap-2/FINAGG.$(FASLEXT)
strap-2/FINAGG.$(FASLEXT): strap-2/HOAGG.$(FASLEXT)
strap-2/LNAGG.$(FASLEXT): strap-2/IXAGG.$(FASLEXT) \
@@ -2705,7 +2707,7 @@ $(OUT)/FLAGG.$(FASLEXT): $(OUT)/BMODULE.$(FASLEXT) $(OUT)/PID.$(FASLEXT) \
$(OUT)/DIFFSPC.$(FASLEXT) $(OUT)/FINAGG.$(FASLEXT)
$(OUT)/A1AGG.$(FASLEXT): $(OUT)/SETCAT.$(FASLEXT) $(OUT)/BOOLE-.$(FASLEXT) \
$(OUT)/FLAGG.$(FASLEXT) $(OUT)/LOGIC-.$(FASLEXT) \
- $(OUT)/ORDTYPE-.$(FASLEXT)
+ $(OUT)/ORDTYPE-.$(FASLEXT) $(OUT)/SMAGG.$(FASLEXT)
$(OUT)/SRAGG.$(FASLEXT): $(OUT)/A1AGG.$(FASLEXT)
$(OUT)/STAGG.$(FASLEXT): $(OUT)/URAGG.$(FASLEXT) $(OUT)/LNAGG.$(FASLEXT)
$(OUT)/LNAGG.$(FASLEXT): $(OUT)/SEGCAT.$(FASLEXT)
@@ -2802,6 +2804,7 @@ $(OUT)/FSAGG.$(FASLEXT): $(OUT)/FINAGG.$(FASLEXT)
$(OUT)/SMAGG.$(FASLEXT): $(OUT)/HOAGG.$(FASLEXT)
$(OUT)/FINAGG.$(FASLEXT): $(OUT)/HOAGG.$(FASLEXT)
+$(OUT)/ELAGG.$(FASLEXT): $(OUT)/SMAGG.$(FASLEXT)
$(OUT)/HOMOTOP.$(FASLEXT): $(OUT)/KOERCE.$(FASLEXT) $(OUT)/KRCFROM.$(FASLEXT)
$(OUT)/ITUPLE.$(FASLEXT): $(OUT)/KOERCE.$(FASLEXT) $(OUT)/STREAM.$(FASLEXT)
diff --git a/src/algebra/tree.spad.pamphlet b/src/algebra/tree.spad.pamphlet
index 1352bd35..985f6dc5 100644
--- a/src/algebra/tree.spad.pamphlet
+++ b/src/algebra/tree.spad.pamphlet
@@ -328,9 +328,7 @@ Tree(S: SetCategory): T==C where
++ Description: \spadtype{BinaryTreeCategory(S)} is the category of
++ binary trees: a tree which is either empty or else is a \spadfun{node} consisting
++ of a value and a \spadfun{left} and \spadfun{right}, both binary trees.
-BinaryTreeCategory(S: SetCategory): Category == Join(BinaryRecursiveAggregate S,FiniteAggregate S) with
- shallowlyMutable
- ++ Binary trees have updateable components
+BinaryTreeCategory(S: SetCategory): Category == Join(BinaryRecursiveAggregate S,FiniteAggregate S,ShallowlyMutableAggregate S) with
node: (%,S,%) -> %
++ node(left,v,right) creates a binary tree with value \spad{v}, a binary
++ tree \spad{left}, and a binary tree \spad{right}.
@@ -340,13 +338,12 @@ BinaryTreeCategory(S: SetCategory): Category == Join(BinaryRecursiveAggregate S,
copy t ==
empty? t => empty()
node(copy left t, value t, copy right t)
- if % has shallowlyMutable then
- map!(f,t) ==
- empty? t => t
- t.value := f(t.value)
- map!(f,left t)
- map!(f,right t)
- t
+ map!(f,t) ==
+ empty? t => t
+ t.value := f(t.value)
+ map!(f,left t)
+ map!(f,right t)
+ t
treeCount : (%, NonNegativeInteger) -> NonNegativeInteger
#t == treeCount(t,0)
treeCount(t,k) ==
@@ -414,7 +411,6 @@ BinaryTree(S: SetCategory): Exports == Implementation where
++ Elements are ordered across the tree.
BinarySearchTree(S: OrderedSet): Exports == Implementation where
Exports == BinaryTreeCategory(S) with
- shallowlyMutable
binarySearchTree: List S -> %
++ binarySearchTree(l) \undocumented
insert!: (S,%) -> %
@@ -460,7 +456,6 @@ BinarySearchTree(S: OrderedSet): Exports == Implementation where
++ and a \spadfun{left} which are both \spadtype{BinaryTree(S)}
BinaryTournament(S: OrderedSet): Exports == Implementation where
Exports == BinaryTreeCategory(S) with
- shallowlyMutable
binaryTournament: List S -> %
++ binaryTournament(ls) creates a binary tournament with the
++ elements of ls as values at the nodes.
@@ -494,7 +489,6 @@ BinaryTournament(S: OrderedSet): Exports == Implementation where
++ by at most leaf node.
BalancedBinaryTree(S: SetCategory): Exports == Implementation where
Exports == BinaryTreeCategory(S) with
- shallowlyMutable
-- BUG: applies wrong fnct for balancedBinaryTree(0,[1,2,3,4])
-- balancedBinaryTree: (S, List S) -> %
-- ++ balancedBinaryTree(s, ls) creates a balanced binary tree with
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-07 06:09:20 +0000