1 // Copyright (c) 2011 Tel-Aviv University (Israel), INRIA Sophia-Antipolis (France). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org). 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Arrangement_on_surface_2/include/CGAL/Arr_rat_arc/Cache.h $ 7 // $Id: Cache.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // Author(s) : Oren Salzman <orenzalz@post.tau.ac.il > 11 // Michael Hemmer <Michael.Hemmer@sophia.inria.fr> 12 13 #ifndef CGAL_RATIONAL_ARC_CACHE 14 #define CGAL_RATIONAL_ARC_CACHE 15 16 #include <CGAL/license/Arrangement_on_surface_2.h> 17 18 19 #include <CGAL/Arr_rat_arc/Base_rational_arc_ds_1.h> 20 #include <CGAL/Arr_rat_arc/Rational_function.h> 21 #include <CGAL/Arr_rat_arc/Rational_function_pair.h> 22 #include <CGAL/Arr_rat_arc/Rational_function_canonicalized_pair.h> 23 24 namespace CGAL { 25 namespace Arr_rational_arc { 26 27 //------------------- 28 //Cache 29 //------------------- 30 template <typename AlgebraicKernel_d_1> 31 class Cache : public Base_rational_arc_ds_1<AlgebraicKernel_d_1> 32 { 33 public: 34 typedef AlgebraicKernel_d_1 Algebraic_kernel_d_1; 35 typedef Base_rational_arc_ds_1<Algebraic_kernel_d_1> Base; 36 typedef Cache<Algebraic_kernel_d_1> Self; 37 38 typedef typename Base::Polynomial_1 Polynomial_1; 39 typedef typename Base::Rational Rational; 40 typedef typename Base::Algebraic_real_1 Algebraic_real_1; 41 typedef typename Base::Integer Integer ; 42 typedef typename Base::FT_rat_1 FT_rat_1; 43 typedef typename Base::Polynomial_traits_1 Polynomial_traits_1; 44 45 typedef CGAL::Arr_rational_arc::Rational_function<Algebraic_kernel_d_1> 46 Rational_function; 47 typedef CGAL::Arr_rational_arc::Rational_function_canonicalized_pair<Algebraic_kernel_d_1> 48 Rational_function_canonicalized_pair; 49 typedef CGAL::Arr_rational_arc::Rational_function_pair<Algebraic_kernel_d_1> 50 Rational_function_pair; 51 52 typedef std::pair<Polynomial_1,Polynomial_1> Rational_function_key; 53 class Less_compare_rational_function_key 54 { 55 public: compare(const Rational_function_key & k1,const Rational_function_key & k2)56 Comparison_result compare(const Rational_function_key& k1, 57 const Rational_function_key& k2) const 58 { 59 Comparison_result cr = 60 typename Polynomial_traits_1::Compare()(k1.first, k2.first); 61 if (cr != CGAL::EQUAL) 62 return (cr); 63 cr = typename Polynomial_traits_1::Compare()(k1.second, k2.second); 64 65 return cr; 66 } 67 operator()68 bool operator()(const Rational_function_key& k1, 69 const Rational_function_key& k2) const 70 { 71 Comparison_result cr = compare(k1,k2); 72 return ((cr == CGAL::LARGER) ? true : false); 73 } 74 }; 75 76 typedef typename std::map<Rational_function_key, 77 Rational_function, 78 Less_compare_rational_function_key> 79 Rational_function_map; 80 81 typedef typename Rational_function::Id_type Rational_function_id_type; 82 typedef std::pair<Rational_function_id_type, Rational_function_id_type> 83 Rational_function_canonicalized_pair_key; 84 85 class Less_compare_rational_function_pair_key 86 { 87 public: operator()88 bool operator()(const Rational_function_canonicalized_pair_key& k1, 89 const Rational_function_canonicalized_pair_key& k2) const 90 { 91 return (k1<k2); 92 } 93 }; 94 95 typedef typename std::map< Rational_function_canonicalized_pair_key, 96 Rational_function_canonicalized_pair, 97 Less_compare_rational_function_pair_key> 98 Rational_function_canonicalized_pair_map; 99 100 public: Cache()101 Cache() : 102 _rat_func_map_watermark(128), _rat_pair_map_watermark(128), _ak_ptr(nullptr){}; 103 initialize(Algebraic_kernel_d_1 * ak_ptr)104 void initialize(Algebraic_kernel_d_1* ak_ptr) 105 { 106 _ak_ptr = ak_ptr; 107 } initialize(const Self & other,Algebraic_kernel_d_1 * ak_ptr)108 void initialize(const Self& other, Algebraic_kernel_d_1* ak_ptr) 109 { 110 //copy kernel pointer 111 _ak_ptr = ak_ptr; 112 113 //copy rational function map 114 typename Rational_function_map::const_iterator iter1; 115 for ( iter1 = other.rat_func_map().begin(); 116 iter1 != other.rat_func_map().end(); 117 ++iter1) 118 { 119 if (iter1->second.is_shared()) 120 { 121 Rational_function_key key = iter1->first; 122 //construct new instance 123 Rational_function f(iter1->second.numer(), iter1->second.denom(), 124 _ak_ptr); 125 _rat_func_map.insert(std::make_pair(key,f)); 126 } 127 } 128 129 //copy rational function pair map 130 typename Rational_function_canonicalized_pair_map::const_iterator iter2; 131 for ( iter2 = other.rat_pair_map().begin(); 132 iter2 != other.rat_pair_map().end(); 133 ++iter2) 134 { 135 if (iter2->second.is_shared()) 136 { 137 Rational_function_canonicalized_pair_key key = iter2->first; 138 //construct new instance 139 Rational_function_canonicalized_pair p(iter2->second.f(), 140 iter2->second.g(), _ak_ptr); 141 _rat_pair_map.insert(std::make_pair(key,p)); 142 } 143 } 144 145 } rat_func_map()146 const Rational_function_map& rat_func_map() const 147 { 148 return _rat_func_map; 149 } 150 rat_pair_map()151 const Rational_function_canonicalized_pair_map& rat_pair_map() const 152 { 153 return _rat_pair_map; 154 } 155 get_rational_function(const Polynomial_1 & numer,const Polynomial_1 & denom)156 const Rational_function& get_rational_function(const Polynomial_1& numer, 157 const Polynomial_1& denom) const 158 { 159 CGAL_precondition (_ak_ptr != nullptr); 160 Rational_function_key key = get_key(numer,denom); 161 162 //look if element exists in cache already 163 typename Rational_function_map::iterator it = _rat_func_map.lower_bound(key); 164 165 if(it != _rat_func_map.end() && !(_rat_func_map.key_comp()(key, it->first))) 166 { 167 return it->second; //iterator to a type <key,value> 168 } 169 else //element does not exist, create it & insert to cache 170 { 171 //first check if to clean up cache 172 if (_rat_func_map.size() > _rat_func_map_watermark) 173 rat_func_map_clean_up(); 174 175 //then insert the new element 176 Rational_function f(numer,denom,_ak_ptr); 177 typename Rational_function_map::iterator it2 = 178 _rat_func_map.insert(it,std::make_pair(key,f)); 179 return it2->second; 180 } 181 } get_rational_function(const Rational & rat)182 const Rational_function& get_rational_function( const Rational& rat) const 183 { 184 Integer numer,denom; 185 typename FT_rat_1::Decompose()(rat,numer,denom); 186 187 Polynomial_1 numer_poly = 188 typename Polynomial_traits_1::Construct_polynomial()(numer); 189 Polynomial_1 denom_poly = 190 typename Polynomial_traits_1::Construct_polynomial()(denom); 191 192 return get_rational_function (numer_poly,denom_poly); 193 } 194 get_rational_pair(const Rational_function & f,const Rational_function & g)195 const Rational_function_pair get_rational_pair(const Rational_function& f, 196 const Rational_function& g) const 197 { 198 CGAL_precondition (_ak_ptr != nullptr); 199 CGAL_precondition(!(f==g)); 200 Rational_function_canonicalized_pair_key key = get_key(f,g); 201 bool is_opposite = (f.id() < g.id()) ? false : true ; 202 203 //look if element exists in cache already 204 typename Rational_function_canonicalized_pair_map::iterator it = 205 _rat_pair_map.lower_bound(key); 206 207 if(it != _rat_pair_map.end() && !(_rat_pair_map.key_comp()(key, it->first))) 208 { 209 return (Rational_function_pair(it->second,is_opposite)); 210 } 211 else //element does not exist, 212 { 213 //first check if to clean up cache 214 if (_rat_pair_map.size() > _rat_pair_map_watermark) 215 rat_pair_map_clean_up(); 216 217 //create it & insert to cache 218 Rational_function_canonicalized_pair p(f, g, _ak_ptr); 219 std::pair<typename Rational_function_canonicalized_pair_map::const_iterator, bool> res = 220 _rat_pair_map.insert(std::make_pair(key,p)); 221 return (Rational_function_pair(res.first->second,is_opposite)); 222 } 223 } 224 cleanup()225 void cleanup() const 226 { 227 rat_pair_map_clean_up(); 228 rat_func_map_clean_up(); 229 } 230 private: get_key(const Polynomial_1 & numer,const Polynomial_1 & denom)231 Rational_function_key get_key(const Polynomial_1& numer, 232 const Polynomial_1& denom) const 233 { 234 return Rational_function_key(numer, denom); 235 } 236 get_key(const Rational_function & f)237 Rational_function_key get_key(const Rational_function& f) const 238 { 239 return get_key(f.numer(), f.denom()); 240 } 241 242 Rational_function_canonicalized_pair_key get_key(const Rational_function & f,const Rational_function & g)243 get_key(const Rational_function& f, const Rational_function& g) const 244 { 245 return (f.id() < g.id()) ? 246 Rational_function_canonicalized_pair_key( f.id(),g.id() ): 247 Rational_function_canonicalized_pair_key( g.id(),f.id() ); 248 249 } 250 rat_func_map_clean_up()251 void rat_func_map_clean_up() const 252 { 253 254 //find eraseable rational functions 255 std::vector<Rational_function_key> eraseable; 256 typename Rational_function_map::iterator iter1; 257 for ( iter1 = _rat_func_map.begin(); 258 iter1 != _rat_func_map.end(); 259 ++iter1) 260 { 261 if (iter1->second.is_shared() == false) 262 eraseable.push_back(iter1->first); 263 } 264 265 //erase functions 266 typename std::vector<Rational_function_key>::iterator iter2; 267 for ( iter2 = eraseable.begin(); 268 iter2 != eraseable.end(); 269 ++iter2) 270 { 271 _rat_func_map.erase(*iter2); 272 } 273 274 //re-set watermark 275 _rat_func_map_watermark 276 = static_cast<unsigned int>((std::max)(2* _rat_func_map.size(), 277 typename Rational_function_map::size_type(128))); 278 return; 279 } rat_pair_map_clean_up()280 void rat_pair_map_clean_up() const 281 { 282 //find eraseable rational functions 283 std::vector<Rational_function_canonicalized_pair_key> eraseable; 284 typename Rational_function_canonicalized_pair_map::iterator iter1; 285 for ( iter1 = _rat_pair_map.begin(); 286 iter1 != _rat_pair_map.end(); 287 ++iter1) 288 { 289 if (iter1->second.is_shared() == false) 290 eraseable.push_back(iter1->first); 291 } 292 293 //erase functions 294 typename std::vector<Rational_function_canonicalized_pair_key>::iterator iter2; 295 for ( iter2 = eraseable.begin(); 296 iter2 != eraseable.end(); 297 ++iter2) 298 { 299 _rat_pair_map.erase(*iter2); 300 } 301 302 //re-set watermark 303 _rat_pair_map_watermark = 304 static_cast<unsigned int>((std::max)(2* _rat_pair_map.size(), 305 typename Rational_function_canonicalized_pair_map::size_type(128))); 306 } 307 308 private: 309 mutable Rational_function_map _rat_func_map; 310 mutable unsigned int _rat_func_map_watermark; 311 mutable Rational_function_canonicalized_pair_map _rat_pair_map; 312 mutable unsigned int _rat_pair_map_watermark; 313 mutable Algebraic_kernel_d_1* _ak_ptr; 314 }; //Cache 315 316 } //namespace Arr_rational_arc 317 } //namespace CGAL { 318 #endif //CGAL_RATIONAL_ARC_CACHE 319