src/common/hilbert.h

/* RCSid $Id$ */
/* 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_box_vtx 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_ */
Revision:	3.2
Committed:	Fri Feb 18 18:41:04 2011 UTC (13 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R4, rad5R2, rad4R2P2, rad5R0, rad5R1, rad4R2, rad4R1, rad4R2P1, rad5R3, HEAD
Changes since 3.1:	+1 -0 lines
Log Message:	Added missing RCS tags
#	Content
1	/* RCSid $Id$ */
2	/* C header file for Hilbert curve functions */
3	#if !defined(_hilbert_h_)
4	#define _hilbert_h_
5
6	#ifdef __cplusplus
7	extern "C" {
8	#endif
9
10	/* define the bitmask_t type as an integer of sufficient size */
11	typedef unsigned long long bitmask_t;
12	/* define the halfmask_t type as an integer of 1/2 the size of bitmask_t */
13	typedef unsigned long halfmask_t;
14
15	/*****************************************************************
16	* hilbert_i2c
17	*
18	* Convert an index into a Hilbert curve to a set of coordinates.
19	* Inputs:
20	* nDims: Number of coordinate axes.
21	* nBits: Number of bits per axis.
22	* index: The index, contains nDimsnBits bits (so nDimsnBits must be <= 8*sizeof(bitmask_t)).
23	* Outputs:
24	* coord: The list of nDims coordinates, each with nBits bits.
25	* Assumptions:
26	* nDimsnBits <= (sizeof index) (bits_per_byte)
27	*/
28
29	void hilbert_i2c(unsigned nDims, unsigned nBits, bitmask_t index, bitmask_t coord[]);
30
31	/*****************************************************************
32	* hilbert_c2i
33	*
34	* Convert coordinates of a point on a Hilbert curve to its index.
35	* Inputs:
36	* nDims: Number of coordinates.
37	* nBits: Number of bits/coordinate.
38	* coord: Array of n nBits-bit coordinates.
39	* Outputs:
40	* index: Output index value. nDims*nBits bits.
41	* Assumptions:
42	* nDimsnBits <= (sizeof bitmask_t) (bits_per_byte)
43	*/
44
45	bitmask_t hilbert_c2i(unsigned nDims, unsigned nBits, bitmask_t const coord[]);
46
47	/*****************************************************************
48	* hilbert_cmp, hilbert_ieee_cmp
49	*
50	* Determine which of two points lies further along the Hilbert curve
51	* Inputs:
52	* nDims: Number of coordinates.
53	* nBytes: Number of bytes of storage/coordinate (hilbert_cmp only)
54	* nBits: Number of bits/coordinate. (hilbert_cmp only)
55	* coord1: Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
56	* coord2: Array of nDims nBytes-byte coordinates (or doubles for ieee_cmp).
57	* Return value:
58	* -1, 0, or 1 according to whether
59	coord1<coord2, coord1==coord2, coord1>coord2
60	* Assumptions:
61	* nBits <= (sizeof bitmask_t) * (bits_per_byte)
62	*/
63
64	int hilbert_cmp(unsigned nDims, unsigned nBytes, unsigned nBits, void const* coord1, void const* coord2);
65	int hilbert_ieee_cmp(unsigned nDims, double const* coord1, double const* coord2);
66
67	/*****************************************************************
68	* hilbert_box_vtx
69	*
70	* Determine the first or last vertex of a box to lie on a Hilbert curve
71	* Inputs:
72	* nDims: Number of coordinates.
73	* nBytes: Number of bytes/coordinate.
74	* nBits: Number of bits/coordinate. (hilbert_box_vtx only)
75	* findMin: Is it the least vertex sought?
76	* coord1: Array of nDims nBytes-byte coordinates - one corner of box
77	* coord2: Array of nDims nBytes-byte coordinates - opposite corner
78	* Output:
79	* c1 and c2 modified to refer to selected corner
80	* value returned is log2 of size of largest power-of-two-aligned box that
81	* contains the selected corner and no other corners
82	* Assumptions:
83	* nBits <= (sizeof bitmask_t) * (bits_per_byte)
84	*/
85	unsigned
86	hilbert_box_vtx(unsigned nDims, unsigned nBytes, unsigned nBits,
87	int findMin, void* c1, void* c2);
88	unsigned
89	hilbert_ieee_box_vtx(unsigned nDims,
90	int findMin, double* c1, double* c2);
91
92	/*****************************************************************
93	* hilbert_box_pt
94	*
95	* Determine the first or last point of a box to lie on a Hilbert curve
96	* Inputs:
97	* nDims: Number of coordinates.
98	* nBytes: Number of bytes/coordinate.
99	* nBits: Number of bits/coordinate.
100	* findMin: Is it the least vertex sought?
101	* coord1: Array of nDims nBytes-byte coordinates - one corner of box
102	* coord2: Array of nDims nBytes-byte coordinates - opposite corner
103	* Output:
104	* c1 and c2 modified to refer to least point
105	* Assumptions:
106	* nBits <= (sizeof bitmask_t) * (bits_per_byte)
107	*/
108	unsigned
109	hilbert_box_pt(unsigned nDims, unsigned nBytes, unsigned nBits,
110	int findMin, void* coord1, void* coord2);
111	unsigned
112	hilbert_ieee_box_pt(unsigned nDims,
113	int findMin, double* c1, double* c2);
114
115	/*****************************************************************
116	* hilbert_nextinbox
117	*
118	* Determine the first point of a box after a given point to lie on a Hilbert curve
119	* Inputs:
120	* nDims: Number of coordinates.
121	* nBytes: Number of bytes/coordinate.
122	* nBits: Number of bits/coordinate.
123	* findPrev: Is the previous point sought?
124	* coord1: Array of nDims nBytes-byte coordinates - one corner of box
125	* coord2: Array of nDims nBytes-byte coordinates - opposite corner
126	* point: Array of nDims nBytes-byte coordinates - lower bound on point returned
127	*
128	* Output:
129	if returns 1:
130	* c1 and c2 modified to refer to least point after "point" in box
131	else returns 0:
132	arguments unchanged; "point" is beyond the last point of the box
133	* Assumptions:
134	* nBits <= (sizeof bitmask_t) * (bits_per_byte)
135	*/
136	int
137	hilbert_nextinbox(unsigned nDims, unsigned nBytes, unsigned nBits,
138	int findPrev, void* coord1, void* coord2,
139	void const* point);
140
141	/*****************************************************************
142	* hilbert_incr
143	*
144	* Advance from one point to its successor on a Hilbert curve
145	* Inputs:
146	* nDims: Number of coordinates.
147	* nBits: Number of bits/coordinate.
148	* coord: Array of nDims nBits-bit coordinates.
149	* Output:
150	* coord: Next point on Hilbert curve
151	* Assumptions:
152	* nBits <= (sizeof bitmask_t) * (bits_per_byte)
153	*/
154
155	void
156	hilbert_incr(unsigned nDims, unsigned nBits, bitmask_t coord[]);
157
158	#ifdef __cplusplus
159	}
160	#endif
161
162	#endif /* _hilbert_h_ */