The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.
The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.
The ResGraphAdaptor is based on this composition.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
32 #include <lemon/error.h>
36 namespace _radix_sort_bits {
38 template <typename Value>
40 const Value& operator()(const Value& val) {
47 template <typename Value, typename Iterator, typename Functor>
48 Iterator radixSortPartition(Iterator first, Iterator last,
49 Functor functor, Value mask) {
50 while (first != last && !(functor(*first) & mask)) {
57 while (first != last && (functor(*last) & mask)) {
63 std::iter_swap(first, last);
65 if (!(first < last)) {
69 while (!(functor(*first) & mask)) {
73 while (functor(*last) & mask) {
76 if (!(first < last)) {
79 std::iter_swap(first, last);
84 template <typename Iterator, typename Functor>
85 Iterator radixSortSignPartition(Iterator first, Iterator last,
87 while (first != last && functor(*first) < 0) {
94 while (first != last && functor(*last) >= 0) {
100 std::iter_swap(first, last);
102 if (!(first < last)) {
106 while (functor(*first) < 0) {
110 while (functor(*last) >= 0) {
113 if (!(first < last)) {
116 std::iter_swap(first, last);
121 template <typename Value, typename Iterator, typename Functor>
122 void radixIntroSort(Iterator first, Iterator last,
123 Functor functor, Value mask) {
124 while (mask != 0 && last - first > 1) {
125 Iterator cut = radixSortPartition(first, last, functor, mask);
127 radixIntroSort(first, cut, functor, mask);
132 template <typename Value, typename Iterator, typename Functor>
133 void radixSignedSort(Iterator first, Iterator last, Functor functor) {
134 Iterator cut = radixSortSignPartition(first, last, functor);
140 mask = 0; max_digit = 0;
141 for (it = first; it != cut; ++it) {
142 if ((mask | functor(*it)) != ~0) {
148 radixIntroSort(first, cut, functor, 1 << max_digit);
150 mask = ~0; max_digit = 0;
151 for (it = cut; it != last; ++it) {
152 if (mask & functor(*it)) {
157 radixIntroSort(cut, last, functor, 1 << max_digit);
160 template <typename Value, typename Iterator, typename Functor>
161 void radixUnsignedSort(Iterator first, Iterator last, Functor functor) {
167 for (it = first; it != last; ++it) {
168 if (mask & functor(*it)) {
173 radixIntroSort(first, last, functor, 1 << max_digit);
176 namespace _radix_sort_bits {
178 template <typename Value,
179 bool sign = std::numeric_limits<Value>::is_signed >
180 struct RadixSortSelector {
181 template <typename Iterator, typename Functor>
182 static void sort(Iterator first, Iterator last, Functor functor) {
183 radixSignedSort<Value>(first, last, functor);
187 template <typename Value>
188 struct RadixSortSelector<Value, false> {
189 template <typename Iterator, typename Functor>
190 static void sort(Iterator first, Iterator last, Functor functor) {
191 radixUnsignedSort<Value>(first, last, functor);
199 /// \brief Sorts the stl compatible range into ascending order.
201 /// The \c radixSort sorts the stl compatible range into ascending order.
202 /// The radix sort algorithm can sort the items which mapped to an
203 /// integer by the adaptable unary function \c functor and the order
204 /// will be ascending by these mapped values. As function specialization
205 /// there is possible to use a normal function as the functor object
206 /// or if the functor is not given it will use an identity function instead.
208 /// This implemented radix sort is a special quick sort which pivot value
209 /// is choosen to partite the items on the next bit. This way, let be
210 /// \c c the maximal capacity and \c n the number of the items in
211 /// the container, the time complexity of the algorithm \c O(log(c)*n)
212 /// and the additional space complexity is \c O(log(c)).
214 /// \param first The begin of the given range.
215 /// \param last The end of the given range.
216 /// \param functor An adaptible unary function or a normal function which
217 /// maps the items to any integer type which can be wheter signed or
219 template <typename Iterator, typename Functor>
220 void radixSort(Iterator first, Iterator last, Functor functor) {
221 using namespace _radix_sort_bits;
222 typedef typename Functor::result_type Value;
223 RadixSortSelector<Value>::sort(first, last, functor);
226 template <typename Iterator, typename Value, typename Key>
227 void radixSort(Iterator first, Iterator last, Value (*functor)(Key)) {
228 using namespace _radix_sort_bits;
229 RadixSortSelector<Value>::sort(first, last, functor);
232 template <typename Iterator, typename Value, typename Key>
233 void radixSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
234 using namespace _radix_sort_bits;
235 RadixSortSelector<Value>::sort(first, last, functor);
238 template <typename Iterator, typename Value, typename Key>
239 void radixSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
240 using namespace _radix_sort_bits;
241 RadixSortSelector<Value>::sort(first, last, functor);
244 template <typename Iterator, typename Value, typename Key>
245 void radixSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
246 using namespace _radix_sort_bits;
247 RadixSortSelector<Value>::sort(first, last, functor);
250 template <typename Iterator>
251 void radixSort(Iterator first, Iterator last) {
252 using namespace _radix_sort_bits;
253 typedef typename std::iterator_traits<Iterator>::value_type Value;
254 RadixSortSelector<Value>::sort(first, last, Identity<Value>());
257 template <typename Value>
258 unsigned char valueByte(Value value, int byte) {
259 return value >> (std::numeric_limits<unsigned char>::digits * byte);
262 template <typename Functor, typename Key>
263 void counterIntroSort(Key *first, Key *last, Key *target,
264 int byte, Functor functor) {
266 (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
267 std::vector<int> counter(size);
268 for (int i = 0; i < size; ++i) {
272 while (first != last) {
273 ++counter[valueByte(functor(*first), byte)];
277 for (int i = 0; i < size; ++i) {
283 target[counter[valueByte(functor(*it), byte)]++] = *it;
288 template <typename Functor, typename Key>
289 void signedCounterIntroSort(Key *first, Key *last, Key *target,
290 int byte, Functor functor) {
292 (unsigned int)std::numeric_limits<unsigned char>::max() + 1;
293 std::vector<int> counter(size);
294 for (int i = 0; i < size; ++i) {
298 while (first != last) {
299 counter[valueByte(functor(*first), byte)]++;
303 for (int i = size / 2; i < size; ++i) {
308 for (int i = 0; i < size / 2; ++i) {
314 target[counter[valueByte(functor(*it), byte)]++] = *it;
320 template <typename Value, typename Iterator, typename Functor>
321 void counterSignedSort(Iterator first, Iterator last, Functor functor) {
322 if (first == last) return;
323 typedef typename std::iterator_traits<Iterator>::value_type Key;
324 typedef std::allocator<Key> Allocator;
327 int length = std::distance(first, last);
329 buffer = allocator.allocate(2 * length);
332 std::copy(first, last, buffer);
333 for (int i = 0; i < (int)sizeof(Value) - 1; ++i) {
335 counterIntroSort(buffer, buffer + length, buffer + length,
338 counterIntroSort(buffer + length, buffer + 2 * length, buffer,
344 signedCounterIntroSort(buffer, buffer + length, buffer + length,
345 sizeof(Value) - 1, functor);
346 std::copy(buffer + length, buffer + 2 * length, first);
348 signedCounterIntroSort(buffer + length, buffer + 2 * length, buffer,
349 sizeof(Value) - 1, functor);
350 std::copy(buffer, buffer + length, first);
353 allocator.deallocate(buffer, 2 * length);
356 allocator.deallocate(buffer, 2 * length);
359 template <typename Value, typename Iterator, typename Functor>
360 void counterUnsignedSort(Iterator first, Iterator last, Functor functor) {
361 if (first == last) return;
362 typedef typename std::iterator_traits<Iterator>::value_type Key;
363 typedef std::allocator<Key> Allocator;
366 int length = std::distance(first, last);
368 buffer = allocator.allocate(2 * length);
371 std::copy(first, last, buffer);
372 for (int i = 0; i < (int)sizeof(Value); ++i) {
374 counterIntroSort(buffer, buffer + length, buffer + length, i, functor);
376 counterIntroSort(buffer + length, buffer + 2 * length, buffer, i, functor);
381 std::copy(buffer, buffer + length, first);
383 std::copy(buffer + length, buffer + 2 * length, first);
386 allocator.deallocate(buffer, 2 * length);
389 allocator.deallocate(buffer, 2 * length);
392 namespace _radix_sort_bits {
394 template <typename Value,
395 bool sign = std::numeric_limits<Value>::is_signed >
396 struct CounterSortSelector {
397 template <typename Iterator, typename Functor>
398 static void sort(Iterator first, Iterator last, Functor functor) {
399 counterSignedSort<Value>(first, last, functor);
403 template <typename Value>
404 struct CounterSortSelector<Value, false> {
405 template <typename Iterator, typename Functor>
406 static void sort(Iterator first, Iterator last, Functor functor) {
407 counterUnsignedSort<Value>(first, last, functor);
415 /// \brief Sorts stable the stl compatible range into ascending order.
417 /// The \c counterSort sorts the stl compatible range into ascending order.
418 /// The counter sort algorithm can sort the items which mapped to an
419 /// integer by the adaptable unary function \c functor and the order
420 /// will be ascending by these mapped values. As function specialization
421 /// there is possible to use a normal function as the functor object
422 /// or if the functor is not given it will use an identity function instead.
424 /// This implemented counter sort use a radix forward sort on the bytes of
425 /// the integer. The algorithm can sort the items on a given byte.
426 /// First time it counts how many times occurs a byte value in the container.
427 /// By the occurence number it is possible to copy the container
428 /// in the right order in \c O(n) time. The algorithm sorts the container
429 /// by each bytes in forward direction which sorts the container by the
430 /// whole value. This way, let be \c c the maximal capacity of the integer
431 /// type and \c n the number of the items in
432 /// the container, the time complexity of the algorithm \c O(log(c)*n)
433 /// and the additional space complexity is \c O(n).
435 /// This sorting algorithm is stable so the order of two equal element
436 /// stay in the same order.
438 /// \param first The begin of the given range.
439 /// \param last The end of the given range.
440 /// \param functor An adaptible unary function or a normal function which
441 /// maps the items to any integer type which can be wheter signed or
443 template <typename Iterator, typename Functor>
444 void counterSort(Iterator first, Iterator last, Functor functor) {
445 using namespace _radix_sort_bits;
446 typedef typename Functor::result_type Value;
447 CounterSortSelector<Value>::sort(first, last, functor);
450 template <typename Iterator, typename Value, typename Key>
451 void counterSort(Iterator first, Iterator last, Value (*functor)(Key)) {
452 using namespace _radix_sort_bits;
453 CounterSortSelector<Value>::sort(first, last, functor);
456 template <typename Iterator, typename Value, typename Key>
457 void counterSort(Iterator first, Iterator last, Value& (*functor)(Key)) {
458 using namespace _radix_sort_bits;
459 CounterSortSelector<Value>::sort(first, last, functor);
462 template <typename Iterator, typename Value, typename Key>
463 void counterSort(Iterator first, Iterator last, Value (*functor)(Key&)) {
464 using namespace _radix_sort_bits;
465 CounterSortSelector<Value>::sort(first, last, functor);
468 template <typename Iterator, typename Value, typename Key>
469 void counterSort(Iterator first, Iterator last, Value& (*functor)(Key&)) {
470 using namespace _radix_sort_bits;
471 CounterSortSelector<Value>::sort(first, last, functor);
474 template <typename Iterator>
475 void counterSort(Iterator first, Iterator last) {
476 using namespace _radix_sort_bits;
477 typedef typename std::iterator_traits<Iterator>::value_type Value;
478 CounterSortSelector<Value>::sort(first, last, Identity<Value>());