← Back to branch summary

~ubuntu-branches/ubuntu/wily/qgis/wily

« back to all changes in this revision

Viewing changes to src/core/pal/hashtable.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Johan Van de Wauw
  • Date: 2010-07-11 20:23:24 UTC
  • mfrom: (3.1.4 squeeze)
  • Revision ID: james.westby@ubuntu.com-20100711202324-5ktghxa7hracohmr
Tags: 1.4.0+12730-3ubuntu1
https://launchpad.net/bugs/540941
* Merge from Debian unstable (LP: #540941).
* Fix compilation issues with QT 4.7
* Add build-depends on libqt4-webkit-dev 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/pal/hashtable.hpp
 
1
/*
 
2
 *   libpal - Automated Placement of Labels Library
 
3
 *
 
4
 *   Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
 
5
 *                      University of Applied Sciences, Western Switzerland
 
6
 *                      http://www.hes-so.ch
 
7
 *
 
8
 *   Contact:
 
9
 *      maxence.laurent <at> heig-vd <dot> ch
 
10
 *    or
 
11
 *      eric.taillard <at> heig-vd <dot> ch
 
12
 *
 
13
 * This file is part of libpal.
 
14
 *
 
15
 * libpal is free software: you can redistribute it and/or modify
 
16
 * it under the terms of the GNU General Public License as published by
 
17
 * the Free Software Foundation, either version 3 of the License, or
 
18
 * (at your option) any later version.
 
19
 *
 
20
 * libpal is distributed in the hope that it will be useful,
 
21
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
22
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
23
 * GNU General Public License for more details.
 
24
 *
 
25
 * You should have received a copy of the GNU General Public License
 
26
 * along with libpal.  If not, see <http://www.gnu.org/licenses/>.
 
27
 *
 
28
 */
 
29
 
 
30
#ifdef HAVE_CONFIG_H
 
31
#include <config.h>
 
32
#endif
 
33
 
 
34
#ifndef _HASHTABLE_HPP_
 
35
#define _HASHTABLE_HPP_
 
36
 
 
37
#include <cassert>
 
38
#include <cstdlib>
 
39
#include <cstring>
 
40
 
 
41
#include "linkedlist.hpp"
 
42
 
 
43
namespace pal
 
44
{
 
45
 
 
46
// Each hash entry stores a key, object pair
 
47
  template <typename Data>
 
48
  struct HashTableEntry
 
49
  {
 
50
    char * _key;
 
51
    Data _data;
 
52
  };
 
53
 
 
54
 
 
55
// This is a Hash table that maps string keys to objects of type Data
 
56
  template <typename Data>
 
57
  class HashTable
 
58
  {
 
59
    public:
 
60
      int tableSize;
 
61
 
 
62
      LinkedList<HashTableEntry<Data>*> **_hashtable;
 
63
 
 
64
      unsigned long hash( const char * key );
 
65
 
 
66
    public:
 
67
      HashTable( int tableSize );
 
68
      ~HashTable();
 
69
      bool insertItem( const char * key, Data data );
 
70
      Data* find( const char * key );
 
71
      bool removeElement( const char * key );
 
72
 
 
73
      void printStat();
 
74
  };
 
75
 
 
76
  template <typename Data> HashTable<Data>::~HashTable()
 
77
  {
 
78
    int i;
 
79
    LinkedList<HashTableEntry<Data>*> *list;
 
80
    HashTableEntry <Data> *entry;
 
81
 
 
82
    for ( i = 0; i < tableSize; i++ )
 
83
    {
 
84
      list = _hashtable[i];
 
85
      if ( list )
 
86
      {
 
87
        while ( list->size() > 0 )
 
88
        {
 
89
          entry = list->pop_front();
 
90
          delete[] entry->_key;
 
91
          delete entry;
 
92
        }
 
93
        delete list;
 
94
      }
 
95
    }
 
96
    delete[] _hashtable;
 
97
 
 
98
  }
 
99
  template <typename Data>
 
100
  unsigned long HashTable<Data>::hash( const char * key )
 
101
  {
 
102
    unsigned long hash = 5381;
 
103
    int c;
 
104
 
 
105
    while (( c = *key++ ) )
 
106
    {
 
107
      hash = (( hash << 5 ) + hash ) + c; // hash*33 + c
 
108
    }
 
109
 
 
110
    return hash % tableSize;
 
111
  }
 
112
 
 
113
 
 
114
  template <typename Data>
 
115
  HashTable<Data>::HashTable( int tableSize ) : tableSize( tableSize )
 
116
  {
 
117
    // TODO: Initialize the hash table
 
118
    _hashtable = new LinkedList<HashTableEntry<Data>*>*[tableSize];
 
119
 
 
120
 
 
121
    for ( int i = 0; i < tableSize; i++ )
 
122
    {
 
123
      _hashtable[i] = NULL;
 
124
    }
 
125
  }
 
126
 
 
127
  template <class Data>
 
128
  bool hashEntryCompare( HashTableEntry<Data> *a, HashTableEntry<Data> *b )
 
129
  {
 
130
    return strcmp( a->_key, b->_key ) == 0;
 
131
  }
 
132
 
 
133
  template <typename Data>
 
134
  bool HashTable<Data>::insertItem( const char * key, Data data )
 
135
  {
 
136
    unsigned long i = hash( key );
 
137
 
 
138
    LinkedList<HashTableEntry<Data>*> *e = _hashtable[i];
 
139
 
 
140
    HashTableEntry<Data> *entry = new HashTableEntry<Data>();
 
141
    entry->_key = new char[strlen( key ) +1];
 
142
    strcpy( entry->_key, key );
 
143
    entry->_data = data;
 
144
 
 
145
    if ( e )
 
146
    {
 
147
      Cell<HashTableEntry<Data>*> *elem = e->search( entry );
 
148
      if ( elem ) // change data
 
149
      {
 
150
        elem->item->_data = data;
 
151
        delete[] entry->_key;
 
152
        delete entry;
 
153
      }
 
154
      else
 
155
      {
 
156
        e->push_back( entry );
 
157
        return true;
 
158
      }
 
159
    }
 
160
    else
 
161
    {
 
162
      e = _hashtable[i] = new LinkedList<HashTableEntry<Data>*> ( hashEntryCompare );
 
163
      e->push_back( entry );
 
164
      return true;
 
165
    }
 
166
 
 
167
 
 
168
    return false;
 
169
  }
 
170
 
 
171
 
 
172
  template <typename Data>
 
173
  Data* HashTable<Data>::find( const char * key )
 
174
  {
 
175
    unsigned long i = hash( key );
 
176
 
 
177
    HashTableEntry<Data> * entry = new HashTableEntry<Data> ();
 
178
    entry->_key = new char[strlen( key ) +1];
 
179
    strcpy( entry->_key, key );
 
180
 
 
181
    LinkedList<HashTableEntry<Data>*> *e = _hashtable[i];
 
182
 
 
183
    Cell<HashTableEntry<Data>*> *cell;
 
184
 
 
185
    if ( !e )
 
186
    {
 
187
      delete[] entry->_key;
 
188
      delete entry;
 
189
      return NULL;
 
190
    }
 
191
    else
 
192
    {
 
193
      if (( cell = e->search( entry ) ) == NULL )
 
194
      {
 
195
        delete[] entry->_key;
 
196
        delete entry;
 
197
        return NULL;
 
198
      }
 
199
      else
 
200
      {
 
201
        delete[] entry->_key;
 
202
        delete entry;
 
203
        return & ( cell->item->_data );
 
204
      }
 
205
    }
 
206
  }
 
207
 
 
208
  template<typename Data>
 
209
  void HashTable<Data>::printStat()
 
210
  {
 
211
 
 
212
    double c = 0;
 
213
    int i;
 
214
    int n = 0;
 
215
 
 
216
    for ( i = 0; i < tableSize; i++ )
 
217
    {
 
218
      if ( _hashtable[i] )
 
219
      {
 
220
        n++;
 
221
        c += _hashtable[i]->size();
 
222
      }
 
223
    }
 
224
 
 
225
    std::cout << "# elem: " << c << std::endl;
 
226
    std::cout << "# linked list : " << n << " / " << tableSize << std::endl;
 
227
    std::cout << "nb elem / real list" << c / n << std::endl;
 
228
    std::cout << "nb elem / tableSize" << c / tableSize << std::endl;
 
229
  }
 
230
 
 
231
 
 
232
  template <typename Data>
 
233
  bool HashTable<Data>::removeElement( const char * key )
 
234
  {
 
235
    // TODO: Remove the element that has this key from the hash table.
 
236
    // Return true if the entry is found or false otherwise.
 
237
    /*int i = hash(key);
 
238
    HashTableEntry<Data> *eC = _buckets[i];
 
239
    HashTableEntry<Data> *eP = NULL;
 
240
 
 
241
    while(eC != NULL && strcmp(key, eC->_key) != 0)
 
242
    {
 
243
      eP = eC;
 
244
      eC = eC->_next;
 
245
    }
 
246
 
 
247
    //key is found
 
248
    if(eC != NULL)
 
249
    {
 
250
      if(eP != NULL)
 
251
        eP->_next = eC->_next;
 
252
      else
 
253
        _buckets[i] = eC->_next;
 
254
      return true;
 
255
    }
 
256
 
 
257
    //key is not found*/
 
258
    return false;
 
259
  }
 
260
 
 
261
 
 
262
/////////////////////////////////////
 
263
//
 
264
// Class used to iterate over the hash table
 
265
//
 
266
/////////////////////////////////////
 
267
  /*template <typename Data>
 
268
  class HashTableIterator {
 
269
    int _currentBucket; // Current bucket that is being iterated
 
270
    HashTableEntry<Data> *_currentEntry; // Current entry iterated
 
271
    HashTable<Data> * _hashTable;  // Pointer to the hash table being iterated
 
272
  public:
 
273
    HashTableIterator(HashTable<Data> * hashTable);
 
274
    bool next(const char * & key, Data & data);
 
275
  };
 
276
 
 
277
 
 
278
  template <typename Data>
 
279
  HashTableIterator<Data>::HashTableIterator(HashTable<Data> * hashTable)
 
280
  {
 
281
    // TODO: Initialize iterator. "hashTable" is the table to be iterated.
 
282
     _hashTable =  hashTable;
 
283
  }
 
284
 
 
285
  template <typename Data>
 
286
  bool HashTableIterator<Data>::next(const char * & key, Data & data)
 
287
  {
 
288
    // TODO: Returns the next element in the hash table.
 
289
    // The key and data values are stored in the references passed
 
290
    // as argument. It returns true if there are more entries or
 
291
    // false otherwise.
 
292
    return false;
 
293
  }
 
294
 
 
295
  */
 
296
 
 
297
} // end namespace
 
298
 
 
299
#endif
 
300