include/root/RooLinkedList.h

0001 /*****************************************************************************
0002  * Project: RooFit                                                           *
0003  * Package: RooFitCore                                                       *
0004  *    File: $Id: RooLinkedList.h,v 1.15 2007/05/11 09:11:30 verkerke Exp $
0005  * Authors:                                                                  *
0006  *   WV, Wouter Verkerke, UC Santa Barbara, verkerke@slac.stanford.edu       *
0007  *   DK, David Kirkby,    UC Irvine,         dkirkby@uci.edu                 *
0008  *                                                                           *
0009  * Copyright (c) 2000-2005, Regents of the University of California          *
0010  *                          and Stanford University. All rights reserved.    *
0011  *                                                                           *
0012  * Redistribution and use in source and binary forms,                        *
0013  * with or without modification, are permitted according to the terms        *
0014  * listed in LICENSE (http://roofit.sourceforge.net/license.txt)             *
0015  *****************************************************************************/
0016 #ifndef ROO_LINKED_LIST
0017 #define ROO_LINKED_LIST
0018
0019 #include "TObject.h"
0020 #include "RooLinkedListElem.h"
0021 #include "TString.h"
0022
0023 #include <vector>
0024 #include <memory>
0025 #include <unordered_map>
0026
0027 class RooLinkedListIter ;
0028 class RooLinkedListIterImpl ;
0029 class RooFIter;
0030 class TIterator ;
0031 class RooAbsArg ;
0032 template<class T>
0033 class RooSTLRefCountList;
0034
0035 /// \cond ROOFIT_INTERNAL
0036
0037 namespace RooLinkedListImplDetails {
0038     class Chunk;
0039     class Pool;
0040 }
0041
0042 /// \endcond
0043
0044 class RooLinkedList : public TObject {
0045 public:
0046   // Constructor
0047   RooLinkedList(Int_t htsize=0) ;
0048
0049   // Copy constructor
0050   RooLinkedList(const RooLinkedList& other) ;
0051
0052   TObject* Clone(const char* =nullptr) const override {
0053     return new RooLinkedList(*this) ;
0054   }
0055
0056   // Assignment operator
0057   RooLinkedList& operator=(const RooLinkedList& other) ;
0058
0059   Int_t getHashTableSize() const {
0060     // Return size of hash table
0061     return _htableName ? _htableName->size() : 0 ;
0062   }
0063
0064   void setHashTableSize(Int_t size) ;
0065
0066   // Destructor
0067   ~RooLinkedList() override ;
0068
0069   Int_t GetSize() const { return _size ; }
0070   std::size_t size() const { return _size ; }
0071   bool empty() const { return _size == 0 ; }
0072
0073   virtual void Add(TObject* arg) { Add(arg,1) ; }
0074   virtual bool Remove(TObject* arg) ;
0075   TObject* At(int index) const ;
0076   bool Replace(const TObject* oldArg, const TObject* newArg) ;
0077   TIterator* MakeIterator(bool forward = true) const ;
0078   RooLinkedListIter iterator(bool forward = true) const ;
0079   RooFIter fwdIterator() const ;
0080   RooLinkedListIterImpl begin() const;
0081   RooLinkedListIterImpl end() const;
0082   RooLinkedListIterImpl rbegin() const;
0083   RooLinkedListIterImpl rend() const;
0084
0085   void Clear(Option_t *o=nullptr) override ;
0086   void Delete(Option_t *o=nullptr) override ;
0087   TObject* find(const char* name) const ;
0088   RooAbsArg* findArg(const RooAbsArg*) const ;
0089   TObject* FindObject(const char* name) const override ;
0090   TObject* FindObject(const TObject* obj) const override ;
0091   Int_t IndexOf(const char* name) const ;
0092   Int_t IndexOf(const TObject* arg) const ;
0093   TObject* First() const {
0094     return _first ? _first->_arg : nullptr ;
0095   }
0096
0097   void RecursiveRemove(TObject *obj) override;
0098
0099   void Print(const char* opt) const override ;
0100   void Sort(bool ascend=true) ;
0101
0102   // const char* GetName() const { return "" ; /*_name.Data() ; */ }
0103   // void SetName(const char* /*name*/) { /*_name = name ; */ }
0104   const char* GetName() const override { return _name.Data() ;  }
0105   void SetName(const char* name) { _name = name ;  }
0106
0107    void useNptr(bool flag) { _useNptr = flag ; }
0108    // needed for using it in THashList/THashTable
0109
0110    ULong_t  Hash() const override { return _name.Hash(); }
0111
0112 protected:
0113
0114   RooLinkedListElem* createElement(TObject* obj, RooLinkedListElem* elem=nullptr) ;
0115   void deleteElement(RooLinkedListElem*) ;
0116
0117   template<class T> friend class RooSTLRefCountList;
0118   friend class RooLinkedListIterImpl ;
0119   friend class RooFIterForLinkedList ;
0120
0121   virtual void Add(TObject* arg, Int_t refCount) ;
0122
0123   RooLinkedListElem* findLink(const TObject* arg) const ;
0124
0125   Int_t _hashThresh ;          ///<  Size threshold for hashing
0126   Int_t _size ;                ///<  Current size of list
0127   RooLinkedListElem*  _first ; ///<! Link to first element of list
0128   RooLinkedListElem*  _last ;  ///<! Link to last element of list
0129
0130   using HashTableByName = std::unordered_map<std::string,TObject const*>;
0131   using HashTableByLink = std::unordered_map<TObject const*,TObject const*>;
0132   std::unique_ptr<HashTableByName> _htableName; ///<! Hash table by name
0133   std::unique_ptr<HashTableByLink> _htableLink; ///<! Hash table by link pointer
0134
0135   TString             _name ;
0136   bool              _useNptr ; ///<!
0137
0138 private:
0139   template <bool ascending>
0140   static RooLinkedListElem* mergesort_impl(RooLinkedListElem* l1,
0141      const unsigned sz, RooLinkedListElem** tail = nullptr);
0142   /// memory pool for quick allocation of RooLinkedListElems
0143   typedef RooLinkedListImplDetails::Pool Pool;
0144   /// shared memory pool for allocation of RooLinkedListElems
0145   static Pool* _pool; //!
0146
0147   std::vector<RooLinkedListElem *> _at; ///<! index list for quick index through ::At
0148
0149   ClassDefOverride(RooLinkedList,3) // Doubly linked list for storage of RooAbsArg objects
0150 };
0151
0152 #endif