If you are using the latest March 2009 sources (See http://axiom-developer.org/axiom-website/download.html
you'll find that there are several sources of information about trees. First, there is the actual Tree domain (attached below) which is contained in Book Volume 10.3: Axiom Algebra Domains (See http://axiom-developer.org/axiom-website/bookvol10.3.pdf Second, if you look at the tree domain sources below you will see various functions that are available. You will also see lines that begin with --X which are examples of using each function. These examples will show up if you display the operation, such as: )display op cyclic? Third, Book Volume 0: Axiom Jenks and Sutor (See: http://axiom-developer.org/axiom-website/documentation.html http://axiom-developer.org/axiom-website/bookvol0.pdf has a few references to the tree domain (e.g. p93). See BalancedBinaryTree (BBTREE) in section 9.2 of volume 0 and BinarySearchTree (BSTREE) in section 9.4 of volume 0. Fourth, in a running Axiom there are several "tree" domains which you can find by typing: )apropos tree Fifth, there is domain specific information you can get with: )show BalancedBinaryTree )show BinarySearchTree )show Tree You can get some help on these by typing: )help BalancedBinaryTree )help BinarySearchTree or you can use their abbreviations: )help BBTREE )help BSTREE Sixth, in the $AXIOM/doc/src/input directory there is a .dvi file for bbtree, bstree, and tree: xdvi $AXIOM/doc/src/input/bbtree.input.dvi xdvi $AXIOM/doc/src/input/bstree.input.dvi xdvi $AXIOM/doc/src/input/tree.input.dvi Seventh, if you start Axiom and use Hyperdoc you can do: Reference -> Examples -> BalancedBinaryTree Reference -> Examples -> BinarySearchTree and finally, the corresponding input files can be read into Axiom using: )read /home/simon/axiom/mnt/fedora10/input/bbtree.input )read /home/simon/axiom/mnt/fedora10/input/bstree.input )read /home/simon/axiom/mnt/fedora10/input/tree.input Feel free to post further questions. Tim ====================================================================== tree.spad ====================================================================== )abbrev domain TREE Tree ++ Author:W. H. Burge ++ Date Created:17 Feb 1992 ++ Date Last Updated: ++ Basic Operations: ++ Related Domains: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ Examples: ++ References: ++ Description: \spadtype{Tree(S)} is a basic domains of tree structures. ++ Each tree is either empty or else is a {\it node} consisting of a value and ++ a list of (sub)trees. Tree(S: SetCategory): T==C where T== RecursiveAggregate(S) with finiteAggregate shallowlyMutable tree: (S,List %) -> % ++ tree(nd,ls) creates a tree with value nd, and children ls. ++ ++X t1:=tree [1,2,3,4] ++X tree(5,[t1]) tree: List S -> % ++ tree(ls) creates a tree from a list of elements of s. ++ ++X tree [1,2,3,4] tree: S -> % ++ tree(nd) creates a tree with value nd, and no children ++ ++X tree 6 cyclic?: % -> Boolean ++ cyclic?(t) tests if t is a cyclic tree. ++ ++X t1:=tree [1,2,3,4] ++X cyclic? t1 cyclicCopy: % -> % ++ cyclicCopy(l) makes a copy of a (possibly) cyclic tree l. ++ ++X t1:=tree [1,2,3,4] ++X cyclicCopy t1 cyclicEntries: % -> List % ++ cyclicEntries(t) returns a list of top-level cycles in tree t. ++ ++X t1:=tree [1,2,3,4] ++X cyclicEntries t1 cyclicEqual?: (%, %) -> Boolean ++ cyclicEqual?(t1, t2) tests of two cyclic trees have ++ the same structure. ++ ++X t1:=tree [1,2,3,4] ++X t2:=tree [1,2,3,4] ++X cyclicEqual?(t1,t2) cyclicParents: % -> List % ++ cyclicParents(t) returns a list of cycles that are parents of t. ++ ++X t1:=tree [1,2,3,4] ++X cyclicParents t1 C== add cycleTreeMax ==> 5 Rep := Union(node:Record(value: S, args: List %),empty:"empty") t:% br:% s: S ls: List S empty? t == t case empty empty() == ["empty"] children t == t case empty => error "cannot take the children of an empty tree" (t.node.args)@List(%) setchildren_!(t,lt) == t case empty => error "cannot set children of an empty tree" (t.node.args:=lt;t pretend %) setvalue_!(t,s) == t case empty => error "cannot set value of an empty tree" (t.node.value:=s;s) count(n, t) == t case empty => 0 i := +/[count(n, c) for c in children t] value t = n => i + 1 i count(fn: S -> Boolean, t: %): NonNegativeInteger == t case empty => 0 i := +/[count(fn, c) for c in children t] fn value t => i + 1 i map(fn, t) == t case empty => t tree(fn value t,[map(fn, c) for c in children t]) map_!(fn, t) == t case empty => t setvalue_!(t, fn value t) for c in children t repeat map_!(fn, c) tree(s,lt) == [[s,lt]] tree(s) == [[s,[]]] tree(ls) == empty? ls => empty() tree(first ls, [tree s for s in rest ls]) value t == t case empty => error "cannot take the value of an empty tree" t.node.value child?(t1,t2) == empty? t2 => false "or"/[t1 = t for t in children t2] distance1(t1: %, t2: %): Integer == t1 = t2 => 0 t2 case empty => -1 u := [n for t in children t2 | (n := distance1(t1,t)) >= 0] #u > 0 => 1 + "min"/u -1 distance(t1,t2) == n := distance1(t1, t2) n >= 0 => n distance1(t2, t1) node?(t1, t2) == t1 = t2 => true t case empty => false "or"/[node?(t1, t) for t in children t2] leaf? t == t case empty => false empty? children t leaves t == t case empty => empty() leaf? t => [value t] "append"/[leaves c for c in children t] less? (t, n) == # t < n more?(t, n) == # t > n nodes t == ---buggy t case empty => empty() nl := [nodes c for c in children t] nl = empty() => [t] cons(t,"append"/nl) size? (t, n) == # t = n any?(fn, t) == ---bug fixed t case empty => false fn value t or "or"/[any?(fn, c) for c in children t] every?(fn, t) == t case empty => true fn value t and "and"/[every?(fn, c) for c in children t] member?(n, t) == t case empty => false n = value t or "or"/[member?(n, c) for c in children t] members t == parts t parts t == --buggy? t case empty => empty() u := [parts c for c in children t] u = empty() => [value t] cons(value t,"append"/u) ---Functions that guard against cycles: =, #, copy------------- -----> = equal?: (%, %, %, %, Integer) -> Boolean t1 = t2 == equal?(t1, t2, t1, t2, 0) equal?(t1, t2, ot1, ot2, k) == k = cycleTreeMax and (cyclic? ot1 or cyclic? ot2) => error "use cyclicEqual? to test equality on cyclic trees" t1 case empty => t2 case empty t2 case empty => false value t1 = value t2 and (c1 := children t1) = (c2 := children t2) and "and"/[equal?(x,y,ot1, ot2,k + 1) for x in c1 for y in c2] -----> # treeCount: (%, %, NonNegativeInteger) -> NonNegativeInteger # t == treeCount(t, t, 0) treeCount(t, origTree, k) == k = cycleTreeMax and cyclic? origTree => error "# is not defined on cyclic trees" t case empty => 0 1 + +/[treeCount(c, origTree, k + 1) for c in children t] -----> copy copy1: (%, %, Integer) -> % copy t == copy1(t, t, 0) copy1(t, origTree, k) == k = cycleTreeMax and cyclic? origTree => error "use cyclicCopy to copy a cyclic tree" t case empty => t empty? children t => tree value t tree(value t, [copy1(x, origTree, k + 1) for x in children t]) -----------Functions that allow cycles--------------- --local utility functions: eqUnion: (List %, List %) -> List % eqMember?: (%, List %) -> Boolean eqMemberIndex: (%, List %, Integer) -> Integer lastNode: List % -> List % insert: (%, List %) -> List % -----> coerce to OutputForm if S has SetCategory then multipleOverbar: (OutputForm, Integer, List %) -> OutputForm coerce1: (%, List %, List %) -> OutputForm coerce(t:%): OutputForm == coerce1(t, empty()$(List %), cyclicParents t) coerce1(t,parents, pl) == t case empty => empty()@List(S)::OutputForm eqMember?(t, parents) => multipleOverbar((".")::OutputForm,eqMemberIndex(t, pl,0),pl) empty? children t => value t::OutputForm nodeForm := (value t)::OutputForm if (k := eqMemberIndex(t, pl, 0)) > 0 then nodeForm := multipleOverbar(nodeForm, k, pl) prefix(nodeForm, [coerce1(br,cons(t,parents),pl) for br in children t]) multipleOverbar(x, k, pl) == k < 1 => x #pl = 1 => overbar x s : String := "abcdefghijklmnopqrstuvwxyz" c := s.(1 + ((k - 1) rem 26)) overlabel(c::OutputForm, x) -----> cyclic? cyclic2?: (%, List %) -> Boolean cyclic? t == cyclic2?(t, empty()$(List %)) cyclic2?(x,parents) == empty? x => false eqMember?(x, parents) => true for y in children x repeat cyclic2?(y,cons(x, parents)) => return true false -----> cyclicCopy cyclicCopy2: (%, List %) -> % copyCycle2: (%, List %) -> % copyCycle4: (%, %, %, List %) -> % cyclicCopy(t) == cyclicCopy2(t, cyclicEntries t) cyclicCopy2(t, cycles) == eqMember?(t, cycles) => return copyCycle2(t, cycles) tree(value t, [cyclicCopy2(c, cycles) for c in children t]) copyCycle2(cycle, cycleList) == newCycle := tree(value cycle, nil) setchildren!(newCycle, [copyCycle4(c,cycle,newCycle, cycleList) for c in children cycle]) newCycle copyCycle4(t, cycle, newCycle, cycleList) == empty? cycle => empty() eq?(t, cycle) => newCycle eqMember?(t, cycleList) => copyCycle2(t, cycleList) tree(value t, [copyCycle4(c, cycle, newCycle, cycleList) for c in children t]) -----> cyclicEntries cyclicEntries3: (%, List %, List %) -> List % cyclicEntries(t) == cyclicEntries3(t, empty()$(List %), empty()$(List %)) cyclicEntries3(t, parents, cl) == empty? t => cl eqMember?(t, parents) => insert(t, cl) parents := cons(t, parents) for y in children t repeat cl := cyclicEntries3(t, parents, cl) cl -----> cyclicEqual? cyclicEqual4?: (%, %, List %, List %) -> Boolean cyclicEqual?(t1, t2) == cp1 := cyclicParents t1 cp2 := cyclicParents t2 #cp1 ^= #cp2 or null cp1 => t1 = t2 cyclicEqual4?(t1, t2, cp1, cp2) cyclicEqual4?(t1, t2, cp1, cp2) == t1 case empty => t2 case empty t2 case empty => false 0 ^= (k := eqMemberIndex(t1, cp1, 0)) => eq?(t2, cp2 . k) value t1 = value t2 and "and"/[cyclicEqual4?(x,y,cp1,cp2) for x in children t1 for y in children t2] -----> cyclicParents t cyclicParents3: (%, List %, List %) -> List % cyclicParents t == cyclicParents3(t, empty()$(List %), empty()$(List %)) cyclicParents3(x, parents, pl) == empty? x => pl eqMember?(x, parents) => cycleMembers := [y for y in parents while not eq?(x,y)] eqUnion(cons(x, cycleMembers), pl) parents := cons(x, parents) for y in children x repeat pl := cyclicParents3(y, parents, pl) pl insert(x, l) == eqMember?(x, l) => l cons(x, l) lastNode l == empty? l => error "empty tree has no last node" while not empty? rest l repeat l := rest l l eqMember?(y,l) == for x in l repeat eq?(x,y) => return true false eqMemberIndex(x, l, k) == null l => k k := k + 1 eq?(x, first l) => k eqMemberIndex(x, rest l, k) eqUnion(u, v) == null u => v x := first u newV := eqMember?(x, v) => v cons(x, v) eqUnion(rest u, newV) @ _______________________________________________ Axiom-developer mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/axiom-developer
