five/hbrdd/ntx/ntx_test.go

// Copyright (c) 2026 Charles KWON OhJun (charleskwonohjun@gmail.com)
// All rights reserved.

package ntx

import (
	"encoding/binary"
	"os"
	"path/filepath"
	"testing"
)

// createTestNTX builds a minimal NTX file with a simple B-tree for testing.
// Creates a 3-level tree: root → 2 internal → leaves with sorted keys.
func createTestNTX(t *testing.T, dir string, keys []string, keyLen int) string {
	t.Helper()
	path := filepath.Join(dir, "test.ntx")
	f, err := os.Create(path)
	if err != nil {
		t.Fatal(err)
	}

	itemSize := 8 + keyLen // child(4) + recNo(4) + key
	// Calculate max items per page
	// Available space = BlockSize - 2(keyCount) - 2*(maxItem+1)(offset table)
	// Approximate: (BlockSize - 2) / (itemSize + 2) - 1
	maxItem := (BlockSize - 4) / (itemSize + 2)
	if maxItem > 255 {
		maxItem = 255
	}

	// Build header
	hdr := Header{
		Type:     0x0401,
		Version:  1,
		Root:     uint32(HeaderSize), // root page at offset 1024
		NextPage: 0,
		ItemSize: uint16(itemSize),
		KeySize:  uint16(keyLen),
		KeyDec:   0,
		MaxItem:  uint16(maxItem),
		HalfPage: uint16(maxItem / 2),
	}
	copy(hdr.KeyExpr[:], "KEY")
	copy(hdr.TagName[:], "TEST")

	WriteHeader(f, &hdr)

	// Build a simple single-page leaf with all keys (for small test sets)
	// Page layout: [keyCount:2][offsets:...][key entries...]
	page := [BlockSize]byte{}
	nKeys := len(keys)
	if nKeys > maxItem {
		nKeys = maxItem
	}
	binary.LittleEndian.PutUint16(page[0:2], uint16(nKeys))

	// Build offset table and key data
	dataStart := 2 + (maxItem+1)*2
	for i := 0; i < nKeys; i++ {
		entryOffset := dataStart + i*itemSize
		// Offset table entry
		binary.LittleEndian.PutUint16(page[2+i*2:4+i*2], uint16(entryOffset))
		// Key entry: child(0) + recNo + key
		binary.LittleEndian.PutUint32(page[entryOffset:entryOffset+4], 0)         // no child (leaf)
		binary.LittleEndian.PutUint32(page[entryOffset+4:entryOffset+8], uint32(i+1)) // recNo = 1-based
		// Key value (padded with spaces)
		key := make([]byte, keyLen)
		for j := range key {
			key[j] = ' '
		}
		copy(key, keys[i])
		copy(page[entryOffset+8:entryOffset+8+keyLen], key)
	}
	// Last offset entry (for child pointer at end)
	binary.LittleEndian.PutUint16(page[2+nKeys*2:4+nKeys*2], uint16(dataStart+nKeys*itemSize))

	f.WriteAt(page[:], int64(HeaderSize))

	// Update header NextPage
	hdr.NextPage = uint32(HeaderSize + BlockSize)
	WriteHeader(f, &hdr)

	f.Close()
	return path
}

func TestOpenAndSeek(t *testing.T) {
	dir := t.TempDir()
	keys := []string{"JONES", "KIM", "LEE", "PARK", "SMITH"}
	path := createTestNTX(t, dir, keys, 10)

	idx, err := OpenIndex(path)
	if err != nil {
		t.Fatal(err)
	}
	defer idx.Close()

	// Seek exact: "KIM"
	searchKey := padKey("KIM", 10)
	recNo, found := idx.Seek(searchKey)
	if !found {
		t.Error("SEEK 'KIM' should find exact match")
	}
	if recNo != 2 { // KIM is at position 2 (sorted: JONES=1, KIM=2, LEE=3, ...)
		t.Errorf("SEEK 'KIM' recNo = %d, want 2", recNo)
	}

	// Seek exact: "SMITH"
	searchKey = padKey("SMITH", 10)
	recNo, found = idx.Seek(searchKey)
	if !found {
		t.Error("SEEK 'SMITH' should find exact match")
	}
	if recNo != 5 {
		t.Errorf("SEEK 'SMITH' recNo = %d, want 5", recNo)
	}

	// Seek not found: "MILLER" — should position at "PARK" (next higher)
	searchKey = padKey("MILLER", 10)
	recNo, found = idx.Seek(searchKey)
	if found {
		t.Error("SEEK 'MILLER' should NOT find exact match")
	}
	if recNo != 4 { // PARK is next after MILLER
		t.Errorf("SEEK 'MILLER' soft recNo = %d, want 4 (PARK)", recNo)
	}
}

func TestGoTopGoBottom(t *testing.T) {
	dir := t.TempDir()
	keys := []string{"APPLE", "BANANA", "CHERRY", "DATE", "ELDER"}
	path := createTestNTX(t, dir, keys, 10)

	idx, err := OpenIndex(path)
	if err != nil {
		t.Fatal(err)
	}
	defer idx.Close()

	// GO TOP
	if !idx.GoTop() {
		t.Fatal("GoTop failed")
	}
	if idx.CurRecNo() != 1 {
		t.Errorf("GoTop recNo = %d, want 1", idx.CurRecNo())
	}
	if string(idx.CurKey()[:5]) != "APPLE" {
		t.Errorf("GoTop key = %q", string(idx.CurKey()[:5]))
	}

	// GO BOTTOM
	if !idx.GoBottom() {
		t.Fatal("GoBottom failed")
	}
	if idx.CurRecNo() != 5 {
		t.Errorf("GoBottom recNo = %d, want 5", idx.CurRecNo())
	}
	if string(idx.CurKey()[:5]) != "ELDER" {
		t.Errorf("GoBottom key = %q", string(idx.CurKey()[:5]))
	}
}

func TestSkipForwardBackward(t *testing.T) {
	dir := t.TempDir()
	keys := []string{"AAA", "BBB", "CCC", "DDD", "EEE"}
	path := createTestNTX(t, dir, keys, 10)

	idx, err := OpenIndex(path)
	if err != nil {
		t.Fatal(err)
	}
	defer idx.Close()

	// Start at top
	idx.GoTop()

	// Skip forward through all keys
	var recNos []uint32
	recNos = append(recNos, idx.CurRecNo())
	for idx.SkipNext() {
		recNos = append(recNos, idx.CurRecNo())
	}

	if len(recNos) != 5 {
		t.Fatalf("forward skip collected %d records, want 5", len(recNos))
	}
	for i, rn := range recNos {
		if rn != uint32(i+1) {
			t.Errorf("forward[%d] recNo = %d, want %d", i, rn, i+1)
		}
	}

	// Should be EOF now
	if !idx.IsEOF() {
		t.Error("should be EOF after full forward scan")
	}

	// Go bottom and skip backward
	idx.GoBottom()
	recNos = nil
	recNos = append(recNos, idx.CurRecNo())
	for idx.SkipPrev() {
		recNos = append(recNos, idx.CurRecNo())
	}

	if len(recNos) != 5 {
		t.Fatalf("backward skip collected %d records, want 5", len(recNos))
	}
	// Should be 5, 4, 3, 2, 1
	for i, rn := range recNos {
		expected := uint32(5 - i)
		if rn != expected {
			t.Errorf("backward[%d] recNo = %d, want %d", i, rn, expected)
		}
	}
}

func TestSeekFirstAndLast(t *testing.T) {
	dir := t.TempDir()
	keys := []string{"FIRST", "MIDDLE", "ZZZZZ"}
	path := createTestNTX(t, dir, keys, 10)

	idx, err := OpenIndex(path)
	if err != nil {
		t.Fatal(err)
	}
	defer idx.Close()

	// Seek first key
	recNo, found := idx.Seek(padKey("FIRST", 10))
	if !found || recNo != 1 {
		t.Errorf("SEEK 'FIRST': found=%v recNo=%d", found, recNo)
	}

	// Seek last key
	recNo, found = idx.Seek(padKey("ZZZZZ", 10))
	if !found || recNo != 3 {
		t.Errorf("SEEK 'ZZZZZ': found=%v recNo=%d", found, recNo)
	}

	// Seek before first: should position at FIRST (softseek)
	recNo, found = idx.Seek(padKey("AAA", 10))
	if found {
		t.Error("SEEK 'AAA' should not find exact match")
	}
	if recNo != 1 {
		t.Errorf("SEEK 'AAA' soft recNo = %d, want 1", recNo)
	}

	// Seek after last: should be EOF
	recNo, found = idx.Seek(padKey("ZZZZZZZ", 10))
	if found {
		t.Error("SEEK past last should not find")
	}
	if !idx.IsEOF() {
		t.Error("SEEK past last should set EOF")
	}
}

// --- Helper ---

func padKey(s string, keyLen int) []byte {
	key := make([]byte, keyLen)
	for i := range key {
		key[i] = ' '
	}
	copy(key, s)
	return key
}