source: trunk/SISCone/hash.cc

Last change on this file was 20, checked in by Pavel Demin, 16 years ago

add SISCone library

File size: 7.1 KB
Line 
1///////////////////////////////////////////////////////////////////////////////
2// File: hash.cpp //
3// Description: source file for classes hash_element and hash_cones //
4// This file is part of the SISCone project. //
5// For more details, see http://projects.hepforge.org/siscone //
6// //
7// Copyright (c) 2006 Gavin Salam and Gregory Soyez //
8// //
9// This program is free software; you can redistribute it and/or modify //
10// it under the terms of the GNU General Public License as published by //
11// the Free Software Foundation; either version 2 of the License, or //
12// (at your option) any later version. //
13// //
14// This program is distributed in the hope that it will be useful, //
15// but WITHOUT ANY WARRANTY; without even the implied warranty of //
16// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the //
17// GNU General Public License for more details. //
18// //
19// You should have received a copy of the GNU General Public License //
20// along with this program; if not, write to the Free Software //
21// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA //
22// //
23// $Revision: 1.1 $//
24// $Date: 2008-10-02 15:20:26 $//
25///////////////////////////////////////////////////////////////////////////////
26
27#include <math.h>
28#include <stdio.h>
29#include "hash.h"
30#include <iostream>
31
32namespace siscone{
33
34using namespace std;
35
36/**************************************************************
37 * implementation of hash_cones *
38 * list of cones candidates. *
39 * We store in this class all the hash_elements and give *
40 * functions to manipulate them. *
41 **************************************************************/
42
43// constructor with initialisation
44// - _Np number of particles
45// - _R2 cone radius (squared)
46//-----------------------------------
47hash_cones::hash_cones(int _Np, double _R2){
48 int i;
49
50 n_cones = 0;
51
52 // determine hash size
53 mask = 1 << (int) (2*log(double(_Np))/log(2.0));
54 if (mask<=1) mask=2;
55
56 // create hash
57 hash_array = new hash_element*[mask];
58 mask--;
59
60 // set the array to 0
61 //? needed ?
62 for (i=0;i<mask+1;i++)
63 hash_array[i] = NULL;
64
65 R2 = _R2;
66}
67
68// destructor
69//------------
70hash_cones::~hash_cones(){
71 int i;
72 hash_element *elm;
73
74 for (i=0;i<mask+1;i++){
75 while (hash_array[i]!=NULL){
76 elm = hash_array[i];
77 hash_array[i] = hash_array[i]->next;
78 delete elm;
79 }
80 }
81
82 delete[] hash_array;
83}
84
85
86/*
87 * insert a new candidate into the hash.
88 * - v 4-momentum of the cone to add
89 * - parent parent particle defining the cone
90 * - child child particle defining the cone
91 * - p_io whether the parent has to belong to the cone or not
92 * - c_io whether the child has to belong to the cone or not
93 * return 0 on success, 1 on error
94 ***********************************************************************/
95int hash_cones::insert(Cmomentum *v, Cmomentum *parent, Cmomentum *child, bool p_io, bool c_io){
96 hash_element *elm;
97 int index = (v->ref.ref[0]) & mask;
98
99 // check the array cell corresponding to our reference
100 elm = hash_array[index];
101 do{
102 // if it is not present, add it
103 if (elm==NULL){
104 // create element
105 elm = new hash_element;
106
107 // set its varibles
108 // Note: at this level, eta and phi have already been computed
109 // through Cmomentum::build_etaphi.
110 elm->ref = v->ref;
111
112 //compute vectors centre
113 v->build_etaphi();
114 elm->eta = v->eta;
115 elm->phi = v->phi;
116 // if at least one of the two is_inside tests gives a result != from the expected,
117 // the || will be true hence !(...) false as wanted
118 elm->is_stable = !((is_inside(v, parent)^p_io)||(is_inside(v, child)^c_io));
119 //cout << "-- new status of " << v->ref[0] << ":" << elm->is_stable << endl;
120
121 // update hash
122 elm->next = hash_array[index];
123 hash_array[index] = elm;
124
125 n_cones++;
126 return 0;
127 }
128
129 // if the cone is already there, simply update stability status
130 if (v->ref == elm->ref){
131 // there is only an update to perform to see if the cone is still stable
132 if (elm->is_stable){
133 v->build_etaphi();
134 elm->is_stable = !((is_inside(v, parent)^p_io)||(is_inside(v, child)^c_io));
135 //cout << " parent/child: "
136 // << parent->ref[0] << ":" << is_inside(v, parent) << ":" << p_io << " "
137 // << child->ref[0] << ":" << is_inside(v, child) << ":" << c_io << endl;
138 //cout << "-- rep status of " << v->ref[0] << ":" << elm->is_stable << endl;
139 //cout << v->eta << " " << v->phi << endl;
140 //cout << (child->eta) << " " << child->phi << endl;
141 }
142 return 0;
143 }
144
145 elm = elm->next;
146 } while (1);
147
148 return 1;
149}
150
151/*
152 * insert a new candidate into the hash.
153 * - v 4-momentum of te cone to add
154 * Note, in this case, we assume stability. We also assume
155 * that eta and phi are computed for v
156 * return 0 on success, 1 on error
157 ***********************************************************************/
158int hash_cones::insert(Cmomentum *v){
159 hash_element *elm;
160 int index = (v->ref.ref[0]) & mask;
161 //cout << "-- stable candidate: " << v->ref[0] << ":" << endl;
162
163 // check the array cell corresponding to our reference
164 elm = hash_array[index];
165 do{
166 // if it is not present, add it
167 if (elm==NULL){
168 // create element
169 elm = new hash_element;
170
171 // set its varibles
172 // Note: at this level, eta and phi have already been computed
173 // through Cmomentum::build_etaphi.
174 elm->ref = v->ref;
175 elm->eta = v->eta;
176 elm->phi = v->phi;
177 elm->is_stable = true;
178
179 // update hash
180 elm->next = hash_array[index];
181 hash_array[index] = elm;
182
183 n_cones++;
184 return 0;
185 }
186
187 // if the cone is already there, we have nothing to do
188 if (v->ref == elm->ref){
189 return 0;
190 }
191
192 elm = elm->next;
193 } while (1);
194
195 return 1;
196}
197
198/*
199 * test if a particle is inside a cone of given centre.
200 * check if the particle of coordinates 'v' is inside the circle of radius R
201 * centered at 'centre'.
202 * - centre centre of the circle
203 * - v particle to test
204 * return true if inside, false if outside
205 ******************************************************************************/
206inline bool hash_cones::is_inside(Cmomentum *centre, Cmomentum *v){
207 double dx, dy;
208
209 dx = centre->eta - v->eta;
210 dy = fabs(centre->phi - v->phi);
211 if (dy>M_PI)
212 dy -= 2.0*M_PI;
213
214 return dx*dx+dy*dy<R2;
215}
216
217}
Note: See TracBrowser for help on using the repository browser.