-
Notifications
You must be signed in to change notification settings - Fork 0
/
hash.h
127 lines (103 loc) · 4.58 KB
/
hash.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#ifndef _HASH_H_
#define _HASH_H_
// to handle different platforms with different variants of a developing standard
// NOTE: You may need to adjust these depending on your installation
#ifdef __APPLE__
#include <ext/hash_map>
#elif defined(_WIN32)
#include <unordered_map>
#elif defined(__linux__)
#include <unordered_map>
#elif defined(__FreeBSD__)
#include <ext/hash_map>
#else
#error "unknown system"
#endif
class Edge;
#include "triangle.h"
#include "vertex.h"
#define LARGE_PRIME_A 10007
#define LARGE_PRIME_B 11003
// ===================================================================================
// DIRECTED EDGES are stored in a hash table using a simple hash
// function based on the indices of the start and end vertices
// ===================================================================================
inline unsigned int ordered_two_int_hash(unsigned int a, unsigned int b) {
return LARGE_PRIME_A * a + LARGE_PRIME_B * b;
}
struct orderedvertexpairhash {
size_t operator()(std::pair<Vertex*,Vertex*> p) const {
return ordered_two_int_hash(p.first->getIndex(),p.second->getIndex());
}
};
struct orderedsamevertexpair {
bool operator()(std::pair<Vertex*,Vertex*> p1, std::pair<Vertex*,Vertex*>p2) const {
if (p1.first->getIndex() == p2.first->getIndex() && p1.second->getIndex() == p2.second->getIndex())
return true;
return false;
}
};
// ===================================================================================
// PARENT/CHILD VERTEX relationships (for subdivision) are stored in a
// hash table using a simple hash function based on the indices of the
// parent vertices, smaller index first
// ===================================================================================
inline unsigned int unordered_two_int_hash(unsigned int a, unsigned int b) {
assert (a != b);
if (b < a) {
return ordered_two_int_hash(b,a);
} else {
assert (a < b);
return ordered_two_int_hash(a,b);
}
}
struct unorderedvertexpairhash {
size_t operator()(std::pair<Vertex*,Vertex*> p) const {
return unordered_two_int_hash(p.first->getIndex(),p.second->getIndex());
}
};
struct unorderedsamevertexpair {
bool operator()(std::pair<Vertex*,Vertex*> p1, std::pair<Vertex*,Vertex*>p2) const {
if ((p1.first->getIndex() == p2.first->getIndex() && p1.second->getIndex() == p2.second->getIndex()) ||
(p1.first->getIndex() == p2.second->getIndex() && p1.second->getIndex() == p2.first->getIndex())) return true;
return false;
}
};
// ===================================================================================
// TRIANGLES are stored in a hash table using a simple hash function
// based on the id of the triangle (unique ids are assigned when the
// triangle is constructed)
// ===================================================================================
struct idhash {
size_t operator()(unsigned int id) const {
return LARGE_PRIME_A * id;
}
};
struct sameid {
bool operator()(unsigned int a, unsigned int b) const {
if (a == b)
return true;
return false;
}
};
// to handle different platforms with different variants of a developing standard
// NOTE: You may need to adjust these depending on your installation
#ifdef __APPLE__
typedef __gnu_cxx::hash_map<std::pair<Vertex*,Vertex*>,Vertex*,unorderedvertexpairhash,unorderedsamevertexpair> vphashtype;
typedef __gnu_cxx::hash_map<std::pair<Vertex*,Vertex*>,Edge*,orderedvertexpairhash,orderedsamevertexpair> edgeshashtype;
typedef __gnu_cxx::hash_map<unsigned int,Triangle*,idhash,sameid> triangleshashtype;
#elif defined(_WIN32)
typedef std::unordered_map<std::pair<Vertex*,Vertex*>,Vertex*,unorderedvertexpairhash,unorderedsamevertexpair> vphashtype;
typedef std::unordered_map<std::pair<Vertex*,Vertex*>,Edge*,orderedvertexpairhash,orderedsamevertexpair> edgeshashtype;
typedef std::unordered_map<unsigned int,Triangle*,idhash,sameid> triangleshashtype;
#elif defined(__linux__)
typedef std::unordered_map<std::pair<Vertex*,Vertex*>,Vertex*,unorderedvertexpairhash,unorderedsamevertexpair> vphashtype;
typedef std::unordered_map<std::pair<Vertex*,Vertex*>,Edge*,orderedvertexpairhash,orderedsamevertexpair> edgeshashtype;
typedef std::unordered_map<unsigned int,Triangle*,idhash,sameid> triangleshashtype;
#elif defined(__FreeBSD__)
typedef __gnu_cxx::hash_map<std::pair<Vertex*,Vertex*>,Vertex*,unorderedvertexpairhash,unorderedsamevertexpair> vphashtype;
typedef __gnu_cxx::hash_map<std::pair<Vertex*,Vertex*>,Edge*,orderedvertexpairhash,orderedsamevertexpair> edgeshashtype;
typedef __gnu_cxx::hash_map<unsigned int,Triangle*,idhash,sameid> triangleshashtype;
#else
#endif
#endif // _HASH_H_