cc/gapic/interval_list_test.cpp

/*
 * 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.
 */

#include "interval_list.h"

#include <gmock/gmock.h>
#include <gtest/gtest.h>

using ::testing::ElementsAreArray;

namespace gapic {

template <typename T>
::std::ostream& operator<<(::std::ostream& os, const Interval<T>& interval) {
    return os << "[" << interval.start << " - " << interval.end-1 << "]";
}

template <typename T>
::std::ostream& operator<<(::std::ostream& os, const IntervalList<T>& l) {
    os << "IntervalList{";
    for (auto i : l) {
        os << i;
    }
    return os << "}";
}

namespace test {

Interval<int> I(int first, int last) {
    return Interval<int>{first, last + 1};
}


class IntervalListTest : public ::testing::Test, public IntervalList<int> {
public:
    inline IntervalList<int>& L() {
        return *static_cast<IntervalList<int>*>(this);
    }
};

TEST_F(IntervalListTest, Empty) {
    EXPECT_EQ(count(), 0);
    EXPECT_EQ(begin(), end());
}

TEST_F(IntervalListTest, SingleMerge) {
    merge(I(1, 2));
    EXPECT_THAT(L(), ElementsAreArray({I(1, 2)}));
}

TEST_F(IntervalListTest, MergeSparseForward) {
    merge(I(1, 2));
    merge(I(4, 5));
    merge(I(7, 8));
    EXPECT_THAT(L(), ElementsAreArray({I(1, 2), I(4, 5), I(7, 8)}));
}

TEST_F(IntervalListTest, MergeSparseReverse) {
    merge(I(7, 8));
    merge(I(4, 5));
    merge(I(1, 2));
    EXPECT_THAT(L(), ElementsAreArray({I(1, 2), I(4, 5), I(7, 8)}));
}

//   0   1   2   3   4   5   6   7   8   9   A   B   C   D   E
//  -----------------------------------------------------------
//          ╭         ╮             ╭     ╮     ╭     ╮
//          │    0    │             │  1  │     │  2  │
//          ╰         ╯             ╰     ╯     ╰     ╯
//  -----------------------------------------------------------
//  ╭ ╮ ╭ ╮     ╭ ╮     ╭ ╮     ╭     ╮ ╭         ╮ ╭     ╮ ╭ ╮
//  │a│ │b│     │c│     │d│     │  e  │ │    f    │ │  g  │ │h│
//  ╰ ╯ ╰ ╯     ╰ ╯     ╰ ╯     ╰     ╯ ╰         ╯ ╰     ╯ ╰ ╯
//      ╭                 ╮         ╭                 ╮
//      │        i        │         │        j        │
//      ╰                 ╯         ╰                 ╯
//  ╭                                                         ╮
//  │                            k                            │
//  ╰                                                         ╯
auto a = I(0x0, 0x0);
auto b = I(0x1, 0x1);
auto c = I(0x3, 0x3);
auto d = I(0x5, 0x5);
auto e = I(0x7, 0x8);
auto f = I(0x9, 0xb);
auto g = I(0xc, 0xd);
auto h = I(0xe, 0xe);
auto i = I(0x1, 0x5);
auto j = I(0x8, 0xc);
auto k = I(0x0, 0xe);

TEST_F(IntervalListTest, Merge) {
    struct test {
        const char*                name;
        Interval<int>              interval;
        std::vector<Interval<int>> expected;
    };
    for (auto t : {
        test{"a", a, { I(0x0, 0x0), I(0x2, 0x4), I(0x8, 0x9), I(0xb, 0xc) } },
        test{"b", b, { I(0x1, 0x4), I(0x8, 0x9), I(0xb, 0xc) } },
        test{"c", c, { I(0x2, 0x4), I(0x8, 0x9), I(0xb, 0xc) } },
        test{"d", d, { I(0x2, 0x5), I(0x8, 0x9), I(0xb, 0xc) } },
        test{"e", e, { I(0x2, 0x4), I(0x7, 0x9), I(0xb, 0xc) } },
        test{"f", f, { I(0x2, 0x4), I(0x8, 0xc) } },
        test{"g", g, { I(0x2, 0x4), I(0x8, 0x9), I(0xb, 0xd) } },
        test{"h", h, { I(0x2, 0x4), I(0x8, 0x9), I(0xb, 0xc), I(0xe, 0xe) } },
        test{"i", i, { I(0x1, 0x5), I(0x8, 0x9), I(0xb, 0xc) } },
        test{"j", j, { I(0x2, 0x4), I(0x8, 0xc) } },
        test{"k", k, { I(0x0, 0xe) } },
    }) {
        clear();
        merge(I(0x2, 0x4)); // 0
        merge(I(0x8, 0x9)); // 1
        merge(I(0xb, 0xc)); // 2

        merge(t.interval);

        EXPECT_THAT(L(), ElementsAreArray(t.expected));
    }
}

TEST_F(IntervalListTest, MergeStartEnd) {
    merge(I(0x2, 0x4)); // 0
    merge(I(0x8, 0x9)); // 1
    merge(I(0xb, 0xc)); // 2

    struct test {
        const char*   name;
        Interval<int> interval;
        int           start;
        int           end;
    };
    for (auto t : {
        test{"a", a, 0, -1},
        test{"b", b, 0, 0},
        test{"c", c, 0, 0},
        test{"d", d, 0, 0},
        test{"e", e, 1, 1},
        test{"f", f, 1, 2},
        test{"g", g, 2, 2},
        test{"h", h, 3, 2},
        test{"i", i, 0, 0},
        test{"j", j, 1, 2},
        test{"k", k, 0, 2},
    }) {
        size_t s = mergeStart(t.interval);
        size_t e = mergeEnd(t.interval);
        if (t.start != s) {
            ADD_FAILURE() << t.name << ": l.mergeStart(" << t.interval << ") "
                    "returned " << s << ", expected " << t.start;
        }
        if (t.end != e) {
            ADD_FAILURE() << t.name << ": l.mergeEnd(" << t.interval << ") "
                    "returned " << e << ", expected " << t.end;
        }
    }
}

} // namespace test
} // namespace gapic