queso-0.53.0
Public Member Functions | Private Attributes | List of all members
ANNbd_shrink Class Reference

#include <bd_tree.h>

Inheritance diagram for ANNbd_shrink:
Inheritance graph
[legend]
Collaboration diagram for ANNbd_shrink:
Collaboration graph
[legend]

Public Member Functions

 ANNbd_shrink (int nb, ANNorthHSArray bds, ANNkd_ptr ic=NULL, ANNkd_ptr oc=NULL)
 
 ~ANNbd_shrink ()
 
virtual void getStats (int dim, ANNkdStats &st, ANNorthRect &bnd_box)
 
virtual void print (int level, ostream &out)
 
virtual void dump (ostream &out)
 
virtual void ann_search (ANNdist)
 
virtual void ann_pri_search (ANNdist)
 
virtual void ann_FR_search (ANNdist)
 
- Public Member Functions inherited from ANNkd_node
virtual ~ANNkd_node ()
 

Private Attributes

int n_bnds
 
ANNorthHSArray bnds
 
ANNkd_ptr child [2]
 

Detailed Description

Definition at line 61 of file bd_tree.h.

Constructor & Destructor Documentation

ANNbd_shrink::ANNbd_shrink ( int  nb,
ANNorthHSArray  bds,
ANNkd_ptr  ic = NULL,
ANNkd_ptr  oc = NULL 
)
inline

Definition at line 67 of file bd_tree.h.

References ANN_IN, ANN_OUT, bnds, child, and n_bnds.

71  {
72  n_bnds = nb; // cutting dimension
73  bnds = bds; // assign bounds
74  child[ANN_IN] = ic; // set children
75  child[ANN_OUT] = oc;
76  }
ANN_OUT
Definition: ANNx.h:46
ANN_IN
Definition: ANNx.h:46
ANNbd_shrink::n_bnds
int n_bnds
Definition: bd_tree.h:63
ANNbd_shrink::child
ANNkd_ptr child[2]
Definition: bd_tree.h:65
ANNbd_shrink::bnds
ANNorthHSArray bnds
Definition: bd_tree.h:64
ANNbd_shrink::~ANNbd_shrink ( )
inline

Definition at line 78 of file bd_tree.h.

References ANN_IN, ANN_OUT, bnds, child, and KD_TRIVIAL.

79  {
80  if (child[ANN_IN]!= NULL && child[ANN_IN]!= KD_TRIVIAL)
81  delete child[ANN_IN];
82  if (child[ANN_OUT]!= NULL&& child[ANN_OUT]!= KD_TRIVIAL)
83  delete child[ANN_OUT];
84  if (bnds != NULL)
85  delete [] bnds; // delete bounds
86  }
ANN_OUT
Definition: ANNx.h:46
ANN_IN
Definition: ANNx.h:46
KD_TRIVIAL
ANNkd_leaf * KD_TRIVIAL
Definition: kd_tree.cpp:50
ANNbd_shrink::child
ANNkd_ptr child[2]
Definition: bd_tree.h:65
ANNbd_shrink::bnds
ANNorthHSArray bnds
Definition: bd_tree.h:64

Member Function Documentation

void ANNbd_shrink::ann_FR_search ( ANNdist  box_dist)
virtual

Implements ANNkd_node.

Definition at line 39 of file bd_fix_rad_search.cpp.

References ANN_FLOP, ANNkd_node::ann_FR_search(), ANN_IN, ANN_OUT, ANN_SHR, ANN_SUM, ANNkdFRQ, ANNmaxPtsVisited, ANNptsVisited, bnds, child, and n_bnds.

40 {
41  // check dist calc term cond.
42  if (ANNmaxPtsVisited != 0 && ANNptsVisited > ANNmaxPtsVisited) return;
43 
44  ANNdist inner_dist = 0; // distance to inner box
45  for (int i = 0; i < n_bnds; i++) { // is query point in the box?
46  if (bnds[i].out(ANNkdFRQ)) { // outside this bounding side?
47  // add to inner distance
48  inner_dist = (ANNdist) ANN_SUM(inner_dist, bnds[i].dist(ANNkdFRQ));
49  }
50  }
51  if (inner_dist <= box_dist) { // if inner box is closer
52  child[ANN_IN]->ann_FR_search(inner_dist);// search inner child first
53  child[ANN_OUT]->ann_FR_search(box_dist);// ...then outer child
54  }
55  else { // if outer box is closer
56  child[ANN_OUT]->ann_FR_search(box_dist);// search outer child first
57  child[ANN_IN]->ann_FR_search(inner_dist);// ...then outer child
58  }
59  ANN_FLOP(3*n_bnds) // increment floating ops
60  ANN_SHR(1) // one more shrinking node
61 }
ANNkd_node::ann_FR_search
virtual void ann_FR_search(ANNdist)=0
ANN_OUT
Definition: ANNx.h:46
ANN_IN
Definition: ANNx.h:46
ANN_SUM
#define ANN_SUM(x, y)
Definition: ANN.h:362
ANNptsVisited
int ANNptsVisited
Definition: ANN.cpp:191
ANN_SHR
#define ANN_SHR(n)
Definition: ANNperf.h:134
ANN_FLOP
#define ANN_FLOP(n)
Definition: ANNperf.h:131
ANNdist
double ANNdist
Definition: ANN.h:159
ANNbd_shrink::n_bnds
int n_bnds
Definition: bd_tree.h:63
ANNkdFRQ
ANNpoint ANNkdFRQ
Definition: kd_fix_rad_search.cpp:46
ANNbd_shrink::child
ANNkd_ptr child[2]
Definition: bd_tree.h:65
ANNbd_shrink::bnds
ANNorthHSArray bnds
Definition: bd_tree.h:64
ANNmaxPtsVisited
int ANNmaxPtsVisited
Definition: ANN.cpp:190
void ANNbd_shrink::ann_pri_search ( ANNdist  box_dist)
virtual

Implements ANNkd_node.

Definition at line 39 of file bd_pr_search.cpp.

References ANN_FLOP, ANN_IN, ANN_OUT, ANNkd_node::ann_pri_search(), ANN_SHR, ANN_SUM, ANNprBoxPQ, ANNprQ, bnds, child, ANNpr_queue::insert(), KD_TRIVIAL, and n_bnds.

40 {
41  ANNdist inner_dist = 0; // distance to inner box
42  for (int i = 0; i < n_bnds; i++) { // is query point in the box?
43  if (bnds[i].out(ANNprQ)) { // outside this bounding side?
44  // add to inner distance
45  inner_dist = (ANNdist) ANN_SUM(inner_dist, bnds[i].dist(ANNprQ));
46  }
47  }
48  if (inner_dist <= box_dist) { // if inner box is closer
49  if (child[ANN_OUT] != KD_TRIVIAL) // enqueue outer if not trivial
50  ANNprBoxPQ->insert(box_dist,child[ANN_OUT]);
51  // continue with inner child
52  child[ANN_IN]->ann_pri_search(inner_dist);
53  }
54  else { // if outer box is closer
55  if (child[ANN_IN] != KD_TRIVIAL) // enqueue inner if not trivial
56  ANNprBoxPQ->insert(inner_dist,child[ANN_IN]);
57  // continue with outer child
58  child[ANN_OUT]->ann_pri_search(box_dist);
59  }
60  ANN_FLOP(3*n_bnds) // increment floating ops
61  ANN_SHR(1) // one more shrinking node
62 }
ANNprQ
ANNpoint ANNprQ
Definition: kd_pr_search.cpp:77
ANNpr_queue::insert
void insert(PQkey kv, PQinfo inf)
Definition: pr_queue.h:84
ANNprBoxPQ
ANNpr_queue * ANNprBoxPQ
Definition: kd_pr_search.cpp:80
ANN_OUT
Definition: ANNx.h:46
ANN_IN
Definition: ANNx.h:46
ANN_SUM
#define ANN_SUM(x, y)
Definition: ANN.h:362
ANN_SHR
#define ANN_SHR(n)
Definition: ANNperf.h:134
KD_TRIVIAL
ANNkd_leaf * KD_TRIVIAL
Definition: kd_tree.cpp:50
ANN_FLOP
#define ANN_FLOP(n)
Definition: ANNperf.h:131
ANNkd_node::ann_pri_search
virtual void ann_pri_search(ANNdist)=0
ANNdist
double ANNdist
Definition: ANN.h:159
ANNbd_shrink::n_bnds
int n_bnds
Definition: bd_tree.h:63
ANNbd_shrink::child
ANNkd_ptr child[2]
Definition: bd_tree.h:65
ANNbd_shrink::bnds
ANNorthHSArray bnds
Definition: bd_tree.h:64
void ANNbd_shrink::ann_search ( ANNdist  box_dist)
virtual

Implements ANNkd_node.

Definition at line 39 of file bd_search.cpp.

References ANN_FLOP, ANN_IN, ANN_OUT, ANNkd_node::ann_search(), ANN_SHR, ANN_SUM, ANNkdQ, ANNmaxPtsVisited, ANNptsVisited, bnds, child, and n_bnds.

40 {
41  // check dist calc term cond.
42  if (ANNmaxPtsVisited != 0 && ANNptsVisited > ANNmaxPtsVisited) return;
43 
44  ANNdist inner_dist = 0; // distance to inner box
45  for (int i = 0; i < n_bnds; i++) { // is query point in the box?
46  if (bnds[i].out(ANNkdQ)) { // outside this bounding side?
47  // add to inner distance
48  inner_dist = (ANNdist) ANN_SUM(inner_dist, bnds[i].dist(ANNkdQ));
49  }
50  }
51  if (inner_dist <= box_dist) { // if inner box is closer
52  child[ANN_IN]->ann_search(inner_dist); // search inner child first
53  child[ANN_OUT]->ann_search(box_dist); // ...then outer child
54  }
55  else { // if outer box is closer
56  child[ANN_OUT]->ann_search(box_dist); // search outer child first
57  child[ANN_IN]->ann_search(inner_dist); // ...then outer child
58  }
59  ANN_FLOP(3*n_bnds) // increment floating ops
60  ANN_SHR(1) // one more shrinking node
61 }
ANNkd_node::ann_search
virtual void ann_search(ANNdist)=0
ANN_OUT
Definition: ANNx.h:46
ANN_IN
Definition: ANNx.h:46
ANN_SUM
#define ANN_SUM(x, y)
Definition: ANN.h:362
ANNptsVisited
int ANNptsVisited
Definition: ANN.cpp:191
ANN_SHR
#define ANN_SHR(n)
Definition: ANNperf.h:134
ANN_FLOP
#define ANN_FLOP(n)
Definition: ANNperf.h:131
ANNdist
double ANNdist
Definition: ANN.h:159
ANNbd_shrink::n_bnds
int n_bnds
Definition: bd_tree.h:63
ANNkdQ
ANNpoint ANNkdQ
Definition: kd_search.cpp:80
ANNbd_shrink::child
ANNkd_ptr child[2]
Definition: bd_tree.h:65
ANNbd_shrink::bnds
ANNorthHSArray bnds
Definition: bd_tree.h:64
ANNmaxPtsVisited
int ANNmaxPtsVisited
Definition: ANN.cpp:190
void ANNbd_shrink::dump ( ostream &  out)
virtual

Implements ANNkd_node.

Definition at line 159 of file kd_dump.cpp.

References ANN_IN, and ANN_OUT.

161 {
162  out << "shrink " << n_bnds << "\n";
163  for (int j = 0; j < n_bnds; j++) {
164  out << bnds[j].cd << " " << bnds[j].cv << " " << bnds[j].sd << "\n";
165  }
166  child[ANN_IN]->dump(out); // print in-child
167  child[ANN_OUT]->dump(out); // print out-child
168 }
ANNkd_node::dump
virtual void dump(ostream &out)=0
ANN_OUT
Definition: ANNx.h:46
ANN_IN
Definition: ANNx.h:46
ANNorthHalfSpace::cv
ANNcoord cv
Definition: ANNx.h:135
ANNbd_shrink::n_bnds
int n_bnds
Definition: bd_tree.h:63
ANNbd_shrink::child
ANNkd_ptr child[2]
Definition: bd_tree.h:65
ANNbd_shrink::bnds
ANNorthHSArray bnds
Definition: bd_tree.h:64
void ANNbd_shrink::getStats ( int  dim,
ANNkdStats &  st,
ANNorthRect &  bnd_box 
)
virtual

Implements ANNkd_node.

Definition at line 71 of file bd_tree.cpp.

References ANN_IN, ANN_OUT, annBnds2Box(), bnds, child, ANNkdStats::depth, ANNkd_node::getStats(), ANNkdStats::merge(), n_bnds, ANNkdStats::n_shr, and ANNkdStats::reset().

75 {
76  ANNkdStats ch_stats; // stats for children
77  ANNorthRect inner_box(dim); // inner box of shrink
78 
79  annBnds2Box(bnd_box, // enclosing box
80  dim, // dimension
81  n_bnds, // number of bounds
82  bnds, // bounds array
83  inner_box); // inner box (modified)
84  // get stats for inner child
85  ch_stats.reset(); // reset
86  child[ANN_IN]->getStats(dim, ch_stats, inner_box);
87  st.merge(ch_stats); // merge them
88  // get stats for outer child
89  ch_stats.reset(); // reset
90  child[ANN_OUT]->getStats(dim, ch_stats, bnd_box);
91  st.merge(ch_stats); // merge them
92 
93  st.depth++; // increment depth
94  st.n_shr++; // increment number of shrinks
95 }
ANNkdStats::depth
int depth
Definition: ANNperf.h:54
ANN_OUT
Definition: ANNx.h:46
ANN_IN
Definition: ANNx.h:46
ANNkdStats::reset
void reset(int d=0, int n=0, int bs=0)
Definition: ANNperf.h:59
ANNkdStats::n_shr
int n_shr
Definition: ANNperf.h:53
ANNbd_shrink::n_bnds
int n_bnds
Definition: bd_tree.h:63
annBnds2Box
void annBnds2Box(const ANNorthRect &bnd_box, int dim, int n_bnds, ANNorthHSArray bnds, ANNorthRect &inner_box)
Definition: kd_util.cpp:426
dim
int dim
Definition: ann2fig.cpp:81
ANNkdStats::merge
void merge(const ANNkdStats &st)
Definition: kd_tree.cpp:133
ANNbd_shrink::child
ANNkd_ptr child[2]
Definition: bd_tree.h:65
ANNkd_node::getStats
virtual void getStats(int dim, ANNkdStats &st, ANNorthRect &bnd_box)=0
ANNbd_shrink::bnds
ANNorthHSArray bnds
Definition: bd_tree.h:64
void ANNbd_shrink::print ( int  level,
ostream &  out 
)
virtual

Implements ANNkd_node.

Definition at line 41 of file bd_tree.cpp.

References ANN_IN, ANN_OUT, bnds, ANNorthHalfSpace::cd, child, n_bnds, ANNkd_node::print(), and ANNorthHalfSpace::sd.

44 {
45  child[ANN_OUT]->print(level+1, out); // print out-child
46 
47  out << " ";
48  for (int i = 0; i < level; i++) // print indentation
49  out << "..";
50  out << "Shrink";
51  for (int j = 0; j < n_bnds; j++) { // print sides, 2 per line
52  if (j % 2 == 0) {
53  out << "\n"; // newline and indentation
54  for (int i = 0; i < level+2; i++) out << " ";
55  }
56  out << " ([" << bnds[j].cd << "]"
57  << (bnds[j].sd > 0 ? ">=" : "< ")
58  << bnds[j].cv << ")";
59  }
60  out << "\n";
61 
62  child[ANN_IN]->print(level+1, out); // print in-child
63 }
ANN_OUT
Definition: ANNx.h:46
ANN_IN
Definition: ANNx.h:46
ANNkd_node::print
virtual void print(int level, ostream &out)=0
ANNbd_shrink::n_bnds
int n_bnds
Definition: bd_tree.h:63
ANNbd_shrink::child
ANNkd_ptr child[2]
Definition: bd_tree.h:65
ANNbd_shrink::bnds
ANNorthHSArray bnds
Definition: bd_tree.h:64

Member Data Documentation

ANNorthHSArray ANNbd_shrink::bnds
private

Definition at line 64 of file bd_tree.h.

Referenced by ann_FR_search(), ann_pri_search(), ann_search(), ANNbd_shrink(), getStats(), print(), and ~ANNbd_shrink().

ANNkd_ptr ANNbd_shrink::child[2]
private

Definition at line 65 of file bd_tree.h.

Referenced by ann_FR_search(), ann_pri_search(), ann_search(), ANNbd_shrink(), getStats(), print(), and ~ANNbd_shrink().

int ANNbd_shrink::n_bnds
private

Definition at line 63 of file bd_tree.h.

Referenced by ann_FR_search(), ann_pri_search(), ann_search(), ANNbd_shrink(), getStats(), and print().

The documentation for this class was generated from the following files:
Generated on Thu Jun 11 2015 13:52:33 for queso-0.53.0 by  doxygen 1.8.5