[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Axiom-developer] Programming with the Tree domain
From: |
daly |
Subject: |
[Axiom-developer] Programming with the Tree domain |
Date: |
Thu, 26 Mar 2009 01:56:23 -0600 |
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)
@
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Axiom-developer] Programming with the Tree domain,
daly <=