AERN-RnToRm-0.5: polynomial function enclosures (PFEs) approximating exact real functions

Portabilityportable
Stabilityexperimental
Maintainermik@konecny.aow.cz

Data.Number.ER.RnToRm.BisectionTree

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

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 

Fields

bistrDepth :: Depth
 
bistrDom :: box

domain

bistrVal :: v

value estimate

Node 

Fields

bistrDepth :: Depth
 
bistrDom :: box

domain

bistrDir :: varid

direction to split in

bistrPt :: d

point that the split is at

bistrLO :: BisectionTree box varid d v

the half towards -Infty in split dir

bistrHI :: BisectionTree box varid d v

the half towards +Infty in split dir

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 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

Arguments

:: (ERIntApprox d, DomainBox box varid d) 
=> ValueSplitter box varid d v 
-> EffortIndex 
-> varid

variable x to split by

-> d

point in domain of x to split at

-> box

domain 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

Arguments

:: (ERIntApprox d, DomainIntBox box varid d) 
=> ValueSplitter box varid d v1

value splitter function for tree 1

-> ValueSplitter box varid d v2

value 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

Arguments

:: (ERIntApprox d, DomainBox box varid d) 
=> BisectionTree box varid d v 
-> box

domain to look up within the tree

-> [BisectionTree box varid d v] 

lookup all maximal subtrees whose domain intersect the given rectangle