Download Jar. Libraryless. Click here for Pure Java version (2533L/17K).
!7 sclass ArrayTreeSet<A> { A[] array; *() {} *(L<A> l) { array = (A[]) new O[roundUpToPowerOfTwo(l(l))]; l = sorted(l); fill(l, 0, l(array), 0); } void fill(L<A> l, int lIdx1, int lIdx2, int aIdx) { if (lIdx2 <= lIdx1) ret; int middle = (lIdx1+lIdx2)/2; array[aIdx] = get(l, middle); fill(l, lIdx1, middle, aIdx*2+1); fill(l, middle+1, lIdx2, aIdx*2+2); } bool contains(A a) { int i = 0; while (i < l(array)) { int x = array[i] == null ? -1 : cmp(a, array[i]); if (x == 0) true; i = i*2+(x > 0 ? 2 : 1); } false; } } p { new L<Int> l; for (int n = 0; n <= 64; n++) { if (n != 0) l.add(n*10); print("n=" + n); assertEquals(n, l(l)); ArrayTreeSet tree = new ArrayTreeSet(shuffledList(l)); printStruct(tree); for (int i : l) { assertTrue(str(i), tree.contains(i)); assertFalse(tree.contains(i-1)); assertFalse(tree.contains(i+1)); } } print("OK"); }
download show line numbers debug dex old transpilations
Travelled to 13 computer(s): aoiabmzegqzx, bhatertpkbcr, cbybwowwnfue, cfunsshuasjs, gwrvuhgaqvyk, ishqpsrjomds, lpdgvwnxivlt, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tslmcundralx, tvejysmllsmz, vouqrxazstgt
No comments. add comment
Snippet ID: | #1011274 |
Snippet name: | Array-Based Binary Tree [OK!] |
Eternal ID of this version: | #1011274/23 |
Text MD5: | fc7e2c79acd8e4e8ee0dcf1141f8fbba |
Transpilation MD5: | a1b31f67608168d505057540f4735450 |
Author: | stefan |
Category: | javax |
Type: | JavaX source code (desktop) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2017-10-21 23:06:51 |
Source code size: | 1035 bytes / 46 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 534 / 1240 |
Version history: | 22 change(s) |
Referenced in: | #1011276 - Array-Based Tree Map [OK!] |