Transpiled version (9760L) is out of date.
1 | asclass AbstractQuadTree<A> extends WidthAndHeightImpl is Matrix<A> {
|
2 | replace Node with O. |
3 | |
4 | sclass Composite > Node {
|
5 | Node a, b, c, d; |
6 | |
7 | void set(int idx, Node n) {
|
8 | if (idx == 0) a = n; |
9 | if (idx == 1) b = n; |
10 | if (idx == 2) c = n; |
11 | if (idx == 3) d = n; |
12 | } |
13 | |
14 | *(Node n) {
|
15 | a = b = c = d = n; |
16 | } |
17 | |
18 | bool simplifiable() {
|
19 | ret allEq(a, b, c, d); |
20 | } |
21 | |
22 | int compositeNodeCount() { ret 1+
|
23 | _compositeNodeCount(a) + |
24 | _compositeNodeCount(b) + |
25 | _compositeNodeCount(c) + |
26 | _compositeNodeCount(d); |
27 | } |
28 | } |
29 | |
30 | Node root = defaultValue(); |
31 | |
32 | *() {}
|
33 | *(int *width, int *height) {}
|
34 | |
35 | int half(int x) { ret roundUpToPowerOfTwo((x+1)/2); }
|
36 | int halfX(Rect r) { ret r.x+half(r.w); }
|
37 | int halfY(Rect r) { ret r.y+half(r.h); }
|
38 | |
39 | Rect rectA(Rect r) { ret rect(r.x, r.y, half(r.w), half(r.h)); }
|
40 | Rect rectB(Rect r) { ret rectFromPoints(r.x+half(r.w), r.y, r.x2(), halfY(r)); }
|
41 | Rect rectC(Rect r) { ret rectFromPoints(r.x, r.y+half(r.h), r.x+half(r.w), r.y2()); }
|
42 | Rect rectD(Rect r) { ret rectFromPoints(r.x+half(r.w), r.y+half(r.h), r.x2(), r.y2()); }
|
43 | |
44 | public A get(int x, int y) {
|
45 | Node node = root; |
46 | Rect r = rect(0, 0, width, height); |
47 | while (node cast Composite) {
|
48 | int hx = halfX(r), hy = halfY(r); |
49 | if (y < hy) |
50 | if (x < hx) {
|
51 | node = node.a; r = rectA(r); |
52 | } else {
|
53 | node = node.b; r = rectB(r); |
54 | } |
55 | else |
56 | if (x < hx) {
|
57 | node = node.c; r = rectC(r); |
58 | } else {
|
59 | node = node.d; r = rectD(r); |
60 | } |
61 | ifdef QuadTreeBitMatrix_debug |
62 | printVars(+x, +y, +hx, +hy); |
63 | endifdef |
64 | } |
65 | ret (A) node; |
66 | } |
67 | |
68 | public void set(int x, int y, A value) {
|
69 | set(pointRect(x, y), value); |
70 | } |
71 | |
72 | void set(Rect r, A value) {
|
73 | set(rootCursor(), r, value); |
74 | } |
75 | |
76 | scaffolded void set(Cursor cursor, Rect r, A value) {
|
77 | // no intersection? exit |
78 | if (!rectsIntersect(r, cursor.r)) ret; |
79 | |
80 | // fully contained? replace with primitive |
81 | if (rectContains(r, cursor.r)) |
82 | cursor.replace(value); |
83 | else {
|
84 | // partial intersection - turn into composite |
85 | cursor.turnIntoComposite(); |
86 | |
87 | for (Cursor c : cursor.subCursors()) |
88 | set(c, r, value); |
89 | } |
90 | |
91 | cursor.simplify(); |
92 | } |
93 | |
94 | class Cursor {
|
95 | settable Composite parent; |
96 | settable int indexInParent; |
97 | |
98 | settable Rect r; |
99 | settable Node node; |
100 | |
101 | L<Cursor> subCursors() {
|
102 | if (node cast Composite) |
103 | ret ll( |
104 | subCursor(0, node.a, rectA(r)), |
105 | subCursor(1, node.b, rectB(r)), |
106 | subCursor(2, node.c, rectC(r)), |
107 | subCursor(3, node.d, rectD(r))); |
108 | ret emptyList(); |
109 | } |
110 | |
111 | Cursor subCursor(int idx, Node n, Rect r) {
|
112 | ret new Cursor().r(r).node(n) |
113 | .parent((Composite) node).indexInParent(idx); |
114 | } |
115 | |
116 | scaffolded void turnIntoComposite {
|
117 | if (!node instanceof Composite) |
118 | replace(new Composite(node)); |
119 | } |
120 | |
121 | scaffolded void replace(Node n) {
|
122 | if (node == n) ret; |
123 | node = n; |
124 | if (parent == null) |
125 | root = n; |
126 | else |
127 | parent.set(indexInParent, n); |
128 | } |
129 | |
130 | // opposite of turnIntoComposite |
131 | scaffolded void simplify {
|
132 | if (node cast Composite && node.simplifiable()) |
133 | replace(node.a); |
134 | } |
135 | |
136 | /*toString {
|
137 | ret stdToString(this); |
138 | }*/ |
139 | } |
140 | |
141 | Cursor rootCursor() {
|
142 | ret new Cursor().r(bounds()).node(root); |
143 | } |
144 | |
145 | static int _compositeNodeCount(Node n) {
|
146 | if (n cast Composite) |
147 | ret n.compositeNodeCount(); |
148 | ret 0; |
149 | } |
150 | |
151 | int compositeNodeCount() { ret _compositeNodeCount(root); }
|
152 | |
153 | abstract A defaultValue(); |
154 | } |
Began life as a copy of #1033638
download show line numbers debug dex old transpilations
Travelled to 3 computer(s): bhatertpkbcr, ekrmjmnbrukm, mqqgnosmbjvj
No comments. add comment
| Snippet ID: | #1033689 |
| Snippet name: | AbstractQuadTree - generic quad tree |
| Eternal ID of this version: | #1033689/9 |
| Text MD5: | b714a8d635d764693439f36c1bdcd361 |
| Author: | stefan |
| Category: | javax / |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2022-08-21 07:38:11 |
| Source code size: | 3869 bytes / 154 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 112 / 213 |
| Version history: | 8 change(s) |
| Referenced in: | [show references] |