\documentclass{article} \usepackage{open-axiom} \begin{document} \title{\$SPAD/src/algebra newpoint.spad} \author{The Axiom Team} \maketitle \begin{abstract} \end{abstract} \eject \tableofcontents \eject \section{category PTCAT PointCategory} <>= )abbrev category PTCAT PointCategory ++ Author: ++ Date Created: ++ Date Last Updated: ++ Basic Operations: point, elt, setelt, copy, dimension, minIndex, maxIndex, ++ convert ++ Related Constructors: ++ Also See: ++ AMS Classifications: ++ Keywords: ++ References: ++ Description: PointCategory is the category of points in space which ++ may be plotted via the graphics facilities. Functions are provided for ++ defining points and handling elements of points. PointCategory(R:Ring) : Category == Join(VectorCategory(R),ConvertibleFrom List R) with point: List R -> % ++ point(l) returns a point category defined by a list l of elements from ++ the domain R. dimension: % -> PositiveInteger ++ dimension(s) returns the dimension of the point category s. cross: (%,%) -> % ++ cross(p,q) computes the cross product of the two points \spad{p} ++ and \spad{q}. Error if the p and q are not 3 dimensional extend : (%,List R) -> % ++ extend(x,l,r) \undocumented @ \section{domain POINT Point} <>= )abbrev domain POINT Point ++ Description: ++ This domain implements points in coordinate space Point(R:Ring) : Exports == Implementation where -- Domains for points, subspaces and properties of components in -- a subspace Exports ==> PointCategory(R) Implementation ==> Vector (R) add PI ==> PositiveInteger point(l:List R):% == per vector l dimension p == (# p)::PI -- Vector returns NonNegativeInteger...? convert(l:List R):% == point(l) cross(p0, p1) == #p0 ~=3 or #p1~=3 => error "Arguments to cross must be three dimensional" point [p0.2 * p1.3 - p1.2 * p0.3, _ p1.1 * p0.3 - p0.1 * p1.3, _ p0.1 * p1.2 - p1.1 * p0.2] extend(p,l) == concat(p,point l) @ \section{domain COMPPROP SubSpaceComponentProperty} <>= )abbrev domain COMPPROP SubSpaceComponentProperty ++ Description: ++ This domain implements some global properties of subspaces. SubSpaceComponentProperty() : Exports == Implementation where O ==> OutputForm I ==> Integer PI ==> PositiveInteger NNI ==> NonNegativeInteger L ==> List B ==> Boolean Exports ==> SetCategory with new : () -> % ++ new() \undocumented closed? : % -> B ++ closed?(x) \undocumented solid? : % -> B ++ solid?(x) \undocumented close : (%,B) -> B ++ close(x,b) \undocumented solid : (%,B) -> B ++ solid(x,b) \undocumented copy : % -> % ++ copy(x) \undocumented Implementation ==> add import B Rep := Record(closed:B, solid:B) closed? p == p.closed solid? p == p.solid close(p,b) == p.closed := b solid(p,b) == p.solid := b new() == [false,false] copy p == annuderOne := new() close(annuderOne,closed? p) solid(annuderOne,solid? p) annuderOne coerce p == hconcat(["Component is "::O, (closed? p => ""::O; "not "::O),"closed, "::O, _ (solid? p => ""::O; "not "::O),"solid"::O ]) @ \section{domain SUBSPACE SubSpace} <>= )abbrev domain SUBSPACE SubSpace ++ Description: ++ This domain \undocumented SubSpace(n:PI,R:Ring) : Exports == Implementation where -- n is the dimension of the subSpace -- The SubSpace domain is implemented as a tree. The root of the tree -- is the only node in which the field dataList - which points to a -- list of points over the ring, R - is defined. The children of the -- root are the top level components of the SubSpace (in 2D, these -- would be separate curves; in 3D, these would be separate surfaces). -- The pt field is only defined in the leaves. -- By way of example, consider a three dimensional subspace with -- two components - a three by three grid and a sphere. The internal -- representation of this subspace is a tree with a depth of three. -- The root holds a list of all the points used in the subspace (so, -- if the grid and the sphere share points, the shared points would not -- be represented redundantly but would be referenced by index). -- The root, in this case, has two children - the first points to the -- grid component and the second to the sphere component. The grid child -- has four children of its own - a 3x3 grid has 4 endpoints - and each -- of these point to a list of four points. To see it another way, the -- grid (child of the root) holds a list of line components which, when -- placed one above the next, forms a grid. Each of these line components -- is a list of points. -- Points could be explicitly added to subspaces at any level. A path -- could be given as an argument to the addPoint() function. It is a list -- of NonNegativeIntegers and refers, in order, to the n-th child of the -- current node. For example, -- addPoint(s,[2,3],p) -- would add the point p to the subspace s by going to the second child of -- the root and then the third child of that node. If the path does extend -- to the full depth of the tree, nodes are automatically added so that -- the tree is of constant depth down any path. By not specifying the full -- path, new components could be added - e.g. for s from SubSpace(3,Float) -- addPoint(s,[],p) -- would create a new child to the root (a new component in N-space) and -- extend a path to a leaf of depth 3 that points to the data held in p. -- The subspace s would now have a new component which has one child -- which, in turn, has one child (the leaf). The new component is then a -- point. I ==> Integer PI ==> PositiveInteger NNI ==> NonNegativeInteger L ==> List B ==> Boolean POINT ==> Point(R) PROP ==> SubSpaceComponentProperty() S ==> String O ==> OutputForm empty ==> nil -- macro to ease conversion to new aggcat.spad Exports ==> SetCategory with leaf? : % -> B ++ leaf?(x) \undocumented root? : % -> B ++ root?(x) \undocumented internal? : % -> B ++ internal?(x) \undocumented new : () -> % ++ new() \undocumented subspace : () -> % ++ subspace() \undocumented birth : % -> % -- returns a pointer to the baby ++ birth(x) \undocumented child : (%,NNI) -> % ++ child(x,n) \undocumented children : % -> List % ++ children(x) \undocumented numberOfChildren: % -> NNI ++ numberOfChildren(x) \undocumented shallowCopy : % -> % ++ shallowCopy(x) \undocumented deepCopy : % -> % ++ deepCopy(x) \undocumented merge : (%,%) -> % ++ merge(s1,s2) the subspaces s1 and s2 into a single subspace. merge : List % -> % ++ merge(ls) a list of subspaces, ls, into one subspace. separate : % -> List % ++ separate(s) makes each of the components of the \spadtype{SubSpace}, ++ s, into a list of separate and distinct subspaces and returns ++ the list. addPoint : (%,List NNI,POINT) -> % ++ addPoint(s,li,p) adds the 4 dimensional point, p, to the 3 ++ dimensional subspace, s. The list of non negative integers, li, ++ dictates the path to follow, or, to look at it another way, ++ points to the component in which the point is to be added. It's ++ length should range from 0 to \spad{n - 1} where n is the dimension ++ of the subspace. If the length is \spad{n - 1}, then a specific ++ lowest level component is being referenced. If it is less than ++ \spad{n - 1}, then some higher level component (0 indicates top ++ level component) is being referenced and a component of that level ++ with the desired point is created. The subspace s is returned ++ with the additional point. addPoint2 : (%,POINT) -> % ++ addPoint2(s,p) adds the 4 dimensional point, p, to the 3 ++ dimensional subspace, s. ++ The subspace s is returned with the additional point. addPointLast : (%,%,POINT, NNI) -> % ++ addPointLast(s,s2,li,p) adds the 4 dimensional point, p, to the 3 ++ dimensional subspace, s. s2 point to the end of the subspace ++ s. n is the path in the s2 component. ++ The subspace s is returned with the additional point. modifyPoint : (%,List NNI,POINT) -> % ++ modifyPoint(s,li,p) replaces an existing point in the 3 dimensional ++ subspace, s, with the 4 dimensional point, p. The list of non ++ negative integers, li, dictates the path to follow, or, to look at ++ it another way, points to the component in which the existing point ++ is to be modified. An error message occurs if s is empty, otherwise ++ the subspace s is returned with the point modification. addPoint : (%,List NNI,NNI) -> % ++ addPoint(s,li,i) adds the 4 dimensional point indicated by the ++ index location, i, to the 3 dimensional subspace, s. The list of ++ non negative integers, li, dictates the path to follow, or, to ++ look at it another way, points to the component in which the point ++ is to be added. It's length should range from 0 to \spad{n - 1} ++ where n is the dimension of the subspace. If the length is ++ \spad{n - 1}, then a specific lowest level component is being ++ referenced. If it is less than \spad{n - 1}, then some higher ++ level component (0 indicates top level component) is being ++ referenced and a component of that level with the desired point ++ is created. The subspace s is returned with the additional point. modifyPoint : (%,List NNI,NNI) -> % ++ modifyPoint(s,li,i) replaces an existing point in the 3 dimensional ++ subspace, s, with the 4 dimensional point indicated by the index ++ location, i. The list of non negative integers, li, dictates ++ the path to follow, or, to look at it another way, points to the ++ component in which the existing point is to be modified. An error ++ message occurs if s is empty, otherwise the subspace s is returned ++ with the point modification. addPoint : (%,POINT) -> NNI ++ addPoint(s,p) adds the point, p, to the 3 dimensional subspace, s, ++ and returns the new total number of points in s. modifyPoint : (%,NNI,POINT) -> % ++ modifyPoint(s,ind,p) modifies the point referenced by the index ++ location, ind, by replacing it with the point, p in the 3 dimensional ++ subspace, s. An error message occurs if s is empty, otherwise the ++ subspace s is returned with the point modification. closeComponent : (%,List NNI,B) -> % ++ closeComponent(s,li,b) sets the property of the component in the ++ 3 dimensional subspace, s, to be closed if b is true, or open if ++ b is false. The list of non negative integers, li, dictates the ++ path to follow, or, to look at it another way, points to the ++ component whose closed property is to be set. The subspace, s, ++ is returned with the component property modification. defineProperty : (%,List NNI,PROP) -> % ++ defineProperty(s,li,p) defines the component property in the ++ 3 dimensional subspace, s, to be that of p, where p is of the ++ domain \spadtype{SubSpaceComponentProperty}. The list of non ++ negative integers, li, dictates the path to follow, or, to look ++ at it another way, points to the component whose property is ++ being defined. The subspace, s, is returned with the component ++ property definition. traverse : (%,List NNI) -> % ++ traverse(s,li) follows the branch list of the 3 dimensional ++ subspace, s, along the path dictated by the list of non negative ++ integers, li, which points to the component which has been ++ traversed to. The subspace, s, is returned, where s is now ++ the subspace pointed to by li. extractPoint : % -> POINT ++ extractPoint(s) returns the point which is given by the current ++ index location into the point data field of the 3 dimensional ++ subspace s. extractIndex : % -> NNI ++ extractIndex(s) returns a non negative integer which is the current ++ index of the 3 dimensional subspace s. extractClosed : % -> B ++ extractClosed(s) returns the \spadtype{Boolean} value of the closed ++ property for the indicated 3 dimensional subspace s. If the ++ property is closed, \spad{True} is returned, otherwise \spad{False} ++ is returned. extractProperty : % -> PROP ++ extractProperty(s) returns the property of domain ++ \spadtype{SubSpaceComponentProperty} of the indicated 3 dimensional ++ subspace s. level : % -> NNI ++ level(s) returns a non negative integer which is the current ++ level field of the indicated 3 dimensional subspace s. parent : % -> % ++ parent(s) returns the subspace which is the parent of the indicated ++ 3 dimensional subspace s. If s is the top level subspace an error ++ message is returned. pointData : % -> L POINT ++ pointData(s) returns the list of points from the point data field ++ of the 3 dimensional subspace s. Implementation ==> add import String() Rep := Record(pt:POINT, index:NNI, property:PROP, _ childrenField:List %, _ lastChild: List %, _ levelField:NNI, _ pointDataField:L POINT, _ lastPoint: L POINT, _ noPoints: NNI, _ noChildren: NNI, _ parentField:List %) -- needn't be list but...base case? TELLWATT : String := "Non-null list: Please inform Stephen Watt" leaf? space == empty? children space root? space == (space.levelField = 0$NNI) internal? space == not (root? space and leaf? space) new() == [point(empty())$POINT,0,new()$PROP,empty(),empty(),0,_ empty(),empty(),0,0,empty()] subspace() == new() birth momma == baby := new() baby.levelField := momma.levelField+1 baby.parentField := [momma] if not empty?(lastKid := momma.lastChild) then not empty? rest lastKid => error TELLWATT if empty? lastKid then momma.childrenField := [baby] momma.lastChild := momma.childrenField momma.noChildren := 1 else setrest!(lastKid,[baby]) momma.lastChild := rest lastKid momma.noChildren := momma.noChildren + 1 baby child(space,num) == space.childrenField.num children space == space.childrenField numberOfChildren space == space.noChildren shallowCopy space == node := new() node.pt := space.pt node.index := space.index node.property := copy(space.property) node.levelField := space.levelField node.parentField := nil() if root? space then node.pointDataField := copy(space.pointDataField) node.lastPoint := tail(node.pointDataField) node.noPoints := space.noPoints node deepCopy space == node := shallowCopy(space) leaf? space => node for c in children space repeat cc := deepCopy c cc.parentField := [node] node.childrenField := cons(cc,node.childrenField) node.childrenField := reverse!(node.childrenField) node.lastChild := tail node.childrenField node merge(s1,s2) == ------------------ need to worry about reindexing s2 & parentField n1 : Rep := deepCopy s1 n2 : Rep := deepCopy s2 n1.childrenField := append(children n1,children n2) n1 merge listOfSpaces == ------------------ need to worry about reindexing & parentField empty? listOfSpaces => error "empty list passed as argument to merge" -- notice that the properties of the first subspace on the -- list are the ones that are inherited...hmmmm... space := deepCopy first listOfSpaces for s in rest listOfSpaces repeat -- because of the initial deepCopy, above, everything is -- deepCopied to be consistent...more hmmm... space.childrenField := append(space.childrenField,[deepCopy c for c in s.childrenField]) space separate space == ------------------ need to worry about reindexing & parentField spaceList := empty() for s in space.childrenField repeat spc:=shallowCopy space spc.childrenField:=[deepCopy s] spaceList := cons(spc,spaceList) spaceList addPoint(space:%,path:List NNI,point:POINT) == if not empty?(lastPt := space.lastPoint) then not empty? rest lastPt => error TELLWATT if empty? lastPt then space.pointDataField := [point] space.lastPoint := space.pointDataField else setrest!(lastPt,[point]) space.lastPoint := rest lastPt space.noPoints := space.noPoints + 1 which := space.noPoints node := space depth : NNI := 0 for i in path repeat node := child(node,i) depth := depth + 1 for more in depth..(n-1) repeat node := birth node node.pt := point -- will be obsolete field node.index := which space addPoint2(space:%,point:POINT) == if not empty?(lastPt := space.lastPoint) then not empty? rest lastPt => error TELLWATT if empty? lastPt then space.pointDataField := [point] space.lastPoint := space.pointDataField else setrest!(lastPt,[point]) space.lastPoint := rest lastPt space.noPoints := space.noPoints + 1 which := space.noPoints node := space depth : NNI := 0 node := birth node first := node for more in 1..n-1 repeat node := birth node node.pt := point -- will be obsolete field node.index := which first addPointLast(space:%,node:%, point:POINT, depth:NNI) == if not empty?(lastPt := space.lastPoint) then not empty? rest lastPt => error TELLWATT if empty? lastPt then space.pointDataField := [point] space.lastPoint := space.pointDataField else setrest!(lastPt,[point]) space.lastPoint := rest lastPt space.noPoints := space.noPoints + 1 which := space.noPoints if depth = 2 then node := child(node, 2) for more in depth..(n-1) repeat node := birth node node.pt := point -- will be obsolete field node.index := which node -- space addPoint(space:%,path:List NNI,which:NNI) == node := space depth : NNI := 0 for i in path repeat node := child(node,i) depth := depth + 1 for more in depth..(n-1) repeat node := birth node node.pt := space.pointDataField.which -- will be obsolete field node.index := which space addPoint(space:%,point:POINT) == root? space => if not empty?(lastPt := space.lastPoint) then not empty? rest lastPt => error TELLWATT if empty? lastPt then space.pointDataField := [point] space.lastPoint := space.pointDataField else setrest!(lastPt,[point]) space.lastPoint := rest lastPt space.noPoints := space.noPoints + 1 error "You need to pass a top level SubSpace (level should be zero)" modifyPoint(space:%,path:List NNI,point:POINT) == if not empty?(lastPt := space.lastPoint) then not empty? rest lastPt => error TELLWATT if empty? lastPt then space.pointDataField := [point] space.lastPoint := space.pointDataField else setrest!(lastPt,[point]) space.lastPoint := rest lastPt space.noPoints := space.noPoints + 1 which := space.noPoints node := space for i in path repeat node := child(node,i) node.pt := point ---------- will be obsolete field node.index := which space modifyPoint(space:%,path:List NNI,which:NNI) == node := space for i in path repeat node := child(node,i) node.pt := space.pointDataField.which ---------- will be obsolete field node.index := which space modifyPoint(space:%,which:NNI,point:POINT) == root? space => space.pointDataField.which := point space error "You need to pass a top level SubSpace (level should be zero)" closeComponent(space,path,val) == node := space for i in path repeat node := child(node,i) close(node.property,val) space defineProperty(space,path,prop) == node := space for i in path repeat node := child(node,i) node.property := prop space traverse(space,path) == for i in path repeat space := child(space,i) space extractPoint space == node := space while not root? node repeat node := parent node (node.pointDataField).(space.index) extractIndex space == space.index extractClosed space == closed? space.property extractProperty space == space.property parent space == empty? space.parentField => error "This is a top level SubSpace - it does not have a parent" first space.parentField pointData space == space.pointDataField level space == space.levelField s1 = s2 == ------------ extra checks for list of point data (leaf? s1 and leaf? s2) => (s1.pt = s2.pt) and (s1.property = s2.property) and (s1.levelField = s2.levelField) -- note that the ordering of children is important #s1.childrenField ~= #s2.childrenField => false and/[c1 = c2 for c1 in s1.childrenField for c2 in s2.childrenField] and (s1.property = s2.property) and (s1.levelField = s2.levelField) coerce(space:%):O == hconcat([n::O,"-Space with depth of "::O, _ (n - space.levelField)::O," and "::O,(s:=(#space.childrenField))::O, _ (s=1 => " component"::O;" components"::O)]) @ \section{package PTPACK PointPackage} <>= )abbrev package PTPACK PointPackage ++ Description: ++ This package \undocumented PointPackage(R:Ring):Exports == Implementation where POINT ==> Point(R) I ==> Integer PI ==> PositiveInteger NNI ==> NonNegativeInteger L ==> List B ==> Boolean Exports == with xCoord : POINT -> R ++ xCoord(pt) returns the first element of the point, pt, ++ although no assumptions are made as to the coordinate ++ system being used. This function is defined for the ++ convenience of the user dealing with a Cartesian ++ coordinate system. yCoord : POINT -> R ++ yCoord(pt) returns the second element of the point, pt, ++ although no assumptions are made as to the coordinate ++ system being used. This function is defined for the ++ convenience of the user dealing with a Cartesian ++ coordinate system. zCoord : POINT -> R ++ zCoord(pt) returns the third element of the point, pt, ++ although no assumptions are made as to the coordinate ++ system being used. This function is defined for the ++ convenience of the user dealing with a Cartesian ++ or a cylindrical coordinate system. rCoord : POINT -> R ++ rCoord(pt) returns the first element of the point, pt, ++ although no assumptions are made as to the coordinate ++ system being used. This function is defined for the ++ convenience of the user dealing with a spherical ++ or a cylindrical coordinate system. thetaCoord : POINT -> R ++ thetaCoord(pt) returns the second element of the point, pt, ++ although no assumptions are made as to the coordinate ++ system being used. This function is defined for the ++ convenience of the user dealing with a spherical ++ or a cylindrical coordinate system. phiCoord : POINT -> R ++ phiCoord(pt) returns the third element of the point, pt, ++ although no assumptions are made as to the coordinate ++ system being used. This function is defined for the ++ convenience of the user dealing with a spherical ++ coordinate system. color : POINT -> R ++ color(pt) returns the fourth element of the point, pt, ++ although no assumptions are made with regards as to ++ how the components of higher dimensional points are ++ interpreted. This function is defined for the ++ convenience of the user using specifically, color ++ to express a fourth dimension. hue : POINT -> R ++ hue(pt) returns the third element of the two dimensional point, pt, ++ although no assumptions are made with regards as to how the ++ components of higher dimensional points are interpreted. This ++ function is defined for the convenience of the user using ++ specifically, hue to express a third dimension. shade : POINT -> R ++ shade(pt) returns the fourth element of the two dimensional ++ point, pt, although no assumptions are made with regards as to ++ how the components of higher dimensional points are interpreted. ++ This function is defined for the convenience of the user using ++ specifically, shade to express a fourth dimension. -- 2D and 3D extraction of data Implementation ==> add xCoord p == elt(p,1) yCoord p == elt(p,2) zCoord p == elt(p,3) rCoord p == elt(p,1) thetaCoord p == elt(p,2) phiCoord p == elt(p,3) color p == #p > 3 => p.4 p.3 hue p == elt(p,3) -- 4D points in 2D using extra dimensions for palette information shade p == elt(p,4) -- 4D points in 2D using extra dimensions for palette information @ \section{package PTFUNC2 PointFunctions2} <>= )abbrev package PTFUNC2 PointFunctions2 ++ Description: ++ This package \undocumented PointFunctions2(R1:Ring,R2:Ring):Exports == Implementation where Exports == with map : ((R1->R2),Point(R1)) -> Point(R2) ++ map(f,p) \undocumented Implementation ==> add import Point(R1) import Point(R2) map(mapping,p) == point([mapping p.(i::PositiveInteger) for i in minIndex(p)..maxIndex(p)])$Point(R2) @ \section{License} <>= --Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd. --All rights reserved. -- --Redistribution and use in source and binary forms, with or without --modification, are permitted provided that the following conditions are --met: -- -- - Redistributions of source code must retain the above copyright -- notice, this list of conditions and the following disclaimer. -- -- - Redistributions in binary form must reproduce the above copyright -- notice, this list of conditions and the following disclaimer in -- the documentation and/or other materials provided with the -- distribution. -- -- - Neither the name of The Numerical ALgorithms Group Ltd. nor the -- names of its contributors may be used to endorse or promote products -- derived from this software without specific prior written permission. -- --THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS --IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED --TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A --PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER --OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, --EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, --PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR --PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF --LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING --NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS --SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. @ <<*>>= <> <> <> <> <> <> <> @ \eject \begin{thebibliography}{99} \bibitem{1} nothing \end{thebibliography} \end{document}