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)
 Constructor. Construct an array with n elements.
 array_t (size_t n, const T &val)
 Constructor. Construct an array with n elements of value val.
 array_t (const array_t< T > &rhs)
 Copy constructor.
 array_t (const std::vector< T > &rhs)
 Constructor. Copy the values from a vector to array_t.
 array_t (const array_t< T > &rhs, const size_t begin, const size_t end=0)
 A shallow copy constructor.
 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 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 (const char *fn, const int fdes, const off_t begin, const off_t end)
 Constructor.
 array_t (T *addr, size_t nelm)
 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.
bool empty () const
T * end ()
const T * end () const
bool equal_to (const array_t< T > &) const
 Does this array have the same content as the other? Return true is yes, otherwise false.
iterator erase (iterator p)
iterator erase (iterator i, iterator j)
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
 Find the first position where the value is no less than val.
size_t find_upper (const T &val) const
 Find the first position where the value is greater than 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?
iterator insert (iterator pos, const T &val)
void insert (iterator p, size_t n, const T &val)
void insert (iterator p, const_iterator i, const_iterator j)
bool isSorted () const
 Verify the values are in ascending order.
bool isSorted (const array_t< uint32_t > &) const
 Verify the index array orders the values in the ascending order.
void nosharing ()
 Make a non-shared copy of the array.
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.
void read (const char *)
 Read an array from the name file.
off_t read (const char *, const off_t, const off_t)
 Read a portion of the named file.
off_t read (const int, const off_t, const off_t)
 Read an array from a file already open.
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.
int write (const char *) const
 Write the content of array to the named file.
int write (FILE *fptr) const
 Write the content of the array to a file already opened.

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)

Copy constructor.

Makes a shallow copy. Should not throw any exception.

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

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 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>
void ibis::array_t< T >::deepCopy ( const array_t< T > &  rhs)

The deep copy function.

It makes an in-memory copy of rhs. If rhs is empty or uninitialized, the current content is cleared resulting in an empty array.

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

Referenced by ibis::query::getRIDs(), ibis::part::quickTest(), ibis::query::setRIDs(), and ibis::array_t< T >::stableSort().

template<typename T>
bool ibis::array_t< T >::equal_to ( const array_t< T > &  other) const

Does this array have the same content as the other? Return true is yes, otherwise false.

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

Referenced by ibis::bord::column::equal_to().

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::index::mapValues(), ibis::part::mapValues(), ibis::query::recordDeltaPairs(), ibis::query::recordEqualPairs(), ibis::bord::reorder(), ibis::bundles::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

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

Assuming the array is already sorted in the 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

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

Assuming the array is already sorted in the 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 >
bool ibis::array_t< T >::isSorted ( ) const

Verify the values are in ascending order.

Returns true if yes, otherwise no.

Referenced by ibis::array_t< T >::stableSort().

template<class T >
bool ibis::array_t< T >::isSorted ( const array_t< uint32_t > &  ind) const

Verify the index array orders the values in the ascending order.

Returns true if yes, otherwise false.

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

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

Make a non-shared copy of the array.

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::fileManager::storage::begin(), ibis::fileManager::storage::beginUse(), ibis::fileManager::storage::end(), ibis::util::envLock, and ibis::gVerbose.

Referenced by ibis::part::doComp(), ibis::part::doCompare(), ibis::bord::merge10(), ibis::bord::merge11(), ibis::bord::merge12(), ibis::bord::merge20(), ibis::bord::merge20T1(), ibis::bord::merge21(), ibis::bord::merge21T1(), ibis::bord::merge21T2(), 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::direkte::append(), ibis::relic::append(), ibis::tafel::append(), ibis::bin::append(), ibis::bord::column::append(), ibis::bin::binOrderT(), ibis::part::calculate(), ibis::mensa::combineCategories(), ibis::bitvector64::compress(), ibis::index::divideCounts(), ibis::part::doComp(), ibis::part::doCompare(), ibis::part::doScan(), ibis::part::equalWeightBins(), ibis::bitvector64::erase(), ibis::bitvector::erase(), ibis::bord::evaluateTerms(), ibis::blob::extractAll(), ibis::blob::extractSome(), ibis::fromClause::getNames(), ibis::part::getRIDs(), ibis::query::getRIDs(), ibis::bord::groupbya(), ibis::selectClause::isUnivariate(), ibis::direkte::keys(), ibis::meshQuery::label2DBlocks(), ibis::meshQuery::label3DBlocks(), ibis::meshQuery::label4DBlocks(), ibis::meshQuery::labelBlocks(), ibis::part::loadIndexes(), ibis::index::mapValues(), ibis::dictionary::merge(), ibis::bord::merge10T(), ibis::bord::merge11T(), ibis::bord::merge20T2(), ibis::bord::merge21T3(), ibis::roster::mergeBlock2(), ibis::bin::mergeValues(), ibis::relic::mergeValuesT(), ibis::tafel::normalize(), ibis::tafel::parseLine(), ibis::table::parseNames(), ibis::table::parseOrderby(), ibis::dictionary::patternSearch(), ibis::qAnyAny::qAnyAny(), ibis::qDiscreteRange::qDiscreteRange(), ibis::qIntHod::qIntHod(), ibis::qUIntHod::qUIntHod(), ibis::ridHandler::read(), ibis::bord::reorder(), ibis::bundles::reorder(), ibis::part::reorderValues(), ibis::bin::scanAndPartition(), ibis::colInts::segment(), ibis::colUInts::segment(), ibis::colLongs::segment(), ibis::colULongs::segment(), ibis::colShorts::segment(), ibis::colUShorts::segment(), ibis::colBytes::segment(), ibis::colUBytes::segment(), ibis::colFloats::segment(), ibis::colDoubles::segment(), ibis::colStrings::segment(), ibis::jNatural::select(), ibis::jRange::select(), ibis::text::selectLongs(), ibis::text::selectUInts(), ibis::column::selectValuesT(), ibis::index::setBases(), ibis::filter::sift2(), ibis::filter::sift2S(), ibis::colInts::sort(), ibis::colUInts::sort(), ibis::colLongs::sort(), ibis::colULongs::sort(), ibis::colShorts::sort(), ibis::colUShorts::sort(), ibis::colBytes::sort(), ibis::colUBytes::sort(), ibis::colFloats::sort(), ibis::colDoubles::sort(), ibis::colStrings::sort(), ibis::bord::sortStrings(), ibis::bord::sortValues(), ibis::column::string2int(), ibis::index::sumBins(), ibis::index::sumBits(), ibis::bundles::truncate(), ibis::bitvector64::write(), ibis::bitvector::write(), and ibis::bord::xgroupby().

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

Read an array from the name file.

This version may use either explicit read or on-deman read (i.e. memory map) depending on the file size and available file pointers.

References ibis::fileManager::getFile(), ibis::gVerbose, and ibis::fileManager::instance().

Referenced by ibis::roster::mergeBlock2(), ibis::bin::mergeValues(), ibis::part::reorderValues(), ibis::category::setDictionary(), and ibis::part::writeValues().

template<class T >
off_t ibis::array_t< T >::read ( const char *  fname,
const off_t  begin,
const off_t  end 
)

Read a portion of the named file.

This version always uses the explicit read function to extract the content of file.

References ibis::gVerbose.

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::adaptive3DBins(), ibis::tafel::append(), ibis::bin::append(), ibis::category::append(), ibis::bin::bin(), ibis::array_t< T >::bottomk(), ibis::colStrings::bottomk(), ibis::bylt::bylt(), ibis::part::calculate(), ibis::part::coarsenBins(), ibis::mesa::construct(), ibis::bitvector64::decompress(), ibis::bitvector::decompress(), ibis::direkte::direkte(), ibis::index::divideCounts(), ibis::tafel::doReserve(), ibis::part::equalWeightBins(), ibis::blob::extractAll(), ibis::blob::extractSome(), ibis::category::fillIndex(), ibis::fuge::fuge(), ibis::fuzz::fuzz(), ibis::part::get2DDistributionI(), ibis::part::getJointDistribution(), ibis::roster::mergeBlock2(), ibis::bin::mergeValues(), ibis::relic::mergeValuesT(), ibis::dictionary::morph(), ibis::tafel::normalize(), 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::selectUBytes(), ibis::bord::column::selectUInts(), ibis::bord::column::selectULongs(), ibis::bord::column::selectUShorts(), ibis::column::selectValuesT(), ibis::index::setBases(), ibis::dictionary::sort(), ibis::array_t< T >::sort(), ibis::util::sortMerge(), ibis::bord::sortStrings(), ibis::bord::sortValues(), ibis::array_t< T >::stableSort(), ibis::array_t< T >::topk(), ibis::colStrings::topk(), ibis::tafel::toTable(), ibis::bitvector64::write(), ibis::bitvector::write(), ibis::zona::zona(), 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::index::addBits(), ibis::part::addColumn(), ibis::bord::column::addCounts(), ibis::bord::column::addIncoreData(), ibis::meshQuery::afind(), ibis::meshQuery::aflatten(), ibis::bitvector64::all0s(), ibis::ridHandler::append(), ibis::direkte::append(), ibis::tafel::append(), ibis::relic::append(), ibis::bin::append(), ibis::category::append(), ibis::bord::append(), ibis::column::appendValues(), ibis::meshQuery::aset(), ibis::bin::binning(), ibis::bin::binningT(), ibis::bin::binOrderT(), ibis::bitvector::bitvector(), ibis::bord::bord(), ibis::bundle0::bundle0(), ibis::bundle1::bundle1(), ibis::bundles::bundles(), ibis::bylt::bylt(), ibis::bitvector64::bytes(), ibis::part::calculate(), ibis::part::coarsenBins(), ibis::mensa::combineCategories(), ibis::bitvector64::compress(), ibis::column::computeMax(), ibis::column::computeMin(), ibis::column::computeSum(), ibis::relic::construct(), ibis::range::construct(), ibis::ambit::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::direkte::direkte(), ibis::bin::divideBitmaps(), ibis::index::divideCounts(), ibis::part::doComp(), ibis::part::doComp0(), ibis::part::doCompare(), ibis::part::doCount(), ibis::part::doScan(), ibis::egale::egale(), ibis::dictionary::equal_to(), ibis::array_t< T >::equal_to(), ibis::part::equalWeightBins(), ibis::direkte::estimate(), ibis::relic::estimate(), ibis::direkte::estimateCost(), ibis::relic::estimateCost(), ibis::keywords::estimateCost(), ibis::bin::estimateCost(), ibis::slice::estimateCost(), ibis::part::estimateMatchAny(), ibis::direkte::evaluate(), ibis::relic::evaluate(), ibis::query::evaluate(), ibis::slice::evaluate(), ibis::fade::evaluate(), ibis::sbiad::evaluate(), ibis::sapid::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::jNatural::fillResult(), ibis::jRange::fillResult(), ibis::table::freeBuffers(), ibis::fromClause::fromClause(), ibis::fuzz::fuzz(), ibis::part::get1DBins_(), ibis::part::get1DDistribution(), ibis::part::get2DDistributionI(), ibis::index::getBitvector(), 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::direkte::getMax(), 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::part::getRIDs(), ibis::query::getRIDs(), ibis::query::getRIDsInBundle(), ibis::bitvector64::getSerialSize(), ibis::category::getString(), ibis::roster::icSearch(), ibis::bitvector64::isCompressed(), ibis::array_t< T >::isSorted(), ibis::selectClause::isUnivariate(), ibis::meshQuery::label2DBlocks(), ibis::meshQuery::label3DBlocks(), ibis::meshQuery::label4DBlocks(), ibis::meshQuery::labelBlocks(), ibis::part::loadIndexes(), ibis::roster::locate(), ibis::roster::locate2(), ibis::index::mapValues(), ibis::bak::mapValues(), ibis::part::mapValues(), ibis::bak2::mapValues(), ibis::dictionary::merge(), ibis::bord::merge0T(), ibis::bord::merge10T(), ibis::bord::merge11T(), ibis::bord::merge20T2(), ibis::bord::merge21T3(), ibis::roster::mergeBlock2(), ibis::bin::mergeValues(), ibis::relic::mergeValuesT(), ibis::dictionary::morph(), ibis::part::negativeCompare(), ibis::tafel::normalize(), ibis::index::numBitvectors(), 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::index::optionalUnpack(), ibis::part::part(), ibis::category::patternSearch(), ibis::bord::column::patternSearch(), ibis::query::printRIDs(), ibis::qDiscreteRange::qDiscreteRange(), ibis::part::quickTest(), ibis::ridHandler::read(), ibis::pale::read(), ibis::pack::read(), ibis::zone::read(), ibis::query::readRIDs(), ibis::query::recordDeltaPairs(), ibis::query::recordEqualPairs(), ibis::colInts::reduce(), ibis::colUInts::reduce(), ibis::colLongs::reduce(), ibis::colULongs::reduce(), ibis::colShorts::reduce(), ibis::colUShorts::reduce(), ibis::colBytes::reduce(), ibis::colUBytes::reduce(), ibis::colFloats::reduce(), ibis::colDoubles::reduce(), ibis::colStrings::reduce(), ibis::relic::relic(), ibis::direkte::remapKeys(), ibis::util::reorder(), ibis::bord::reorder(), ibis::bundles::reorder(), ibis::part::reorder(), ibis::colStrings::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::colInts::segment(), ibis::colUInts::segment(), ibis::colLongs::segment(), ibis::colULongs::segment(), ibis::colShorts::segment(), ibis::colUShorts::segment(), ibis::colBytes::segment(), ibis::colUBytes::segment(), ibis::colFloats::segment(), ibis::colDoubles::segment(), ibis::colStrings::segment(), ibis::jNatural::select(), ibis::jRange::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::text::selectLongs(), ibis::column::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::category::setDictionary(), ibis::query::setRIDs(), ibis::filter::sift2(), ibis::filter::sift2S(), ibis::index::sizeInBytes(), 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::bord::column::stringSearch(), ibis::index::sumBins(), ibis::index::sumBits(), 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::category::fillIndex(), ibis::bord::reorder(), ibis::bundles::reorder(), ibis::part::reorderValues(), ibis::bord::sortValues(), and ibis::bundles::truncate().

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

A stable sort using the provided workspace.

The current content is modified to be in the ascending order. The argument tmp is only used as temporary storage. It uses the merge sort algorithm.

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< uint32_t > &  ind) const

A stable sort that does not modify the current array.

It uses two additional arrays for temporary storage. It uses the merge sort algorithm to produce an index array so that array[ind[i]] would in ascending order.

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< uint32_t > &  ind,
array_t< T > &  sorted 
) const

A stable sort.

It does not change this array, but produces a sorted version in sorted. The content of array ind will be simply moved together with @ this array if it is the same size as this array. Otherwise, it is initialized to consecutive integers starting from 0 before the actual sorting is performed.

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

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 the 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 >
int ibis::array_t< T >::write ( const char *  file) const

Write the content of array to the named file.

Returns 0 for success, a negative number for errors.

References ibis::gVerbose.

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


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