func (a *ShelfAllocator) Allocate(w, h int) (x, y int, ok bool) {
	// Add padding to requested size
	paddedW := w + a.padding
	paddedH := h + a.padding

	// Try to find an existing shelf with enough space and height
	for i := range a.shelves {
		shelf := &a.shelves[i]

		// Check if item fits horizontally
		if shelf.x+paddedW > a.width {
			continue
		}

		// Check if item fits vertically in this shelf
		if h > shelf.height {
			// Item is taller than shelf - check if we can extend the shelf
			// Only possible if this is the last shelf and there's room below
			if i == len(a.shelves)-1 {
				newBottom := shelf.y + paddedH
				if newBottom <= a.height {
					// Extend shelf height
					shelf.height = h
					x, y = shelf.x, shelf.y
					shelf.x += paddedW
					a.usedArea += w * h
					return x, y, true
				}
			}
			continue
		}

		// Item fits on this shelf
		x, y = shelf.x, shelf.y
		shelf.x += paddedW
		a.usedArea += w * h
		return x, y, true
	}

	// No existing shelf works - try to create a new one
	newY := 0
	if len(a.shelves) > 0 {
		last := a.shelves[len(a.shelves)-1]
		newY = last.y + last.height + a.padding
	}

	// Check if new shelf fits
	if newY+paddedH > a.height {
		return -1, -1, false
	}

	// Create new shelf
	newShelf := shelf{
		y:	newY,
		height:	h,
		x:	paddedW,
	}
	a.shelves = append(a.shelves, newShelf)
	a.usedArea += w * h

	return 0, newY, true
}

func (g *GridAllocator) Allocate() (x, y int, ok bool) {
	if g.next >= g.cols*g.rows {
		return -1, -1, false
	}

	col := g.next % g.cols
	row := g.next / g.cols

	cellWithPad := g.cellSize + g.padding
	x = col * cellWithPad
	y = row * cellWithPad

	g.next++
	return x, y, true
}

func (a *ShelfAllocator) AllocateFixed(cellSize int) (x, y int, ok bool) {
	return a.Allocate(cellSize, cellSize)
}

func (g *GridAllocator) Allocated() int {
	return g.next
}

func (a *ShelfAllocator) CanFit(w, h int) bool {
	paddedW := w + a.padding
	paddedH := h + a.padding

	// Items wider than the allocator can never fit
	if paddedW > a.width {
		return false
	}

	// Items taller than the allocator can never fit
	if paddedH > a.height {
		return false
	}

	// Check existing shelves
	for i := range a.shelves {
		shelf := &a.shelves[i]

		// Check if item fits horizontally
		if shelf.x+paddedW > a.width {
			continue
		}

		// Check if item fits in shelf height
		if h <= shelf.height {
			return true
		}

		// Check if we can extend last shelf
		if i == len(a.shelves)-1 {
			if shelf.y+paddedH <= a.height {
				return true
			}
		}
	}

	// Check if we can create a new shelf
	newY := 0
	if len(a.shelves) > 0 {
		last := a.shelves[len(a.shelves)-1]
		newY = last.y + last.height + a.padding
	}

	return newY+paddedH <= a.height
}

func (g *GridAllocator) Capacity() int {
	return g.cols * g.rows
}

func (g *GridAllocator) CellSize() int {
	return g.cellSize
}

func (a *ShelfAllocator) CurrentShelfRemainingWidth() int {
	if len(a.shelves) == 0 {
		return a.width
	}
	last := a.shelves[len(a.shelves)-1]
	if last.x >= a.width {
		return 0
	}
	return a.width - last.x
}

func (g *GridAllocator) GridDimensions() (cols, rows int) {
	return g.cols, g.rows
}

func (g *GridAllocator) IsFull() bool {
	return g.next >= g.cols*g.rows
}

func NewGridAllocator(width, height, cellSize, padding int) *GridAllocator {
	cellWithPad := cellSize + padding
	cols := width / cellWithPad
	rows := height / cellWithPad

	if cols <= 0 {
		cols = 1
	}
	if rows <= 0 {
		rows = 1
	}

	return &GridAllocator{
		width:		width,
		height:		height,
		cellSize:	cellSize,
		padding:	padding,
		cols:		cols,
		rows:		rows,
		next:		0,
	}
}

func NewShelfAllocator(width, height, padding int) *ShelfAllocator {
	return &ShelfAllocator{
		width:		width,
		height:		height,
		padding:	padding,
		shelves:	make([]shelf, 0, 16),	// Preallocate for typical use
	}
}

func (g *GridAllocator) Remaining() int {
	return g.Capacity() - g.next
}

func (a *ShelfAllocator) RemainingHeight() int {
	if len(a.shelves) == 0 {
		return a.height
	}

	last := a.shelves[len(a.shelves)-1]
	used := last.y + last.height + a.padding
	if used >= a.height {
		return 0
	}
	return a.height - used
}

func (g *GridAllocator) Reset() {
	g.next = 0
}

func (a *ShelfAllocator) Reset() {
	a.shelves = a.shelves[:0]	// Keep capacity
	a.usedArea = 0
}

func (a *ShelfAllocator) ShelfCount() int {
	return len(a.shelves)
}

func (a *ShelfAllocator) TotalArea() int {
	return a.width * a.height
}

func (a *ShelfAllocator) UsedArea() int {
	return a.usedArea
}

func (a *ShelfAllocator) Utilization() float64 {
	if a.width <= 0 || a.height <= 0 {
		return 0
	}
	totalArea := a.width * a.height
	return float64(a.usedArea) / float64(totalArea)
}

func (g *GridAllocator) Utilization() float64 {
	capacity := g.Capacity()
	if capacity <= 0 {
		return 0
	}
	return float64(g.next) / float64(capacity)
}

type ShelfAllocator struct {
	width	int	// Total width of the atlas
	height	int	// Total height of the atlas
	padding	int	// Padding between glyphs
	shelves	[]shelf	// List of shelves

	// Tracking for utilization
	usedArea	int
}

type GridAllocator struct {
	width		int	// Atlas width
	height		int	// Atlas height
	cellSize	int	// Size of each cell (square)
	padding		int	// Padding between cells
	cols		int	// Number of columns
	rows		int	// Number of rows
	next		int	// Next cell index
}