#! /usr/bin/lua

local _max, _abs = math.max, math.abs

local avl_tree = {}

local avl_tree_empty_child__ = {
    depth = 0
}

function avl_tree:insert_r(rootparent, rootdir, root, data)
    local cmpres = self.compare(data, root.data)
    local next_root_dir
    if cmpres > 0 then
        next_root_dir = 0
    elseif cmpres < 0 then
        next_root_dir = 1
    else
        root.data = data
        return true -- no insertion, no problem
    end
    -- local next_root
    if root.children[next_root_dir] == avl_tree_empty_child__ then
        root.children[next_root_dir] = {
            data = data,
            depth = 1,
            children = {
                [0] = avl_tree_empty_child__,
                [1] = avl_tree_empty_child__
            }
        }
    else
        if self:insert_r(root, next_root_dir, root.children[next_root_dir], data) then
            return true -- no insertion, no problem
        end
    end
    local chdiff = root.children[0].depth - root.children[1].depth
    if _abs(chdiff) > 1 then
        local deepdir = (chdiff > 0) and 0 or 1

        local new_root

        local c = root
        local b = c.children[deepdir]

        if b.children[deepdir].depth < b.children[1 - deepdir].depth then
            local a = b.children[1 - deepdir]

            c.children[deepdir] = a.children[1 - deepdir]
            b.children[1 - deepdir] = a.children[deepdir]
            a.children[deepdir] = b
            a.children[1 - deepdir] = c

            c.depth = _max(c.children[0].depth, c.children[1].depth) + 1
            b.depth = _max(b.children[0].depth, b.children[1].depth) + 1
            a.depth = _max(a.children[0].depth, a.children[1].depth) + 1

            new_root = a
        else
            c.children[deepdir], b.children[1 - deepdir] = b.children[1 - deepdir], c

            c.depth = _max(c.children[0].depth, c.children[1].depth) + 1
            b.depth = _max(b.children[0].depth, b.children[1].depth) + 1

            new_root = b
            print(b.data)
            print(b.children[0].data)
            print(b.children[1].data)
        end


        if rootparent then
            rootparent.children[rootdir] = new_root
        end

        return
    end
    root.depth = _max(root.children[0].depth, root.children[1].depth) + 1
end

function avl_tree:insert(data)
    if not self.ghostroot.children[0] then
        self.ghostroot.children[0] = {
            data = data,
            depth = 1,
            children = {
                [0] = avl_tree_empty_child__,
                [1] = avl_tree_empty_child__
            }
        }
        return
    end
    print(self.ghostroot)
    self:insert_r(self.ghostroot, 0, self.ghostroot.children[0], data)
end

function avl_tree:debug_r(root, tlen)
    local pstr = tostring(root.data) .. " [" .. root.depth .. "]"
    local ntlen = tlen + #pstr
    if root.children[0] ~= avl_tree_empty_child__ then
        self:debug_r(root.children[0], ntlen + 1)
        print((" "):rep(ntlen) .. "/")
    end
    print((" "):rep(tlen) .. pstr)
    if root.children[1] ~= avl_tree_empty_child__ then
        print((" "):rep(ntlen) .. "\\")
        self:debug_r(root.children[1], ntlen + 1)
    end
    -- lol no
end

function avl_tree:debug()
    print(("-"):rep(50))
    if self.ghostroot.children[0] then
        self:debug_r(self.ghostroot.children[0], 0)
    end
    print(("-"):rep(50))
end

local meta_avl_tree = {__index = avl_tree}
local function avl_tree_new(cmpfunc)
    return setmetatable({
        compare = cmpfunc,
        ghostroot = {
            children = {}
        }
    }, meta_avl_tree)
end


local myavltree = avl_tree_new(function(a, b)
    return (a > b) and -1 or ((a < b) and 1 or 0)
end)

while true do
    local s = io.read()
    local n = tonumber(s)
    if not n then break end
    myavltree:insert(n)
    myavltree:debug()
end

--[=[for ix = 1, 64 do
    myavltree:insert(math.random(1, 1000))
end
myavltree:debug()--]=]