-
Notifications
You must be signed in to change notification settings - Fork 11
/
Copy pathhilbert.h
161 lines (146 loc) · 5.63 KB
/
hilbert.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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
/* C header file for Hilbert curve functions */
#if !defined(_hilbert_h_)
#define _hilbert_h_
#ifdef __cplusplus
extern "C" {
#endif
/* define the bitmask_t type as an integer of sufficient size */
typedef unsigned long long bitmask_t;
/* define the halfmask_t type as an integer of 1/2 the size of bitmask_t */
typedef unsigned long halfmask_t;
/*****************************************************************
* hilbert_i2c
*
* Convert an index into a Hilbert curve to a set of coordinates.
* Inputs:
* nDims: Number of coordinate axes.
* nBits: Number of bits per axis.
* index: The index, contains nDims*nBits bits (so nDims*nBits must be <= 8*sizeof(bitmask_t)).
* Outputs:
* coord: The list of nDims coordinates, each with nBits bits.
* Assumptions:
* nDims*nBits <= (sizeof index) * (bits_per_byte)
*/
void hilbert_i2c(unsigned nDims, unsigned nBits, bitmask_t index, bitmask_t coord[]);
/*****************************************************************
* hilbert_c2i
*
* Convert coordinates of a point on a Hilbert curve to its index.
* Inputs:
* nDims: Number of coordinates.
* nBits: Number of bits/coordinate.
* coord: Array of n nBits-bit coordinates.
* Outputs:
* index: Output index value. nDims*nBits bits.
* Assumptions:
* nDims*nBits <= (sizeof bitmask_t) * (bits_per_byte)
*/
bitmask_t hilbert_c2i(unsigned nDims, unsigned nBits, bitmask_t const coord[]);
/*****************************************************************
* hilbert_cmp, hilbert_ieee_cmp
*
* Determine which of two points lies further along the Hilbert curve
* Inputs:
* nDims: Number of coordinates.
* nBytes: Number of bytes of storage/coordinate (hilbert_cmp only)
* nBits: Number of bits/coordinate. (hilbert_cmp only)
* coord1: Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
* coord2: Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
* Return value:
* -1, 0, or 1 according to whether
coord1<coord2, coord1==coord2, coord1>coord2
* Assumptions:
* nBits <= (sizeof bitmask_t) * (bits_per_byte)
*/
int hilbert_cmp(unsigned nDims, unsigned nBytes, unsigned nBits, void const* coord1, void const* coord2);
int hilbert_ieee_cmp(unsigned nDims, double const* coord1, double const* coord2);
/*****************************************************************
* hilbert_box_vtx
*
* Determine the first or last vertex of a box to lie on a Hilbert curve
* Inputs:
* nDims: Number of coordinates.
* nBytes: Number of bytes/coordinate.
* nBits: Number of bits/coordinate. (hilbert_cmp only)
* findMin: Is it the least vertex sought?
* coord1: Array of nDims nBytes-byte coordinates - one corner of box
* coord2: Array of nDims nBytes-byte coordinates - opposite corner
* Output:
* c1 and c2 modified to refer to selected corner
* value returned is log2 of size of largest power-of-two-aligned box that
* contains the selected corner and no other corners
* Assumptions:
* nBits <= (sizeof bitmask_t) * (bits_per_byte)
*/
unsigned
hilbert_box_vtx(unsigned nDims, unsigned nBytes, unsigned nBits,
int findMin, void* c1, void* c2);
unsigned
hilbert_ieee_box_vtx(unsigned nDims,
int findMin, double* c1, double* c2);
/*****************************************************************
* hilbert_box_pt
*
* Determine the first or last point of a box to lie on a Hilbert curve
* Inputs:
* nDims: Number of coordinates.
* nBytes: Number of bytes/coordinate.
* nBits: Number of bits/coordinate.
* findMin: Is it the least vertex sought?
* coord1: Array of nDims nBytes-byte coordinates - one corner of box
* coord2: Array of nDims nBytes-byte coordinates - opposite corner
* Output:
* c1 and c2 modified to refer to least point
* Assumptions:
* nBits <= (sizeof bitmask_t) * (bits_per_byte)
*/
unsigned
hilbert_box_pt(unsigned nDims, unsigned nBytes, unsigned nBits,
int findMin, void* coord1, void* coord2);
unsigned
hilbert_ieee_box_pt(unsigned nDims,
int findMin, double* c1, double* c2);
/*****************************************************************
* hilbert_nextinbox
*
* Determine the first point of a box after a given point to lie on a Hilbert curve
* Inputs:
* nDims: Number of coordinates.
* nBytes: Number of bytes/coordinate.
* nBits: Number of bits/coordinate.
* findPrev: Is the previous point sought?
* coord1: Array of nDims nBytes-byte coordinates - one corner of box
* coord2: Array of nDims nBytes-byte coordinates - opposite corner
* point: Array of nDims nBytes-byte coordinates - lower bound on point returned
*
* Output:
if returns 1:
* c1 and c2 modified to refer to least point after "point" in box
else returns 0:
arguments unchanged; "point" is beyond the last point of the box
* Assumptions:
* nBits <= (sizeof bitmask_t) * (bits_per_byte)
*/
int
hilbert_nextinbox(unsigned nDims, unsigned nBytes, unsigned nBits,
int findPrev, void* coord1, void* coord2,
void const* point);
/*****************************************************************
* hilbert_incr
*
* Advance from one point to its successor on a Hilbert curve
* Inputs:
* nDims: Number of coordinates.
* nBits: Number of bits/coordinate.
* coord: Array of nDims nBits-bit coordinates.
* Output:
* coord: Next point on Hilbert curve
* Assumptions:
* nBits <= (sizeof bitmask_t) * (bits_per_byte)
*/
void
hilbert_incr(unsigned nDims, unsigned nBits, bitmask_t coord[]);
#ifdef __cplusplus
}
#endif
#endif /* _hilbert_h_ */