Public Types | Public Member Functions | Static Public Member Functions | List of all members
ibis::array_t< T > Class Template Reference

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

#include <array_t.h>

Public Types

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

Public Member Functions

 array_t ()
 The default constructor. It constructs an empty array.
 
 array_t (size_t n, const T &val)
 Constructor. 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. More...
 
 array_t (ibis::fileManager::storage *rhs, const size_t start, const size_t end)
 Construct an array from a section of the raw storage. More...
 
 array_t (const array_t< T > &rhs)
 Copy constructor. More...
 
 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. More...
 
 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)
 Constructor. Construct an array with n elements.
 
 array_t (const std::vector< T > &rhs)
 Constructor. More...
 
 array_t (const char *fn, const int fdes, const off_t begin, const off_t end)
 Constructor. More...
 
 array_t (T *addr, size_t nelm)
 Constructor. More...
 
 array_t (const array_t< T > &rhs, const size_t begin, const size_t end=0)
 A shallow copy constructor. More...
 
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. More...
 
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. More...
 
void deepCopy (const array_t< T > &rhs)
 The deep copy function. More...
 
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. More...
 
iterator erase (iterator p)
 
iterator erase (iterator i, iterator j)
 
size_t find (const T &) const
 Find the first position where the value is no less than val. More...
 
uint32_t find (const array_t< uint32_t > &, const T &) const
 Find the position of the first element that is no less than val. More...
 
size_t find_upper (const T &) const
 Find the first position where the value is greater than val. More...
 
T & front ()
 
const T & front () const
 
ibis::fileManager::storagegetStorage ()
 Export the actual storage object. More...
 
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. More...
 
bool isSorted (const array_t< uint32_t > &) const
 Verify the index array orders the values in the ascending order. More...
 
void nosharing ()
 Make a non-shared copy of the array. More...
 
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. More...
 
void pop_back ()
 Remove the last element.
 
void print (std::ostream &out) const
 Print out the content of the array to the given output stream. More...
 
void printStatus (std::ostream &out) const
 Print internal pointer addresses.
 
void push_back (const T &elm)
 Add one element from the back. More...
 
void read (const char *)
 Read an array from the name file. More...
 
off_t read (const char *, const off_t, const off_t)
 Read a portion of the named file. More...
 
off_t read (const int, const off_t, const off_t)
 Read an array from a file already open.
 
T * release ()
 Release the memory under management to the caller as a raw pointer. More...
 
void reserve (size_t n)
 Increase the size of the array_t to have the capacity to store at least n elements. More...
 
void resize (size_t n)
 Change the size of the array to have
elements. More...
 
size_t size () const
 
void sort (array_t< uint32_t > &ind) const
 Produce index for ascending order. More...
 
void stableSort (array_t< T > &tmp)
 A stable sort using the provided workspace. More...
 
void stableSort (array_t< uint32_t > &ind) const
 A stable sort that does not modify the current array. More...
 
void stableSort (array_t< uint32_t > &ind, array_t< T > &sorted) const
 A stable sort. More...
 
void swap (array_t< T > &rhs)
 Swap the content of two array_t objects.
 
void topk (uint32_t k, array_t< uint32_t > &ind) const
 Return the positions of the k largest elements. More...
 
void truncate (size_t keep, size_t start)
 Replace the current array with nnew rows. More...
 
int write (const char *) const
 Write the content of array to the named file. More...
 
int write (FILE *fptr) const
 Write the content of the array to a file already opened. More...
 
 ~array_t ()
 !<For difference between pointers.
 

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. More...
 

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().

template<class T>
ibis::array_t< T >::array_t ( const std::vector< T > &  rhs)

Constructor.

Copy the values from a vector to array_t, i.e., deep copy.

References ibis::fileManager::storage::begin(), ibis::fileManager::storage::beginUse(), and ibis::util::copy().

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().

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, i.e., shallow copy.

References ibis::fileManager::storage::beginUse().

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, i.e., shallow copy.

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(), and ibis::fileManager::storage::end().

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().

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().

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

Constructor.

Directly use the raw pointer provided, i.e., shallow copy.

Note
The second argument is the number of elements starting at the given address.
This object does not copy the content at the given address, nor takes the responsibility of freeing the content at the given address. It merely provide a reference to the content at the given address. The caller needs to free the memory after use.

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 then removes any entry that is not in strictly assending order.

Warning
This function uses std::sort to order the values first before removing 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 would 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::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>
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.

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

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.

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.
Warning
Likely to be removed in a future release. Don't rely on this function!

Referenced by ibis::index::activate(), and ibis::bord::column::getRawData().

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::category::fillIndex(), and 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 copying is unnecessary.

If this object is not well-formed, it will be reset to be an empty array.

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

Referenced by ibis::part::doComp(), ibis::part::doCompare(), ibis::bord::column::limit(), 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 >::print ( std::ostream &  out) const

Print out the content of the array to the given output stream.

The elements are given on a single line separated by comas.

Referenced by ibis::index::initOffsets().

template<class T>
void ibis::array_t< T >::push_back ( const T &  elm)
inline

Add one element from the back.

This function allocates new storage under one of the following conditions:

  • the existing storage object is empty or nil,
  • the existing storage object is read-only (i.e., associated with a named file),
  • the existing storage object has no free space for the new data value.

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::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::part::gatherSortKeys(), 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::mensa::mergeCategories(), ibis::bin::mergeValues(), ibis::relic::mergeValuesT(), 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::bord::column::selectBytes(), 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(), ibis::dictionary::writeKeys(), 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(), and ibis::fileManager::instance().

Referenced by ibis::index::activate(), ibis::category::fillIndex(), 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.

template<class T >
T * ibis::array_t< T >::release ( )

Release the memory under management to the caller as a raw pointer.

The caller takes the responsibility to free to memory. This object is emptied.

Referenced by fastbit_iapi_deconstruct_index().

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

Increase the size of the array_t to have the capacity to store at least n elements.

If the current storage object already has n elements, nothing is done, otherwise new storage is allocated. If it fails to allocate new storage, the current array is unchanged. The newly allocated space is not initalized to any specific value.

Note
If the incoming argument is 0, this function will either allocate 32 / sizeof(T) elements if sizeof(T) is less than 32, or 2 elements if sizeof(T) is greater or equal to 32.
If the underlying storage could not be modified (i.e., is read-only), new storage will be allocated regardless of the current available storage. In this case, the newly reserved piece of memory will be at least as large as the existing one.

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

Referenced by ibis::bord::column::addIncoreData(), ibis::bin::binOrderT(), ibis::part::calculate(), ibis::part::doComp(), ibis::part::doCompare(), ibis::tafel::doReserve(), ibis::part::doScan(), ibis::part::equalWeightBins(), ibis::part::gatherSortKeys(), ibis::fromClause::getNames(), ibis::part::getRIDs(), ibis::query::getRIDs(), ibis::direkte::keys(), ibis::part::loadIndexes(), ibis::index::mapValues(), ibis::dictionary::merge(), ibis::bin::mergeValues(), ibis::relic::mergeValuesT(), ibis::qAnyAny::qAnyAny(), ibis::qDiscreteRange::qDiscreteRange(), ibis::ridHandler::read(), ibis::bundles::reorder(), ibis::bin::scanAndPartition(), ibis::jNatural::select(), ibis::jRange::select(), ibis::bord::column::selectBytes(), ibis::blob::selectRawBytes(), ibis::column::selectValuesT(), ibis::index::setBases(), ibis::category::setDictionary(), 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::index::sumBins(), ibis::index::sumBits(), ibis::bundles::truncate(), ibis::bin::write(), ibis::bitvector64::write(), and ibis::bitvector::write().

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

Change the size of the array to have
elements.

If n is greater than its current capacity, it allocates exactly enough space for the new array and copy the existing content to the new space. The existing content is copied while the new elements are left uninitialized. If the user needs to perform a series of resize operations with progressively larger sizes, call the function reserve with the final size to increase the underlying storage and avoid copying the data multiple times.

Note
New space is allocated through the function reserve. The new elements of the array are not initalized. They contain random unspecified values, don't rely their content.

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::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::part::get2DDistributionI(), ibis::part::getJointDistribution(), ibis::bord::column::getValuesArray(), ibis::bord::column::limit(), 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::qAnyAny::qAnyAny(), ibis::qDiscreteRange::qDiscreteRange(), ibis::qIntHod::qIntHod(), ibis::part::quickTest(), ibis::qUIntHod::qUIntHod(), ibis::range::range(), ibis::index::bitmapReader::read(), ibis::dictionary::readKeys2(), ibis::bundle::readRIDs(), ibis::relic::relic(), ibis::part::reorder(), 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::relic::write(), ibis::bin::write(), ibis::direkte::write(), ibis::keywords::write(), 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::index::activate(), 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::column::computeMax(), ibis::column::computeMin(), ibis::column::computeSum(), ibis::relic::construct(), ibis::bin::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::bin::estimateCost(), ibis::keywords::estimateCost(), ibis::skive::estimateCost(), ibis::part::estimateMatchAny(), ibis::direkte::evaluate(), ibis::relic::evaluate(), ibis::query::evaluate(), ibis::skive::evaluate(), ibis::fade::evaluate(), ibis::sbiad::evaluate(), ibis::sapid::evaluate(), ibis::column::evaluateRange(), ibis::bord::column::evaluateRange(), ibis::part::evaluateRIDSet(), ibis::bord::evaluateTerms(), ibis::blob::extractAll(), ibis::blob::extractSome(), ibis::fade::fade(), fastbit_iapi_deconstruct_index(), fastbit_selection_get_coordinates(), 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::util::find(), ibis::table::freeBuffers(), ibis::fromClause::fromClause(), ibis::fuzz::fuzz(), ibis::part::gatherSortKeys(), 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::cursor::getColumnAsOpaque(), ibis::bord::getColumnAsOpaques(), 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::column::getNullMask(), ibis::column::getOpaque(), 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::index::index(), ibis::bitvector64::isCompressed(), ibis::array_t< T >::isSorted(), ibis::selectClause::isUnivariate(), ibis::meshQuery::label2DBlocks(), ibis::meshQuery::label3DBlocks(), ibis::meshQuery::label4DBlocks(), ibis::meshQuery::labelBlocks(), ibis::bord::column::limit(), ibis::part::loadIndexes(), ibis::roster::locate(), ibis::roster::locate2(), ibis::index::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::mensa::mergeCategories(), 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::index::bitmapReader::read(), ibis::pale::read(), ibis::pack::read(), ibis::zone::read(), ibis::query::readRIDs(), ibis::text::readStrings2(), 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::colBlobs::reduce(), ibis::relic::relic(), ibis::direkte::remapKeys(), ibis::util::reorder(), ibis::bord::reorder(), ibis::bundles::reorder(), ibis::part::reorder(), ibis::colStrings::reorder(), ibis::colBlobs::reorder(), ibis::part::reorderBitmap(), ibis::bord::reorderStrings(), ibis::keywords::reorderTerms(), 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::selectOpaques(), ibis::blob::selectRawBytes(), ibis::column::selectShorts(), ibis::bord::column::selectShorts(), 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::index::setBases(), ibis::category::setDictionary(), ibis::part::setMeshShape(), ibis::query::setRIDs(), ibis::filter::sift2(), ibis::filter::sift2S(), ibis::skive::skive(), 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_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::relic::write(), ibis::bin::write(), ibis::direkte::write(), ibis::keywords::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::keywords::reorderTerms(), 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::part::gatherSortKeys(), ibis::query::sortEquiJoin(), ibis::query::sortRangeJoin(), and ibis::array_t< T >::stableSort().

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(), ibis::array_t< T >::resize(), and ibis::array_t< T >::stableSort().

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(), ibis::array_t< T >::resize(), and ibis::array_t< T >::stableSort().

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 >::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.

Referenced by ibis::category::fillIndex(), ibis::category::setDictionary(), ibis::relic::write(), ibis::bin::write(), ibis::keywords::write(), and ibis::query::writeRIDs().

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

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

The content of the array is written out in binary.


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