Open
Graph Drawing
Framework
v.2012.07
Overview
Class Hierarchy
Class Index
Class List
Members
Namespaces
Source Files
Hashing.h
Go to the documentation of this file.
1
/*
2
* $Revision: 2523 $
3
*
4
* last checkin:
5
* $Author: gutwenger $
6
* $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7
***************************************************************/
8
47
#ifdef _MSC_VER
48
#pragma once
49
#endif
50
51
#ifndef OGDF_HASHING_H
52
#define OGDF_HASHING_H
53
54
#include <
ogdf/basic/basic.h
>
55
#include <
math.h
>
56
#include <limits.h>
57
58
59
namespace
ogdf {
60
61
class
HashingBase;
62
69
class
HashElementBase
{
70
friend
class
HashingBase
;
71
72
HashElementBase
*
m_next
;
73
size_t
m_hashValue
;
74
75
public
:
77
HashElementBase
(
size_t
hashValue
) :
m_hashValue
(hashValue) { }
78
80
HashElementBase
*
next
()
const
{
return
m_next
; }
81
83
size_t
hashValue
()
const
{
return
m_hashValue
; }
84
85
OGDF_NEW_DELETE
86
};
87
88
95
class
HashingBase
{
96
protected
:
97
int
m_tableSize
;
98
int
m_hashMask
;
99
int
m_minTableSize
;
100
int
m_tableSizeLow
;
101
int
m_tableSizeHigh
;
102
int
m_count
;
103
HashElementBase
**
m_table
;
104
105
public
:
107
HashingBase
(
int
minTableSize);
108
110
HashingBase
(
const
HashingBase
&H);
111
112
// destruction
113
virtual
~HashingBase
();
114
116
void
resize
(
int
newTableSize);
117
119
void
insert
(
HashElementBase
*pElement);
120
122
void
del
(
HashElementBase
*pElement);
123
125
void
clear
();
126
128
HashingBase
&
operator=
(
const
HashingBase
&H);
129
131
int
size
()
const
{
return
m_count
; }
132
134
int
empty
()
const
{
return
(
m_count
==0); }
135
141
HashElementBase
*
firstListElement
(
size_t
hashValue)
const
{
142
return
*(
m_table
+ (hashValue &
m_hashMask
));
143
}
144
153
HashElementBase
*
firstElement
(
HashElementBase
***pList)
const
;
154
164
HashElementBase
*
nextElement
(
HashElementBase
***pList,
165
HashElementBase
*pElement)
const
;
166
167
protected
:
169
void
destroyAll
();
170
177
virtual
void
destroy
(
HashElementBase
*pElement) = 0;
178
180
virtual
HashElementBase
*
copy
(
HashElementBase
*pElement)
const
= 0;
181
182
private
:
184
void
init
(
int
tableSize);
185
187
void
copyAll
(
const
HashingBase
&H);
188
};
189
190
191
template
<
class
K,
class
I,
class
H>
class
Hashing;
192
template
<
class
K,
class
I,
class
H>
class
HashArray;
193
194
202
template
<
class
K,
class
I>
203
class
HashElement
:
public
HashElementBase
204
{
205
K
m_key
;
206
I
m_info
;
207
208
public
:
210
HashElement
(
size_t
hashValue
,
const
K &
key
,
const
I &
info
) :
211
HashElementBase
(hashValue),
m_key
(key),
m_info
(info) { }
212
214
HashElement<K,I>
*
next
()
const
{
215
return
(
HashElement<K,I>
*)
HashElementBase::next
();
216
}
217
219
const
K &
key
()
const
{
return
m_key
; }
220
222
const
I &
info
()
const
{
return
m_info
; }
223
225
I &
info
() {
return
m_info
; }
226
227
OGDF_NEW_DELETE
228
};
229
230
231
template
<
class
K,
class
I,
class
H>
class
HashConstIterator;
232
233
//--------------------------------------------------------------------
234
// Hash function classes have to define
235
// int hash(const E &key)
236
//
237
// "const E &" can be replaced by "E"
238
//--------------------------------------------------------------------
239
248
template
<
class
K>
class
DefHashFunc
{
250
public
:
size_t
hash
(
const
K &key)
const
{
return
size_t(key); }
251
};
252
254
template
<>
class
DefHashFunc
<void *> {
255
public
:
size_t
hash
(
const
void
* &key)
const
{
return
size_t(key && 0xffffffff); }
256
};
257
259
template
<>
class
DefHashFunc
<double> {
260
public
:
size_t
hash
(
const
double
&key)
const
{
261
int
dummy;
262
return
size_t(
SIZE_MAX
*frexp(key,&dummy));
263
}
264
};
265
266
280
template
<
class
K,
class
I,
class
H = DefHashFunc<K> >
281
class
Hashing
:
private
HashingBase
282
{
283
friend
class
HashConstIterator
<K,I,H>;
284
H
m_hashFunc
;
285
286
public
:
288
typedef
HashConstIterator<K,I,H>
const_iterator
;
289
291
explicit
Hashing
(
int
minTableSize = 256,
const
H &hashFunc = H())
292
:
HashingBase
(minTableSize),
m_hashFunc
(hashFunc) { }
293
295
Hashing
(
const
Hashing<K,I>
&h) :
HashingBase
(h) { }
296
297
// destruction
298
~Hashing
() {
HashingBase::destroyAll
(); }
299
301
int
size
()
const
{
return
HashingBase::size
(); }
302
304
bool
empty
()
const
{
return
(
HashingBase::size
() == 0); }
305
307
bool
member
(
const
K &key)
const
{
return
(
lookup
(key) != 0); }
308
310
HashConstIterator<K,I,H>
begin
()
const
;
311
313
HashElement<K,I>
*
lookup
(
const
K &key)
const
{
314
HashElement<K,I>
*pElement =
315
(
HashElement<K,I>
*)
firstListElement
(
m_hashFunc
.hash(key));
316
for
(; pElement; pElement = pElement->
next
())
317
if
(pElement->
key
() == key)
return
pElement;
318
319
return
0;
320
}
321
323
Hashing<K,I>
&
operator=
(
const
Hashing<K,I>
&hashing) {
324
HashingBase::operator =
(hashing);
325
m_hashFunc
= hashing.
m_hashFunc
;
326
return
*
this
;
327
}
328
336
HashElement<K,I>
*
insert
(
const
K &key,
const
I &info) {
337
HashElement<K,I>
*pElement =
lookup
(key);
338
339
if
(pElement)
340
pElement->
info
() = info;
341
else
342
HashingBase::insert
(pElement =
343
OGDF_NEW
HashElement<K,I>
(
m_hashFunc
.hash(key),key,info));
344
345
return
pElement;
346
}
347
355
HashElement<K,I>
*
insertByNeed
(
const
K &key,
const
I &info) {
356
HashElement<K,I>
*pElement =
lookup
(key);
357
358
if
(!pElement)
359
HashingBase::insert
(pElement =
OGDF_NEW
HashElement<K,I>
(
m_hashFunc
.hash(key),key,info));
360
361
return
pElement;
362
}
363
370
HashElement<K,I>
*
fastInsert
(
const
K &key,
const
I &info) {
371
HashElement<K,I>
*pElement =
OGDF_NEW
HashElement<K,I>
(
m_hashFunc
.hash(key),key,info);
372
HashingBase::insert
(pElement);
373
return
pElement;
374
}
375
377
void
del
(
const
K &key) {
378
HashElement<K,I>
*pElement =
lookup
(key);
379
if
(pElement) {
380
HashingBase::del
(pElement);
381
delete
pElement;
382
}
383
}
384
386
void
clear
() {
HashingBase::clear
(); }
387
388
protected
:
397
HashElement<K,I>
*
firstElement
(
HashElement<K,I>
***pList)
const
{
398
return
(
HashElement<K,I>
*)(
HashingBase::firstElement
((
HashElementBase
***)pList));
399
}
400
410
HashElement<K,I>
*
nextElement
(
HashElement<K,I>
***pList,
411
HashElement<K,I>
*pElement)
const
412
{
413
return
(
HashElement<K,I>
*)(
HashingBase::nextElement
(
414
(
HashElementBase
***)pList,pElement));
415
}
416
417
private
:
419
virtual
void
destroy
(
HashElementBase
*pElement) {
420
delete
(
HashElement<K,I>
*)(pElement);
421
}
422
424
virtual
HashElementBase
*
copy
(
HashElementBase
*pElement)
const
{
425
HashElement<K,I>
*pX = (
HashElement<K,I>
*)(pElement);
426
return
OGDF_NEW
HashElement<K,I>
(pX->
hashValue
(),pX->
key
(),pX->
info
());
427
}
428
};
429
430
454
template
<
class
K,
class
I,
class
H = DefHashFunc<K> >
455
class
HashConstIterator
{
456
HashElement<K,I>
*
m_pElement
;
457
HashElement<K,I>
**
m_pList
;
458
const
Hashing<K,I,H>
*
m_pHashing
;
459
460
public
:
462
HashConstIterator
() :
m_pElement
(0),
m_pList
(0),
m_pHashing
(0) { }
463
465
HashConstIterator
(
HashElement<K,I>
*pElement,
HashElement<K,I>
**pList,
466
const
Hashing<K,I,H>
*pHashing) :
m_pElement
(pElement),
m_pList
(pList),
467
m_pHashing
(pHashing) { }
468
470
HashConstIterator
(
const
HashConstIterator<K,I,H>
&it) :
m_pElement
(it.
m_pElement
),
471
m_pList
(it.
m_pList
),
m_pHashing
(it.
m_pHashing
) { }
472
474
HashConstIterator
&
operator=
(
const
HashConstIterator<K,I,H>
&it) {
475
m_pElement
= it.
m_pElement
;
476
m_pList
= it.
m_pList
;
477
m_pHashing
= it.
m_pHashing
;
478
return
*
this
;
479
}
480
482
bool
valid
()
const
{
return
(
m_pElement
!= 0); }
483
485
const
K &
key
()
const
{
return
m_pElement
->key(); }
486
488
const
I &
info
()
const
{
return
m_pElement
->info(); }
489
491
friend
bool
operator==
(
const
HashConstIterator<K,I,H>
&it1,
492
const
HashConstIterator<K,I,H>
&it2) {
return
(it1.
m_pElement
== it2.
m_pElement
); }
493
495
friend
bool
operator!=
(
const
HashConstIterator<K,I,H>
&it1,
496
const
HashConstIterator<K,I,H>
&it2) {
return
(it1.
m_pElement
!= it2.
m_pElement
); }
497
499
HashConstIterator<K,I,H>
&
operator++
() {
500
m_pElement
=
m_pHashing
->nextElement(&
m_pList
,
m_pElement
);
501
return
*
this
;
502
}
503
};
504
505
506
template
<
class
K,
class
I,
class
H>
507
inline
HashConstIterator<K,I,H>
Hashing<K,I,H>::begin
()
const
508
{
509
HashElement<K,I>
*pElement, **pList;
510
pElement = firstElement(&pList);
511
return
HashConstIterator<K,I,H>
(pElement,pList,
this
);
512
}
513
514
515
}
// end namespace ogdf
516
517
#endif
ogdf
basic
Hashing.h
© 1999-2012 by
TU Dortmund
,
University of Jena
,
University of Cologne
,
University of Sydney
,
oreas GmbH