gistfile1.txt

package main

import (
	_ "image/png"
	"log"
	"net/http"
	"strconv"
)

type nodeManager struct {
	root            *node
	minimalNodeSize int
}

type node struct {
	start, size int
	occupied    bool
	left        *node
	right       *node
}

func (m *nodeManager) findNode(size int) *node {
	if size == 0 {
		return nil
	}

	var _find func(current *node) *node
	_find = func(current *node) *node {
		if current == nil {
			return nil
		}

		if current.occupied && current.left == nil && current.right == nil {
			return nil
		}

		if !current.occupied {
			if size > current.size {
				return nil
			}

			if size > current.size/2 {
				current.occupied = true
				return current
			}

			if current.size < m.minimalNodeSize*2 {
				current.occupied = true
				return current
			}

			current.split()
		}

		l := _find(current.left)
		if l != nil {
			return l
		}
		return _find(current.right)
	}

	return _find(m.root)
}

func (n *node) split() {
	if n.left != nil || n.right != nil {
		panic("already splitted")
	}

	n.left = &node{
		start: n.start,
		size:  n.size / 2,
	}
	n.right = &node{
		start: n.start + n.size/2,
		size:  n.size / 2,
	}
	n.occupied = true
}