AERN-RnToRm-0.4.9.1: polynomial function enclosures (PFEs) approximating exact real functionsSource codeContentsIndex
Data.Number.ER.RnToRm.BisectionTree
Portabilityportable
Stabilityexperimental
Maintainermik@konecny.aow.cz
Description

Defines a representation for recursive bisections of R^n by hyperplanes, each of which is perpendicular to a base axis.

Arbitrary data can be associated with the sections of a partition.

To be imported qualified, usually with prefix BISTR.

Synopsis
data BisectionTree box varid d v
= Leaf {
bistrDepth :: Depth
bistrDom :: box
bistrVal :: v
}
| Node {
bistrDepth :: Depth
bistrDom :: box
bistrDir :: varid
bistrPt :: d
bistrLO :: BisectionTree box varid d v
bistrHI :: BisectionTree box varid d v
}
type Depth = Int
type ValueSplitter box varid d v = EffortIndex -> Depth -> box -> v -> varid -> d -> (v, v)
type ValueCombiner box varid d v = EffortIndex -> Depth -> BisectionTree box varid d v -> v
isLeaf :: BisectionTree box varid d v -> Bool
const :: box -> v -> BisectionTree box varid d v
removeVars :: (ERIntApprox d, DomainIntBox box varid d, DomainBoxMappable box box varid d d) => box -> BisectionTree box varid d v -> BisectionTree box varid d v
sync2 :: (ERIntApprox d, DomainIntBox box varid d) => ValueSplitter box varid d v1 -> ValueSplitter box varid d v2 -> EffortIndex -> BisectionTree box varid d v1 -> BisectionTree box varid d v2 -> (BisectionTree box varid d v1, BisectionTree box varid d v2)
syncMany :: (ERIntApprox d, DomainIntBox box varid d) => ValueSplitter box varid d v -> EffortIndex -> [BisectionTree box varid d v] -> [BisectionTree box varid d v]
setDepth :: Depth -> BisectionTree box varid d v -> BisectionTree box varid d v
split :: (ERIntApprox d, DomainBox box varid d) => ValueSplitter box varid d v -> EffortIndex -> varid -> d -> box -> BisectionTree box varid d v -> BisectionTree box varid d v
mapWithDom :: DomainBox box varid d => (box -> v1 -> v2) -> BisectionTree box varid d v1 -> BisectionTree box varid d v2
mapLeaves :: (BisectionTree box varid d v1 -> BisectionTree box varid d v2) -> BisectionTree box varid d v1 -> BisectionTree box varid d v2
doBistr :: (box -> v -> IO ()) -> Maybe Int -> BisectionTree box varid d v -> IO ()
doMap :: (Depth -> box -> v -> IO v) -> Maybe Int -> BisectionTree box varid d v -> IO (BisectionTree box varid d v)
doMapLeaves :: (BisectionTree box varid d v -> IO (BisectionTree box varid d v)) -> Maybe Int -> BisectionTree box varid d v -> IO (BisectionTree box varid d v)
combineWith :: (ERIntApprox d, DomainIntBox box varid d) => ValueSplitter box varid d v1 -> ValueSplitter box varid d v2 -> (box -> v1 -> v2 -> (Maybe res, aux)) -> EffortIndex -> BisectionTree box varid d v1 -> BisectionTree box varid d v2 -> (Maybe (BisectionTree box varid d res), [aux])
collectValues :: BisectionTree box varid b a -> [a]
collectDomValues :: BisectionTree box varid d v -> [(box, v)]
compare :: (Ord varid, DomainBox box varid d) => (d -> d -> Ordering) -> (v -> v -> Ordering) -> BisectionTree box varid d v -> BisectionTree box varid d v -> Ordering
lookupSubtreeDoms :: (ERIntApprox d, DomainBox box varid d) => BisectionTree box varid d v -> box -> [BisectionTree box varid d v]
Documentation
data BisectionTree box varid d v Source
  • The root of the tree often represents the whole R^n.
  • Each node splits the parent's space into two using a specified variable (ie direction) and an optional splitting point.
  • By default, a split is taken at the point defined by the method RA.bisect.
Constructors
Leaf
bistrDepth :: Depth
bistrDom :: boxdomain
bistrVal :: vvalue estimate
Node
bistrDepth :: Depthdepth of this node
bistrDom :: boxdomain
bistrDir :: variddirection to split in
bistrPt :: dpoint that the split is at
bistrLO :: BisectionTree box varid d vthe half towards -Infty in split dir
bistrHI :: BisectionTree box varid d vthe half towards +Infty in split dir
show/hide Instances
Typeable4 BisectionTree
(Data box, Data varid, Data d, Data v) => Data (BisectionTree box varid d v)
(VariableID varid, Show d, Show v, DomainBox box varid d) => Show (BisectionTree box varid d v)
(Binary a, Binary b, Binary c, Binary d) => Binary (BisectionTree a b c d)
(Show d, HTML v, DomainBox box varid d) => HTML (BisectionTree box varid d v)
type Depth = IntSource
type ValueSplitter box varid d v = EffortIndex -> Depth -> box -> v -> varid -> d -> (v, v)Source
value splitter function - parameters are: depth, domain of value, value, variable to split by, point to split at; returns the two split values
type ValueCombiner box varid d v = EffortIndex -> Depth -> BisectionTree box varid d v -> vSource
isLeaf :: BisectionTree box varid d v -> BoolSource
const :: box -> v -> BisectionTree box varid d vSource
removeVars :: (ERIntApprox d, DomainIntBox box varid d, DomainBoxMappable box box varid d d) => box -> BisectionTree box varid d v -> BisectionTree box varid d vSource
sync2 :: (ERIntApprox d, DomainIntBox box varid d) => ValueSplitter box varid d v1 -> ValueSplitter box varid d v2 -> EffortIndex -> BisectionTree box varid d v1 -> BisectionTree box varid d v2 -> (BisectionTree box varid d v1, BisectionTree box varid d v2)Source

Ensure both trees have equal structure at the top level: either they are all leaves or they all split at the same direction with the same splitting point.

Also, unify the domains at the top level.

syncMany :: (ERIntApprox d, DomainIntBox box varid d) => ValueSplitter box varid d v -> EffortIndex -> [BisectionTree box varid d v] -> [BisectionTree box varid d v]Source

Ensure all the trees have equal structure at the top level: either they are all leaves or they all split at the same direction with the same splitting point.

Also, unify the domains at the top level.

setDepth :: Depth -> BisectionTree box varid d v -> BisectionTree box varid d vSource
splitSource
:: (ERIntApprox d, DomainBox box varid d)
=> ValueSplitter box varid d v
-> EffortIndex
-> varidvariable x to split by
-> dpoint in domain of x to split at
-> boxdomain to lookup x in if tree's domain does not have x
-> BisectionTree box varid d v
-> BisectionTree box varid d v
mapWithDom :: DomainBox box varid d => (box -> v1 -> v2) -> BisectionTree box varid d v1 -> BisectionTree box varid d v2Source
Apply a function to all values, thus creating a new tree.
mapLeaves :: (BisectionTree box varid d v1 -> BisectionTree box varid d v2) -> BisectionTree box varid d v1 -> BisectionTree box varid d v2Source
Apply a function to all values, thus creating a new tree.
doBistr :: (box -> v -> IO ()) -> Maybe Int -> BisectionTree box varid d v -> IO ()Source
Perform a given action on all branches of a bisection tree, left to right. (optionally now going below the given depth)
doMap :: (Depth -> box -> v -> IO v) -> Maybe Int -> BisectionTree box varid d v -> IO (BisectionTree box varid d v)Source
Perform a given action on all branches of a bisection tree, left to right. (optionally now going below the given depth)
doMapLeaves :: (BisectionTree box varid d v -> IO (BisectionTree box varid d v)) -> Maybe Int -> BisectionTree box varid d v -> IO (BisectionTree box varid d v)Source
Perform a given action on all branches of a bisection tree, left to right with the option of further branching the tree. (optionally now going below the given depth)
combineWithSource
:: (ERIntApprox d, DomainIntBox box varid d)
=> ValueSplitter box varid d v1value splitter function for tree 1
-> ValueSplitter box varid d v2value splitter function for tree 2
-> box -> v1 -> v2 -> (Maybe res, aux)partial function to combine values with
-> EffortIndex
-> BisectionTree box varid d v1
-> BisectionTree box varid d v2
-> (Maybe (BisectionTree box varid d res), [aux])
Combine two bisection trees using a given value combining function. Where necessary, leaves are split so that the resulting tree's structure is the union of the two argument tree structures. Such splitting of values in leaves is performed by the provided functions.
collectValues :: BisectionTree box varid b a -> [a]Source
return all values in leafs (except those within some CE subtree) as a list (from the leftmost to the rightmost)
collectDomValues :: BisectionTree box varid d v -> [(box, v)]Source
return all values in leafs (except those within some CE subtree) as a list (from the leftmost to the rightmost)
compare :: (Ord varid, DomainBox box varid d) => (d -> d -> Ordering) -> (v -> v -> Ordering) -> BisectionTree box varid d v -> BisectionTree box varid d v -> OrderingSource
linear ordering on bisection trees
lookupSubtreeDomsSource
:: (ERIntApprox d, DomainBox box varid d)
=> BisectionTree box varid d v
-> boxdomain to look up within the tree
-> [BisectionTree box varid d v]
lookup all maximal subtrees whose domain intersect the given rectangle
Produced by Haddock version 2.4.2