/*****************************************************************************
 * Project: RooFit                                                           *
 * Package: RooFitCore                                                       *
 * @(#)root/roofitcore:$Id$
 * Authors:                                                                  *
 *   WV, Wouter Verkerke, UC Santa Barbara, verkerke@slac.stanford.edu       *
 *   DK, David Kirkby,    UC Irvine,         dkirkby@uci.edu                 *
 *                                                                           *
 * Copyright (c) 2000-2005, Regents of the University of California          *
 *                          and Stanford University. All rights reserved.    *
 *                                                                           *
 * Redistribution and use in source and binary forms,                        *
 * with or without modification, are permitted according to the terms        *
 * listed in LICENSE (http://roofit.sourceforge.net/license.txt)             *
 *****************************************************************************/

//////////////////////////////////////////////////////////////////////////////
//
// BEGIN_HTML
// Class RooBinning is an implements RooAbsBinning in terms
// of an array of boundary values, posing no constraints on the choice
// of binning, thus allowing variable bin sizes. Various methods allow
// the user to add single bin boundaries, mirrored pairs, or sets of
// uniformly spaced boundaries.
// END_HTML
//

#include <cmath>
#include <algorithm>
#include "RooFit.h"

#include "Riostream.h"
#include "Riostream.h"
#include "RooBinning.h"
#include "RooDouble.h"
#include "RooAbsPdf.h"
#include "RooRealVar.h"
#include "RooNumber.h"
#include "RooMsgService.h"
#include "TList.h"

using namespace std;

ClassImp(RooBinning)
;


//_____________________________________________________________________________
RooBinning::RooBinning(Double_t xlo, Double_t xhi, const char* name) :
  RooAbsBinning(name),
  _xlo(0), _xhi(0), _ownBoundLo(kTRUE), _ownBoundHi(kTRUE),
  _array(0), _blo(0)
{
  // Constructor for an initially empty binning defining the range [xlo,xhi]
  setRange(xlo,xhi);
}

//_____________________________________________________________________________
RooBinning::RooBinning(Int_t nbins, Double_t xlo, Double_t xhi, const char* name) :
  RooAbsBinning(name),
  _xlo(0), _xhi(0), _ownBoundLo(kTRUE), _ownBoundHi(kTRUE),
  _array(0), _blo(0)
{
  // Constructor for a uniform binning in 'nbins' bins in the range [xlo,xhi]
  _boundaries.reserve(1 + nbins);
  setRange(xlo, xhi);
  addUniform(nbins, xlo, xhi);
}

//_____________________________________________________________________________
RooBinning::RooBinning(Int_t nbins, const Double_t* boundaries, const char* name) :
  RooAbsBinning(name),
  _xlo(0), _xhi(0), _ownBoundLo(kTRUE), _ownBoundHi(kTRUE),
  _array(0), _blo(0)
{
  // Constructor for a binning in the range[xlo,xhi] with 'nbins' bin boundaries listed
  // array 'boundaries'

  // Variable bin size constructor
  _boundaries.reserve(1 + nbins);
  setRange(boundaries[0], boundaries[nbins]);
  while (nbins--) addBoundary(boundaries[nbins]);
}

//_____________________________________________________________________________
RooBinning::RooBinning(const RooBinning& other, const char* name) :
  RooAbsBinning(name), _xlo(other._xlo), _xhi(other._xhi),
  _ownBoundLo(other._ownBoundLo), _ownBoundHi(other._ownBoundHi),
  _nbins(other._nbins), _boundaries(other._boundaries), _array(0),
  _blo(other._blo)
{
  // Copy constructor
}

//_____________________________________________________________________________
RooBinning::~RooBinning()
{
  // Destructor
  delete[] _array;
}

//_____________________________________________________________________________
Bool_t RooBinning::addBoundary(Double_t boundary)
{
  // Add bin boundary at given value
  std::vector<Double_t>::iterator it =
      std::lower_bound(_boundaries.begin(), _boundaries.end(), boundary);
  if (_boundaries.end() != it && *it == boundary) {
    // If boundary previously existed as range delimiter,
    //                    convert to regular boundary now
    if (boundary == _xlo) _ownBoundLo = kFALSE;
    if (boundary == _xhi) _ownBoundHi = kFALSE;
    return kFALSE;
  }
  // Add a new boundary
  _boundaries.insert(it, boundary);
  updateBinCount();
  return kTRUE;
}

//_____________________________________________________________________________
void RooBinning::addBoundaryPair(Double_t boundary, Double_t mirrorPoint)
{
  // Add pair of boundaries: one at 'boundary' and one at 2*mirrorPoint-boundary
  addBoundary(boundary);
  addBoundary(2. * mirrorPoint - boundary);
}

//_____________________________________________________________________________
Bool_t RooBinning::removeBoundary(Double_t boundary)
{
  // Remove boundary at given value
  std::vector<Double_t>::iterator it = std::lower_bound(_boundaries.begin(),
      _boundaries.end(), boundary);
  if  (_boundaries.end() != it && *it == boundary) {
    _boundaries.erase(it);
    // if some moron deletes the boundaries corresponding to the current
    // range, we need to make sure that we do not get into an undefined state,
    // so _xlo and _xhi need to be set to some valid values
    if (_boundaries.empty()) {
      _xlo = _xhi = 0.;
    } else {
      if (boundary == _xlo) _xlo = _boundaries.front();
      if (boundary == _xhi) _xhi = _boundaries.back();
    }
    updateBinCount();
    return kFALSE;
  }
  // Return error status - no boundary found
  return kTRUE;
}

//_____________________________________________________________________________
Bool_t RooBinning::hasBoundary(Double_t boundary)
{
  // Check if boundary exists at given value
  return std::binary_search(_boundaries.begin(), _boundaries.end(), boundary);
}

//_____________________________________________________________________________
void RooBinning::addUniform(Int_t nbins, Double_t xlo, Double_t xhi)
{
  // Add array of nbins uniformly sized bins in range [xlo,xhi]
  _boundaries.reserve(_boundaries.size() + nbins + 1);
  for (Int_t i = 0; i <= nbins; ++i)
    addBoundary((double(nbins - i) / double(nbins)) * xlo +
	(double(i) / double(nbins)) * xhi);
}

//_____________________________________________________________________________
Int_t RooBinning::binNumber(Double_t x) const
{
  // Return sequential bin number that contains value x where bin
  // zero is the first bin with an upper boundary above the lower bound
  // of the range
  return std::max(0, std::min(_nbins, rawBinNumber(x) - _blo));
}

//_____________________________________________________________________________
Int_t RooBinning::rawBinNumber(Double_t x) const
{
  // Return sequential bin number that contains value x where bin
  // zero is the first bin that is defined, regardless if that bin
  // is outside the current defined range
  std::vector<Double_t>::const_iterator it = std::lower_bound(
      _boundaries.begin(), _boundaries.end(), x);
  // always return valid bin number
  while (_boundaries.begin() != it &&
	  (_boundaries.end() == it || _boundaries.end() == it + 1 || x < *it)) --it;
  return it - _boundaries.begin();
}

//_____________________________________________________________________________
Double_t RooBinning::nearestBoundary(Double_t x) const
{
  // Return the value of the nearest boundary to x
  Double_t xl, xh;
  binEdges(binNumber(x), xl, xh);
  return (std::abs(xl - x) < std::abs(xh - x)) ? xl : xh;
}

//_____________________________________________________________________________
Double_t* RooBinning::array() const
{
  // Return array of boundary values

  delete[] _array;
  _array = new Double_t[numBoundaries()];
  std::copy(_boundaries.begin()+_blo, _boundaries.begin()+_blo+_nbins+1, _array);
  return _array;
}

//_____________________________________________________________________________
void RooBinning::setRange(Double_t xlo, Double_t xhi)
{
  // Change the defined range associated with this binning.
  // Bins that lie outside the new range [xlo,xhi] will not be
  // removed, but will be 'inactive', i.e. the new 0 bin will
  // be the first bin with an upper boundarie > xlo
  if (xlo > xhi) {
    coutE(InputArguments) << "RooBinning::setRange: ERROR low bound > high bound" << endl;
    return;
  }
  // Remove previous boundaries
  if (_ownBoundLo) removeBoundary(_xlo);
  if (_ownBoundHi) removeBoundary(_xhi);
  // Insert boundaries at range delimiter, if necessary
  _ownBoundLo = addBoundary(xlo);
  _ownBoundHi = addBoundary(xhi);
  _xlo = xlo, _xhi = xhi;
  // Count number of bins with new range
  updateBinCount();
}

//_____________________________________________________________________________
void RooBinning::updateBinCount()
{
  // Update the internal bin counter
  if (_boundaries.size() <= 1) {
      _nbins = -1;
      return;
  }
  _blo = rawBinNumber(_xlo);
  std::vector<Double_t>::const_iterator it = std::lower_bound(
      _boundaries.begin(), _boundaries.end(), _xhi);
  if (_boundaries.begin() != it && (_boundaries.end() == it || _xhi < *it)) --it;
  const Int_t bhi = it - _boundaries.begin();
  _nbins = bhi - _blo;
}

//_____________________________________________________________________________
Bool_t RooBinning::binEdges(Int_t bin, Double_t& xlo, Double_t& xhi) const
{
  // Return upper and lower bound of bin 'bin'. If the return value
  // is true an error occurred
  if (0 > bin || bin >= _nbins) {
    coutE(InputArguments) << "RooBinning::binEdges ERROR: bin number must be in range (0," << _nbins << ")" << endl;
    return kTRUE;
  }
  xlo = _boundaries[bin + _blo], xhi = _boundaries[bin + _blo + 1];
  return kFALSE;
}

//_____________________________________________________________________________
Double_t RooBinning::binCenter(Int_t bin) const
{
  // Return the position of the center of bin 'bin'

  Double_t xlo, xhi;
  if (binEdges(bin, xlo, xhi)) return 0;
  return 0.5 * (xlo + xhi);
}

//_____________________________________________________________________________
Double_t RooBinning::binWidth(Int_t bin) const
{
  // Return the width of the requested bin

  Double_t xlo, xhi;
  if (binEdges(bin, xlo, xhi)) return 0;
  return (xhi - xlo);
}

//_____________________________________________________________________________
Double_t RooBinning::binLow(Int_t bin) const
{
  // Return the lower bound of the requested bin

  Double_t xlo, xhi;
  if (binEdges(bin, xlo, xhi)) return 0;
  return xlo;
}

//_____________________________________________________________________________
Double_t RooBinning::binHigh(Int_t bin) const
{
  // Return the upper bound of the requested bin

  Double_t xlo, xhi;
  if (binEdges(bin, xlo, xhi)) return  0;
  return xhi;
}

//______________________________________________________________________________
void RooBinning::Streamer(TBuffer &R__b)
{
   // Custom streamer that provides backward compatibility to read v1 data

   if (R__b.IsReading()) {

     UInt_t R__s, R__c;
     Version_t R__v = R__b.ReadVersion(&R__s, &R__c); if (R__v) { }
     switch (R__v) {
       case 3:
	 // current version - fallthrough intended
       case 2:
	 // older version with std::set<Double_t> instead of
	 // std::vector<Double_t>, apparently ROOT is clever enough to not care
	 // about set vs vector
	 R__b.ReadClassBuffer(RooBinning::Class(), this, R__v, R__s, R__c);
	 break;
       case 1:
	 {
	   RooAbsBinning::Streamer(R__b);
	   R__b >> _xlo;
	   R__b >> _xhi;
	   R__b >> _ownBoundLo;
	   R__b >> _ownBoundHi;
	   R__b >> _nbins;

	   _boundaries.clear();
	   // Convert TList to std::vector<Double_t>
	   TList tmp;
	   tmp.Streamer(R__b);
	   _boundaries.reserve(tmp.GetSize());
	   TIterator* it = tmp.MakeIterator();
	   for (RooDouble* el = (RooDouble*) it->Next(); el;
	       el = (RooDouble*) it->Next()) _boundaries.push_back(*el);
	   delete it;
	 }
	 R__b.CheckByteCount(R__s, R__c, RooBinning::IsA());
	 break;
       default:
	 throw std::string("Unknown class version!");
     }
     if (_boundaries.size() > 2) {
       std::sort(_boundaries.begin(), _boundaries.end());
       _boundaries.erase(std::unique(_boundaries.begin(), _boundaries.end()),
	   _boundaries.end());
     }
   } else {
     R__b.WriteClassBuffer(RooBinning::Class(),this);
   }
}
 RooBinning.cxx:1
 RooBinning.cxx:2
 RooBinning.cxx:3
 RooBinning.cxx:4
 RooBinning.cxx:5
 RooBinning.cxx:6
 RooBinning.cxx:7
 RooBinning.cxx:8
 RooBinning.cxx:9
 RooBinning.cxx:10
 RooBinning.cxx:11
 RooBinning.cxx:12
 RooBinning.cxx:13
 RooBinning.cxx:14
 RooBinning.cxx:15
 RooBinning.cxx:16
 RooBinning.cxx:17
 RooBinning.cxx:18
 RooBinning.cxx:19
 RooBinning.cxx:20
 RooBinning.cxx:21
 RooBinning.cxx:22
 RooBinning.cxx:23
 RooBinning.cxx:24
 RooBinning.cxx:25
 RooBinning.cxx:26
 RooBinning.cxx:27
 RooBinning.cxx:28
 RooBinning.cxx:29
 RooBinning.cxx:30
 RooBinning.cxx:31
 RooBinning.cxx:32
 RooBinning.cxx:33
 RooBinning.cxx:34
 RooBinning.cxx:35
 RooBinning.cxx:36
 RooBinning.cxx:37
 RooBinning.cxx:38
 RooBinning.cxx:39
 RooBinning.cxx:40
 RooBinning.cxx:41
 RooBinning.cxx:42
 RooBinning.cxx:43
 RooBinning.cxx:44
 RooBinning.cxx:45
 RooBinning.cxx:46
 RooBinning.cxx:47
 RooBinning.cxx:48
 RooBinning.cxx:49
 RooBinning.cxx:50
 RooBinning.cxx:51
 RooBinning.cxx:52
 RooBinning.cxx:53
 RooBinning.cxx:54
 RooBinning.cxx:55
 RooBinning.cxx:56
 RooBinning.cxx:57
 RooBinning.cxx:58
 RooBinning.cxx:59
 RooBinning.cxx:60
 RooBinning.cxx:61
 RooBinning.cxx:62
 RooBinning.cxx:63
 RooBinning.cxx:64
 RooBinning.cxx:65
 RooBinning.cxx:66
 RooBinning.cxx:67
 RooBinning.cxx:68
 RooBinning.cxx:69
 RooBinning.cxx:70
 RooBinning.cxx:71
 RooBinning.cxx:72
 RooBinning.cxx:73
 RooBinning.cxx:74
 RooBinning.cxx:75
 RooBinning.cxx:76
 RooBinning.cxx:77
 RooBinning.cxx:78
 RooBinning.cxx:79
 RooBinning.cxx:80
 RooBinning.cxx:81
 RooBinning.cxx:82
 RooBinning.cxx:83
 RooBinning.cxx:84
 RooBinning.cxx:85
 RooBinning.cxx:86
 RooBinning.cxx:87
 RooBinning.cxx:88
 RooBinning.cxx:89
 RooBinning.cxx:90
 RooBinning.cxx:91
 RooBinning.cxx:92
 RooBinning.cxx:93
 RooBinning.cxx:94
 RooBinning.cxx:95
 RooBinning.cxx:96
 RooBinning.cxx:97
 RooBinning.cxx:98
 RooBinning.cxx:99
 RooBinning.cxx:100
 RooBinning.cxx:101
 RooBinning.cxx:102
 RooBinning.cxx:103
 RooBinning.cxx:104
 RooBinning.cxx:105
 RooBinning.cxx:106
 RooBinning.cxx:107
 RooBinning.cxx:108
 RooBinning.cxx:109
 RooBinning.cxx:110
 RooBinning.cxx:111
 RooBinning.cxx:112
 RooBinning.cxx:113
 RooBinning.cxx:114
 RooBinning.cxx:115
 RooBinning.cxx:116
 RooBinning.cxx:117
 RooBinning.cxx:118
 RooBinning.cxx:119
 RooBinning.cxx:120
 RooBinning.cxx:121
 RooBinning.cxx:122
 RooBinning.cxx:123
 RooBinning.cxx:124
 RooBinning.cxx:125
 RooBinning.cxx:126
 RooBinning.cxx:127
 RooBinning.cxx:128
 RooBinning.cxx:129
 RooBinning.cxx:130
 RooBinning.cxx:131
 RooBinning.cxx:132
 RooBinning.cxx:133
 RooBinning.cxx:134
 RooBinning.cxx:135
 RooBinning.cxx:136
 RooBinning.cxx:137
 RooBinning.cxx:138
 RooBinning.cxx:139
 RooBinning.cxx:140
 RooBinning.cxx:141
 RooBinning.cxx:142
 RooBinning.cxx:143
 RooBinning.cxx:144
 RooBinning.cxx:145
 RooBinning.cxx:146
 RooBinning.cxx:147
 RooBinning.cxx:148
 RooBinning.cxx:149
 RooBinning.cxx:150
 RooBinning.cxx:151
 RooBinning.cxx:152
 RooBinning.cxx:153
 RooBinning.cxx:154
 RooBinning.cxx:155
 RooBinning.cxx:156
 RooBinning.cxx:157
 RooBinning.cxx:158
 RooBinning.cxx:159
 RooBinning.cxx:160
 RooBinning.cxx:161
 RooBinning.cxx:162
 RooBinning.cxx:163
 RooBinning.cxx:164
 RooBinning.cxx:165
 RooBinning.cxx:166
 RooBinning.cxx:167
 RooBinning.cxx:168
 RooBinning.cxx:169
 RooBinning.cxx:170
 RooBinning.cxx:171
 RooBinning.cxx:172
 RooBinning.cxx:173
 RooBinning.cxx:174
 RooBinning.cxx:175
 RooBinning.cxx:176
 RooBinning.cxx:177
 RooBinning.cxx:178
 RooBinning.cxx:179
 RooBinning.cxx:180
 RooBinning.cxx:181
 RooBinning.cxx:182
 RooBinning.cxx:183
 RooBinning.cxx:184
 RooBinning.cxx:185
 RooBinning.cxx:186
 RooBinning.cxx:187
 RooBinning.cxx:188
 RooBinning.cxx:189
 RooBinning.cxx:190
 RooBinning.cxx:191
 RooBinning.cxx:192
 RooBinning.cxx:193
 RooBinning.cxx:194
 RooBinning.cxx:195
 RooBinning.cxx:196
 RooBinning.cxx:197
 RooBinning.cxx:198
 RooBinning.cxx:199
 RooBinning.cxx:200
 RooBinning.cxx:201
 RooBinning.cxx:202
 RooBinning.cxx:203
 RooBinning.cxx:204
 RooBinning.cxx:205
 RooBinning.cxx:206
 RooBinning.cxx:207
 RooBinning.cxx:208
 RooBinning.cxx:209
 RooBinning.cxx:210
 RooBinning.cxx:211
 RooBinning.cxx:212
 RooBinning.cxx:213
 RooBinning.cxx:214
 RooBinning.cxx:215
 RooBinning.cxx:216
 RooBinning.cxx:217
 RooBinning.cxx:218
 RooBinning.cxx:219
 RooBinning.cxx:220
 RooBinning.cxx:221
 RooBinning.cxx:222
 RooBinning.cxx:223
 RooBinning.cxx:224
 RooBinning.cxx:225
 RooBinning.cxx:226
 RooBinning.cxx:227
 RooBinning.cxx:228
 RooBinning.cxx:229
 RooBinning.cxx:230
 RooBinning.cxx:231
 RooBinning.cxx:232
 RooBinning.cxx:233
 RooBinning.cxx:234
 RooBinning.cxx:235
 RooBinning.cxx:236
 RooBinning.cxx:237
 RooBinning.cxx:238
 RooBinning.cxx:239
 RooBinning.cxx:240
 RooBinning.cxx:241
 RooBinning.cxx:242
 RooBinning.cxx:243
 RooBinning.cxx:244
 RooBinning.cxx:245
 RooBinning.cxx:246
 RooBinning.cxx:247
 RooBinning.cxx:248
 RooBinning.cxx:249
 RooBinning.cxx:250
 RooBinning.cxx:251
 RooBinning.cxx:252
 RooBinning.cxx:253
 RooBinning.cxx:254
 RooBinning.cxx:255
 RooBinning.cxx:256
 RooBinning.cxx:257
 RooBinning.cxx:258
 RooBinning.cxx:259
 RooBinning.cxx:260
 RooBinning.cxx:261
 RooBinning.cxx:262
 RooBinning.cxx:263
 RooBinning.cxx:264
 RooBinning.cxx:265
 RooBinning.cxx:266
 RooBinning.cxx:267
 RooBinning.cxx:268
 RooBinning.cxx:269
 RooBinning.cxx:270
 RooBinning.cxx:271
 RooBinning.cxx:272
 RooBinning.cxx:273
 RooBinning.cxx:274
 RooBinning.cxx:275
 RooBinning.cxx:276
 RooBinning.cxx:277
 RooBinning.cxx:278
 RooBinning.cxx:279
 RooBinning.cxx:280
 RooBinning.cxx:281
 RooBinning.cxx:282
 RooBinning.cxx:283
 RooBinning.cxx:284
 RooBinning.cxx:285
 RooBinning.cxx:286
 RooBinning.cxx:287
 RooBinning.cxx:288
 RooBinning.cxx:289
 RooBinning.cxx:290
 RooBinning.cxx:291
 RooBinning.cxx:292
 RooBinning.cxx:293
 RooBinning.cxx:294
 RooBinning.cxx:295
 RooBinning.cxx:296
 RooBinning.cxx:297
 RooBinning.cxx:298
 RooBinning.cxx:299
 RooBinning.cxx:300
 RooBinning.cxx:301
 RooBinning.cxx:302
 RooBinning.cxx:303
 RooBinning.cxx:304
 RooBinning.cxx:305
 RooBinning.cxx:306
 RooBinning.cxx:307
 RooBinning.cxx:308
 RooBinning.cxx:309
 RooBinning.cxx:310
 RooBinning.cxx:311
 RooBinning.cxx:312
 RooBinning.cxx:313
 RooBinning.cxx:314
 RooBinning.cxx:315
 RooBinning.cxx:316
 RooBinning.cxx:317
 RooBinning.cxx:318
 RooBinning.cxx:319
 RooBinning.cxx:320
 RooBinning.cxx:321
 RooBinning.cxx:322
 RooBinning.cxx:323
 RooBinning.cxx:324
 RooBinning.cxx:325
 RooBinning.cxx:326
 RooBinning.cxx:327
 RooBinning.cxx:328
 RooBinning.cxx:329
 RooBinning.cxx:330
 RooBinning.cxx:331
 RooBinning.cxx:332
 RooBinning.cxx:333
 RooBinning.cxx:334
 RooBinning.cxx:335
 RooBinning.cxx:336
 RooBinning.cxx:337
 RooBinning.cxx:338
 RooBinning.cxx:339
 RooBinning.cxx:340
 RooBinning.cxx:341
 RooBinning.cxx:342
 RooBinning.cxx:343
 RooBinning.cxx:344
 RooBinning.cxx:345
 RooBinning.cxx:346
 RooBinning.cxx:347
 RooBinning.cxx:348
 RooBinning.cxx:349
 RooBinning.cxx:350
 RooBinning.cxx:351
 RooBinning.cxx:352
 RooBinning.cxx:353
 RooBinning.cxx:354