* algebra/tree.spad.pamphlet(BinaryTreeCategory): Extend

	ShallowlyMutableAggregate S.
	(BinarySearchTree): Remove redundant shallowlyMutable attribute.
	(BalancedBinaryTree): Likewise.

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