package buffercache

import (
	"fmt"
	"reflect"
	"testing"
)

func Test_findFirstZero64(t *testing.T) {
	tests := []struct {
		x    uint64
		want int
		ok   bool
	}{
		{x: 0b0000000000000000000000000000000000000000000000000000000000000000, want: 63, ok: true},
		{x: 0b1000000000000000000000000000000000000000000000000000000000000000, want: 62, ok: true},
		{x: 0b1111111111111111111111111111111111111111111111111111111111111111, ok: false},
		{x: 0b1111101000000000000000000000000000000000000000000000000000000000, want: 58, ok: true},
		{x: 0b1111111111111111111111111111111111111111111111111111111111111110, want: 0, ok: true},
		{x: 0b1111111111111111111111111111111111111111111111111111111111111110, want: 0, ok: true},
	}
	for _, tt := range tests {
		t.Run(fmt.Sprintf("%064b", tt.x), func(t *testing.T) {
			got, ok := findFirstZero64(tt.x)
			if !ok {
				if tt.ok {
					t.Errorf("findFirstZero64(%064b) = %v, want %v", tt.x, ok, tt.ok)
				}
				return
			}
			if got != tt.want {
				t.Errorf("findFirstZero64(%064b) = %v, want %v", tt.x, got, tt.want)
			}
		})
	}
}

func TestBitMap_leadingZeros(t *testing.T) {
	tests := []struct {
		bm   []uint64
		want int
		ok   bool
	}{
		{
			bm: []uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			},
			want: 63,
			ok:   true,
		},
		{
			bm: []uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			},
			want: 63 + 64,
			ok:   true,
		},
		{
			bm: []uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111100000000000000000000000000000000000000000000000000000000,
			},
			want: 128 + 55,
			ok:   true,
		},
		{
			bm: []uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111110,
			},
			want: 128,
			ok:   true,
		},
		{
			bm: []uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
			},
			want: 0,
			ok:   false,
		},
	}
	for _, tt := range tests {
		t.Run(fmt.Sprintf("%064b", tt.bm), func(t *testing.T) {
			t.Run(fmt.Sprintf("%064b", tt.bm), func(t *testing.T) {
				bm := bitmap(tt.bm)
				got, ok := bm.findFreeCell()
				if !ok {
					if tt.ok {
						t.Errorf("bitMap.leadingZeros(%064b) = %v, want %v", tt.bm, ok, tt.ok)
					}
					return
				}
				if got != tt.want {
					t.Errorf("bitMap.leadingZeros(%064b) = %v, want %v", tt.bm, got, tt.want)
				}
			})
		})
	}
}

func Test_bitmap_setBit(t *testing.T) {
	tests := []struct {
		bm    bitmap
		index int
		want  bitmap
		panic bool
	}{
		{
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
			index: 0,
			want: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000001,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
			index: 64,
			want: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000001,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
			index: 127,
			want: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b1000000000000000000000000000000000000000000000000000000000000000,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
			index: 63,
			want: bitmap([]uint64{
				0b1000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
			index: 64 + 33,
			want: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000001000000000000000000000000000000000,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000001000000000000000000000000000000000,
			}),
			index: 64 + 33,
			want: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000001000000000000000000000000000000000,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
			index: 128,
			panic: true,
		},
	}
	for _, tt := range tests {
		t.Run(fmt.Sprintf("%064b", tt.bm), func(t *testing.T) {
			if tt.panic {
				defer func() {
					if r := recover(); r == nil {
						t.Errorf("got no panic, want panic")
					}
				}()
			}
			tt.bm.setBit(tt.index)
			if !reflect.DeepEqual(tt.bm, tt.want) {
				t.Errorf("got: %064b, want: %064b", tt.bm, tt.want)
			}
		})
	}
}

func Test_bitmap_clearBit(t *testing.T) {
	tests := []struct {
		name  string
		bm    bitmap
		index int
		want  bitmap
		panic bool
	}{
		{
			bm: bitmap([]uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
			}),
			index: 63,
			want: bitmap([]uint64{
				0b0111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
			}),
			index: 64,
			want: bitmap([]uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111110,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
			}),
			index: 0,
			want: bitmap([]uint64{
				0b1111111111111111111111111111111111111111111111111111111111111110,
				0b1111111111111111111111111111111111111111111111111111111111111111,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
			}),
			index: 127,
			want: bitmap([]uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b0111111111111111111111111111111111111111111111111111111111111111,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
			}),
			index: 64 + 18,
			want: bitmap([]uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111110111111111111111111,
			}),
		},
		{
			bm: bitmap([]uint64{
				0b1111111111111111111111111111111111111111111111111111111111111111,
				0b1111111111111111111111111111111111111111111111111111111111111111,
			}),
			index: 128,
			panic: true,
		},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			if tt.panic {
				defer func() {
					if r := recover(); r == nil {
						t.Errorf("want panic, got nothing")
					}
				}()
			}
			tt.bm.clearBit(tt.index)
			if !reflect.DeepEqual(tt.bm, tt.want) {
				t.Errorf("got: %064b, want: %064b", tt.bm, tt.want)
			}
		})
	}
}

func Test_bitmap_getBit(t *testing.T) {
	tests := []struct {
		name  string
		bm    bitmap
		index int
		want  uint64
	}{
		{
			name: "empty",
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
			index: 0,
			want:  0,
		},
		{
			name: "first bit",
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000001,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
			index: 0,
			want:  1,
		},
		{
			name: "second bit",
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000010,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
			index: 1,
			want:  1,
		},
		{
			name: "first bit of second slice",
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000001,
			}),
			index: 64,
			want:  1,
		},
		{
			name: "last bit of 1st slice",
			bm: bitmap([]uint64{
				0b1000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000000000000000000000000000000000,
			}),
			index: 63,
			want:  1,
		},
		{
			name: "random bit",
			bm: bitmap([]uint64{
				0b0000000000000000000000000000000000000000000000000000000000000000,
				0b0000000000000000000000000000000000010000000000000000000000000000,
			}),
			index: 64 + 28,
			want:  1,
		},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			got := tt.bm.bit(tt.index)
			if got != tt.want {
				t.Errorf("got: %d, want: %d", got, tt.want)
			}
		})
	}
}

// getBit is mainly used for testing purposes
func (bm *bitmap) bit(i int) uint64 {
	index := i / 64
	bit := i % 64

	return ((*bm)[index] & (1 << bit)) >> bit
}
