Stxxl 1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/stream/stream.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2003-2005 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 00011 **************************************************************************/ 00012 00013 #ifndef STXXL_STREAM_HEADER 00014 #define STXXL_STREAM_HEADER 00015 00016 #include <stxxl/bits/namespace.h> 00017 #include <stxxl/bits/mng/buf_istream.h> 00018 #include <stxxl/bits/mng/buf_ostream.h> 00019 #include <stxxl/bits/common/tuple.h> 00020 #include <stxxl/vector> 00021 #include <stxxl/bits/compat_auto_ptr.h> 00022 00023 00024 __STXXL_BEGIN_NAMESPACE 00025 00027 namespace stream 00028 { 00053 00057 template <class InputIterator_> 00058 class iterator2stream 00059 { 00060 InputIterator_ current_, end_; 00061 00062 public: 00064 typedef typename std::iterator_traits<InputIterator_>::value_type value_type; 00065 00066 iterator2stream(InputIterator_ begin, InputIterator_ end) : 00067 current_(begin), end_(end) { } 00068 00069 iterator2stream(const iterator2stream & a) : current_(a.current_), end_(a.end_) { } 00070 00072 const value_type & operator * () const 00073 { 00074 return *current_; 00075 } 00076 00077 const value_type * operator -> () const 00078 { 00079 return &(*current_); 00080 } 00081 00083 iterator2stream & operator ++ () 00084 { 00085 assert(end_ != current_); 00086 ++current_; 00087 return *this; 00088 } 00089 00091 bool empty() const 00092 { 00093 return (current_ == end_); 00094 } 00095 }; 00096 00097 00102 template <class InputIterator_> 00103 iterator2stream<InputIterator_> streamify(InputIterator_ begin, InputIterator_ end) 00104 { 00105 return iterator2stream<InputIterator_>(begin, end); 00106 } 00107 00109 template <class InputIterator_> 00110 struct streamify_traits 00111 { 00113 typedef iterator2stream<InputIterator_> stream_type; 00114 }; 00115 00120 template <class InputIterator_> 00121 class vector_iterator2stream 00122 { 00123 InputIterator_ current_, end_; 00124 typedef buf_istream<typename InputIterator_::block_type, 00125 typename InputIterator_::bids_container_iterator> buf_istream_type; 00126 00127 typedef typename stxxl::compat_auto_ptr<buf_istream_type>::result auto_ptr_type; 00128 mutable auto_ptr_type in; 00129 00130 void delete_stream() 00131 { 00132 in.reset(); 00133 } 00134 00135 public: 00136 typedef vector_iterator2stream<InputIterator_> Self_; 00137 00139 typedef typename std::iterator_traits<InputIterator_>::value_type value_type; 00140 00141 vector_iterator2stream(InputIterator_ begin, InputIterator_ end, unsigned_type nbuffers = 0) : 00142 current_(begin), end_(end) 00143 { 00144 begin.flush(); // flush container 00145 typename InputIterator_::bids_container_iterator end_iter = end.bid() + ((end.block_offset()) ? 1 : 0); 00146 00147 if (end_iter - begin.bid() > 0) 00148 { 00149 in.reset(new buf_istream_type(begin.bid(), end_iter, nbuffers ? nbuffers : 00150 (2 * config::get_instance()->disks_number()))); 00151 00152 InputIterator_ cur = begin - begin.block_offset(); 00153 00154 // skip the beginning of the block 00155 for ( ; cur != begin; ++cur) 00156 ++(*in); 00157 } 00158 } 00159 00160 vector_iterator2stream(const Self_ & a) : current_(a.current_), end_(a.end_), in(a.in) { } 00161 00163 const value_type & operator * () const 00164 { 00165 return **in; 00166 } 00167 00168 const value_type * operator -> () const 00169 { 00170 return &(**in); 00171 } 00172 00174 Self_ & operator ++ () 00175 { 00176 assert(end_ != current_); 00177 ++current_; 00178 ++(*in); 00179 if (empty()) 00180 delete_stream(); 00181 00182 return *this; 00183 } 00184 00186 bool empty() const 00187 { 00188 return (current_ == end_); 00189 } 00190 virtual ~vector_iterator2stream() 00191 { 00192 delete_stream(); // not needed actually 00193 } 00194 }; 00195 00203 00204 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00205 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 00206 vector_iterator2stream<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > 00207 streamify( 00208 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> begin, 00209 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> end, 00210 unsigned_type nbuffers = 0) 00211 { 00212 STXXL_VERBOSE1("streamify for vector_iterator range is called"); 00213 return vector_iterator2stream<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > 00214 (begin, end, nbuffers); 00215 } 00216 00217 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00218 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 00219 struct streamify_traits<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > 00220 { 00221 typedef vector_iterator2stream<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stream_type; 00222 }; 00223 00231 00232 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00233 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 00234 vector_iterator2stream<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > 00235 streamify( 00236 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> begin, 00237 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> end, 00238 unsigned_type nbuffers = 0) 00239 { 00240 STXXL_VERBOSE1("streamify for const_vector_iterator range is called"); 00241 return vector_iterator2stream<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > 00242 (begin, end, nbuffers); 00243 } 00244 00245 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00246 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 00247 struct streamify_traits<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > 00248 { 00249 typedef vector_iterator2stream<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > stream_type; 00250 }; 00251 00252 00259 template <class InputIterator_> 00260 class vector_iterator2stream_sr 00261 { 00262 vector_iterator2stream<InputIterator_> * vec_it_stream; 00263 iterator2stream<InputIterator_> * it_stream; 00264 00265 typedef typename InputIterator_::block_type block_type; 00266 00267 public: 00268 typedef vector_iterator2stream_sr<InputIterator_> Self_; 00269 00271 typedef typename std::iterator_traits<InputIterator_>::value_type value_type; 00272 00273 vector_iterator2stream_sr(InputIterator_ begin, InputIterator_ end, unsigned_type nbuffers = 0) 00274 { 00275 if (end - begin < block_type::size) 00276 { 00277 STXXL_VERBOSE1("vector_iterator2stream_sr::vector_iterator2stream_sr: Choosing iterator2stream<InputIterator_>"); 00278 it_stream = new iterator2stream<InputIterator_>(begin, end); 00279 vec_it_stream = NULL; 00280 } 00281 else 00282 { 00283 STXXL_VERBOSE1("vector_iterator2stream_sr::vector_iterator2stream_sr: Choosing vector_iterator2stream<InputIterator_>"); 00284 it_stream = NULL; 00285 vec_it_stream = new vector_iterator2stream<InputIterator_>(begin, end, nbuffers); 00286 } 00287 } 00288 00289 vector_iterator2stream_sr(const Self_ & a) : vec_it_stream(a.vec_it_stream), it_stream(a.it_stream) { } 00290 00292 const value_type & operator * () const 00293 { 00294 if (it_stream) 00295 return **it_stream; 00296 00297 return **vec_it_stream; 00298 } 00299 00300 const value_type * operator -> () const 00301 { 00302 if (it_stream) 00303 return &(**it_stream); 00304 00305 return &(**vec_it_stream); 00306 } 00307 00309 Self_ & operator ++ () 00310 { 00311 if (it_stream) 00312 ++(*it_stream); 00313 00314 else 00315 ++(*vec_it_stream); 00316 00317 00318 return *this; 00319 } 00320 00322 bool empty() const 00323 { 00324 if (it_stream) 00325 return it_stream->empty(); 00326 00327 return vec_it_stream->empty(); 00328 } 00329 virtual ~vector_iterator2stream_sr() 00330 { 00331 if (it_stream) 00332 delete it_stream; 00333 00334 else 00335 delete vec_it_stream; 00336 } 00337 }; 00338 00340 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00341 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 00342 vector_iterator2stream_sr<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > 00343 streamify_sr( 00344 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> begin, 00345 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> end, 00346 unsigned_type nbuffers = 0) 00347 { 00348 STXXL_VERBOSE1("streamify_sr for vector_iterator range is called"); 00349 return vector_iterator2stream_sr<stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > 00350 (begin, end, nbuffers); 00351 } 00352 00354 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00355 unsigned BlkSize_, typename PgTp_, unsigned PgSz_> 00356 vector_iterator2stream_sr<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > 00357 streamify_sr( 00358 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> begin, 00359 stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> end, 00360 unsigned_type nbuffers = 0) 00361 { 00362 STXXL_VERBOSE1("streamify_sr for const_vector_iterator range is called"); 00363 return vector_iterator2stream_sr<stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> > 00364 (begin, end, nbuffers); 00365 } 00366 00373 template <class OutputIterator_, class StreamAlgorithm_> 00374 OutputIterator_ materialize(StreamAlgorithm_ & in, OutputIterator_ out) 00375 { 00376 while (!in.empty()) 00377 { 00378 *out = *in; 00379 ++out; 00380 ++in; 00381 } 00382 return out; 00383 } 00384 00385 00395 template <class OutputIterator_, class StreamAlgorithm_> 00396 OutputIterator_ materialize(StreamAlgorithm_ & in, OutputIterator_ outbegin, OutputIterator_ outend) 00397 { 00398 while ((!in.empty()) && outend != outbegin) 00399 { 00400 *outbegin = *in; 00401 ++outbegin; 00402 ++in; 00403 } 00404 return outbegin; 00405 } 00406 00407 00419 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00420 unsigned BlkSize_, typename PgTp_, unsigned PgSz_, class StreamAlgorithm_> 00421 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> 00422 materialize(StreamAlgorithm_ & in, 00423 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> outbegin, 00424 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> outend, 00425 unsigned_type nbuffers = 0) 00426 { 00427 typedef stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> ExtIterator; 00428 typedef stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> ConstExtIterator; 00429 typedef buf_ostream<typename ExtIterator::block_type, typename ExtIterator::bids_container_iterator> buf_ostream_type; 00430 00431 00432 while (outbegin.block_offset()) // go to the beginning of the block 00433 // of the external vector 00434 { 00435 if (in.empty() || outbegin == outend) 00436 return outbegin; 00437 00438 *outbegin = *in; 00439 ++outbegin; 00440 ++in; 00441 } 00442 00443 if (nbuffers == 0) 00444 nbuffers = 2 * config::get_instance()->disks_number(); 00445 00446 00447 outbegin.flush(); // flush container 00448 00449 // create buffered write stream for blocks 00450 buf_ostream_type outstream(outbegin.bid(), nbuffers); 00451 00452 assert(outbegin.block_offset() == 0); 00453 00454 while (!in.empty() && outend != outbegin) 00455 { 00456 if (outbegin.block_offset() == 0) 00457 outbegin.touch(); 00458 00459 *outstream = *in; 00460 ++outbegin; 00461 ++outstream; 00462 ++in; 00463 } 00464 00465 ConstExtIterator const_out = outbegin; 00466 00467 while (const_out.block_offset()) // filling the rest of the block 00468 { 00469 *outstream = *const_out; 00470 ++const_out; 00471 ++outstream; 00472 } 00473 outbegin.flush(); 00474 00475 return outbegin; 00476 } 00477 00478 00487 template <typename Tp_, typename AllocStr_, typename SzTp_, typename DiffTp_, 00488 unsigned BlkSize_, typename PgTp_, unsigned PgSz_, class StreamAlgorithm_> 00489 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> 00490 materialize(StreamAlgorithm_ & in, 00491 stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> out, 00492 unsigned_type nbuffers = 0) 00493 { 00494 typedef stxxl::vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> ExtIterator; 00495 typedef stxxl::const_vector_iterator<Tp_, AllocStr_, SzTp_, DiffTp_, BlkSize_, PgTp_, PgSz_> ConstExtIterator; 00496 typedef buf_ostream<typename ExtIterator::block_type, typename ExtIterator::bids_container_iterator> buf_ostream_type; 00497 00498 // on the I/O complexity of "materialize": 00499 // crossing block boundary causes O(1) I/Os 00500 // if you stay in a block, then materialize function accesses only the cache of the 00501 // vector (only one block indeed), amortized complexity should apply here 00502 00503 while (out.block_offset()) // go to the beginning of the block 00504 // of the external vector 00505 { 00506 if (in.empty()) 00507 return out; 00508 00509 *out = *in; 00510 ++out; 00511 ++in; 00512 } 00513 00514 if (nbuffers == 0) 00515 nbuffers = 2 * config::get_instance()->disks_number(); 00516 00517 00518 out.flush(); // flush container 00519 00520 // create buffered write stream for blocks 00521 buf_ostream_type outstream(out.bid(), nbuffers); 00522 00523 assert(out.block_offset() == 0); 00524 00525 while (!in.empty()) 00526 { 00527 if (out.block_offset() == 0) 00528 out.touch(); 00529 // tells the vector that the block was modified 00530 *outstream = *in; 00531 ++out; 00532 ++outstream; 00533 ++in; 00534 } 00535 00536 ConstExtIterator const_out = out; 00537 00538 while (const_out.block_offset()) 00539 { 00540 *outstream = *const_out; // might cause I/Os for loading the page that 00541 ++const_out; // contains data beyond out 00542 ++outstream; 00543 } 00544 out.flush(); 00545 00546 return out; 00547 } 00548 00549 00553 template <class Generator_> 00554 class generator2stream 00555 { 00556 public: 00558 typedef typename Generator_::value_type value_type; 00559 00560 private: 00561 Generator_ gen_; 00562 value_type current_; 00563 00564 public: 00565 generator2stream(Generator_ g) : 00566 gen_(g), current_(gen_()) { } 00567 00568 generator2stream(const generator2stream & a) : gen_(a.gen_), current_(a.current_) { } 00569 00571 const value_type & operator * () const 00572 { 00573 return current_; 00574 } 00575 00576 const value_type * operator -> () const 00577 { 00578 return ¤t_; 00579 } 00580 00582 generator2stream & operator ++ () 00583 { 00584 current_ = gen_(); 00585 return *this; 00586 } 00587 00589 bool empty() const 00590 { 00591 return false; 00592 } 00593 }; 00594 00598 template <class Generator_> 00599 generator2stream<Generator_> streamify(Generator_ gen_) 00600 { 00601 return generator2stream<Generator_>(gen_); 00602 } 00603 00604 struct Stopper { }; 00605 00617 template <class Operation_, class Input1_, 00618 class Input2_ = Stopper, 00619 class Input3_ = Stopper, 00620 class Input4_ = Stopper, 00621 class Input5_ = Stopper, 00622 class Input6_ = Stopper 00623 > 00624 class transform 00625 { 00626 Operation_ op; 00627 Input1_ & i1; 00628 Input2_ & i2; 00629 Input3_ & i3; 00630 Input4_ & i4; 00631 Input5_ & i5; 00632 Input6_ & i6; 00633 00634 public: 00636 typedef typename Operation_::value_type value_type; 00637 00638 private: 00639 value_type current; 00640 00641 public: 00643 transform(Operation_ o, Input1_ & i1_, Input2_ & i2_, Input3_ & i3_, Input4_ & i4_, 00644 Input5_ & i5_, Input5_ & i6_) : 00645 op(o), i1(i1_), i2(i2_), i3(i3_), i4(i4_), i5(i5_), i6(i6_), 00646 current(op(*i1, *i2, *i3, *i4, *i5, *i6)) { } 00647 00649 const value_type & operator * () const 00650 { 00651 return current; 00652 } 00653 00654 const value_type * operator -> () const 00655 { 00656 return ¤t; 00657 } 00658 00660 transform & operator ++ () 00661 { 00662 ++i1; 00663 ++i2; 00664 ++i3; 00665 ++i4; 00666 ++i5; 00667 ++i6; 00668 00669 if (!empty()) 00670 current = op(*i1, *i2, *i3, *i4, *i5, *i6); 00671 00672 00673 return *this; 00674 } 00675 00677 bool empty() const 00678 { 00679 return i1.empty() || i2.empty() || i3.empty() || 00680 i4.empty() || i5.empty() || i6.empty(); 00681 } 00682 }; 00683 00684 // Specializations 00685 00693 template <class Operation_, class Input1_> 00694 class transform<Operation_, Input1_, Stopper, Stopper, Stopper, Stopper, Stopper> 00695 { 00696 Operation_ op; 00697 Input1_ & i1; 00698 00699 public: 00701 typedef typename Operation_::value_type value_type; 00702 00703 private: 00704 value_type current; 00705 00706 public: 00708 transform(Operation_ o, Input1_ & i1_) : op(o), i1(i1_), 00709 current(op(*i1)) { } 00710 00712 const value_type & operator * () const 00713 { 00714 return current; 00715 } 00716 00717 const value_type * operator -> () const 00718 { 00719 return ¤t; 00720 } 00721 00723 transform & operator ++ () 00724 { 00725 ++i1; 00726 if (!empty()) 00727 current = op(*i1); 00728 00729 00730 return *this; 00731 } 00732 00734 bool empty() const 00735 { 00736 return i1.empty(); 00737 } 00738 }; 00739 00740 00749 template <class Operation_, class Input1_, 00750 class Input2_ 00751 > 00752 class transform<Operation_, Input1_, Input2_, Stopper, Stopper, Stopper, Stopper> 00753 { 00754 Operation_ op; 00755 Input1_ & i1; 00756 Input2_ & i2; 00757 00758 public: 00760 typedef typename Operation_::value_type value_type; 00761 00762 private: 00763 value_type current; 00764 00765 public: 00767 transform(Operation_ o, Input1_ & i1_, Input2_ & i2_) : op(o), i1(i1_), i2(i2_), 00768 current(op(*i1, *i2)) { } 00769 00771 const value_type & operator * () const 00772 { 00773 return current; 00774 } 00775 00776 const value_type * operator -> () const 00777 { 00778 return ¤t; 00779 } 00780 00782 transform & operator ++ () 00783 { 00784 ++i1; 00785 ++i2; 00786 if (!empty()) 00787 current = op(*i1, *i2); 00788 00789 00790 return *this; 00791 } 00792 00794 bool empty() const 00795 { 00796 return i1.empty() || i2.empty(); 00797 } 00798 }; 00799 00800 00810 template <class Operation_, class Input1_, 00811 class Input2_, 00812 class Input3_ 00813 > 00814 class transform<Operation_, Input1_, Input2_, Input3_, Stopper, Stopper, Stopper> 00815 { 00816 Operation_ op; 00817 Input1_ & i1; 00818 Input2_ & i2; 00819 Input3_ & i3; 00820 00821 public: 00823 typedef typename Operation_::value_type value_type; 00824 00825 private: 00826 value_type current; 00827 00828 public: 00830 transform(Operation_ o, Input1_ & i1_, Input2_ & i2_, Input3_ & i3_) : 00831 op(o), i1(i1_), i2(i2_), i3(i3_), 00832 current(op(*i1, *i2, *i3)) { } 00833 00835 const value_type & operator * () const 00836 { 00837 return current; 00838 } 00839 00840 const value_type * operator -> () const 00841 { 00842 return ¤t; 00843 } 00844 00846 transform & operator ++ () 00847 { 00848 ++i1; 00849 ++i2; 00850 ++i3; 00851 if (!empty()) 00852 current = op(*i1, *i2, *i3); 00853 00854 00855 return *this; 00856 } 00857 00859 bool empty() const 00860 { 00861 return i1.empty() || i2.empty() || i3.empty(); 00862 } 00863 }; 00864 00865 00876 template <class Operation_, class Input1_, 00877 class Input2_, 00878 class Input3_, 00879 class Input4_ 00880 > 00881 class transform<Operation_, Input1_, Input2_, Input3_, Input4_, Stopper, Stopper> 00882 { 00883 Operation_ op; 00884 Input1_ & i1; 00885 Input2_ & i2; 00886 Input3_ & i3; 00887 Input4_ & i4; 00888 00889 public: 00891 typedef typename Operation_::value_type value_type; 00892 00893 private: 00894 value_type current; 00895 00896 public: 00898 transform(Operation_ o, Input1_ & i1_, Input2_ & i2_, Input3_ & i3_, Input4_ & i4_) : 00899 op(o), i1(i1_), i2(i2_), i3(i3_), i4(i4_), 00900 current(op(*i1, *i2, *i3, *i4)) { } 00901 00903 const value_type & operator * () const 00904 { 00905 return current; 00906 } 00907 00908 const value_type * operator -> () const 00909 { 00910 return ¤t; 00911 } 00912 00914 transform & operator ++ () 00915 { 00916 ++i1; 00917 ++i2; 00918 ++i3; 00919 ++i4; 00920 if (!empty()) 00921 current = op(*i1, *i2, *i3, *i4); 00922 00923 00924 return *this; 00925 } 00926 00928 bool empty() const 00929 { 00930 return i1.empty() || i2.empty() || i3.empty() || i4.empty(); 00931 } 00932 }; 00933 00934 00946 template <class Operation_, class Input1_, 00947 class Input2_, 00948 class Input3_, 00949 class Input4_, 00950 class Input5_ 00951 > 00952 class transform<Operation_, Input1_, Input2_, Input3_, Input4_, Input5_, Stopper> 00953 { 00954 Operation_ op; 00955 Input1_ & i1; 00956 Input2_ & i2; 00957 Input3_ & i3; 00958 Input4_ & i4; 00959 Input5_ & i5; 00960 00961 public: 00963 typedef typename Operation_::value_type value_type; 00964 00965 private: 00966 value_type current; 00967 00968 public: 00970 transform(Operation_ o, Input1_ & i1_, Input2_ & i2_, Input3_ & i3_, Input4_ & i4_, 00971 Input5_ & i5_) : 00972 op(o), i1(i1_), i2(i2_), i3(i3_), i4(i4_), i5(i5_), 00973 current(op(*i1, *i2, *i3, *i4, *i5)) { } 00974 00976 const value_type & operator * () const 00977 { 00978 return current; 00979 } 00980 00981 const value_type * operator -> () const 00982 { 00983 return ¤t; 00984 } 00985 00987 transform & operator ++ () 00988 { 00989 ++i1; 00990 ++i2; 00991 ++i3; 00992 ++i4; 00993 ++i5; 00994 if (!empty()) 00995 current = op(*i1, *i2, *i3, *i4, *i5); 00996 00997 00998 return *this; 00999 } 01000 01002 bool empty() const 01003 { 01004 return i1.empty() || i2.empty() || i3.empty() || i4.empty() || i5.empty(); 01005 } 01006 }; 01007 01008 01018 template <class Input1_, 01019 class Input2_, 01020 class Input3_ = Stopper, 01021 class Input4_ = Stopper, 01022 class Input5_ = Stopper, 01023 class Input6_ = Stopper 01024 > 01025 class make_tuple 01026 { 01027 Input1_ & i1; 01028 Input2_ & i2; 01029 Input3_ & i3; 01030 Input4_ & i4; 01031 Input5_ & i5; 01032 Input6_ & i6; 01033 01034 public: 01036 typedef typename stxxl::tuple< 01037 typename Input1_::value_type, 01038 typename Input2_::value_type, 01039 typename Input3_::value_type, 01040 typename Input4_::value_type, 01041 typename Input5_::value_type, 01042 typename Input6_::value_type 01043 > value_type; 01044 01045 private: 01046 value_type current; 01047 01048 public: 01050 make_tuple( 01051 Input1_ & i1_, 01052 Input2_ & i2_, 01053 Input3_ & i3_, 01054 Input4_ & i4_, 01055 Input5_ & i5_, 01056 Input6_ & i6_ 01057 ) : 01058 i1(i1_), i2(i2_), i3(i3_), i4(i4_), i5(i5_), i6(i6_), 01059 current(value_type(*i1, *i2, *i3, *i4, *i5, *i6)) { } 01060 01062 const value_type & operator * () const 01063 { 01064 return current; 01065 } 01066 01067 const value_type * operator -> () const 01068 { 01069 return ¤t; 01070 } 01071 01073 make_tuple & operator ++ () 01074 { 01075 ++i1; 01076 ++i2; 01077 ++i3; 01078 ++i4; 01079 ++i5; 01080 ++i6; 01081 01082 if (!empty()) 01083 current = value_type(*i1, *i2, *i3, *i4, *i5, *i6); 01084 01085 01086 return *this; 01087 } 01088 01090 bool empty() const 01091 { 01092 return i1.empty() || i2.empty() || i3.empty() || 01093 i4.empty() || i5.empty() || i6.empty(); 01094 } 01095 }; 01096 01097 01104 template <class Input1_, class Input2_> 01105 class make_tuple<Input1_, Input2_, Stopper, Stopper, Stopper, Stopper> 01106 { 01107 Input1_ & i1; 01108 Input2_ & i2; 01109 01110 public: 01112 typedef typename stxxl::tuple< 01113 typename Input1_::value_type, 01114 typename Input2_::value_type 01115 > value_type; 01116 01117 private: 01118 value_type current; 01119 01120 public: 01122 make_tuple( 01123 Input1_ & i1_, 01124 Input2_ & i2_ 01125 ) : 01126 i1(i1_), i2(i2_) 01127 { 01128 if (!empty()) 01129 { 01130 current = value_type(*i1, *i2); 01131 } 01132 } 01133 01135 const value_type & operator * () const 01136 { 01137 return current; 01138 } 01139 01140 const value_type * operator -> () const 01141 { 01142 return ¤t; 01143 } 01144 01146 make_tuple & operator ++ () 01147 { 01148 ++i1; 01149 ++i2; 01150 01151 if (!empty()) 01152 current = value_type(*i1, *i2); 01153 01154 01155 return *this; 01156 } 01157 01159 bool empty() const 01160 { 01161 return i1.empty() || i2.empty(); 01162 } 01163 }; 01164 01172 template <class Input1_, class Input2_, class Input3_> 01173 class make_tuple<Input1_, Input2_, Input3_, Stopper, Stopper, Stopper> 01174 { 01175 Input1_ & i1; 01176 Input2_ & i2; 01177 Input3_ & i3; 01178 01179 public: 01181 typedef typename stxxl::tuple< 01182 typename Input1_::value_type, 01183 typename Input2_::value_type, 01184 typename Input3_::value_type 01185 > value_type; 01186 01187 private: 01188 value_type current; 01189 01190 public: 01192 make_tuple( 01193 Input1_ & i1_, 01194 Input2_ & i2_, 01195 Input3_ & i3_ 01196 ) : 01197 i1(i1_), i2(i2_), i3(i3_), 01198 current(value_type(*i1, *i2, *i3)) { } 01199 01201 const value_type & operator * () const 01202 { 01203 return current; 01204 } 01205 01206 const value_type * operator -> () const 01207 { 01208 return ¤t; 01209 } 01210 01212 make_tuple & operator ++ () 01213 { 01214 ++i1; 01215 ++i2; 01216 ++i3; 01217 01218 if (!empty()) 01219 current = value_type(*i1, *i2, *i3); 01220 01221 01222 return *this; 01223 } 01224 01226 bool empty() const 01227 { 01228 return i1.empty() || i2.empty() || i3.empty(); 01229 } 01230 }; 01231 01240 template <class Input1_, 01241 class Input2_, 01242 class Input3_, 01243 class Input4_ 01244 > 01245 class make_tuple<Input1_, Input2_, Input3_, Input4_, Stopper, Stopper> 01246 { 01247 Input1_ & i1; 01248 Input2_ & i2; 01249 Input3_ & i3; 01250 Input4_ & i4; 01251 01252 public: 01254 typedef typename stxxl::tuple< 01255 typename Input1_::value_type, 01256 typename Input2_::value_type, 01257 typename Input3_::value_type, 01258 typename Input4_::value_type 01259 > value_type; 01260 01261 private: 01262 value_type current; 01263 01264 public: 01266 make_tuple( 01267 Input1_ & i1_, 01268 Input2_ & i2_, 01269 Input3_ & i3_, 01270 Input4_ & i4_ 01271 ) : 01272 i1(i1_), i2(i2_), i3(i3_), i4(i4_), 01273 current(value_type(*i1, *i2, *i3, *i4)) { } 01274 01276 const value_type & operator * () const 01277 { 01278 return current; 01279 } 01280 01281 const value_type * operator -> () const 01282 { 01283 return ¤t; 01284 } 01285 01287 make_tuple & operator ++ () 01288 { 01289 ++i1; 01290 ++i2; 01291 ++i3; 01292 ++i4; 01293 01294 if (!empty()) 01295 current = value_type(*i1, *i2, *i3, *i4); 01296 01297 01298 return *this; 01299 } 01300 01302 bool empty() const 01303 { 01304 return i1.empty() || i2.empty() || i3.empty() || 01305 i4.empty(); 01306 } 01307 }; 01308 01318 template < 01319 class Input1_, 01320 class Input2_, 01321 class Input3_, 01322 class Input4_, 01323 class Input5_ 01324 > 01325 class make_tuple<Input1_, Input2_, Input3_, Input4_, Input5_, Stopper> 01326 { 01327 Input1_ & i1; 01328 Input2_ & i2; 01329 Input3_ & i3; 01330 Input4_ & i4; 01331 Input5_ & i5; 01332 01333 public: 01335 typedef typename stxxl::tuple< 01336 typename Input1_::value_type, 01337 typename Input2_::value_type, 01338 typename Input3_::value_type, 01339 typename Input4_::value_type, 01340 typename Input5_::value_type 01341 > value_type; 01342 01343 private: 01344 value_type current; 01345 01346 public: 01348 make_tuple( 01349 Input1_ & i1_, 01350 Input2_ & i2_, 01351 Input3_ & i3_, 01352 Input4_ & i4_, 01353 Input5_ & i5_ 01354 ) : 01355 i1(i1_), i2(i2_), i3(i3_), i4(i4_), i5(i5_), 01356 current(value_type(*i1, *i2, *i3, *i4, *i5)) { } 01357 01359 const value_type & operator * () const 01360 { 01361 return current; 01362 } 01363 01364 const value_type * operator -> () const 01365 { 01366 return ¤t; 01367 } 01368 01370 make_tuple & operator ++ () 01371 { 01372 ++i1; 01373 ++i2; 01374 ++i3; 01375 ++i4; 01376 ++i5; 01377 01378 if (!empty()) 01379 current = value_type(*i1, *i2, *i3, *i4, *i5); 01380 01381 01382 return *this; 01383 } 01384 01386 bool empty() const 01387 { 01388 return i1.empty() || i2.empty() || i3.empty() || 01389 i4.empty() || i5.empty(); 01390 } 01391 }; 01392 01393 01394 template <class Input_, int Which> 01395 class choose 01396 { }; 01397 01404 template <class Input_> 01405 class choose<Input_, 1> 01406 { 01407 Input_ & in; 01408 01409 typedef typename Input_::value_type tuple_type; 01410 01411 public: 01413 typedef typename tuple_type::first_type value_type; 01414 01415 private: 01416 value_type current; 01417 01418 public: 01420 choose(Input_ & in_) : 01421 in(in_), 01422 current((*in_).first) { } 01423 01425 const value_type & operator * () const 01426 { 01427 return current; 01428 } 01429 01430 const value_type * operator -> () const 01431 { 01432 return ¤t; 01433 } 01434 01436 choose & operator ++ () 01437 { 01438 ++in; 01439 01440 if (!empty()) 01441 current = (*in).first; 01442 01443 01444 return *this; 01445 } 01446 01448 bool empty() const 01449 { 01450 return in.empty(); 01451 } 01452 }; 01453 01460 template <class Input_> 01461 class choose<Input_, 2> 01462 { 01463 Input_ & in; 01464 01465 typedef typename Input_::value_type tuple_type; 01466 01467 public: 01469 typedef typename tuple_type::second_type value_type; 01470 01471 private: 01472 value_type current; 01473 01474 public: 01476 choose(Input_ & in_) : 01477 in(in_), 01478 current((*in_).second) { } 01479 01481 const value_type & operator * () const 01482 { 01483 return current; 01484 } 01485 01486 const value_type * operator -> () const 01487 { 01488 return ¤t; 01489 } 01490 01492 choose & operator ++ () 01493 { 01494 ++in; 01495 01496 if (!empty()) 01497 current = (*in).second; 01498 01499 01500 return *this; 01501 } 01502 01504 bool empty() const 01505 { 01506 return in.empty(); 01507 } 01508 }; 01509 01516 template <class Input_> 01517 class choose<Input_, 3> 01518 { 01519 Input_ & in; 01520 01521 typedef typename Input_::value_type tuple_type; 01522 01523 public: 01525 typedef typename tuple_type::third_type value_type; 01526 01527 private: 01528 value_type current; 01529 01530 public: 01532 choose(Input_ & in_) : 01533 in(in_), 01534 current((*in_).third) { } 01535 01537 const value_type & operator * () const 01538 { 01539 return current; 01540 } 01541 01542 const value_type * operator -> () const 01543 { 01544 return ¤t; 01545 } 01546 01548 choose & operator ++ () 01549 { 01550 ++in; 01551 01552 if (!empty()) 01553 current = (*in).third; 01554 01555 01556 return *this; 01557 } 01558 01560 bool empty() const 01561 { 01562 return in.empty(); 01563 } 01564 }; 01565 01572 template <class Input_> 01573 class choose<Input_, 4> 01574 { 01575 Input_ & in; 01576 01577 typedef typename Input_::value_type tuple_type; 01578 01579 public: 01581 typedef typename tuple_type::fourth_type value_type; 01582 01583 private: 01584 value_type current; 01585 01586 public: 01588 choose(Input_ & in_) : 01589 in(in_), 01590 current((*in_).fourth) { } 01591 01593 const value_type & operator * () const 01594 { 01595 return current; 01596 } 01597 01598 const value_type * operator -> () const 01599 { 01600 return ¤t; 01601 } 01602 01604 choose & operator ++ () 01605 { 01606 ++in; 01607 01608 if (!empty()) 01609 current = (*in).fourth; 01610 01611 01612 return *this; 01613 } 01614 01616 bool empty() const 01617 { 01618 return in.empty(); 01619 } 01620 }; 01621 01628 template <class Input_> 01629 class choose<Input_, 5> 01630 { 01631 Input_ & in; 01632 01633 typedef typename Input_::value_type tuple_type; 01634 01635 public: 01637 typedef typename tuple_type::fifth_type value_type; 01638 01639 private: 01640 value_type current; 01641 01642 public: 01644 choose(Input_ & in_) : 01645 in(in_), 01646 current((*in_).fifth) { } 01647 01649 const value_type & operator * () const 01650 { 01651 return current; 01652 } 01653 01654 const value_type * operator -> () const 01655 { 01656 return ¤t; 01657 } 01658 01660 choose & operator ++ () 01661 { 01662 ++in; 01663 01664 if (!empty()) 01665 current = (*in).fifth; 01666 01667 01668 return *this; 01669 } 01670 01672 bool empty() const 01673 { 01674 return in.empty(); 01675 } 01676 }; 01677 01684 template <class Input_> 01685 class choose<Input_, 6> 01686 { 01687 Input_ & in; 01688 01689 typedef typename Input_::value_type tuple_type; 01690 01691 public: 01693 typedef typename tuple_type::sixth_type value_type; 01694 01695 private: 01696 value_type current; 01697 01698 public: 01700 choose(Input_ & in_) : 01701 in(in_), 01702 current((*in_).sixth) { } 01703 01705 const value_type & operator * () const 01706 { 01707 return current; 01708 } 01709 01710 const value_type * operator -> () const 01711 { 01712 return ¤t; 01713 } 01714 01716 choose & operator ++ () 01717 { 01718 ++in; 01719 01720 if (!empty()) 01721 current = (*in).sixth; 01722 01723 01724 return *this; 01725 } 01726 01728 bool empty() const 01729 { 01730 return in.empty(); 01731 } 01732 }; 01733 01738 template <class Input, class BinaryPredicate = Stopper> 01739 class unique 01740 { 01741 Input & input; 01742 BinaryPredicate binary_pred; 01743 typename Input::value_type current; 01744 01745 public: 01746 typedef typename Input::value_type value_type; 01747 unique(Input & input_, BinaryPredicate binary_pred_) : input(input_), binary_pred(binary_pred_) 01748 { 01749 if (!input.empty()) 01750 current = *input; 01751 } 01752 01754 unique & operator ++ () 01755 { 01756 value_type old_value = current; 01757 ++input; 01758 while (!input.empty() && (binary_pred(current = *input, old_value))) 01759 ++input; 01760 } 01762 const value_type operator * () const { return current; } 01764 const value_type * operator -> () const 01765 { 01766 return ¤t; 01767 } 01768 01770 bool empty() const { return input.empty(); } 01771 }; 01772 01776 template <class Input> 01777 class unique<Input, Stopper> 01778 { 01779 Input & input; 01780 typename Input::value_type current; 01781 01782 public: 01783 typedef typename Input::value_type value_type; 01784 unique(Input & input_) : input(input_) 01785 { 01786 if (!input.empty()) 01787 current = *input; 01788 } 01790 unique & operator ++ () 01791 { 01792 value_type old_value = current; 01793 ++input; 01794 while (!input.empty() && ((current = *input) == old_value)) 01795 ++input; 01796 } 01798 value_type operator * () const { return current; } 01799 01801 const value_type * operator -> () const 01802 { 01803 return ¤t; 01804 } 01805 01807 bool empty() const { return input.empty(); } 01808 }; 01809 01810 01812 } 01813 01814 __STXXL_END_NAMESPACE 01815 01816 #endif // !STXXL_STREAM_HEADER