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 *obj, Option_t *) override { Add(obj); };
0062    void              Add(TObject *key, TObject *value);
0063    Float_t           AverageCollisions() const;
0064    Int_t             Capacity() const;
0065    void              Clear(Option_t *option="") override;
0066    Int_t             Collisions(const char *keyname) const;
0067    Int_t             Collisions(TObject *key) const;
0068    void              Delete(Option_t *option="") override;
0069    void              DeleteKeys() { Delete(); }
0070    void              DeleteValues();
0071    void              DeleteAll();
0072    Bool_t            DeleteEntry(TObject *key);
0073    TObject          *FindObject(const char *keyname) const override;
0074    TObject          *FindObject(const TObject *key) const override;
0075    TObject         **GetObjectRef(const TObject *obj) const override { return fTable->GetObjectRef(obj); }
0076    const THashTable *GetTable() const { return fTable; }
0077    TObject          *GetValue(const char *keyname) const;
0078    TObject          *GetValue(const TObject *key) const;
0079    Bool_t            IsOwnerValue() const { return TestBit(kIsOwnerValue); }
0080    TObject          *operator()(const char *keyname) const { return GetValue(keyname); }
0081    TObject          *operator()(const TObject *key) const { return GetValue(key); }
0082    TIterator        *MakeIterator(Bool_t dir = kIterForward) const override;
0083    void              Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
0084    TObject          *Remove(TObject *key) override;
0085    TPair            *RemoveEntry(TObject *key);
0086    virtual void      SetOwnerValue(Bool_t enable = kTRUE);
0087    virtual void      SetOwnerKeyValue(Bool_t ownkeys = kTRUE, Bool_t ownvals = kTRUE);
0088    Int_t             Write(const char *name=nullptr, Int_t option=0, Int_t bufsize=0) override;
0089    Int_t             Write(const char *name=nullptr, Int_t option=0, Int_t bufsize=0) const override;
0090
0091    ClassDefOverride(TMap,3)  //A (key,value) map
0092 };
0093
0094
0095 //////////////////////////////////////////////////////////////////////////
0096 //                                                                      //
0097 // TPair                                                                //
0098 //                                                                      //
0099 // Class used by TMap to store (key,value) pairs.                       //
0100 //                                                                      //
0101 //////////////////////////////////////////////////////////////////////////
0102
0103 class TPair : public TObject {
0104
0105 private:
0106    TObject  *fKey;
0107    TObject  *fValue;
0108
0109    TPair& operator=(const TPair&) = delete;
0110
0111 public:
0112    TPair(TObject *key, TObject *value) : fKey(key), fValue(value) { }
0113    TPair(const TPair &a) : TObject(), fKey(a.fKey), fValue(a.fValue) { }
0114    virtual               ~TPair();
0115    Bool_t                IsFolder() const override { return kTRUE;}
0116    void                  Browse(TBrowser *b) override;
0117    const char           *GetName() const override { return fKey->GetName(); }
0118    const char           *GetTitle() const override { return fKey->GetTitle(); }
0119    ULong_t               Hash() const override { return fKey->Hash(); }
0120    Bool_t                IsEqual(const TObject *obj) const override { return fKey->IsEqual(obj); }
0121    TObject              *Key() const { return fKey; }
0122    TObject              *Value() const { return fValue; }
0123    void                  SetValue(TObject *val) { fValue = val; }
0124
0125    ClassDefOverride(TPair,0); // Pair TObject*, TObject*
0126 };
0127
0128 typedef TPair   TAssoc;     // for backward compatibility
0129
0130
0131 // Preventing warnings with -Weffc++ in GCC since it is a false positive for the TMapIter destructor.
0132 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
0133 #pragma GCC diagnostic push
0134 #pragma GCC diagnostic ignored "-Weffc++"
0135 #endif
0136
0137 //////////////////////////////////////////////////////////////////////////
0138 //                                                                      //
0139 // TMapIter                                                             //
0140 //                                                                      //
0141 // Iterator of a map.                                                   //
0142 //                                                                      //
0143 //////////////////////////////////////////////////////////////////////////
0144
0145 class TMapIter : public TIterator {
0146
0147 private:
0148    const TMap       *fMap;         //map being iterated
0149    THashTableIter   *fCursor;      //current position in map
0150    Bool_t            fDirection;   //iteration direction
0151
0152    TMapIter() : fMap(nullptr), fCursor(nullptr), fDirection(kIterForward) { }
0153
0154 public:
0155    using iterator_category = std::bidirectional_iterator_tag;
0156    using value_type = TObject *;
0157    using difference_type = std::ptrdiff_t;
0158    using pointer = TObject **;
0159    using const_pointer = const TObject **;
0160    using reference = const TObject *&;
0161
0162    TMapIter(const TMap *map, Bool_t dir = kIterForward);
0163    TMapIter(const TMapIter &iter);
0164    ~TMapIter();
0165    TIterator &operator=(const TIterator &rhs) override;
0166    TMapIter  &operator=(const TMapIter &rhs);
0167
0168    const TCollection *GetCollection() const override { return fMap; }
0169    TObject           *Next() override;
0170    void               Reset() override;
0171    Bool_t             operator!=(const TIterator &aIter) const override;
0172    Bool_t             operator!=(const TMapIter &aIter) const;
0173    TObject           *operator*() const override;
0174
0175    ClassDefOverride(TMapIter,0)  //Map iterator
0176 };
0177
0178 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
0179 #pragma GCC diagnostic pop
0180 #endif
0181
0182 #endif