COMBINATORIAL_BLAS 1.6
 
Loading...
Searching...
No Matches
funnel.timpl.h
Go to the documentation of this file.
1// The Funnelsort Project - Cache oblivious sorting algorithm implementation
2// Copyright (C) 2005 Kristoffer Vinther
3//
4// This program is free software; you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation; either version 2 of the License, or
7// (at your option) any later version.
8//
9// This program is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU General Public License for more details.
13//
14// You should have received a copy of the GNU General Public License
15// along with this program; if not, write to the Free Software
16// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
17
18
19namespace iosort
20{
21
22template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
23void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::Node::Edge::fill_dflt(TPtr b, TPtr e, allocator alloc)
24{
25 TPtr p = b;
26 try
27 {
28 value_type dflt;
29 for( ; p!=e; ++p )
30 alloc.construct(p,dflt);
31 }
32 catch( ... )
33 {
34 if( p != b )
35 {
36 for( --p; p!=b; --p )
37 alloc.destroy(p);
38 alloc.destroy(p);
39 }
40 alloc.deallocate(b,e-b);
41 throw;
42 }
43}
44
45template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
46void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::Node::construct(order_t k, height_t height, size_t *buf_size, allocator alloc, nallocator nalloc)
47{
48 order_t lk = pow_of_order<order>(height-1);
49 int i = 0;
50 try
51 {
52 for( ; i!=order && lk < k; ++i, k-=lk )
53 {
54 edges[i].construct(lk, height-1, buf_size, alloc, nalloc);
55 }
56 if( i != order )
57 {
58 assert( k <= lk );
59 edges[i].construct(k, height-1, buf_size, alloc, nalloc);
60 ++i;
61 }
62 for( ; i!=order; ++i )
63 {
64 edges[i].child = NPtr();
65 edges[i].begin = edges[i].end = TPtr();
66 }
67 }
68 catch( ... )
69 {
70 if( i )
71 {
72 for( --i; i; --i )
73 edges[i].destroy(alloc, nalloc);
74 edges[i].destroy(alloc, nalloc);
75 }
76 throw;
77 }
78}
79
80template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
81void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::Node::Edge::construct(order_t k, height_t height, size_t *buf_size, allocator alloc, nallocator nalloc)
82{
83 begin = alloc.allocate(*buf_size);
84 head = tail = end = begin+*buf_size;
85 try
86 {
87 fill_dflt(begin,end,alloc);
88 if( height > 1 )
89 try
90 {
91 child = nalloc.allocate(1);
92 try
93 {
94 nalloc.construct(child, Node());
95 child->construct(k,height,buf_size+1,alloc,nalloc);
96 }
97 catch( ... )
98 {
99 child->destroy(alloc, nalloc);
100 nalloc.destroy(child);
101 throw;
102 }
103 }
104 catch( ... )
105 {
106 nalloc.deallocate(child, 1);
107 throw;
108 }
109 else
110 child = NPtr();
111 }
112 catch( ... )
113 {
114 alloc.deallocate(begin,*buf_size);
115 throw;
116 }
117}
118
119template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
120void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::Node::destroy(allocator alloc, nallocator nalloc)
121{
122 for( int i=0; i!=order; ++i )
123 edges[i].destroy(alloc, nalloc);
124}
125
126
127template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
128void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::Node::Edge::destroy(allocator alloc, nallocator nalloc)
129{
130 if( child != NPtr() )
131 {
132 child->destroy(alloc,nalloc);
133 nalloc.destroy(child);
134 nalloc.deallocate(child,1);
135 }
136 if( begin != TPtr() )
137 {
138 for( TPtr p=begin; p!=end; ++p )
139 alloc.destroy(p);
140 alloc.deallocate(begin,end-begin);
141 }
142}
143
144
145
146template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
147void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::compute_buffer_sizes(size_type *b, size_type *e)
148{
149 height_t sp = Splitter::split(static_cast<height_t>(e-b));
150 if( e-b > 2 )
151 {
152 compute_buffer_sizes(b, b+sp);
153 compute_buffer_sizes(b+sp, e);
154 }
155 b[sp] = Splitter::out_buffer_size(pow_of_order<order>(static_cast<height_t>(e-b-sp)));
156}
157
158template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
159void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::construct(order_t k)
160{
161 if(!( order < k ))
162 throw std::invalid_argument("Merge tree too small");
163 height_t height = static_cast<height_t>(logc<order>(k));
164 if( height > MAX_MERGE_TREE_HEIGHT )
165 throw std::invalid_argument("Merge tree too high");
166 bfs_index<order> bfs;
167 for( height_t l=1; l!=logc<order>(k); ++l )
168 bfs.child(0);
169 leaf_index = bfs;
170 size_type buffer_sizes[MAX_MERGE_TREE_HEIGHT];
171 compute_buffer_sizes(buffer_sizes,buffer_sizes+height);
172
173 root = nalloc.allocate(1);
174 try
175 {
176 nalloc.construct(root, Node());
177 root->construct(k,height,buffer_sizes+1,alloc,nalloc);
178 try
179 {
180 order_t K = k+order-1;
181 K = K - K%order;
182 last_stream = input_streams = salloc.allocate(K);
183 SPtr p = input_streams;
184 try
185 {
186 stream_t dflt = stream_t(RanIt(),RanIt());
187 for( ; p!=last_stream+K; ++p )
188 salloc.construct(p,dflt);
189 }
190 catch( ... )
191 {
192 if( p != input_streams )
193 {
194 for( --p; p!=input_streams; --p )
195 salloc.destroy(p);
196 salloc.destroy(p);
197 }
198 salloc.deallocate(input_streams,K);
199 throw;
200 }
201 }
202 catch( ... )
203 {
204 root->destroy(alloc, nalloc);
205 nalloc.destroy(root);
206 throw;
207 }
208 }
209 catch( ... )
210 {
211 nalloc.deallocate(root,1);
212 throw;
213 }
214}
215
216template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
217merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::~merge_tree()
218{
219 order_t K = k+order-1;
220 K = K - K%order;
221 for( SPtr s=input_streams; s!=input_streams+K; ++s )
222 salloc.destroy(s);
223 salloc.deallocate(input_streams, K);
224 root->destroy(alloc, nalloc);
225 nalloc.destroy(root);
226 nalloc.deallocate(root,1);
227}
228
229template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
230void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::reset()
231{
232 if( !cold )
233 {
234 stream_t dflt;
235 for( SPtr s=input_streams; s!=last_stream; ++s )
236 {
237 salloc.destroy(s);
238 salloc.construct(s,dflt);
239 }
240 cold = true;
241 }
242 last_stream = input_streams;
243}
244
245template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
246template<class FwIt>
247FwIt merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::operator()(FwIt begin, FwIt end)
248{
249 if( cold )
250 {
251 bfs_index<order> index;
252 for( basic_order_t i=0; i!=order; ++i )
253 {
254 index.child(i);
255 go_down_cold(root->edges[i],index);
256 }
257 }
258 cold = false;
259 return fill_root(begin, end);
260}
261
262template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
263template<class OutIt>
264OutIt merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::operator()(OutIt begin)
265{
266 if( cold )
267 {
268 bfs_index<order> index;
269 for( basic_order_t i=0; i!=order; ++i )
270 {
271 index.child(i);
272 go_down_cold(root->edges[i],index);
273 }
274 }
275 cold = false;
276 return fill_root(begin);
277}
278
279template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
280template<class FwIt>
281FwIt merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::empty_buffers(NPtr n, FwIt begin, FwIt end)
282{
283 for( int i=0; i!=order; ++i )
284 {
285 for( ; n->edges[i].head!=n->edges[i].tail && begin!=end; ++n->edges[i].head, ++begin )
286 *begin = *n->edges[i].head;
287 if( n->edges[i].child )
288 begin = empty_buffers(n->edges[i].child, begin, end);
289 }
290 return begin;
291}
292
293template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
294template<class OutIt>
295OutIt merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::empty_buffers(NPtr n, OutIt begin)
296{
297 for( int i=0; i!=order; ++i )
298 {
299 begin = std::copy(n->edges[i].head, n->edges[i].tail, begin);
300 if( n->edges[i].child )
301 begin = empty_buffers(n->edges[i].child, begin);
302 }
303 return begin;
304}
305
306template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
307void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::go_down(typename Node::Edge& e, bfs_index<order> index)
308{
309 assert( e.tail == e.head );
310 e.head = e.begin;
311 if( e.child == NPtr() )
312 fill_leaf(e,index);
313 else
314 fill(e.child,e,index);
315 e.tail = e.head, e.head = e.begin;
316 index.parent();
317}
318
319template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
320void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::go_down_cold(typename Node::Edge& e, bfs_index<order>& index)
321{
322 e.tail = e.end, e.head = e.begin;
323 if( e.child )
324 warmup(e.child, e, index);
325 else if( leaf_index <= index && input_streams+order*(index-leaf_index) < last_stream )
326 fill_leaf(e,index);
327 e.tail = e.head, e.head = e.begin;
328 index.parent();
329}
330
331template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
332void merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::warmup(NPtr n, typename Node::Edge& output, bfs_index<order> index)
333{
334 for( basic_order_t i=0; i!=order; ++i )
335 {
336 index.child(i);
337 go_down_cold(n->edges[i],index);
338 }
339 fill(n,output,index);
340}
341
342template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
343template<class FwIt>
344FwIt merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::copy_root(typename Node::Edge& de, bfs_index<order> index, FwIt begin, FwIt end, std::forward_iterator_tag)
345{
346 for( ;; )
347 {
348 for( ; de.tail!=de.head && begin!=end; ++begin, ++de.head )
349 *begin = *de.head;
350 if( de.tail == de.head )
351 {
352 go_down(de,index);
353 if( de.head == de.tail )
354 return begin;
355 }
356 else
357 return begin;
358 }
359}
360
361template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
362template<class RIt>
363RIt merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::copy_root(typename Node::Edge& de, bfs_index<order> index, RIt begin, RIt end, std::random_access_iterator_tag)
364{
365 for( ;; )
366 {
367 for( ; de.tail!=de.head && begin!=end; ++begin, ++de.head )
368 *begin = *de.head;
369 if( de.tail == de.head )
370 {
371 go_down(de,index);
372 if( de.head == de.tail )
373 return begin;
374 }
375 else
376 return begin;
377 }
378}
379
380template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
381template<class OutIt>
382OutIt merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::copy_root(typename Node::Edge& de, bfs_index<order> index, OutIt begin)
383{
384 do
385 {
386 for( ; de.tail!=de.head; ++begin, ++de.head )
387 *begin = *de.head;
388 go_down(de,index);
389 }
390 while( de.head != de.tail );
391 return begin;
392}
393
394template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
395typename merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::TPtr merge_tree<RanIt,order,Splitter,Pred,Refiller,Alloc>::copy(typename Node::Edge& de, bfs_index<order> index, TPtr b, TPtr e)
396{
397 for( ;; )
398 {
399 if( e-b < de.tail-de.head )
400 {
401 for( ; b!=e; ++b, ++de.head )
402 *b = *de.head;
403 return b;
404 }
405 else
406 {
407 for( ; de.tail!=de.head; ++b, ++de.head )
408 *b = *de.head;
409 go_down(de,index);
410 if( de.head == de.tail )
411 return b;
412 }
413 }
414}
415
416
417/*****
418 * Order 2 basic merger template specialization
419 */
420
421template<class RanIt, class Splitter, class Pred, class Refiller, class Alloc>
422class special_<RanIt,2,Splitter,Pred,Refiller,Alloc>
423{
424 friend class merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>;
425
426 template<class FwIt>
427 static FwIt fill_root(merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>* that, FwIt begin, FwIt end)
428 {
429 typedef typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
430 typedef typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::Node Node;
431 bfs_index<2> index;
432 for( ;; )
433 if( that->root->edges[0].head != that->root->edges[0].tail )
434 if( that->root->edges[1].head != that->root->edges[1].tail )
435 for( TPtr l=that->root->edges[0].head, r=that->root->edges[1].head;; )
436 {
437 if( begin == end )
438 {
439 that->root->edges[0].head = l;
440 that->root->edges[1].head = r;
441 return begin;
442 }
443 if( that->comp(*l,*r) )
444 {
445 *begin = *l, ++l, ++begin;
446 if( l == that->root->edges[0].tail )
447 {
448 typename Node::Edge& de = that->root->edges[0];
449 that->root->edges[0].head = l; that->root->edges[1].head = r;
450 index.child(0);
451 that->go_down(de,index);
452 index.parent();
453 if( de.head == de.tail )
454 break;
455 l = that->root->edges[0].head;
456 }
457 }
458 else
459 {
460 *begin = *r, ++r, ++begin;
461 if( r == that->root->edges[1].tail )
462 {
463 typename Node::Edge& de = that->root->edges[1];
464 that->root->edges[0].head = l; that->root->edges[1].head = r;
465 index.child(1);
466 that->go_down(de,index);
467 index.parent();
468 if( de.head == de.tail )
469 break;
470 r = that->root->edges[1].head;
471 }
472 }
473 }
474 else
475 {
476 index.child(0);
477 return that->copy_root(that->root->edges[0], index, begin, end, typename std::iterator_traits<FwIt>::iterator_category());
478 }
479 else if( that->root->edges[1].head != that->root->edges[1].tail )
480 {
481 index.child(1);
482 return that->copy_root(that->root->edges[1], index, begin, end, typename std::iterator_traits<FwIt>::iterator_category());
483 }
484 else
485 return begin;
486 }
487
488 template<class OutIt>
489 static OutIt fill_root(merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>* that, OutIt begin)
490 {
491 typedef typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
492 typedef typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::Node Node;
493 bfs_index<2> index;
494 for( ;; )
495 if( that->root->edges[0].head != that->root->edges[0].tail )
496 if( that->root->edges[1].head != that->root->edges[1].tail )
497 for( TPtr l=that->root->edges[0].head, r=that->root->edges[1].head;; )
498 if( that->comp(*l,*r) )
499 {
500 *begin = *l, ++l, ++begin;
501 if( l == that->root->edges[0].tail )
502 {
503 typename Node::Edge& de = that->root->edges[0];
504 that->root->edges[0].head = l; that->root->edges[1].head = r;
505 index.child(0);
506 that->go_down(de,index);
507 index.parent();
508 if( de.head == de.tail )
509 break;
510 l = that->root->edges[0].head;
511 }
512 }
513 else
514 {
515 *begin = *r, ++r, ++begin;
516 if( r == that->root->edges[1].tail )
517 {
518 typename Node::Edge& de = that->root->edges[1];
519 that->root->edges[0].head = l; that->root->edges[1].head = r;
520 index.child(1);
521 that->go_down(de,index);
522 index.parent();
523 if( de.head == de.tail )
524 break;
525 r = that->root->edges[1].head;
526 }
527 }
528 else
529 {
530 index.child(0);
531 return that->copy_root(that->root->edges[0], index, begin);
532 }
533 else if( that->root->edges[1].head != that->root->edges[1].tail )
534 {
535 index.child(1);
536 return that->copy_root(that->root->edges[1], index, begin);
537 }
538 else
539 return begin;
540 }
541
542 static void fill(merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>* that, typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::NPtr n, typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::Node::Edge& output, bfs_index<2> index)
543 {
544 typedef typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
545 typedef typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::Node Node;
546 for( TPtr p = output.head;; )
547 if( n->edges[0].head != n->edges[0].tail )
548 if( n->edges[1].head != n->edges[1].tail )
549 for( TPtr l=n->edges[0].head, r=n->edges[1].head;; )
550 {
551 if( p == output.tail )
552 {
553 output.head = p;
554 n->edges[0].head = l;
555 n->edges[1].head = r;
556 return;
557 }
558#ifdef USE_COND_MOVS_
559#ifdef _MSC_VER
560 __asm
561 {
562 mov eax, p
563 mov ebx, l
564 mov ecx, r
565 mov edi, dword ptr [ebx] ; edges[0] key in edi
566 mov edx, dword ptr [ecx] ; edges[1] key in edx
567 cmp edi, edx ; compare keys
568 cmovl edx, edi ; small key in edx
569 cmovl edi, dword ptr [ebx+4] ; small pointer in edi
570 cmovge edi, dword ptr [ecx+4] ; small pointer in edi
571 mov dword ptr [eax], edx ; output small key
572 mov dword ptr [eax+4], edi ; output small pointer
573 setl dl
574 mov edi, ebx ; cond-inc edges[0]
575 add edi, 8
576 test dl, dl
577 cmovnz ebx, edi
578 mov edi, ecx ; cond-inc edges[1]
579 add edi, 8
580 test dl, dl
581 cmovz ecx, edi
582 add eax, 8 ; inc out
583 mov r, ecx
584 mov l, ebx
585 mov p, eax
586 }
587#else // _MSC_VER
588#ifdef __GNUC__
589 asm("movl\t(%1), %%edi\n\t" // edges[0] key in edi
590 "movl\t(%2), %%edx\n\t" // edges[1] key in edx
591 "cmpl\t%%edx, %%edi\n\t" // compare keys
592 "cmovll\t%%edi, %%edx\n\t" // small key in edx
593 "cmovll\t4(%1), %%edi\n\t" // small pointer in edi
594 "cmovgel\t4(%2), %%edi\n\t" // small pointer in edi
595 "movl\t%%edx, (%0)\n\t" // output small key
596 "movl\t%%edi, 4(%0)\n\t" // output small pointer
597 "setb\t%%dl\n\t"
598 "movl\t%1, %%edi\n\t" // cond-inc edges[0]
599 "addl\t$8, %%edi\n\t"
600 "testb\t%%dl, %%dl\n\t"
601 "cmovnzl\t%%edi, %1\n\t"
602 "movl\t%2, %%edi\n\t" // cond-inc edges[1]
603 "addl\t$8, %%edi\n\t"
604 "testb\t%%dl, %%dl\n\t"
605 "cmovzl\t%%edi, %2\n\t"
606 "addl\t$8, %0" // inc out
607 : "=r"(p), "=r"(l), "=r"(r) : "0"(p), "1"(l), "2"(r) : "edx", "edi");
608#else // __GNUC__
609 register TPtr nh = l+1;
610 bool b = that->comp(*l,*r);
611 *p = b? *l : *r;
612 l = b? nh : l;
613 nh = r+1;
614 r = b? r : nh;
615 ++p;
616#endif // __GNUC__
617#endif // _MSC_VER
618 if( l == n->edges[0].tail )
619 {
620 typename Node::Edge& de = n->edges[0];
621 n->edges[0].head = l; n->edges[1].head = r;
622 index.child(0);
623 that->go_down(de,index);
624 if( de.head == de.tail )
625 break;
626 l = n->edges[0].head;
627 }
628 if( r == n->edges[1].tail )
629 {
630 typename Node::Edge& de = n->edges[1];
631 n->edges[0].head = l; n->edges[1].head = r;
632 index.child(1);
633 that->go_down(de,index);
634 if( de.head == de.tail )
635 break;
636 r = n->edges[1].head;
637 }
638#else // USE_COND_MOVS_
639 if( that->comp(*l,*r) )
640 {
641 *p = *l, ++l, ++p;
642 if( l == n->edges[0].tail )
643 {
644 typename Node::Edge& de = n->edges[0];
645 n->edges[0].head = l; n->edges[1].head = r;
646 index.child(0);
647 that->go_down(de,index);
648 index.parent();
649 if( de.head == de.tail )
650 break;
651 l = n->edges[0].head;
652 }
653 }
654 else
655 {
656 *p = *r, ++r, ++p;
657 if( r == n->edges[1].tail )
658 {
659 typename Node::Edge& de = n->edges[1];
660 n->edges[0].head = l; n->edges[1].head = r;
661 index.child(1);
662 that->go_down(de,index);
663 index.parent();
664 if( de.head == de.tail )
665 break;
666 r = n->edges[1].head;
667 }
668 }
669#endif // USE_COND_MOVS_
670 }
671 else
672 {
673 index.child(0);
674 output.head = that->copy(n->edges[0], index, p, output.tail);
675 return;
676 }
677 else if( n->edges[1].head != n->edges[1].tail )
678 {
679 index.child(1);
680 output.head = that->copy(n->edges[1], index, p, output.tail);
681 return;
682 }
683 else
684 return;
685 }
686
687 static void fill_leaf(merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>* that, typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::Node::Edge& output, bfs_index<2> index)
688 {
689 typedef typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
690 typedef typename merge_tree<RanIt,2,Splitter,Pred,Refiller,Alloc>::stream_iterator stream_iterator;
691 stream_iterator left = that->input_streams+2*(index-that->leaf_index);
692 stream_iterator right = left;
693 ++right;
694 //assert( left < that->last_stream );
695 //assert( that->input_streams <= left );
696 RanIt l=(*left).begin(), r=(*right).begin();
697 for( TPtr p = output.head;; )
698 if( l != (*left).end() )
699 if( r != (*right).end() )
700 for( ;; )
701 {
702 if( p == output.tail )
703 {
704 output.head = p;
705 (*left).begin() = l;
706 (*right).begin() = r;
707 // TODO: Refill
708 return;
709 }
710 if( that->comp(*l,*r) )
711 {
712 *p = *l, ++l, ++p;
713 if( l == (*left).end() )
714 break;
715 }
716 else
717 {
718 *p = *r, ++r, ++p;
719 if( r == (*right).end() )
720 break;
721 }
722 }
723 else
724 {
725 assert( r == (*right).end() );
726 if( output.tail-p < (*left).end()-l )
727 for( ; p!=output.tail; ++p, ++l )
728 *p = *l;
729 else
730 for( ; (*left).end()!=l; ++p, ++l )
731 *p = *l;
732 output.head = p;
733 (*left).begin() = l;
734 (*right).begin() = r;
735 // TODO: Refill
736 return;
737 }
738 else if( r != (*right).end() )
739 {
740 assert( l == (*left).end() );
741 if( output.tail-p < (*right).end()-r )
742 for( ; p!=output.tail; ++p, ++r )
743 *p = *r;
744 else
745 for( ; (*right).end()!=r; ++p, ++r )
746 *p = *r;
747 output.head = p;
748 (*left).begin() = l;
749 (*right).begin() = r;
750 // TODO: Refill
751 return;
752 }
753 else
754 return;
755 }
756};
757
758/*****
759 * Order 4 basic merger template specialization
760 */
761
762#define MOVE_SMALL(i,n) *begin = *head[i], ++head[i], ++begin; \
763 if( head[i] == tail[i] ) \
764 { \
765 stream[i]->head = head[i]; \
766 index.child(static_cast<basic_order_t>(stream[i]-n->edges)); \
767 that->go_down(*stream[i],index); \
768 index.parent(); \
769 head[i] = stream[i]->head; tail[i] = stream[i]->tail; \
770 if( head[i] == tail[i] ) \
771 { \
772 --active; \
773 head[i] = head[active]; \
774 tail[i] = tail[active]; \
775 stream[i] = stream[active]; \
776 break; \
777 } \
778 }
779#define MOVE_SMALL_(i,n) *begin = *head[i], ++head[i], ++begin; \
780 if( head[i] == tail[i] ) \
781 if( go_down(that, i, active-1, index, head, tail, n->edges, stream) ) \
782 { \
783 --active; \
784 break; \
785 }
786
787template<class RanIt, class Splitter, class Pred, class Refiller, class Alloc>
788class special_<RanIt,4,Splitter,Pred,Refiller,Alloc>
789{
790 friend class merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>;
791
792 template<class TPtr>
793 static bool go_down(merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc> *that, order_t i, order_t active, bfs_index<4> index, TPtr *head, TPtr *tail, typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::Node::Edge* edges, typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::Node::Edge** stream)
794 {
795 stream[i]->head = head[i];
796 index.child(static_cast<basic_order_t>(stream[i]-edges));
797 that->go_down(*stream[i],index);
798 head[i] = stream[i]->head; tail[i] = stream[i]->tail;
799 if( head[i] == tail[i] )
800 {
801 head[i] = head[active];
802 tail[i] = tail[active];
803 stream[i] = stream[active];
804 return true;
805 }
806 else
807 return false;
808 }
809
810 template<class FwIt>
811 static FwIt fill_root(merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>* that, FwIt begin, FwIt end)
812 {
813 typedef typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
814 typedef typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::Node::Edge Edge;
815 Pred& comp = that->comp;
816 bfs_index<4> index;
817 TPtr head[4], tail[4];
818 Edge *stream[4];
819 order_t active = 0;
820 for( Edge *p=that->root->edges; p!=that->root->edges+4; ++p )
821 if( p->head != p->tail )
822 {
823 stream[active] = p;
824 head[active] = p->head, tail[active] = p->tail;
825 ++active;
826 }
827
828 switch( active )
829 {
830 case 4:
831 for( ;; )
832 {
833 if( begin == end )
834 {
835 stream[0]->head = head[0]; stream[1]->head = head[1]; stream[2]->head = head[2]; stream[3]->head = head[3];
836 return begin;
837 }
838 if( comp(*head[0],*head[3]) )
839 {
840 if( comp(*head[0],*head[2]) )
841 {
842 if( comp(*head[0],*head[1]) )
843 {
844 MOVE_SMALL(0,that->root)
845 }
846 else
847 {
848 MOVE_SMALL(1,that->root)
849 }
850 }
851 else
852 {
853 if( comp(*head[1],*head[2]) )
854 {
855 MOVE_SMALL(1,that->root)
856 }
857 else
858 {
859 MOVE_SMALL(2,that->root)
860 }
861 }
862 }
863 else
864 {
865 if( comp(*head[1],*head[3]) )
866 {
867 if( comp(*head[1],*head[2]) )
868 {
869 MOVE_SMALL(1,that->root)
870 }
871 else
872 {
873 MOVE_SMALL(2,that->root)
874 }
875 }
876 else
877 {
878 if( comp(*head[2],*head[3]) )
879 {
880 MOVE_SMALL(2,that->root)
881 }
882 else
883 {
884 MOVE_SMALL(3,that->root)
885 }
886 }
887 }
888 }
889 case 3:
890 for( ;; )
891 {
892 if( begin == end )
893 {
894 stream[0]->head = head[0]; stream[1]->head = head[1]; stream[2]->head = head[2];
895 return begin;
896 }
897 if( comp(*head[0],*head[2]) )
898 {
899 if( comp(*head[0],*head[1]) )
900 {
901 MOVE_SMALL(0,that->root)
902 }
903 else
904 {
905 MOVE_SMALL(1,that->root)
906 }
907 }
908 else
909 {
910 if( comp(*head[1],*head[2]) )
911 {
912 MOVE_SMALL(1,that->root)
913 }
914 else
915 {
916 MOVE_SMALL(2,that->root)
917 }
918 }
919 }
920 case 2:
921 for( ;; )
922 {
923 if( begin == end )
924 {
925 stream[0]->head = head[0]; stream[1]->head = head[1];
926 return begin;
927 }
928 if( comp(*head[0],*head[1]) )
929 {
930 MOVE_SMALL(0,that->root)
931 }
932 else
933 {
934 MOVE_SMALL(1,that->root)
935 }
936 }
937 case 1:
938 stream[0]->head = head[0];
939 index.child(static_cast<basic_order_t>(stream[0]-that->root->edges));
940 begin = that->copy_root(*stream[0], index, begin, end, typename std::iterator_traits<FwIt>::iterator_category());
941 case 0:
942 return begin;
943 default:
944 assert( false );
945 return begin;
946 }
947 }
948
949 template<class OutIt>
950 static OutIt fill_root(merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>* that, OutIt begin)
951 {
952 typedef typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
953 typedef typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::Node::Edge Edge;
954 Pred& comp = that->comp;
955 bfs_index<4> index;
956 TPtr head[4], tail[4];
957 Edge *stream[4];
958 order_t active = 0;
959 for( Edge *p=that->root->edges; p!=that->root->edges+4; ++p )
960 if( p->head != p->tail )
961 {
962 stream[active] = p;
963 head[active] = p->head, tail[active] = p->tail;
964 ++active;
965 }
966
967 switch( active )
968 {
969 case 4:
970 for( ;; )
971 if( comp(*head[0],*head[3]) )
972 {
973 if( comp(*head[0],*head[2]) )
974 {
975 if( comp(*head[0],*head[1]) )
976 {
977 MOVE_SMALL(0,that->root)
978 }
979 else
980 {
981 MOVE_SMALL(1,that->root)
982 }
983 }
984 else
985 {
986 if( comp(*head[1],*head[2]) )
987 {
988 MOVE_SMALL(1,that->root)
989 }
990 else
991 {
992 MOVE_SMALL(2,that->root)
993 }
994 }
995 }
996 else
997 {
998 if( comp(*head[1],*head[3]) )
999 {
1000 if( comp(*head[1],*head[2]) )
1001 {
1002 MOVE_SMALL(1,that->root)
1003 }
1004 else
1005 {
1006 MOVE_SMALL(2,that->root)
1007 }
1008 }
1009 else
1010 {
1011 if( comp(*head[2],*head[3]) )
1012 {
1013 MOVE_SMALL(2,that->root)
1014 }
1015 else
1016 {
1017 MOVE_SMALL(3,that->root)
1018 }
1019 }
1020 }
1021 case 3:
1022 for( ;; )
1023 if( comp(*head[0],*head[2]) )
1024 {
1025 if( comp(*head[0],*head[1]) )
1026 {
1027 MOVE_SMALL(0,that->root)
1028 }
1029 else
1030 {
1031 MOVE_SMALL(1,that->root)
1032 }
1033 }
1034 else
1035 {
1036 if( comp(*head[1],*head[2]) )
1037 {
1038 MOVE_SMALL(1,that->root)
1039 }
1040 else
1041 {
1042 MOVE_SMALL(2,that->root)
1043 }
1044 }
1045 case 2:
1046 for( ;; )
1047 if( comp(*head[0],*head[1]) )
1048 {
1049 MOVE_SMALL(0,that->root)
1050 }
1051 else
1052 {
1053 MOVE_SMALL(1,that->root)
1054 }
1055 case 1:
1056 stream[0]->head = head[0];
1057 index.child(static_cast<basic_order_t>(stream[0]-that->root->edges));
1058 begin = that->copy_root(*stream[0], index, begin);
1059 case 0:
1060 return begin;
1061 default:
1062 assert( false );
1063 return begin;
1064 }
1065 }
1066
1067 static void fill(merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>* that, typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::NPtr n, typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::Node::Edge& output, bfs_index<4> index)
1068 {
1069 typedef typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
1070 typedef typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::Node::Edge Edge;
1071 Pred& comp = that->comp;
1072 TPtr head[4], tail[4];
1073 Edge *stream[4];
1074 order_t active = 0;
1075 for( Edge *p=n->edges; p!=n->edges+4; ++p )
1076 if( p->head != p->tail )
1077 {
1078 stream[active] = p;
1079 head[active] = p->head, tail[active] = p->tail;
1080 ++active;
1081 }
1082
1083 TPtr begin = output.head;
1084 switch( active )
1085 {
1086 case 4:
1087 for( ;; )
1088 {
1089 if( begin == output.tail )
1090 {
1091 output.head = begin;
1092 stream[0]->head = head[0]; stream[1]->head = head[1]; stream[2]->head = head[2]; stream[3]->head = head[3];
1093 return;
1094 }
1095 if( comp(*head[0],*head[3]) )
1096 {
1097 if( comp(*head[0],*head[2]) )
1098 {
1099 if( comp(*head[0],*head[1]) )
1100 {
1101 MOVE_SMALL(0,n)
1102 }
1103 else
1104 {
1105 MOVE_SMALL(1,n)
1106 }
1107 }
1108 else
1109 {
1110 if( comp(*head[1],*head[2]) )
1111 {
1112 MOVE_SMALL(1,n)
1113 }
1114 else
1115 {
1116 MOVE_SMALL(2,n)
1117 }
1118 }
1119 }
1120 else
1121 {
1122 if( comp(*head[1],*head[3]) )
1123 {
1124 if( comp(*head[1],*head[2]) )
1125 {
1126 MOVE_SMALL(1,n)
1127 }
1128 else
1129 {
1130 MOVE_SMALL(2,n)
1131 }
1132 }
1133 else
1134 {
1135 if( comp(*head[2],*head[3]) )
1136 {
1137 MOVE_SMALL(2,n)
1138 }
1139 else
1140 {
1141 MOVE_SMALL(3,n)
1142 }
1143 }
1144 }
1145 }
1146 case 3:
1147 for( ;; )
1148 {
1149 if( begin == output.tail )
1150 {
1151 output.head = begin;
1152 stream[0]->head = head[0]; stream[1]->head = head[1]; stream[2]->head = head[2];
1153 return;
1154 }
1155 if( comp(*head[0],*head[2]) )
1156 {
1157 if( comp(*head[0],*head[1]) )
1158 {
1159 MOVE_SMALL(0,n)
1160 }
1161 else
1162 {
1163 MOVE_SMALL(1,n)
1164 }
1165 }
1166 else
1167 {
1168 if( comp(*head[1],*head[2]) )
1169 {
1170 MOVE_SMALL(1,n)
1171 }
1172 else
1173 {
1174 MOVE_SMALL(2,n)
1175 }
1176 }
1177 }
1178 case 2:
1179 for( ;; )
1180 {
1181 if( begin == output.tail )
1182 {
1183 output.head = begin;
1184 stream[0]->head = head[0]; stream[1]->head = head[1];
1185 return;
1186 }
1187 if( comp(*head[0],*head[1]) )
1188 {
1189 MOVE_SMALL(0,n)
1190 }
1191 else
1192 {
1193 MOVE_SMALL(1,n)
1194 }
1195 }
1196 case 1:
1197 stream[0]->head = head[0];
1198 index.child(static_cast<basic_order_t>(stream[0]-n->edges));
1199 output.head = that->copy(*stream[0], index, begin, output.tail);
1200 case 0:
1201 return;
1202 default:
1203 assert( false );
1204 return;
1205 }
1206 }
1207
1208 static void fill_leaf(merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>* that, typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::Node::Edge& output, bfs_index<4> index)
1209 {
1210 typedef typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
1211 typedef typename merge_tree<RanIt,4,Splitter,Pred,Refiller,Alloc>::SPtr SPtr;
1212 assert( that->input_streams+4*(index-that->leaf_index) < that->last_stream );
1213 assert( that->input_streams <= that->input_streams+4*(index-that->leaf_index) );
1214 Pred& comp = that->comp;
1215 RanIt head[4], tail[4];
1216 SPtr stream[4];
1217 order_t active = 0;
1218 for( SPtr p=that->input_streams+4*(index-that->leaf_index); p!=that->input_streams+4*(index-that->leaf_index+1); ++p )
1219 if( p->first != p->second )
1220 {
1221 stream[active] = p;
1222 head[active] = p->first, tail[active] = p->second;
1223 ++active;
1224 }
1225
1226 TPtr begin = output.head;
1227 switch( active )
1228 {
1229 case 4:
1230 for( ;; )
1231 {
1232 if( begin == output.tail )
1233 {
1234 output.head = begin;
1235 stream[0]->first = head[0]; stream[1]->first = head[1]; stream[2]->first = head[2]; stream[3]->first = head[3];
1236 // TODO: Refill
1237 return;
1238 }
1239 if( comp(*head[0],*head[3]) )
1240 {
1241 if( comp(*head[0],*head[2]) )
1242 {
1243 if( comp(*head[0],*head[1]) )
1244 {
1245 *begin = *head[0], ++head[0], ++begin;
1246 if( head[0] == tail[0] )
1247 {
1248 stream[0]->first = head[0];
1249 head[0] = head[3];
1250 tail[0] = tail[3];
1251 stream[0] = stream[3];
1252 break;
1253 }
1254 }
1255 else
1256 {
1257 *begin = *head[1], ++head[1], ++begin;
1258 if( head[1] == tail[1] )
1259 {
1260 stream[1]->first = head[1];
1261 head[1] = head[3];
1262 tail[1] = tail[3];
1263 stream[1] = stream[3];
1264 break;
1265 }
1266 }
1267 }
1268 else
1269 {
1270 if( comp(*head[1],*head[2]) )
1271 {
1272 *begin = *head[1], ++head[1], ++begin;
1273 if( head[1] == tail[1] )
1274 {
1275 stream[1]->first = head[1];
1276 head[1] = head[3];
1277 tail[1] = tail[3];
1278 stream[1] = stream[3];
1279 break;
1280 }
1281 }
1282 else
1283 {
1284 *begin = *head[2], ++head[2], ++begin;
1285 if( head[2] == tail[2] )
1286 {
1287 stream[2]->first = head[2];
1288 head[2] = head[3];
1289 tail[2] = tail[3];
1290 stream[2] = stream[3];
1291 break;
1292 }
1293 }
1294 }
1295 }
1296 else
1297 {
1298 if( comp(*head[1],*head[3]) )
1299 {
1300 if( comp(*head[1],*head[2]) )
1301 {
1302 *begin = *head[1], ++head[1], ++begin;
1303 if( head[1] == tail[1] )
1304 {
1305 stream[1]->first = head[1];
1306 head[1] = head[3];
1307 tail[1] = tail[3];
1308 stream[1] = stream[3];
1309 break;
1310 }
1311 }
1312 else
1313 {
1314 *begin = *head[2], ++head[2], ++begin;
1315 if( head[2] == tail[2] )
1316 {
1317 stream[2]->first = head[2];
1318 head[2] = head[3];
1319 tail[2] = tail[3];
1320 stream[2] = stream[3];
1321 break;
1322 }
1323 }
1324 }
1325 else
1326 {
1327 if( comp(*head[2],*head[3]) )
1328 {
1329 *begin = *head[2], ++head[2], ++begin;
1330 if( head[2] == tail[2] )
1331 {
1332 stream[2]->first = head[2];
1333 head[2] = head[3];
1334 tail[2] = tail[3];
1335 stream[2] = stream[3];
1336 break;
1337 }
1338 }
1339 else
1340 {
1341 *begin = *head[3], ++head[3], ++begin;
1342 if( head[3] == tail[3] )
1343 {
1344 stream[3]->first = head[3];
1345 break;
1346 }
1347 }
1348 }
1349 }
1350 }
1351 case 3:
1352 for( ;; )
1353 {
1354 if( begin == output.tail )
1355 {
1356 output.head = begin;
1357 stream[0]->first = head[0]; stream[1]->first = head[1]; stream[2]->first = head[2];
1358 // TODO: Refill
1359 return;
1360 }
1361 if( comp(*head[0],*head[2]) )
1362 {
1363 if( comp(*head[0],*head[1]) )
1364 {
1365 *begin = *head[0], ++head[0], ++begin;
1366 if( head[0] == tail[0] )
1367 {
1368 stream[0]->first = head[0];
1369 head[0] = head[2];
1370 tail[0] = tail[2];
1371 stream[0] = stream[2];
1372 break;
1373 }
1374 }
1375 else
1376 {
1377 *begin = *head[1], ++head[1], ++begin;
1378 if( head[1] == tail[1] )
1379 {
1380 stream[1]->first = head[1];
1381 head[1] = head[2];
1382 tail[1] = tail[2];
1383 stream[1] = stream[2];
1384 break;
1385 }
1386 }
1387 }
1388 else
1389 {
1390 if( comp(*head[1],*head[2]) )
1391 {
1392 *begin = *head[1], ++head[1], ++begin;
1393 if( head[1] == tail[1] )
1394 {
1395 stream[1]->first = head[1];
1396 head[1] = head[2];
1397 tail[1] = tail[2];
1398 stream[1] = stream[2];
1399 break;
1400 }
1401 }
1402 else
1403 {
1404 *begin = *head[2], ++head[2], ++begin;
1405 if( head[2] == tail[2] )
1406 {
1407 stream[2]->first = head[2];
1408 break;
1409 }
1410 }
1411 }
1412 }
1413 case 2:
1414 for( ;; )
1415 {
1416 if( begin == output.tail )
1417 {
1418 output.head = begin;
1419 stream[0]->first = head[0]; stream[1]->first = head[1];
1420 // TODO: Refill
1421 return;
1422 }
1423 if( comp(*head[0],*head[1]) )
1424 {
1425 *begin = *head[0], ++head[0], ++begin;
1426 if( head[0] == tail[0] )
1427 {
1428 stream[0]->first = head[0];
1429
1430 if( output.tail-begin < stream[1]->second-head[1] )
1431 for( ; begin!=output.tail; ++begin, ++head[1] )
1432 *begin = *head[1];
1433 else
1434 for( ; stream[1]->second!=head[1]; ++begin, ++head[1] )
1435 *begin = *head[1];
1436 output.head = begin;
1437 stream[1]->first = head[1];
1438
1439 //head[0] = head[1];
1440 //tail[0] = tail[1];
1441 //stream[0] = stream[1];
1442 //break;
1443 return;
1444 }
1445 }
1446 else
1447 {
1448 *begin = *head[1], ++head[1], ++begin;
1449 if( head[1] == tail[1] )
1450 {
1451 stream[1]->first = head[1];
1452 break;
1453 }
1454 }
1455 }
1456 case 1:
1457 if( output.tail-begin < stream[0]->second-head[0] )
1458 for( ; begin!=output.tail; ++begin, ++head[0] )
1459 *begin = *head[0];
1460 else
1461 for( ; stream[0]->second!=head[0]; ++begin, ++head[0] )
1462 *begin = *head[0];
1463 output.head = begin;
1464 stream[0]->first = head[0];
1465 // TODO: Refill
1466 return;
1467 case 0:
1468 return;
1469 default:
1470 assert( false );
1471 return;
1472 }
1473 }
1474};
1475
1476
1477
1478/*****
1479 * Alloc::pointer iterator template specialization
1480 */
1481
1482template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1483void merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::Node::Edge::fill_dflt(TPtr b, TPtr e, allocator alloc)
1484{
1485 TPtr p = b;
1486 try
1487 {
1488 value_type dflt;
1489 for( ; p!=e; ++p )
1490 alloc.construct(p,dflt);
1491 }
1492 catch( ... )
1493 {
1494 if( p != b )
1495 {
1496 for( --p; p!=b; --p )
1497 alloc.destroy(p);
1498 alloc.destroy(p);
1499 }
1500 alloc.deallocate(b,e-b);
1501 throw;
1502 }
1503}
1504
1505template<int Order, class Splitter, class Pred, class Refiller, class Alloc>
1506typename merge_tree<typename Alloc::pointer,Order,Splitter,Pred,Refiller,Alloc>::Node::Edge** merge_tree<typename Alloc::pointer,Order,Splitter,Pred,Refiller,Alloc>::Node::construct(order_t k, height_t height, size_t *buf_size, typename merge_tree<typename Alloc::pointer,Order,Splitter,Pred,Refiller,Alloc>::Node::Edge** edge_list, allocator alloc, nallocator nalloc)
1507{
1508 order_t lk = pow_of_order<order>(height-1);
1509 int i = 0;
1510 try
1511 {
1512 for( ; i!=order && lk < k; ++i, k-=lk )
1513 {
1514 edge_list = edges[i].construct(lk, height-1, buf_size, edge_list, alloc, nalloc);
1515 }
1516 if( i != order )
1517 {
1518 assert( k <= lk );
1519 edge_list = edges[i].construct(k, height-1, buf_size, edge_list, alloc, nalloc);
1520 ++i;
1521 }
1522 for( ; i!=order; ++i )
1523 {
1524 edges[i].child = NPtr();
1525 edges[i].begin = edges[i].end = TPtr();
1526 }
1527 return edge_list;
1528 }
1529 catch( ... )
1530 {
1531 if( i )
1532 {
1533 for( --i; i; --i )
1534 edges[i].destroy(alloc, nalloc);
1535 edges[i].destroy(alloc, nalloc);
1536 }
1537 throw;
1538 }
1539}
1540
1541template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1542typename merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::Node::Edge** merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::Node::Edge::construct(order_t k, height_t height, size_t *buf_size, Edge** edge_list, allocator alloc, nallocator nalloc)
1543{
1544 if( height > 0 )
1545 {
1546 begin = alloc.allocate(*buf_size);
1547 head = tail = end = begin+*buf_size;
1548 try
1549 {
1550 fill_dflt(begin,end,alloc);
1551 try
1552 {
1553 child = nalloc.allocate(1);
1554 try
1555 {
1556 nalloc.construct(child, Node());
1557 return child->construct(k,height,buf_size+1,edge_list,alloc,nalloc);
1558 }
1559 catch( ... )
1560 {
1561 child->destroy(alloc, nalloc);
1562 nalloc.destroy(child);
1563 throw;
1564 }
1565 }
1566 catch( ... )
1567 {
1568 nalloc.deallocate(child, 1);
1569 throw;
1570 }
1571 }
1572 catch( ... )
1573 {
1574 alloc.deallocate(begin,*buf_size);
1575 throw;
1576 }
1577 }
1578 else
1579 {
1580 child = NPtr();
1581 head = tail = end = begin = TPtr();
1582 *edge_list = this;
1583 return edge_list+1;
1584 }
1585}
1586
1587template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1588void merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::Node::destroy(allocator alloc, nallocator nalloc)
1589{
1590 for( int i=0; i!=order; ++i )
1591 edges[i].destroy(alloc, nalloc);
1592}
1593
1594
1595template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1596void merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::Node::Edge::destroy(allocator alloc, nallocator nalloc)
1597{
1598 if( child != NPtr() )
1599 {
1600 child->destroy(alloc,nalloc);
1601 nalloc.destroy(child);
1602 nalloc.deallocate(child,1);
1603 }
1604 if( begin != TPtr() )
1605 {
1606 for( TPtr p=begin; p!=end; ++p )
1607 alloc.destroy(p);
1608 alloc.deallocate(begin,end-begin);
1609 }
1610}
1611
1612
1613template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1614void merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::compute_buffer_sizes(size_type *b, size_type *e)
1615{
1616 height_t sp = Splitter::split(static_cast<height_t>(e-b));
1617 if( e-b > 2 )
1618 {
1619 compute_buffer_sizes(b, b+sp);
1620 compute_buffer_sizes(b+sp, e);
1621 }
1622 b[sp] = Splitter::out_buffer_size(pow_of_order<order>(static_cast<height_t>(e-b-sp)));
1623}
1624
1625template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1626void merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::construct(order_t k)
1627{
1628 if(!( order < k ))
1629 throw std::invalid_argument("Merge tree too small");
1630 height_t height = logc<order>(k);
1631 if( height > MAX_MERGE_TREE_HEIGHT )
1632 throw std::invalid_argument("Merge tree too high");
1633 bfs_index<order> bfs;
1634 for( height_t l=1; l!=logc<order>(k); ++l )
1635 bfs.child(0);
1636 leaf_index = bfs;
1637 size_type buffer_sizes[MAX_MERGE_TREE_HEIGHT];
1638 compute_buffer_sizes(buffer_sizes,buffer_sizes+height);
1639
1640 last_stream = input_streams = salloc.allocate(k);
1641 SPtr p = input_streams;
1642 try
1643 {
1644 stream_t dflt;
1645 for( ; p!=last_stream+k; ++p )
1646 salloc.construct(p,dflt);
1647
1648 try
1649 {
1650 root = nalloc.allocate(1);
1651 try
1652 {
1653 nalloc.construct(root, Node());
1654 root->construct(k,height,buffer_sizes+1,input_streams,alloc,nalloc);
1655 }
1656 catch( ... )
1657 {
1658 root->destroy(alloc, nalloc);
1659 nalloc.destroy(root);
1660 throw;
1661 }
1662 }
1663 catch( ... )
1664 {
1665 nalloc.deallocate(root,1);
1666 throw;
1667 }
1668 }
1669 catch( ... )
1670 {
1671 if( p != input_streams )
1672 {
1673 for( --p; p!=input_streams; --p )
1674 salloc.destroy(p);
1675 salloc.destroy(p);
1676 }
1677 salloc.deallocate(input_streams,k);
1678 throw;
1679 }
1680}
1681
1682template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1683merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::~merge_tree()
1684{
1685 for( SPtr s=input_streams; s!=input_streams+k; ++s )
1686 salloc.destroy(s);
1687 salloc.deallocate(input_streams, k);
1688 root->destroy(alloc, nalloc);
1689 nalloc.destroy(root);
1690 nalloc.deallocate(root,1);
1691}
1692
1693template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1694void merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::reset()
1695{
1696 cold = true;
1697 last_stream = input_streams;
1698}
1699
1700template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1701template<class FwIt>
1702FwIt merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::operator()(FwIt begin, FwIt end)
1703{
1704 if( cold )
1705 for( int i=0; i!=order; ++i )
1706 if( root->edges[i].child != NPtr() )
1707 go_down_cold(root->edges[i], comp);
1708 cold = false;
1709 return fill(root, begin, end, comp);
1710}
1711
1712template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1713template<class OutIt>
1714OutIt merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::operator()(OutIt begin)
1715{
1716 if( cold )
1717 for( int i=0; i!=order; ++i )
1718 if( root->edges[i].child != NPtr() )
1719 go_down_cold(root->edges[i], comp);
1720 cold = false;
1721 return fill(root, begin, comp);
1722}
1723
1724template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1725template<class FwIt>
1726FwIt merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::empty_buffers(NPtr n, FwIt begin, FwIt end)
1727{
1728 for( int i=0; i!=order; ++i )
1729 {
1730 for( ; n->edges[i].head!=n->edges[i].tail && begin!=end; ++n->edges[i].head, ++begin )
1731 *begin = *n->edges[i].head;
1732 if( n->edges[i].child )
1733 begin = empty_buffers(n->edges[i].child, begin, end);
1734 }
1735 return begin;
1736}
1737
1738template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1739template<class OutIt>
1740OutIt merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::empty_buffers(NPtr n, OutIt begin)
1741{
1742 for( int i=0; i!=order; ++i )
1743 {
1744 begin = std::copy(n->edges[i].head, n->edges[i].tail, begin);
1745 if( n->edges[i].child )
1746 begin = empty_buffers(n->edges[i].child, begin);
1747 }
1748 return begin;
1749}
1750
1751template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1752void merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::go_down(typename Node::Edge& e, Pred comp)
1753{
1754 assert( e.tail == e.head );
1755 assert( e.child != NPtr() );
1756 e.tail = fill(e.child, e.begin, e.tail, comp);
1757 e.head = e.begin;
1758}
1759
1760template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1761void merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::go_down_cold(typename Node::Edge& e, Pred comp)
1762{
1763 assert( e.child != NPtr() );
1764 e.tail = e.end, e.head = e.begin;
1765 warmup(e.child, e, comp);
1766 e.tail = e.head, e.head = e.begin;
1767}
1768
1769template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1770void merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::warmup(NPtr n, typename Node::Edge& output, Pred comp)
1771{
1772 for( int i=0; i!=order; ++i )
1773 if( n->edges[i].child != NPtr() )
1774 go_down_cold(n->edges[i], comp);
1775 output.head = fill(n, output.head, output.tail, comp);
1776}
1777
1778template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1779template<class FwIt>
1780FwIt merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::copy(typename Node::Edge& de, FwIt begin, FwIt end, Pred comp, std::forward_iterator_tag)
1781{
1782 for( ;; )
1783 {
1784 for( ; de.tail!=de.head && begin!=end; ++begin, ++de.head )
1785 *begin = *de.head;
1786 if( de.tail == de.head && de.child != NPtr() )
1787 {
1788 go_down(de, comp);
1789 if( de.head == de.tail )
1790 return begin;
1791 }
1792 else
1793 return begin;
1794 }
1795}
1796
1797template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1798template<class RIt>
1799RIt merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::copy(typename Node::Edge& de, RIt begin, RIt end, Pred comp, std::random_access_iterator_tag)
1800{
1801/* for( ;; )
1802 {
1803 for( ; de.tail!=de.head && begin!=end; ++begin, ++de.head )
1804 *begin = *de.head;
1805 if( de.tail == de.head )
1806 {
1807 go_down(de, comp);
1808 if( de.head == de.tail )
1809 return begin;
1810 }
1811 else
1812 return begin;
1813 }
1814*/
1815 for( ;; )
1816 {
1817 if( end-begin < de.tail-de.head )
1818 {
1819 for( ; begin!=end; ++begin, ++de.head )
1820 *begin = *de.head;
1821 return begin;
1822 }
1823 else
1824 {
1825 for( ; de.tail!=de.head; ++begin, ++de.head )
1826 *begin = *de.head;
1827 if( de.child != NPtr() )
1828 {
1829 go_down(de, comp);
1830 if( de.head == de.tail )
1831 return begin;
1832 }
1833 else
1834 return begin;
1835 }
1836 }
1837
1838}
1839
1840template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1841template<class OutIt>
1842OutIt merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::copy(typename Node::Edge& de, OutIt begin, Pred comp)
1843{
1844 do
1845 {
1846 for( ; de.tail!=de.head; ++begin, ++de.head )
1847 *begin = *de.head;
1848 if( de.child != NPtr() )
1849 go_down(de, comp);
1850 else
1851 break;
1852 }
1853 while( de.head != de.tail );
1854 return begin;
1855}
1856
1857/*****
1858 * Alloc::pointer iterator, order 2 basic merger template specialization
1859 */
1860
1861template<class Splitter, class Pred, class Refiller, class Alloc>
1862class special_<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>
1863{
1864 friend class merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>;
1865
1866 template<class FwIt>
1867 static FwIt fill(typename merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::NPtr root, FwIt begin, FwIt end, Pred comp)
1868 {
1869 typedef typename merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::NPtr NPtr;
1870 typedef typename merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
1871 typedef typename merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::Node Node;
1872 for( ;; )
1873 if( root->edges[0].head != root->edges[0].tail )
1874 if( root->edges[1].head != root->edges[1].tail )
1875 for( TPtr l=root->edges[0].head, r=root->edges[1].head;; )
1876 {
1877 if( begin == end )
1878 {
1879 root->edges[0].head = l;
1880 root->edges[1].head = r;
1881 return begin;
1882 }
1883 if( comp(*l,*r) )
1884 {
1885 *begin = *l, ++l, ++begin;
1886 if( l == root->edges[0].tail )
1887 {
1888 typename Node::Edge& de = root->edges[0];
1889 root->edges[0].head = l; root->edges[1].head = r;
1890 if( de.child != NPtr() )
1891 merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::go_down(de, comp);
1892 if( de.head == de.tail )
1893 break;
1894 l = root->edges[0].head;
1895 }
1896 }
1897 else
1898 {
1899 *begin = *r, ++r, ++begin;
1900 if( r == root->edges[1].tail )
1901 {
1902 typename Node::Edge& de = root->edges[1];
1903 root->edges[0].head = l; root->edges[1].head = r;
1904 if( de.child != NPtr() )
1905 merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::go_down(de, comp);
1906 if( de.head == de.tail )
1907 break;
1908 r = root->edges[1].head;
1909 }
1910 }
1911 }
1912 else
1913 return merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::copy(root->edges[0], begin, end, comp, typename std::iterator_traits<FwIt>::iterator_category());
1914 else if( root->edges[1].head != root->edges[1].tail )
1915 return merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::copy(root->edges[1], begin, end, comp, typename std::iterator_traits<FwIt>::iterator_category());
1916 else
1917 return begin;
1918 }
1919
1920 template<class OutIt>
1921 static OutIt fill(typename merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::NPtr root, OutIt begin, Pred comp)
1922 {
1923 typedef typename merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::NPtr NPtr;
1924 typedef typename merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
1925 typedef typename merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::Node Node;
1926 for( ;; )
1927 if( root->edges[0].head != root->edges[0].tail )
1928 if( root->edges[1].head != root->edges[1].tail )
1929 for( TPtr l=root->edges[0].head, r=root->edges[1].head;; )
1930 if( comp(*l,*r) )
1931 {
1932 *begin = *l, ++l, ++begin;
1933 if( l == root->edges[0].tail )
1934 {
1935 typename Node::Edge& de = root->edges[0];
1936 root->edges[0].head = l; root->edges[1].head = r;
1937 if( de.child != NPtr() )
1938 merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::go_down(de, comp);
1939 if( de.head == de.tail )
1940 break;
1941 l = root->edges[0].head;
1942 }
1943 }
1944 else
1945 {
1946 *begin = *r, ++r, ++begin;
1947 if( r == root->edges[1].tail )
1948 {
1949 typename Node::Edge& de = root->edges[1];
1950 root->edges[0].head = l; root->edges[1].head = r;
1951 if( de.child != NPtr() )
1952 merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::go_down(de, comp);
1953 if( de.head == de.tail )
1954 break;
1955 r = root->edges[1].head;
1956 }
1957 }
1958 else
1959 return merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::copy(root->edges[0], begin, comp);
1960 else if( root->edges[1].head != root->edges[1].tail )
1961 return merge_tree<typename Alloc::pointer,2,Splitter,Pred,Refiller,Alloc>::copy(root->edges[1], begin, comp);
1962 else
1963 return begin;
1964 }
1965
1966};
1967
1968/*****
1969 * Alloc::pointer iterator, order 4 basic merger template specialization
1970 */
1971
1972#define MOVE_SMALL_PTR(i,a) *begin = *head[i], ++head[i], ++begin; \
1973 if( head[i] == tail[i] ) \
1974 { \
1975 stream[i]->head = head[i]; \
1976 if( stream[i]->child != NPtr() ) \
1977 { \
1978 merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::go_down(*stream[i], comp); \
1979 head[i] = stream[i]->head; tail[i] = stream[i]->tail; \
1980 } \
1981 if( head[i] == tail[i] ) \
1982 { \
1983 head[i] = head[a-1]; \
1984 tail[i] = tail[a-1]; \
1985 stream[i] = stream[a-1]; \
1986 break; \
1987 } \
1988 }
1989#define MOVE_SMALL_PTR_(i,a) *begin = *head[i], ++head[i], ++begin; \
1990 if( head[i] == tail[i] ) \
1991 if( go_down<i,a>(stream,head,tail,comp) ) \
1992 break; \
1993
1994template<class Splitter, class Pred, class Refiller, class Alloc>
1995class special_<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>
1996{
1997 friend class merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>;
1998
1999 template<int i, int a>
2000 static bool go_down(typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::Node::Edge** stream, typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::TPtr* head, typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::TPtr* tail, Pred comp)
2001 {
2002 typedef typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::NPtr NPtr;
2003 stream[i]->head = head[i];
2004 if( stream[i]->child != NPtr() )
2005 {
2006 merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::go_down(*stream[i], comp);
2007 head[i] = stream[i]->head; tail[i] = stream[i]->tail;
2008 }
2009 if( head[i] == tail[i] )
2010 {
2011 head[i] = head[a-1];
2012 tail[i] = tail[a-1];
2013 stream[i] = stream[a-1];
2014 return true;
2015 }
2016 return false;
2017 }
2018
2019 template<class FwIt>
2020 static FwIt fill(typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::NPtr n, FwIt begin, FwIt end, Pred comp)
2021 {
2022 typedef typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::NPtr NPtr;
2023 typedef typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
2024 typedef typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::Node::Edge Edge;
2025 TPtr head[4], tail[4];
2026 Edge *stream[4];
2027 order_t active = 0;
2028 for( Edge *p=n->edges; p!=n->edges+4; ++p )
2029 if( p->head != p->tail )
2030 {
2031 stream[active] = p;
2032 head[active] = p->head, tail[active] = p->tail;
2033 ++active;
2034 }
2035
2036 switch( active )
2037 {
2038 case 4:
2039 for( ;; )
2040 {
2041 if( begin == end )
2042 {
2043 stream[0]->head = head[0]; stream[1]->head = head[1]; stream[2]->head = head[2]; stream[3]->head = head[3];
2044 return begin;
2045 }
2046 if( comp(*head[0],*head[3]) )
2047 {
2048 if( comp(*head[0],*head[2]) )
2049 {
2050 if( comp(*head[0],*head[1]) )
2051 {
2052 MOVE_SMALL_PTR(0,4)
2053 }
2054 else
2055 {
2056 MOVE_SMALL_PTR(1,4)
2057 }
2058 }
2059 else
2060 {
2061 if( comp(*head[1],*head[2]) )
2062 {
2063 MOVE_SMALL_PTR(1,4)
2064 }
2065 else
2066 {
2067 MOVE_SMALL_PTR(2,4)
2068 }
2069 }
2070 }
2071 else
2072 {
2073 if( comp(*head[1],*head[3]) )
2074 {
2075 if( comp(*head[1],*head[2]) )
2076 {
2077 MOVE_SMALL_PTR(1,4)
2078 }
2079 else
2080 {
2081 MOVE_SMALL_PTR(2,4)
2082 }
2083 }
2084 else
2085 {
2086 if( comp(*head[2],*head[3]) )
2087 {
2088 MOVE_SMALL_PTR(2,4)
2089 }
2090 else
2091 {
2092 MOVE_SMALL_PTR(3,4)
2093 }
2094 }
2095 }
2096 }
2097 case 3:
2098 for( ;; )
2099 {
2100 if( begin == end )
2101 {
2102 stream[0]->head = head[0]; stream[1]->head = head[1]; stream[2]->head = head[2];
2103 return begin;
2104 }
2105 if( comp(*head[0],*head[2]) )
2106 {
2107 if( comp(*head[0],*head[1]) )
2108 {
2109 MOVE_SMALL_PTR(0,3)
2110 }
2111 else
2112 {
2113 MOVE_SMALL_PTR(1,3)
2114 }
2115 }
2116 else
2117 {
2118 if( comp(*head[1],*head[2]) )
2119 {
2120 MOVE_SMALL_PTR(1,3)
2121 }
2122 else
2123 {
2124 MOVE_SMALL_PTR(2,3)
2125 }
2126 }
2127 }
2128 case 2:
2129 for( ;; )
2130 {
2131 if( begin == end )
2132 {
2133 stream[0]->head = head[0]; stream[1]->head = head[1];
2134 return begin;
2135 }
2136 if( comp(*head[0],*head[1]) )
2137 {
2138 MOVE_SMALL_PTR(0,2)
2139 }
2140 else
2141 {
2142 MOVE_SMALL_PTR(1,2)
2143 }
2144 }
2145 case 1:
2146 stream[0]->head = head[0];
2147 begin = merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::copy(*stream[0], begin, end, comp, typename std::iterator_traits<FwIt>::iterator_category());
2148 case 0:
2149 return begin;
2150 default:
2151 assert( false );
2152 return begin;
2153 }
2154 }
2155
2156 template<class OutIt>
2157 static OutIt fill(typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::NPtr n, OutIt begin, Pred comp)
2158 {
2159 typedef typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::NPtr NPtr;
2160 typedef typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::TPtr TPtr;
2161 typedef typename merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::Node::Edge Edge;
2162 TPtr head[4], tail[4];
2163 Edge *stream[4];
2164 order_t active = 0;
2165 for( Edge *p=n->edges; p!=n->edges+4; ++p )
2166 if( p->head != p->tail )
2167 {
2168 stream[active] = p;
2169 head[active] = p->head, tail[active] = p->tail;
2170 ++active;
2171 }
2172
2173 switch( active )
2174 {
2175 case 4:
2176 for( ;; )
2177 if( comp(*head[0],*head[3]) )
2178 {
2179 if( comp(*head[0],*head[2]) )
2180 {
2181 if( comp(*head[0],*head[1]) )
2182 {
2183 MOVE_SMALL_PTR(0,4)
2184 }
2185 else
2186 {
2187 MOVE_SMALL_PTR(1,4)
2188 }
2189 }
2190 else
2191 {
2192 if( comp(*head[1],*head[2]) )
2193 {
2194 MOVE_SMALL_PTR(1,4)
2195 }
2196 else
2197 {
2198 MOVE_SMALL_PTR(2,4)
2199 }
2200 }
2201 }
2202 else
2203 {
2204 if( comp(*head[1],*head[3]) )
2205 {
2206 if( comp(*head[1],*head[2]) )
2207 {
2208 MOVE_SMALL_PTR(1,4)
2209 }
2210 else
2211 {
2212 MOVE_SMALL_PTR(2,4)
2213 }
2214 }
2215 else
2216 {
2217 if( comp(*head[2],*head[3]) )
2218 {
2219 MOVE_SMALL_PTR(2,4)
2220 }
2221 else
2222 {
2223 MOVE_SMALL_PTR(3,4)
2224 }
2225 }
2226 }
2227 case 3:
2228 for( ;; )
2229 if( comp(*head[0],*head[2]) )
2230 {
2231 if( comp(*head[0],*head[1]) )
2232 {
2233 MOVE_SMALL_PTR(0,3)
2234 }
2235 else
2236 {
2237 MOVE_SMALL_PTR(1,3)
2238 }
2239 }
2240 else
2241 {
2242 if( comp(*head[1],*head[2]) )
2243 {
2244 MOVE_SMALL_PTR(1,3)
2245 }
2246 else
2247 {
2248 MOVE_SMALL_PTR(2,3)
2249 }
2250 }
2251 case 2:
2252 for( ;; )
2253 if( comp(*head[0],*head[1]) )
2254 {
2255 MOVE_SMALL_PTR(0,2)
2256 }
2257 else
2258 {
2259 MOVE_SMALL_PTR(1,2)
2260 }
2261 case 1:
2262 stream[0]->head = head[0];
2263 begin = merge_tree<typename Alloc::pointer,4,Splitter,Pred,Refiller,Alloc>::copy(*stream[0], begin, comp);
2264 case 0:
2265 return begin;
2266 default:
2267 assert( false );
2268 return begin;
2269 }
2270 }
2271
2272};
2273
2274
2275} // namespace iosort
compare
int compare(const void *arg, const void *obj)
Definition TommyObj.h:33
iosort::bfs_index
Definition funnel.h:72
iosort::bfs_index::child
void child(basic_order_t ch)
Definition funnel.h:83
iosort::bfs_index::parent
void parent()
Definition funnel.h:85
iosort::merge_tree::stream_iterator
Definition funnel.h:183
iosort::merge_tree
Definition funnel.h:121
iosort::merge_tree::operator()
It operator()(It begin, It end)
iosort::merge_tree::MAX_MERGE_TREE_HEIGHT
@ MAX_MERGE_TREE_HEIGHT
Definition funnel.h:126
iosort::merge_tree::reset
void reset()
Definition funnel.timpl.h:230
iosort::merge_tree::allocator
Alloc allocator
Definition funnel.h:129
iosort::merge_tree::order
@ order
Definition funnel.h:125
iosort::merge_tree::begin
stream_iterator begin()
Definition funnel.h:208
iosort::merge_tree::order_t
unsigned int order_t
Definition funnel.h:124
iosort::merge_tree::~merge_tree
~merge_tree()
Definition funnel.timpl.h:217
iosort::merge_tree::value_type
std::iterator_traits< RanIt >::value_type value_type
Definition funnel.h:128
iosort::merge_tree::end
stream_iterator end()
Definition funnel.h:210
iosort::special_
Definition funnel.h:117
output
bool output
Definition comms.cpp:56
MOVE_SMALL
#define MOVE_SMALL(i, n)
Definition funnel.timpl.h:762
MOVE_SMALL_PTR
#define MOVE_SMALL_PTR(i, a)
Definition funnel.timpl.h:1972
iosort::order_t
unsigned int order_t
Definition funnel.h:34
iosort::basic_order_t
unsigned short basic_order_t
Definition funnel.h:33
iosort::height_t
unsigned short height_t
Definition funnel.h:32
Node
Definition Node.h:14
iosort::merge_tree::Node::Edge
Definition funnel.h:144
iosort::merge_tree::Node::Edge::TPtr
allocator::pointer TPtr
Definition funnel.h:145
iosort::merge_tree::Node::Edge::NPtr
nallocator::pointer NPtr
Definition funnel.h:147
iosort::merge_tree::Node::Edge::tail
allocator::pointer tail
Definition funnel.h:151
iosort::merge_tree::Node::Edge::construct
void construct(order_t k, height_t height, size_t *buf_size, allocator alloc, nallocator nalloc)
Definition funnel.timpl.h:81
iosort::merge_tree::Node::Edge::nallocator
allocator::template rebind< Node >::other nallocator
Definition funnel.h:146
iosort::merge_tree::Node::Edge::destroy
void destroy(allocator alloc, nallocator nalloc)
Definition funnel.timpl.h:128
iosort::merge_tree::Node::Edge::head
allocator::pointer head
Definition funnel.h:151