src/bisection_tree/refine.rs

Wed, 26 Oct 2022 22:16:57 +0300

author
Tuomo Valkonen <tuomov@iki.fi>
date
Wed, 26 Oct 2022 22:16:57 +0300
changeset 7
860a54fca7bc
parent 5
59dc4c5883f4
child 8
4e09b7829b51
permissions
-rw-r--r--

Added tag unthreaded for changeset d80b87b8acd0

0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
1
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
2 use std::collections::BinaryHeap;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
3 use std::cmp::{PartialOrd,Ord,Ordering,Ordering::*,max};
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
4 use std::rc::Rc;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
5 use std::marker::PhantomData;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
6 use crate::types::*;
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
7 use crate::nanleast::NaNLeast;
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
8 use crate::sets::Cube;
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
9 use super::support::*;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
10 use super::bt::*;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
11 use super::aggregator::*;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
12
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
13 /// Trait for sorting [`Aggregator`]s for [`BT`] refinement.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
14 ///
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
15 /// The sorting involves two sorting keys, the “upper” and the “lower” key. Any [`BT`] nodes
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
16 /// with upper key less the lower key of another are discarded from the refinement process.
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
17 /// Nodes with the highest upper sorting key are picked for refinement.
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
18 pub trait AggregatorSorting {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
19 // Priority
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
20 type Agg : Aggregator;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
21 type Sort : Ord + Copy + std::fmt::Debug;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
22
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
23 /// Returns lower sorting key
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
24 fn sort_lower(aggregator : &Self::Agg) -> Self::Sort;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
25
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
26 /// Returns upper sorting key
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
27 fn sort_upper(aggregator : &Self::Agg) -> Self::Sort;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
28
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
29 /// Returns a sorting key that is less than any other sorting key.
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
30 fn bottom() -> Self::Sort;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
31 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
32
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
33 /// An [`AggregatorSorting`] for [`Bounds`], using the upper/lower bound as the upper/lower key.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
34 ///
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
35 /// See [`LowerBoundSorting`] for the opposite ordering.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
36 pub struct UpperBoundSorting<F : Float>(PhantomData<F>);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
37
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
38 /// An [`AggregatorSorting`] for [`Bounds`], using the upper/lower bound as the lower/upper key.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
39 ///
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
40 /// See [`UpperBoundSorting`] for the opposite ordering.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
41 pub struct LowerBoundSorting<F : Float>(PhantomData<F>);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
42
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
43 impl<F : Float> AggregatorSorting for UpperBoundSorting<F> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
44 type Agg = Bounds<F>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
45 type Sort = NaNLeast<F>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
46
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
47 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
48 fn sort_lower(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(aggregator.lower()) }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
49
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
50 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
51 fn sort_upper(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(aggregator.upper()) }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
52
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
53 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
54 fn bottom() -> Self::Sort { NaNLeast(F::NEG_INFINITY) }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
55 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
56
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
57
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
58 impl<F : Float> AggregatorSorting for LowerBoundSorting<F> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
59 type Agg = Bounds<F>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
60 type Sort = NaNLeast<F>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
61
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
62 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
63 fn sort_upper(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(-aggregator.lower()) }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
64
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
65 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
66 fn sort_lower(aggregator : &Bounds<F>) -> Self::Sort { NaNLeast(-aggregator.upper()) }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
67
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
68 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
69 fn bottom() -> Self::Sort { NaNLeast(F::NEG_INFINITY) }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
70 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
71
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
72 /// Return type of [`Refiner::refine`].
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
73 ///
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
74 /// The parameter `R` is the result type of the refiner acting on an [`Aggregator`] of type `A`.
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
75 pub enum RefinerResult<A : Aggregator, R> {
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
76 /// Indicates an insufficiently refined state: the [`BT`] needs to be further refined.
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
77 NeedRefinement,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
78 /// Indicates a certain result `R`, stop refinement immediately.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
79 Certain(R),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
80 /// Indicates an uncertain result: continue refinement until candidates have been exhausted
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
81 /// or a certain result found.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
82 Uncertain(A, R)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
83 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
84
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
85 use RefinerResult::*;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
86
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
87 /// A `Refiner` is used to search a [`BT`], refining the subdivision when necessary.
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
88 ///
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
89 /// The search is performed by [`BTSearch::search_and_refine`].
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
90 /// The `Refiner` is used to determine whether an [`Aggregator`] `A` stored in the [`BT`] is
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
91 /// sufficiently refined within a [`Cube`], and in such a case, produce a desired result (e.g.
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
92 /// a maximum value of a function).
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
93 pub trait Refiner<F : Float, A, G, const N : usize>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
94 where F : Num,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
95 A : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
96 G : SupportGenerator<F, N> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
97
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
98 /// The result type of the refiner
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
99 type Result : std::fmt::Debug;
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
100 /// The sorting to be employed by [`BTSearch::search_and_refine`] on node aggregators
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
101 /// to detemrine node priority.
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
102 type Sorting : AggregatorSorting<Agg = A>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
103
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
104 /// Determines whether `aggregator` is sufficiently refined within `domain`.
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
105 ///
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
106 /// If the aggregator is sufficiently refined that the desired `Self::Result` can be produced,
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
107 /// a [`RefinerResult`]`::Certain` or `Uncertain` should be returned, depending on
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
108 /// the confidence of the solution. In the uncertain case an improved aggregator should also
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
109 /// be included. If the result cannot be produced, `NeedRefinement` should be
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
110 /// returned.
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
111 ///
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
112 /// For example, if the refiner is used to minimise a function presented by the `BT`,
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
113 /// an `Uncertain` result can be used to return a local maximum of the function on `domain`
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
114 /// The result can be claimed `Certain` if it is a global maximum. In that case the
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
115 /// refinment will stop immediately. A `NeedRefinement` result indicates that the `aggregator`
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
116 /// and/or `domain` are not sufficiently refined to compute a lcoal maximum of sufficient
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
117 /// quality.
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
118 ///
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
119 /// The vector `data` stored all the data of the [`BT`] in the node corresponding to `domain`.
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
120 /// The `generator` can be used to convert `data` into [`Support`]s. The parameter `step`
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
121 /// counts the calls to `refine`, and can be used to stop the refinement when a maximum
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
122 /// number of steps is reached.
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
123 fn refine(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
124 &self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
125 aggregator : &A,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
126 domain : &Cube<F, N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
127 data : &Vec<G::Id>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
128 generator : &G,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
129 step : usize,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
130 ) -> RefinerResult<A, Self::Result>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
131 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
132
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
133 /// Structure for tracking the refinement process in a [`BinaryHeap`].
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
134 struct RefinementInfo<'a, F, D, A, S, RResult, const N : usize, const P : usize>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
135 where F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
136 D : 'static +,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
137 A : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
138 S : AggregatorSorting<Agg = A> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
139 cube : Cube<F, N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
140 node : &'a mut Node<F, D, A, N, P>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
141 refiner_info : Option<(A, RResult)>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
142 sorting : PhantomData<S>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
143 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
144
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
145 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
146 RefinementInfo<'a, F, D, A, S, RResult, N, P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
147 where F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
148 D : 'static,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
149 A : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
150 S : AggregatorSorting<Agg = A> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
151
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
152 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
153 fn aggregator(&self) -> &A {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
154 match self.refiner_info {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
155 Some((ref agg, _)) => agg,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
156 None => &self.node.aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
157 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
158 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
159
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
160 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
161 fn sort_lower(&self) -> S::Sort {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
162 S::sort_lower(self.aggregator())
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
163 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
164
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
165 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
166 fn sort_upper(&self) -> S::Sort {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
167 S::sort_upper(self.aggregator())
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
168 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
169 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
170
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
171 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> PartialEq
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
172 for RefinementInfo<'a, F, D, A, S, RResult, N, P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
173 where F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
174 D : 'static,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
175 A : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
176 S : AggregatorSorting<Agg = A> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
177
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
178 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
179 fn eq(&self, other : &Self) -> bool { self.cmp(other) == Equal }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
180 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
181
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
182 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> PartialOrd
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
183 for RefinementInfo<'a, F, D, A, S, RResult, N, P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
184 where F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
185 D : 'static,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
186 A : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
187 S : AggregatorSorting<Agg = A> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
188
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
189 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
190 fn partial_cmp(&self, other : &Self) -> Option<Ordering> { Some(self.cmp(other)) }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
191 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
192
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
193 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> Eq
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
194 for RefinementInfo<'a, F, D, A, S, RResult, N, P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
195 where F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
196 D : 'static,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
197 A : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
198 S : AggregatorSorting<Agg = A> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
199 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
200
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
201 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize> Ord
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
202 for RefinementInfo<'a, F, D, A, S, RResult, N, P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
203 where F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
204 D : 'static,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
205 A : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
206 S : AggregatorSorting<Agg = A> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
207
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
208 #[inline]
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
209 fn cmp(&self, other : &Self) -> Ordering {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
210 let agg1 = self.aggregator();
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
211 let agg2 = other.aggregator();
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
212 match S::sort_upper(agg1).cmp(&S::sort_upper(agg2)) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
213 Equal => S::sort_lower(agg1).cmp(&S::sort_lower(agg2)),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
214 order => order,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
215 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
216 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
217 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
218
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
219 /// This is a container for a [`BinaryHeap`] of [`RefinementInfo`]s together with tracking of
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
220 /// the greatest lower bound of the [`Aggregator`]s of the [`Node`]s therein accroding to
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
221 /// chosen [`AggregatorSorting`].
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
222 struct HeapContainer<'a, F, D, A, S, RResult, const N : usize, const P : usize>
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
223 where F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
224 D : 'static + Copy,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
225 Const<P> : BranchCount<N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
226 A : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
227 S : AggregatorSorting<Agg = A> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
228 heap : BinaryHeap<RefinementInfo<'a, F, D, A, S, RResult, N, P>>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
229 glb : S::Sort,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
230 glb_stale_counter : usize,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
231 stale_insert_counter : usize,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
232 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
233
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
234 impl<'a, F, D, A, S, RResult, const N : usize, const P : usize>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
235 HeapContainer<'a, F, D, A, S, RResult, N, P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
236 where F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
237 D : 'static + Copy,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
238 Const<P> : BranchCount<N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
239 A : Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
240 S : AggregatorSorting<Agg = A> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
241
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
242 /// Push `ri` into the [`BinaryHeap`]. Do greatest lower bound maintenance.
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
243 fn push(&mut self, ri : RefinementInfo<'a, F, D, A, S, RResult, N, P>) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
244 if ri.sort_upper() >= self.glb {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
245 let l = ri.sort_lower();
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
246 self.heap.push(ri);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
247 self.glb = self.glb.max(l);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
248 if self.glb_stale_counter > 0 {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
249 self.stale_insert_counter += 1;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
250 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
251 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
252 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
253 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
254
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
255 impl<F : Float, D : 'static + Copy, A, const N : usize, const P : usize>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
256 Branches<F,D,A,N,P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
257 where Const<P> : BranchCount<N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
258 A : Aggregator {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
259
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
260 /// Stage all subnodes of `self` into the refinement queue [`container`].
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
261 fn stage_refine<'a, S, RResult>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
262 &'a mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
263 domain : Cube<F,N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
264 container : &mut HeapContainer<'a, F, D, A, S, RResult, N, P>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
265 ) where S : AggregatorSorting<Agg = A> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
266 // Insert all subnodes into the refinement heap.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
267 for (node, subcube) in self.nodes_and_cubes_mut(&domain) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
268 container.push(RefinementInfo {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
269 cube : subcube,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
270 node : node,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
271 refiner_info : None,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
272 sorting : PhantomData,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
273 });
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
274 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
275 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
276 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
277
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
278
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
279 impl<F : Float, D : 'static + Copy, A, const N : usize, const P : usize>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
280 Node<F,D,A,N,P>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
281 where Const<P> : BranchCount<N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
282 A : Aggregator {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
283
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
284 /// If `self` is a leaf node, uses the `refiner` to determine whether further subdivision
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
285 /// is required to get a sufficiently refined solution for the problem the refiner is used
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
286 /// to solve. If the refiner returns [`RefinerResult::Certain`] result, it is returned.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
287 /// If [`RefinerResult::Uncertain`] is returned, the leaf is inserted back into the refinement
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
288 /// queue `container`. If `self` is a branch, its subnodes are staged into `container` using
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
289 /// [`Branches::stage_refine`].
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
290 ///
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
291 /// `domain`, as usual, indicates the spatial area corresponding to `self`.
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
292 fn search_and_refine<'a, 'b, R, G>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
293 &'a mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
294 domain : Cube<F,N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
295 refiner : &R,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
296 generator : &G,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
297 container : &'b mut HeapContainer<'a, F, D, A, R::Sorting, R::Result, N, P>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
298 step : usize
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
299 ) -> Option<R::Result>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
300 where R : Refiner<F, A, G, N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
301 G : SupportGenerator<F, N, Id=D>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
302 G::SupportType : LocalAnalysis<F, A, N> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
303
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
304 // The “complex” repeated pattern matching here is forced by mutability requirements.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
305
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
306 // Refine a leaf.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
307 let res = if let NodeOption::Leaf(ref v) = &mut self.data {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
308 let res = refiner.refine(&self.aggregator, &domain, v, generator, step);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
309 if let NeedRefinement = res {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
310 // The refiner has deemed the leaf unsufficiently refined, so subdivide
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
311 // it and add the new nodes into the refinement priority heap.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
312 // We start iterating from the end to mix support_hint a bit.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
313 let mut it = v.iter().rev();
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
314 if let Some(&d) = it.next() {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
315 // Construct new Branches
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
316 let support = generator.support_for(d);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
317 let b = Rc::new({
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
318 let mut b0 = Branches::new_with(&domain, &support);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
319 b0.insert(&domain, d, Const::<1>, &support);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
320 for &d in it {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
321 let support = generator.support_for(d);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
322 // TODO: can we be smarter than just refining one level?
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
323 b0.insert(&domain, d, Const::<1>, &support);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
324 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
325 b0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
326 });
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
327 // Update current node
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
328 self.aggregator.summarise(b.aggregators());
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
329 self.data = NodeOption::Branches(b);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
330 // The branches will be inserted into the refinement priority queue below.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
331 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
332 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
333 res
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
334 } else {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
335 NeedRefinement
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
336 };
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
337
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
338 if let Uncertain(agg, val) = res {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
339 // The refiner gave an undertain result. Push a leaf back into the refinement queue
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
340 // with the new refined aggregator and custom return value. It will be popped and
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
341 // returned in the loop of [`BT::search_and_refine`] when there are no unrefined
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
342 // candidates that could potentially be better according to their basic aggregator.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
343 container.push(RefinementInfo {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
344 cube : domain,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
345 node : self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
346 refiner_info : Some((agg, val)),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
347 sorting : PhantomData,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
348 });
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
349 None
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
350 } else if let Certain(val) = res {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
351 // The refiner gave a certain result so return it to allow early termination
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
352 Some(val)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
353 } else if let NodeOption::Branches(ref mut b) = &mut self.data {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
354 // Insert branches into refinement priority queue.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
355 Rc::make_mut(b).stage_refine(domain, container);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
356 None
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
357 } else {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
358 None
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
359 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
360 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
361 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
362
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
363 /// Interface trait to a refining search on a [`BT`].
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
364 ///
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
365 /// This can be removed and the methods implemented directly on [`BT`] once Rust's const generics
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
366 /// are flexible enough to allow fixing `P=pow(2, N)`.
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
367 pub trait BTSearch<F, const N : usize> : BTImpl<F, N>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
368 where F : Float {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
369
5
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
370 /// Perform a search on [`Self`], as determined by `refiner`.
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
371 ///
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
372 /// Nodes are inserted in a priority queue and processed in the order determined by the
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
373 /// [`AggregatorSorting`] [`Refiner::Sorting`]. Leaf nodes are subdivided until the refiner
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
374 /// decides that a sufficiently refined leaf node has been found, as determined by either the
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
375 /// refiner returning a [`RefinerResult::Certain`] result, or a previous
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
376 /// [`RefinerResult::Uncertain`] result is found again at the top of the priority queue.
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
377 ///
59dc4c5883f4 Improve documentation
Tuomo Valkonen <tuomov@iki.fi>
parents: 0
diff changeset
378 /// The `generator` converts [`BTImpl::Data`] stored in the bisection tree into a [`Support`].
0
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
379 fn search_and_refine<'b, R, G>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
380 &'b mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
381 refiner : &R,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
382 generator : &G,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
383 ) -> Option<R::Result>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
384 where R : Refiner<F, Self::Agg, G, N>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
385 G : SupportGenerator<F, N, Id=Self::Data>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
386 G::SupportType : LocalAnalysis<F, Self::Agg, N>;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
387 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
388
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
389 // Needed to get access to a Node without a trait interface.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
390 macro_rules! impl_btsearch {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
391 ($($n:literal)*) => { $(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
392 impl<'a, M, F, D, A>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
393 BTSearch<F, $n>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
394 for BT<M,F,D,A,$n>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
395 where //Self : BTImpl<F,$n,Data=D,Agg=A, Depth=M>, // <== automatically deduce to be implemented
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
396 M : Depth,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
397 F : Float,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
398 A : 'a + Aggregator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
399 D : 'static + Copy + std::fmt::Debug {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
400 fn search_and_refine<'b, R, G>(
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
401 &'b mut self,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
402 refiner : &R,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
403 generator : &G,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
404 ) -> Option<R::Result>
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
405 where R : Refiner<F, A, G, $n>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
406 G : SupportGenerator<F, $n, Id=D>,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
407 G::SupportType : LocalAnalysis<F, A, $n> {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
408 let mut container = HeapContainer {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
409 heap : BinaryHeap::new(),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
410 glb : R::Sorting::bottom(),
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
411 glb_stale_counter : 0,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
412 stale_insert_counter : 0,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
413 };
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
414 container.push(RefinementInfo {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
415 cube : self.domain,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
416 node : &mut self.topnode,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
417 refiner_info : None,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
418 sorting : PhantomData,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
419 });
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
420 let mut step = 0;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
421 while let Some(ri) = container.heap.pop() {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
422 if let Some((_, result)) = ri.refiner_info {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
423 // Terminate based on a “best possible” result.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
424 return Some(result)
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
425 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
426
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
427 if ri.sort_lower() >= container.glb {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
428 container.glb_stale_counter += 1;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
429 if container.stale_insert_counter + container.glb_stale_counter
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
430 > container.heap.len()/2 {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
431 // GLB propery no longer correct.
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
432 match container.heap.iter().map(|ri| ri.sort_lower()).reduce(max) {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
433 Some(glb) => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
434 container.glb = glb;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
435 container.heap.retain(|ri| ri.sort_upper() >= glb);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
436 },
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
437 None => {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
438 container.glb = R::Sorting::bottom()
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
439 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
440 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
441 container.glb_stale_counter = 0;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
442 container.stale_insert_counter = 0;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
443 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
444 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
445
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
446 let res = ri.node.search_and_refine(ri.cube, refiner, generator,
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
447 &mut container, step);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
448 if let Some(_) = res {
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
449 // Terminate based on a certain result from the refiner
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
450 return res
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
451 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
452
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
453 step += 1;
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
454 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
455 None
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
456 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
457 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
458 )* }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
459 }
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
460
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
461 impl_btsearch!(1 2 3 4);
9f27689eb130 Initialise new clean repository
Tuomo Valkonen <tuomov@iki.fi>
parents:
diff changeset
462

mercurial