(t *testing.T)
| 17 | } |
| 18 | |
| 19 | func TestSegmentTree(t *testing.T) { |
| 20 | var segmentTreeTestData = []struct { |
| 21 | description string |
| 22 | array []int |
| 23 | updates []update |
| 24 | queries []query |
| 25 | expected []int |
| 26 | }{ |
| 27 | { |
| 28 | description: "test empty array", |
| 29 | array: []int{}, |
| 30 | queries: []query{{0, 0}}, |
| 31 | expected: []int{0}, |
| 32 | }, |
| 33 | { |
| 34 | description: "test array with size 5", |
| 35 | array: []int{1, 2, 3, 4, 5}, |
| 36 | queries: []query{{0, 5}, {0, 2}, {2, 4}}, |
| 37 | expected: []int{15, 6, 12}, |
| 38 | }, |
| 39 | { |
| 40 | description: "test array with size 5 and updates", |
| 41 | array: []int{1, 2, 3, 4, 5}, |
| 42 | updates: []update{{firstIndex: 1, lastIndex: 1, value: 2}, |
| 43 | {firstIndex: 2, lastIndex: 2, value: 3}}, |
| 44 | queries: []query{{0, 5}, {0, 2}, {2, 4}}, |
| 45 | expected: []int{20, 11, 15}, |
| 46 | }, |
| 47 | { |
| 48 | description: "test array with size 5 and single index updates", |
| 49 | array: []int{1, 2, 3, 4, 5}, |
| 50 | updates: []update{{firstIndex: 1, lastIndex: 1, value: 2}, |
| 51 | {firstIndex: 2, lastIndex: 2, value: 3}}, |
| 52 | queries: []query{{0, 5}, {0, 2}, {2, 4}}, |
| 53 | expected: []int{20, 11, 15}, |
| 54 | }, |
| 55 | { |
| 56 | description: "test array with size 5 and range updates", |
| 57 | array: []int{1, 2, 3, 4, 5}, |
| 58 | updates: []update{{firstIndex: 0, lastIndex: 4, value: 2}, |
| 59 | {firstIndex: 2, lastIndex: 4, value: 2}}, |
| 60 | queries: []query{{0, 5}, {0, 2}, {2, 4}}, |
| 61 | expected: []int{31, 14, 24}, |
| 62 | }, |
| 63 | { |
| 64 | description: "test array with size 11 and range updates", |
| 65 | array: []int{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, |
| 66 | updates: []update{{firstIndex: 2, lastIndex: 8, value: 2}, |
| 67 | {firstIndex: 2, lastIndex: 8, value: 2}}, |
| 68 | queries: []query{{3, 5}, {7, 8}, {4, 5}, {8, 8}}, |
| 69 | expected: []int{15, 10, 10, 5}, |
| 70 | }, |
| 71 | } |
| 72 | for _, test := range segmentTreeTestData { |
| 73 | t.Run(test.description, func(t *testing.T) { |
| 74 | segmentTree := NewSegmentTree(test.array) |
| 75 | |
| 76 | for i := 0; i < len(test.updates); i++ { |
nothing calls this directly
no test coverage detected