// @(#)root/cont:$Id$
// Author: Fons Rademakers 10/08/95
/*************************************************************************
* Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. *
* All rights reserved. *
* *
* For the licensing terms see $ROOTSYS/LICENSE. *
* For the list of contributors see $ROOTSYS/README/CREDITS. *
*************************************************************************/
#ifndef ROOT_TList
#define ROOT_TList
//////////////////////////////////////////////////////////////////////////
// //
// TList //
// //
// A doubly linked list. All classes inheriting from TObject can be //
// inserted in a TList. //
// //
//////////////////////////////////////////////////////////////////////////
#include "TSeqCollection.h"
#include "TString.h"
#include <iterator>
#include <memory>
const Bool_t kSortAscending = kTRUE;
const Bool_t kSortDescending = !kSortAscending;
class TObjLink;
class TListIter;
class TList : public TSeqCollection {
friend class TListIter;
protected:
using TObjLinkPtr_t = std::shared_ptr<TObjLink>;
using TObjLinkWeakPtr_t = std::weak_ptr<TObjLink>;
TObjLinkPtr_t fFirst; //! pointer to first entry in linked list
TObjLinkPtr_t fLast; //! pointer to last entry in linked list
TObjLinkWeakPtr_t fCache; //! cache to speedup sequential calling of Before() and After() functions
Bool_t fAscending; //! sorting order (when calling Sort() or for TSortedList)
TObjLink *LinkAt(Int_t idx) const;
TObjLink *FindLink(const TObject *obj, Int_t &idx) const;
TObjLinkPtr_t *DoSort(TObjLinkPtr_t *head, Int_t n);
Bool_t LnkCompare(const TObjLinkPtr_t &l1, const TObjLinkPtr_t &l2);
TObjLinkPtr_t NewLink(TObject *obj, const TObjLinkPtr_t &prev = nullptr);
TObjLinkPtr_t NewOptLink(TObject *obj, Option_t *opt, const TObjLinkPtr_t &prev = nullptr);
TObjLinkPtr_t NewLink(TObject *obj, TObjLink *prev);
TObjLinkPtr_t NewOptLink(TObject *obj, Option_t *opt, TObjLink *prev);
// virtual void DeleteLink(TObjLink *lnk);
void InsertAfter(const TObjLinkPtr_t &newlink, const TObjLinkPtr_t &prev);
private:
TList(const TList&) = delete;
TList& operator=(const TList&) = delete;
public:
typedef TListIter Iterator_t;
TList() : fAscending(kTRUE) { }
TList(TObject *) : fAscending(kTRUE) { } // for backward compatibility, don't use
virtual ~TList();
void Clear(Option_t *option="") override;
void Delete(Option_t *option="") override;
TObject *FindObject(const char *name) const override;
TObject *FindObject(const TObject *obj) const override;
TIterator *MakeIterator(Bool_t dir = kIterForward) const override;
void Add(TObject *obj) override { AddLast(obj); }
virtual void Add(TObject *obj, Option_t *opt) { AddLast(obj, opt); }
void AddFirst(TObject *obj) override;
virtual void AddFirst(TObject *obj, Option_t *opt);
void AddLast(TObject *obj) override;
virtual void AddLast(TObject *obj, Option_t *opt);
void AddAt(TObject *obj, Int_t idx) override;
void AddAfter(const TObject *after, TObject *obj) override;
virtual void AddAfter(TObjLink *after, TObject *obj);
void AddBefore(const TObject *before, TObject *obj) override;
virtual void AddBefore(TObjLink *before, TObject *obj);
TObject *Remove(TObject *obj) override;
virtual TObject *Remove(TObjLink *lnk);
TObject *Remove(const TObjLinkPtr_t &lnk) { return Remove(lnk.get()); }
void RemoveLast() override;
void RecursiveRemove(TObject *obj) override;
TObject *At(Int_t idx) const override;
TObject *After(const TObject *obj) const override;
TObject *Before(const TObject *obj) const override;
TObject *First() const override;
virtual TObjLink *FirstLink() const { return fFirst.get(); }
TObject **GetObjectRef(const TObject *obj) const override;
TObject *Last() const override;
virtual TObjLink *LastLink() const { return fLast.get(); }
virtual void Sort(Bool_t order = kSortAscending);
Bool_t IsAscending() { return fAscending; }
ClassDefOverride(TList,5) //Doubly linked list
};
//////////////////////////////////////////////////////////////////////////
// //
// TObjLink //
// //
// Wrapper around a TObject so it can be stored in a TList. //
// //
//////////////////////////////////////////////////////////////////////////
class TObjLink : public std::enable_shared_from_this<TObjLink> {
friend class TList;
private:
using TObjLinkPtr_t = std::shared_ptr<TObjLink>;
using TObjLinkWeakPtr_t = std::weak_ptr<TObjLink>;
TObjLinkPtr_t fNext;
TObjLinkWeakPtr_t fPrev;
TObject *fObject; // should be atomic ...
TObjLink(const TObjLink&) = delete;
TObjLink& operator=(const TObjLink&) = delete;
TObjLink() = delete;
public:
TObjLink(TObject *obj) : fObject(obj) { }
virtual ~TObjLink() { }
TObject *GetObject() const { return fObject; }
TObject **GetObjectRef() { return &fObject; }
void SetObject(TObject *obj) { fObject = obj; }
virtual Option_t *GetAddOption() const { return ""; }
virtual Option_t *GetOption() const { return fObject->GetOption(); }
virtual void SetOption(Option_t *) { }
TObjLink *Next() { return fNext.get(); }
TObjLink *Prev() { return fPrev.lock().get(); }
TObjLinkPtr_t NextSP() { return fNext; }
TObjLinkPtr_t PrevSP() { return fPrev.lock(); }
};
//////////////////////////////////////////////////////////////////////////
// //
// TObjOptLink //
// //
// Wrapper around a TObject so it can be stored in a TList including //
// an option string. //
// //
//////////////////////////////////////////////////////////////////////////
class TObjOptLink : public TObjLink {
private:
TString fOption;
public:
TObjOptLink(TObject *obj, Option_t *opt) : TObjLink(obj), fOption(opt) { }
~TObjOptLink() { }
Option_t *GetAddOption() const override { return fOption.Data(); }
Option_t *GetOption() const override { return fOption.Data(); }
void SetOption(Option_t *option) override { fOption = option; }
};
// Preventing warnings with -Weffc++ in GCC since it is a false positive for the TListIter destructor.
#if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Weffc++"
#endif
//////////////////////////////////////////////////////////////////////////
// //
// TListIter //
// //
// Iterator of linked list. //
// //
//////////////////////////////////////////////////////////////////////////
class TListIter : public TIterator {
protected:
using TObjLinkPtr_t = std::shared_ptr<TObjLink>;
const TList *fList; //list being iterated
TObjLinkPtr_t fCurCursor; //current position in list
TObjLinkPtr_t fCursor; //next position in list
Bool_t fDirection; //iteration direction
Bool_t fStarted; //iteration started
TListIter() : fList(nullptr), fCurCursor(), fCursor(), fDirection(kIterForward),
fStarted(kFALSE) { }
public:
using iterator_category = std::bidirectional_iterator_tag;
using value_type = TObject *;
using difference_type = std::ptrdiff_t;
using pointer = TObject **;
using const_pointer = const TObject **;
using reference = const TObject *&;
TListIter(const TList *l, Bool_t dir = kIterForward);
TListIter(const TListIter &iter);
~TListIter() { }
TIterator &operator=(const TIterator &rhs) override;
TListIter &operator=(const TListIter &rhs);
const TCollection *GetCollection() const override { return fList; }
Option_t *GetOption() const override;
void SetOption(Option_t *option);
TObject *Next() override;
void Reset() override;
Bool_t operator!=(const TIterator &aIter) const override;
Bool_t operator!=(const TListIter &aIter) const;
TObject *operator*() const override { return (fCurCursor ? fCurCursor->GetObject() : nullptr); }
ClassDefOverride(TListIter,0) //Linked list iterator
};
inline bool operator==(TObjOptLink *l, const std::shared_ptr<TObjLink> &r) {
return l == r.get();
}
inline bool operator==(const std::shared_ptr<TObjLink> &l, TObjOptLink *r) {
return r == l;
}
inline TList::TObjLinkPtr_t TList::NewLink(TObject *obj, TObjLink *prev) {
return NewLink(obj, prev ? prev->shared_from_this() : nullptr);
}
inline TList::TObjLinkPtr_t TList::NewOptLink(TObject *obj, Option_t *opt, TObjLink *prev) {
return NewOptLink(obj, opt, prev ? prev->shared_from_this() : nullptr);
}
#if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
#pragma GCC diagnostic pop
#endif
#endif