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
#	User	Rev	Content
1	greg	3.2	/* RCSid $Id$ */
2	greg	3.1	/* 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_ */