diff options
| -rw-r--r-- | src/ChangeLog | 7 | ||||
| -rw-r--r-- | src/algebra/Makefile.am | 27 | ||||
| -rw-r--r-- | src/algebra/Makefile.in | 27 | ||||
| -rw-r--r-- | src/algebra/tree.spad.pamphlet | 20 |
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 |