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 )
--   wv.log('debug','tree insert, e=%s', elm.v)
   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)
      -- no nodes change, but in full implementation, we should (possibly) split
      -- the strings here to make a new node, which I guess would be
      -- inserted to the right??
      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)
         -- wv.log('debug','avl text tree split string=%d -> %d',#modified, 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 -- tree_balance(self)
         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
         -- tree_delete( self.r, 1, len-removed )
         
--         local lideal = math.floor(#modified / 2)
--         self.v = modified:sub(1,lideal)
--         -- wv.log('debug','avl text tree split string=%d -> %d',#modified, lideal)
--         self.r = tree_insert( self.r, 0, Node(modified:sub(lideal+1)) )
--         node_setlen( self )
--         return -- tree_balance(self)
      end
   else
      posbeg = posbeg - #self.v
   end

   if self.r then
      local remain = tree_delete( self.r, posbeg, len )
      node_setlen(self)
      return remain -- tree_balance(self)
   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 -- out of bounds or something
      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
      -- wv.log('debug','treewalk_to point=%d #l=%d',point,#self.v)
      return self.v, point
   end

   return treewalk_to( self.r, point - #self.v )
end


function tree_traverse( self, point, cbfun )
--   wv.log('debug','tree_traverse point=%d cbfun=%s', 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:lcol4point(point)
--   local ndx = 1
--   if not point or point < 1 then
--      wv.log('abnorm','invalid point=%s',point)
--      error('invalid point')
--   end
--   if point >= self.cachept and (point < (self.cachept+self.cachelen)) then
--      return self.cachel, (point-self.cachept+1)
--   end
--   local startPoint = point
--   while ndx <= #self.lines do
--      local llen = #(self.lines[ndx])
--      -- wv.log('debug','ndx=%d llen=%d point=%d line=%s',ndx,llen,point,self.lines[ndx])
--      if llen >= point then
--         self.cachept = startPoint - point + 1
--         self.cachel = ndx
--         self.cachelen = #self.lines[1]
--         return ndx, point
--      else
--         point = point - llen
--         ndx = ndx + 1
--      end
--   end
--   wv.log('error','point=%d, max=%d #lines=%d',point,self.max,#self.lines)
--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 )
   -- this could probably be optimized with an optimized AVL
   -- "insert all the way to the right" operation that avoids
   -- all the un-needed comparisons...
   -- but for now, it is okay
   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()
      --wv.log('debug','walkFragments resuming point=%d',point)
      local ok, t, point = coroutine.resume(co)
      -- wv.log('debug','walkFragments resumed=%s / %s / %s',ok, tostring(point), tostring(t))
      if ok then
         return t, point
      end
--      local t = {}
--      while point < self:end_point() do
--         table.insert(t,self:char_at_point(point))
--         point = point + 1
--         if t[#t] == '\n' then
--            break
--         end
--      end
--      if #t > 0 then
--         local str = table.concat(t)
--         wv.log('debug','walkfrag, t=%d str=%s', #t,str)
--         return str, 1, #t
--      else
--         wv.log('debug','walkfrag END, t=%d', #t)
--      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)
--         wv.log('debug','walkFragmentsEOL, [b,e] = [%d,%d] t[]=%s',
--                point, (eol or -1), t:sub(point,eol) )
         if eol then
            lastt = t
            lasteol = eol
            return t, point, eol
         else
            return t, point
         end
      end
   end

--   local ndx, col = self:lcol4point(point)
--   return function()
--      local rcl ,rccol = self.lines[ndx], col
--      if not rcl then
--         return
--      end
--      local nl = string.find( rcl, '\n', rccol )
--      if nl then
--         col = nl+1
--         if col > #rcl then
--            col = 1
--            ndx = ndx + 1
--         end
--         return rcl,rccol,nl
--      else -- no EOL, go to next fragment
--         col = 1
--         ndx = ndx + 1
--         if self.lines[ndx] then
--            return rcl,rccol
--         else
--            return rcl,rccol,(#rcl+1)
--         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({
                   -- lines = {},
                   --  textavlroot = Node(''),
                   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

-- returns some point near where the undone operation occurred or something
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 -- possibly if self.max = 0
      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
--   return self:_remove_int( l, r )
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)
--   wv.log( 'debug', 'remove [%d-%d] :: end=%d :: [%d,%d]->[%d,%d]',
--           l, r, self:end_point(),
   --           lndx or -99,lcol or -99, rndx or -99, rcol or -99)
   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 )
--   if point > self:end_point() then
--      return self:append(text)
--   else
   local full = #text
   -- wv.log('debug','insert point=%d max=%d #text=%d', point or -99, self.max, #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
end

function Bbuf:replace( ptl, ptr, text )
   -- making this a primitive because it is a good candidate for optimization,
   -- but for now it is just implemented as 'remove' + insert
   self:remove(ptl,ptr)
   self:insert(ptl,text)
end


-- local subbed = l:gsub('\t','    '):gsub('\n','')






return Bbuf