|
1
|
|
|
<?php |
|
2
|
|
|
|
|
3
|
|
|
namespace drupol\phpermutations; |
|
4
|
|
|
|
|
5
|
|
|
/** |
|
6
|
|
|
* Class Hilbert. |
|
7
|
|
|
* |
|
8
|
|
|
* @package drupol\phpermutations |
|
9
|
|
|
*/ |
|
10
|
|
|
class Hilbert { |
|
|
|
|
|
|
11
|
|
|
|
|
12
|
|
|
var $hilbert_map = array( |
|
|
|
|
|
|
13
|
|
|
'a' => array( |
|
14
|
|
|
"0, 0" => array(0, 'd'), |
|
15
|
|
|
"0, 1" => array(1, 'a'), |
|
16
|
|
|
"1, 0" => array(3, 'b'), |
|
17
|
|
|
"1, 1" => array(2, 'a'), |
|
18
|
|
|
), |
|
19
|
|
|
'b' => array( |
|
20
|
|
|
"0, 0" => array(2, 'b'), |
|
21
|
|
|
"0, 1" => array(1, 'b'), |
|
22
|
|
|
"1, 0" => array(3, 'a'), |
|
23
|
|
|
"1, 1" => array(0, 'c'), |
|
24
|
|
|
), |
|
25
|
|
|
'c' => array( |
|
26
|
|
|
"0, 0" => array(2, 'c'), |
|
27
|
|
|
"0, 1" => array(3, 'd'), |
|
28
|
|
|
"1, 0" => array(1, 'c'), |
|
29
|
|
|
"1, 1" => array(0, 'b'), |
|
30
|
|
|
), |
|
31
|
|
|
'd' => array( |
|
32
|
|
|
"0, 0" => array(0, 'a'), |
|
33
|
|
|
"0, 1" => array(3, 'c'), |
|
34
|
|
|
"1, 0" => array(1, 'd'), |
|
35
|
|
|
"1, 1" => array(2, 'd'), |
|
36
|
|
|
), |
|
37
|
|
|
); |
|
38
|
|
|
|
|
39
|
|
|
var $rev_map = Array( |
|
|
|
|
|
|
40
|
|
|
'a' => Array( |
|
|
|
|
|
|
41
|
|
|
Array(3, 'd'), |
|
|
|
|
|
|
42
|
|
|
Array(1, 'a'), |
|
|
|
|
|
|
43
|
|
|
Array(0, 'a'), |
|
|
|
|
|
|
44
|
|
|
Array(2, 'c'), |
|
|
|
|
|
|
45
|
|
|
), |
|
46
|
|
|
'b' => Array( |
|
|
|
|
|
|
47
|
|
|
Array(0, 'c'), |
|
|
|
|
|
|
48
|
|
|
Array(2, 'b'), |
|
|
|
|
|
|
49
|
|
|
Array(3, 'b'), |
|
|
|
|
|
|
50
|
|
|
Array(1, 'd'), |
|
|
|
|
|
|
51
|
|
|
), |
|
52
|
|
|
'c' => Array( |
|
|
|
|
|
|
53
|
|
|
Array(0, 'b'), |
|
|
|
|
|
|
54
|
|
|
Array(1, 'c'), |
|
|
|
|
|
|
55
|
|
|
Array(3, 'c'), |
|
|
|
|
|
|
56
|
|
|
Array(2, 'a'), |
|
|
|
|
|
|
57
|
|
|
), |
|
58
|
|
|
'd' => Array( |
|
|
|
|
|
|
59
|
|
|
Array(3, 'a'), |
|
|
|
|
|
|
60
|
|
|
Array(2, 'd'), |
|
|
|
|
|
|
61
|
|
|
Array(0, 'd'), |
|
|
|
|
|
|
62
|
|
|
Array(1, 'b'), |
|
|
|
|
|
|
63
|
|
|
), |
|
64
|
|
|
); |
|
65
|
|
|
|
|
66
|
|
|
/** |
|
67
|
|
|
* @var int |
|
68
|
|
|
*/ |
|
69
|
|
|
protected $recursion; |
|
70
|
|
|
|
|
71
|
|
|
/** |
|
72
|
|
|
* Hilbert constructor. |
|
73
|
|
|
* |
|
74
|
|
|
* @param null $recursion |
|
75
|
|
|
*/ |
|
76
|
|
|
public function __construct($recursion = NULL) { |
|
|
|
|
|
|
77
|
|
|
if (is_null($recursion)) { |
|
78
|
|
|
$recursion = 28; |
|
|
|
|
|
|
79
|
|
|
} |
|
80
|
|
|
$this->setRecursion($recursion); |
|
81
|
|
|
} |
|
82
|
|
|
|
|
83
|
|
|
/** |
|
84
|
|
|
* @param $recursion |
|
85
|
|
|
* |
|
86
|
|
|
* @return $this |
|
87
|
|
|
*/ |
|
88
|
|
|
public function setRecursion($recursion) { |
|
89
|
|
|
$this->recursion = $recursion; |
|
90
|
|
|
return $this; |
|
91
|
|
|
} |
|
92
|
|
|
|
|
93
|
|
|
/** |
|
94
|
|
|
* @return int |
|
95
|
|
|
*/ |
|
96
|
|
|
public function getRecursion() { |
|
97
|
|
|
return $this->recursion; |
|
98
|
|
|
} |
|
99
|
|
|
|
|
100
|
|
|
|
|
101
|
|
View Code Duplication |
function point_to_hilbert($x, $y, $order = 16, $map = "hilbert_map_1", $mode = "hilbert") { |
|
|
|
|
|
|
102
|
|
|
$current_square = 'a'; |
|
103
|
|
|
$position = 0; |
|
104
|
|
|
foreach (range($order - 1, 0, -1) as $i) { |
|
105
|
|
|
$position <<= 2; |
|
106
|
|
|
$quad_x = $x & (1 << $i) ? 1 : 0; |
|
107
|
|
|
$quad_y = $y & (1 << $i) ? 1 : 0; |
|
108
|
|
|
list($quad_position, $current_square) = $this->{$map}[$current_square]["$quad_x, $quad_y"]; |
|
109
|
|
|
$position |= $quad_position; |
|
110
|
|
|
} |
|
111
|
|
|
return $position; |
|
112
|
|
|
} |
|
113
|
|
|
|
|
114
|
|
View Code Duplication |
function hilbert_to_point($hilbert, $order) { |
|
|
|
|
|
|
115
|
|
|
$current_square = "a"; |
|
116
|
|
|
$amount = 1 << $order - 1; |
|
117
|
|
|
$x = $y = 0; |
|
|
|
|
|
|
118
|
|
|
for ($i = 2 * $order; $i > 0; $i -= 2) { |
|
119
|
|
|
list ($position, $current_square) = $this->rev_map[$current_square][$hilbert >> $i - 2]; |
|
120
|
|
|
switch ($position) { |
|
121
|
|
|
case 1: |
|
122
|
|
|
$x += $amount; |
|
123
|
|
|
break; |
|
124
|
|
|
case 2: |
|
125
|
|
|
$y += $amount; |
|
126
|
|
|
break; |
|
127
|
|
|
case 3: |
|
128
|
|
|
$y += $amount; |
|
129
|
|
|
$x += $amount; |
|
130
|
|
|
break; |
|
131
|
|
|
default: |
|
132
|
|
|
break; |
|
133
|
|
|
} |
|
134
|
|
|
$amount /= 2; |
|
135
|
|
|
$hilbert &= (1 << ($i - 2)) - 1; |
|
136
|
|
|
} |
|
137
|
|
|
return [$x, $y]; |
|
138
|
|
|
} |
|
139
|
|
|
|
|
140
|
|
|
|
|
141
|
|
View Code Duplication |
function xy2d($x, $y, $order = 16) { |
|
|
|
|
|
|
142
|
|
|
$current_square = 'a'; |
|
143
|
|
|
$position = 0; |
|
144
|
|
|
|
|
145
|
|
|
foreach (range($order - 1, 0, -1) as $i) { |
|
146
|
|
|
$position <<= 2; |
|
147
|
|
|
$quad_x = $x & (1 << $i) ? 1 : 0; |
|
148
|
|
|
$quad_y = $y & (1 << $i) ? 1 : 0; |
|
149
|
|
|
list($quad_position, $current_square) = $this->hilbert_map[$current_square]["$quad_x, $quad_y"]; |
|
150
|
|
|
$position |= $quad_position; |
|
151
|
|
|
} |
|
152
|
|
|
|
|
153
|
|
|
return $position; |
|
154
|
|
|
} |
|
155
|
|
|
|
|
156
|
|
View Code Duplication |
function d2xy($hilbert, $order = 16) { |
|
|
|
|
|
|
157
|
|
|
$current_square = "a"; |
|
158
|
|
|
$amount = 1 << $order - 1; |
|
159
|
|
|
$x = $y = 0; |
|
|
|
|
|
|
160
|
|
|
for ($i = 2 * $order; $i > 0; $i -= 2) { |
|
161
|
|
|
list ($position, $current_square) = $this->rev_map[$current_square][$hilbert >> $i - 2]; |
|
162
|
|
|
switch ($position) { |
|
163
|
|
|
case 1: |
|
164
|
|
|
$x += $amount; |
|
165
|
|
|
break; |
|
166
|
|
|
case 2: |
|
167
|
|
|
$y += $amount; |
|
168
|
|
|
break; |
|
169
|
|
|
case 3: |
|
170
|
|
|
$y += $amount; |
|
171
|
|
|
$x += $amount; |
|
172
|
|
|
break; |
|
173
|
|
|
default: |
|
174
|
|
|
break; |
|
175
|
|
|
} |
|
176
|
|
|
$amount /= 2; |
|
177
|
|
|
$hilbert &= (1 << ($i - 2)) - 1; |
|
178
|
|
|
} |
|
179
|
|
|
return [$x, $y]; |
|
180
|
|
|
} |
|
181
|
|
|
|
|
182
|
|
|
function test_pth() { |
|
|
|
|
|
|
183
|
|
|
foreach (range(7, 0, -1) as $x) { |
|
184
|
|
|
foreach (range(7, 0, -1) as $y) { |
|
185
|
|
|
$sort[] = $points["$x, $y"] = $this->point_to_hilbert($x, $y, 3); |
|
186
|
|
|
} |
|
187
|
|
|
} |
|
188
|
|
|
array_multisort($points, $sort); |
|
189
|
|
|
foreach ($points as $k => $v) { |
|
190
|
|
|
echo $k . "\n"; |
|
191
|
|
|
} |
|
192
|
|
|
} |
|
193
|
|
|
|
|
194
|
|
|
} |
|
195
|
|
|
|
drupol /
phpermutations
Loading history...
This check marks property names that have not been written in camelCase.
In camelCase names are written without any punctuation, the start of each new word being marked by a capital letter. Thus the name database connection string becomes
databaseConnectionString.