Jpp  18.0.0-rc.2
the software that should make you happy
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Public Member Functions | Private Member Functions | Private Attributes | List of all members
JTRIGGER::clusterize Struct Reference

Anonymous structure for clustering of hits. More...

#include <JAlgorithm.hh>

Public Member Functions

template<class JHitIterator_t , class JMatch_t >
JHitIterator_t operator() (JHitIterator_t __begin, JHitIterator_t __end, const JMatch_t &match, const int Nmin=1) const
 Partition data according given binary match operator. More...
 
template<class JHitIterator_t , class JComparator_t , class JMatch_t >
JHitIterator_t operator() (JHitIterator_t __begin, JHitIterator_t __end, const JComparator_t &comparator, const JMatch_t &match) const
 Select best root hit according given comparator and partition remaining data according given binary match operator and this root hit. More...
 

Private Member Functions

template<class JHitIterator_t , class JMatch_t >
JHitIterator_t operator() (JHitIterator_t buffer, const int N, const JMatch_t &match, const int Nmin, std::random_access_iterator_tag tag) const
 Implementation of method clusterize for random access iterators. More...
 

Private Attributes

std::vector< int > count
 

Detailed Description

Anonymous structure for clustering of hits.

Definition at line 23 of file JAlgorithm.hh.

Member Function Documentation

template<class JHitIterator_t , class JMatch_t >
JHitIterator_t JTRIGGER::clusterize::operator() ( JHitIterator_t  __begin,
JHitIterator_t  __end,
const JMatch_t &  match,
const int  Nmin = 1 
) const
inline

Partition data according given binary match operator.

The underlying algorithm is known in literature as 'clique'. The result is (likely to be) the maximal sub-set with all elements matched to each other. The complexity is quadratic, i.e. at most (number of elements x number of elements) operations. The algorithm will sort the data such that all clusterized hits are at the front. The return value points the first non clusterized hit.

The hit iterator refers to a data structure which should conform with the match operator.

Parameters
__beginbegin of data
__endend of data
matchbinary match operator
Nminminimum cluster size
Returns
end of data

Definition at line 43 of file JAlgorithm.hh.

47  {
48  return (*this)(__begin, std::distance(__begin,__end), match, Nmin, typename std::iterator_traits<JHitIterator_t>::iterator_category());
49  }
std::vector< T >::difference_type distance(typename std::vector< T >::const_iterator first, typename PhysicsEvent::const_iterator< T > second)
Specialisation of STL distance.
template<class JHitIterator_t , class JComparator_t , class JMatch_t >
JHitIterator_t JTRIGGER::clusterize::operator() ( JHitIterator_t  __begin,
JHitIterator_t  __end,
const JComparator_t &  comparator,
const JMatch_t &  match 
) const
inline

Select best root hit according given comparator and partition remaining data according given binary match operator and this root hit.

The complexity is linear, i.e. at most number of elements operations. The algorithm will sort the data such that all selected hits are at the front.

Parameters
__beginbegin of data
__endend of data
comparatorcomparator
matchbinary match operator
Returns
end of data

Definition at line 65 of file JAlgorithm.hh.

69  {
70  if (__begin != __end) {
71 
72  std::sort(__begin, __end, comparator);
73 
74  JHitIterator_t root = __begin;
75 
76  return std::partition(++__begin, __end, JBind2nd(match, *root));
77 
78  } else {
79 
80  return __end;
81  }
82  }
JBinder2nd< JHit_t > JBind2nd(const JMatch< JHit_t > &match, const JHit_t &second)
Auxiliary method to create JBinder2nd object.
Definition: JBind2nd.hh:66
do JPlot2D f $WORKDIR detector root
template<class JHitIterator_t , class JMatch_t >
JHitIterator_t JTRIGGER::clusterize::operator() ( JHitIterator_t  buffer,
const int  N,
const JMatch_t &  match,
const int  Nmin,
std::random_access_iterator_tag  tag 
) const
inlineprivate

Implementation of method clusterize for random access iterators.

Parameters
bufferpointer to data
Nnumber of hits
matchbinary match operator
Nminminimum cluster size
tagiterator tag
Returns
pointer to end of data

Definition at line 96 of file JAlgorithm.hh.

101  {
102  using namespace std;
103 
104  if (N >= Nmin) {
105 
106  int i, j;
107  int n = N;
108 
109  // Determine number of associated hits for each hit.
110 
111  count.resize(N);
112 
113  for (vector<int>::iterator __i = count.begin(); __i != count.end(); ++__i) {
114  *__i = 1; // Assume always a match with itself.
115  }
116 
117  for (i = 0; i != N; ++i) {
118  for (j = i; ++j != N; ) {
119  if (match(buffer[i], buffer[j])) {
120  ++count[i];
121  ++count[j];
122  }
123  }
124  }
125 
126  // Remove hit with the smallest number of associated hits.
127  // This procedure stops when:
128  // 1) number of associated hits is equal to the number of (remaining) hits or
129  // 2) maximal number of associated hits is less than the specified minimum.
130 
131  for ( ; ; ) {
132 
133  int M = (count[0] >= Nmin ? 1 : 0);
134 
135  j = 0;
136 
137  for (i = 1; i != n; ++i) {
138  if (count[i] < count[j]) {
139  j = i;
140  }
141  if (count[i] >= Nmin) {
142  ++M;
143  }
144  }
145 
146  // Ready?
147 
148  if (count[j] == n) {
149  return buffer + n;
150  }
151 
152  if (M < Nmin) {
153  return buffer;
154  }
155 
156  // Reduce effective size.
157 
158  --n;
159 
160  // Swap the selected hit to end.
161 
162  swap(buffer[j], buffer[n]);
163  swap(count [j], count [n]);
164 
165  // Decrease number of associated hits for each associated hit.
166 
167  for (i = 0; i != n && count[n] != 1; ++i) {
168  if (match(buffer[i], buffer[n])) {
169  --count[i];
170  --count[n];
171  }
172  }
173  }
174  }
175 
176  return buffer;
177  }
const int n
Definition: JPolint.hh:697
std::vector< int > count
Definition: JAlgorithm.hh:180
then usage $script< input file >[option[primary[working directory]]] nWhere option can be N
Definition: JMuonPostfit.sh:36
int j
Definition: JPolint.hh:703

Member Data Documentation

std::vector<int> JTRIGGER::clusterize::count
mutableprivate

Definition at line 180 of file JAlgorithm.hh.


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