jx/internal/search/binary_test.go

// Copyright 2024 Matthew Rich <matthewrich.conf@gmail.com>. All rights reserved.

package search 

import (
	"github.com/stretchr/testify/assert"
	"testing"
	"log/slog"
)

func TestNewBinary(t *testing.T) {
	b := NewBinaryTree[int](9)
	assert.NotNil(t, b)

	for _, v := range []struct { expectedindex , value int } {
		{ expectedindex: BSTROOTNODEID, value: 7 },
		{ expectedindex: 2*BSTROOTNODEID + LEFTOFFSET, value: 4 },
		{ expectedindex: 2*BSTROOTNODEID + RIGHTOFFSET, value: 9 },
		{ expectedindex: 4 + RIGHTOFFSET, value: 18 },
		{ expectedindex: 2 + RIGHTOFFSET, value: 5 },
		{ expectedindex: 4 + RIGHTOFFSET, value: 20 },
		{ expectedindex: 4 - LEFTOFFSET, value: 3 },
		{ expectedindex: 8 - LEFTOFFSET, value: 2 },
		{ expectedindex: 8 - LEFTOFFSET, value: 1 },
		{ expectedindex: 16 - LEFTOFFSET, value: 0 },
		{ expectedindex: 16 - LEFTOFFSET, value: -1 },
	} {
		idx := b.Insert(v.value)
		slog.Info("TestInsert()", "index", idx, "value", v, "b", b, "data", b.Binary)
		assert.Equal(t, v.expectedindex, idx)
		assert.Equal(t, v.value, b.Get(v.expectedindex))
	}
	assert.Equal(t, 7, b.zeroIndex)
	b.BFS(func(index int, depth int, v int) {
		slog.Info("BFS()", "index", index, "depth", depth, "value", v, "b", b, "data", b.Binary)
		assert.Equal(t, v, b.Get(index))
	})
}

func TestBinaryDepth(t *testing.T) {
	b := NewBinaryTree[int](9)
	assert.NotNil(t, b)
	for _, v := range []struct{ expecteddepth, index int }{
		{ expecteddepth: 1, index: 0 },
		{ expecteddepth: 2, index: 1 },
		{ expecteddepth: 2, index: 2 },
		{ expecteddepth: 3, index: 5 },
	} {
		assert.Equal(t, v.expecteddepth, b.Depth(v.index))
	}
}

func TestBinaryWidth(t *testing.T) {
	b := NewBinaryTree[int](9)
	assert.NotNil(t, b)
	for _, v := range []struct{ expectedwidth, index int }{
		{ expectedwidth: 1, index: 0 },
		{ expectedwidth: 2, index: 1 },
		{ expectedwidth: 2, index: 2 },
		{ expectedwidth: 4, index: 5 },
		{ expectedwidth: 8, index: 8 },
		{ expectedwidth: 16, index: 17 },
	} {
		assert.Equal(t, v.expectedwidth, b.Width(v.index))
	}
}

func TestBinaryInSubTree(t *testing.T) {
	b := NewBinaryTree[int](9)
	assert.NotNil(t, b)
	for _, v := range []struct{ expected bool; tree, index, start, end int }{
		{ expected: true, tree: 0, index: 0, start: 0, end: 0 },
		{ expected: true, tree: 4, index: 19, start: 19, end: 22 },
		{ expected: false, tree: 4, index: 13, start: -1, end: -1 },
		{ expected: false, tree: 5, index: 6, start: -1, end: -1 },
	} {
		start, end := b.LevelRange(v.index, v.tree)
		assert.Equal(t, v.start, start)
		assert.Equal(t, v.end, end)
		assert.Equal(t, v.expected, b.InSubTree(v.index, v.tree))
	}
}

func TestBinaryMoveSubTree(t *testing.T) {
	expected := []int{ 0, 4, 0, 7, 0, 0, 5, 18, 0, 0, 0, 0, 0, 0, 9, 20 }
	b := NewBinaryTree[int](9)
	assert.NotNil(t, b)

	b.Insert(7)
	b.Insert(4)
	b.Insert(9)
	b.Insert(18)
	b.Insert(20)
	b.MoveSubTree(2, 6)
	b.RotateRight(0, 2, 1)
	b.Insert(5)
	assert.EqualValues(t, expected, (*b.Binary)[:16])
}

func TestBinaryMaxDepth(t *testing.T) {
	//expected := []int{ 0, 4, 0, 7, 0, 0, 5, 18, 0, 0, 0, 0, 0, 0, 9, 20 }
	b := NewBinaryTree[int](9)
	assert.NotNil(t, b)

	b.Insert(7)
	b.Insert(4)
	b.Insert(9)
	b.Insert(18)
	b.Insert(20)
	b.Insert(5)
	b.Insert(11)
	b.Insert(-1)
	b.Insert(33)
	b.Insert(15)
	b.Insert(13)
	slog.Info("TestBinaryMaxDepth", "maxdepth", b.MaxDepth(), "last", b.LastNode(),  "data", (*b.Binary))
}