fastjet::ClosestPair2D Class Reference

concrete implementation for finding closest pairs in 2D -- will use Chan's (hopefully efficient) shuffle based structures More...

#include <ClosestPair2D.hh>

Inheritance diagram for fastjet::ClosestPair2D:

[legend]

Collaboration diagram for fastjet::ClosestPair2D:

[legend]

List of all members.

Classes
class	Point
	class for representing all info needed about a point More...
class	Shuffle
	class that will take care of ordering of shuffles for us More...
class	triplet
	since sets of three objects will crop up repeatedly, useful to have a triplet class? More...
Public Member Functions
	ClosestPair2D (const std::vector< Coord2D > &positions, const Coord2D &left_corner, const Coord2D &right_corner)
	constructor from a vector of 2D positions -- number of objects after insertion and deletion must never exceed positions.size(); objects are given IDs that correspond to their index in the vector of positions
	ClosestPair2D (const std::vector< Coord2D > &positions, const Coord2D &left_corner, const Coord2D &right_corner, const unsigned int max_size)
	constructor which allows structure to grow beyond positions.size(), up to max_size
void	closest_pair (unsigned int &ID1, unsigned int &ID2, double &distance2) const
	provides the IDs of the closest pair as well as the distance between them
void	remove (unsigned int ID)
	removes the entry labelled by ID from the object;
unsigned int	insert (const Coord2D &)
	inserts the position into the closest pair structure and returns the ID that has been allocated for the object.
virtual unsigned int	replace (unsigned int ID1, unsigned int ID2, const Coord2D &position)
	removes ID1 and ID2 and inserts position, returning the ID corresponding to position.
virtual void	replace_many (const std::vector< unsigned int > &IDs_to_remove, const std::vector< Coord2D > &new_positions, std::vector< unsigned int > &new_IDs)
	replaces IDs_to_remove with points at the new_positions indicating the IDs allocated to the new points in new_IDs
void	print_tree_depths (std::ostream &outdev) const
unsigned int	size ()
Private Types
typedef SearchTree< Shuffle >	Tree
typedef Tree::circulator	circulator
typedef Tree::const_circulator	const_circulator
Private Member Functions
void	_initialize (const std::vector< Coord2D > &positions, const Coord2D &left_corner, const Coord2D &right_corner, const unsigned int max_size)
void	_add_label (Point *point, unsigned int review_flag)
	add a label to a point as to the nature of review needed (includes adding it to list of points needing review) [doesn't affect other labels already set for the point]
void	_set_label (Point *point, unsigned int review_flag)
	sets the label for the point to be exclusively this review flag (and adds it to list of points needing review if not already there)
void	_deal_with_points_to_review ()
	for all entries of the _points_under_review[] vector, carry out the actions indicated by its review flag; the points are then removed from _points_under_review[] and their flags set to zero
void	_remove_from_search_tree (Point *point_to_remove)
	carry out the search-tree related operations of point removal
void	_insert_into_search_tree (Point *new_point)
	carry out the search-tree related operations of point insertion
void	_point2shuffle (Point &, Shuffle &, unsigned int shift)
	takes a point and creates a shuffle with the given shift
int	_ID (const Point *) const
	returns the ID for the specified point...
Private Attributes
triplet< std::auto_ptr< Tree > >	_trees
std::auto_ptr< MinHeap >	_heap
std::vector< Point >	_points
std::stack< Point * >	_available_points
std::vector< Point * >	_points_under_review
	points that are "under review" in some way
Coord2D	_left_corner
	pieces needed for converting coordinates to integer
double	_range
triplet< unsigned int >	_shifts
triplet< unsigned int >	_rel_shifts
unsigned int	_cp_search_range
Static Private Attributes
static const unsigned int	_nshift = 3
static const unsigned int	_remove_heap_entry = 1
static const unsigned int	_review_heap_entry = 2
static const unsigned int	_review_neighbour = 4

Detailed Description

concrete implementation for finding closest pairs in 2D -- will use Chan's (hopefully efficient) shuffle based structures

Definition at line 46 of file ClosestPair2D.hh.

Member Typedef Documentation

typedef Tree::circulator fastjet::ClosestPair2D::circulator [private]

Definition at line 128 of file ClosestPair2D.hh.

typedef Tree::const_circulator fastjet::ClosestPair2D::const_circulator [private]

Definition at line 129 of file ClosestPair2D.hh.

typedef SearchTree<Shuffle> fastjet::ClosestPair2D::Tree [private]

Definition at line 127 of file ClosestPair2D.hh.

Constructor & Destructor Documentation

fastjet::ClosestPair2D::ClosestPair2D	(	const std::vector< Coord2D > &	positions,
		const Coord2D &	left_corner,
		const Coord2D &	right_corner
	)			`[inline]`

constructor from a vector of 2D positions -- number of objects after insertion and deletion must never exceed positions.size(); objects are given IDs that correspond to their index in the vector of positions

Definition at line 52 of file ClosestPair2D.hh.

00053                                                                            {
00054     _initialize(positions, left_corner, right_corner, positions.size());
00055   };

fastjet::ClosestPair2D::ClosestPair2D	(	const std::vector< Coord2D > &	positions,
		const Coord2D &	left_corner,
		const Coord2D &	right_corner,
		const unsigned int	max_size
	)			`[inline]`

constructor which allows structure to grow beyond positions.size(), up to max_size

Definition at line 59 of file ClosestPair2D.hh.

00061                                              {
00062     _initialize(positions, left_corner, right_corner, max_size);
00063   };

Member Function Documentation

void fastjet::ClosestPair2D::_add_label	(	Point *	point,
		unsigned int	review_flag
	)			`[private]`

add a label to a point as to the nature of review needed (includes adding it to list of points needing review) [doesn't affect other labels already set for the point]

void fastjet::ClosestPair2D::_deal_with_points_to_review ( ) [private]

for all entries of the _points_under_review[] vector, carry out the actions indicated by its review flag; the points are then removed from _points_under_review[] and their flags set to zero

int fastjet::ClosestPair2D::_ID ( const Point * point ) const [inline, private]

returns the ID for the specified point...

Definition at line 220 of file ClosestPair2D.hh.

References _points.

00220                                                        {
00221   return point - &(_points[0]);
00222 }

void fastjet::ClosestPair2D::_initialize	(	const std::vector< Coord2D > &	positions,
		const Coord2D &	left_corner,
		const Coord2D &	right_corner,
		const unsigned int	max_size
	)			`[private]`

void fastjet::ClosestPair2D::_insert_into_search_tree ( Point * new_point ) [private]

carry out the search-tree related operations of point insertion

void fastjet::ClosestPair2D::_point2shuffle	(	Point &	,
		Shuffle &	,
		unsigned int	shift
	)			`[private]`

takes a point and creates a shuffle with the given shift

void fastjet::ClosestPair2D::_remove_from_search_tree ( Point * point_to_remove ) [private]

carry out the search-tree related operations of point removal

void fastjet::ClosestPair2D::_set_label	(	Point *	point,
		unsigned int	review_flag
	)			`[private]`

sets the label for the point to be exclusively this review flag (and adds it to list of points needing review if not already there)

void fastjet::ClosestPair2D::closest_pair	(	unsigned int &	ID1,
		unsigned int &	ID2,
		double &	distance2
	)			const `[virtual]`

provides the IDs of the closest pair as well as the distance between them

Implements fastjet::ClosestPair2DBase.

unsigned int fastjet::ClosestPair2D::insert ( const Coord2D & ) [virtual]

inserts the position into the closest pair structure and returns the ID that has been allocated for the object.

Implements fastjet::ClosestPair2DBase.

void fastjet::ClosestPair2D::print_tree_depths ( std::ostream & outdev ) const [inline]

Definition at line 89 of file ClosestPair2D.hh.

00089                                                            {
00090     outdev    << _trees[0]->max_depth() << " "
00091               << _trees[1]->max_depth() << " "
00092               << _trees[2]->max_depth() << "\n";
00093   };

void fastjet::ClosestPair2D::remove ( unsigned int ID ) [virtual]

removes the entry labelled by ID from the object;

Implements fastjet::ClosestPair2DBase.

virtual unsigned int fastjet::ClosestPair2D::replace	(	unsigned int	ID1,
		unsigned int	ID2,
		const Coord2D &	position
	)			`[virtual]`

removes ID1 and ID2 and inserts position, returning the ID corresponding to position.

..

Reimplemented from fastjet::ClosestPair2DBase.

virtual void fastjet::ClosestPair2D::replace_many	(	const std::vector< unsigned int > &	IDs_to_remove,
		const std::vector< Coord2D > &	new_positions,
		std::vector< unsigned int > &	new_IDs
	)			`[virtual]`

replaces IDs_to_remove with points at the new_positions indicating the IDs allocated to the new points in new_IDs

Reimplemented from fastjet::ClosestPair2DBase.

unsigned int fastjet::ClosestPair2D::size ( ) [inline, virtual]

Implements fastjet::ClosestPair2DBase.

Definition at line 226 of file ClosestPair2D.hh.

References _available_points, and _points.

00226                                         {
00227   return _points.size() - _available_points.size();
00228 }

Member Data Documentation

std::stack<Point *> fastjet::ClosestPair2D::_available_points [private]

Definition at line 135 of file ClosestPair2D.hh.

Referenced by size().

unsigned int fastjet::ClosestPair2D::_cp_search_range [private]

Definition at line 179 of file ClosestPair2D.hh.

std::auto_ptr<MinHeap> fastjet::ClosestPair2D::_heap [private]

Definition at line 133 of file ClosestPair2D.hh.

Coord2D fastjet::ClosestPair2D::_left_corner [private]

pieces needed for converting coordinates to integer

Definition at line 171 of file ClosestPair2D.hh.

const unsigned int fastjet::ClosestPair2D::_nshift = 3 [static, private]

Definition at line 103 of file ClosestPair2D.hh.

std::vector<Point> fastjet::ClosestPair2D::_points [private]

Definition at line 134 of file ClosestPair2D.hh.

Referenced by _ID(), and size().

std::vector<Point *> fastjet::ClosestPair2D::_points_under_review [private]

points that are "under review" in some way

Definition at line 138 of file ClosestPair2D.hh.

double fastjet::ClosestPair2D::_range [private]

Definition at line 172 of file ClosestPair2D.hh.

triplet<unsigned int> fastjet::ClosestPair2D::_rel_shifts [private]

Definition at line 177 of file ClosestPair2D.hh.

const unsigned int fastjet::ClosestPair2D::_remove_heap_entry = 1 [static, private]

Definition at line 141 of file ClosestPair2D.hh.

const unsigned int fastjet::ClosestPair2D::_review_heap_entry = 2 [static, private]

Definition at line 142 of file ClosestPair2D.hh.

const unsigned int fastjet::ClosestPair2D::_review_neighbour = 4 [static, private]

Definition at line 143 of file ClosestPair2D.hh.

triplet<unsigned int> fastjet::ClosestPair2D::_shifts [private]

Definition at line 176 of file ClosestPair2D.hh.

triplet<std::auto_ptr<Tree> > fastjet::ClosestPair2D::_trees [private]

Definition at line 132 of file ClosestPair2D.hh.

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

include/fastjet/internal/ClosestPair2D.hh

fastjet::ClosestPair2D Class Reference

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation