ClosestPair2D

Inheritance diagram for ClosestPair2D:

Collaboration diagram for ClosestPair2D:

Classes
class	Point
class	Shuffle
class	triplet

Public Member Functions
	ClosestPair2D (const std::vector< Coord2D > &positions, const Coord2D &left_corner, const Coord2D &right_corner)
	ClosestPair2D (const std::vector< Coord2D > &positions, const Coord2D &left_corner, const Coord2D &right_corner, const unsigned int max_size)
void	closest_pair (unsigned int &ID1, unsigned int &ID2, double &distance2) const
void	remove (unsigned int ID)
unsigned int	insert (const Coord2D &)
virtual unsigned int	replace (unsigned int ID1, unsigned int ID2, const Coord2D &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)
void	print_tree_depths (std::ostream &outdev) const
unsigned int	size ()
Public Member Functions inherited from ClosestPair2DBase
virtual	~ClosestPair2DBase ()

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)
void	_set_label (Point *point, unsigned int review_flag)
void	_deal_with_points_to_review ()
void	_remove_from_search_tree (Point *point_to_remove)
void	_insert_into_search_tree (Point *new_point)
void	_point2shuffle (Point &, Shuffle &, unsigned int shift)
int	_ID (const Point *) const

Private Attributes
triplet< SharedPtr< Tree > >	_trees
SharedPtr< MinHeap >	_heap
std::vector< Point >	_points
std::stack< Point * >	_available_points
std::vector< Point * >	_points_under_review
Coord2D	_left_corner
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

Member Typedef Documentation

circulator

typedef Tree::circulator circulator

private

const_circulator

typedef Tree::const_circulator const_circulator

private

Tree

typedef SearchTree<Shuffle> Tree

private

Constructor & Destructor Documentation

ClosestPair2D() [1/2]

ClosestPair2D ( const std::vector< Coord2D > &  positions, const Coord2D &  left_corner, const Coord2D &  right_corner  )

inline

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

ClosestPair2D() [2/2]

ClosestPair2D ( const std::vector< Coord2D > &  positions, const Coord2D &  left_corner, const Coord2D &  right_corner, const unsigned int  max_size  )

inline

                                     {
    _initialize(positions, left_corner, right_corner, max_size);
  };

Member Function Documentation

_add_label()

void _add_label ( Point *  point, unsigned int  review_flag  )

inlineprivate

                                                                             {
  if (point->review_flag == 0) _points_under_review.push_back(point);
  point->review_flag |= review_flag;
}

_deal_with_points_to_review()

void _deal_with_points_to_review ( )

private

                                                {
  unsigned int CP_range = min(_cp_search_range, size()-1);
  while(_points_under_review.size() > 0) {
    Point * this_point = _points_under_review.back();
    _points_under_review.pop_back();
    if (this_point->review_flag & _remove_heap_entry) {
      assert(!(this_point->review_flag ^ _remove_heap_entry));
      _heap->remove(_ID(this_point));
    }
    else {
      if (this_point->review_flag & _review_neighbour) {
    this_point->neighbour_dist2 = numeric_limits<double>::max();
    // among all three shifts
    for (unsigned int ishift = 0; ishift < _nshift; ishift++) {
      circulator other = this_point->circ[ishift];
      // among points within CP_range
      for (unsigned i=0; i < CP_range; i++) {
        ++other;
        double dist2 = this_point->distance2(*other->point);
        if (dist2 < this_point->neighbour_dist2) {
          this_point->neighbour_dist2 = dist2;
          this_point->neighbour       = other->point;
        }
      }
    }
      }
      _heap->update(_ID(this_point), this_point->neighbour_dist2);
    }
    this_point->review_flag = 0;
  }
}

_ID()

int _ID ( const Point *  point ) const

inlineprivate

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

_initialize()

void _initialize ( const std::vector< Coord2D > &  positions, const Coord2D &  left_corner, const Coord2D &  right_corner, const unsigned int  max_size  )

private

                                        {
  unsigned int n_positions = positions.size();
  assert(max_size >= n_positions);
  _points.resize(max_size);
  for (unsigned int i = n_positions; i < max_size; i++) {
    _available_points.push(&(_points[i]));
  }
  _left_corner = left_corner;
  _range       = max((right_corner.x - left_corner.x),
             (right_corner.y - left_corner.y));
  vector<Shuffle> shuffles(n_positions);
  for (unsigned int i = 0; i < n_positions; i++) {
    _points[i].coord = positions[i];
    _points[i].neighbour_dist2 = numeric_limits<double>::max();
    _points[i].review_flag = 0;
    _point2shuffle(_points[i], shuffles[i], 0);
  }
  for (unsigned ishift = 0; ishift < _nshift; ishift++) {
   _shifts[ishift] = static_cast<unsigned int>(((twopow31*1.0)*ishift)/_nshift);
    if (ishift == 0) {_rel_shifts[ishift] = 0;}
    else {_rel_shifts[ishift] = _shifts[ishift] - _shifts[ishift-1];}
  }
  _cp_search_range = 30;
  _points_under_review.reserve(_nshift * _cp_search_range);
  for (unsigned int ishift = 0; ishift < _nshift; ishift++) {
    if (ishift > 0) {
      unsigned rel_shift = _rel_shifts[ishift];
      for (unsigned int i = 0; i < shuffles.size(); i++) {
    shuffles[i] += rel_shift; }
    }
    sort(shuffles.begin(), shuffles.end());
    _trees[ishift] = SharedPtr<Tree>(new Tree(shuffles, max_size));
    circulator circ = _trees[ishift]->somewhere(), start=circ;
    unsigned int CP_range = min(_cp_search_range, n_positions-1);
    do {
      Point * this_point = circ->point;
      this_point->circ[ishift] = circ;
      circulator other = circ;
      for (unsigned i=0; i < CP_range; i++) {
    ++other;
    double dist2 = this_point->distance2(*other->point);
    if (dist2 < this_point->neighbour_dist2) {
      this_point->neighbour_dist2 = dist2;
      this_point->neighbour       = other->point;
    }
      }
    } while (++circ != start);
  }
  vector<double> mindists2(n_positions);
  for (unsigned int i = 0; i < n_positions; i++) {
    mindists2[i] = _points[i].neighbour_dist2;}
  _heap = SharedPtr<MinHeap>(new MinHeap(mindists2, max_size));
}

_insert_into_search_tree()

void _insert_into_search_tree ( Point *  new_point )

private

                                                              {
  _set_label(new_point, _review_heap_entry);
  new_point->neighbour_dist2 = numeric_limits<double>::max();
  unsigned int CP_range = min(_cp_search_range, size()-1);
  for (unsigned ishift = 0; ishift < _nshift; ishift++) {
    Shuffle new_shuffle;
    _point2shuffle(*new_point, new_shuffle, _shifts[ishift]);
    circulator new_circ = _trees[ishift]->insert(new_shuffle);
    new_point->circ[ishift] = new_circ;
    circulator right_edge = new_circ; right_edge++;
    circulator left_edge  = new_circ;
    for (unsigned int i = 0; i < CP_range; i++) {left_edge--;}
    do {
      Point * left_point  = left_edge->point;
      Point * right_point = right_edge->point;
      double new_dist2 = left_point->distance2(*new_point);
      if (new_dist2 < left_point->neighbour_dist2) {
    left_point->neighbour_dist2 = new_dist2;
    left_point->neighbour       = new_point;
    _add_label(left_point, _review_heap_entry);
      }
      new_dist2 = new_point->distance2(*right_point);
      if (new_dist2 < new_point->neighbour_dist2) {
    new_point->neighbour_dist2 = new_dist2;
    new_point->neighbour = right_point;
      }
      if (left_point->neighbour == right_point) {
    _add_label(left_point, _review_neighbour);
      }
      right_edge++;
    } while (++left_edge != new_circ);
  }
}

_point2shuffle()

void _point2shuffle ( Point &  point, Shuffle &  shuffle, unsigned int  shift  )

private

                                      {
  Coord2D renorm_point = (point.coord - _left_corner)/_range;
  assert(renorm_point.x >=0);
  assert(renorm_point.x <=1);
  assert(renorm_point.y >=0);
  assert(renorm_point.y <=1);
  shuffle.x = static_cast<unsigned int>(twopow31 * renorm_point.x) + shift;
  shuffle.y = static_cast<unsigned int>(twopow31 * renorm_point.y) + shift;
  shuffle.point = &point;
}

_remove_from_search_tree()

void _remove_from_search_tree ( Point *  point_to_remove )

private

                                                                    {
  _available_points.push(point_to_remove);
  _set_label(point_to_remove, _remove_heap_entry);
  unsigned int CP_range = min(_cp_search_range, size()-1);
  for (unsigned int ishift = 0; ishift < _nshift; ishift++) {
    circulator removed_circ = point_to_remove->circ[ishift];
    circulator right_end = removed_circ.next();
    _trees[ishift]->remove(removed_circ);
    circulator left_end  = right_end, orig_right_end = right_end;
    for (unsigned int i = 0; i < CP_range; i++) {left_end--;}
    if (size()-1 < _cp_search_range) {
      left_end--; right_end--;
    }
    do {
      Point * left_point = left_end->point;
      if (left_point->neighbour == point_to_remove) {
    // we'll deal with it later...
    _add_label(left_point, _review_neighbour);
      } else {
    // check to see if right point has become its closest neighbour
    double dist2 = left_point->distance2(*right_end->point);
    if (dist2 < left_point->neighbour_dist2) {
      left_point->neighbour = right_end->point;
      left_point->neighbour_dist2 = dist2;
      // NB: (LESSER) REVIEW NEEDED HERE TOO...
      _add_label(left_point, _review_heap_entry);
    }
      }
      ++right_end;
    } while (++left_end != orig_right_end);
  } // ishift...
}

_set_label()

void _set_label ( Point *  point, unsigned int  review_flag  )

inlineprivate

                                                                             {
  if (point->review_flag == 0) _points_under_review.push_back(point);
  point->review_flag = review_flag;
}

closest_pair()

void closest_pair ( unsigned int &  ID1, unsigned int &  ID2, double &  distance2  ) const

virtual

Implements ClosestPair2DBase.

                                           {
  ID1 = _heap->minloc();
  ID2 = _ID(_points[ID1].neighbour);
  distance2 = _points[ID1].neighbour_dist2;
  if (ID1 > ID2) std::swap(ID1,ID2);
}

insert()

unsigned int insert ( const Coord2D &  new_coord )

virtual

Implements ClosestPair2DBase.

                                                            {
  assert(_available_points.size() > 0);
  Point * new_point = _available_points.top();
  _available_points.pop();
  new_point->coord = new_coord;
  _insert_into_search_tree(new_point);
  _deal_with_points_to_review();
  return _ID(new_point);
}

print_tree_depths()

void print_tree_depths ( std::ostream &  outdev ) const

inline

                                                           {
    outdev    << _trees[0]->max_depth() << " "
          << _trees[1]->max_depth() << " "
          << _trees[2]->max_depth() << "\n";
  };

remove()

void remove ( unsigned int  ID )

virtual

Implements ClosestPair2DBase.

                                          {
  Point * point_to_remove = & (_points[ID]);
  _remove_from_search_tree(point_to_remove);
  _deal_with_points_to_review();
}

replace()

unsigned int replace ( unsigned int  ID1, unsigned int  ID2, const Coord2D &  position  )

virtual

Reimplemented from ClosestPair2DBase.

                                              {
  Point * point_to_remove = & (_points[ID1]);
  _remove_from_search_tree(point_to_remove);
  point_to_remove = & (_points[ID2]);
  _remove_from_search_tree(point_to_remove);
  Point * new_point = _available_points.top();
  _available_points.pop();
  new_point->coord = position;
  _insert_into_search_tree(new_point);
  _deal_with_points_to_review();
  return _ID(new_point);
}

replace_many()

void replace_many ( const std::vector< unsigned int > &  IDs_to_remove, const std::vector< Coord2D > &  new_positions, std::vector< unsigned int > &  new_IDs  )

virtual

Reimplemented from ClosestPair2DBase.

                                             {
  for (unsigned int i = 0; i < IDs_to_remove.size(); i++) {
    _remove_from_search_tree(& (_points[IDs_to_remove[i]]));
  }
  new_IDs.resize(0);
  for (unsigned int i = 0; i < new_positions.size(); i++) {
    Point * new_point = _available_points.top();
    _available_points.pop();
    new_point->coord = new_positions[i];
    _insert_into_search_tree(new_point);
    new_IDs.push_back(_ID(new_point));
  }
  _deal_with_points_to_review();
}

size()

unsigned int size ( )

inlinevirtual

Implements ClosestPair2DBase.

                                        {
  return _points.size() - _available_points.size();
}

Member Data Documentation

_available_points

std::stack<Point *> _available_points

private

_cp_search_range

unsigned int _cp_search_range

private

_heap

SharedPtr<MinHeap> _heap

private

_left_corner

Coord2D _left_corner

private

_nshift

const unsigned int _nshift = 3

staticprivate

_points

std::vector<Point> _points

private

_points_under_review

std::vector<Point *> _points_under_review

private

_range

double _range

private

_rel_shifts

triplet<unsigned int> _rel_shifts

private

_remove_heap_entry

const unsigned int _remove_heap_entry = 1

staticprivate

_review_heap_entry

const unsigned int _review_heap_entry = 2

staticprivate

_review_neighbour

const unsigned int _review_neighbour = 4

staticprivate

_shifts

triplet<unsigned int> _shifts

private

_trees

triplet<SharedPtr<Tree> > _trees

private

---

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

• /builds/cms-analysis/general/DasAnalysisSystem/Core/Installer/Core/JetObservables/src/fjcore.cc