00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #pragma once
00014
00015 #ifndef __DYNAMICCALYCONSTRUCTEDPATH__
00016 #define __DYNAMICCALYCONSTRUCTEDPATH__
00017
00018
00019 #include "BasePath.h"
00020 #include "DataTree.h"
00021
00023
00027 template <typename my_alg_type>
00028 class DynamicallyConstructedPath :
00029 public BasePath<my_alg_type>
00030 {
00031 typedef std::map < dyadic_interval, Increment<my_alg_type> > DataTree;
00032
00033 private:
00034
00035 MAPS mLibAlgMaps;
00036 CBH mLibAlgCBH;
00037 mutable DataTree mPathData;
00038
00039 public:
00040
00042 DynamicallyConstructedPath(void){};
00044 ~DynamicallyConstructedPath(void){};
00045
00047 LIE DescribePath(const dyadic_interval &increment, const int accuracy) const
00048 {
00049 assert(increment.k >= 0);
00050
00051
00052 typename DataTree::const_iterator itFound = mPathData.find(increment);
00053 if (itFound != mPathData.end())
00054 {
00055
00056 const Increment<my_alg_type> & nvFound = itFound->second;
00057 if (nvFound.Accuracy() >= accuracy)
00058 return nvFound.LieValue();
00059 }
00060
00061
00062 ConstIterator itRoot = mPathData.begin();
00063 if ( itRoot != mPathData.end() )
00064 {
00065
00066 if ((itRoot->first).contains(increment))
00067 {
00068
00069 return DescribePath2(increment, accuracy);
00070 }
00071 else
00072 {
00073
00074 return DescribePath1(increment, accuracy);
00075 }
00076 }
00077 else
00078 {
00079
00080 return DescribePath0(increment, accuracy);
00081 }
00082 };
00083
00084 protected:
00085
00087 typedef typename DataTree::iterator Iterator;
00088 typedef typename DataTree::const_iterator ConstIterator;
00089
00090
00093 virtual void ComputeChildLieIncrements( Increment<my_alg_type> & nvLeft, Increment<my_alg_type> & nvRight, ConstIterator itLeafAbove) const
00094 {
00095 const dyadic_interval & diAbove = itLeafAbove->first;
00096 const Increment<my_alg_type> & nvAbove = itLeafAbove->second;
00097 assert(Increment<my_alg_type>::IsLeaf(itLeafAbove));
00098
00099 nvLeft.LieValue(nvAbove.LieValue()*S(.5));
00100 nvRight.LieValue(nvAbove.LieValue()*S(.5));
00101 };
00102
00103 virtual void MakeNeighborRootLieIncrement( LIE & ans, const Iterator & OldRoot) const
00104 {
00105
00106 dyadic_interval diIncrement = OldRoot->first;
00107 diIncrement.flip_interval();
00108 ans = LIE(1,double(diIncrement.sup())-double(diIncrement.inf()));
00109 };
00110
00112 virtual LIE MakeRootLieIncrement( const dyadic_interval &increment ) const
00113 {
00114 return LIE(1,double(increment.sup())-double(increment.inf()));
00115 };
00116
00117
00118 private:
00120
00123 Iterator InsertChildrenAndRefinePathData ( Iterator itLeafAbove, const dyadic_interval & increment ) const
00124 {
00125 const dyadic_interval & diAbove = itLeafAbove->first;
00126 Increment<my_alg_type> & nvAbove = itLeafAbove->second;
00127
00128 assert(diAbove.contains(increment));
00129 assert(Increment<my_alg_type>::IsLeaf(itLeafAbove));
00130
00131 dyadic_interval diLeft(diAbove), diRight(diAbove);
00132 diLeft.shrink_interval_left();
00133 diRight.shrink_interval_right();
00134
00135 Increment<my_alg_type> nvLeft(diLeft,itLeafAbove,mPathData.end()), nvRight(diRight,itLeafAbove,mPathData.end());
00136
00137 ComputeChildLieIncrements(nvLeft, nvRight, itLeafAbove);
00138
00139 Iterator itLeft = mPathData.insert(
00140 itLeafAbove,
00141 DataTree::value_type(diLeft,nvLeft)
00142 );
00143 Iterator itRight = mPathData.insert(
00144 itLeft,
00145 DataTree::value_type(diRight,nvRight)
00146 );
00147
00148 itLeft->second.mitSibling=itRight;
00149 itRight->second.mitSibling=itLeft;
00150
00151
00152 UpdateAboveLeaf(itLeft);
00153
00154 if (diLeft.contains(increment)) itLeafAbove=itLeft;
00155 else itLeafAbove=itRight;
00156 return itLeafAbove;
00157 };
00158
00159
00160
00161
00166 Iterator UpdateParentAccuracy( Iterator itCurrent ) const
00167 {
00168 const dyadic_interval &
00169 diBelow = itCurrent->first;
00170 Increment<my_alg_type> &
00171 nvBelow = itCurrent->second;
00172 {
00173 Iterator &
00174 itParent = nvBelow.mitParent ;
00175 if ( itParent != mPathData.end() )
00176 {
00177
00178 const dyadic_interval &
00179 diParent = itParent->first;
00180 Increment<my_alg_type> &
00181 nvParent = itParent->second;
00182
00183
00184 Iterator &
00185 itSibling = nvBelow.mitSibling ;
00186 const dyadic_interval &
00187 diSibling = itSibling->first;
00188 Increment<my_alg_type> &
00189 nvSibling = itSibling->second;
00190
00191
00192 int iAccuracyAvailable = std::min(nvBelow.Accuracy(), nvSibling.Accuracy());
00193 if ( nvParent.Accuracy() < iAccuracyAvailable )
00194 {
00195 std::vector <LIE*>
00196 pincs(std::vector<LIE*>::size_type(2));
00197 if (diBelow.aligned())
00198 {
00199 pincs[0]= & nvBelow.LieValue();
00200 pincs[1]= & nvSibling.LieValue();
00201 }
00202 else
00203 {
00204 pincs[1]= & nvBelow.LieValue();
00205 pincs[0]= & nvSibling.LieValue();
00206 }
00207
00208 nvParent.LieValue(mLibAlgCBH.full(pincs));
00209 nvParent.Accuracy(iAccuracyAvailable);
00210 itCurrent = itParent;
00211 }
00212 }
00213 }
00214 return itCurrent;
00215 };
00216
00218 LIE DescribePath2( const dyadic_interval & increment, const int accuracy ) const
00219 {
00220
00221 assert((mPathData.begin()->first).contains(increment) && (accuracy>=increment.n));
00222
00223 std::pair <Iterator, Iterator> itPair = mPathData.equal_range( increment );
00224
00225 if (itPair.first != itPair.second)
00226 {
00227
00228
00229 const Iterator &
00230 itCurrent = itPair.first;
00231 const dyadic_interval &
00232 diCurrent = itCurrent->first;
00233 Increment<my_alg_type> &
00234 nvCurrent = itCurrent->second;
00235
00236
00237 assert(accuracy > nvCurrent.Accuracy());
00238
00239
00240
00241 dyadic_interval diLeft(diCurrent), diRight(diCurrent);
00242 diLeft.shrink_interval_left();
00243 diRight.shrink_interval_right();
00244
00245
00246 DescribePath(diLeft, accuracy);
00247 DescribePath(diRight, accuracy);
00248
00249
00250 assert(accuracy <= nvCurrent.Accuracy());
00251
00252 return nvCurrent.LieValue();
00253 }
00254 else
00255 {
00256
00257
00258 dyadic_interval diRefinedIncrement(increment), diRefinedEnd(increment);
00259 ++diRefinedEnd;
00260
00261 diRefinedIncrement.shrink_interval_left(accuracy-increment.n);
00262 diRefinedEnd.shrink_interval_left(accuracy-increment.n);
00263
00264 for( ; diRefinedIncrement < diRefinedEnd ; ++(++diRefinedIncrement) )
00265 {
00266
00267 Iterator itLeafAbove (mPathData.equal_range( diRefinedIncrement ).first);
00268 itLeafAbove--;
00269
00270 while ((itLeafAbove->first).contains(diRefinedIncrement) && ((itLeafAbove->first) != diRefinedIncrement))
00271 {
00272 itLeafAbove = InsertChildrenAndRefinePathData(itLeafAbove, diRefinedIncrement);
00273 }
00274
00275 UpdateAboveLeaf(itLeafAbove);
00276
00277 }
00278 return DescribePath( increment, accuracy );
00279 }
00280 };
00281
00282 LIE DescribePath1( const dyadic_interval & increment, const int accuracy ) const
00283 {
00284
00285
00286 assert((!((mPathData.begin()->first).contains(increment))) && (accuracy >= increment.n));
00287
00288 Iterator itRoot = mPathData.begin();
00289 while (!((itRoot->first).contains(increment)))
00290 {
00291
00292
00293 const dyadic_interval & diOldRoot = itRoot->first;
00294 Increment<my_alg_type> & nvOldRoot = itRoot->second;
00295
00296 dyadic_interval diNewRoot(diOldRoot);
00297 diNewRoot.expand_interval();
00298 dyadic_interval diNeighbour(diNewRoot);
00299 (diOldRoot.aligned())
00300 ?diNeighbour.shrink_interval_right()
00301 :diNeighbour.shrink_interval_left();
00302
00303 Iterator itNeighbour = mPathData.insert( itRoot, DataTree::value_type(diNeighbour, Increment<my_alg_type>(diNeighbour,mPathData.end(),mPathData.end()) ) );
00304 Increment<my_alg_type> & nvNeighbour = itNeighbour->second;
00305 Iterator itNewRoot = mPathData.insert( itRoot, DataTree::value_type(diNewRoot, Increment<my_alg_type>(diNewRoot,mPathData.end(),mPathData.end()) ) );
00306 Increment<my_alg_type> & nvNewRoot = itNewRoot->second;
00307 nvOldRoot.mitSibling = itNeighbour;
00308 nvOldRoot.mitParent = itNewRoot;
00309 nvNeighbour.mitSibling = itRoot;
00310 nvNeighbour.mitParent = itNewRoot;
00311 MakeNeighborRootLieIncrement(nvNeighbour.LieValue(),itRoot);
00312 UpdateParentAccuracy(itRoot);
00313 itRoot = mPathData.begin();
00314 }
00315 return DescribePath( increment, accuracy );
00316 };
00317
00318 LIE DescribePath0( const dyadic_interval & increment, const int accuracy ) const
00319 {
00320
00321 assert(mPathData.size()==0 && (accuracy>=increment.n));
00322
00323
00324
00325 Increment<my_alg_type> nvData(increment,mPathData.end(),mPathData.end());
00326
00327 Iterator itRoot = mPathData.insert(
00328 DataTree::value_type (increment,nvData)
00329 ).first;
00330
00331 itRoot->second.LieValue(MakeRootLieIncrement(increment));
00332
00333
00334 return DescribePath( increment, accuracy );
00335 };
00336
00337 void UpdateAboveLeaf( Iterator itLeft ) const
00338 {
00339 Iterator top,below (itLeft);
00340 top = UpdateParentAccuracy(below);
00341 while (top != below)
00342 {
00343 below = top;
00344 top = UpdateParentAccuracy(below);
00345 }
00346 };
00347
00348 };
00349
00350 #endif // __DYNAMICCALYCONSTRUCTEDPATH__