1 package org.davidmoten.hilbert;
2
3 import com.github.davidmoten.guavamini.Preconditions;
4
5 /**
6 * Converts between Hilbert index ({@code BigInteger}) and N-dimensional points.
7 *
8 * <p>
9 * Note: This algorithm is derived from work done by John Skilling and published
10 * in "Programming the Hilbert curve". (c) 2004 American Institute of Physics.
11 * With thanks also to Paul Chernoch who published a C# algorithm for Skilling's
12 * work on StackOverflow and
13 * <a href="https://github.com/paulchernoch/HilbertTransformation">GitHub</a>).
14 */
15 public final class SmallHilbertCurve {
16
17 private final int bits;
18 private final int dimensions;
19 private final int length;
20
21 private SmallHilbertCurve(int bits, int dimensions) {
22 this.bits = bits;
23 this.dimensions = dimensions;
24 this.length = bits * dimensions;
25 }
26
27 /**
28 * Converts a point to its Hilbert curve index.
29 *
30 * @param point
31 * an array of {@code long}. Each coordinate can be between 0 and
32 * 2<sup>bits</sup>-1.
33 * @return index {@code long} in the range 0 to 2<sup>bits *
34 * dimensions</sup> - 1
35 * @throws IllegalArgumentException
36 * if length of point array is not equal to the number of
37 * dimensions.
38 */
39 public long index(long... point) {
40 Preconditions.checkArgument(point.length == dimensions);
41 return toIndex(HilbertCurve.transposedIndex(bits, point));
42 }
43
44 /**
45 * Converts a {@code long} index (distance along the Hilbert Curve from 0)
46 * to a point of dimensions defined in the constructor of {@code this}.
47 *
48 * @param index
49 * index along the Hilbert Curve from 0. Maximum value 2
50 * <sup>bits * dimensions</sup>-1.
51 * @return array of longs being the point
52 * @throws IllegalArgumentException
53 * if index is negative
54 */
55 public long[] point(long index) {
56 return HilbertCurve.transposedIndexToPoint(bits, transposeLong(index));
57 }
58
59 private long toIndex(long... transposedIndex) {
60 long b = 0;
61 int bIndex = length - 1;
62 long mask = 1L << (bits - 1);
63 for (int i = 0; i < bits; i++) {
64 for (int j = 0; j < transposedIndex.length; j++) {
65 if ((transposedIndex[j] & mask) != 0) {
66 b |= 1 << bIndex;
67 }
68 bIndex--;
69 }
70 mask >>= 1;
71 }
72 // b is expected to be BigEndian
73 return b;
74 }
75
76 private long[] transposeLong(long index) {
77 long[] x = new long[dimensions];
78 for (int idx = 0; idx < 64; idx++) {
79 if ((index & (1L << idx)) != 0) {
80 int dim = (length - idx - 1) % dimensions;
81 int shift = (idx / dimensions) % bits;
82 x[dim] |= 1L << shift;
83 }
84 }
85 return x;
86 }
87
88 public static final class Builder {
89 private int bits;
90
91 Builder() {
92 // private instantiation
93 }
94
95 public Builder bits(int bits) {
96 this.bits = bits;
97 return this;
98 }
99
100 public SmallHilbertCurve dimensions(int dimensions) {
101 Preconditions.checkArgument(bits * dimensions <= 63, "bits * dimensions must be less than or equal to 63");
102 return new SmallHilbertCurve(bits, dimensions);
103 }
104
105 }
106 }