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