There is are functional data structure call
[FingerTree](https://www.staff.city.ac.uk/~ross/papers/FingerTree.html) which
is normally used for immutable seq. But it can be modified to be mutable and
'no-reallocation' to suite your need.
The core idea of finger tree is that at each level, keep `StableChunk` (the
following implementation call Ring) of two ends. And then if a chunk is full,
put that chunk to **next level of chunk**. This means top level keeps 2 chunks,
level 1 keeps 2 chunks of chunks, level 2 keeps 2 chunks of chunks of chunks
and so on. So there is at most O(log(n)) level. Finger tree is said to be
analogical to number system. Top level correspond to least significant digits
and next level is next digit, and so on. With this analogy, it is intuitive to
see that append/prepend is worst case O(log(n)) and amortized O(1). Accessing
element at two ends is O(1) and in the middle O(log(n)).
The following implement the idea, not thoroughly tested.
type
StableSeqDefect* = object of Defect
template throw(msg) =
raise newException(StableSeqDefect, msg)
#
------------------------------------------------------------------------------
# Fix size chunk. Cap is arbitrary, the larger, the flater the tree.
const CAP = 4
type
RingObj[T] = object
i, len: int
data: array[CAP, T]
Ring[T] = ptr RingObj[T]
Node = ref object
left, right: Ring[pointer]
next: Node
StableSeq*[T] = object
left, right: Ring[T]
next: Node
# ----------------------------------- Ring
-------------------------------------
proc allocRing[T](): Ring[T] =
result = cast[Ring[T]](alloc0(sizeof(RingObj[T])))
proc deallocRing(r: Ring) =
dealloc(r)
proc isFull(r: Ring): bool = r.len == CAP
proc isEmpty(r: Ring): bool = r.len == 0
proc isNotEmpty(r: Ring): bool = not r.isEmpty
proc `[]`[T](r: Ring[T], i: int): T = r.data[r.i + i]
proc `[]=`[T](r: Ring[T], i: int, v: T) = r.data[r.i + i] = v
proc addFirst[T](r: Ring[T], v: T) =
if r.isFull: throw("ring is full")
r.i = (r.i + CAP - 1) mod CAP
r.data[r.i] = v
r.len += 1
proc addLast[T](r: Ring[T], v: T) =
if r.isFull: throw("ring is full")
let j = (r.i + r.len) mod CAP
r.data[j] = v
r.len += 1
proc popFirst[T](r: Ring[T]): T =
if r.len == 0: throw("ring is empty")
result = r.data[r.i]
r.i = (r.i + 1) mod CAP
r.len -= 1
proc popLast[T](r: Ring[T]): T =
if r.len == 0: throw("ring is empty")
r.len -= 1
let j = (r.i + r.len) mod CAP
result = r.data[j]
# ----------------------------------- Node
-------------------------------------
proc newNode(): Node =
result.new()
result.left = allocRing[pointer]()
result.right = allocRing[pointer]()
result.next = nil
proc isEmpty(n: Node): bool =
return n.left.isEmpty and n.right.isEmpty and (n.next.isNil or
n.next.isEmpty)
proc hasNext(n: Node): bool = not n.next.isNil
proc len(n: Node): int =
result += n.left.len + n.right.len
if n.hasNext:
result += n.next.len * CAP
proc `[]`(n: Node, i: int): pointer =
if i < n.left.len:
return n.left[i]
var j = i - n.left.len
if n.hasNext:
let nextLen = CAP * n.next.len
if j < nextLen:
let r = cast[Ring[pointer]](n.next[j div CAP])
return r[j mod CAP]
j -= nextLen
if j < n.right.len:
return n.right[j]
throw("out of bound")
proc `[]=`(n: Node, i: int, v: pointer) =
if i < n.left.len:
n.left[i] = v
return
var j = i - n.left.len
if n.hasNext:
let nextLen = CAP * n.next.len
if j < nextLen:
let r = cast[Ring[pointer]](n.next[j div CAP])
r[j mod CAP] = v
return
j -= nextLen
if j < n.right.len:
n.right[j] = v
return
throw("out of bound")
proc getOrCreateNext(n: Node): Node =
if n.next.isNil: n.next = newNode()
return n.next
proc addFirst(n: Node, v: pointer) =
if n.left.isFull:
let next = n.getOrCreateNext()
next.addFirst(n.left)
n.left = allocRing[pointer]()
n.left.addFirst(v)
proc addLast(n: Node, v: pointer) =
if n.right.isFull:
let next = n.getOrCreateNext()
next.addLast(n.right)
n.right = allocRing[pointer]()
n.right.addLast(v)
proc popFirst(n: Node): pointer =
if n.left.isNotEmpty:
return n.left.popFirst()
if n.hasNext:
# take one from next level
deallocRing(n.left)
n.left = cast[Ring[pointer]](n.next.popFirst())
if n.next.isEmpty: n.next = nil
return n.left.popFirst()
if n.right.isNotEmpty:
return n.right.popFirst()
throw("node is empty")
proc popLast(n: Node): pointer =
if n.right.isNotEmpty:
return n.right.popLast()
if n.hasNext:
deallocRing(n.right)
n.right = cast[Ring[pointer]](n.next.popLast())
if n.next.isEmpty: n.next = nil
return n.right.popLast()
if n.left.isNotEmpty:
return n.left.popLast()
throw("node is empty")
# -------------------------------- StableSeq
-----------------------------------
proc initStableSeq*[T](): StableSeq[T] =
result.left = allocRing[T]()
result.right = allocRing[T]()
result.next = nil
proc isEmpty[T](t: StableSeq[T]): bool =
return t.left.isEmpty and t.right.isEmpty and (t.next.isNil or
t.next.isEmpty)
proc hasNext[T](t: StableSeq[T]): bool = not t.next.isNil
proc len*[T](t: StableSeq[T]): int =
result += t.right.len + t.left.len
if not t.next.isNil: result += CAP * t.next.len
proc `[]`*[T](t: StableSeq[T], i: int): T =
if i < t.left.len: return t.left[i]
var j = i - t.left.len
if t.hasNext:
let nextLen = CAP * t.next.len
if j < nextLen:
let r = cast[Ring[T]](t.next[j div CAP])
return r[j mod CAP]
j -= nextLen
if j < t.right.len:
return t.right[j]
throw("out of bound")
proc `[]=`*[T](t: StableSeq[T], i: int, v: T) =
if i < t.left.len:
t.left[i] = v
return
var j = i - t.left.len
if t.hasNext:
let nextLen = CAP * t.next.len
if j < nextLen:
let r = cast[Ring[T]](t.next[j div CAP])
r[j mod CAP] = v
return
j -= nextLen
if j < t.right.len:
t.right[j] = v
return
throw("out of bound")
proc pushLast*[T](t: var StableSeq[T], p: Ring[T]) =
if t.next.isNil: t.next = newNode()
t.next.addLast(cast[pointer](p))
proc pushFirst*[T](t: var StableSeq[T], p: Ring[T]) =
if t.next.isNil: t.next = newNode()
t.next.addFirst(cast[pointer](p))
proc addLast*[T](t: var StableSeq[T], v: T) =
if t.right.isFull:
t.pushLast(t.right)
t.right = allocRing[T]()
t.right.addLast(v)
proc addFirst*[T](t: var StableSeq[T], v: T) =
if t.left.isFull:
t.pushFirst(t.left)
t.left = allocRing[T]()
t.left.addFirst(v)
proc popFirst*[T](t: var StableSeq[T]): T =
if t.left.isNotEmpty:
return t.left.popFirst()
if t.hasNext:
deallocRing(t.left)
t.left = cast[Ring[T]](t.next.popFirst())
if t.next.isEmpty: t.next = nil
return t.left.popFirst()
if t.right.isNotEmpty:
return t.right.popFirst()
throw("node is empty")
proc popLast*[T](t: var StableSeq[T]): T =
if t.right.isNotEmpty:
return t.right.popLast()
if t.hasNext:
deallocRing(t.right)
t.right = cast[Ring[T]](t.next.popLast())
if t.next.isEmpty: t.next = nil
return t.right.popLast()
if t.left.isNotEmpty:
return t.left.popLast()
throw("node is empty")
#
------------------------------------------------------------------------------
when isMainModule:
var s = initStableSeq[int]()
for i in 1..10:
s.addLast(i)
s[8] = 13
for i in 0 ..< s.len:
echo s[i]
while not s.isEmpty:
echo s.popLast()
Run
