1 // This file has been generated by Py++. 2 3 // Header file algorithms.hpp 4 // 5 // Uniform interface layer for all containers. 6 // 7 // Copyright (c) 2003 Raoul M. Gough 8 // 9 // Use, modification and distribution is subject to the Boost Software 10 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy 11 // at http://www.boost.org/LICENSE_1_0.txt) 12 // 13 // History 14 // ======= 15 // 2003/ 9/11 rmg File creation from suite_utils.hpp 16 // 2003/10/28 rmg Split container-specific versions into separate headers 17 // 2006/10/25 Roman Adding keys function to assoc_algorithms class 18 // 2008/12/08 Roman Change indexing suite layout 19 // 20 // $Id: algorithms.hpp,v 1.1.2.15 2004/02/08 18:57:42 raoulgough Exp $ 21 // 22 23 #ifndef BOOST_PYTHON_INDEXING_ALGORITHMS_HPP 24 #define BOOST_PYTHON_INDEXING_ALGORITHMS_HPP 25 26 #include <indexing_suite/suite_utils.hpp> 27 28 #include <boost/type_traits.hpp> 29 #include <boost/python/errors.hpp> 30 #include <indexing_suite/int_slice_helper.hpp> 31 #include <indexing_suite/slice.hpp> 32 #include <boost/mpl/if.hpp> 33 #include <boost/limits.hpp> 34 #include <algorithm> 35 #include <functional> 36 #include <stdexcept> 37 #include <string> 38 #include <set> 39 40 namespace boost { namespace python { namespace indexing { 41 template<typename ContainerTraits, typename Ovr = detail::no_override> 42 class default_algorithms 43 { 44 typedef default_algorithms<ContainerTraits, Ovr> self_type; 45 typedef typename detail::maybe_override<self_type, Ovr> 46 ::type most_derived; 47 48 public: 49 typedef ContainerTraits container_traits; 50 51 // Import typedefs from the container_traits for convenience 52 typedef typename ContainerTraits::container container; 53 typedef typename ContainerTraits::iterator iterator; 54 typedef typename ContainerTraits::reference reference; 55 typedef typename ContainerTraits::size_type size_type; 56 typedef typename ContainerTraits::value_type value_type; 57 typedef typename ContainerTraits::value_param value_param; 58 typedef typename ContainerTraits::index_param index_param; 59 typedef typename ContainerTraits::key_param key_param; 60 61 // Defer selection of supported_methods to the ContainerTraits 62 // template argument. This makes sense because default_algorithms 63 // derives all of its other information from this argument, and 64 // can't decide which of the static member functions will 65 // instantiate successfully for the container. Obviously a 66 // custom-written Algorithms implementation could choose to 67 // provide the supported_methods directly. 68 69 BOOST_STATIC_CONSTANT( 70 method_set_type, 71 supported_methods = ContainerTraits::supported_methods); 72 73 static size_type size (container &); 74 static iterator find (container &, key_param); 75 static size_type get_index (container &, key_param); 76 static size_type count (container &, key_param); 77 static bool contains (container &, key_param); 78 static void reverse (container &); 79 static reference get (container &, index_param); 80 static void assign (container &, index_param, value_param); 81 static void insert (container &, index_param, value_param); 82 static void erase_one (container &, index_param); 83 static void erase_range(container &, index_param, index_param); 84 static void push_back (container &, value_param); 85 static void sort (container &); 86 // static void sort (container &, PyObject *); 87 begin(container & c)88 static iterator begin (container &c) { return c.begin(); } end(container & c)89 static iterator end (container &c) { return c.end(); } 90 91 // Reasonable defaults for slice handling 92 typedef int_slice_helper<self_type, integer_slice> slice_helper; 93 94 static slice_helper make_slice_helper (container &c, slice const &); 95 96 // Default visit_container_class 97 template<typename PythonClass, typename Policy> visit_container_class(PythonClass & pyClass,Policy const & policy)98 static void visit_container_class( 99 PythonClass &pyClass, Policy const &policy) 100 { 101 container_traits::visit_container_class (pyClass, policy); 102 } 103 104 #if BOOST_WORKAROUND(BOOST_MSVC, <= 1300) 105 // MSVC6 and 7.0 seem to complain about most_derived::bounds_check 106 // for an instantiation of list_algorithms. 107 public: 108 #else 109 private: 110 #endif 111 static size_type bounds_check( 112 container &, index_param, char const *msg, 113 bool one_past = false, 114 bool truncate = false); 115 // Throws std::out_of_range if necessary. If one_past is set, then 116 // indexes up to container.size() *inclusive* are allowed. If 117 // truncate is set, then out of bounds values are reset to the 118 // nearest in-bound value (and if none exists, throws an 119 // exception). If truncate is *not* set, then negative values index 120 // from the upper bound backwards and are bounds-checked. 121 }; 122 123 ///////////////////////////////////////////////////////////////////////// 124 // Base class for associative containers 125 ///////////////////////////////////////////////////////////////////////// 126 127 template<typename ContainerTraits, typename Ovr = detail::no_override> 128 class assoc_algorithms 129 : public default_algorithms 130 <ContainerTraits, 131 BOOST_DEDUCED_TYPENAME detail::maybe_override 132 <assoc_algorithms<ContainerTraits, Ovr>, Ovr> 133 ::type> 134 { 135 typedef assoc_algorithms<ContainerTraits, Ovr> self_type; 136 typedef typename detail::maybe_override<self_type, Ovr> 137 ::type most_derived; 138 typedef default_algorithms<ContainerTraits, most_derived> Parent; 139 140 public: 141 typedef typename Parent::iterator iterator; 142 typedef typename Parent::size_type size_type; 143 typedef typename Parent::container container; 144 typedef typename Parent::reference reference; 145 typedef typename Parent::key_param key_param; 146 typedef typename Parent::value_param value_param; 147 typedef typename Parent::index_param index_param; 148 149 static reference get (container &, index_param); 150 151 // Use member functions for the following (hiding base class versions) 152 static void erase_one (container &, key_param); 153 static iterator find (container &, key_param); 154 static size_type count (container &, key_param); 155 static bool contains (container &, key_param); 156 157 // Default visit_container_class 158 template<typename PythonClass, typename Policy> visit_container_class(PythonClass & pyClass,Policy const & policy)159 static void visit_container_class( PythonClass &pyClass, Policy const &policy) 160 { 161 ContainerTraits::visit_container_class (pyClass, policy); 162 } 163 164 165 protected: 166 static iterator find_or_throw (container &, index_param); 167 }; 168 169 ///////////////////////////////////////////////////////////////////////// 170 // Get the size of a container 171 ///////////////////////////////////////////////////////////////////////// 172 173 template<typename ContainerTraits, typename Ovr> 174 BOOST_DEDUCED_TYPENAME default_algorithms<ContainerTraits, Ovr>::size_type size(container & c)175 default_algorithms<ContainerTraits, Ovr>::size (container &c) 176 { 177 return c.size(); 178 } 179 180 ///////////////////////////////////////////////////////////////////////// 181 // Range check an index and throw out_of_range if necessary 182 ///////////////////////////////////////////////////////////////////////// 183 184 template<typename ContainerTraits, typename Ovr> 185 BOOST_DEDUCED_TYPENAME default_algorithms<ContainerTraits, Ovr>::size_type bounds_check(container & c,index_param ix,char const * msg,bool one_past,bool truncate)186 default_algorithms<ContainerTraits, Ovr>::bounds_check( 187 container &c, 188 index_param ix, 189 char const *msg, 190 bool one_past, 191 bool truncate) 192 { 193 size_type bound = most_derived::size(c) + (one_past ? 1 : 0); 194 size_type result; 195 196 if (truncate) 197 { 198 if (ix < 0) 199 { 200 result = 0; 201 } 202 203 else 204 { 205 result = ix; 206 207 if ((result >= bound) && (bound > 0)) 208 { 209 result = bound - 1; 210 } 211 } 212 } 213 214 else if (ix < 0) 215 { 216 if (size_type(-ix) > bound) 217 { 218 throw std::out_of_range (msg); 219 } 220 221 result = bound + ix; 222 } 223 224 else 225 { 226 result = ix; 227 } 228 229 if (result >= bound) 230 { 231 throw std::out_of_range (msg); 232 } 233 234 return result; 235 } 236 237 ///////////////////////////////////////////////////////////////////////// 238 // Find an element in a container (std algorithm version) 239 ///////////////////////////////////////////////////////////////////////// 240 241 template<typename ContainerTraits, typename Ovr> 242 BOOST_DEDUCED_TYPENAME default_algorithms<ContainerTraits, Ovr>::iterator find(container & c,key_param key)243 default_algorithms<ContainerTraits, Ovr>::find( 244 container &c, key_param key) 245 { 246 typedef typename container_traits::value_traits_type vtraits; 247 typedef typename vtraits::equal_to comparison; 248 249 return std::find_if( 250 most_derived::begin(c), 251 most_derived::end(c), 252 std::bind1st (comparison(), key)); 253 } 254 255 ///////////////////////////////////////////////////////////////////////// 256 // Find an element and return its index (std algorithm version) 257 ///////////////////////////////////////////////////////////////////////// 258 259 template<typename ContainerTraits, typename Ovr> 260 BOOST_DEDUCED_TYPENAME default_algorithms<ContainerTraits, Ovr>::size_type get_index(container & c,key_param key)261 default_algorithms<ContainerTraits, Ovr>::get_index( 262 container &c, key_param key) 263 { 264 iterator found (most_derived::find (c, key)); 265 266 if (found == most_derived::end(c)) 267 { 268 PyErr_SetString( 269 PyExc_ValueError, "get_index: element not found"); 270 271 boost::python::throw_error_already_set (); 272 } 273 274 iterator start (most_derived::begin (c)); 275 return std::distance (start, found); 276 } 277 278 ///////////////////////////////////////////////////////////////////////// 279 // Count occurances of an element in a container (std algorithm version) 280 ///////////////////////////////////////////////////////////////////////// 281 282 template<typename ContainerTraits, typename Ovr> 283 BOOST_DEDUCED_TYPENAME default_algorithms<ContainerTraits, Ovr>::size_type count(container & c,key_param key)284 default_algorithms<ContainerTraits, Ovr>::count( 285 container &c, key_param key) 286 { 287 typedef typename container_traits::value_traits_type vtraits; 288 typedef typename vtraits::equal_to comparison; 289 290 return std::count_if( 291 most_derived::begin(c), 292 most_derived::end(c), 293 std::bind1st (comparison(), key)); 294 } 295 296 ///////////////////////////////////////////////////////////////////////// 297 // Check whether a container contains the given element (std algo ver) 298 ///////////////////////////////////////////////////////////////////////// 299 300 template<typename ContainerTraits, typename Ovr> 301 bool contains(container & c,key_param key)302 default_algorithms<ContainerTraits, Ovr>::contains( 303 container &c, key_param key) 304 { 305 return most_derived::find (c, key) != most_derived::end(c); 306 } 307 308 ///////////////////////////////////////////////////////////////////////// 309 // Index into a container (generic version) 310 ///////////////////////////////////////////////////////////////////////// 311 312 template<typename ContainerTraits, typename Ovr> 313 BOOST_DEDUCED_TYPENAME default_algorithms<ContainerTraits, Ovr>::reference get(container & c,index_param ix)314 default_algorithms<ContainerTraits, Ovr>::get( 315 container &c, index_param ix) 316 { 317 return c[most_derived::bounds_check (c, ix, "get")]; 318 } 319 320 ///////////////////////////////////////////////////////////////////////// 321 // Assign a value at a particular index (generic version) 322 ///////////////////////////////////////////////////////////////////////// 323 324 template<typename ContainerTraits, typename Ovr> 325 void assign(container & c,index_param ix,value_param val)326 default_algorithms<ContainerTraits, Ovr>::assign( 327 container &c, index_param ix, value_param val) 328 { 329 c[most_derived::bounds_check (c, ix, "assign")] = val; 330 } 331 332 ///////////////////////////////////////////////////////////////////////// 333 // Insert at end of a container (generic version) 334 ///////////////////////////////////////////////////////////////////////// 335 336 template<typename ContainerTraits, typename Ovr> 337 void push_back(container & c,value_param v)338 default_algorithms<ContainerTraits, Ovr>::push_back( 339 container &c, value_param v) 340 { 341 c.push_back (v); 342 } 343 344 ///////////////////////////////////////////////////////////////////////// 345 // Insert at an index in the container (generic version) 346 ///////////////////////////////////////////////////////////////////////// 347 348 template<typename ContainerTraits, typename Ovr> 349 void insert(container & c,index_param i,value_param v)350 default_algorithms<ContainerTraits, Ovr>::insert( 351 container &c, index_param i, value_param v) 352 { 353 iterator insert_pos (most_derived::begin(c)); 354 355 // Index may range up to c.size() inclusive to allow inserting at end 356 std::advance( 357 insert_pos, most_derived::bounds_check (c, i, "insert", true, true)); 358 359 c.insert (insert_pos, v); 360 } 361 362 ///////////////////////////////////////////////////////////////////////// 363 // Erase between given indexes in the container (generic version) 364 ///////////////////////////////////////////////////////////////////////// 365 366 template<typename ContainerTraits, typename Ovr> 367 void erase_range(container & c,index_param from,index_param to)368 default_algorithms<ContainerTraits, Ovr>::erase_range( 369 container &c, index_param from, index_param to) 370 { 371 iterator start (most_derived::begin(c)); 372 iterator finish (most_derived::begin(c)); 373 374 // Start index must be properly in bounds 375 std::advance 376 (start, most_derived::bounds_check (c, from, "erase_range (from)")); 377 378 // End index is one-past-the-end, so may range up to c.size() inclusive 379 std::advance 380 (finish, most_derived::bounds_check (c, to, "erase_range (to)", true)); 381 382 c.erase (start, finish); 383 } 384 385 ///////////////////////////////////////////////////////////////////////// 386 // Erase one element at the given index in the container (generic version) 387 ///////////////////////////////////////////////////////////////////////// 388 389 template<typename ContainerTraits, typename Ovr> 390 void erase_one(container & c,index_param ix)391 default_algorithms<ContainerTraits, Ovr>::erase_one( 392 container &c, index_param ix) 393 { 394 iterator iter (most_derived::begin(c)); 395 std::advance (iter, most_derived::bounds_check (c, ix, "erase_one")); 396 c.erase (iter); 397 } 398 399 ///////////////////////////////////////////////////////////////////////// 400 // Reverse the contents of a container (std algorithm version) 401 ///////////////////////////////////////////////////////////////////////// 402 403 template<typename ContainerTraits, typename Ovr> reverse(container & c)404 void default_algorithms<ContainerTraits, Ovr>::reverse (container &c) 405 { 406 std::reverse (most_derived::begin(c), most_derived::end(c)); 407 } 408 409 ///////////////////////////////////////////////////////////////////////// 410 // Sort the contents of a container (std algorithm version) 411 ///////////////////////////////////////////////////////////////////////// 412 413 template<typename ContainerTraits, typename Ovr> sort(container & c)414 void default_algorithms<ContainerTraits, Ovr>::sort (container &c) 415 { 416 typedef typename container_traits::value_traits_type vtraits; 417 typedef typename vtraits::less comparison; 418 std::sort (most_derived::begin(c), most_derived::end(c), comparison()); 419 } 420 421 ///////////////////////////////////////////////////////////////////////// 422 // slice_helper factory function (default version) 423 ///////////////////////////////////////////////////////////////////////// 424 425 template<typename ContainerTraits, typename Ovr> 426 BOOST_DEDUCED_TYPENAME default_algorithms<ContainerTraits, Ovr>::slice_helper 427 default_algorithms<ContainerTraits, Ovr> make_slice_helper(container & c,slice const & sl)428 ::make_slice_helper (container &c, slice const &sl) 429 { 430 return slice_helper (c, integer_slice (sl, most_derived::size (c))); 431 } 432 433 ///////////////////////////////////////////////////////////////////////// 434 // Index into a container (associative version) 435 ///////////////////////////////////////////////////////////////////////// 436 437 template<typename ContainerTraits, typename Ovr> 438 BOOST_DEDUCED_TYPENAME assoc_algorithms<ContainerTraits, Ovr>::reference get(container & c,index_param ix)439 assoc_algorithms<ContainerTraits, Ovr>::get (container &c, index_param ix) 440 { 441 return *most_derived::find_or_throw (c, ix); 442 } 443 444 ///////////////////////////////////////////////////////////////////////// 445 // Erase elements with the given key (associative version) 446 ///////////////////////////////////////////////////////////////////////// 447 448 template<typename ContainerTraits, typename Ovr> 449 void erase_one(container & c,key_param key)450 assoc_algorithms<ContainerTraits, Ovr>::erase_one( 451 container &c, key_param key) 452 { 453 if (c.erase (key) == 0) 454 { 455 PyErr_SetString( 456 PyExc_ValueError, "Container does not hold value to be erased"); 457 458 boost::python::throw_error_already_set (); 459 } 460 } 461 462 ///////////////////////////////////////////////////////////////////////// 463 // Find an element in an associative container 464 ///////////////////////////////////////////////////////////////////////// 465 466 template<typename ContainerTraits, typename Ovr> 467 BOOST_DEDUCED_TYPENAME assoc_algorithms<ContainerTraits, Ovr>::iterator 468 assoc_algorithms<ContainerTraits, Ovr> find(container & c,key_param key)469 ::find (container &c, key_param key) 470 { 471 return c.find (key); 472 } 473 474 ///////////////////////////////////////////////////////////////////////// 475 // Find an element in an associative container 476 ///////////////////////////////////////////////////////////////////////// 477 478 template<typename ContainerTraits, typename Ovr> 479 bool contains(container & c,key_param key)480 assoc_algorithms<ContainerTraits, Ovr>::contains( 481 container &c, key_param key) 482 { 483 return most_derived::find (c, key) != most_derived::end(c); 484 } 485 486 ///////////////////////////////////////////////////////////////////////// 487 // Find an element in an associative container - throw an exception if 488 // not found 489 ///////////////////////////////////////////////////////////////////////// 490 491 template<typename ContainerTraits, typename Ovr> 492 BOOST_DEDUCED_TYPENAME assoc_algorithms<ContainerTraits, Ovr>::iterator find_or_throw(container & c,index_param ix)493 assoc_algorithms<ContainerTraits, Ovr>::find_or_throw( 494 container &c, index_param ix) 495 { 496 iterator iter = most_derived::find (c, ix); 497 498 if (iter == most_derived::end(c)) 499 { 500 PyErr_SetString( 501 PyExc_ValueError, "associative container: key not found"); 502 503 boost::python::throw_error_already_set (); 504 } 505 506 return iter; 507 } 508 509 ///////////////////////////////////////////////////////////////////////// 510 // Count occurances of an element in a container (associative version) 511 ///////////////////////////////////////////////////////////////////////// 512 513 template<typename ContainerTraits, typename Ovr> 514 BOOST_DEDUCED_TYPENAME assoc_algorithms<ContainerTraits, Ovr>::size_type count(container & c,key_param key)515 assoc_algorithms<ContainerTraits, Ovr>::count( 516 container &c, key_param key) 517 { 518 return c.count (key); 519 } 520 521 ///////////////////////////////////////////////////////////////////////// 522 // Some meta-information to select algorithms for const and 523 // non-const qualified containers. All algorithms_selector specializations 524 // include two publically accessible typedefs, called 525 // mutable_algorithms and const_algorithms. This saves having to 526 // have separate partial specializations of algorithms for 527 // const and non-const containers. Client code should probably 528 // specialize algorithms directly. 529 ///////////////////////////////////////////////////////////////////////// 530 531 namespace detail { 532 template<typename Container> class algorithms_selector 533 # if defined(BOOST_MPL_MSVC_ETI_BUG) 534 { 535 // Bogus types to prevent compile errors due to ETI 536 typedef algorithms_selector<Container> mutable_algorithms; 537 typedef algorithms_selector<Container> const_algorithms; 538 } 539 # endif 540 ; 541 } 542 543 ///////////////////////////////////////////////////////////////////////// 544 // Algorithms selection for mutable containers 545 ///////////////////////////////////////////////////////////////////////// 546 547 template<class Container> 548 struct algorithms 549 : public detail::algorithms_selector<Container>::mutable_algorithms 550 { 551 }; 552 553 # if !defined (BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) 554 ///////////////////////////////////////////////////////////////////////// 555 // Algorithms selection for const-qualified containers 556 ///////////////////////////////////////////////////////////////////////// 557 558 template<class Container> 559 struct algorithms<Container const> 560 : public detail::algorithms_selector<Container>::const_algorithms 561 { 562 }; 563 # endif 564 } } } 565 566 #endif // BOOST_PYTHON_INDEXING_ALGORITHMS_HPP 567 568 569 570