include/root/TMap.h

0001 // @(#)root/cont:$Id$
0002 // Author: Fons Rademakers   12/11/95
0003
0004 /*************************************************************************
0005  * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
0006  * All rights reserved.                                                  *
0007  *                                                                       *
0008  * For the licensing terms see $ROOTSYS/LICENSE.                         *
0009  * For the list of contributors see $ROOTSYS/README/CREDITS.             *
0010  *************************************************************************/
0011
0012 #ifndef ROOT_TMap
0013 #define ROOT_TMap
0014
0015
0016 //////////////////////////////////////////////////////////////////////////
0017 //                                                                      //
0018 // TMap                                                                 //
0019 //                                                                      //
0020 // TMap implements an associative array of (key,value) pairs using a    //
0021 // hash table for efficient retrieval (therefore TMap does not conserve //
0022 // the order of the entries). The hash value is calculated              //
0023 // using the value returned by the keys Hash() function. Both key and   //
0024 // value need to inherit from TObject.                                  //
0025 //                                                                      //
0026 //////////////////////////////////////////////////////////////////////////
0027
0028 #include "TCollection.h"
0029 #include "THashTable.h"
0030
0031 #include <iterator>
0032
0033
0034 class THashTableIter;
0035 class TMapIter;
0036 class TPair;
0037 class TBrowser;
0038
0039
0040 class TMap : public TCollection {
0041
0042 friend class  TMapIter;
0043
0044 private:
0045    THashTable   *fTable;     //Hash table used to store TPair's
0046
0047    TMap(const TMap& map) = delete;
0048    TMap& operator=(const TMap& map) = delete;
0049
0050 protected:
0051    enum EStatusBits { kIsOwnerValue = BIT(15) };
0052
0053    void        PrintCollectionEntry(TObject* entry, Option_t* option, Int_t recurse) const override;
0054
0055 public:
0056    typedef TMapIter Iterator_t;
0057
0058    TMap(Int_t capacity = TCollection::kInitHashTableCapacity, Int_t rehash = 0);
0059    virtual           ~TMap();
0060    void              Add(TObject *obj) override;
0061    void              Add(TObject *key, TObject *value);
0062    Float_t           AverageCollisions() const;
0063    Int_t             Capacity() const;
0064    void              Clear(Option_t *option="") override;
0065    Int_t             Collisions(const char *keyname) const;
0066    Int_t             Collisions(TObject *key) const;
0067    void              Delete(Option_t *option="") override;
0068    void              DeleteKeys() { Delete(); }
0069    void              DeleteValues();
0070    void              DeleteAll();
0071    Bool_t            DeleteEntry(TObject *key);
0072    TObject          *FindObject(const char *keyname) const override;
0073    TObject          *FindObject(const TObject *key) const override;
0074    TObject         **GetObjectRef(const TObject *obj) const override { return fTable->GetObjectRef(obj); }
0075    const THashTable *GetTable() const { return fTable; }
0076    TObject          *GetValue(const char *keyname) const;
0077    TObject          *GetValue(const TObject *key) const;
0078    Bool_t            IsOwnerValue() const { return TestBit(kIsOwnerValue); }
0079    TObject          *operator()(const char *keyname) const { return GetValue(keyname); }
0080    TObject          *operator()(const TObject *key) const { return GetValue(key); }
0081    TIterator        *MakeIterator(Bool_t dir = kIterForward) const override;
0082    void              Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
0083    TObject          *Remove(TObject *key) override;
0084    TPair            *RemoveEntry(TObject *key);
0085    virtual void      SetOwnerValue(Bool_t enable = kTRUE);
0086    virtual void      SetOwnerKeyValue(Bool_t ownkeys = kTRUE, Bool_t ownvals = kTRUE);
0087    Int_t             Write(const char *name=nullptr, Int_t option=0, Int_t bufsize=0) override;
0088    Int_t             Write(const char *name=nullptr, Int_t option=0, Int_t bufsize=0) const override;
0089
0090    ClassDefOverride(TMap,3)  //A (key,value) map
0091 };
0092
0093
0094 //////////////////////////////////////////////////////////////////////////
0095 //                                                                      //
0096 // TPair                                                                //
0097 //                                                                      //
0098 // Class used by TMap to store (key,value) pairs.                       //
0099 //                                                                      //
0100 //////////////////////////////////////////////////////////////////////////
0101
0102 class TPair : public TObject {
0103
0104 private:
0105    TObject  *fKey;
0106    TObject  *fValue;
0107
0108    TPair& operator=(const TPair&) = delete;
0109
0110 public:
0111    TPair(TObject *key, TObject *value) : fKey(key), fValue(value) { }
0112    TPair(const TPair &a) : TObject(), fKey(a.fKey), fValue(a.fValue) { }
0113    virtual               ~TPair();
0114    Bool_t                IsFolder() const override { return kTRUE;}
0115    void                  Browse(TBrowser *b) override;
0116    const char           *GetName() const override { return fKey->GetName(); }
0117    const char           *GetTitle() const override { return fKey->GetTitle(); }
0118    ULong_t               Hash() const override { return fKey->Hash(); }
0119    Bool_t                IsEqual(const TObject *obj) const override { return fKey->IsEqual(obj); }
0120    TObject              *Key() const { return fKey; }
0121    TObject              *Value() const { return fValue; }
0122    void                  SetValue(TObject *val) { fValue = val; }
0123
0124    ClassDefOverride(TPair,0); // Pair TObject*, TObject*
0125 };
0126
0127 typedef TPair   TAssoc;     // for backward compatibility
0128
0129
0130 // Preventing warnings with -Weffc++ in GCC since it is a false positive for the TMapIter destructor.
0131 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
0132 #pragma GCC diagnostic push
0133 #pragma GCC diagnostic ignored "-Weffc++"
0134 #endif
0135
0136 //////////////////////////////////////////////////////////////////////////
0137 //                                                                      //
0138 // TMapIter                                                             //
0139 //                                                                      //
0140 // Iterator of a map.                                                   //
0141 //                                                                      //
0142 //////////////////////////////////////////////////////////////////////////
0143
0144 class TMapIter : public TIterator {
0145
0146 private:
0147    const TMap       *fMap;         //map being iterated
0148    THashTableIter   *fCursor;      //current position in map
0149    Bool_t            fDirection;   //iteration direction
0150
0151    TMapIter() : fMap(nullptr), fCursor(nullptr), fDirection(kIterForward) { }
0152
0153 public:
0154    using iterator_category = std::bidirectional_iterator_tag;
0155    using value_type = TObject *;
0156    using difference_type = std::ptrdiff_t;
0157    using pointer = TObject **;
0158    using const_pointer = const TObject **;
0159    using reference = const TObject *&;
0160
0161    TMapIter(const TMap *map, Bool_t dir = kIterForward);
0162    TMapIter(const TMapIter &iter);
0163    ~TMapIter();
0164    TIterator &operator=(const TIterator &rhs) override;
0165    TMapIter  &operator=(const TMapIter &rhs);
0166
0167    const TCollection *GetCollection() const override { return fMap; }
0168    TObject           *Next() override;
0169    void               Reset() override;
0170    Bool_t             operator!=(const TIterator &aIter) const override;
0171    Bool_t             operator!=(const TMapIter &aIter) const;
0172    TObject           *operator*() const override;
0173
0174    ClassDefOverride(TMapIter,0)  //Map iterator
0175 };
0176
0177 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
0178 #pragma GCC diagnostic pop
0179 #endif
0180
0181 #endif