WDL/ptrlist_indexed.h

   1 #ifndef _WDL_PTRLIST_INDEXED_H_
   2 #define _WDL_PTRLIST_INDEXED_H_
   3
   4 #include "assocarray.h"
   5 #include "ptrlist.h"
   6
   7 template<class T> class WDL_IndexedPtrList {
   8   public:
   9     WDL_IndexedPtrList() { }
  10     ~WDL_IndexedPtrList() { }
  11
  12     int GetSize() const {
  13       // do not _checkState(), GetSize() may be called while unlocked for estimation purposes
  14       return m_list.GetSize();
  15     }
  16     T * const *GetList() const { _checkState(); return m_list.GetList(); }
  17     T *Get(INT_PTR idx) const { _checkState(); return m_list.Get(idx); }
  18     int Find(const T *p) const
  19     {
  20       _checkState();
  21       if (!p) return -1;
  22       const int *ret = m_index.GetPtr((INT_PTR)p);
  23       return ret ? *ret : -1;
  24     }
  25     void Empty() { _checkState(); m_list.Empty(); m_index.DeleteAll(); }
  26     void Empty(bool wantDelete, void (*delfunc)(void*)=NULL) { _checkState(); m_list.Empty(wantDelete,delfunc); m_index.DeleteAll(); }
  27     void Delete(int idx, bool wantDelete=false, void (*delfunc)(void *)=NULL)
  28     {
  29       _checkState();
  30       T *item = m_list.Get(idx);
  31       m_list.Delete(idx,wantDelete,delfunc);
  32       if (item)
  33       {
  34         m_index.Delete((INT_PTR)item);
  35         const int indexsz = m_index.GetSize();
  36         WDL_ASSERT(m_list.GetSize() == indexsz);
  37         if (idx < indexsz)
  38         {
  39           for (int x=0;x<indexsz;x++)
  40           {
  41             int *val = m_index.EnumeratePtr(x);
  42             if (WDL_NORMALLY(val))
  43             {
  44               WDL_ASSERT(*val != idx);
  45               if (*val > idx) (*val)--;
  46             }
  47           }
  48         }
  49       }
  50     }
  51     void DeletePtr(const T *p) { Delete(Find(p)); }
  52     void DeletePtr(const T *p, bool wantDelete, void (*delfunc)(void *)=NULL) { Delete(Find(p),wantDelete,delfunc); }
  53     void Add(T *p)
  54     {
  55       _checkState();
  56       WDL_ASSERT(Find(p) < 0);
  57       if (WDL_NORMALLY(p))
  58       {
  59         const int sz = m_list.GetSize();
  60         m_list.Add(p);
  61         m_index.Insert((INT_PTR)p,sz);
  62       }
  63     }
  64     void RebuildIndex()
  65     {
  66       m_index.DeleteAll();
  67       for (int x = 0; x < m_list.GetSize(); x ++)
  68       {
  69         m_index.AddUnsorted((INT_PTR)m_list.Get(x),x);
  70       }
  71       m_index.Resort();
  72       _checkState();
  73     }
  74     void Swap(int index1, int index2)
  75     {
  76       _checkState();
  77       if (index1 != index2 &&
  78           WDL_NORMALLY(index1>=0) &&
  79           WDL_NORMALLY(index1<m_list.GetSize()) &&
  80           WDL_NORMALLY(index2>=0) &&
  81           WDL_NORMALLY(index2<m_list.GetSize()))
  82       {
  83         T **list = m_list.GetList();
  84         T *a = list[index1];
  85         T *b = list[index2];
  86         list[index2]=a;
  87         list[index1]=b;
  88         m_index.Insert((INT_PTR)a,index2);
  89         m_index.Insert((INT_PTR)b,index1);
  90       }
  91     }
  92     void Insert(int index, T *p)
  93     {
  94       _checkState();
  95       if (!WDL_NORMALLY(p)) return;
  96       const int listsz = m_list.GetSize();
  97       if (index < 0) index=0;
  98       if (index >= listsz) { Add(p); return; }
  99
 100       const int indexsz = m_index.GetSize();
 101       WDL_ASSERT(listsz==indexsz);
 102
 103       for (int x=0;x<indexsz;x++)
 104       {
 105         int *val = m_index.EnumeratePtr(x);
 106         if (WDL_NORMALLY(val))
 107         {
 108           if (*val >= index) (*val)++;
 109           WDL_ASSERT(*val != index);
 110         }
 111       }
 112       m_list.Insert(index,p);
 113       m_index.Insert((INT_PTR)p,index);
 114     }
 115
 116     WDL_PtrList<T> m_list;
 117     WDL_PtrKeyedArray<int> m_index;
 118
 119     WDL_IndexedPtrList<T> &operator=(const WDL_IndexedPtrList<T> &cp)
 120     {
 121       m_list = cp.m_list;
 122       RebuildIndex();
 123       return *this;
 124     }
 125
 126     void _checkState() const
 127     {
 128 #ifdef _DEBUG
 129       const int idxsz = m_index.GetSize(), listsz = m_list.GetSize();
 130       WDL_ASSERT(idxsz == listsz);
 131 #endif
 132     }
 133 };
 134
 135 #endif