RootCore Packages: /cvmfs/atlas.cern.ch/repo/sw/ASG/AnalysisBase/2.4.31/AthContainers/AthContainers/tools/DVL

00001 // This file's extension implies that it's C, but it's really -*- C++ -*-.
00002 // $Id$
00011 #ifndef ATHCONTAINERS_TOOLS_DVL_ALGORITHMS_H
00012 #define ATHCONTAINERS_TOOLS_DVL_ALGORITHMS_H
00013 
00014 
00015 #include "AthContainers/tools/DVLIterator.h"
00016 #include <iterator>
00017 #include <algorithm>
00018 
00019 
00020 #include "AthContainers/tools/DVL_algorithms.icc"
00021 
00022 
00023 
00024 //===========================================================================
00025 // Algorithms requiring @c ForwardIterator.
00026 // Usable with @c DataVector and @c DataList.
00027 //
00028 
00029 namespace std {
00030 
00031 
00042 template <class DVL, class T>
00043 typename DataModel_detail::iterator<DVL>
00044 remove (typename DataModel_detail::iterator<DVL> beg,
00045         typename DataModel_detail::iterator<DVL> end,
00046         const T& value)
00047 {
00048   // Implemented with iter_swap, no extra index manipulation needed.
00049   return DataModel_detail::dvl_remove (beg, end, value);
00050 }
00051 
00052 
00063 template <class DVL, class Predicate>
00064 typename DataModel_detail::iterator<DVL>
00065 remove_if (typename DataModel_detail::iterator<DVL> beg,
00066            typename DataModel_detail::iterator<DVL> end,
00067            Predicate pred)
00068 {
00069   // Implemented with iter_swap, no extra index manipulation needed.
00070   return DataModel_detail::dvl_remove_if (beg, end, pred);
00071 }
00072 
00073 
00085 template <class DVL, class T>
00086 typename std::reverse_iterator<DataModel_detail::iterator<DVL> >
00087 remove (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00088         typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end,
00089         const T& value)
00090 {
00091   // Implemented with iter_swap, no extra index manipulation needed.
00092   return DataModel_detail::dvl_remove (beg, end, value);
00093 }
00094 
00095 
00107 template <class DVL, class Predicate>
00108 typename std::reverse_iterator<DataModel_detail::iterator<DVL> >
00109 remove_if (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00110            typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end,
00111            Predicate pred)
00112 {
00113   // Implemented with iter_swap, no extra index manipulation needed.
00114   return DataModel_detail::dvl_remove_if (beg, end, pred);
00115 }
00116 
00117 
00128 template <class DVL>
00129 typename DataModel_detail::iterator<DVL>
00130 unique (typename DataModel_detail::iterator<DVL> beg,
00131         typename DataModel_detail::iterator<DVL> end)
00132 {
00133   // Implemented with iter_swap, no extra index manipulation needed.
00134   return DataModel_detail::dvl_unique (beg, end);
00135 }
00136 
00137 
00148 template <class DVL, class BinaryPredicate>
00149 typename DataModel_detail::iterator<DVL>
00150 unique (typename DataModel_detail::iterator<DVL> beg,
00151         typename DataModel_detail::iterator<DVL> end,
00152         BinaryPredicate pred)
00153 {
00154   // Implemented with iter_swap, no extra index manipulation needed.
00155   return DataModel_detail::dvl_unique (beg, end, pred);
00156 }
00157 
00158 
00170 template <class DVL>
00171 typename std::reverse_iterator<DataModel_detail::iterator<DVL> >
00172 unique (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00173         typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end)
00174 {
00175   // Implemented with iter_swap, no extra index manipulation needed.
00176   return DataModel_detail::dvl_unique (beg, end);
00177 }
00178 
00179 
00192 template <class DVL, class BinaryPredicate>
00193 typename std::reverse_iterator<DataModel_detail::iterator<DVL> >
00194 unique (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00195         typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end,
00196         BinaryPredicate pred)
00197 {
00198   // Implemented with iter_swap, no extra index manipulation needed.
00199   return DataModel_detail::dvl_unique (beg, end, pred);
00200 }
00201 
00202 
00215 template <class DVL>
00216 void rotate (typename DataModel_detail::iterator<DVL> beg,
00217              typename DataModel_detail::iterator<DVL> mid,
00218              typename DataModel_detail::iterator<DVL> end)
00219 {
00220   std::rotate (beg.base(), mid.base(), end.base());
00221   DataModel_detail::resortAux (beg, end);
00222 }
00223 
00224 
00237 template <class DVL>
00238 void
00239 rotate (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00240         typename std::reverse_iterator<DataModel_detail::iterator<DVL> > mid,
00241         typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end)
00242 {
00243   typedef typename DVL::BaseContainer::reverse_iterator ri;
00244   std::rotate (ri(beg.base().base()),
00245                ri(mid.base().base()),
00246                ri(end.base().base()));
00247   DataModel_detail::resortAux (beg, end);
00248 }
00249 
00250 
00251 } // namespace std
00252 
00253 
00254 
00255 //===========================================================================
00256 // Algorithms requiring @c BidirectionalIterator.
00257 // Usable with @c DataVector and @c DataList.
00258 //
00259 
00260 namespace std {
00261 
00262 
00274 template <class DVL>
00275 void reverse (typename DataModel_detail::iterator<DVL> beg,
00276               typename DataModel_detail::iterator<DVL> end)
00277 {
00278   std::reverse (beg.base(), end.base());
00279   DataModel_detail::resortAux (beg, end);
00280 }
00281 
00282 
00294 template <class DVL>
00295 void
00296 reverse (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00297          typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end)
00298 {
00299   typedef typename DVL::BaseContainer::reverse_iterator ri;
00300   std::reverse (ri(beg.base().base()), ri(end.base().base()));
00301   DataModel_detail::resortAux (beg, end);
00302 }
00303 
00304 
00317 template <class DVL, class Predicate>
00318 typename DataModel_detail::iterator<DVL>
00319 partition (typename DataModel_detail::iterator<DVL> beg,
00320            typename DataModel_detail::iterator<DVL> end,
00321            Predicate pred)
00322 {
00323   typename DataModel_detail::iterator<DVL> ret
00324     (std::partition (beg.base(), end.base(),
00325                      DataModel_detail::Predwrapper<DVL, Predicate> (pred)),
00326      beg.container());
00327   DataModel_detail::resortAux (beg, end);
00328   return ret;
00329 }
00330 
00331 
00344 template <class DVL, class Predicate>
00345 typename std::reverse_iterator<DataModel_detail::iterator<DVL> >
00346 partition (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00347            typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end,
00348            Predicate pred)
00349 {
00350   typedef typename DataModel_detail::iterator<DVL> Iterator;
00351   typedef typename DVL::BaseContainer::reverse_iterator ri;
00352   typedef typename DataModel_detail::Predwrapper<DVL, Predicate> pwrap_t;
00353   std::reverse_iterator<Iterator> ret
00354     (Iterator (std::partition (ri(beg.base().base()),
00355                                ri(end.base().base()),
00356                                pwrap_t (pred)).base(),
00357                beg.base().container()));
00358   DataModel_detail::resortAux (beg, end);
00359   return ret;
00360 }
00361 
00362 
00375 template <class DVL, class Predicate>
00376 typename DataModel_detail::iterator<DVL>
00377 stable_partition (typename DataModel_detail::iterator<DVL> beg,
00378                   typename DataModel_detail::iterator<DVL> end,
00379                   Predicate pred)
00380 {
00381   DataModel_detail::iterator<DVL> ret
00382     (std::stable_partition (beg.base(), end.base(),
00383                             DataModel_detail::Predwrapper<DVL, Predicate>
00384                               (pred)),
00385      beg.container());
00386   DataModel_detail::resortAux (beg, end);
00387   return ret;
00388 }
00389 
00390 
00403 template <class DVL, class Predicate>
00404 typename std::reverse_iterator<DataModel_detail::iterator<DVL> >
00405 stable_partition
00406   (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00407    typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end,
00408    Predicate pred)
00409 {
00410   typedef typename DataModel_detail::iterator<DVL> Iterator;
00411   typedef typename DVL::BaseContainer::reverse_iterator ri;
00412   typedef typename DataModel_detail::Predwrapper<DVL, Predicate> pwrap_t;
00413   std::reverse_iterator<Iterator> ret
00414     (Iterator (std::stable_partition (ri(beg.base().base()),
00415                                       ri(end.base().base()),
00416                                       pwrap_t (pred)).base(),
00417                beg.base().container()));
00418   DataModel_detail::resortAux (beg, end);
00419   return ret;
00420 }
00421 
00422 
00435 template <class DVL>
00436 void
00437 inplace_merge (typename DataModel_detail::iterator<DVL> beg,
00438                typename DataModel_detail::iterator<DVL> mid,
00439                typename DataModel_detail::iterator<DVL> end)
00440 {
00441   std::inplace_merge (beg.base(), mid.base(), end.base());
00442   DataModel_detail::resortAux (beg, end);
00443 }
00444 
00445 
00459 template <class DVL, class Compare>
00460 void
00461 inplace_merge (typename DataModel_detail::iterator<DVL> beg,
00462                typename DataModel_detail::iterator<DVL> mid,
00463                typename DataModel_detail::iterator<DVL> end,
00464                Compare comp)
00465 {
00466   std::inplace_merge (beg.base(), mid.base(), end.base(),
00467                       typename DataModel_detail::Compwrapper<DVL, Compare>(comp));
00468   DataModel_detail::resortAux (beg, end);
00469 }
00470 
00471 
00484 template <class DVL>
00485 void
00486 inplace_merge (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00487                typename std::reverse_iterator<DataModel_detail::iterator<DVL> > mid,
00488                typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end)
00489 {
00490   typedef typename DVL::BaseContainer::reverse_iterator ri;
00491   std::inplace_merge (ri (beg.base().base()),
00492                       ri (mid.base().base()),
00493                       ri (end.base().base()));
00494   DataModel_detail::resortAux (beg, end);
00495 }
00496 
00497 
00511 template <class DVL, class Compare>
00512 void
00513 inplace_merge (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00514                typename std::reverse_iterator<DataModel_detail::iterator<DVL> > mid,
00515                typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end,
00516                Compare comp)
00517 {
00518   typedef typename DVL::BaseContainer::reverse_iterator ri;
00519   std::inplace_merge (ri (beg.base().base()),
00520                       ri (mid.base().base()),
00521                       ri (end.base().base()),
00522                       typename DataModel_detail::Compwrapper<DVL, Compare>(comp));
00523   DataModel_detail::resortAux (beg, end);
00524 }
00525 
00526 
00527 } // namespace std
00528 
00529 
00530 
00531 //===========================================================================
00532 // Algorithms requiring @c RandomAccessIterator.
00533 // Usable with @c DataVector.
00534 //
00535 
00536 namespace std {
00537 
00538 
00548 template <class DVL>
00549 void sort (typename DataModel_detail::iterator<DVL> beg,
00550            typename DataModel_detail::iterator<DVL> end)
00551 {
00552   // Wrap the default comparison object,
00553   // in case someone's overridden operator< for pointers.
00554   typedef std::less<typename DVL::BaseContainer::value_type> less;
00555   std::sort (beg.base(), end.base(),
00556              typename DataModel_detail::Compwrapper<DVL, less> (less()));
00557   DataModel_detail::resortAux (beg, end);
00558 }
00559 
00560 
00571 template <class DVL, class Compare>
00572 void sort (typename DataModel_detail::iterator<DVL> beg,
00573            typename DataModel_detail::iterator<DVL> end,
00574            Compare comp)
00575 {
00576   std::sort (beg.base(), end.base(),
00577              typename DataModel_detail::Compwrapper<DVL, Compare> (comp));
00578   DataModel_detail::resortAux (beg, end);
00579 }
00580 
00581 
00592 template <class DVL>
00593 void sort (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00594            typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end)
00595 {
00596   typedef typename DVL::BaseContainer::reverse_iterator ri;
00597   // Wrap the default comparison object,
00598   // in case someone's overridden operator< for pointers.
00599   typedef std::less<typename DVL::BaseContainer::value_type> less;
00600   std::sort (ri (beg.base().base()), ri (end.base().base()),
00601              typename DataModel_detail::Compwrapper<DVL, less> (less()));
00602   DataModel_detail::resortAux (beg, end);
00603 }
00604 
00605 
00617 template <class DVL, class Compare>
00618 void sort (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00619            typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end,
00620            const Compare& comp)
00621 {
00622   typedef typename DVL::BaseContainer::reverse_iterator ri;
00623   std::sort (ri (beg.base().base()), ri (end.base().base()),
00624              typename DataModel_detail::Compwrapper<DVL, Compare> (comp));
00625   DataModel_detail::resortAux (beg, end);
00626 }
00627 
00628 
00638 template <class DVL>
00639 void stable_sort (DataModel_detail::iterator<DVL> beg,
00640                   DataModel_detail::iterator<DVL> end)
00641 {
00642   // Wrap the default comparison object,
00643   // in case someone's overridden operator< for pointers.
00644   typedef std::less<typename DVL::BaseContainer::value_type> less;
00645   std::stable_sort (beg.base(), end.base(),
00646                     DataModel_detail::Compwrapper<DVL, less> (less()));
00647   DataModel_detail::resortAux (beg, end);
00648 }
00649 
00650 
00660 template <class DVL, class Compare>
00661 void stable_sort (DataModel_detail::iterator<DVL> beg,
00662                   DataModel_detail::iterator<DVL> end,
00663                   Compare comp)
00664 {
00665   std::stable_sort (beg.base(), end.base(),
00666                     DataModel_detail::Compwrapper<DVL, Compare> (comp));
00667   DataModel_detail::resortAux (beg, end);
00668 }
00669 
00670 
00681 template <class DVL>
00682 void stable_sort (std::reverse_iterator<DataModel_detail::iterator <DVL> > beg,
00683                   std::reverse_iterator<DataModel_detail::iterator <DVL> > end)
00684 {
00685   typedef typename DVL::BaseContainer::reverse_iterator ri;
00686   // Wrap the default comparison object,
00687   // in case someone's overridden operator< for pointers.
00688   typedef std::less<typename DVL::BaseContainer::value_type> less;
00689   std::stable_sort (ri (beg.base().base()), ri (end.base().base()),
00690                     typename DataModel_detail::Compwrapper<DVL, less> (less()));
00691   DataModel_detail::resortAux (beg, end);
00692 }
00693 
00694 
00705 template <class DVL, class Compare>
00706 void stable_sort (std::reverse_iterator<DataModel_detail::iterator <DVL> > beg,
00707                   std::reverse_iterator<DataModel_detail::iterator <DVL> > end,
00708                   Compare comp)
00709 {
00710   typedef typename DVL::BaseContainer::reverse_iterator ri;
00711   std::stable_sort (ri (beg.base().base()), ri (end.base().base()),
00712                     typename DataModel_detail::Compwrapper<DVL, Compare>(comp));
00713   DataModel_detail::resortAux (beg, end);
00714 }
00715 
00716 
00728 template <class DVL>
00729 void partial_sort (DataModel_detail::iterator<DVL> beg,
00730                    DataModel_detail::iterator<DVL> mid,
00731                    DataModel_detail::iterator<DVL> end)
00732 {
00733   // Wrap the default comparison object,
00734   // in case someone's overridden operator< for pointers.
00735   typedef std::less<typename DVL::BaseContainer::value_type> less;
00736   std::partial_sort (beg.base(), mid.base(), end.base(),
00737                      DataModel_detail::Compwrapper<DVL, less> (less()));
00738   DataModel_detail::resortAux (beg, end);
00739 }
00740 
00741 
00753 template <class DVL, class Compare>
00754 void partial_sort (DataModel_detail::iterator<DVL> beg,
00755                    DataModel_detail::iterator<DVL> mid,
00756                    DataModel_detail::iterator<DVL> end,
00757                    Compare comp)
00758 {
00759   std::partial_sort (beg.base(), mid.base(), end.base(),
00760                      DataModel_detail::Compwrapper<DVL, Compare> (comp));
00761   DataModel_detail::resortAux (beg, end);
00762 }
00763 
00764 
00776 template <class DVL>
00777 void partial_sort (std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00778                    std::reverse_iterator<DataModel_detail::iterator<DVL> > mid,
00779                    std::reverse_iterator<DataModel_detail::iterator<DVL> > end)
00780 {
00781   typedef typename DVL::BaseContainer::reverse_iterator ri;
00782   // Wrap the default comparison object,
00783   // in case someone's overridden operator< for pointers.
00784   typedef std::less<typename DVL::BaseContainer::value_type> less;
00785   std::partial_sort (ri (beg.base().base()),
00786                      ri (mid.base().base()),
00787                      ri (end.base().base()),
00788                      typename DataModel_detail::Compwrapper<DVL, less>
00789                        (less()));
00790   DataModel_detail::resortAux (beg, end);
00791 }
00792 
00793 
00805 template <class DVL, class Compare>
00806 void partial_sort (std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00807                    std::reverse_iterator<DataModel_detail::iterator<DVL> > mid,
00808                    std::reverse_iterator<DataModel_detail::iterator<DVL> > end,
00809                    Compare comp)
00810 {
00811   typedef typename DVL::BaseContainer::reverse_iterator ri;
00812   std::partial_sort (ri (beg.base().base()),
00813                      ri (mid.base().base()),
00814                      ri (end.base().base()),
00815                      typename DataModel_detail::Compwrapper<DVL, Compare>
00816                        (comp));
00817   DataModel_detail::resortAux (beg, end);
00818 }
00819 
00820 
00832 template <class DVL>
00833 void random_shuffle (typename DataModel_detail::iterator<DVL> beg,
00834                      typename DataModel_detail::iterator<DVL> end)
00835 {
00836   std::random_shuffle (beg.base(), end.base());
00837   DataModel_detail::resortAux (beg, end);
00838 }
00839 
00840 
00853 template <class DVL, class Random>
00854 void random_shuffle (typename DataModel_detail::iterator<DVL> beg,
00855                      typename DataModel_detail::iterator<DVL> end,
00856                      Random& rand)
00857 {
00858   std::random_shuffle (beg.base(), end.base(), rand);
00859   DataModel_detail::resortAux (beg, end);
00860 }
00861 
00862 
00874 template <class DVL>
00875 void
00876 random_shuffle
00877   (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00878    typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end)
00879 {
00880   typedef typename DVL::BaseContainer::reverse_iterator ri;
00881   std::random_shuffle (ri(beg.base().base()),
00882                        ri(end.base().base()));
00883   DataModel_detail::resortAux (beg, end);
00884 }
00885 
00886 
00899 template <class DVL, class Random>
00900 void
00901 random_shuffle
00902   (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00903    typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end,
00904    Random& rand)
00905 {
00906   typedef typename DVL::BaseContainer::reverse_iterator ri;
00907   std::random_shuffle (ri(beg.base().base()),
00908                        ri(end.base().base()),
00909                        rand);
00910   DataModel_detail::resortAux (beg, end);
00911 }
00912                           
00913 
00914 #if __cplusplus > 201100
00915 
00927 template <class DVL, class UniformRandom>
00928 void shuffle (typename DataModel_detail::iterator<DVL> beg,
00929               typename DataModel_detail::iterator<DVL> end,
00930               UniformRandom& g)
00931 {
00932   std::shuffle (beg.base(), end.base(), g);
00933   DataModel_detail::resortAux (beg, end);
00934 }
00935 
00936 
00949 template <class DVL, class UniformRandom>
00950 void
00951 shuffle
00952   (typename std::reverse_iterator<DataModel_detail::iterator<DVL> > beg,
00953    typename std::reverse_iterator<DataModel_detail::iterator<DVL> > end,
00954    UniformRandom& g)
00955 {
00956   typedef typename DVL::BaseContainer::reverse_iterator ri;
00957   std::shuffle (ri(beg.base().base()),
00958                 ri(end.base().base()),
00959                 g);
00960   DataModel_detail::resortAux (beg, end);
00961 }
00962 #endif
00963 
00964 
00965 } // namespace std
00966 
00967 
00968 
00969 #endif // not ATHCONTAINERS_TOOLS_DVL_ALGORITHMS_H
/cvmfs/atlas.cern.ch/repo/sw/ASG/AnalysisBase/2.4.31/AthContainers/AthContainers/tools/DVL_algorithms.h
