| // 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) |
| } |
| } |