Created
June 10, 2023 19:09
-
-
Save hackwaly/a0f58585288980a22f58560afccff605 to your computer and use it in GitHub Desktop.
Efficent mutable list in reasonml
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
let dummy_arr = [||]; | |
module type ELT = { | |
type t; | |
let uninitialized: t; | |
}; | |
module Make = (Elt: ELT) => { | |
type t('a) = { | |
mutable arrs: array(array('a)), | |
mutable arrs_cur: int, | |
mutable arr: array('a), | |
mutable arr_cur: int, | |
}; | |
let make = () => {arrs: dummy_arr, arrs_cur: 0, arr: dummy_arr, arr_cur: 0}; | |
let push = (l, e) => { | |
let arr_len = Array.length(l.arr); | |
if (l.arr_cur >= arr_len) { | |
let arrs_len = Array.length(l.arrs); | |
if (arr_len > 0) { | |
if (arrs_len == 0) { | |
l.arrs = Array.make(4, dummy_arr); | |
} else if (l.arrs_cur >= arrs_len) { | |
let arrs = Array.make(arrs_len * 2, dummy_arr); | |
Array.blit(l.arrs, 0, arrs, 0, arrs_len); | |
l.arrs = arrs; | |
}; | |
l.arrs[l.arrs_cur] = l.arr; | |
l.arrs_cur = l.arrs_cur + 1; | |
}; | |
let shift = | |
if (arrs_len <= 7) { | |
arrs_len; | |
} else if (arrs_len <= 10) { | |
7; | |
} else { | |
arrs_len - 3; | |
}; | |
let cap = Int.min(4 lsl shift, Sys.max_array_length); | |
let arr = Array.make(cap, Elt.uninitialized); | |
l.arr = arr; | |
l.arr_cur = 0; | |
}; | |
l.arr[l.arr_cur] = e; | |
l.arr_cur = l.arr_cur + 1; | |
}; | |
let iter = (l, f) => { | |
for (i in 0 to l.arrs_cur - 1) { | |
let arr = l.arrs[i]; | |
Array.iter(f, arr); | |
}; | |
for (i in 0 to l.arr_cur - 1) { | |
f(l.arr[i]); | |
}; | |
}; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment