COMBINATORIAL_BLAS  1.6
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 
19 namespace iosort
20 {
21 
22 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
23 void 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 
45 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
46 void 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 
80 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
81 void 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 
119 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
120 void 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 
127 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
128 void 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 
146 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
147 void 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 
158 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
159 void 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 
216 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
217 merge_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 
229 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
230 void 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 
245 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
246 template<class FwIt>
247 FwIt 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 
262 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
263 template<class OutIt>
264 OutIt 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 
279 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
280 template<class FwIt>
281 FwIt 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 
293 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
294 template<class OutIt>
295 OutIt 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 
306 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
307 void 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 
319 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
320 void 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 
331 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
332 void 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 
342 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
343 template<class FwIt>
344 FwIt 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 
361 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
362 template<class RIt>
363 RIt 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 
380 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
381 template<class OutIt>
382 OutIt 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 
394 template<class RanIt, int order, class Splitter, class Pred, class Refiller, class Alloc>
395 typename 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 
421 template<class RanIt, class Splitter, class Pred, class Refiller, class Alloc>
422 class 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 
787 template<class RanIt, class Splitter, class Pred, class Refiller, class Alloc>
788 class 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 
1482 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1483 void 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 
1505 template<int Order, class Splitter, class Pred, class Refiller, class Alloc>
1506 typename 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 
1541 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1542 typename 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 
1587 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1588 void 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 
1595 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1596 void 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 
1613 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1614 void 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 
1625 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1626 void 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 
1682 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1683 merge_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 
1693 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1694 void merge_tree<typename Alloc::pointer,order,Splitter,Pred,Refiller,Alloc>::reset()
1695 {
1696  cold = true;
1697  last_stream = input_streams;
1698 }
1699 
1700 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1701 template<class FwIt>
1702 FwIt 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 
1712 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1713 template<class OutIt>
1714 OutIt 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 
1724 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1725 template<class FwIt>
1726 FwIt 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 
1738 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1739 template<class OutIt>
1740 OutIt 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 
1751 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1752 void 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 
1760 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1761 void 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 
1769 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1770 void 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 
1778 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1779 template<class FwIt>
1780 FwIt 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 
1797 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1798 template<class RIt>
1799 RIt 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 
1840 template<int order, class Splitter, class Pred, class Refiller, class Alloc>
1841 template<class OutIt>
1842 OutIt 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 
1861 template<class Splitter, class Pred, class Refiller, class Alloc>
1862 class 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 
1994 template<class Splitter, class Pred, class Refiller, class Alloc>
1995 class 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
iosort::merge_tree::Node::Edge::destroy
void destroy(allocator alloc, nallocator nalloc)
Definition: funnel.timpl.h:128
iosort::merge_tree::Node::Edge::tail
allocator::pointer tail
Definition: funnel.h:151
iosort::merge_tree::Node::Edge::NPtr
nallocator::pointer NPtr
Definition: funnel.h:147
MOVE_SMALL
#define MOVE_SMALL(i, n)
Definition: funnel.timpl.h:762
iosort::merge_tree::Node
friend struct Node
Definition: funnel.h:135
iosort::merge_tree::reset
void reset()
Definition: funnel.timpl.h:230
iosort::merge_tree
Definition: funnel.h:120
iosort::merge_tree::~merge_tree
~merge_tree()
Definition: funnel.timpl.h:217
iosort::special_
Definition: funnel.h:117
iosort::merge_tree::Node::Edge::TPtr
allocator::pointer TPtr
Definition: funnel.h:145
iosort::bfs_index::child
void child(basic_order_t ch)
Definition: funnel.h:83
iosort::merge_tree::value_type
std::iterator_traits< RanIt >::value_type value_type
Definition: funnel.h:128
iosort::basic_order_t
unsigned short basic_order_t
Definition: funnel.h:33
iosort::height_t
unsigned short height_t
Definition: funnel.h:32
iosort::order_t
unsigned int order_t
Definition: funnel.h:34
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
MOVE_SMALL_PTR
#define MOVE_SMALL_PTR(i, a)
Definition: funnel.timpl.h:1972
iosort::merge_tree::Node::Edge::head
allocator::pointer head
Definition: funnel.h:151
iosort::merge_tree::operator()
It operator()(It begin, It end)
iosort::merge_tree::Node::Edge
Definition: funnel.h:143
iosort::merge_tree::Node::Edge::begin
allocator::pointer begin
Definition: funnel.h:151
iosort::merge_tree::order_t
unsigned int order_t
Definition: funnel.h:124
iosort::merge_tree::Node::Edge::child
allocator::template rebind< Node >::other::pointer child
Definition: funnel.h:150
iosort::merge_tree::Node::Edge::nallocator
allocator::template rebind< Node >::other nallocator
Definition: funnel.h:146
iosort::bfs_index
Definition: funnel.h:71
iosort::merge_tree::stream_iterator
Definition: funnel.h:182
iosort::bfs_index::parent
void parent()
Definition: funnel.h:85
iosort
Definition: funnel.h:29
iosort::merge_tree::order
Definition: funnel.h:125
iosort::merge_tree::allocator
Alloc allocator
Definition: funnel.h:129
combblas::compare
bool compare(const T &a, const T &b, std::false_type)
Definition: Compare.h:41
iosort::merge_tree::MAX_MERGE_TREE_HEIGHT
Definition: funnel.h:126
iosort::merge_tree::Node::Edge::end
allocator::pointer end
Definition: funnel.h:151