blob: bed94250dc2829249e7e397167dba04b687df28c [file] [log] [blame]
// Copyright (C) 2015 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package atom
import (
"reflect"
"testing"
)
func check(t *testing.T, name string, expected, got uint64) {
if expected != got {
t.Errorf("%s was not as expected.\nExpected: %d\nGot: %d", name, expected, got)
}
}
// Root-group
// │
// ├─ [0..99] ───── Atoms[0..99]
// │
// ├─ [100] ─────── Sub-group 0
// │ │
// │ └─ [0..99] ── Atoms[100..199]
// │
// ├─ [101..200] ── Atoms[200..299]
// │
// ├─ [201] ─────── Sub-group 1
// │ │
// │ ├─ [0..39] ── Atoms[300..339]
// │ │
// │ ├─ [40] ───── Sub-group 0
// │ │ │
// │ │ └─ [0..19] Atoms[340..359]
// │ │
// │ └─ [41..81] ─ Atoms[360..399]
// │
// ├─ [202..301] ── Atoms[400..499]
// │
// ├─ [302] ─────── Sub-group 2
// │ │
// │ └─ [0..100) ─ Atoms[500..599]
// │
// └─ [303..9702] ─ Atoms[600..9999]
//
func buildTestGroup() Group {
return Group{
Range: Range{Start: 0, End: 10000},
SubGroups: GroupList{
Group{Range: Range{Start: 100, End: 200}},
Group{
Range: Range{Start: 300, End: 400},
SubGroups: GroupList{
Group{Range: Range{Start: 340, End: 360}},
},
},
Group{Range: Range{Start: 500, End: 600}},
},
}
}
func TestGroupCount(t *testing.T) {
root := buildTestGroup()
check(t, "root count", 10000-300+3, root.Count())
check(t, "sub group 0 count", 100, root.SubGroups[0].Count())
check(t, "sub group 1 count", 40+1+40, root.SubGroups[1].Count())
check(t, "sub group 1's sub group count", 20, root.SubGroups[1].SubGroups[0].Count())
check(t, "sub group 2 count", 100, root.SubGroups[2].Count())
}
func TestGroupIndex(t *testing.T) {
root := buildTestGroup()
for _, test := range []struct {
index uint64
expectedBaseAtomID ID
expectedSubGroup *Group
}{
{0, 0, nil},
{1, 1, nil},
{50, 50, nil},
{100, 100, &root.SubGroups[0]},
{101, 200, nil},
{102, 201, nil},
{151, 250, nil},
{200, 299, nil},
{201, 300, &root.SubGroups[1]},
{202, 400, nil},
{203, 401, nil},
{252, 450, nil},
{301, 499, nil},
{302, 500, &root.SubGroups[2]},
{303, 600, nil},
{304, 601, nil},
{353, 650, nil},
{402, 699, nil},
} {
gotBaseAtomID, gotSubGroup := root.Index(test.index)
if test.expectedBaseAtomID != gotBaseAtomID {
t.Errorf("base atom id was not as expected for index %d.\nExpected: %d\nGot: %d",
test.index, test.expectedBaseAtomID, gotBaseAtomID)
}
if test.expectedSubGroup != gotSubGroup {
t.Errorf("sub group was not as expected for index %d.\nExpected: %+v\nGot: %+v",
test.index, test.expectedSubGroup, gotSubGroup)
}
}
}
func TestGroupIndexOf(t *testing.T) {
root := buildTestGroup()
for _, test := range []struct {
atomID ID
expected uint64
}{
{0, 0},
{1, 1},
{50, 50},
{100, 100},
{101, 100},
{150, 100},
{199, 100},
{200, 101},
{201, 102},
{250, 151},
{299, 200},
{300, 201},
{301, 201},
{350, 201},
{399, 201},
{400, 202},
{401, 203},
{450, 252},
{499, 301},
{500, 302},
{501, 302},
{550, 302},
{599, 302},
{600, 303},
{601, 304},
{650, 353},
{699, 402},
} {
got := root.IndexOf(test.atomID)
if test.expected != got {
t.Errorf("IndexOf(%d) returned unexpected atom id.\nExpected: %+v\nGot: %+v",
test.atomID, test.expected, got)
}
}
}
func TestGroupAddTopDown(t *testing.T) {
root := Group{}
root.Range = Range{Start: 0, End: 1000}
root.SubGroups.Add(0, 1000, "R")
root.SubGroups.Add(100, 200, "A0")
root.SubGroups.Add(300, 400, "B0")
root.SubGroups.Add(500, 600, "C0")
root.SubGroups.Add(120, 180, "A1")
root.SubGroups.Add(310, 390, "B1")
root.SubGroups.Add(500, 600, "C1")
root.SubGroups.Add(140, 160, "A2")
root.SubGroups.Add(320, 380, "B2")
root.SubGroups.Add(500, 600, "C2")
expected := Group{
Range: Range{Start: 0, End: 1000},
SubGroups: GroupList{
Group{
Range: Range{Start: 0, End: 1000},
Name: "R",
SubGroups: GroupList{
Group{
Range: Range{Start: 100, End: 200},
Name: "A0",
SubGroups: GroupList{
Group{
Range: Range{Start: 120, End: 180},
Name: "A1",
SubGroups: GroupList{
Group{
Range: Range{Start: 140, End: 160},
Name: "A2",
},
},
},
},
},
Group{
Range: Range{Start: 300, End: 400},
Name: "B0",
SubGroups: GroupList{
Group{
Range: Range{Start: 310, End: 390},
Name: "B1",
SubGroups: GroupList{
Group{
Range: Range{Start: 320, End: 380},
Name: "B2",
},
},
},
},
},
Group{
Range: Range{Start: 500, End: 600},
Name: "C0",
SubGroups: GroupList{
Group{
Range: Range{Start: 500, End: 600},
Name: "C1",
SubGroups: GroupList{
Group{
Range: Range{Start: 500, End: 600},
Name: "C2",
},
},
},
},
},
},
},
},
}
if !reflect.DeepEqual(expected, root) {
t.Errorf("built group was not as expected.\nExpected: %+v\nGot: %+v",
expected, root)
}
}
func TestGroupAddBottomUp(t *testing.T) {
root := Group{}
root.Range = Range{Start: 0, End: 1000}
root.SubGroups.Add(140, 160, "A2")
root.SubGroups.Add(320, 380, "B2")
root.SubGroups.Add(500, 600, "C2")
root.SubGroups.Add(120, 180, "A1")
root.SubGroups.Add(310, 390, "B1")
root.SubGroups.Add(500, 600, "C1")
root.SubGroups.Add(100, 200, "A0")
root.SubGroups.Add(300, 400, "B0")
root.SubGroups.Add(500, 600, "C0")
root.SubGroups.Add(0, 1000, "R")
expected := Group{
Range: Range{Start: 0, End: 1000},
SubGroups: GroupList{
Group{
Range: Range{Start: 0, End: 1000},
Name: "R",
SubGroups: GroupList{
Group{
Range: Range{Start: 100, End: 200},
Name: "A0",
SubGroups: GroupList{
Group{
Range: Range{Start: 120, End: 180},
Name: "A1",
SubGroups: GroupList{
Group{
Range: Range{Start: 140, End: 160},
Name: "A2",
},
},
},
},
},
Group{
Range: Range{Start: 300, End: 400},
Name: "B0",
SubGroups: GroupList{
Group{
Range: Range{Start: 310, End: 390},
Name: "B1",
SubGroups: GroupList{
Group{
Range: Range{Start: 320, End: 380},
Name: "B2",
},
},
},
},
},
Group{
Range: Range{Start: 500, End: 600},
Name: "C2",
SubGroups: GroupList{
Group{
Range: Range{Start: 500, End: 600},
Name: "C1",
SubGroups: GroupList{
Group{
Range: Range{Start: 500, End: 600},
Name: "C0",
},
},
},
},
},
},
},
},
}
if !reflect.DeepEqual(expected, root) {
t.Errorf("built group was not as expected.\nExpected: %+v\nGot: %+v",
expected, root)
}
}
func TestGroupAddMixed(t *testing.T) {
root := Group{}
root.Range = Range{Start: 0, End: 1000}
root.SubGroups.Add(100, 500, "A")
root.SubGroups.Add(400, 500, "C")
root.SubGroups.Add(200, 500, "B")
expected := Group{
Range: Range{Start: 0, End: 1000},
SubGroups: GroupList{
Group{
Range: Range{Start: 100, End: 500},
Name: "A",
SubGroups: GroupList{
Group{
Range: Range{Start: 200, End: 500},
Name: "B",
SubGroups: GroupList{
Group{
Range: Range{Start: 400, End: 500},
Name: "C",
},
},
},
},
},
},
}
if !reflect.DeepEqual(expected, root) {
t.Errorf("built group was not as expected.\nExpected: %+v\nGot: %+v",
expected, root)
}
}