Public Types | Public Member Functions | Static Public Member Functions
ibis::array_t< T > Class Template Reference

Template array_t is a replacement of std::vector. More...

#include <array_t.h>

List of all members.

Public Types

typedef const T * const_iterator
 Const iterator type.
typedef const T * const_pointer
 Pointer to a constant value.
typedef const T & const_reference
 Reference to a constant value.
typedef std::ptrdiff_t difference_type
 For difference between pointers.
typedef T * iterator
 Iterator type.
typedef T * pointer
 Pointer to a value.
typedef T & reference
 Reference to a value.
typedef size_t size_type
 For array size.
typedef T value_type
 Type of values.

Public Member Functions

 array_t ()
 The default constructor. It constructs an empty array.
 array_t (size_t n, const T &val)
 Construct an array with n elements of value val.
 array_t (ibis::fileManager::storage *rhs)
 Turn a raw storage object into an array_t object.
 array_t (ibis::fileManager::storage *rhs, const size_t start, const size_t end)
 Construct an array from a section of the raw storage.
 array_t (const array_t< T > &rhs)
 Copy constructor. Shallow copy. Should not throw any exception.
 array_t (const int fdes, const off_t begin, const off_t end)
 Construct a new array by reading a part of a binary file.
 array_t (const char *fn, const off_t begin, const off_t end)
 Constructor. Reads a portion of the named file.
 array_t (size_t n)
 Construct an array with n elements.
 array_t (const std::vector< T > &rhs)
 Copy the values from a vector to array_t.
 array_t (const char *fn, const int fdes, const off_t begin, const off_t end)
 Constructor.
 array_t (T *addr, size_t nelm)
 Constructor.
 array_t (const array_t< T > &rhs, const size_t begin, const size_t end=0)
 A shallow copy constructor.
T & back ()
const T & back () const
T * begin ()
const T * begin () const
void bottomk (uint32_t k, array_t< uint32_t > &ind) const
 Return the positions of the k smallest elements.
size_t capacity () const
 The maximum number of elements can be stored with the current memory.
void clear ()
 Reset the size to zero.
void copy (const array_t< T > &rhs)
 The copy function. It performs a shallow copy.
void deduplicate ()
 Remove the duplicate values.
void deepCopy (const array_t< T > &rhs)
 The deep copy function. It makes an in-memory copy of rhs.
bool empty () const
T * end ()
const T * end () const
iterator erase (iterator i, iterator j)
iterator erase (iterator p)
uint32_t find (const array_t< uint32_t > &ind, const T &val) const
 Find the position of the first element that is no less than val.
size_t find (const T &val) const
 Return the smallest i such that [i] >= val.
size_t find_upper (const T &val) const
 Return the smallest i such that [i] > val.
T & front ()
const T & front () const
ibis::fileManager::storagegetStorage ()
 Export the actual storage object.
bool incore () const
 Is the content of the array solely in memory?
void insert (iterator p, const_iterator i, const_iterator j)
iterator insert (iterator pos, const T &val)
void insert (iterator p, size_t n, const T &val)
void nosharing ()
 Make a not-shared copy of the array if it is currently shared or read-only.
array_t< T > & operator= (const array_t< T > &rhs)
 Assignment operator. It performs a shallow copy.
const T & operator[] (size_t i) const
 Non-modifiable reference to an element of the array.
T & operator[] (size_t i)
 Modifiable reference to an element of the array.
void pop_back ()
void printStatus (std::ostream &out) const
 Print internal pointer addresses.
void push_back (const T &elm)
 Add one element.
off_t read (const int fdes, const off_t begin, const off_t end)
 Read a portion of an open file.
void read (const char *)
 Read an array from the name file.
void reserve (size_t n)
 Reserve space.
void resize (size_t n)
 Remove the last element.
size_t size () const
void sort (array_t< uint32_t > &ind) const
 Produce index for ascending order.
void stableSort (array_t< T > &tmp)
 A stable sort using the provided workspace.
void stableSort (array_t< uint32_t > &ind) const
 A stable sort that does not modify the current array.
void stableSort (array_t< uint32_t > &ind, array_t< T > &sorted) const
 A stable sort.
void swap (array_t< T > &rhs)
 Exchange the content.
void topk (uint32_t k, array_t< uint32_t > &ind) const
 Return the positions of the k largest elements.
void truncate (size_t keep, size_t start)
 Replace the current array with nnew rows.
void write (FILE *fptr) const
 write whole array to an opened file
void write (const char *) const
 write whole array to the named file

Static Public Member Functions

static void stableSort (array_t< T > &val, array_t< uint32_t > &ind, array_t< T > &tmp, array_t< uint32_t > &itmp)
 This function sorts the content of array val.

Detailed Description

template<class T>
class ibis::array_t< T >

Template array_t is a replacement of std::vector.

The main difference is that the underlying memory of this object is reference-counted and managed by ibis::fileManager. It is intended to store arrays in memory, and it's possible to have shallow copies of read-only arrays. The memory is guaranteed to be contiguous. It also implements read and write functions that are not present in std::vector.

Note:
This implementation uses size_t integers for measuring the number of elements, therefore, the maximum size it can handle is machine and compiler dependent.

Constructor & Destructor Documentation

template<class T>
ibis::array_t< T >::array_t ( const array_t< T > &  rhs,
const size_t  begin,
const size_t  end = 0 
)

A shallow copy constructor.

It makes a new array out of a section of the existing array. The values of begin and end are indices to the array rhs.

Note:
If end is less than to begin, the array section is assumed to extend to the end of rhs.

References ibis::fileManager::storage::beginUse(), ibis::gVerbose, and ibis::fileManager::storage::size().

template<class T>
ibis::array_t< T >::array_t ( ibis::fileManager::storage rhs) [explicit]

Turn a raw storage object into an array_t object.

The input storage object is used by the array. No new storage is allocated.

References ibis::fileManager::storage::beginUse(), ibis::gVerbose, and ibis::fileManager::storage::size().

template<class T>
ibis::array_t< T >::array_t ( ibis::fileManager::storage rhs,
const size_t  start,
const size_t  end 
)

Construct an array from a section of the raw storage.

No new storage is allocated.

Note:
The arguments start and end are offsets into the raw storage measured in number of bytes, NOT the number of elements of type T!

References ibis::fileManager::storage::beginUse(), ibis::fileManager::storage::end(), and ibis::gVerbose.

template<class T>
ibis::array_t< T >::array_t ( const int  fdes,
const off_t  begin,
const off_t  end 
)

Construct a new array by reading a part of a binary file.

The argument fdes must be a valid file descriptor (as defined in unistd.h). It attempt to read end - begin bytes from the file starting at offset begin.

References ibis::fileManager::storage::beginUse(), and ibis::gVerbose.

template<class T>
ibis::array_t< T >::array_t ( const char *  fn,
const int  fdes,
const off_t  begin,
const off_t  end 
)

Constructor.

Reads a portion of the named file through the specified file descriptor.

References ibis::fileManager::storage::beginUse(), and ibis::gVerbose.

template<class T>
ibis::array_t< T >::array_t ( T *  addr,
size_t  nelm 
)

Constructor.

Directly use the raw pointer provided. Note that the second argument is the number of elements starting at the given address.

References ibis::gVerbose.


Member Function Documentation

template<class T >
void ibis::array_t< T >::bottomk ( uint32_t  k,
array_t< uint32_t > &  ind 
) const

Return the positions of the k smallest elements.

Sort the first k elemnent of the array.

Return the indices of the smallest values in array ind.

Note:
The resulting array ind may have more than k elements if the kth smallest value is not a single value. The array ind may have less than k elements if this array has less than k elements.

References ibis::array_t< T >::clear(), and ibis::array_t< T >::resize().

Referenced by ibis::bundles::truncate().

template<class T >
void ibis::array_t< T >::deduplicate ( )

Remove the duplicate values.

It sorts the values first and remove any entry that is not in strictly assending order.

Warning:
This function uses std::sort to order the values first before removign duplicates. The function std::sort normally would places not-a-number (nan) at the end of the array which allows this function to remove them from the list of values. However, should std::sort actually places nans at the beginning of the sorted list, this function will produce an empty array.

Referenced by ibis::qDiscreteRange::qDiscreteRange(), ibis::qIntHod::qIntHod(), and ibis::qUIntHod::qUIntHod().

template<class T>
uint32_t ibis::array_t< T >::find ( const array_t< uint32_t > &  ind,
const T &  val 
) const

Find the position of the first element that is no less than val.

Assuming ind was produced by the sort function, it returns the smallest i such that operator[](ind[i]) >= val.

Referenced by ibis::query::countDeltaPairs(), ibis::query::countEqualPairs(), ibis::part::mapValues(), ibis::index::mapValues(), ibis::query::recordDeltaPairs(), ibis::query::recordEqualPairs(), ibis::bundles::reorder(), ibis::bord::reorder(), ibis::column::searchSortedICC(), ibis::column::searchSortedICD(), ibis::part::vault::seek(), and ibis::bundles::truncate().

template<class T>
size_t ibis::array_t< T >::find ( const T &  val) const

Return the smallest i such that [i] >= val.

Find the first position where the value is no less than val.

Assuming the array is already sorted in ascending order, it returns the smallest i such that operator[](i) >= val.

template<class T>
size_t ibis::array_t< T >::find_upper ( const T &  val) const

Return the smallest i such that [i] > val.

Find the first position where the value is greater than val.

Assuming the array is already sorted in ascending order, it returns the smallest i such that operator[](i) > val.

Note:
The word upper is used in the same sense as in the STL function std::upper_bound.

Referenced by ibis::column::searchSortedICC().

template<class T>
ibis::fileManager::storage* ibis::array_t< T >::getStorage ( ) [inline]

Export the actual storage object.

Note:
This function returns the internal storage representation of the array_t object. In general, it is very dangarous to expose internal implementation details to clients. Likely to be removed soon. Don't rely on this function!
template<class T >
void ibis::array_t< T >::nosharing ( )

Make a not-shared copy of the array if it is currently shared or read-only.

This function makes a copy of the current content if the content is shared by two or more clients.

This does not guarantee that it would not become shared later. The complete solution is to implement copy-on-write in all functions that modifies an array, however, there are plenty of cases where the copying is unnecessary. This function will create a private copy of the data if there are more than one active references on this object and when the underlying data is tracked by the file managers.

References ibis::gVerbose.

Referenced by ibis::util::sortAll(), ibis::util::sortKeys(), ibis::util::sortMerge(), and ibis::util::sortRIDs().

template<class T>
T& ibis::array_t< T >::operator[] ( size_t  i) [inline]

Modifiable reference to an element of the array.

Note:
For efficiency reasons, this is not a copy-on-write implementation! The caller has to call the function nosharing to make sure the underlying data is not shared with others.
template<class T>
void ibis::array_t< T >::push_back ( const T &  elm) [inline]

Add one element.

Add one element from the back.

References ibis::array_t< T >::resize().

Referenced by ibis::tafel::append(), ibis::relic::append(), ibis::bin::append(), ibis::bin::binningT(), ibis::bin::binOrderT(), ibis::part::calculate(), ibis::bitvector64::compress(), ibis::index::divideCounts(), ibis::part::equalWeightBins(), ibis::bitvector64::erase(), ibis::bitvector::erase(), ibis::bord::evaluateTerms(), ibis::blob::extractAll(), ibis::blob::extractSome(), ibis::fromClause::getNames(), ibis::query::getRIDs(), ibis::part::getRIDs(), ibis::bord::groupby(), ibis::meshQuery::label2DBlocks(), ibis::meshQuery::label3DBlocks(), ibis::meshQuery::label4DBlocks(), ibis::meshQuery::labelBlocks(), ibis::part::loadIndexes(), ibis::index::mapValues(), ibis::roster::mergeBlock2(), ibis::tafel::normalize(), ibis::tafel::parseLine(), ibis::table::parseNames(), ibis::qAnyAny::qAnyAny(), ibis::qDiscreteRange::qDiscreteRange(), ibis::qIntHod::qIntHod(), ibis::qUIntHod::qUIntHod(), ibis::ridHandler::read(), ibis::bundles::reorder(), ibis::bord::reorder(), ibis::part::reorderValues(), ibis::bin::scanAndPartition(), ibis::colStrings::segment(), ibis::colDoubles::segment(), ibis::colFloats::segment(), ibis::colUBytes::segment(), ibis::colBytes::segment(), ibis::colUShorts::segment(), ibis::colShorts::segment(), ibis::colULongs::segment(), ibis::colLongs::segment(), ibis::colUInts::segment(), ibis::colInts::segment(), ibis::text::selectLongs(), ibis::text::selectUInts(), ibis::column::selectValuesT(), ibis::index::setBases(), ibis::colStrings::sort(), ibis::colDoubles::sort(), ibis::colFloats::sort(), ibis::colUBytes::sort(), ibis::colBytes::sort(), ibis::colUShorts::sort(), ibis::colShorts::sort(), ibis::colULongs::sort(), ibis::colLongs::sort(), ibis::colUInts::sort(), ibis::colInts::sort(), ibis::bord::sortStrings(), ibis::bord::sortValues(), ibis::column::string2int(), ibis::bundles::truncate(), ibis::bitvector64::write(), and ibis::bitvector::write().

template<class T >
off_t ibis::array_t< T >::read ( const int  fdes,
const off_t  begin,
const off_t  end 
)

Read a portion of an open file.

Read an array from a file already open.

References ibis::gVerbose, and ibis::array_t< T >::read().

template<class T >
void ibis::array_t< T >::reserve ( size_t  n)
template<class T >
void ibis::array_t< T >::resize ( size_t  n)

Remove the last element.

Change the size of the array so it has no less than
elements.

Resize array.

If n is greater than its current capacity, it allocates exactly enough space for the new array. If the user needs to perform a series of resize operations with progressively larger size, call function reserve to increase the underlying storage to avoid this function copying the data many times.

References ibis::gVerbose.

Referenced by ibis::part::adaptive2DBins(), ibis::part::adaptive3DBins(), ibis::part::adaptiveInts(), ibis::part::adaptiveIntsDetailed(), ibis::tafel::append(), ibis::bin::append(), ibis::category::append(), ibis::bin::bin(), ibis::colStrings::bottomk(), ibis::array_t< T >::bottomk(), ibis::part::calculate(), ibis::part::coarsenBins(), ibis::bitvector64::decompress(), ibis::bitvector::decompress(), ibis::index::divideCounts(), ibis::tafel::doReserve(), ibis::part::equalWeightBins(), ibis::blob::extractAll(), ibis::blob::extractSome(), ibis::part::fill1DBinsWeighted(), ibis::part::fill2DBinsWeighted(), ibis::part::fill3DBinsWeighted(), ibis::category::fillIndex(), ibis::part::get2DDistributionI(), ibis::bord::getColumnAsDoubles(), ibis::bord::getColumnAsStrings(), ibis::part::getJointDistribution(), ibis::bord::groupby(), ibis::roster::mergeBlock2(), ibis::tafel::normalize(), ibis::part::old2DDistribution(), ibis::bitvector64::operator&(), ibis::bitvector::operator&(), ibis::bitvector64::operator-(), ibis::bitvector::operator-(), ibis::bitvector64::operator^(), ibis::bitvector::operator^(), ibis::bitvector64::operator|(), ibis::bitvector::operator|(), ibis::pack::pack(), ibis::tafel::parseLine(), ibis::array_t< T >::push_back(), ibis::qAnyAny::qAnyAny(), ibis::qDiscreteRange::qDiscreteRange(), ibis::qIntHod::qIntHod(), ibis::part::quickTest(), ibis::qUIntHod::qUIntHod(), ibis::range::range(), ibis::bundle::readRIDs(), ibis::relic::relic(), ibis::part::reorderValues(), ibis::bundle::rowCounts(), ibis::bord::column::selectBytes(), ibis::bord::column::selectDoubles(), ibis::bord::column::selectFloats(), ibis::bord::column::selectInts(), ibis::bord::column::selectLongs(), ibis::bord::column::selectShorts(), ibis::bord::column::selectStrings(), ibis::bord::column::selectUBytes(), ibis::bord::column::selectUInts(), ibis::bord::column::selectULongs(), ibis::bord::column::selectUShorts(), ibis::column::selectValuesT(), ibis::index::setBases(), ibis::array_t< T >::sort(), ibis::util::sortMerge(), ibis::bord::sortStrings(), ibis::bord::sortValues(), ibis::array_t< T >::stableSort(), ibis::colStrings::topk(), ibis::array_t< T >::topk(), ibis::tafel::toTable(), ibis::bitvector64::write(), ibis::bitvector::write(), and ibis::zone::zone().

template<class T>
size_t ibis::array_t< T >::size ( ) const [inline]

< Return the number of elements.

Referenced by ibis::column::actualMinMax(), ibis::part::adaptive2DBins(), ibis::part::adaptive3DBins(), ibis::part::adaptiveFloats(), ibis::part::adaptiveFloatsDetailed(), ibis::part::adaptiveInts(), ibis::part::adaptiveIntsDetailed(), ibis::part::addColumn(), ibis::bord::column::addIncoreData(), ibis::meshQuery::afind(), ibis::meshQuery::aflatten(), ibis::bitvector64::all0s(), ibis::tafel::append(), ibis::ridHandler::append(), ibis::relic::append(), ibis::bin::append(), ibis::category::append(), ibis::column::appendValues(), ibis::meshQuery::aset(), ibis::bin::binning(), ibis::bin::binningT(), ibis::bin::binOrderT(), ibis::bitvector::bitvector(), ibis::bord::bord(), ibis::bundle1::bundle1(), ibis::bundles::bundles(), ibis::bylt::bylt(), ibis::bitvector64::bytes(), ibis::part::calculate(), ibis::part::coarsenBins(), ibis::bitvector64::compress(), ibis::column::computeMax(), ibis::column::computeMin(), ibis::column::computeSum(), ibis::ambit::construct(), ibis::relic::construct(), ibis::range::construct(), ibis::egale::construct(), ibis::bitvector::count(), ibis::part::count2DBins(), ibis::part::count2DWeights(), ibis::part::count3DBins(), ibis::part::count3DWeights(), ibis::query::countDeltaPairs(), ibis::query::countEqualPairs(), ibis::blob::countRawBytes(), ibis::bitvector64::decompress(), ibis::bitvector::decompress(), ibis::array_t< T >::deepCopy(), ibis::dictionary::dictionary(), ibis::index::divideCounts(), ibis::part::doCompare(), ibis::part::doCompare0(), ibis::part::doCount(), ibis::part::doScan(), ibis::egale::egale(), ibis::part::equalWeightBins(), ibis::relic::estimate(), ibis::direkte::estimate(), ibis::slice::estimateCost(), ibis::relic::estimateCost(), ibis::part::estimateMatchAny(), ibis::query::evaluate(), ibis::slice::evaluate(), ibis::sbiad::evaluate(), ibis::sapid::evaluate(), ibis::relic::evaluate(), ibis::fade::evaluate(), ibis::direkte::evaluate(), ibis::column::evaluateRange(), ibis::part::evaluateRIDSet(), ibis::bord::evaluateTerms(), ibis::blob::extractAll(), ibis::blob::extractSome(), ibis::fade::fade(), ibis::part::fill1DBins(), ibis::part::fill1DBinsWeighted(), ibis::part::fill2DBins(), ibis::part::fill2DBinsWeighted(), ibis::part::fill3DBins(), ibis::part::fill3DBinsWeighted(), ibis::category::fillIndex(), ibis::jRange::fillResult(), ibis::jNatural::fillResult(), ibis::table::freeBuffers(), ibis::fromClause::fromClause(), ibis::fuzz::fuzz(), ibis::part::get1DBins_(), ibis::part::get1DDistribution(), ibis::part::get2DDistributionI(), ibis::blob::getBlob(), ibis::bord::getColumnAsBytes(), ibis::bord::getColumnAsDoubles(), ibis::bord::getColumnAsFloats(), ibis::bord::getColumnAsInts(), ibis::bord::getColumnAsLongs(), ibis::bord::getColumnAsShorts(), ibis::bord::getColumnAsStrings(), ibis::bord::getColumnAsUBytes(), ibis::bord::getColumnAsUInts(), ibis::bord::getColumnAsULongs(), ibis::bord::getColumnAsUShorts(), ibis::part::getCumulativeDistribution(), ibis::part::getDistribution(), ibis::fileManager::getFile(), ibis::part::getJointDistribution(), ibis::query::getQualifiedBytes(), ibis::query::getQualifiedDoubles(), ibis::query::getQualifiedFloats(), ibis::query::getQualifiedInts(), ibis::query::getQualifiedLongs(), ibis::query::getQualifiedShorts(), ibis::query::getQualifiedUBytes(), ibis::query::getQualifiedUInts(), ibis::query::getQualifiedULongs(), ibis::query::getQualifiedUShorts(), ibis::query::getRIDs(), ibis::part::getRIDs(), ibis::query::getRIDsInBundle(), ibis::bitvector64::getSerialSize(), ibis::roster::icSearch(), ibis::meshQuery::label2DBlocks(), ibis::meshQuery::label3DBlocks(), ibis::meshQuery::label4DBlocks(), ibis::meshQuery::labelBlocks(), ibis::part::loadIndexes(), ibis::roster::locate(), ibis::roster::locate2(), ibis::part::mapValues(), ibis::index::mapValues(), ibis::bak2::mapValues(), ibis::bak::mapValues(), ibis::roster::mergeBlock2(), ibis::part::negativeCompare(), ibis::tafel::normalize(), ibis::part::old2DDistribution(), ibis::roster::oocSearch(), ibis::bitvector64::operator&(), ibis::bitvector::operator&(), ibis::bitvector64::operator&=(), ibis::bitvector::operator&=(), ibis::bitvector64::operator-(), ibis::bitvector::operator-(), ibis::bitvector64::operator-=(), ibis::bitvector::operator-=(), ibis::bitvector64::operator==(), ibis::bitvector::operator==(), ibis::roster::operator[](), ibis::bitvector64::operator^(), ibis::bitvector::operator^(), ibis::bitvector64::operator^=(), ibis::bitvector::operator^=(), ibis::bitvector64::operator|(), ibis::bitvector::operator|(), ibis::bitvector64::operator|=(), ibis::bitvector::operator|=(), ibis::part::part(), ibis::query::printRIDs(), ibis::qDiscreteRange::qDiscreteRange(), ibis::part::quickTest(), ibis::ridHandler::read(), ibis::zone::read(), ibis::pale::read(), ibis::pack::read(), ibis::query::readRIDs(), ibis::query::recordDeltaPairs(), ibis::query::recordEqualPairs(), ibis::colStrings::reduce(), ibis::colDoubles::reduce(), ibis::colFloats::reduce(), ibis::colUBytes::reduce(), ibis::colBytes::reduce(), ibis::colUShorts::reduce(), ibis::colShorts::reduce(), ibis::colULongs::reduce(), ibis::colLongs::reduce(), ibis::colUInts::reduce(), ibis::colInts::reduce(), ibis::relic::relic(), ibis::util::reorder(), ibis::part::reorder(), ibis::colStrings::reorder(), ibis::bundles::reorder(), ibis::bord::reorder(), ibis::bord::reorderStrings(), ibis::part::reorderValues(), ibis::bord::column::restoreCategoriesAsStrings(), ibis::roster::roster(), ibis::sapid::sapid(), ibis::sbiad::sbiad(), ibis::bin::scanAndPartition(), ibis::column::searchSortedICC(), ibis::column::searchSortedICD(), ibis::column::searchSortedOOCD(), ibis::colStrings::segment(), ibis::colDoubles::segment(), ibis::colFloats::segment(), ibis::colUBytes::segment(), ibis::colBytes::segment(), ibis::colUShorts::segment(), ibis::colShorts::segment(), ibis::colULongs::segment(), ibis::colLongs::segment(), ibis::colUInts::segment(), ibis::colInts::segment(), ibis::jRange::select(), ibis::jNatural::select(), ibis::column::selectBytes(), ibis::bord::column::selectBytes(), ibis::selectClause::selectClause(), ibis::column::selectDoubles(), ibis::bord::column::selectDoubles(), ibis::column::selectFloats(), ibis::bord::column::selectFloats(), ibis::column::selectInts(), ibis::bord::column::selectInts(), ibis::column::selectLongs(), ibis::text::selectLongs(), ibis::bord::column::selectLongs(), ibis::blob::selectRawBytes(), ibis::column::selectShorts(), ibis::bord::column::selectShorts(), ibis::text::selectStrings(), ibis::bord::column::selectStrings(), ibis::column::selectToStrings(), ibis::column::selectUBytes(), ibis::bord::column::selectUBytes(), ibis::column::selectUInts(), ibis::bord::column::selectUInts(), ibis::column::selectULongs(), ibis::bord::column::selectULongs(), ibis::column::selectUShorts(), ibis::bord::column::selectUShorts(), ibis::column::selectValuesT(), ibis::query::setRIDs(), ibis::slice::slice(), ibis::array_t< T >::sort(), ibis::util::sort_heap(), ibis::util::sort_insertion(), ibis::util::sort_partition(), ibis::util::sort_partition3(), ibis::util::sort_quick(), ibis::util::sort_quick3(), ibis::util::sort_radix(), ibis::util::sort_shell(), ibis::util::sortAll(), ibis::util::sortAll_quick(), ibis::util::sortAll_shell(), ibis::util::sortAll_split(), ibis::query::sortEquiJoin(), ibis::util::sortKeys(), ibis::util::sortMerge(), ibis::query::sortRangeJoin(), ibis::util::sortRIDs(), ibis::util::sortStrings(), ibis::bord::sortStrings(), ibis::util::sortStrings_partition(), ibis::util::sortStrings_quick(), ibis::util::sortStrings_shell(), ibis::bord::sortValues(), ibis::array_t< T >::stableSort(), ibis::column::string2int(), ibis::bundles::truncate(), ibis::fileManager::tryGetFile(), ibis::ridHandler::write(), ibis::part::writeColumn(), ibis::part::writeRaw(), ibis::part::writeValues(), ibis::zona::zona(), and ibis::zone::zone().

template<class T >
void ibis::array_t< T >::sort ( array_t< uint32_t > &  ind) const

Produce index for ascending order.

Sort the array to produce ind so that array_t[ind[i]] is in ascending order.

Uses the quicksort algorithm with introspection. On entering this function, if the values in ind are less than size(), then this function only sorts the subset of elements identified by the indices. Otherwise, it is fill with values between 0 and size()-1. It returns an empty array ind to indicate errors.

References ibis::array_t< T >::clear(), ibis::array_t< T >::resize(), and ibis::array_t< T >::size().

Referenced by ibis::bundles::reorder(), ibis::bord::reorder(), ibis::part::reorderValues(), ibis::bord::sortValues(), and ibis::bundles::truncate().

template<class T>
void ibis::array_t< T >::stableSort ( array_t< uint32_t > &  ind,
array_t< T > &  sorted 
) const

A stable sort.

The content of array ind will be simply moved together with @ this array if it is the same size as this array.

It does not change this array, but produces a sorted version in sorted.

Otherwise, it is initialized to consecutive integers starting from 0 before the actual sorting is performed.

References ibis::array_t< T >::clear(), and ibis::array_t< T >::resize().

template<class T>
void ibis::array_t< T >::stableSort ( array_t< uint32_t > &  ind) const

A stable sort that does not modify the current array.

Use merge sort algorithm to produce an index array so that array[ind[i]] would in ascending order.

It uses two additional arrays for temporary storage.

References ibis::array_t< T >::clear(), ibis::array_t< T >::deepCopy(), and ibis::array_t< T >::resize().

template<class T>
void ibis::array_t< T >::stableSort ( array_t< T > &  tmp)

A stable sort using the provided workspace.

Merge sort algorithm.

The current content is modified to be in ascending order. The argument tmp is only used as temporary storage.

This array is sorted. The argument tmp is only used as temporary storage.

References ibis::array_t< T >::resize(), and ibis::array_t< T >::size().

Referenced by ibis::query::sortEquiJoin(), and ibis::query::sortRangeJoin().

template<class T>
void ibis::array_t< T >::stableSort ( array_t< T > &  val,
array_t< uint32_t > &  ind,
array_t< T > &  tmp,
array_t< uint32_t > &  itmp 
) [static]

This function sorts the content of array val.

The values of ind[i] will be reordered in the same way as the array val. The two other arrays are used as temporary storage.

Note:
On input, if array ind has the same size as array val, the content of array ind will be directly used. Otherwise, array ind will be initialized to be consecutive integers starting from 0.
If the input array val has less than two elements, this function does nothing, i.e., does not change any of the four arguments.

References ibis::array_t< T >::clear(), ibis::array_t< T >::resize(), ibis::array_t< T >::size(), and ibis::array_t< T >::swap().

template<class T>
void ibis::array_t< T >::swap ( array_t< T > &  rhs) [inline]
template<class T >
void ibis::array_t< T >::topk ( uint32_t  k,
array_t< uint32_t > &  ind 
) const

Return the positions of the k largest elements.

Sort the k largest elements of the array.

Return the indices of the in sorted values.

Note:
The resulting array ind may have more than k elements if the kth largest value is not a single value. The array ind may have less than k elements if this array has less than k elements.
The values are sorted in ascending order, i.e., [ind[i]] <= [ind[i+1]]. This is done so that all sorting routines produce indices in the same ascending order. It should be easy to reverse the order the indices since it only contains the largest values.

References ibis::array_t< T >::clear(), and ibis::array_t< T >::resize().

template<class T >
void ibis::array_t< T >::truncate ( size_t  nnew,
size_t  start 
)

Replace the current array with nnew rows.

The first row kept has the row number start in the current content. Note the the rows are numbered from 0.

template<class T >
void ibis::array_t< T >::write ( const char *  file) const

write whole array to the named file

Write the content of array to the named file.

References ibis::gVerbose.

Referenced by ibis::category::fillIndex(), and ibis::query::writeRIDs().

template<class T >
void ibis::array_t< T >::write ( FILE *  fptr) const

write whole array to an opened file

Write the content of the array to a file already opened.

References ibis::gVerbose.


The documentation for this class was generated from the following files:

Make It A Bit Faster
Contact us
Disclaimers
FastBit source code
FastBit mailing list archive