Line data    Source code

       1              : // Copyright (c) 2022 The Authors. All rights reserved.
       2              : //
       3              : // Licensed under the Apache License, Version 2.0 (the "License");
       4              : // you may not use this file except in compliance with the License.
       5              : // You may obtain a copy of the License at
       6              : //
       7              : //      https://www.apache.org/licenses/LICENSE-2.0
       8              : //
       9              : // Unless required by applicable law or agreed to in writing, software
      10              : // distributed under the License is distributed on an "AS IS" BASIS,
      11              : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12              : // See the License for the specific language governing permissions and
      13              : // limitations under the License.
      14              : 
      15              : // Authors: liubang (it.liubang@gmail.com)
      16              : // Created: 2022/01/17 14:50
      17              : 
      18              : #include <gtest/gtest.h>
      19              : 
      20              : #include <iostream>
      21              : #include <vector>
      22              : 
      23              : namespace {
      24              : class NestedInteger {
      25              : public:
      26            8 :     NestedInteger(int value) : value_(value), is_integer_(true) {}
      27              : 
      28            1 :     NestedInteger(const std::vector<NestedInteger>& list) : is_integer_(false), list_(list) {}
      29              : 
      30            3 :     NestedInteger(const std::vector<int>& ints) {
      31            8 :         for (int i : ints) {
      32            5 :             list_.emplace_back(i);
      33              :         }
      34            3 :         is_integer_ = false;
      35            3 :     }
      36              : 
      37            3 :     NestedInteger(const NestedInteger&) = default;
      38              :     NestedInteger& operator=(const NestedInteger&) = default;
      39            7 :     NestedInteger(NestedInteger&&) = default;
      40              : 
      41           12 :     bool isInteger() const { return is_integer_; }
      42              : 
      43            8 :     int getInteger() const { return value_; }
      44              : 
      45            4 :     const std::vector<NestedInteger>& getList() const { return list_; }
      46              : 
      47              : private:
      48              :     int value_{0};
      49              :     bool is_integer_{true};
      50              :     std::vector<NestedInteger> list_;
      51              : };
      52              : 
      53              : class NestedIterator {
      54              : public:
      55            2 :     NestedIterator(const std::vector<NestedInteger>& nestedList) { visit(nestedList); }
      56              : 
      57            8 :     int next() { return list_[idx_++]; }
      58              : 
      59           10 :     bool hasNext() { return idx_ < list_.size(); }
      60              : 
      61              : private:
      62            6 :     void visit(const std::vector<NestedInteger>& nestedList) {
      63           18 :         for (auto& nestedInteger : nestedList) {
      64           12 :             if (nestedInteger.isInteger()) {
      65            8 :                 list_.push_back(nestedInteger.getInteger());
      66              :             } else {
      67            4 :                 visit(nestedInteger.getList());
      68              :             }
      69              :         }
      70            6 :     }
      71              : 
      72              : private:
      73              :     std::vector<int> list_;
      74              :     int idx_{0};
      75              : };
      76              : } // namespace
      77              : 
      78            4 : TEST(Leetcode, flatten_nested_list_iterator) {
      79              :     {
      80              :         // [[1,1],2,[1,1]]
      81            1 :         std::vector<NestedInteger> inputs;
      82            1 :         std::vector<int> output;
      83            1 :         std::vector<int> exp = {1, 1, 2, 1, 1};
      84            1 :         inputs.emplace_back(std::vector<int>{1, 1});
      85            1 :         inputs.emplace_back(2);
      86            1 :         inputs.emplace_back(std::vector<int>{1, 1});
      87              : 
      88            1 :         NestedIterator it(inputs);
      89            6 :         while (it.hasNext()) {
      90            5 :             output.push_back(it.next());
      91              :         }
      92            1 :         EXPECT_EQ(exp, output);
      93            1 :     }
      94              : 
      95              :     {
      96              :         // [1,[4,[6]]]
      97            1 :         std::vector<NestedInteger> inputs;
      98            1 :         std::vector<int> output;
      99            1 :         std::vector<int> exp = {1, 4, 6};
     100            1 :         inputs.emplace_back(1);
     101              : 
     102            1 :         std::vector<NestedInteger> inner;
     103            1 :         inner.emplace_back(4);
     104            1 :         inner.emplace_back(std::vector<int>{6});
     105            1 :         inputs.emplace_back(inner);
     106              : 
     107            1 :         NestedIterator it(inputs);
     108            4 :         while (it.hasNext()) {
     109            3 :             output.push_back(it.next());
     110              :         }
     111            1 :         EXPECT_EQ(exp, output);
     112            1 :     }
     113            1 : }