Public Member Functions | Static Public Member Functions | Protected Member Functions | Static Protected Member Functions
ibis::meshQuery Class Reference

The class adds more functionality to ibis::query to handle data from regular meshes. More...

#include <meshQuery.h>

Inheritance diagram for ibis::meshQuery:
ibis::query

List of all members.

Public Member Functions

int getHitsAsBlocks (std::vector< std::vector< uint32_t > > &reg, const bool merge=false) const
 Translate hit vector into bounding boxes.
int getHitsAsBlocks (std::vector< std::vector< uint32_t > > &reg, const std::vector< uint32_t > &dim, const bool merge=false) const
 This function converts the input bitmap to a list of blocks.
int getHitsAsLines (std::vector< uint32_t > &lines) const
int getHitsAsLines (std::vector< uint32_t > &lines, const std::vector< uint32_t > &dim) const
 Convert the hit vector into a list of line segments.
int getPointsOnBoundary (std::vector< std::vector< uint32_t > > &bdy, const std::vector< uint32_t > &dim) const
 Determine points with neighbors that are not hits.
int getPointsOnBoundary (std::vector< std::vector< uint32_t > > &bdy) const
 Determine points with neighbors that are not hits.
 meshQuery (const char *uid, const part *et, const char *pref=0)
 Constructor for building a new query.
 meshQuery (const char *dir, const ibis::partList &tl)
 Constructor for recoverying from crash.

Static Public Member Functions

static int bitvectorToCoordinates (const ibis::bitvector &bv, const std::vector< uint32_t > &dim, std::vector< uint32_t > &coords)
 Convert positions in a bit vector to mesh coordinates.
static int labelBlocks (const std::vector< std::vector< uint32_t > > &blocks, std::vector< uint32_t > &labels)
 Assign a unique labels to each connected set of blocks.
static int labelLines (uint32_t nd, const std::vector< uint32_t > &lines, std::vector< uint32_t > &labels)
 Assign each connected component a unique label.

Protected Member Functions

void block2d (uint32_t last, const std::vector< uint32_t > &dim, std::vector< uint32_t > &block, std::vector< std::vector< uint32_t > > &reg) const
 Deal with one (single) 2D block.
void block3d (uint32_t last, const uint32_t n2, const uint32_t n3, const std::vector< uint32_t > &dim, std::vector< uint32_t > &block, std::vector< std::vector< uint32_t > > &reg) const
 Deal with one (single) 3D block.
void blocknd (uint32_t last, const std::vector< uint32_t > &scl, const std::vector< uint32_t > &dim, std::vector< uint32_t > &block, std::vector< std::vector< uint32_t > > &reg) const
 Deal with one (single) N-Dimensional block.
void boundary2d (const std::vector< uint32_t > &dim, const std::vector< std::vector< uint32_t > > &rang, std::vector< std::vector< uint32_t > > &bdy) const
void boundary2d1 (const std::vector< uint32_t > &dim, const std::vector< std::vector< uint32_t > > &rang, std::vector< std::vector< uint32_t > > &bdy) const
void boundary3d (const std::vector< uint32_t > &dim, const std::vector< std::vector< uint32_t > > &rang, std::vector< std::vector< uint32_t > > &bdy) const
void boundarynd (const std::vector< uint32_t > &dim, const std::vector< std::vector< uint32_t > > &rang, std::vector< std::vector< uint32_t > > &bdy) const
int findPointsOnBoundary (const ibis::bitvector &bv, const std::vector< uint32_t > &dim, std::vector< std::vector< uint32_t > > &bdy) const
int linesIn1D (std::vector< uint32_t > &lines) const
 Convert the hits into line segements on a 1-D mesh.
int linesIn2D (std::vector< uint32_t > &lines, const std::vector< uint32_t > &dim) const
 Convert the hits into line segments on a 2-D mesh.
int linesIn3D (std::vector< uint32_t > &lines, const std::vector< uint32_t > &dim) const
 Convert hits into line segments in 3-D.
int linesIn4D (std::vector< uint32_t > &lines, const std::vector< uint32_t > &dim) const
 Convert hits into line segments in 4-D.
int linesInND (std::vector< uint32_t > &lines, const std::vector< uint32_t > &dim) const
 Convert hits into line segments in a regular mesh of any dimension.
void merge2DBlocks (std::vector< std::vector< uint32_t > > &reg) const
 Merge 2D blocks.
void merge3DBlocks (std::vector< std::vector< uint32_t > > &reg) const
 Merge 3D blocks.
void mergeNDBlocks (std::vector< std::vector< uint32_t > > &reg) const
 Merge n-D blocks.
int toBlocks1 (const ibis::bitvector &bv, std::vector< std::vector< uint32_t > > &reg) const
 Convert a bitvector into 1-D blocks.
int toBlocks2 (const ibis::bitvector &bv, const std::vector< uint32_t > &dim, std::vector< std::vector< uint32_t > > &reg) const
 Convert a bitvector to a list of 2-D blocks.
int toBlocks3 (const ibis::bitvector &bv, const std::vector< uint32_t > &dim, std::vector< std::vector< uint32_t > > &reg) const
 Convert a bitvector to a list of 3-D blocks.
int toBlocksN (const ibis::bitvector &bv, const std::vector< uint32_t > &dim, std::vector< std::vector< uint32_t > > &reg) const
 Convert a bitvector to a list of n-D blocks.

Static Protected Member Functions

static uint32_t afind (ibis::array_t< uint32_t > &rep, uint32_t s)
 The array-based find operation.
static uint32_t aflatten (ibis::array_t< uint32_t > &rep)
 Flatten the array-based union-find data strucutre.
static void aset (ibis::array_t< uint32_t > &rep, uint32_t s, uint32_t r)
 Reset all nodes from s to the root to directly point to node r.
static int label1DBlocks (const std::vector< std::vector< uint32_t > > &blocks, std::vector< uint32_t > &labels)
 Assign labels to blocks on a 1D mesh.
static int label2DBlocks (const std::vector< std::vector< uint32_t > > &blocks, std::vector< uint32_t > &labels)
 Assign labels to blocks on 2D regular mesh.
static int label3DBlocks (const std::vector< std::vector< uint32_t > > &blocks, std::vector< uint32_t > &labels)
 Assign a unique labels to each connected set of blocks.
static int label4DBlocks (const std::vector< std::vector< uint32_t > > &blocks, std::vector< uint32_t > &labels)
 Assign a unique labels to each connected set of blocks.
static int labelLines1 (const std::vector< uint32_t > &lines, std::vector< uint32_t > &labels)
 Label line segements on a 1D mesh.
static int labelLines2 (const std::vector< uint32_t > &lines, std::vector< uint32_t > &labels)
static int labelLines3 (const std::vector< uint32_t > &lines, std::vector< uint32_t > &labels)
static int labelLines4 (const std::vector< uint32_t > &lines, std::vector< uint32_t > &labels)
static int labelLinesN (uint32_t nd, const std::vector< uint32_t > &lines, std::vector< uint32_t > &labels)

Detailed Description

The class adds more functionality to ibis::query to handle data from regular meshes.

The new functions treats cells of meshes as connected regions in space.


Member Function Documentation

uint32_t ibis::meshQuery::afind ( ibis::array_t< uint32_t > &  rep,
uint32_t  s 
) [static, protected]

The array-based find operation.

This is the find operation of the implicit union-find data structur that uses the array rep to represent the union-find data structure. Starting a node s, it returns the root of the union-find tree containing s.

Note:
The incoming value of s is used as the position in array rep. If the value of s is too large to be a valid position in rep, its value is immediately returned, which is equivalent to indicating the node is the root of a tree.
The path from s to the root is compressed in this function, i.e., all nodes from s to the root will point directly to the root at the conclusion of this function.
See also:
http://crd.lbl.gov/~kewu/ps/LBNL-59102.html

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

uint32_t ibis::meshQuery::aflatten ( ibis::array_t< uint32_t > &  rep) [static, protected]

Flatten the array-based union-find data strucutre.

It also compress all labels to be consecutive integers starting from 0. It returns the number of unique labels used.

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

void ibis::meshQuery::aset ( ibis::array_t< uint32_t > &  rep,
uint32_t  s,
uint32_t  r 
) [static, protected]

Reset all nodes from s to the root to directly point to node r.

This is the path-compression operation of the implicit union-find data structure.

In the implicit union-find data structure, the values s1 and s2 are used as positions in array rep. If the array is too small, this function extends rep so that the newly created trees all have only a single node each.

Note:
The union and find operations are to be implemented with a combination of afind and aset. For example, the find operation with path-compress can be implemented with a call to afind followed by a call to aset; the union operation can be implemented with two calls to afind followed by two calls to aset.
See also:
http://crd.lbl.gov/~kewu/ps/LBNL-59102.html

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

int ibis::meshQuery::bitvectorToCoordinates ( const ibis::bitvector bv,
const std::vector< uint32_t > &  dim,
std::vector< uint32_t > &  coords 
) [static]

Convert positions in a bit vector to mesh coordinates.

It converts the positions of bits that are 1 to coordinates in a regular mesh with deminsions given in dim. The C-sytle array ordering is assumed.

References ibis::bitvector::cnt(), ibis::gVerbose, ibis::bitvector::indexSet::nIndices(), and ibis::bitvector::size().

void ibis::meshQuery::block2d ( uint32_t  last,
const std::vector< uint32_t > &  dim,
std::vector< uint32_t > &  block,
std::vector< std::vector< uint32_t > > &  reg 
) const [protected]

Deal with one (single) 2D block.

The last block generated is not recorded, other blocks generated here are recorded in reg.

int ibis::meshQuery::getHitsAsBlocks ( std::vector< std::vector< uint32_t > > &  reg,
const bool  merge = false 
) const

Translate hit vector into bounding boxes.

This variant of getHitsAsBlocks uses the dimensions defined by ibis::table::getMeshShape().

See also:
ibis::meshQuery::getHitsAsBlocks
ibis::table::getMeshShape

References ibis::gVerbose, ibis::horometer::realTime(), ibis::horometer::resume(), ibis::horometer::start(), and ibis::horometer::stop().

int ibis::meshQuery::getHitsAsBlocks ( std::vector< std::vector< uint32_t > > &  reg,
const std::vector< uint32_t > &  dim,
const bool  merge = false 
) const

This function converts the input bitmap to a list of blocks.

The bitmap is assumed to be a mapping of a regular mesh with dimensions specified in variable dim. A row-major ordering (C style multiple dimensional arrays, NOT Fortran style) is assumed, that is the slowest varying dimension is dim[0].

Parameters:
regThe return value that contains the list of blocks as hypercubes. Following the convention of typical C/C++ indexing scheme, the lower bounds of the blocks are inclusive and the upper bounds of the blocks are exclusive. For example, a 2D block [2, 3, 5, 10] covers points with coordinates [2, 5], [2, 6], [2, 7], [2, 8] and [2, 9]. This is an example of a line segment with five points. This function may generate hypercubes of any shape or size. In general, the lower and upper bounds of each dimension is specified together, where the lower bound is inclusive but the upper bound is exclusive.
dimThe size of the mesh. The value dim.size() is the number of dimensions. Input argument, not modified.
mergeAn optional argument. If true, will attempt to merge line segments generated to form larger hypercubes. Default to false because it make take a significant amount of time to merge the blocks.

This function returns an integer value with the following definition.

  • 0 -- conversion succeeded (no warning)
  • -1 -- the bitvector length does not match the product of values in dim
  • -2 -- product of values in dim overflows an unsigned integer
  • -3 -- no hit vector to work with
  • -4 -- array dim is empty
Note:
It can only be called after the functions estimate or evaluate have been called. The blocks computed after calling estimate may be smaller than that computed after calling evaluate becaue estimate may not generate the exact answer to the query.

References ibis::gVerbose, ibis::horometer::realTime(), ibis::horometer::resume(), ibis::horometer::start(), and ibis::horometer::stop().

int ibis::meshQuery::getHitsAsLines ( std::vector< uint32_t > &  lines,
const std::vector< uint32_t > &  dim 
) const

Convert the hit vector into a list of line segments.

The underlying data is assumed to be defined a simple regular mesh. The shape of the mesh is defined by the argument dim, where dim[0] is the slowest varying dimension. A line segment here is a group of nodes sharing the same coordinates in all dimensions expected the fastest varying one and having consecutive coordiantes in the fastest varying dimension. Each line segement is represented by (dim.size()+1) consecutive values in the array lines. The first (dim.size()-1) values are the shared coordinates in the first (dim.size()-1) dimensions, element dim.size() is the coordinate of the first node in dimension dim.size() and the last element is the coordinate of the point just beyond the last node in the line segement. For example, on a 2D mesh, the line segment (11, 2, 5) contains three nodes with the coordinates (11, 2), (11, 3) and (11, 4). On a 3D mesh, the line segment (4, 8, 1, 3) contains two points with coordinates (4, 8, 1) and (4, 8, 2).

References ibis::gVerbose, ibis::horometer::realTime(), ibis::horometer::start(), and ibis::horometer::stop().

int ibis::meshQuery::getPointsOnBoundary ( std::vector< std::vector< uint32_t > > &  bdy,
const std::vector< uint32_t > &  dim 
) const

Determine points with neighbors that are not hits.

Assume the records are a linearization of points on a simple regular mesh, the function getPointsOnBoundary computes all points that satisfy the conditions specified by function setWhereClause but have at least one neighboring mesh point that does not satisfy the conditions.

Parameters:
bdyThe return value that contains the list of points.
dimThe size of the mesh. The value dim.size() is the number of dimensions. Each element of bdy is a std::vector with the same size as dim.
See also:
ibis::meshQuery::getHitsAsBlocks
Note:
The inner array has the same number of elements as argument dim and the dimensions are ordered the same way as in dim as well. All functions in this class assumes that the mesh points are linearized using a raster scan order where dim[0] varies the slowest.

References ibis::gVerbose, ibis::horometer::realTime(), ibis::horometer::resume(), ibis::horometer::start(), and ibis::horometer::stop().

int ibis::meshQuery::getPointsOnBoundary ( std::vector< std::vector< uint32_t > > &  bdy) const

Determine points with neighbors that are not hits.

The variant of getPointsOnBoundary use dimensions returned by ibis::table::getMeshShape().

See also:
ibis::meshQuery::getPointsOnBoundary
ibis::table::getMeshShape

References ibis::gVerbose, ibis::horometer::realTime(), ibis::horometer::resume(), ibis::horometer::start(), and ibis::horometer::stop().

int ibis::meshQuery::label1DBlocks ( const std::vector< std::vector< uint32_t > > &  blocks,
std::vector< uint32_t > &  labels 
) [static, protected]

Assign labels to blocks on a 1D mesh.

A node on this 1D mesh is assumed to connected to its two immediate neighbors. Furthermore, it assumes that the blocks are sorted and do not overlap. The only error condition checked by this function is that the first block must have at least two numbers. If this this not true, it returns -1. There are two other error conditions that are not check: failure to allocate enough space for the array labels and memory access error cuased by some blocks having less than 2 values.

References ibis::gVerbose.

int ibis::meshQuery::label2DBlocks ( const std::vector< std::vector< uint32_t > > &  blocks,
std::vector< uint32_t > &  labels 
) [static, protected]

Assign labels to blocks on 2D regular mesh.

A node on this mesh is assumed to connect to its four nearest neighbors. The blocks are assumed to be in ascending order. Furthermore, the blocks are constructed in such way that if two blocks are connected along the second (the faster varying) dimension, they would be absorbed into a single block. This simplifies the processing of blocks in this function.

Returns:
This function returns the number of connected components identified if it runs to completion. Otherwise, it returns a negative number to indicate error.

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

int ibis::meshQuery::label3DBlocks ( const std::vector< std::vector< uint32_t > > &  blocks,
std::vector< uint32_t > &  labels 
) [static, protected]

Assign a unique labels to each connected set of blocks.

It assumes the incoming blocks are defined on a simple regular 3D mesh, presumably outputted from ibis::meshQuery::getHitsAsBlocks. This function checks that first block has at least 6 numbers. Failure to pass this minimal test will cause this function to return a negative code. If some of the blocks does not have 6 numbers it may cause memory access errors that are not checked by this function. It further assumes that the blocks are organized in ascending order. If it detects any block out of order, it will return with an error code (-2).

This function assumes the nearest neighbors along each of the three dimensions are connected. This is the minimum connectivity.

Returns:
Upon successful completion of this function, it returns the number of connected components identified. It returns a negative value to indicate errors.

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

int ibis::meshQuery::label4DBlocks ( const std::vector< std::vector< uint32_t > > &  blocks,
std::vector< uint32_t > &  labels 
) [static, protected]

Assign a unique labels to each connected set of blocks.

It assumes the incoming blocks are defined on a simple regular mesh, presumably outputted from ibis::meshQuery::getHitsAsBlocks. This function works with a mesh with four dimensions only. The bounding box produced are expected to be produced from ibis::meshQuery::getHitsAsBlocks, where each box uses two numbers (an inclusive lower bound and an exclusive upper bound) for each dimension. However, this function only check the number of values of the first bounding box; it does not check the sizes of remaining blocks. It is happy to proceed if the first bounding box has at least eight values, otherwise an error code is returned. It further assumes that the blocks are organized in ascending order. If it detects any block out of order, it will return with an error code (-2).

This function assumes the nearest neighbors along each of the three dimensions are connected. This is the minimum connectivity.

Returns:
Upon successful completion of this function, it returns the number of connected components identified. It returns a negative value to indicate errors.

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

int ibis::meshQuery::labelBlocks ( const std::vector< std::vector< uint32_t > > &  blocks,
std::vector< uint32_t > &  labels 
) [static]

Assign a unique labels to each connected set of blocks.

It assumes the incoming blocks are defined on a simple regular mesh, presumably outputted from ibis::meshQuery::getHitsAsBlocks. This function works with a mesh with an arbitrary number of dimensions. The bounding box produced are expected to be produced from ibis::meshQuery::getHitsAsBlocks, where each box uses two numbers (an inclusive lower bound and an exclusive upper bound) for each dimension. However, this function determines the number of dimensions based on the size of the first bounding box; it does not check the sizes of remaining blocks. It further assumes that the blocks are organized in ascending order. If it detects any block out of order, it will return with an error code (-2).

This function assumes the nearest neighbors along each of the three dimensions are connected. This is the minimum connectivity.

Returns:
Upon successful completion of this function, it returns the number of connected components identified. It returns a negative value to indicate errors. There are two likely exceptional conditions not monitored by this function: failure to allocate enough space for array labels and memory access failure due to some blocks actually having less than expected number of elements.

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

int ibis::meshQuery::labelLines ( uint32_t  nd,
const std::vector< uint32_t > &  lines,
std::vector< uint32_t > &  labels 
) [static]

Assign each connected component a unique label.

This version works with query lines. It assumes the underlying mesh is a simple nd-dimensional mesh with nearest neighbors on each dimension connected to each other.

The input lines are assumed to be produced by ibis::meshQuery::getHitsAsLines. In particular, it assumes the query lines are in ascending order of their start coordinates. Any violation of this ordering will treated as an input error.

It returns the number of connected components identified upon successful completion. Otherwise, it returns a negative number to indicate error.

References ibis::gVerbose.

void ibis::meshQuery::merge2DBlocks ( std::vector< std::vector< uint32_t > > &  reg) const [protected]

Merge 2D blocks.

Blocks with one dimension that has connecting coordinates and the same coordinates on all other dimensions can be merged.

Assumptions/requirements: (1) the incoming reg is assumed to be sorted. (2) no dimension reaches the maximum value of UINT_MAX, which is used to denote a invalid block to be removed.


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