Re: the ring proposal - I understand it's not quite the same, but there is also
already `std/deques`.
I didn't do any ensureMove/lent/sink/etc., and I just picked `Colony[T]` since
that seems to be used in at least one other ecosystem and doesn't sound
"suggestive" of, well, anything - so people will have to look at what it is. At
first I was going to say `Zones[T]` or `Hunks[T]` \- just anything like
"region" or "area" that sounds plural.
Also, I literally just coded this up quickly so there may be bugs, but this
fleshes out my ideas more concretely which is always good. { It didn't sound
like Araq needed them fleshed out - this isn't rocket science, though some
semi-working code is better than just a request. }
import std/[assertions, algorithm]
type # lib/pure/collections/colony.nim
Colony*[T] = object
cCaps, cLens: seq[int] # cX = cumsum(X)
hunks: seq[ptr UncheckedArray[T]] # storage hunks
proc nHunk*[T](c: Colony[T]): int = c.hunks.len
proc destroy*[T](c: Colony[T]) =
for h in c.hunks: dealloc h
iterator items*[T](c: Colony[T]): T =
for i in 0 ..< c.nHunk:
let n = c.lens(i)
for j in 0 ..< n: yield c.hunks[i][j]
iterator pairs*[T](c: Colony[T]): (int, T) =
var ct = 0
for i in 0 ..< c.nHunk:
let n = c.lens(i)
for j in 0 ..< n: yield (ct, c.hunks[i][j]); inc ct
# mitems, mpairs, etc.
proc `$`[T](c: Colony[T]): string =
result = "cCaps: " & $c.cCaps & " cLens: " & $c.cLens &
" members: ["
for i, e in c: result.add (if i>0: " " else: "") & $e
result.add "]"
const defaultHunk0 = 3
template getHunk(T: typedesc, cap: int): untyped =
cast[ptr UncheckedArray[T]](alloc0(cap * T.sizeof))
proc initColony*[T](cap=defaultHunk0): Colony[T] =
assert cap > 1 # `1` so *3 div 2 always increases
result.cLens.add 0
result.cCaps.add cap
result.hunks.add getHunk(T, cap)
proc lastCap[T](c: Colony[T]): int =
if c.nHunk < 2: c.cCaps[^1] else: c.cCaps[^1] - c.cCaps[^2]
proc lens[T](c: Colony[T], i: int): int =
if i == 0: c.cLens[0] else: c.cLens[i] - c.cLens[i-1]
proc len*[T](c: Colony[T]): int = c.cLens[^1]
proc cLenBefore[T](c: Colony[T], i = -1): int =
if i == -1:
if c.nHunk > 1: c.cLens[^2] else: 0
elif i == 0:
return 0
else:
if c.nHunk > 1: c.cLens[i - 1] else: 0
proc ensure[T](c: var Colony[T], n: int) =
if c.nHunk == 0:
c.cLens.add 0
c.cCaps.add defaultHunk0
c.hunks.add getHunk(T, defaultHunk0)
elif n > c.cCaps[^1]: # Make first branch impossible?
if c.cCaps[0] == 0: c.cCaps.add defaultHunk0
else: # User growth policy for below?
c.cCaps.add c.cCaps[^1] + 3*c.lastCap div 2
c.cLens.add c.cLens[^1]
c.hunks.add getHunk(T, c.lastCap)
proc add*[T](c: var Colony[T]; e: T) =
let n = c.cLens[^1]
c.ensure n + 1
let j = n - c.cLenBefore
c.hunks[^1][j] = e
inc c.cLens[^1]
template get(c, index, i, j, body) =
var i = c.cLens.lowerBound index
let j = index - c.cLenBefore(i)
if j < c.lens(i): body
else: raise newException(IndexDefect, "out of bounds")
proc `[]`*[T](c: Colony[T]; index: int): T =
get(c, index, i, j): return c.hunks[i][j]
proc `[]`*[T](c: var Colony[T]; index: int): var T =
get(c, index, i, j): return c.hunks[i][j]
proc `[]=`*[T](c: var Colony[T]; index: int; e: T) =
get(c, index, i, j): c.hunks[i][j] = e
when isMainModule:
var c = initColony[int]() # var c: Colony[int]
for i in 0 ..< 13: c.add i
echo c; c[1] = -9; c[5] = -9; c[9] = -9; echo c
destroy c
Run
I really don't think it's more complex. I think it's simpler. E.g., only one
type. Very easy to describe (`[i][j]` indexing). Etc. I mean, someone _will_
come along saying "Use some more scalable structure for the cumulative
caps/lens" (I've implemented plenty of such structures myself), but I doubt
there is one that isn't at least O(lg N) on a packed dense/cacheable memory
area for something like the `lowerBound`. Anyway, this seems a better starting
point and I hereby donate it if there's interest. { Also, @Vindaar helped fix
one last minute bug w/2 lines of code. }
