ROOT logo
/**************************************************************************
* Copyright(c) 1998-1999, ALICE Experiment at CERN, All rights reserved. *
*                                                                        *
* Author: The ALICE Off-line Project.                                    *
* Contributors are mentioned in the code where appropriate.              *
*                                                                        *
* Permission to use, copy, modify and distribute this software and its   *
* documentation strictly for non-commercial purposes is hereby granted   *
* without fee, provided that the above copyright notice appears in all   *
* copies and that both the copyright notice and this permission notice   *
* appear in the supporting documentation. The authors make no claims     *
* about the suitability of this software for any purpose. It is          *
* provided "as is" without express or implied warranty.                  *
**************************************************************************/

// $Id$

/// \class AliMUONNode
/// 
/// A node of a segment tree
///
/// For the details of the meaning of cardinality and potent data
/// members, please see Diane L. Souvaine and Iliana Bjorling-Sachs,
/// Proceedings of the IEEE, Vol. 80, No. 9, September 1992, p. 1449
///
/// 
/// \author Laurent Aphecetche, Subatech

#include "AliMUONNode.h"

#include "AliLog.h"
#include "AliMUONSegment.h"
#include "Riostream.h"
#include "TMath.h"
#include "TObjArray.h"
#include "TString.h"

using std::cout;
using std::endl;
///\cond CLASSIMP
ClassImp(AliMUONNode)
///\endcond

//_____________________________________________________________________________
AliMUONNode::AliMUONNode(Double_t a, Double_t b, Double_t midpoint)
: fLeftNode(0x0), fRightNode(0x0), fMin(a), fMax(b), fMidPoint(midpoint), fC(0), fP(0)
{
  /// ctor
}

//_____________________________________________________________________________
AliMUONNode::~AliMUONNode()
{
  /// dtor
  delete fLeftNode;
  delete fRightNode;
}

//_____________________________________________________________________________
void 
AliMUONNode::Print(const char* opt) const
{
  /// Printout
  cout << opt << Form("[%7.2f,%7.2f]",fMin,fMax);
  if ( !TMath::IsNaN(fMidPoint) ) cout << Form(" (%7.2f)",fMidPoint);
  cout << endl;
  
  TString sopt(opt);
  sopt += "   ";
  
  if ( fLeftNode ) 
  {
    fLeftNode->Print(sopt.Data());
  }
  if ( fRightNode ) 
  {
    fRightNode->Print(sopt.Data());
  }
}

//_____________________________________________________________________________
void 
AliMUONNode::Contribution(Double_t b, Double_t e, TObjArray& stack)
{
  /// Contribution of an edge (b,e) to the final contour
  if ( fMax < fMin ) 
  {
    AliError(Form("fMax(%10.5f) < fMin(%10.5f",fMax,fMin));
  }
  
  if ( fC == 0 ) 
  {
    if ( IsFullyContained(b,e) && fP == 0 ) 
    {
      AliMUONSegment* back = static_cast<AliMUONSegment*>(stack.Last());

      if ( back && AliMUONSegment::AreEqual(back->EndY(),fMin) )
      {
        // merge to existing segment
        Double_t y(back->StartY());
        back->Set(0.0,y,0.0,fMax);
      }
      else
      {
        // add a new segment
        stack.Add(new AliMUONSegment(0.0,fMin,0.0,fMax));
      }
    }
    else
    {
      if ( b < fMidPoint ) 
      {
        fLeftNode->Contribution(b,e,stack);
      }
      if ( fMidPoint < e ) 
      {
        fRightNode->Contribution(b,e,stack);
      }
    }
  }
}

//_____________________________________________________________________________
Bool_t 
AliMUONNode::IsFullyContained(Double_t b, Double_t e) const
{
  /// Whether this node's interval is fully contained into [b,e]
  
  return ( ( b < fMin || AliMUONSegment::AreEqual(b,fMin) ) && ( fMax < e || AliMUONSegment::AreEqual(e,fMax)) );
}

//_____________________________________________________________________________
void 
AliMUONNode::InsertInterval(Double_t b, Double_t e, TObjArray& stack)
{
  /// Insert an interval
  if ( IsFullyContained(b,e) ) 
  {
    C(1);
  }
  else
  {
    if ( b < fMidPoint ) 
    {
      fLeftNode->InsertInterval(b,e,stack);
    }
    if ( fMidPoint <  e ) 
    {
      fRightNode->InsertInterval(b,e,stack);
    }
  }
  Update();
}

//_____________________________________________________________________________
void 
AliMUONNode::DeleteInterval(Double_t b, Double_t e, TObjArray& stack)
{
  /// Delete an interval
  if ( IsFullyContained(b,e) ) 
  {
    C(-1);
  }
  else
  {
    if ( fC > 0 ) Demote();
    if ( b < fMidPoint )
    {
      fLeftNode->DeleteInterval(b,e,stack);
    }
    
    if ( fMidPoint < e ) 
    {
      fRightNode->DeleteInterval(b,e,stack);
    }
  }
  Update();
}

//_____________________________________________________________________________
void 
AliMUONNode::Update()
{
  /// Update internal values
  if ( !fLeftNode ) 
  {
    fP = 0;
  }
  else
  {
    if (fLeftNode->C() > 0 && fRightNode->C() > 0 )
    {
      Promote();
    }
    if (fLeftNode->C()==0 && fRightNode->C()==0 && fLeftNode->P()==0 && fRightNode->P()==0 ) 
    {
      fP = 0;
    }
    else
    {
      fP = 1;
    }
  }
}

//_____________________________________________________________________________
void 
AliMUONNode::Promote()
{
  /// Promote node
  fLeftNode->C(-1);
  fRightNode->C(-1);
  C(+1);
}

//_____________________________________________________________________________
void 
AliMUONNode::Demote()
{
  /// Demote node
  fLeftNode->C(+1);
  fRightNode->C(+1);
  C(-1);
  fP = 1;
}

 AliMUONNode.cxx:1
 AliMUONNode.cxx:2
 AliMUONNode.cxx:3
 AliMUONNode.cxx:4
 AliMUONNode.cxx:5
 AliMUONNode.cxx:6
 AliMUONNode.cxx:7
 AliMUONNode.cxx:8
 AliMUONNode.cxx:9
 AliMUONNode.cxx:10
 AliMUONNode.cxx:11
 AliMUONNode.cxx:12
 AliMUONNode.cxx:13
 AliMUONNode.cxx:14
 AliMUONNode.cxx:15
 AliMUONNode.cxx:16
 AliMUONNode.cxx:17
 AliMUONNode.cxx:18
 AliMUONNode.cxx:19
 AliMUONNode.cxx:20
 AliMUONNode.cxx:21
 AliMUONNode.cxx:22
 AliMUONNode.cxx:23
 AliMUONNode.cxx:24
 AliMUONNode.cxx:25
 AliMUONNode.cxx:26
 AliMUONNode.cxx:27
 AliMUONNode.cxx:28
 AliMUONNode.cxx:29
 AliMUONNode.cxx:30
 AliMUONNode.cxx:31
 AliMUONNode.cxx:32
 AliMUONNode.cxx:33
 AliMUONNode.cxx:34
 AliMUONNode.cxx:35
 AliMUONNode.cxx:36
 AliMUONNode.cxx:37
 AliMUONNode.cxx:38
 AliMUONNode.cxx:39
 AliMUONNode.cxx:40
 AliMUONNode.cxx:41
 AliMUONNode.cxx:42
 AliMUONNode.cxx:43
 AliMUONNode.cxx:44
 AliMUONNode.cxx:45
 AliMUONNode.cxx:46
 AliMUONNode.cxx:47
 AliMUONNode.cxx:48
 AliMUONNode.cxx:49
 AliMUONNode.cxx:50
 AliMUONNode.cxx:51
 AliMUONNode.cxx:52
 AliMUONNode.cxx:53
 AliMUONNode.cxx:54
 AliMUONNode.cxx:55
 AliMUONNode.cxx:56
 AliMUONNode.cxx:57
 AliMUONNode.cxx:58
 AliMUONNode.cxx:59
 AliMUONNode.cxx:60
 AliMUONNode.cxx:61
 AliMUONNode.cxx:62
 AliMUONNode.cxx:63
 AliMUONNode.cxx:64
 AliMUONNode.cxx:65
 AliMUONNode.cxx:66
 AliMUONNode.cxx:67
 AliMUONNode.cxx:68
 AliMUONNode.cxx:69
 AliMUONNode.cxx:70
 AliMUONNode.cxx:71
 AliMUONNode.cxx:72
 AliMUONNode.cxx:73
 AliMUONNode.cxx:74
 AliMUONNode.cxx:75
 AliMUONNode.cxx:76
 AliMUONNode.cxx:77
 AliMUONNode.cxx:78
 AliMUONNode.cxx:79
 AliMUONNode.cxx:80
 AliMUONNode.cxx:81
 AliMUONNode.cxx:82
 AliMUONNode.cxx:83
 AliMUONNode.cxx:84
 AliMUONNode.cxx:85
 AliMUONNode.cxx:86
 AliMUONNode.cxx:87
 AliMUONNode.cxx:88
 AliMUONNode.cxx:89
 AliMUONNode.cxx:90
 AliMUONNode.cxx:91
 AliMUONNode.cxx:92
 AliMUONNode.cxx:93
 AliMUONNode.cxx:94
 AliMUONNode.cxx:95
 AliMUONNode.cxx:96
 AliMUONNode.cxx:97
 AliMUONNode.cxx:98
 AliMUONNode.cxx:99
 AliMUONNode.cxx:100
 AliMUONNode.cxx:101
 AliMUONNode.cxx:102
 AliMUONNode.cxx:103
 AliMUONNode.cxx:104
 AliMUONNode.cxx:105
 AliMUONNode.cxx:106
 AliMUONNode.cxx:107
 AliMUONNode.cxx:108
 AliMUONNode.cxx:109
 AliMUONNode.cxx:110
 AliMUONNode.cxx:111
 AliMUONNode.cxx:112
 AliMUONNode.cxx:113
 AliMUONNode.cxx:114
 AliMUONNode.cxx:115
 AliMUONNode.cxx:116
 AliMUONNode.cxx:117
 AliMUONNode.cxx:118
 AliMUONNode.cxx:119
 AliMUONNode.cxx:120
 AliMUONNode.cxx:121
 AliMUONNode.cxx:122
 AliMUONNode.cxx:123
 AliMUONNode.cxx:124
 AliMUONNode.cxx:125
 AliMUONNode.cxx:126
 AliMUONNode.cxx:127
 AliMUONNode.cxx:128
 AliMUONNode.cxx:129
 AliMUONNode.cxx:130
 AliMUONNode.cxx:131
 AliMUONNode.cxx:132
 AliMUONNode.cxx:133
 AliMUONNode.cxx:134
 AliMUONNode.cxx:135
 AliMUONNode.cxx:136
 AliMUONNode.cxx:137
 AliMUONNode.cxx:138
 AliMUONNode.cxx:139
 AliMUONNode.cxx:140
 AliMUONNode.cxx:141
 AliMUONNode.cxx:142
 AliMUONNode.cxx:143
 AliMUONNode.cxx:144
 AliMUONNode.cxx:145
 AliMUONNode.cxx:146
 AliMUONNode.cxx:147
 AliMUONNode.cxx:148
 AliMUONNode.cxx:149
 AliMUONNode.cxx:150
 AliMUONNode.cxx:151
 AliMUONNode.cxx:152
 AliMUONNode.cxx:153
 AliMUONNode.cxx:154
 AliMUONNode.cxx:155
 AliMUONNode.cxx:156
 AliMUONNode.cxx:157
 AliMUONNode.cxx:158
 AliMUONNode.cxx:159
 AliMUONNode.cxx:160
 AliMUONNode.cxx:161
 AliMUONNode.cxx:162
 AliMUONNode.cxx:163
 AliMUONNode.cxx:164
 AliMUONNode.cxx:165
 AliMUONNode.cxx:166
 AliMUONNode.cxx:167
 AliMUONNode.cxx:168
 AliMUONNode.cxx:169
 AliMUONNode.cxx:170
 AliMUONNode.cxx:171
 AliMUONNode.cxx:172
 AliMUONNode.cxx:173
 AliMUONNode.cxx:174
 AliMUONNode.cxx:175
 AliMUONNode.cxx:176
 AliMUONNode.cxx:177
 AliMUONNode.cxx:178
 AliMUONNode.cxx:179
 AliMUONNode.cxx:180
 AliMUONNode.cxx:181
 AliMUONNode.cxx:182
 AliMUONNode.cxx:183
 AliMUONNode.cxx:184
 AliMUONNode.cxx:185
 AliMUONNode.cxx:186
 AliMUONNode.cxx:187
 AliMUONNode.cxx:188
 AliMUONNode.cxx:189
 AliMUONNode.cxx:190
 AliMUONNode.cxx:191
 AliMUONNode.cxx:192
 AliMUONNode.cxx:193
 AliMUONNode.cxx:194
 AliMUONNode.cxx:195
 AliMUONNode.cxx:196
 AliMUONNode.cxx:197
 AliMUONNode.cxx:198
 AliMUONNode.cxx:199
 AliMUONNode.cxx:200
 AliMUONNode.cxx:201
 AliMUONNode.cxx:202
 AliMUONNode.cxx:203
 AliMUONNode.cxx:204
 AliMUONNode.cxx:205
 AliMUONNode.cxx:206
 AliMUONNode.cxx:207
 AliMUONNode.cxx:208
 AliMUONNode.cxx:209
 AliMUONNode.cxx:210
 AliMUONNode.cxx:211
 AliMUONNode.cxx:212
 AliMUONNode.cxx:213
 AliMUONNode.cxx:214
 AliMUONNode.cxx:215
 AliMUONNode.cxx:216
 AliMUONNode.cxx:217
 AliMUONNode.cxx:218
 AliMUONNode.cxx:219
 AliMUONNode.cxx:220
 AliMUONNode.cxx:221
 AliMUONNode.cxx:222
 AliMUONNode.cxx:223
 AliMUONNode.cxx:224
 AliMUONNode.cxx:225
 AliMUONNode.cxx:226