src/libengrid/eghashset.h

   1 //
   2 // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   3 // +                                                                      +
   4 // + This file is part of enGrid.                                         +
   5 // +                                                                      +
   6 // + Copyright 2008-2013 enGits GmbH                                      +
   7 // +                                                                      +
   8 // + enGrid is free software: you can redistribute it and/or modify       +
   9 // + it under the terms of the GNU General Public License as published by +
  10 // + the Free Software Foundation, either version 3 of the License, or    +
  11 // + (at your option) any later version.                                  +
  12 // +                                                                      +
  13 // + enGrid is distributed in the hope that it will be useful,            +
  14 // + but WITHOUT ANY WARRANTY; without even the implied warranty of       +
  15 // + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the        +
  16 // + GNU General Public License for more details.                         +
  17 // +                                                                      +
  18 // + You should have received a copy of the GNU General Public License    +
  19 // + along with enGrid. If not, see <http://www.gnu.org/licenses/>.       +
  20 // +                                                                      +
  21 // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
  22 //
  23 #ifndef SORTEDHASHSET_H
  24 #define SORTEDHASHSET_H
  25
  26 template <class T> class EgHashSet;
  27
  28 #include <QList>
  29
  30 template <class T>
  31 class EgHashSet
  32 {
  33
  34 private: // data types
  35
  36   struct entry_t
  37   {
  38     T   value;
  39     int index;
  40   };
  41
  42 private: // attributes
  43
  44   QVector<QList<entry_t> > m_Buckets;
  45   int                      m_NumEntries;
  46   QVector<int>             m_Old2NewIndex;
  47
  48 public: // methods
  49
  50   EgHashSet();
  51   EgHashSet(int size);
  52
  53   void resize(int size);
  54   void clear();
  55   int  insert(const T &item);
  56   void getQVector(QVector<T> &qv);
  57   void updateIndexMap();
  58   int  newIndex(int old_index) { return m_Old2NewIndex[old_index]; }
  59
  60 };
  61
  62 template <class T>
  63 EgHashSet<T>::EgHashSet()
  64 {
  65   clear();
  66 }
  67
  68 template <class T>
  69 EgHashSet<T>::EgHashSet(int size)
  70 {
  71   clear();
  72   m_Buckets.resize(size);
  73 }
  74
  75 template <class T>
  76 void EgHashSet<T>::resize(int size)
  77 {
  78   clear();
  79   m_Buckets.resize(size);
  80 }
  81
  82 template <class T>
  83 void EgHashSet<T>::clear()
  84 {
  85   m_Buckets.clear();
  86   m_NumEntries = 0;
  87 }
  88
  89 template <class T>
  90 int EgHashSet<T>::insert(const T &item)
  91 {
  92   QList<entry_t> &list = m_Buckets[item.hash()];
  93   int idx = 0;
  94   while (idx < list.size()) {
  95     if (!(item < list[idx].value)) {
  96       break;
  97     }
  98     ++ idx;
  99   }
 100   if (idx < list.size()) {
 101     if (item == list[idx].value) {
 102       return list[idx].index;
 103     }
 104   }
 105   entry_t entry;
 106   entry.value = item;
 107   entry.index = m_NumEntries;
 108   list.insert(idx, entry);
 109   ++m_NumEntries;
 110   return entry.index;
 111 }
 112
 113 template <class T>
 114 void EgHashSet<T>::updateIndexMap()
 115 {
 116   int idx = 0;
 117   m_Old2NewIndex.clear();
 118   m_Old2NewIndex.fill(-1, m_NumEntries);
 119   for (int i = 0; i < m_Buckets.size(); ++i) {
 120     foreach (entry_t entry, m_Buckets[i]) {
 121       m_Old2NewIndex[entry.index] = idx;
 122       ++idx;
 123     }
 124   }
 125 }
 126
 127 template <class T>
 128 void EgHashSet<T>::getQVector(QVector<T> &qv)
 129 {
 130   updateIndexMap();
 131   qv.clear();
 132   qv.resize(m_NumEntries);
 133   QVector<bool> entry_set(m_NumEntries, false);
 134   for (int i = 0; i < m_Buckets.size(); ++i) {
 135     foreach (entry_t entry, m_Buckets[i]) {
 136       qv[entry.index] = entry.value;
 137       entry_set[entry.index] = true;
 138     }
 139   }
 140   foreach (bool is_set, entry_set) {
 141     if (!is_set) {
 142       EG_BUG;
 143     }
 144   }
 145 }
 146
 147 #endif // SORTEDHASHSET_H