Stxxl  1.2.1
stream.h
1 /***************************************************************************
2  * include/stxxl/bits/stream/stream.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2003-2005 Roman Dementiev <dementiev@mpi-sb.mpg.de>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_STREAM_HEADER
14 #define STXXL_STREAM_HEADER
15 
16 #include <stxxl/bits/namespace.h>
17 #include <stxxl/bits/mng/buf_istream.h>
18 #include <stxxl/bits/mng/buf_ostream.h>
19 #include <stxxl/bits/common/tuple.h>
20 #include <stxxl/vector>
21 #include <stxxl/bits/compat_auto_ptr.h>
22 
23 
24 __STXXL_BEGIN_NAMESPACE
25 
27 namespace stream
28 {
53 
57  template <class InputIterator_>
59  {
60  InputIterator_ current_, end_;
61 
62  public:
64  typedef typename std::iterator_traits<InputIterator_>::value_type value_type;
65 
66  iterator2stream(InputIterator_ begin, InputIterator_ end) :
67  current_(begin), end_(end) { }
68 
69  iterator2stream(const iterator2stream & a) : current_(a.current_), end_(a.end_) { }
70 
72  const value_type & operator * () const
73  {
74  return *current_;
75  }
76 
77  const value_type * operator -> () const
78  {
79  return &(*current_);
80  }
81 
84  {
85  assert(end_ != current_);
86  ++current_;
87  return *this;
88  }
89 
91  bool empty() const
92  {
93  return (current_ == end_);
94  }
95  };
96 
97 
102  template <class InputIterator_>
103  iterator2stream<InputIterator_> streamify(InputIterator_ begin, InputIterator_ end)
104  {
105  return iterator2stream<InputIterator_>(begin, end);
106  }
107 
109  template <class InputIterator_>
111  {
114  };
115 
120  template <class InputIterator_>
122  {
123  InputIterator_ current_, end_;
124  typedef buf_istream<typename InputIterator_::block_type,
125  typename InputIterator_::bids_container_iterator> buf_istream_type;
126 
127  typedef typename stxxl::compat_auto_ptr<buf_istream_type>::result auto_ptr_type;
128  mutable auto_ptr_type in;
129 
130  void delete_stream()
131  {
132  in.reset();
133  }
134 
135  public:
137 
139  typedef typename std::iterator_traits<InputIterator_>::value_type value_type;
140 
141  vector_iterator2stream(InputIterator_ begin, InputIterator_ end, unsigned_type nbuffers = 0) :
142  current_(begin), end_(end)
143  {
144  begin.flush(); // flush container
145  typename InputIterator_::bids_container_iterator end_iter = end.bid() + ((end.block_offset()) ? 1 : 0);
146 
147  if (end_iter - begin.bid() > 0)
148  {
149  in.reset(new buf_istream_type(begin.bid(), end_iter, nbuffers ? nbuffers :
150  (2 * config::get_instance()->disks_number())));
151 
152  InputIterator_ cur = begin - begin.block_offset();
153 
154  // skip the beginning of the block
155  for ( ; cur != begin; ++cur)
156  ++(*in);
157  }
158  }
159 
160  vector_iterator2stream(const Self_ & a) : current_(a.current_), end_(a.end_), in(a.in) { }
161 
163  const value_type & operator * () const
164  {
165  return **in;
166  }
167 
168  const value_type * operator -> () const
169  {
170  return &(**in);
171  }
172 
175  {
176  assert(end_ != current_);
177  ++current_;
178  ++(*in);
179  if (empty())
180  delete_stream();
181 
182  return *this;
183  }
184 
186  bool empty() const
187  {
188  return (current_ == end_);
189  }
190  virtual ~vector_iterator2stream()
191  {
192  delete_stream(); // not needed actually
193  }
194  };
195 
203 
204  template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
205  unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
206  vector_iterator2stream<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> >
208  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> begin,
209  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> end,
210  unsigned_type nbuffers = 0)
211  {
212  STXXL_VERBOSE1("streamify for vector_iterator range is called");
214  (begin, end, nbuffers);
215  }
216 
217  template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
218  unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
219  struct streamify_traits<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> >
220  {
221  typedef vector_iterator2stream<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stream_type;
222  };
223 
231 
232  template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
233  unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
234  vector_iterator2stream<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> >
236  stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> begin,
237  stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> end,
238  unsigned_type nbuffers = 0)
239  {
240  STXXL_VERBOSE1("streamify for const_vector_iterator range is called");
242  (begin, end, nbuffers);
243  }
244 
245  template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
246  unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
247  struct streamify_traits<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> >
248  {
249  typedef vector_iterator2stream<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stream_type;
250  };
251 
252 
259  template <class InputIterator_>
261  {
264 
265  typedef typename InputIterator_::block_type block_type;
266 
267  public:
269 
271  typedef typename std::iterator_traits<InputIterator_>::value_type value_type;
272 
273  vector_iterator2stream_sr(InputIterator_ begin, InputIterator_ end, unsigned_type nbuffers = 0)
274  {
275  if (end - begin < block_type::size)
276  {
277  STXXL_VERBOSE1("vector_iterator2stream_sr::vector_iterator2stream_sr: Choosing iterator2stream<InputIterator_>");
278  it_stream = new iterator2stream<InputIterator_>(begin, end);
279  vec_it_stream = NULL;
280  }
281  else
282  {
283  STXXL_VERBOSE1("vector_iterator2stream_sr::vector_iterator2stream_sr: Choosing vector_iterator2stream<InputIterator_>");
284  it_stream = NULL;
285  vec_it_stream = new vector_iterator2stream<InputIterator_>(begin, end, nbuffers);
286  }
287  }
288 
289  vector_iterator2stream_sr(const Self_ & a) : vec_it_stream(a.vec_it_stream), it_stream(a.it_stream) { }
290 
292  const value_type & operator * () const
293  {
294  if (it_stream)
295  return **it_stream;
296 
297  return **vec_it_stream;
298  }
299 
300  const value_type * operator -> () const
301  {
302  if (it_stream)
303  return &(**it_stream);
304 
305  return &(**vec_it_stream);
306  }
307 
310  {
311  if (it_stream)
312  ++(*it_stream);
313 
314  else
315  ++(*vec_it_stream);
316 
317 
318  return *this;
319  }
320 
322  bool empty() const
323  {
324  if (it_stream)
325  return it_stream->empty();
326 
327  return vec_it_stream->empty();
328  }
329  virtual ~vector_iterator2stream_sr()
330  {
331  if (it_stream)
332  delete it_stream;
333 
334  else
335  delete vec_it_stream;
336  }
337  };
338 
340  template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
341  unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
342  vector_iterator2stream_sr<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> >
344  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> begin,
345  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> end,
346  unsigned_type nbuffers = 0)
347  {
348  STXXL_VERBOSE1("streamify_sr for vector_iterator range is called");
350  (begin, end, nbuffers);
351  }
352 
354  template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
355  unsigned BlkSize_, typename PgTp_, unsigned PgSz_>
356  vector_iterator2stream_sr<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> >
358  stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> begin,
359  stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> end,
360  unsigned_type nbuffers = 0)
361  {
362  STXXL_VERBOSE1("streamify_sr for const_vector_iterator range is called");
364  (begin, end, nbuffers);
365  }
366 
373  template <class OutputIterator_, class StreamAlgorithm_>
374  OutputIterator_ materialize(StreamAlgorithm_ & in, OutputIterator_ out)
375  {
376  while (!in.empty())
377  {
378  *out = *in;
379  ++out;
380  ++in;
381  }
382  return out;
383  }
384 
385 
395  template <class OutputIterator_, class StreamAlgorithm_>
396  OutputIterator_ materialize(StreamAlgorithm_ & in, OutputIterator_ outbegin, OutputIterator_ outend)
397  {
398  while ((!in.empty()) && outend != outbegin)
399  {
400  *outbegin = *in;
401  ++outbegin;
402  ++in;
403  }
404  return outbegin;
405  }
406 
407 
419  template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
420  unsigned BlkSize_, typename PgTp_, unsigned PgSz_, class StreamAlgorithm_>
421  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>
422  materialize(StreamAlgorithm_ & in,
423  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> outbegin,
424  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> outend,
425  unsigned_type nbuffers = 0)
426  {
427  typedef stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> ExtIterator;
428  typedef stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> ConstExtIterator;
430 
431 
432  while (outbegin.block_offset()) // go to the beginning of the block
433  // of the external vector
434  {
435  if (in.empty() || outbegin == outend)
436  return outbegin;
437 
438  *outbegin = *in;
439  ++outbegin;
440  ++in;
441  }
442 
443  if (nbuffers == 0)
444  nbuffers = 2 * config::get_instance()->disks_number();
445 
446 
447  outbegin.flush(); // flush container
448 
449  // create buffered write stream for blocks
450  buf_ostream_type outstream(outbegin.bid(), nbuffers);
451 
452  assert(outbegin.block_offset() == 0);
453 
454  while (!in.empty() && outend != outbegin)
455  {
456  if (outbegin.block_offset() == 0)
457  outbegin.touch();
458 
459  *outstream = *in;
460  ++outbegin;
461  ++outstream;
462  ++in;
463  }
464 
465  ConstExtIterator const_out = outbegin;
466 
467  while (const_out.block_offset()) // filling the rest of the block
468  {
469  *outstream = *const_out;
470  ++const_out;
471  ++outstream;
472  }
473  outbegin.flush();
474 
475  return outbegin;
476  }
477 
478 
487  template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_,
488  unsigned BlkSize_, typename PgTp_, unsigned PgSz_, class StreamAlgorithm_>
489  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_>
490  materialize(StreamAlgorithm_ & in,
491  stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> out,
492  unsigned_type nbuffers = 0)
493  {
494  typedef stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> ExtIterator;
495  typedef stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> ConstExtIterator;
497 
498  // on the I/O complexity of "materialize":
499  // crossing block boundary causes O(1) I/Os
500  // if you stay in a block, then materialize function accesses only the cache of the
501  // vector (only one block indeed), amortized complexity should apply here
502 
503  while (out.block_offset()) // go to the beginning of the block
504  // of the external vector
505  {
506  if (in.empty())
507  return out;
508 
509  *out = *in;
510  ++out;
511  ++in;
512  }
513 
514  if (nbuffers == 0)
515  nbuffers = 2 * config::get_instance()->disks_number();
516 
517 
518  out.flush(); // flush container
519 
520  // create buffered write stream for blocks
521  buf_ostream_type outstream(out.bid(), nbuffers);
522 
523  assert(out.block_offset() == 0);
524 
525  while (!in.empty())
526  {
527  if (out.block_offset() == 0)
528  out.touch();
529  // tells the vector that the block was modified
530  *outstream = *in;
531  ++out;
532  ++outstream;
533  ++in;
534  }
535 
536  ConstExtIterator const_out = out;
537 
538  while (const_out.block_offset())
539  {
540  *outstream = *const_out; // might cause I/Os for loading the page that
541  ++const_out; // contains data beyond out
542  ++outstream;
543  }
544  out.flush();
545 
546  return out;
547  }
548 
549 
553  template <class Generator_>
555  {
556  public:
558  typedef typename Generator_::value_type value_type;
559 
560  private:
561  Generator_ gen_;
562  value_type current_;
563 
564  public:
565  generator2stream(Generator_ g) :
566  gen_(g), current_(gen_()) { }
567 
568  generator2stream(const generator2stream & a) : gen_(a.gen_), current_(a.current_) { }
569 
571  const value_type & operator * () const
572  {
573  return current_;
574  }
575 
576  const value_type * operator -> () const
577  {
578  return &current_;
579  }
580 
583  {
584  current_ = gen_();
585  return *this;
586  }
587 
589  bool empty() const
590  {
591  return false;
592  }
593  };
594 
598  template <class Generator_>
600  {
601  return generator2stream<Generator_>(gen_);
602  }
603 
604  struct Stopper { };
605 
617  template <class Operation_, class Input1_,
618  class Input2_ = Stopper,
619  class Input3_ = Stopper,
620  class Input4_ = Stopper,
621  class Input5_ = Stopper,
622  class Input6_ = Stopper
623  >
624  class transform
625  {
626  Operation_ op;
627  Input1_ & i1;
628  Input2_ & i2;
629  Input3_ & i3;
630  Input4_ & i4;
631  Input5_ & i5;
632  Input6_ & i6;
633 
634  public:
636  typedef typename Operation_::value_type value_type;
637 
638  private:
639  value_type current;
640 
641  public:
643  transform(Operation_ o, Input1_ & i1_, Input2_ & i2_, Input3_ & i3_, Input4_ & i4_,
644  Input5_ & i5_, Input5_ & i6_) :
645  op(o), i1(i1_), i2(i2_), i3(i3_), i4(i4_), i5(i5_), i6(i6_),
646  current(op(*i1, *i2, *i3, *i4, *i5, *i6)) { }
647 
649  const value_type & operator * () const
650  {
651  return current;
652  }
653 
654  const value_type * operator -> () const
655  {
656  return &current;
657  }
658 
661  {
662  ++i1;
663  ++i2;
664  ++i3;
665  ++i4;
666  ++i5;
667  ++i6;
668 
669  if (!empty())
670  current = op(*i1, *i2, *i3, *i4, *i5, *i6);
671 
672 
673  return *this;
674  }
675 
677  bool empty() const
678  {
679  return i1.empty() || i2.empty() || i3.empty() ||
680  i4.empty() || i5.empty() || i6.empty();
681  }
682  };
683 
684  // Specializations
685 
693  template <class Operation_, class Input1_>
694  class transform<Operation_, Input1_, Stopper, Stopper, Stopper, Stopper, Stopper>
695  {
696  Operation_ op;
697  Input1_ & i1;
698 
699  public:
701  typedef typename Operation_::value_type value_type;
702 
703  private:
704  value_type current;
705 
706  public:
708  transform(Operation_ o, Input1_ & i1_) : op(o), i1(i1_),
709  current(op(*i1)) { }
710 
712  const value_type & operator * () const
713  {
714  return current;
715  }
716 
717  const value_type * operator -> () const
718  {
719  return &current;
720  }
721 
724  {
725  ++i1;
726  if (!empty())
727  current = op(*i1);
728 
729 
730  return *this;
731  }
732 
734  bool empty() const
735  {
736  return i1.empty();
737  }
738  };
739 
740 
749  template <class Operation_, class Input1_,
750  class Input2_
751  >
752  class transform<Operation_, Input1_, Input2_, Stopper, Stopper, Stopper, Stopper>
753  {
754  Operation_ op;
755  Input1_ & i1;
756  Input2_ & i2;
757 
758  public:
760  typedef typename Operation_::value_type value_type;
761 
762  private:
763  value_type current;
764 
765  public:
767  transform(Operation_ o, Input1_ & i1_, Input2_ & i2_) : op(o), i1(i1_), i2(i2_),
768  current(op(*i1, *i2)) { }
769 
771  const value_type & operator * () const
772  {
773  return current;
774  }
775 
776  const value_type * operator -> () const
777  {
778  return &current;
779  }
780 
783  {
784  ++i1;
785  ++i2;
786  if (!empty())
787  current = op(*i1, *i2);
788 
789 
790  return *this;
791  }
792 
794  bool empty() const
795  {
796  return i1.empty() || i2.empty();
797  }
798  };
799 
800 
810  template <class Operation_, class Input1_,
811  class Input2_,
812  class Input3_
813  >
814  class transform<Operation_, Input1_, Input2_, Input3_, Stopper, Stopper, Stopper>
815  {
816  Operation_ op;
817  Input1_ & i1;
818  Input2_ & i2;
819  Input3_ & i3;
820 
821  public:
823  typedef typename Operation_::value_type value_type;
824 
825  private:
826  value_type current;
827 
828  public:
830  transform(Operation_ o, Input1_ & i1_, Input2_ & i2_, Input3_ & i3_) :
831  op(o), i1(i1_), i2(i2_), i3(i3_),
832  current(op(*i1, *i2, *i3)) { }
833 
835  const value_type & operator * () const
836  {
837  return current;
838  }
839 
840  const value_type * operator -> () const
841  {
842  return &current;
843  }
844 
847  {
848  ++i1;
849  ++i2;
850  ++i3;
851  if (!empty())
852  current = op(*i1, *i2, *i3);
853 
854 
855  return *this;
856  }
857 
859  bool empty() const
860  {
861  return i1.empty() || i2.empty() || i3.empty();
862  }
863  };
864 
865 
876  template <class Operation_, class Input1_,
877  class Input2_,
878  class Input3_,
879  class Input4_
880  >
881  class transform<Operation_, Input1_, Input2_, Input3_, Input4_, Stopper, Stopper>
882  {
883  Operation_ op;
884  Input1_ & i1;
885  Input2_ & i2;
886  Input3_ & i3;
887  Input4_ & i4;
888 
889  public:
891  typedef typename Operation_::value_type value_type;
892 
893  private:
894  value_type current;
895 
896  public:
898  transform(Operation_ o, Input1_ & i1_, Input2_ & i2_, Input3_ & i3_, Input4_ & i4_) :
899  op(o), i1(i1_), i2(i2_), i3(i3_), i4(i4_),
900  current(op(*i1, *i2, *i3, *i4)) { }
901 
903  const value_type & operator * () const
904  {
905  return current;
906  }
907 
908  const value_type * operator -> () const
909  {
910  return &current;
911  }
912 
915  {
916  ++i1;
917  ++i2;
918  ++i3;
919  ++i4;
920  if (!empty())
921  current = op(*i1, *i2, *i3, *i4);
922 
923 
924  return *this;
925  }
926 
928  bool empty() const
929  {
930  return i1.empty() || i2.empty() || i3.empty() || i4.empty();
931  }
932  };
933 
934 
946  template <class Operation_, class Input1_,
947  class Input2_,
948  class Input3_,
949  class Input4_,
950  class Input5_
951  >
952  class transform<Operation_, Input1_, Input2_, Input3_, Input4_, Input5_, Stopper>
953  {
954  Operation_ op;
955  Input1_ & i1;
956  Input2_ & i2;
957  Input3_ & i3;
958  Input4_ & i4;
959  Input5_ & i5;
960 
961  public:
963  typedef typename Operation_::value_type value_type;
964 
965  private:
966  value_type current;
967 
968  public:
970  transform(Operation_ o, Input1_ & i1_, Input2_ & i2_, Input3_ & i3_, Input4_ & i4_,
971  Input5_ & i5_) :
972  op(o), i1(i1_), i2(i2_), i3(i3_), i4(i4_), i5(i5_),
973  current(op(*i1, *i2, *i3, *i4, *i5)) { }
974 
976  const value_type & operator * () const
977  {
978  return current;
979  }
980 
981  const value_type * operator -> () const
982  {
983  return &current;
984  }
985 
988  {
989  ++i1;
990  ++i2;
991  ++i3;
992  ++i4;
993  ++i5;
994  if (!empty())
995  current = op(*i1, *i2, *i3, *i4, *i5);
996 
997 
998  return *this;
999  }
1000 
1002  bool empty() const
1003  {
1004  return i1.empty() || i2.empty() || i3.empty() || i4.empty() || i5.empty();
1005  }
1006  };
1007 
1008 
1018  template <class Input1_,
1019  class Input2_,
1020  class Input3_ = Stopper,
1021  class Input4_ = Stopper,
1022  class Input5_ = Stopper,
1023  class Input6_ = Stopper
1024  >
1026  {
1027  Input1_ & i1;
1028  Input2_ & i2;
1029  Input3_ & i3;
1030  Input4_ & i4;
1031  Input5_ & i5;
1032  Input6_ & i6;
1033 
1034  public:
1036  typedef typename stxxl::tuple<
1037  typename Input1_::value_type,
1038  typename Input2_::value_type,
1039  typename Input3_::value_type,
1040  typename Input4_::value_type,
1041  typename Input5_::value_type,
1042  typename Input6_::value_type
1044 
1045  private:
1046  value_type current;
1047 
1048  public:
1051  Input1_ & i1_,
1052  Input2_ & i2_,
1053  Input3_ & i3_,
1054  Input4_ & i4_,
1055  Input5_ & i5_,
1056  Input6_ & i6_
1057  ) :
1058  i1(i1_), i2(i2_), i3(i3_), i4(i4_), i5(i5_), i6(i6_),
1059  current(value_type(*i1, *i2, *i3, *i4, *i5, *i6)) { }
1060 
1062  const value_type & operator * () const
1063  {
1064  return current;
1065  }
1066 
1067  const value_type * operator -> () const
1068  {
1069  return &current;
1070  }
1071 
1074  {
1075  ++i1;
1076  ++i2;
1077  ++i3;
1078  ++i4;
1079  ++i5;
1080  ++i6;
1081 
1082  if (!empty())
1083  current = value_type(*i1, *i2, *i3, *i4, *i5, *i6);
1084 
1085 
1086  return *this;
1087  }
1088 
1090  bool empty() const
1091  {
1092  return i1.empty() || i2.empty() || i3.empty() ||
1093  i4.empty() || i5.empty() || i6.empty();
1094  }
1095  };
1096 
1097 
1104  template <class Input1_, class Input2_>
1105  class make_tuple<Input1_, Input2_, Stopper, Stopper, Stopper, Stopper>
1106  {
1107  Input1_ & i1;
1108  Input2_ & i2;
1109 
1110  public:
1112  typedef typename stxxl::tuple<
1113  typename Input1_::value_type,
1114  typename Input2_::value_type
1116 
1117  private:
1118  value_type current;
1119 
1120  public:
1123  Input1_ & i1_,
1124  Input2_ & i2_
1125  ) :
1126  i1(i1_), i2(i2_)
1127  {
1128  if (!empty())
1129  {
1130  current = value_type(*i1, *i2);
1131  }
1132  }
1133 
1135  const value_type & operator * () const
1136  {
1137  return current;
1138  }
1139 
1140  const value_type * operator -> () const
1141  {
1142  return &current;
1143  }
1144 
1147  {
1148  ++i1;
1149  ++i2;
1150 
1151  if (!empty())
1152  current = value_type(*i1, *i2);
1153 
1154 
1155  return *this;
1156  }
1157 
1159  bool empty() const
1160  {
1161  return i1.empty() || i2.empty();
1162  }
1163  };
1164 
1172  template <class Input1_, class Input2_, class Input3_>
1173  class make_tuple<Input1_, Input2_, Input3_, Stopper, Stopper, Stopper>
1174  {
1175  Input1_ & i1;
1176  Input2_ & i2;
1177  Input3_ & i3;
1178 
1179  public:
1181  typedef typename stxxl::tuple<
1182  typename Input1_::value_type,
1183  typename Input2_::value_type,
1184  typename Input3_::value_type
1186 
1187  private:
1188  value_type current;
1189 
1190  public:
1193  Input1_ & i1_,
1194  Input2_ & i2_,
1195  Input3_ & i3_
1196  ) :
1197  i1(i1_), i2(i2_), i3(i3_),
1198  current(value_type(*i1, *i2, *i3)) { }
1199 
1201  const value_type & operator * () const
1202  {
1203  return current;
1204  }
1205 
1206  const value_type * operator -> () const
1207  {
1208  return &current;
1209  }
1210 
1213  {
1214  ++i1;
1215  ++i2;
1216  ++i3;
1217 
1218  if (!empty())
1219  current = value_type(*i1, *i2, *i3);
1220 
1221 
1222  return *this;
1223  }
1224 
1226  bool empty() const
1227  {
1228  return i1.empty() || i2.empty() || i3.empty();
1229  }
1230  };
1231 
1240  template <class Input1_,
1241  class Input2_,
1242  class Input3_,
1243  class Input4_
1244  >
1245  class make_tuple<Input1_, Input2_, Input3_, Input4_, Stopper, Stopper>
1246  {
1247  Input1_ & i1;
1248  Input2_ & i2;
1249  Input3_ & i3;
1250  Input4_ & i4;
1251 
1252  public:
1254  typedef typename stxxl::tuple<
1255  typename Input1_::value_type,
1256  typename Input2_::value_type,
1257  typename Input3_::value_type,
1258  typename Input4_::value_type
1260 
1261  private:
1262  value_type current;
1263 
1264  public:
1267  Input1_ & i1_,
1268  Input2_ & i2_,
1269  Input3_ & i3_,
1270  Input4_ & i4_
1271  ) :
1272  i1(i1_), i2(i2_), i3(i3_), i4(i4_),
1273  current(value_type(*i1, *i2, *i3, *i4)) { }
1274 
1276  const value_type & operator * () const
1277  {
1278  return current;
1279  }
1280 
1281  const value_type * operator -> () const
1282  {
1283  return &current;
1284  }
1285 
1288  {
1289  ++i1;
1290  ++i2;
1291  ++i3;
1292  ++i4;
1293 
1294  if (!empty())
1295  current = value_type(*i1, *i2, *i3, *i4);
1296 
1297 
1298  return *this;
1299  }
1300 
1302  bool empty() const
1303  {
1304  return i1.empty() || i2.empty() || i3.empty() ||
1305  i4.empty();
1306  }
1307  };
1308 
1318  template <
1319  class Input1_,
1320  class Input2_,
1321  class Input3_,
1322  class Input4_,
1323  class Input5_
1324  >
1325  class make_tuple<Input1_, Input2_, Input3_, Input4_, Input5_, Stopper>
1326  {
1327  Input1_ & i1;
1328  Input2_ & i2;
1329  Input3_ & i3;
1330  Input4_ & i4;
1331  Input5_ & i5;
1332 
1333  public:
1335  typedef typename stxxl::tuple<
1336  typename Input1_::value_type,
1337  typename Input2_::value_type,
1338  typename Input3_::value_type,
1339  typename Input4_::value_type,
1340  typename Input5_::value_type
1342 
1343  private:
1344  value_type current;
1345 
1346  public:
1349  Input1_ & i1_,
1350  Input2_ & i2_,
1351  Input3_ & i3_,
1352  Input4_ & i4_,
1353  Input5_ & i5_
1354  ) :
1355  i1(i1_), i2(i2_), i3(i3_), i4(i4_), i5(i5_),
1356  current(value_type(*i1, *i2, *i3, *i4, *i5)) { }
1357 
1359  const value_type & operator * () const
1360  {
1361  return current;
1362  }
1363 
1364  const value_type * operator -> () const
1365  {
1366  return &current;
1367  }
1368 
1371  {
1372  ++i1;
1373  ++i2;
1374  ++i3;
1375  ++i4;
1376  ++i5;
1377 
1378  if (!empty())
1379  current = value_type(*i1, *i2, *i3, *i4, *i5);
1380 
1381 
1382  return *this;
1383  }
1384 
1386  bool empty() const
1387  {
1388  return i1.empty() || i2.empty() || i3.empty() ||
1389  i4.empty() || i5.empty();
1390  }
1391  };
1392 
1393 
1394  template <class Input_, int Which>
1395  class choose
1396  { };
1397 
1404  template <class Input_>
1405  class choose<Input_, 1>
1406  {
1407  Input_ & in;
1408 
1409  typedef typename Input_::value_type tuple_type;
1410 
1411  public:
1413  typedef typename tuple_type::first_type value_type;
1414 
1415  private:
1416  value_type current;
1417 
1418  public:
1420  choose(Input_ & in_) :
1421  in(in_),
1422  current((*in_).first) { }
1423 
1425  const value_type & operator * () const
1426  {
1427  return current;
1428  }
1429 
1430  const value_type * operator -> () const
1431  {
1432  return &current;
1433  }
1434 
1436  choose & operator ++ ()
1437  {
1438  ++in;
1439 
1440  if (!empty())
1441  current = (*in).first;
1442 
1443 
1444  return *this;
1445  }
1446 
1448  bool empty() const
1449  {
1450  return in.empty();
1451  }
1452  };
1453 
1460  template <class Input_>
1461  class choose<Input_, 2>
1462  {
1463  Input_ & in;
1464 
1465  typedef typename Input_::value_type tuple_type;
1466 
1467  public:
1469  typedef typename tuple_type::second_type value_type;
1470 
1471  private:
1472  value_type current;
1473 
1474  public:
1476  choose(Input_ & in_) :
1477  in(in_),
1478  current((*in_).second) { }
1479 
1481  const value_type & operator * () const
1482  {
1483  return current;
1484  }
1485 
1486  const value_type * operator -> () const
1487  {
1488  return &current;
1489  }
1490 
1492  choose & operator ++ ()
1493  {
1494  ++in;
1495 
1496  if (!empty())
1497  current = (*in).second;
1498 
1499 
1500  return *this;
1501  }
1502 
1504  bool empty() const
1505  {
1506  return in.empty();
1507  }
1508  };
1509 
1516  template <class Input_>
1517  class choose<Input_, 3>
1518  {
1519  Input_ & in;
1520 
1521  typedef typename Input_::value_type tuple_type;
1522 
1523  public:
1525  typedef typename tuple_type::third_type value_type;
1526 
1527  private:
1528  value_type current;
1529 
1530  public:
1532  choose(Input_ & in_) :
1533  in(in_),
1534  current((*in_).third) { }
1535 
1537  const value_type & operator * () const
1538  {
1539  return current;
1540  }
1541 
1542  const value_type * operator -> () const
1543  {
1544  return &current;
1545  }
1546 
1548  choose & operator ++ ()
1549  {
1550  ++in;
1551 
1552  if (!empty())
1553  current = (*in).third;
1554 
1555 
1556  return *this;
1557  }
1558 
1560  bool empty() const
1561  {
1562  return in.empty();
1563  }
1564  };
1565 
1572  template <class Input_>
1573  class choose<Input_, 4>
1574  {
1575  Input_ & in;
1576 
1577  typedef typename Input_::value_type tuple_type;
1578 
1579  public:
1581  typedef typename tuple_type::fourth_type value_type;
1582 
1583  private:
1584  value_type current;
1585 
1586  public:
1588  choose(Input_ & in_) :
1589  in(in_),
1590  current((*in_).fourth) { }
1591 
1593  const value_type & operator * () const
1594  {
1595  return current;
1596  }
1597 
1598  const value_type * operator -> () const
1599  {
1600  return &current;
1601  }
1602 
1604  choose & operator ++ ()
1605  {
1606  ++in;
1607 
1608  if (!empty())
1609  current = (*in).fourth;
1610 
1611 
1612  return *this;
1613  }
1614 
1616  bool empty() const
1617  {
1618  return in.empty();
1619  }
1620  };
1621 
1628  template <class Input_>
1629  class choose<Input_, 5>
1630  {
1631  Input_ & in;
1632 
1633  typedef typename Input_::value_type tuple_type;
1634 
1635  public:
1637  typedef typename tuple_type::fifth_type value_type;
1638 
1639  private:
1640  value_type current;
1641 
1642  public:
1644  choose(Input_ & in_) :
1645  in(in_),
1646  current((*in_).fifth) { }
1647 
1649  const value_type & operator * () const
1650  {
1651  return current;
1652  }
1653 
1654  const value_type * operator -> () const
1655  {
1656  return &current;
1657  }
1658 
1660  choose & operator ++ ()
1661  {
1662  ++in;
1663 
1664  if (!empty())
1665  current = (*in).fifth;
1666 
1667 
1668  return *this;
1669  }
1670 
1672  bool empty() const
1673  {
1674  return in.empty();
1675  }
1676  };
1677 
1684  template <class Input_>
1685  class choose<Input_, 6>
1686  {
1687  Input_ & in;
1688 
1689  typedef typename Input_::value_type tuple_type;
1690 
1691  public:
1693  typedef typename tuple_type::sixth_type value_type;
1694 
1695  private:
1696  value_type current;
1697 
1698  public:
1700  choose(Input_ & in_) :
1701  in(in_),
1702  current((*in_).sixth) { }
1703 
1705  const value_type & operator * () const
1706  {
1707  return current;
1708  }
1709 
1710  const value_type * operator -> () const
1711  {
1712  return &current;
1713  }
1714 
1716  choose & operator ++ ()
1717  {
1718  ++in;
1719 
1720  if (!empty())
1721  current = (*in).sixth;
1722 
1723 
1724  return *this;
1725  }
1726 
1728  bool empty() const
1729  {
1730  return in.empty();
1731  }
1732  };
1733 
1738  template <class Input, class BinaryPredicate = Stopper>
1739  class unique
1740  {
1741  Input & input;
1742  BinaryPredicate binary_pred;
1743  typename Input::value_type current;
1744 
1745  public:
1746  typedef typename Input::value_type value_type;
1747  unique(Input & input_, BinaryPredicate binary_pred_) : input(input_), binary_pred(binary_pred_)
1748  {
1749  if (!input.empty())
1750  current = *input;
1751  }
1752 
1755  {
1756  value_type old_value = current;
1757  ++input;
1758  while (!input.empty() && (binary_pred(current = *input, old_value)))
1759  ++input;
1760  }
1762  const value_type operator * () const { return current; }
1764  const value_type * operator -> () const
1765  {
1766  return &current;
1767  }
1768 
1770  bool empty() const { return input.empty(); }
1771  };
1772 
1776  template <class Input>
1777  class unique<Input, Stopper>
1778  {
1779  Input & input;
1780  typename Input::value_type current;
1781 
1782  public:
1783  typedef typename Input::value_type value_type;
1784  unique(Input & input_) : input(input_)
1785  {
1786  if (!input.empty())
1787  current = *input;
1788  }
1791  {
1792  value_type old_value = current;
1793  ++input;
1794  while (!input.empty() && ((current = *input) == old_value))
1795  ++input;
1796  }
1798  value_type operator * () const { return current; }
1799 
1801  const value_type * operator -> () const
1802  {
1803  return &current;
1804  }
1805 
1807  bool empty() const { return input.empty(); }
1808  };
1809 
1810 
1812 }
1813 
1814 __STXXL_END_NAMESPACE
1815 
1816 #endif // !STXXL_STREAM_HEADER