void Print(LinkStack<unsigned>& st)
{
    LinkStack<int>  tmp;
    while (st.size() > 0) {
       tmp.push(st.top());
       cout << tmp.top() << " ";
       st.pop();
    } cout << endl;

    while (tmp.size() > 0) {
       st.push(tmp.top());
       tmp.pop();
    }
}

void  NumSelector(unsigned arr[], int len, unsigned k, int b, LinkStack<unsigned>& st)
{
    /* -1 标志每次是否重新选择,大树 */
    int i = (b==-1) ? 0 : b;
    while (i < len) {
        unsigned e = arr[i];
        if ( (0 < e) && (e <= k) ) {
            st.push(e);

            if (k == e) {
                Print(st);
            } else {
                NumSelector(arr, len, k-e, (b==-1) ? 0 : i+1, st);
            }

            st.pop();
        }

        i++;
    }
}

void  BST(BTree<int>& tr, int e)
{
    if ( NULL == tr.root() ) {
        tr.insert(e, NULL, ANY);
    } else if ( e > tr.root()->value ) {
        BST(*(dynamic_cast< BTree<int>* >(tr.root()->left)), e);
    } else {
        BST(*(dynamic_cast< BTree<int>* >(tr.root()->right)), e);
    }

    return ;
}


/**
小偷有一个可承受 m 重量的背包，他潜入一户人家，发现有 n 件物品，第 i 个物
品的价值为 vi ，重量为 wi 。小偷要如何选择物品带走，使其总价值最大？
**/
struct Sth : public Object
{
    int vi, wi;

    Sth()
    {

    }

    Sth(int v, int w) : vi(v), wi(w)
    {

    }

    bool operator ==(const Sth& obj) const
    {
        return ((this->vi && obj.vi) && (this->wi == obj.wi));
    }

    bool operator !=(const Sth& obj) const
    {
        return !(*this == obj);
    }

};

void  StackCopy(LinkStack<Sth>& s1, LinkStack<Sth>& s2)
{
    LinkStack<Sth> tmp;
    while (s1.size() > 0) {
        s2.push(s1.top());
        tmp.push(s1.top());
        s1.pop();
    }

    while (tmp.size() > 0) {
        s1.push(tmp.top());
        tmp.pop();
    }
}

void  choose(Sth all[], int packM, int begin, int end, LinkStack< Sth >&  st, LinkStack< Sth >& ret, Sth& cur, Sth& max )
{
    /* 无限纵深求解 or 求解任选数目 问题 */
    if ( begin <= end  ) {
        for (int i=(-1 == begin ? 0 : begin); i<=end; i++) {
            st.push(all[i]);
            cur.vi += all[i].vi;
            cur.wi += all[i].wi;

            if ( ( cur.vi > max.vi ) && (cur.wi <= packM) ) {
                max = cur;
                ret.clear();
                StackCopy(st, ret);
            }

            if  (cur.wi < packM) {
                choose(all, packM, (-1 == begin ? begin : i+1), end, st, ret, cur, max);
            }

            cur.vi -= all[i].vi;
            cur.wi -= all[i].wi;
            st.pop();

        }

    }
}

void choose()
{
    Sth cur(0, 0);
    Sth max(0, 0);
    LinkStack<Sth>  st1, st2;

    Sth all[] = {Sth(6, 5), Sth(2, 1), Sth(4, 2), Sth(4, 3), Sth(5, 4)};
    int len   = sizeof all / sizeof all[0];

    choose(all, 6, -1, len-1, st1, st2, cur, max);

    cout << max.vi << ", " << max.wi << endl;
    while (st2.size() > 0) {
        cout << "< " << st2.top().vi << "," << st2.top().wi << " > ";
        st2.pop();
    } cout << endl;
}

bool IsVaild(const KString s)
{
    return ( (s == "0") || ( (s[0] != '0') && (atoi(s.str()) <= 255) ) ) ;
}

void MakeIPAddr(const KString& str, int cur_char, LinkList<KString>& cur_ip, LinkList<KString>& ret)
{
    /* 字符刚好用完，且当前的分割可能构成合法的IP */
    if ( (cur_char == str.length()) && (cur_ip.length() == 4) ) {
        KString ip_str;
        for (cur_ip.move(0); !cur_ip.end(); cur_ip.next()) {
            ip_str += cur_ip.current();
            ip_str += ".";
        } ip_str.remove(ip_str.length()-1, 1);

        ret.insert(ip_str);

    } else if ( cur_char < str.length() ) { // 双剪枝
        KString tmp = "";
        KString cur = "";

        /* 计算最近的分段字符串 */
        int pos = (cur_ip.length() ? cur_ip.length()-1 : 0);

        cur_ip.get(pos, tmp);
        cur = tmp + str[cur_char];

        /* 合法则将当前归入之后的数字串更新旧的字符串 */
        if ( IsVaild(cur) && cur_ip.set(pos, cur) ) {
            MakeIPAddr(str, cur_char+1, cur_ip, ret);
            /*
             * 重新选择，新起一个段，处理下一个字符
             * 剪枝选择：当前开新段应当在分段小于4前提下,不允许5枝条
             */
            cur_ip.set(pos, tmp);
        }

        /* 考虑将当前字符新开一个分段，但是在开启之前先判定是否可以再开，最多开到4，剪去多余的枝叶 */
        if ( (cur_ip.length() < 4) && ( cur_ip.insert(str[cur_char])) ) {
            /* 处理完当前之后继续恢复原状 */
            MakeIPAddr(str, cur_char+1, cur_ip, ret);
            cur_ip.remove(cur_ip.length()-1);

        }

    }
}

void MakeIPAddr()
{
    LinkList<KString> ret;
    LinkList<KString> cur_ip;

    MakeIPAddr("192168322", 0, cur_ip, ret);

    for (ret.move(0); !ret.end(); ret.next()) {
        cout << ret.current().str() << endl;
    }

}