23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // accumulative map
23dfcca431 2011-02-23        kinaba: //   basically a map<K,V>, but it eliminates duplication lazily
23dfcca431 2011-02-23        kinaba: //   first keep all inserted elements in a vector. only when the buffer
23dfcca431 2011-02-23        kinaba: //   overflows, it eliminates duplication
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: template<typename K, typename V, int LIMIT = (1<<26)/3/sizeof(pair<K,V>)>
23dfcca431 2011-02-23        kinaba: struct amap
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	typedef typename vector< pair<K,V> >::iterator iterator;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	vector< pair<K,V> > kv;
23dfcca431 2011-02-23        kinaba: 	amap() { kv.reserve(LIMIT); }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	void add(const K& k, const V& v)
23dfcca431 2011-02-23        kinaba: 	{
23dfcca431 2011-02-23        kinaba: 		kv.push_back( make_pair(k,v) );
23dfcca431 2011-02-23        kinaba: 		if( kv.size() == LIMIT )
23dfcca431 2011-02-23        kinaba: 			normalize();
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	iterator begin()       { return kv.begin(); }
23dfcca431 2011-02-23        kinaba: 	iterator end()         { return kv.end(); }
23dfcca431 2011-02-23        kinaba: 	void swap( amap& rhs ) { kv.swap(rhs.kv); }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	// Tested: SRM 469 Lv3
23dfcca431 2011-02-23        kinaba: 	void normalize()
23dfcca431 2011-02-23        kinaba: 	{
23dfcca431 2011-02-23        kinaba: 		sort(kv.begin(), kv.end());
23dfcca431 2011-02-23        kinaba: 		int i=0;
23dfcca431 2011-02-23        kinaba: 		for(int j=0; j<kv.size(); ++i)
23dfcca431 2011-02-23        kinaba: 		{
23dfcca431 2011-02-23        kinaba: 			int k = j;
23dfcca431 2011-02-23        kinaba: 			kv[i] = kv[k];
23dfcca431 2011-02-23        kinaba: 			while( ++j<kv.size() && kv[k].first==kv[j].first )
23dfcca431 2011-02-23        kinaba: 				kv[i].second += kv[j].second;
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 		kv.resize(i);
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: /*
23dfcca431 2011-02-23        kinaba: 	// Not Tested (Prefer First)
23dfcca431 2011-02-23        kinaba: 	void normalize()
23dfcca431 2011-02-23        kinaba: 	{
23dfcca431 2011-02-23        kinaba: 		sort(kv.begin(), kv.end());
23dfcca431 2011-02-23        kinaba: 		int i=0;
23dfcca431 2011-02-23        kinaba: 		for(int j=0; j<kv.size(); ++i)
23dfcca431 2011-02-23        kinaba: 		{
23dfcca431 2011-02-23        kinaba: 			int k = j;
23dfcca431 2011-02-23        kinaba: 			kv[i] = kv[k];
23dfcca431 2011-02-23        kinaba: 			while( ++j<kv.size() && kv[k].first==kv[j].first )
23dfcca431 2011-02-23        kinaba: 				{}
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 		kv.resize(i);
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	// Not Tested (Prefer Last)
23dfcca431 2011-02-23        kinaba: 	void normalize()
23dfcca431 2011-02-23        kinaba: 	{
23dfcca431 2011-02-23        kinaba: 		sort(kv.begin(), kv.end());
23dfcca431 2011-02-23        kinaba: 		int i=0;
23dfcca431 2011-02-23        kinaba: 		for(int j=0; j<kv.size(); ++i)
23dfcca431 2011-02-23        kinaba: 		{
23dfcca431 2011-02-23        kinaba: 			int k = j;
23dfcca431 2011-02-23        kinaba: 			while( ++j<kv.size() && kv[k].first==kv[j].first )
23dfcca431 2011-02-23        kinaba: 				{}
23dfcca431 2011-02-23        kinaba: 			kv[i] = kv[j-1];
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 		kv.resize(i);
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: */
23dfcca431 2011-02-23        kinaba: };