RooLinkedList.cxx

Go to the documentation of this file.

/*****************************************************************************
 * 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)             *
 *****************************************************************************/
 
/**
\file RooLinkedList.cxx
\class RooLinkedList
\ingroup Roofitcore
 
RooLinkedList is an collection class for internal use, storing
a collection of RooAbsArg pointers in a doubly linked list.
It can optionally add a hash table to speed up random access
in large collections
Use RooAbsCollection derived objects for public use
(e.g. RooArgSet or RooArgList)
**/
 
#include "RooLinkedList.h"
 
#include "RooLinkedListIter.h"
#include "RooAbsArg.h"
#include "RooAbsData.h"
#include "RooMsgService.h"
 
#include "Riostream.h"
#include "TBuffer.h"
#include "TROOT.h"
 
#include <algorithm>
#include <list>
#include <memory>
#include <vector>
 
using namespace std;
 
ClassImp(RooLinkedList);
 
/// \cond ROOFIT_INTERNAL
 
namespace RooLinkedListImplDetails {
  /// a chunk of memory in a pool for quick allocation of RooLinkedListElems
  class Chunk {
    public:
      /// constructor
      Chunk(Int_t sz) :
   _sz(sz), _free(capacity()),
   _chunk(new RooLinkedListElem[_free]), _freelist(_chunk)
      {
   //cout << "RLLID::Chunk ctor(" << this << ") of size " << _free << " list elements" << endl ;
   // initialise free list
   for (Int_t i = 0; i < _free; ++i)
     _chunk[i]._next = (i + 1 < _free) ? &_chunk[i + 1] : nullptr;
      }
      /// destructor
      ~Chunk() { delete[] _chunk; }
      /// chunk capacity
      Int_t capacity() const
      { return (1 << _sz) / sizeof(RooLinkedListElem); }
      /// chunk free elements
      Int_t free() const { return _free; }
      /// chunk occupied elements
      Int_t size() const { return capacity() - free(); }
      /// return size class
      int szclass() const { return _sz; }
      /// chunk full?
      bool full() const { return !free(); }
      /// chunk empty?
      bool empty() const { return capacity() == free(); }
      /// return address of chunk
      const void* chunkaddr() const { return _chunk; }
      /// check if el is in this chunk
      bool contains(RooLinkedListElem* el) const
      { return _chunk <= el && el < &_chunk[capacity()]; }
      /// pop a free element off the free list
      RooLinkedListElem* pop_free_elem()
      {
   if (!_freelist) return nullptr;
   RooLinkedListElem* retVal = _freelist;
   _freelist = retVal->_next;
   retVal->_arg = nullptr; retVal->_refCount = 0;
   retVal->_prev = retVal->_next = nullptr;
   --_free;
   return retVal;
      }
      /// push a free element back onto the freelist
      void push_free_elem(RooLinkedListElem* el)
      {
   el->_next = _freelist;
   _freelist = el;
   ++_free;
      }
    private:
      Int_t _sz;           ///< chunk capacity
      Int_t _free;         ///< length of free list
      RooLinkedListElem* _chunk;    ///< chunk from which elements come
      RooLinkedListElem* _freelist; ///< list of free elements
 
      /// forbid copying
      Chunk(const Chunk&) = delete;
      // forbid assignment
      Chunk& operator=(const Chunk&) = delete;
  };
 
  class Pool {
    private:
      enum {
   minsz = 7, ///< minimum chunk size (just below 1 << minsz bytes)
   maxsz = 18, ///< maximum chunk size (just below 1 << maxsz bytes)
   szincr = 1 ///< size class increment (sz = 1 << (minsz + k * szincr))
      };
      /// a chunk of memory in the pool
      typedef RooLinkedListImplDetails::Chunk Chunk;
      typedef std::list<Chunk*> ChunkList;
      typedef std::map<const void*, Chunk*> AddrMap;
    public:
      /// constructor
      Pool();
      /// destructor
      ~Pool();
      /// acquire the pool
      inline void acquire() { ++_refCount; }
      /// release the pool, return true if the pool is unused
      inline bool release() { return 0 == --_refCount; }
      /// pop a free element out of the pool
      RooLinkedListElem* pop_free_elem();
      /// push a free element back into the pool
      void push_free_elem(RooLinkedListElem* el);
    private:
      AddrMap _addrmap;
      ChunkList _freelist;
      UInt_t _szmap[(maxsz - minsz) / szincr];
      Int_t _cursz;
      UInt_t _refCount;
 
      /// adjust _cursz to current largest block
      void updateCurSz(Int_t sz, Int_t incr);
      /// find size of next chunk to allocate (in a hopefully smart way)
      Int_t nextChunkSz() const;
  };
 
  Pool::Pool() : _cursz(minsz), _refCount(0)
  {
    std::fill(_szmap, _szmap + ((maxsz - minsz) / szincr), 0);
  }
 
  Pool::~Pool()
  {
    _freelist.clear();
    for (AddrMap::iterator it = _addrmap.begin(); _addrmap.end() != it; ++it)
      delete it->second;
    _addrmap.clear();
  }
 
  RooLinkedListElem* Pool::pop_free_elem()
  {
    if (_freelist.empty()) {
      // allocate and register new chunk and put it on the freelist
      const Int_t sz = nextChunkSz();
      Chunk *c = new Chunk(sz);
      _addrmap[c->chunkaddr()] = c;
      _freelist.push_back(c);
      updateCurSz(sz, +1);
    }
    // get free element from first chunk on _freelist
    Chunk* c = _freelist.front();
    RooLinkedListElem* retVal = c->pop_free_elem();
    // full chunks are removed from _freelist
    if (c->full()) _freelist.pop_front();
    return retVal;
  }
 
  void Pool::push_free_elem(RooLinkedListElem* el)
  {
    // find from which chunk el came
    AddrMap::iterator ci = _addrmap.end();
    if (!_addrmap.empty()) {
      ci = _addrmap.lower_bound(el);
      if (ci == _addrmap.end()) {
   // point beyond last element, so get last one
   ci = (++_addrmap.rbegin()).base();
      } else {
   // valid ci, check if we need to decrement ci because el isn't the
   // first element in the chunk
   if (_addrmap.begin() != ci && ci->first != el) --ci;
      }
    }
    // either empty addressmap, or ci should now point to the chunk which might
    // contain el
    if (_addrmap.empty() || !ci->second->contains(el)) {
      // el is not in any chunk we know about, so just delete it
      delete el;
      return;
    }
    Chunk *c = ci->second;
    const bool moveToFreelist = c->full();
    c->push_free_elem(el);
    if (c->empty()) {
      // delete chunk if all empty
      ChunkList::iterator it = std::find( _freelist.begin(), _freelist.end(), c);
      if (_freelist.end() != it) _freelist.erase(it);
      _addrmap.erase(ci->first);
      updateCurSz(c->szclass(), -1);
      delete c;
    } else if (moveToFreelist) {
      _freelist.push_back(c);
    }
  }
 
  void Pool::updateCurSz(Int_t sz, Int_t incr)
  {
    _szmap[(sz - minsz) / szincr] += incr;
    _cursz = minsz;
    for (int i = (maxsz - minsz) / szincr; i--; ) {
      if (_szmap[i]) {
   _cursz += i * szincr;
   break;
      }
    }
  }
 
  Int_t Pool::nextChunkSz() const
  {
    // no chunks with space available, figure out chunk size
    Int_t sz = _cursz;
    if (_addrmap.empty()) {
      // if we start allocating chunks, we start from minsz
      sz = minsz;
    } else {
      if (minsz >= sz) {
   // minimal sized chunks are always grown
   sz = minsz + szincr;
      } else {
   if (1 != _addrmap.size()) {
     // if we have more than one completely filled chunk, grow
     sz += szincr;
   } else {
     // just one chunk left, try shrinking chunk size
     sz -= szincr;
   }
      }
    }
    // clamp size to allowed range
    if (sz > maxsz) sz = maxsz;
    if (sz < minsz) sz = minsz;
    return sz;
  }
}
 
/// \endcond
 
RooLinkedList::Pool* RooLinkedList::_pool = nullptr;
 
////////////////////////////////////////////////////////////////////////////////
 
RooLinkedList::RooLinkedList(Int_t htsize) :
  _hashThresh(htsize), _size(0), _first(nullptr), _last(nullptr), _htableName(nullptr), _htableLink(nullptr), _useNptr(true)
{
  if (!_pool) _pool = new Pool;
  _pool->acquire();
}
 
////////////////////////////////////////////////////////////////////////////////
/// Copy constructor
 
RooLinkedList::RooLinkedList(const RooLinkedList& other) :
  TObject(other), _hashThresh(other._hashThresh), _size(0), _first(nullptr), _last(nullptr), _htableName(nullptr), _htableLink(nullptr),
  _name(other._name),
  _useNptr(other._useNptr)
{
  if (!_pool) _pool = new Pool;
  _pool->acquire();
  if (other._htableName) _htableName = std::make_unique<HashTableByName>(other._htableName->size()) ;
  if (other._htableLink) _htableLink = std::make_unique<HashTableByLink>(other._htableLink->size()) ;
  for (RooLinkedListElem* elem = other._first; elem; elem = elem->_next) {
    Add(elem->_arg, elem->_refCount) ;
  }
}
 
////////////////////////////////////////////////////////////////////////////////
///   cout << "RooLinkedList::createElem(" << this << ") obj = " << obj << " elem = " << elem << endl ;
 
RooLinkedListElem* RooLinkedList::createElement(TObject* obj, RooLinkedListElem* elem)
{
  RooLinkedListElem* ret = _pool->pop_free_elem();
  ret->init(obj, elem);
  return ret ;
}
 
////////////////////////////////////////////////////////////////////////////////
 
void RooLinkedList::deleteElement(RooLinkedListElem* elem)
{
  elem->release() ;
  _pool->push_free_elem(elem);
  //delete elem ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Assignment operator, copy contents from 'other'
 
RooLinkedList& RooLinkedList::operator=(const RooLinkedList& other)
{
  // Prevent self-assignment
  if (&other==this) return *this ;
 
  // remove old elements
  Clear();
  // Copy elements
  for (RooLinkedListElem* elem = other._first; elem; elem = elem->_next) {
    Add(elem->_arg) ;
  }
 
  return *this ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Change the threshold for hash-table use to given size.
/// If a hash table exists when this method is called, it is regenerated.
 
void RooLinkedList::setHashTableSize(Int_t size)
{
  if (size<0) {
    coutE(InputArguments) << "RooLinkedList::setHashTable() ERROR size must be positive" << endl ;
    return ;
  }
  if (size==0) {
    if (!_htableName) {
      // No hash table present
      return ;
    } else {
      // Remove existing hash table
      _htableName.reset();
      _htableLink.reset();
    }
  } else {
 
    // (Re)create hash tables
    _htableName = std::make_unique<HashTableByName>(size) ;
    _htableLink = std::make_unique<HashTableByLink>(size) ;
 
    // Fill hash table with existing entries
    RooLinkedListElem* ptr = _first ;
    while(ptr) {
      _htableName->insert({ptr->_arg->GetName(), ptr->_arg}) ;
      _htableLink->insert({ptr->_arg, (TObject*)ptr}) ;
      ptr = ptr->_next ;
    }
  }
}
 
////////////////////////////////////////////////////////////////////////////////
/// Destructor
 
RooLinkedList::~RooLinkedList()
{
   // Required since we overload TObject::Hash.
   ROOT::CallRecursiveRemoveIfNeeded(*this);
 
  _htableName.reset();
  _htableLink.reset();
 
  Clear() ;
  if (_pool->release()) {
    delete _pool;
    _pool = nullptr;
  }
}
 
////////////////////////////////////////////////////////////////////////////////
/// Find the element link containing the given object
 
RooLinkedListElem* RooLinkedList::findLink(const TObject* arg) const
{
  if (_htableLink) {
    auto found = _htableLink->find(arg);
    if (found == _htableLink->end()) return nullptr;
    return (RooLinkedListElem*)found->second;
  }
 
  RooLinkedListElem* ptr = _first;
  while(ptr) {
    if (ptr->_arg == arg) {
      return ptr ;
    }
    ptr = ptr->_next ;
  }
  return nullptr ;
 
}
 
////////////////////////////////////////////////////////////////////////////////
/// Insert object into collection with given reference count value
 
void RooLinkedList::Add(TObject* arg, Int_t refCount)
{
  if (!arg) return ;
 
  // Only use RooAbsArg::namePtr() in lookup-by-name if all elements have it
  if (!dynamic_cast<RooAbsArg*>(arg) && !dynamic_cast<RooAbsData*>(arg)) _useNptr = false;
 
  // Add to hash table
  if (_htableName) {
 
    // Expand capacity of hash table if #entries>#slots
    if (static_cast<size_t>(_size) > _htableName->size()) {
      setHashTableSize(_size*2) ;
    }
 
  } else if (_hashThresh>0 && _size>_hashThresh) {
 
    setHashTableSize(_hashThresh) ;
  }
 
  if (_last) {
    // Append element at end of list
    _last = createElement(arg,_last) ;
  } else {
    // Append first element, set first,last
    _last = createElement(arg) ;
    _first=_last ;
  }
 
  if (_htableName){
    //cout << "storing link " << _last << " with hash arg " << arg << endl ;
    _htableName->insert({arg->GetName(), arg});
    _htableLink->insert({arg, (TObject*)_last});
  }
 
  _size++ ;
  _last->_refCount = refCount ;
 
  _at.push_back(_last);
}
 
////////////////////////////////////////////////////////////////////////////////
/// Remove object from collection
 
bool RooLinkedList::Remove(TObject* arg)
{
  // Find link element
  RooLinkedListElem* elem = findLink(arg) ;
  if (!elem) return false ;
 
  // Remove from hash table
  if (_htableName) {
    _htableName->erase(arg->GetName()) ;
  }
  if (_htableLink) {
    _htableLink->erase(arg) ;
  }
 
  // Update first,last if necessary
  if (elem==_first) _first=elem->_next ;
  if (elem==_last) _last=elem->_prev ;
 
  // Remove from index array
  auto at_elem_it = std::find(_at.begin(), _at.end(), elem);
  _at.erase(at_elem_it);
 
  // Delete and shrink
  _size-- ;
  deleteElement(elem) ;
  return true ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// If one of the TObject we have a referenced to is deleted, remove the
/// reference.
 
void RooLinkedList::RecursiveRemove(TObject *obj)
{
   Remove(obj); // This is a nop if the obj is not in the collection.
}
 
////////////////////////////////////////////////////////////////////////////////
/// Return object stored in sequential position given by index.
/// If index is out of range, a null pointer is returned.
 
TObject* RooLinkedList::At(Int_t index) const
{
  // Check range
  if (index<0 || index>=_size) return nullptr ;
 
  return _at[index]->_arg;
//
//
//  // Walk list
//  RooLinkedListElem* ptr = _first;
//  while(index--) ptr = ptr->_next ;
//
//  // Return arg
//  return ptr->_arg ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Replace object 'oldArg' in collection with new object 'newArg'.
/// If 'oldArg' is not found in collection false is returned
 
bool RooLinkedList::Replace(const TObject* oldArg, const TObject* newArg)
{
  // Find existing element and replace arg
  RooLinkedListElem* elem = findLink(oldArg) ;
  if (!elem) return false ;
 
  if (_htableName) {
    _htableName->erase(oldArg->GetName());
    _htableName->insert({newArg->GetName(), newArg});
  }
  if (_htableLink) {
    // Link is hashed by contents and may change slot in hash table
    _htableLink->erase(oldArg) ;
    _htableLink->insert({newArg, (TObject*)elem}) ;
  }
 
  elem->_arg = (TObject*)newArg ;
  return true ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Return pointer to object with given name. If no such object
/// is found return a null pointer.
 
TObject* RooLinkedList::FindObject(const char* name) const
{
  return find(name) ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Find object in list. If list contains object return
/// (same) pointer to object, otherwise return null pointer
 
TObject* RooLinkedList::FindObject(const TObject* obj) const
{
  RooLinkedListElem *elem = findLink((TObject*)obj) ;
  return elem ? elem->_arg : nullptr ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Remove all elements from collection
 
void RooLinkedList::Clear(Option_t *)
{
  for (RooLinkedListElem *elem = _first, *next; elem; elem = next) {
    next = elem->_next ;
    deleteElement(elem) ;
  }
  _first = nullptr ;
  _last = nullptr ;
  _size = 0 ;
 
  if (_htableName) {
    _htableName = std::make_unique<HashTableByName>(_htableName->size()) ;
  }
  if (_htableLink) {
    _htableLink = std::make_unique<HashTableByLink>(_htableLink->size()) ;
  }
 
  // empty index array
  _at.clear();
}
 
////////////////////////////////////////////////////////////////////////////////
/// Remove all elements in collection and delete all elements
/// NB: Collection does not own elements, this function should
/// be used judiciously by caller.
 
void RooLinkedList::Delete(Option_t *)
{
  RooLinkedListElem* elem = _first;
  while(elem) {
    RooLinkedListElem* next = elem->_next ;
    delete elem->_arg ;
    deleteElement(elem) ;
    elem = next ;
  }
  _first = nullptr ;
  _last = nullptr ;
  _size = 0 ;
 
  if (_htableName) {
    _htableName = std::make_unique<HashTableByName>(_htableName->size()) ;
  }
  if (_htableLink) {
    _htableLink = std::make_unique<HashTableByLink>(_htableLink->size()) ;
  }
 
  // empty index array
  _at.clear();
}
 
////////////////////////////////////////////////////////////////////////////////
/// Return pointer to object with given name in collection.
/// If no such object is found, return null pointer.
 
TObject* RooLinkedList::find(const char* name) const
{
 
  if (_htableName) {
    auto found = _htableName->find(name);
    TObject *a = found != _htableName->end() ? const_cast<TObject*>(found->second) : nullptr;
    // RooHashTable::find could return false negative if element was renamed to 'name'.
    // The list search means it won't return false positive, so can return here.
    if (a) return a;
    if (_useNptr) {
      // See if it might have been renamed
      const TNamed* nptr= RooNameReg::known(name);
      //cout << "RooLinkedList::find: possibly renamed '" << name << "', kRenamedArg=" << (nptr&&nptr->TestBit(RooNameReg::kRenamedArg)) << endl;
      if (nptr && nptr->TestBit(RooNameReg::kRenamedArg)) {
        RooLinkedListElem* ptr = _first ;
        while(ptr) {
          if ( (dynamic_cast<RooAbsArg*>(ptr->_arg) && static_cast<RooAbsArg*>(ptr->_arg)->namePtr() == nptr) ||
               (dynamic_cast<RooAbsData*>(ptr->_arg) && static_cast<RooAbsData*>(ptr->_arg)->namePtr() == nptr)) {
            return ptr->_arg ;
          }
          ptr = ptr->_next ;
        }
      }
      return nullptr ;
    }
    //cout << "RooLinkedList::find: possibly renamed '" << name << "'" << endl;
  }
 
  RooLinkedListElem* ptr = _first ;
 
  // The penalty for RooNameReg lookup seems to be outweighted by the faster search
  // when the size list is longer than ~7, but let's be a bit conservative.
  if (_useNptr && _size>9) {
    const TNamed* nptr= RooNameReg::known(name);
    if (!nptr) return nullptr;
 
    while(ptr) {
      if ( (dynamic_cast<RooAbsArg*>(ptr->_arg) && static_cast<RooAbsArg*>(ptr->_arg)->namePtr() == nptr) ||
           (dynamic_cast<RooAbsData*>(ptr->_arg) && static_cast<RooAbsData*>(ptr->_arg)->namePtr() == nptr)) {
        return ptr->_arg ;
      }
      ptr = ptr->_next ;
    }
    return nullptr ;
  }
 
  while(ptr) {
    if (!strcmp(ptr->_arg->GetName(),name)) {
      return ptr->_arg ;
    }
    ptr = ptr->_next ;
  }
  return nullptr ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Return pointer to object with given name in collection.
/// If no such object is found, return null pointer.
 
RooAbsArg* RooLinkedList::findArg(const RooAbsArg* arg) const
{
  if (_htableName) {
    RooAbsArg* a = (RooAbsArg*) (*_htableName)[arg->GetName()] ;
    if (a) return a;
    //cout << "RooLinkedList::findArg: possibly renamed '" << arg->GetName() << "', kRenamedArg=" << arg->namePtr()->TestBit(RooNameReg::kRenamedArg) << endl;
    // See if it might have been renamed
    if (!arg->namePtr()->TestBit(RooNameReg::kRenamedArg)) return nullptr;
  }
 
  RooLinkedListElem* ptr = _first ;
  const TNamed* nptr = arg->namePtr();
  while(ptr) {
    if (((RooAbsArg*)(ptr->_arg))->namePtr() == nptr) {
      return (RooAbsArg*) ptr->_arg ;
    }
    ptr = ptr->_next ;
  }
  return nullptr ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Return position of given object in list. If object
/// is not contained in list, return -1
 
Int_t RooLinkedList::IndexOf(const TObject* arg) const
{
  RooLinkedListElem* ptr = _first;
  Int_t idx(0) ;
  while(ptr) {
    if (ptr->_arg==arg) return idx ;
    ptr = ptr->_next ;
    idx++ ;
  }
  return -1 ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Return position of given object in list. If object
/// is not contained in list, return -1
 
Int_t RooLinkedList::IndexOf(const char* name) const
{
  RooLinkedListElem* ptr = _first;
  Int_t idx(0) ;
  while(ptr) {
    if (strcmp(ptr->_arg->GetName(),name)==0) return idx ;
    ptr = ptr->_next ;
    idx++ ;
  }
  return -1 ;
}
 
////////////////////////////////////////////////////////////////////////////////
/// Print contents of list, defers to Print() function
/// of contained objects
 
void RooLinkedList::Print(const char* opt) const
{
  RooLinkedListElem* elem = _first ;
  while(elem) {
    cout << elem->_arg << " : " ;
    elem->_arg->Print(opt) ;
    elem = elem->_next ;
  }
}
 
////////////////////////////////////////////////////////////////////////////////
/// Create a TIterator for this list.
/// \param forward Run in forward direction (default).
/// \return Pointer to a TIterator. The caller owns the pointer.
 
TIterator* RooLinkedList::MakeIterator(bool forward) const {
  auto iterImpl = std::make_unique<RooLinkedListIterImpl>(this, forward);
  return new RooLinkedListIter(std::move(iterImpl));
}
 
////////////////////////////////////////////////////////////////////////////////
/// Create an iterator for this list.
/// \param forward Run in forward direction (default).
/// \return RooLinkedListIter (subclass of TIterator) over this list
 
RooLinkedListIter RooLinkedList::iterator(bool forward) const {
  auto iterImpl = std::make_unique<RooLinkedListIterImpl>(this, forward);
  return RooLinkedListIter(std::move(iterImpl));
}
 
////////////////////////////////////////////////////////////////////////////////
/// Create a one-time-use forward iterator for this list.
/// \return RooFIter that only supports next()
 
RooFIter RooLinkedList::fwdIterator() const {
  auto iterImpl = std::make_unique<RooFIterForLinkedList>(this);
  return RooFIter(std::move(iterImpl));
}
 
RooLinkedListIterImpl RooLinkedList::begin() const {
  return {this, true};
}
 
RooLinkedListIterImpl RooLinkedList::end() const {
  return {this, nullptr, true};
}
 
RooLinkedListIterImpl RooLinkedList::rbegin() const {
  return {this, false};
}
 
RooLinkedListIterImpl RooLinkedList::rend() const {
  return {this, nullptr, false};
}
 
////////////////////////////////////////////////////////////////////////////////
 
void RooLinkedList::Sort(bool ascend)
{
  if (ascend) _first = mergesort_impl<true>(_first, _size, &_last);
  else _first = mergesort_impl<false>(_first, _size, &_last);
 
  // rebuild index array
  RooLinkedListElem* elem = _first;
  for (auto it = _at.begin(); it != _at.end(); ++it, elem = elem->_next) {
    *it = elem;
  }
}
 
////////////////////////////////////////////////////////////////////////////////
/// length 0, 1 lists are sorted
 
template <bool ascending>
RooLinkedListElem* RooLinkedList::mergesort_impl(
    RooLinkedListElem* l1, const unsigned sz, RooLinkedListElem** tail)
{
  if (!l1 || sz < 2) {
    // if desired, update the tail of the (newly merged sorted) list
    if (tail) *tail = l1;
    return l1;
  }
  if (sz <= 16) {
    // for short lists, we sort in an array
    std::vector<RooLinkedListElem *> arr(sz, nullptr);
    for (int i = 0; l1; l1 = l1->_next, ++i) arr[i] = l1;
    // straight insertion sort
    {
   int i = 1;
   do {
       int j = i - 1;
       RooLinkedListElem *tmp = arr[i];
       while (0 <= j) {
      const bool inOrder = ascending ?
          (tmp->_arg->Compare(arr[j]->_arg) <= 0) :
          (arr[j]->_arg->Compare(tmp->_arg) <= 0);
      if (!inOrder) break;
      arr[j + 1] = arr[j];
      --j;
       }
       arr[j + 1] = tmp;
       ++i;
   } while (int(sz) != i);
    }
    // link elements in array
    arr[0]->_prev = arr[sz - 1]->_next = nullptr;
    for (int i = 0; i < int(sz - 1); ++i) {
      arr[i]->_next = arr[i + 1];
      arr[i + 1]->_prev = arr[i];
    }
    if (tail) *tail = arr[sz - 1];
    return arr[0];
  }
  // find middle of l1, and let a second list l2 start there
  RooLinkedListElem *l2 = l1;
  for (RooLinkedListElem *end = l2; end->_next; end = end->_next) {
    end = end->_next;
    l2 = l2->_next;
    if (!end->_next) break;
  }
  // disconnect the two sublists
  l2->_prev->_next = nullptr;
  l2->_prev = nullptr;
  // sort the two sublists (only recurse if we have to)
  if (l1->_next) l1 = mergesort_impl<ascending>(l1, sz / 2);
  if (l2->_next) l2 = mergesort_impl<ascending>(l2, sz - sz / 2);
  // merge the two (sorted) sublists
  // l: list head, t: list tail of merged list
  RooLinkedListElem *l = (ascending ? (l1->_arg->Compare(l2->_arg) <= 0) :
     (l2->_arg->Compare(l1->_arg) <= 0)) ? l1 : l2;
  RooLinkedListElem *t = l;
  if (l == l2) {
    RooLinkedListElem* tmp = l1;
    l1 = l2;
    l2 = tmp;
  }
  l1 = l1->_next;
  while (l1 && l2) {
    const bool inOrder = ascending ? (l1->_arg->Compare(l2->_arg) <= 0) :
   (l2->_arg->Compare(l1->_arg) <= 0);
    if (!inOrder) {
      // insert l2 just before l1
      if (l1->_prev) {
   l1->_prev->_next = l2;
   l2->_prev = l1->_prev;
      }
      // swap l2 and l1
      RooLinkedListElem *tmp = l1;
      l1 = l2;
      l2 = tmp;
    }
    // move forward in l1
    t = l1;
    l1 = l1->_next;
  }
  // attach l2 at t
  if (l2) {
    l2->_prev = t;
    if (t) t->_next = l2;
  }
  // if desired, update the tail of the (newly merged sorted) list
  if (tail) {
    for (l1 = t; l1; l1 = l1->_next) t = l1;
    *tail = t;
  }
  // return the head of the sorted list
  return l;
}
// void Roo1DTable::Streamer(TBuffer &R__b)
// {
//    // Stream an object of class Roo1DTable.
 
//    if (R__b.IsReading()) {
//       R__b.ReadClassBuffer(Roo1DTable::Class(),this);
//    } else {
//       R__b.WriteClassBuffer(Roo1DTable::Class(),this);
//    }
// }
 
////////////////////////////////////////////////////////////////////////////////
/// Custom streaming handling schema evolution w.r.t past implementations
 
void RooLinkedList::Streamer(TBuffer &R__b)
{
  if (R__b.IsReading()) {
 
    Version_t v = R__b.ReadVersion();
    //R__b.ReadVersion();
    TObject::Streamer(R__b);
 
    Int_t size ;
    TObject* arg ;
 
    R__b >> size ;
    while(size--) {
      R__b >> arg ;
      Add(arg) ;
    }
 
    if (v > 1 && v < 4) {
       R__b >> _name;
    }
 
  } else {
    R__b.WriteVersion(RooLinkedList::IsA());
    TObject::Streamer(R__b);
    R__b << _size ;
 
    RooLinkedListElem* ptr = _first;
    while(ptr) {
      R__b << ptr->_arg ;
      ptr = ptr->_next ;
    }
 
    R__b << _name ;
  }
}