Stxxl
1.3.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/stream/sorted_runs.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2002-2005 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * Copyright (C) 2009, 2010 Andreas Beckmann <beckmann@cs.uni-frankfurt.de> 00008 * 00009 * Distributed under the Boost Software License, Version 1.0. 00010 * (See accompanying file LICENSE_1_0.txt or copy at 00011 * http://www.boost.org/LICENSE_1_0.txt) 00012 **************************************************************************/ 00013 00014 #ifndef STXXL_STREAM__SORTED_RUNS_H 00015 #define STXXL_STREAM__SORTED_RUNS_H 00016 00017 #include <vector> 00018 #include <stxxl/bits/mng/mng.h> 00019 #include <stxxl/bits/mng/typed_block.h> 00020 #include <stxxl/bits/algo/adaptor.h> 00021 00022 00023 __STXXL_BEGIN_NAMESPACE 00024 00025 namespace stream 00026 { 00029 00030 00032 // SORTED RUNS // 00034 00036 template <typename TriggerEntryType> 00037 struct sorted_runs 00038 { 00039 typedef TriggerEntryType trigger_entry_type; 00040 typedef typename trigger_entry_type::block_type block_type; 00041 typedef typename block_type::value_type value_type; // may differ from trigger_entry_type::value_type 00042 typedef std::vector<trigger_entry_type> run_type; 00043 typedef std::vector<value_type> small_run_type; 00044 typedef stxxl::external_size_type size_type; 00045 typedef typename std::vector<run_type>::size_type run_index_type; 00046 00047 size_type elements; 00048 std::vector<run_type> runs; 00049 std::vector<size_type> runs_sizes; 00050 00051 // Optimization: 00052 // if the input is small such that its total size is 00053 // at most B (block_type::size) 00054 // then input is sorted internally 00055 // and kept in the array "small" 00056 small_run_type small_; 00057 00058 sorted_runs() : elements(0) { } 00059 00060 const small_run_type & small_run() const 00061 { 00062 return small_; 00063 } 00064 00069 void deallocate_blocks() 00070 { 00071 block_manager * bm = block_manager::get_instance(); 00072 for (unsigned_type i = 0; i < runs.size(); ++i) 00073 bm->delete_blocks(make_bid_iterator(runs[i].begin()), make_bid_iterator(runs[i].end())); 00074 00075 runs.clear(); 00076 } 00077 00078 // returns number of elements in all runs together 00079 size_type size() const 00080 { 00081 return elements; 00082 } 00083 }; 00084 00085 00087 } 00088 00089 __STXXL_END_NAMESPACE 00090 00091 #endif // !STXXL_STREAM__SORTED_RUNS_H 00092 // vim: et:ts=4:sw=4