libStatGen Software 1
Loading...
Searching...
No Matches
IntHash.h
1/*
2 * Copyright (C) 2000-2007 Goncalo Abecasis
3 *
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18//////////////////////////////////////////////////////////////////////
19// libsrc/IntHash.h
20// (c) 2000-2007 Goncalo Abecasis
21//
22// This file is distributed as part of the MaCH source code package
23// and may not be redistributed in any form, without prior written
24// permission from the author. Permission is granted for you to
25// modify this file for your own personal use, but modified versions
26// must retain this copyright notice and must not be distributed.
27//
28// Permission is granted for you to use this file to compile MaCH.
29//
30// All computer programs have bugs. Use this file at your own risk.
31//
32// Monday October 29, 2007
33//
34
35#ifndef __INTHASH_H__
36#define __INTHASH_H__
37
38#include <stdlib.h>
39
41{
42protected:
43 bool * objects;
44 unsigned int * keys;
45 unsigned int count, size;
46 unsigned int mask;
47
48public:
49 IntHash(int startsize = 32);
50 virtual ~IntHash();
51
52 void Grow()
53 {
54 SetSize(size * 2);
55 }
56 void Shrink()
57 {
58 SetSize(size / 2);
59 }
60
61 void SetSize(int newsize);
62
63 void Clear();
64
65 int Capacity() const
66 {
67 return size;
68 }
69 int Entries() const
70 {
71 return count;
72 }
73
74 bool Object(int i) const
75 {
76 return objects[i];
77 }
78
79 void SetObject(int i, bool object)
80 {
81 objects[i] = object;
82 }
83
84 int Add(int key, bool object = true);
85 int Find(int key);
86 int Rehash(int key, int h);
87
88 IntHash & operator = (const IntHash & rhs);
89
90 bool operator [](int i) const
91 {
92 return objects[i];
93 }
94
95 void Delete(unsigned int index);
96
97 bool SlotInUse(int index)
98 {
99 return objects[index] != false;
100 }
101
102private:
103 unsigned int Iterate(unsigned int key) const
104 {
105 unsigned int h = key & mask;
106
107 while (objects[h] != false && keys[h] != key)
108 h = (h + 1) & mask;
109
110 return h;
111 }
112
113 unsigned int ReIterate(unsigned int key, unsigned int h) const
114 {
115 h = (h + 1) & mask;
116
117 while (objects[h] != false && keys[h] != key)
118 h = (h + 1) & mask;
119
120 return h;
121 }
122};
123
124#endif
125