迷途知返

#ifndef _ARRAY_H_
#define _ARRAY_H_
#include <map>
#include <vector>
#include <cmath>
#define ARRAY_TEMP template <class T1, class T2>
#define ARRAY_T1S vector<T1>
#define ARRAY_T2S vector<T2>
#define ARRAY_MIT typename map<T1,T2>::const_iterator
#define ARRAY_vint typename ARRAY_T2S::size_type
#define ARRAY_for for(ARRAY_vint i=0; i<ks.size(); i++)
using namespace std;
 
enum SORTOPT {SORT_ASC, SORT_DESC};
 
ARRAY_TEMP class Array{
private:
    map<T1,T2> m;
    ARRAY_T1S ks;                                  //mark the order of keys of array
    int get_index(const int &);                    //get_index, parameter can be negtive number
                                                //range: [-size(),size()), -1=size()-1 
public:
    Array();                                    //constructor
    Array(const ARRAY_T2S &);                    //constructor, T1 must be int, keys will be 0,1,2,...
    Array(const map<T1,T2> &);                    //use map to construct an Array
    Array(const ARRAY_T1S &, const ARRAY_T2S &);//keys and values
    Array(const Array<T1,T2> &);                //use Array to construct an Array
    Array(const int &, const T2 &);                //T1 must be int, fill Array with n values
    void print_r();                                // print the array
    ARRAY_T1S keys();                            // get the keys
    ARRAY_T2S values();                            // get the values
    pair<T1,T2> front();                        // get the first key-value pair
    pair<T1,T2> back();                            // get the last
    unsigned size();                            // get the length of the Array
    bool empty();                                // tell if this Array is empty
    void clear();                                // clear this Array
    void push_back(const pair<T1,T2> &);        // add a new element with pair at the end of the Array
    void push_back(const T1 &, const T2 &);     // add a new element with a single key and value at the end of the Array
    void push_front(const pair<T1,T2> &);        // add a new element with pair at the front of the Array 
    void push_front(const T1 &, const T2 &);     // add a new element with a key and value at the front of the Array
    pair<T1,T2> pop_back();                        // erase the last pair, and return it
    pair<T1,T2> pop_front();                    // erase the first pair, and return it
    void insert(const int &, const pair<T1,T2> &);        // insert a pair at a subscript
    void insert(const int &, const T1 &, const T2 &);    // insert an element with key and value at a subscript
    void insert(const int &, map<T1,T2> &);        // insert a map at a subscript
    void insert(const int &, Array<T1,T2> &);    // insert an Array at a subscript
    T2 &operator[](const T1 &);                    // write or read a value by key
    T2 &at(const int &);                        // read a value at subscript(cannot write)
    pair<T1,T2> pair_at(const int &);            // read a pair at subscript
    T1 key_at(const int &);                        // get key at subscript
    T2 value_at(const int &);                    // get value at subscript
    bool key_exists(const T1 &);                // tell if a key exists
    bool value_exists(const T2 &);                // tell if a value exists
    bool pair_exists(const pair<T1,T2> &);        // tell if a pair exists
    bool operator==(Array<T1,T2> &);            // tell if this Array is equal to another
    bool operator!=(Array<T1,T2> &);            // tell if this Array is not equal to another
    ARRAY_T1S keys_of(const T2 &);                // get the keys of a value
    int index_of_key(const T1 &);                // get the subscript of a key
    int index_of_pair(const pair<T1,T2> &);        // get the subscript of a pair
    vector<int> indices_of_value(const T2 &);    // get the indices of a value
    void erase_at(const int &, const unsigned &len = 1); // erase elements from subscript to subscript+len
    void erase_by_key(const T1 &);                // erase element by key
    void erase_by_value(const T2 &);            // erase ELEMENTS by value
    void erase_by_pair(const pair<T1,T2> &);    // erase element by pair
    void erase(const pair<T1,T2> &);            // reload erase_by_pair
    void erase(const int &, const unsigned &len = 1); // reload erase_at
    Array<T1,T2> operator+(Array<T1,T2> &);        // return an Array = *this + another Array
    Array<T1,T2> operator+(map<T1,T2> &);        // return an Array = *this + a map
    Array<T1,T2> operator+(const pair<T1,T2> &);// return an Array = *this + a pair
    Array<T1,T2> &operator+=(Array<T1,T2> &);    // add another Array to *this
    Array<T1,T2> &operator+=(map<T1,T2> &);        // add a map to *this
    Array<T1,T2> &operator+=(const pair<T1,T2> &); // add a pair to *this
    Array< int,Array<T1,T2> > chunk(const unsigned &); // split this Array to Arrays by a given length
    Array<T1,T2> sub(const int &);                // return a part of this Array from subscript to end
    Array<T1,T2> sub(const int &, const unsigned &); // return a part of this Array from subscript to subscript+length
    Array<T1,T2> slice(const int &);            // reload sub
    Array<T1,T2> slice(const int &, const unsigned &); // reload sub
    Array<T1,T2> combine(Array<T1,T2> &);        // the same as operator+
    Array<T1,T2> merge(Array<T1,T2> &);            // combine
    Array<T2,int> count_values();                // count the values
    Array<T2,T1> flip();                        // change keys to values and values to keys
    Array<T1,T2> unique();                        // delete duplicated values
    Array<T1,T2> mapfun(T2 (*)(T2));            // map a function to each value
    Array<T1,T2> mapfun(pair<T1,T2> (*)(pair<T1,T2>)); // map a function to each pair
    Array<T1,T2> sort_by_keys(const SORTOPT &opt = SORT_ASC); // sort the elements by keys
    Array<T1,T2> sort_by_values(const SORTOPT &opt = SORT_ASC);    // sort the elements by values
    Array<T1,T2> reverse();                        // reverse the Array
    pair<T1,T2> random();                        // get a random pair of the Array
    Array<T1,T2> shuffle();                        // randomly sort the Array
    Array<T1,T2> splice(const int &, const unsigned &, const map<T1,T2> &); // replace a part of elements with a map
    Array<T1,T2> splice(const int &, const unsigned &, const Array<T1,T2> &); // replace a part of elements with an Array
};
 
ARRAY_TEMP Array<T1,T2>::Array(){ }
 
ARRAY_TEMP Array<T1,T2>::Array(const ARRAY_T2S &v2){
    unsigned n = v2.size();
    for(ARRAY_vint i=0; i<n; i++){
        ks.push_back(i);
        m[(T1)i] = v2[i];
    }
}
 
ARRAY_TEMP Array<T1,T2>::Array(const map<T1,T2> &mp){
    for(ARRAY_MIT it = mp.begin(); it!=mp.end(); it++){ks.push_back(it->first);}
    m = mp;
}
 
ARRAY_TEMP Array<T1,T2>::Array(const vector<T1> &v1, const vector<T2> &v2){
    unsigned n = v1.size()>v2.size()?v2.size():v1.size();
    ks = v1;
    for(ARRAY_vint i=0; i<n; i++){m[ks[i]] = v2[i];}
}
 
ARRAY_TEMP Array<T1,T2>::Array(const Array<T1,T2> &a){ks = a.ks; m = a.m;}
 
ARRAY_TEMP Array<T1,T2>::Array(const int &len, const T2 &value){
    for(int i=0; i<len; i++){ ks.push_back((T1)i); m[(T1)i] = value; }
}
 
ARRAY_TEMP int Array<T1,T2>::get_index(const int &index){
    if( index<-(int)ks.size()||index>=(int)ks.size() ){ 
        cerr << "Array<T1,T2>: index:" << index << " out of range:" << ks.size() << endl;
        exit(1); 
    }
    return index>=0?index:ks.size()+index;
}
 
//!!!!!!be cautious!!!!!
//use it when T1,T2 can be cout ed!
ARRAY_TEMP void Array<T1,T2>::print_r(){
    cout << "ARRAY {" << endl;
    ARRAY_for{
        cout << "t[" << i << "] " << ks[i] << " => " 
             << m[ks[i]] << " ," << endl;
    }
    cout << "}" << endl;
}
 
ARRAY_TEMP ARRAY_T1S Array<T1,T2>::keys(){return ks;}
 
ARRAY_TEMP ARRAY_T2S Array<T1,T2>::values(){
    ARRAY_T2S vs;
    ARRAY_for{vs.push_back(m[ks[i]]);}
    return vs;
}
 
ARRAY_TEMP pair<T1,T2> Array<T1,T2>::front(){return pair<T1,T2>(ks[0],m[ks[0]]);}
 
ARRAY_TEMP pair<T1,T2> Array<T1,T2>::back(){return make_pair(ks[ks.size()-1],m[ks[ks.size()-1]]);}
 
ARRAY_TEMP unsigned Array<T1,T2>::size(){return ks.size();}
 
ARRAY_TEMP bool Array<T1,T2>::empty(){return ks.size()==0;}
 
ARRAY_TEMP void Array<T1,T2>::clear(){ks.clear();m.erase(m.begin(),m.end());}
 
ARRAY_TEMP void Array<T1,T2>::push_back(const pair<T1,T2> &p){    
    m[p.first] = p.second; 
    if(!key_exists(p.first)) ks.push_back(p.first);
}
 
ARRAY_TEMP void Array<T1,T2>::push_back(const T1 &key, const T2 &value){
    m[key] = value; 
    if(!key_exists(key)) ks.push_back(key);
}
 
ARRAY_TEMP void Array<T1,T2>::push_front(const pair<T1,T2> &p){
    m[p.first] = p.second; 
    if(!key_exists(p.first)) ks.push_front(p.first);
}
 
ARRAY_TEMP void Array<T1,T2>::push_front(const T1 &key, const T2 &value){
    m[key] = value; 
    if(!key_exists(key)) ks.push_front(key);
}
 
ARRAY_TEMP pair<T1,T2> Array<T1,T2>::pop_back(){
    pair<T1,T2> p = back();
    ks.pop_back();
    m.erase(p.first);
    return p;
}
 
ARRAY_TEMP pair<T1,T2> Array<T1,T2>::pop_front(){
    pair<T1,T2> p = front();
    for(ARRAY_vint i=0; i<ks.size()-1; i++){ks[i] = ks[i+1];}
    ks.pop_back();
    m.erase(p.first);
    return p;
}
 
ARRAY_TEMP void Array<T1,T2>::insert(const int &at, const pair<T1,T2> &p){
    m[p.first] = p.second;
    if(key_exists(p.first)) return;
    int i = get_index(at);
    typename ARRAY_T1S::iterator it = find(ks.begin(),ks.end(),ks[i]);
    ks.insert(it,p.first);    
}
 
ARRAY_TEMP void Array<T1,T2>::insert(const int &at, const T1 &k, const T2 &v){
    m[k] = v;
    if(key_exists(k)) return;
    int i = get_index(at);
    typename ARRAY_T1S::iterator it = find(ks.begin(),ks.end(),ks[i]);
    ks.insert(it,k);
}
 
ARRAY_TEMP void Array<T1,T2>::insert(const int &at, map<T1,T2> &mp){
    typename ARRAY_T1S::iterator itks = (at==(int)ks.size())?ks.end():find(ks.begin(),ks.end(),ks[get_index(at)]);
    ARRAY_T1S ksmp;
    for(ARRAY_MIT it=mp.begin(); it!=mp.end(); it++) ksmp.push_back(it->first);
    ARRAY_vint s = ksmp.size();    
    for(ARRAY_vint i=0; i<s; i++){
        typename ARRAY_T1S::iterator vit =  find(ks.begin(),ks.end(),ksmp[i]);
        if(vit!=ks.end()) ksmp.erase(vit); 
        m[ksmp[i]] = mp[ksmp[i]];
    }
    ks.insert(itks,ksmp.begin(),ksmp.end());
}
 
ARRAY_TEMP void Array<T1,T2>::insert(const int &at, Array<T1,T2> &a){insert(at,a.m);}    
 
ARRAY_TEMP T2 &Array<T1,T2>::operator[](const T1 &key){
    if(!key_exists(key)) ks.push_back(key);
    return m[key];
}
 
ARRAY_TEMP T2 &Array<T1,T2>::at(const int &index){
    int p = get_index(index);
    return m[ks[p]];
}
 
ARRAY_TEMP pair<T1,T2> Array<T1,T2>::pair_at(const int &index){
    int p = get_index(index);
    return make_pair(ks[p],m[ks[p]]);
}
 
ARRAY_TEMP T1 Array<T1,T2>::key_at(const int &index){return ks[get_index(index)];}
 
ARRAY_TEMP T2 Array<T1,T2>::value_at(const int &index){return at(get_index(index));}
 
ARRAY_TEMP bool Array<T1,T2>::key_exists(const T1 &k){return find(ks.begin(),ks.end(),k)!=ks.end();}
 
ARRAY_TEMP bool Array<T1,T2>::value_exists(const T2 &k){
    ARRAY_T2S vs = values();
    typename ARRAY_T2S::iterator it = find(vs.begin(),vs.end(),k);
    return it!=vs.end();
}
 
ARRAY_TEMP bool Array<T1,T2>::pair_exists(const pair<T1,T2> &p){
    if(!key_exists(p.first)) return false;
    if( m[p.first]!=p.second ) return false;
    return true;
}
 
ARRAY_TEMP bool Array<T1,T2>::operator==(Array<T1,T2> &a){
    if( a.ks.size()!= ks.size()) return false;
    ARRAY_for{ if( ks[i]!=a.ks[i] || at(i)!=a.at(i) ){ cout << "i:"<<i <<endl;return false; }}
    return true;
}
 
ARRAY_TEMP bool Array<T1,T2>::operator!=(Array<T1,T2> &a){return !(*this==a);}
 
ARRAY_TEMP ARRAY_T1S Array<T1,T2>::keys_of(const T2 &value){
    ARRAY_T1S aks;
    ARRAY_for{ if( m[ks[i]]==value ) aks.push_back(ks[i]); }
    return aks;
}
 
ARRAY_TEMP int Array<T1,T2>::index_of_key(const T1 &key){
    if(!key_exists(key)) return -1;
    ARRAY_for{ if( ks[i]==key ) return i; }
}
 
ARRAY_TEMP int Array<T1,T2>::index_of_pair(const pair<T1,T2> &p){
    if(!pair_exists(p)) return -1;
    return index_of_key(p.first);
}
 
ARRAY_TEMP vector<int> Array<T1,T2>::indices_of_value(const T2 &value){
    vector<int> a;
    ARRAY_for{ if( m[ks[i]]==value ) a.push_back(i); }
    return a;
}
 
ARRAY_TEMP void Array<T1,T2>::erase_at(const int &index, const unsigned &len){
    print_r();
    int p = get_index(index), s = p+len>=(int)ks.size()?(int)ks.size():(p+len);
    for(int i=p; i<s; i++){
        m.erase(ks[p]);
        ks.erase(find(ks.begin(),ks.end(),ks[p]));
    }
}
 
ARRAY_TEMP void Array<T1,T2>::erase_by_key(const T1 &key){
    m.erase(key);
    ks.erase(find(ks.begin(),ks.end(),key));
}
 
ARRAY_TEMP void Array<T1,T2>::erase_by_value(const T2 &value){
    ARRAY_T1S ekeys = keys_of(value);
    for(ARRAY_vint i=0; i<ekeys.size(); i++){
        m.erase(ekeys[i]);
        ks.erase(find(ks.begin(),ks.end(),ekeys[i]));
    }
}
 
ARRAY_TEMP void Array<T1,T2>::erase_by_pair(const pair<T1,T2> &p){
    if(!pair_exists(p)) return;
    erase_by_key(p.first);
}
 
ARRAY_TEMP void Array<T1,T2>::erase(const pair<T1,T2> &p){erase_by_pair(p);}
 
ARRAY_TEMP void Array<T1,T2>::erase(const int &index, const unsigned &len){erase_at(index,len);}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::operator+(Array<T1,T2> &a){return *this + a.m;}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::operator+(map<T1,T2> &mp){
    Array<T1,T2> b = *this;
    b.insert(ks.size(),mp);
    return b;
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::operator+(const pair<T1,T2> &p){
    Array<T1,T2> b = *this;
    b.push_back(p);
    return b;
}
 
ARRAY_TEMP Array<T1,T2> &Array<T1,T2>::operator+=(Array<T1,T2> &a){*this = *this + a; return *this;}
 
ARRAY_TEMP Array<T1,T2> &Array<T1,T2>::operator+=(map<T1,T2> &mp){*this = *this + mp; return *this;}
 
ARRAY_TEMP Array<T1,T2> &Array<T1,T2>::operator+=(const pair<T1,T2> &p){*this = *this + p; return *this;}
 
ARRAY_TEMP Array< int,Array<T1,T2> > Array<T1,T2>::chunk(const unsigned &len){
    Array< int,Array<T1,T2> > aa;
    Array<T1,T2> a;
    ARRAY_for{
        a += pair_at(i);
        if( (i+1)%len==0 || i==ks.size()-1 ){ aa += make_pair(aa.size(),a); a.clear(); }
    }
    return aa;
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::sub(const int &i, const unsigned &l){
    Array<T1,T2> a;
    int p = get_index(i);
    for(ARRAY_vint x=i; x<i+l; x++){a += pair_at(x);}
    return a;
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::sub(const int &i){return sub(i,ks.size()-i);}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::slice(const int &i, const unsigned &l){return sub(i,l);}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::slice(const int &i){return sub(i);}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::combine(Array<T1,T2> &a){return *this + a;}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::merge(Array<T1,T2> &a){return *this + a;}
 
ARRAY_TEMP Array<T2,int> Array<T1,T2>::count_values(){
    Array<T2,int> result;
    ARRAY_for{
        if(result.key_exists(m[ks[i]])) result[m[ks[i]]] = result[m[ks[i]]] + 1;
        else result[m[ks[i]]] = 1;
    }
    return result;
}
 
ARRAY_TEMP Array<T2,T1> Array<T1,T2>::flip(){
    Array<T2,T1> a;
    ARRAY_for{a.push_back(m[ks[i]],ks[i]);}
    return a;
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::unique(){
    Array<T1,T2> a;
    ARRAY_for{ if(!a.value_exists(at(i))) a+=pair_at(i); }
    return a;
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::mapfun(T2 (*f)(T2)){
    Array<T1,T2> a;
    ARRAY_for{    a[ks[i]] = (*f)(m[ks[i]]);}
    return a;
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::mapfun(pair<T1,T2> (*f)(pair<T1,T2>)){
    Array<T1,T2> a;
    ARRAY_for{    a += (*f)(pair_at(i));}
    return a;
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::sort_by_keys(const SORTOPT &opt){
    Array<T1,T2> a = *this;
    if( opt==SORT_ASC )    sort(a.ks.begin(), a.ks.end());
    else sort(a.ks.begin(), a.ks.end(), greater<T1>());
    return a;
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::sort_by_values(const SORTOPT &opt){
    Array<T1,T2> a = *this;
    ARRAY_T2S vs = values();
    if( opt==SORT_ASC )    sort(vs.begin(), vs.end());
    else sort(vs.begin(), vs.end(), greater<T1>());
    a.ks.clear();
    for(ARRAY_vint i=0; i<vs.size(); i++){
        ARRAY_T1S ksof = keys_of(vs[i]);
        for(ARRAY_vint j=0; j<ksof.size(); j++){
            a.ks.push_back(ksof[j]);
        }
    }
    return a;
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::reverse(){    
    Array<T1,T2> a;
    for(int i=ks.size()-1; i>=0; i--){ a += pair_at(i); }
    return a;
}
 
ARRAY_TEMP pair<T1,T2> Array<T1,T2>::random(){
    srand(time(NULL));
    return pair_at( rand()%ks.size() );
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::shuffle(){
    Array<T1,T2> a, b = *this;
    while(!b.empty()){
        pair<T1,T2> p = b.random();
        a += p;
        b.erase(p);
    }
    return a;    
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::splice(const int &at, const unsigned &len, const map<T1,T2> &mp){
    Array<T1,T2> a = *this;
    int p = get_index(at);
    a.erase(p,len);
    a.insert(at,mp);
    return a;
}
 
ARRAY_TEMP Array<T1,T2> Array<T1,T2>::splice(const int &at, const unsigned &len, const Array<T1,T2> &a){
    return splice(at,len,a.m);
}
 
#endif