local kIdealStringLength=768
local wv = require 'nylon.debug' { name = 'pls-bbuf' }
local Bbuf = {}
function Bbuf.setIdealStringLength( n )
kIdealStringLength = n
end
function Bbuf:_invalidateOnEdit()
self.cachept = 9.0E99
end
local function Node(text)
return { height = 0, v = text, len=#text }
end
local function tree_delta( self )
return (self.l and self.l.height or 0) - (self.r and self.r.height or 0)
end
local tree_balance
local function tree_rotl(self)
local r = self.r
self.r = r.l
r.l = tree_balance(self)
return tree_balance(r)
end
local function tree_rotr( self )
local l = self.l
self.l = l.r
l.r = tree_balance(self)
return tree_balance(l)
end
local function node_setlen( node )
node.len = (node.l and node.l.len or 0) node.len = node.len + #node.v
node.len = node.len + (node.r and node.r.len or 0)
end
tree_balance = function(self)
local delta = tree_delta(self)
if delta < -1 then
self.r = tree_delta(self.r) > 0 and tree_rotr(self.r) or self.r
return tree_rotl(self)
elseif delta > 1 then
self.l = tree_delta(self.l) < 0 and tree_rotl(self.l) or self.l
return tree_rotr(self)
end
self.height = 0
if self.l and self.l.height > self.height then
self.height = self.l.height
end
if self.r and self.r.height > self.height then
self.height = self.r.height
end
self.height = self.height + 1
node_setlen(self)
return self
end
local function tree_insert( self, pos, elm )
if not self then
return elm
end
if self.l then
if pos <= self.l.len then
self.l = tree_insert(self.l, pos, elm)
node_setlen(self)
return tree_balance(self)
else
pos = pos - self.l.len
end
elseif pos <= 1 then
self.l = tree_insert( self.l, pos, elm )
node_setlen(self)
return tree_balance( self )
end
if pos <= (#self.v+1) then
local modified = self.v:sub( 1, pos-1 ) .. elm.v .. self.v:sub(pos)
if #modified < kIdealStringLength then
self.v = modified
node_setlen(self)
return self
else
local lideal = math.floor(kIdealStringLength * 5.0 / 6.0)
self.v = modified:sub(1,lideal)
self.r = tree_insert( self.r, 0, Node(modified:sub(lideal+1)) )
node_setlen( self )
return tree_balance(self)
end
end
pos = pos - #self.v
self.r = tree_insert( self.r, pos, elm )
node_setlen(self)
return tree_balance(self)
end
local function tree_delete( self, posbeg, len )
if not self then
return
end
wv.log('debug','tree_delete, self=%s posbeg=%d len=%d #l=%d #v=%d',
self, posbeg, len, self.l and self.l.len or -1, #self.v)
if self.l then
if posbeg <= self.l.len then
local remain = tree_delete(self.l, posbeg, len)
if remain then
posbeg = 1
len = remain
wv.log('debug','back to clip more, remain=%d #v=%d',remain,#self.v)
else
node_setlen(self)
return end
else
posbeg = posbeg - self.l.len
end
end
if posbeg <= #self.v then
local remain = #self.v - posbeg - len + 1
if remain > 0 then
local modified = self.v:sub( 1, posbeg-1 ) .. self.v:sub(posbeg+len)
self.v = modified
node_setlen(self)
return
else
local modified = self.v:sub( 1, posbeg-1 )
local removed = #self.v - posbeg + 1
self.v = modified
len = len - removed
posbeg = 1
end
else
posbeg = posbeg - #self.v
end
if self.r then
local remain = tree_delete( self.r, posbeg, len )
node_setlen(self)
return remain else
wv.log('debug','need to clip more on return, posbeg=%d len=%d', posbeg, len)
node_setlen(self)
return len
end
end
function treewalk_to( self, point )
if not self then wv.log('abnorm','avl text search out of bounds, point=%d',point)
return
end
if self.l then
if point <= self.l.len then
return treewalk_to( self.l, point )
else
point = point - self.l.len
end
end
if point <= #self.v then
return self.v, point
end
return treewalk_to( self.r, point - #self.v )
end
function tree_traverse( self, point, cbfun )
if not self then
return
end
if self.l then
if point <= self.l.len then
tree_traverse( self.l, point, cbfun )
end
point = point - self.l.len
end
if point <= #self.v then
cbfun( self.v, (point < 1 and 1 or point) )
end
point = point - #self.v
return tree_traverse( self.r, point, cbfun )
end
function Bbuf:end_point()
return self.max
end
function Bbuf:char_at_point_dec( point )
local l, col = treewalk_to( self.textavlroot, point )
if not l then
wv.log('error','point maybe out of range? point=%d max=%d',point or -99,self:end_point())
return string.byte(' ',1)
else
return string.byte(l,col)
end
end
function Bbuf:char_at_point( point )
return string.char( self:char_at_point_dec(point) )
end
function Bbuf:append( text )
self:_insert_int( self.max + 1, text )
end
function Bbuf:walkFragments( point )
local co = coroutine.create(function()
tree_traverse( self.textavlroot, point,
function(t,point)
coroutine.yield(t,point)
end )
end)
return function()
local ok, t, point = coroutine.resume(co)
if ok then
return t, point
end
end
end
function Bbuf:walkFragmentsEOL( point )
local fn = self:walkFragments(point)
local lastt,lasteol
return function()
local t, point
if lasteol and (lasteol+1) <= #lastt then
t = lastt
point = lasteol + 1
lasteol = nil
else
t, point = fn()
end
if t then
local eol = string.find(t,'\n',point)
if eol then
lastt = t
lasteol = eol
return t, point, eol
else
return t, point
end
end
end
end
function Bbuf:walkFragmentsEOL_orWidth( point, width )
local fn = self:walkFragmentsEOL(point)
local t, col, eol
local remain = width
return function()
if not t then
t,col,eol = fn()
if not t then
return
end
end
local w = (eol and eol or #t) - col + 1
if w > remain then
local oldcol = col
local nextcol = col+remain
if nextcol > #t then
t = nil
else
col = nextcol
end
return t, oldcol, nextcol
else
local savet = t
t = nil
if eol then
remain = width
end
return savet, col, eol
end
end
end
function Bbuf:searchPointsCharBackward(point)
local ndx, col = self:lcol4point(point)
return function()
local rcl ,rccol = self.lines[ndx], col
end
end
function tree_dump(self,path)
path = path or '[root'
if self.l then
tree_dump( self.l, path .. ', left' )
end
print( string.format('node %s %s] #=%d l=%s r=%s v="%s"',
self, path, self.len, self.l, self.r, self.v ))
if self.r then
tree_dump( self.r, path .. ', right' )
end
end
function Bbuf:dump()
tree_dump( self.textavlroot )
end
function Bbuf:new()
return setmetatable({
max = 0,
cachept = 9.0E99,
operations = {},
unmodified_operation_index = 0,
}, { __index = self })
end
function Bbuf:sub( l, r )
local substrleft = (r-l)
local frags = {}
for line, col in self:walkFragments(l) do
local llen = #line-col+1
if llen > substrleft then
table.insert(frags,line:sub(col,col+substrleft))
break
else
table.insert(frags,line:sub(col))
substrleft = substrleft - llen
end
end
return table.concat(frags)
end
function Bbuf:undo()
if #self.operations < 1 then
return
end
local last = self.operations[#self.operations]
table.remove( self.operations, #self.operations )
if last.removed then
self:_insert_int( last.l, last.text )
return last.l
elseif last.inserted then
self:_remove_int( last.point, last.point + last.len - 1 )
return last.point
end
end
function Bbuf:isModified()
return self.unmodified_operation_index ~= #self.operations
end
function Bbuf:setUnmodified()
self.unmodified_operation_index = #self.operations
end
function Bbuf:_addoperation( o )
local last = self.operations[#self.operations]
if last and o.inserted and last.inserted and
(o.point == last.point + last.len) then
last.len = last.len + o.len
else
table.insert( self.operations, o )
end
end
function Bbuf:remove( l, r )
l = (l < 1) and 1 or l
r = r or l
r = (r > self.max) and self.max or r
if r < l then return
end
if self.textavlroot then
self:_addoperation{ removed = true, text = self:sub(l,r), l = l, r = r }
self:_remove_int( l, r )
end
end
function Bbuf:_remove_int( l, r )
local len = (r-l)+1
tree_delete( self.textavlroot, l, len )
self.max = self.max - len
end
function Bbuf:_old_remove_int( l, r )
local lndx, lcol = self:lcol4point(l)
local rndx, rcol = self:lcol4point(r)
if lndx == rndx then
if lndx then
local line = self.lines[lndx]
self.lines[lndx] = line:sub(1,lcol-1) .. line:sub(rcol+1)
self.max = self.max - (r-l+1)
end
else
if r > self:end_point() and lndx == #self.lines then
local line = self.lines[lndx]
self.max = self.max - (#line-lcol+1)
self.lines[lndx] = line:sub(1,lcol-1)
else
error( string.format('multi-line remove not implemented [%d,%d]->[%d,%d]',
lndx or -99,lcol or -99, rndx or -99, rcol or -99))
end
end
self:_invalidateOnEdit()
end
function Bbuf:insert( point, text )
if point > self:end_point() + 1 and self:char_at_point_dec(self:end_point()) ~= 10 then
self:insert( self:end_point()+1, '\n' )
end
if #text > 0 then
self:_addoperation{ inserted = true, point = point, len = #text }
end
return self:_insert_int( point, text )
end
function Bbuf:_insert_int( point, text )
local full = #text
local off = 0
while #text > kIdealStringLength do
self.textavlroot = tree_insert( self.textavlroot, point+off, Node(text:sub(1,kIdealStringLength)) )
off = off + kIdealStringLength
text = text:sub(kIdealStringLength+1)
end
if #text > 0 then
self.textavlroot = tree_insert( self.textavlroot, point+off, Node(text:sub(1)) )
end
self.max = self.max + full
self:_invalidateOnEdit()
end
function Bbuf:replace( ptl, ptr, text )
self:remove(ptl,ptr)
self:insert(ptl,text)
end
return Bbuf