struct Node : public Object
{
    int value;
    Node* pre, * next;

    Node(int val=0) : value(val), pre(NULL), next(NULL)
    {

    }
};

void MergeStep(Node*& slider, Node*& node)
{
    slider->next = node;
    node->pre    = slider;
    node   = node->next;   //优化内容：自动将结点指针更新至下一结点
    slider = slider->next;
}

Node* ListMerge(Node* left, Node* right)
{
    /* 双向链表合并操作技巧，附设一个头结点然后以头结点作为新链表头结点 */
    Node  head;
    Node* ret    = &head;
    Node* slider = ret;

    right = (left == right) ? NULL : right;
    while( left && right ) {
        if( left->value <= right->value ) {
            MergeStep(slider, left);
            // left = left->next;
        } else {
            MergeStep(slider, right);
            // right = right->next;
        }
    }

    while( left ) MergeStep(slider, left);

    while( right ) MergeStep(slider, right);

    ret = ret->next;
    if( ret ) {
        ret->pre = NULL;
    }

    return ret;
}

void  SplitList(Node* list, Node*& left, Node*& right)
{
    if ( NULL != list ) {
        Node* p1 = list;
        Node* p2 = list;

        while( NULL != p2 )
        {
            p2 = p2->next;
            p2 = p2 ? (p1 = p1->next, p2->next) : NULL;
        }

        left  = list;
        right = p1;

        p1 = p1->pre;

        if( NULL != p1 ) {
            p1->next = NULL;
        }

        right->pre = NULL;
    }
}


Node* MergeSort(Node* list)
{
    Node* ret  = NULL;
    if ( NULL != list ) {
        if ( NULL == list->next ) {
            ret = list;
        } else {
            Node* left  = NULL;
            Node* right = NULL;
            SplitList(list, left, right);

            ret = ListMerge(MergeSort(left), MergeSort(right));
        }
    }

    return ret;
}


void  StackLinkSort(Stack<int>& st, Node* prev)
{
    if (st.size() > 0) {
        Node node(st.top());
        node.pre = prev;

        if ( NULL != prev ) {
            prev->next = &node;
        }

        st.pop();
        StackLinkSort(st, &node);

    } else if ( NULL != prev ) {
        /* stak is null */
        while (prev->pre) {
            prev = prev->pre;

        }

        Node* ret = MergeSort(prev);

        while ( NULL != ret ) {
            /*st.push(ret->value);*/
            cout << ret->value << " ";
            ret = ret->next;
        }

    }
}

void StackSort()
{
    int a[] = {8, 3, 2, 1, 5, 6, 7, 0, 4, 9};
    int len = sizeof(a)/sizeof(a[0]);
    LinkStack<int> stack;

    for(int i=0; i<len; i++)
    {
        stack.push(a[i]);
    }

    // StackSort1(stack);
    StackLinkSort(stack, NULL);

//    while( stack.size() )
//    {
//        cout << stack.top() << " ";
//        stack.pop();
//    }

    cout << endl;
}

Node* ListStart(Node* front)
{
    Node* ret = NULL;
    if ( (NULL == front) || (NULL == front->pre ) ) {
        ret = front;
    } else {
        ret = ListStart(front->pre);
    }

    return ret;
}

void  ListToStack(Node* start, Stack<int>& st)
{
    if ( start ) {
        st.push(start->value);
        ListToStack( start->next, st);
    }
}

void  StackReverseByList(Stack<int>& st, Node* prev)
{
    if (st.size() > 0) {
        Node node(st.top());
        node.pre = prev;

        if ( NULL != prev ) {
            prev->next = &node;
        }

        st.pop();
        StackReverseByList(st, &node);

    } else if ( NULL != prev ) {
        ListToStack(ListStart(prev), st);
    }
}


void  StackReverse()
{
    int a[] = {8, 3, 2, 1, 5, 6, 7, 0, 4, 9};
    int len = sizeof(a)/sizeof(a[0]);
    LinkStack<int> stack;

    for(int i=0; i<len; i++)
    {
        stack.push(a[i]);
    }

    StackReverseByList(stack, NULL);
    StackReverseByList(stack, NULL);


    while( stack.size() )
    {
        cout << stack.top() << " ";
        stack.pop();
    }
}

void CoutStack(Stack<int>& stack)
{
    while( stack.size() )
    {
        cout << stack.top() << " ";
        stack.pop();
    }
}

void PlaneBoom()
{
    int plan[] = {1, -2, 3, 5, -2, 9, -2};
    int len    = sizeof plan / sizeof *plan;

    LinkStack<int>  res;

    for (int i=0; i<len; i++) {
        while ( (i < len) && res.size() && ( (res.top() > 0) && (plan[i] < 0) ) ) {
           int living = res.top() + plan[i];
           if ( living < 0 ) {
               res.pop();

           } else if ( living > 0 ) {
               i++;

           } else {
               res.pop();
               i++;

           }
        }

        if (i < len) {
            res.push(plan[i]);
        }

    }
    StackReverseByList(res, NULL);
    CoutStack(res);


}

int MinStack(LinkStack<int> pStack[], int len)  // O(k)
{
    int min = 0xFFFF;
    int ret = -1;

    for(int i=0; (i<len) && pStack; i++)
    {
        if( pStack[i].size() && (pStack[i].top() < min) )
        {
            min = pStack[i].top();
            ret = i;
        }
    }

    return ret;
}

int EnterStack(LinkStack<int> pStack[], int len, int total, int index) // O(k)
{
    int ret = -1;
    int min = 0xFFFF;

    for(int i=0; pStack && (i<len); i++)
    {
        if( pStack[i].size() )
        {
            if( (index < pStack[i].top()) && (pStack[i].top() < min) )
            {
                min = pStack[i].top();
                ret = i;
            }
        }
        else if( ret == -1 )
        {
            ret = i;
        }
    }

    if( (ret == -1) && (len < total))
    {
        ret = len;
    }

    if( ret != -1 )
    {
        cout << index << " enter into stack[" << ret << "]." << endl;
        pStack[ret].push(index);
    }

    return ret;
}

void StackToExit(LinkStack<int> pStack[], int len, Queue<int>& result) // O(k*k)
{
    int min = 0xFFFF;
    int msi = 0;

    while( (msi != -1) && pStack )
    {
        min = 0xFFFF;
        msi = -1;

        for(int i=0; i<len; i++)
        {
            if( pStack[i].size() && (pStack[i].top() < min) )
            {
                min = pStack[i].top();
                msi = i;
            }
        }

        if( msi != -1 )
        {
            int index = pStack[msi].top();

            cout << index << " from stack[" << msi << "] to exit." << endl;

            result.add(index);

            pStack[msi].pop();
        }
    }
}