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

__begin	begin of data
__end	end of data
match	binary match operator
Nmin	minimum cluster size

Returns

end of data

Definition at line 43 of file JAlgorithm.hh.

    {
      return (*this)(__begin, std::distance(__begin,__end), match, Nmin, typename std::iterator_traits<JHitIterator_t>::iterator_category());
    }

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

__begin	begin of data
__end	end of data
comparator	comparator
match	binary match operator

Returns

end of data

Definition at line 65 of file JAlgorithm.hh.

    {
      if (__begin != __end) {

        std::sort(__begin, __end, comparator);

        JHitIterator_t root = __begin;

        return std::partition(++__begin, __end, JBind2nd(match, *root));

      } else {

        return __end;
      }
    }

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

buffer	pointer to data
N	number of hits
match	binary match operator
Nmin	minimum cluster size
tag	iterator tag

Returns

pointer to end of data

Definition at line 96 of file JAlgorithm.hh.

    {
      using namespace std;

      if (N >= Nmin) {

        int i, j;
        int n = N;

        // Determine number of associated hits for each hit.

        count.resize(N);

        for (vector<int>::iterator __i = count.begin(); __i != count.end(); ++__i) {
          *__i = 1;                        // Assume always a match with itself.
        }

        for (i = 0; i != N; ++i) {
          for (j = i; ++j != N; ) {
            if (match(buffer[i], buffer[j])) {
              ++count[i];
              ++count[j];
            }
          }
        }

        // Remove hit with the smallest number of associated hits.
        // This procedure stops when:
        // 1) number of associated hits is equal to the number of (remaining) hits or
        // 2) maximal number of associated hits is less than the specified minimum.

        for ( ; ; ) {
      
          int M = (count[0] >= Nmin ? 1 : 0);
      
          j = 0;

          for (i = 1; i != n; ++i) {
            if (count[i] < count[j]) {
              j = i;
            }
            if (count[i] >= Nmin) {
              ++M;
            }
          }
      
          // Ready?

          if (count[j] == n) {
            return buffer + n;
          }

          if (M < Nmin) {
            return buffer;
          }
      
          // Reduce effective size.

          --n;
      
          // Swap the selected hit to end.

          swap(buffer[j], buffer[n]); 
          swap(count [j], count [n]);

          // Decrease number of associated hits for each associated hit.

          for (i = 0; i != n && count[n] != 1; ++i) {
            if (match(buffer[i], buffer[n])) {
              --count[i];
              --count[n];
            }
          }
        }
      }

      return buffer;
    }

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:

• JAlgorithm.hh