package internal

import (
	"testing"

	"github.com/stretchr/testify/require"
)

func TestMemNode_Getters(t *testing.T) {
	left := NewNodePointer(&MemNode{})
	right := NewNodePointer(&MemNode{})
	nodeId := NewNodeID(true, 5, 10)

	testKey := []byte("testkey")
	testValue := []byte("testvalue")
	testHash := []byte("testhash")
	node := &MemNode{
		height:    3,
		version:   7,
		size:      42,
		key:       testKey,
		value:     testValue,
		hash:      testHash,
		left:      left,
		right:     right,
		nodeId:    nodeId,
		keyOffset: 100,
	}

	require.Equal(t, uint8(3), node.Height())
	require.Equal(t, uint32(7), node.Version())
	require.Equal(t, int64(42), node.Size())
	require.Equal(t, left, node.Left())
	require.Equal(t, right, node.Right())
	require.Equal(t, testHash, node.Hash().UnsafeBytes())
	require.Equal(t, nodeId, node.ID())

	key, err := node.Key()
	require.NoError(t, err)
	require.Equal(t, testKey, key.UnsafeBytes())

	value, err := node.Value()
	require.NoError(t, err)
	require.Equal(t, testValue, value.UnsafeBytes())
}

func TestMemNode_IsLeaf(t *testing.T) {
	tests := []struct {
		name   string
		height uint8
		want   bool
	}{
		{name: "leaf", height: 0, want: true},
		{name: "branch height 1", height: 1, want: false},
		{name: "branch height 5", height: 5, want: false},
		{name: "branch max height", height: 255, want: false},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			node := &MemNode{height: tt.height}
			require.Equal(t, tt.want, node.IsLeaf())
		})
	}
}

func TestMemNode_String(t *testing.T) {
	tests := []struct {
		name string
		node *MemNode
		want string
	}{
		{
			name: "leaf node",
			node: &MemNode{
				height:  0,
				version: 1,
				size:    1,
				key:     []byte{0xab, 0xcd},
				value:   []byte{0x12, 0x34},
			},
			want: "MemNode{key:abcd, version:1, size:1, value:1234}",
		},
		{
			name: "branch node",
			node: &MemNode{
				height:  2,
				version: 5,
				size:    10,
				key:     []byte{0xff},
				left:    &NodePointer{id: NewNodeID(true, 1, 1)},
				right:   &NodePointer{id: NewNodeID(true, 1, 2)},
			},
			want: "MemNode{key:ff, version:5, size:10, height:2, left:NodePointer{id: NodeID{leaf:true, version:1, index:1}, fileIdx: 0}, right:NodePointer{id: NodeID{leaf:true, version:1, index:2}, fileIdx: 0}}",
		},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			require.Equal(t, tt.want, tt.node.String())
		})
	}
}

func TestMemNode_MutateBranch(t *testing.T) {
	key := []byte("key")
	origHash := []byte("origHash")
	original := &MemNode{
		height:  2,
		version: 5,
		size:    10,
		key:     key,
		hash:    origHash,
		left:    NewNodePointer(&MemNode{}),
		right:   NewNodePointer(&MemNode{}),
	}

	mutated, err := original.MutateBranch(12)
	require.NoError(t, err)

	// Version updated, hash cleared
	require.Equal(t, uint32(12), mutated.Version())
	require.Nil(t, mutated.Hash().UnsafeBytes())

	// Other fields preserved
	require.Equal(t, original.Height(), mutated.Height())
	require.Equal(t, original.Size(), mutated.Size())
	key2, _ := mutated.Key()
	require.Equal(t, key, key2.UnsafeBytes())
	require.Equal(t, original.Left(), mutated.Left())
	require.Equal(t, original.Right(), mutated.Right())

	// Is a copy, not same pointer
	require.NotSame(t, original, mutated)

	// Original unchanged
	require.Equal(t, uint32(5), original.Version())
	require.Equal(t, origHash, original.Hash().UnsafeBytes())
}

func TestMemNode_Get_Leaf(t *testing.T) {
	// When Get is called on a leaf node:
	// - If key matches: returns (value, 0, nil)
	// - If key not found: returns (nil, index, nil) where index is the insertion point
	//   - key < nodeKey: index=0 (would insert before this leaf)
	//   - key > nodeKey: index=1 (would insert after this leaf)
	tests := []struct {
		name      string
		nodeKey   string
		nodeValue string
		searchKey string
		wantValue []byte
		wantIndex int64
	}{
		{
			name:      "exact match",
			nodeKey:   "b",
			nodeValue: "val_b",
			searchKey: "b",
			wantValue: []byte("val_b"),
			wantIndex: 0,
		},
		{
			name:      "search key less than node key",
			nodeKey:   "b",
			nodeValue: "val_b",
			searchKey: "a",
			wantValue: nil,
			wantIndex: 0, // "a" would be inserted before "b"
		},
		{
			name:      "search key greater than node key",
			nodeKey:   "b",
			nodeValue: "val_b",
			searchKey: "c",
			wantValue: nil,
			wantIndex: 1, // "c" would be inserted after "b"
		},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			node := &MemNode{
				height: 0,
				size:   1,
				key:    []byte(tt.nodeKey),
				value:  []byte(tt.nodeValue),
			}
			val, idx, err := node.Get([]byte(tt.searchKey))
			require.NoError(t, err)
			require.Equal(t, tt.wantValue, val.UnsafeBytes())
			require.Equal(t, tt.wantIndex, idx)
		})
	}
}

func TestMemNode_Get_Branch(t *testing.T) {
	// Hand-construct a simple tree:
	//
	//       [b]          <- branch, key="b", size=2
	//      /   \
	//    [a]   [b]       <- leaves (index 0, index 1)
	//
	// In IAVL, branch key = smallest key in right subtree
	//
	// Index is the 0-based position in sorted leaf order:
	// - "a" is at index 0, "b" is at index 1
	// - Keys not found return the insertion point

	leftLeaf := &MemNode{
		height: 0,
		size:   1,
		key:    []byte("a"),
		value:  []byte("val_a"),
	}
	rightLeaf := &MemNode{
		height: 0,
		size:   1,
		key:    []byte("b"),
		value:  []byte("val_b"),
	}
	root := &MemNode{
		height: 1,
		size:   2,
		key:    []byte("b"), // smallest key in right subtree
		left:   NewNodePointer(leftLeaf),
		right:  NewNodePointer(rightLeaf),
	}

	tests := []struct {
		name      string
		searchKey string
		wantValue []byte
		wantIndex int64
	}{
		{
			name:      "find in left subtree",
			searchKey: "a",
			wantValue: []byte("val_a"),
			wantIndex: 0,
		},
		{
			name:      "find in right subtree",
			searchKey: "b",
			wantValue: []byte("val_b"),
			wantIndex: 1,
		},
		{
			name:      "key not found - less than all",
			searchKey: "0",
			wantValue: nil,
			wantIndex: 0, // "0" would be inserted at position 0
		},
		{
			name:      "key not found - greater than all",
			searchKey: "z",
			wantValue: nil,
			wantIndex: 2, // "z" would be inserted at position 2 (after both leaves)
		},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			val, idx, err := root.Get([]byte(tt.searchKey))
			require.NoError(t, err)
			require.Equal(t, tt.wantValue, val.UnsafeBytes())
			require.Equal(t, tt.wantIndex, idx)
		})
	}
}

func TestMemNode_Get_DeeperTree(t *testing.T) {
	// Hand-construct a 3-level tree:
	//
	//            [c]              <- root, size=4
	//          /     \
	//       [b]       [d]         <- branches, size=2 each
	//      /   \     /   \
	//    [a]   [b] [c]   [d]      <- leaves
	//
	// Sorted keys: a=0, b=1, c=2, d=3

	leafA := &MemNode{height: 0, size: 1, key: []byte("a"), value: []byte("val_a")}
	leafB := &MemNode{height: 0, size: 1, key: []byte("b"), value: []byte("val_b")}
	leafC := &MemNode{height: 0, size: 1, key: []byte("c"), value: []byte("val_c")}
	leafD := &MemNode{height: 0, size: 1, key: []byte("d"), value: []byte("val_d")}

	branchLeft := &MemNode{
		height: 1,
		size:   2,
		key:    []byte("b"),
		left:   NewNodePointer(leafA),
		right:  NewNodePointer(leafB),
	}
	branchRight := &MemNode{
		height: 1,
		size:   2,
		key:    []byte("d"),
		left:   NewNodePointer(leafC),
		right:  NewNodePointer(leafD),
	}
	root := &MemNode{
		height: 2,
		size:   4,
		key:    []byte("c"), // smallest key in right subtree
		left:   NewNodePointer(branchLeft),
		right:  NewNodePointer(branchRight),
	}

	tests := []struct {
		searchKey string
		wantValue []byte
		wantIndex int64
	}{
		{"a", []byte("val_a"), 0},
		{"b", []byte("val_b"), 1},
		{"c", []byte("val_c"), 2},
		{"d", []byte("val_d"), 3},
	}
	for _, tt := range tests {
		t.Run(tt.searchKey, func(t *testing.T) {
			val, idx, err := root.Get([]byte(tt.searchKey))
			require.NoError(t, err)
			require.Equal(t, tt.wantValue, val.UnsafeBytes())
			require.Equal(t, tt.wantIndex, idx)
		})
	}
}
