Vote Sort 多条队伍的合并

为了解决多个队伍合并，并且不产生顺序错误 （由于同一个元素可出现在多个队伍中，但是不在同一个队伍中出现） 代码如下（请注意此代码为GPL版权）

/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
 * vote_sort.h
 * Copyright (C) cch@srdgame 2008
 *
 * main.cc is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * main.cc is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program. If not, see <
 */
#include <set>
#include <list>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;

namespace VoteSort
{

typedef vector< vector< string> > Queues;
typedef set<string> Node;
typedef map< string, Node > NodeMap;
void display_map(NodeMap& map);
void create_node(const Queues& deps, Queues::const_iterator ptr, vector<string>::const_iterator q_ptr, Node& node)
{
    //copy(q_ptr, ptr->end(), back_insert_iterator >(node.second.first));

    for (; q_ptr != ptr->end(); ++q_ptr)
    {
        node.insert(node.end(), *q_ptr);
    }
}

void prepare_vote(const Queues& deps, NodeMap& map, vector<string>& ref)
{
    Queues::const_iterator ptr = deps.begin();
    for (; ptr != deps.end(); ++ptr)
    {
        vector<string>::const_iterator q_ptr = ptr->begin();    
        for (; q_ptr != ptr->end(); ++q_ptr)
        {
            if (find(ref.begin(), ref.end(), *q_ptr) == ref.end())
            {
                ref.push_back(*q_ptr);
            }
            create_node(deps, ptr, q_ptr, map[*q_ptr]);
        }
    }
}

template<class T>
class RefComp : public std::binary_function<T, T, bool>
{
    const vector<T>& _ref;
public:
    RefComp(const vector<T>& ref) : _ref(ref)
    {
    }
    bool operator()(const T& a, const T& b)
    {
        //cerr << "Compare " << a << " with " << b << endl;

        return (find(_ref.begin(), _ref.end(), a) - _ref.begin()) > (find(_ref.begin(), _ref.end(), b) - _ref.begin());
    }
};

void vote_loop_inner(NodeMap& map, const vector<string>& ref, list<string>& result)
{
    NodeMap::iterator ptr = map.begin();
    vector<string> voted;
    string tmp;
    for(; ptr != map.end(); ++ptr)
    {
        if (ptr->second.size() != 1)
        {
            continue;
        }
        if (ptr->second.size() == 1)
        {
            tmp = ptr->first;
            voted.push_back(tmp);
            --ptr;
            map.erase(tmp);
        }
        if (map.empty())
        {
            break;
        }
    }
    /*
    cerr << "voted size is " << voted.size() << endl;
    for (int i = 0; i < voted.size(); ++i)
    {
        cerr << voted[i] << "\t";
    }
    cerr << endl;*/
    if (voted.empty())
    {
        cerr << "ERROR FOUND " << endl;
        return;
    }

    for(ptr = map.begin(); ptr != map.end(); ++ptr)
    {
        /*
        set u_set;
        set r_set;
        set_union(ptr->second.begin(), ptr->second.end(), voted.begin(), voted.end(), inserter(u_set, u_set.end()));
        set_difference(ptr->second.begin(), ptr->second.end(), u_set.begin(), u_set.end(), inserter(r_set, r_set.end()));
        ptr->second = r_set;
        */
        for (int i = 0; i < voted.size(); ++i)
        {
            ptr->second.erase(voted[i]);
        }
    }

    sort(voted.begin(), voted.end(), RefComp<string>(ref));
    vector<string>::iterator v_ptr = voted.begin();
    for (; v_ptr != voted.end(); ++v_ptr)
    {
        result.push_front(*v_ptr);
    }
    if(!map.empty())
    {
        display_map(map);
        vote_loop_inner(map, ref, result);
    }
    return;
}

list<string> vote_loop(const NodeMap& map, const vector<string>& ref)
{
    NodeMap new_map(map);
    list<string> result;
    vote_loop_inner(new_map, ref, result);
    return result;
}
void display_map(NodeMap& map)
{
    return;
    cout << "=================================================================" << endl;
    for( NodeMap::iterator ptr = map.begin(); ptr != map.end(); ++ptr)
    {
        cout << "name:\t" << ptr->first << endl;
        cout << "list:\t";
        set<string>::iterator v_ptr = ptr->second.begin();
        for (; v_ptr != ptr->second.end(); ++v_ptr)
        {
            cout << *v_ptr << "\t";
        }
        cout << endl;

        cout << "=================================================================" << endl;
        //mans.erase(mans.begin());

    }
}
list<string> Sort(Queues deps, vector<string> circle)
{
    list<string> order;
    vector<string> ref;
    NodeMap mans;

    // Prepare our own data.

    prepare_vote(deps, mans, ref);
    for (int i = 0; i < ref.size(); ++i)
    {
        cerr << ref[i] << "\t";
    }
    cerr << endl;
    display_map(mans);

    cout << "Start to vote .... " << endl;
    order = vote_loop(mans, ref);
    return order;
}

}

/* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
/*
 * main.cpp
 * Copyright (C) cch@srdgame 2008
 *
 * main.cc is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * main.cc is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program. If not, see <
 */
#include <iostream>
#include <list>
#include <map>
#include <vector>
#include <string>

#include "./vote_sort.h"

using namespace std;
using namespace VoteSort;
void get_queues(Queues& q)
{
    vector<string> tlist;
    string in;
    while (true)
    {
        cout << "Input every item for this list, input \"ok\" to end of input" << endl;
        while (true)
        {
            cin >> in;
            if ("end" == in || "ok" == in)
                break;
            tlist.push_back(in);
        }
        if ("end" == in && !tlist.empty())
        {
            q.push_back(tlist);
            tlist.clear();
            in = "";
            continue;
        }
        if ("ok" == in)
        {
            break;
        }
    }
}
void display_list(list<string>& order, vector<string>& tlist)
{
    list<string>::const_iterator ptr = order.begin();
    for (; ptr != order.end(); ++ptr)
    {
        cout << *ptr << "\t";
    }
    cout << endl;
    if (!tlist.empty())
    {
        cout << "THE CIRCLE IS:" << endl;
        for(int i = 0; i < tlist.size(); ++i)
        {
            cout << tlist[i] << "\t";
        }
        cout << endl;
    }
}
void s_sort(Queues q)
{
    vector<string> order;
    Queues::iterator ptr = q.begin();
    for (; ptr != q.end(); ++ptr)
    {
        vector<string>::iterator q_ptr = ptr->begin();
        for (; q_ptr != ptr->end(); ++ q_ptr)
        {
            if (order.end() == find(order.begin(), order.end(), *q_ptr))
            {
                cout << *q_ptr << "\t";
                order.push_back(*q_ptr);
            }
        }
    }
    Queues::reverse_iterator r_ptr = q.rbegin();
    for (; r_ptr != q.rend(); ++r_ptr)
    {
        sort(order.begin(), order.end(), RefComp<string>(*r_ptr));
    }
    for (int i = 0; i < order.size(); i++)
    {
        cout << order[i] << "\t";
    }
    cout << endl;
}
int main()
{
    Queues q;
    get_queues(q);
    Queues q2(q);
    cout << "================================================================" << endl;
    cout << "THE ORDER IS:" << endl;

    list<string> order ;
    vector<string> tlist;
    order = VoteSort::Sort(q, tlist);
    display_list(order, tlist);

    cout << "****************************************************************" << endl;
//    s_sort(q2);

}