Saturday, June 6, 2015

Deep iterator, Nested Lists

Print {1, {2,3}, {4,{5,6},7} with the interfaces hasNext and getNext.

Analysis:

             {1, {2,3}, {4,{5,6},7}
                /              |             \
              1            {2,3}     {4,{5,6},
                            /     \           /   \
                          2        3      4    {5,6}
                                                   /    \
                                                  5     6

Note, there are two types of nodes. One is actual number, the other is a list

As shown above, the problem can be solved by pre order traverse the tree. Simply, we can record the current index of a sub list to know which element should be visited.



class ListNode
{
public:
    std::vector<ListNode*> v;
    int val;
    //curIndex points the element to visit in v, if v is not empty
    //else curIndex == 0 means val is not visited yet.
    int curIndex;

    bool hasNext(){
        if(!v.empty())
        {
            if(curIndex >= v.size()) 
                return false;
            if(!v[curIndex]->hasNext() 
                && curIndex+1 >= v.size())
            {
                return false;
            }
            return true;
        }
        //if the element is visited, curIndex is 1.
        return curIndex == 0;
    }
    int getNext(){
        if(!v.empty())
        {
            if(!v[curIndex]->hasNext()) curIndex++;
            return v[curIndex]->getNext();
        }
        curIndex++;
        return val;
    }
    ListNode(int p){
        curIndex = 0;
        val = p;
    }
};

int main()
{
    ListNode l0(-11), l2(-11), l3(-11), l32(-11);
    ListNode n1(1),n2(2), n3(3),n4(4), n5(5),n6(6),n7(7);

    l32.v.push_back(&n5);
    l32.v.push_back(&n6);

    l3.v.push_back(&n4);
    l3.v.push_back(&l32);
    l3.v.push_back(&n7);

    l2.v.push_back(&n2);
    l2.v.push_back(&n3);

    l0.v.push_back(&n1);
    l0.v.push_back(&l2);
    l0.v.push_back(&l3);

    while(l0.hasNext())
    {
        std::cout << l0.getNext() << "\n";
    }
}