src/libengrid/eghashset.h

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