lemon/radix_sort.h
changeset 522 22f932bbb305
parent 443 de16f1f2d228
child 559 c5fd2d996909
equal deleted inserted replaced
2:4e4f960b5780 3:1a43d1e5f7f0
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2009
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
   346         if (dir) {
   346         if (dir) {
   347           signedStableRadixIntroSort(buffer, buffer + length, buffer + length,
   347           signedStableRadixIntroSort(buffer, buffer + length, buffer + length,
   348                                      sizeof(Value) - 1, functor);
   348                                      sizeof(Value) - 1, functor);
   349           std::copy(buffer + length, buffer + 2 * length, first);
   349           std::copy(buffer + length, buffer + 2 * length, first);
   350         }        else {
   350         }        else {
   351           signedStableRadixIntroSort(buffer + length, buffer + 2 * length, 
   351           signedStableRadixIntroSort(buffer + length, buffer + 2 * length,
   352                                      buffer, sizeof(Value) - 1, functor);
   352                                      buffer, sizeof(Value) - 1, functor);
   353           std::copy(buffer, buffer + length, first);
   353           std::copy(buffer, buffer + length, first);
   354         }
   354         }
   355       } catch (...) {
   355       } catch (...) {
   356         allocator.deallocate(buffer, 2 * length);
   356         allocator.deallocate(buffer, 2 * length);
   358       }
   358       }
   359       allocator.deallocate(buffer, 2 * length);
   359       allocator.deallocate(buffer, 2 * length);
   360     }
   360     }
   361 
   361 
   362     template <typename Value, typename Iterator, typename Functor>
   362     template <typename Value, typename Iterator, typename Functor>
   363     void stableRadixUnsignedSort(Iterator first, Iterator last, 
   363     void stableRadixUnsignedSort(Iterator first, Iterator last,
   364                                  Functor functor) {
   364                                  Functor functor) {
   365       if (first == last) return;
   365       if (first == last) return;
   366       typedef typename std::iterator_traits<Iterator>::value_type Key;
   366       typedef typename std::iterator_traits<Iterator>::value_type Key;
   367       typedef std::allocator<Key> Allocator;
   367       typedef std::allocator<Key> Allocator;
   368       Allocator allocator;
   368       Allocator allocator;