sequence.cpp

C++编写的代码

#include "Sequence.h"

using namespace std;

//------------------------------------------------------------------------
//------------------------------------------------------------------------

Sequence::Sequence(const std::string& seqStr, unsigned seqId)
{
	seqId_ = seqId;
	lastTimestamp_ = 0;
	if (seqStr.empty())
		return;

	unsigned timestamp = 1;
	
	size_t pos1, pos2;
	pos1 = 0;
	
	bool sameTsp = false; //not the same timestamp!!
	
	for (int i=0; i<seqStr.size(); ++i)
	{
		if (seqStr[i] == ',')
		{
			pos2 = i;
			
			//这里的+1是为了过滤掉前面的"I"字符，直接得到subscript属性。
			Item item(atoi(seqStr.substr(pos1+1, pos2-pos1-1).c_str()), timestamp);
			AddAnItem(item);
			if (!sameTsp)
				++timestamp;
			pos1 = i+1;
		}
		else if(seqStr[i] == '(')
		{
			sameTsp = true;
			pos1 = i+1;
		}
		else if(seqStr[i] == ')')
		{
			pos2 = i;
			Item item(atoi(seqStr.substr(pos1+1, pos2-pos1-1).c_str()), timestamp);
			AddAnItem(item);
			sameTsp = false;
			++timestamp;
			++i;
			pos1 = i+1;
		}
	}
	if (pos1 < seqStr.size())
	{		
		Item item(atoi(seqStr.substr(pos1+1, seqStr.size()-pos1-1).c_str()), timestamp);
		AddAnItem(item);
	}
	lastTimestamp_ = seq_[Length()-1].timestamp_;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
string Sequence::ToString()const
{
	if (Empty())
		return string("");
	string seqStr = "";
	int currentTsp = 1;
	bool sameTsp = false;
	for (int i=0; i<Length()-1; ++i)
	{
		if (seq_[i].timestamp_ == seq_[i+1].timestamp_)
		{
			if (!sameTsp)
				seqStr += "(";
			seqStr += seq_[i].item();
			seqStr += ",";
			sameTsp = true;
		}
		else
		{
			if (sameTsp)
			{
				seqStr += seq_[i].item();
				seqStr += "),";
				sameTsp = false;
			}
			else
			{
				seqStr += seq_[i].item();
				seqStr += ",";
			}
		}
	}
	
	seqStr += seq_[i].item();
	if (sameTsp)
	{
		seqStr += ")";
	}
	return seqStr;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
Sequence Sequence::SExtern(Item item)const
{
	Sequence resSeq = *this;
	resSeq.AddAnItem(item);
	resSeq.seq_[resSeq.Length()-1].timestamp_ = lastTimestamp_ + 1;
	++resSeq.lastTimestamp_;
	return resSeq;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
Sequence Sequence::IExtern(Item item)const
{
	Sequence resSeq = *this;
	resSeq.AddAnItem(item);
	resSeq.seq_[resSeq.Length()-1].timestamp_ = lastTimestamp_;
	return resSeq;
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
void Sequence::RemoveItem(unsigned index)
{
	assert(index<Length());	

	//index是起始点的时候
	if (index == 0)
	{
		//如果seq的长度大于1，并且紧跟着的单项和index对应的单项timestamp不同。
		if ((Length()>1)&&(seq_[index+1].timestamp_ > seq_[index].timestamp_))
		{
			for (int i=index+1;i<Length();++i)
			{
				--seq_[i].timestamp_;
			}
			lastTimestamp_ = seq_[Length()-1].timestamp_;
		}
		//如果长度等于1。
		else if (Length() == 1)
		{
			lastTimestamp_ = 0;
		}
	}
	//index是结束点的时候
	else if (index == Length()-1)
	{
		//如果序列的长度为1。
		if (Length() == 1)
		{
			lastTimestamp_ = 0;
		}
		//否则设置lastTimestamp_为倒数第二个item的timestamp。
		else
		{
			lastTimestamp_ = seq_[Length()-2].timestamp_;
		}
	}
	//index是中间点的时候，此时seq长度不可能为1，并且没有和index对应的item有相同的
	//timestamp的item。
	else if((seq_[index].timestamp_ != seq_[index-1].timestamp_)&&
		(seq_[index].timestamp_ != seq_[index+1].timestamp_))
	{
		for (int i=index+1;i<Length();++i)
		{
			--seq_[i].timestamp_;
		}
		lastTimestamp_ = seq_[Length()-1].timestamp_;
	}
	
	seq_.erase(seq_.begin()+index);
}

//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
unsigned Sequence::GetSuffixPos(const Sequence& prefix)const
{
	//如果前缀是空串，返回0。
	if (prefix.Empty())
		return 0;

	int i = 0, j = 0; //i,j分别表示本串和prefix中当前的搜索位置。
	int prePos = 0;	//prePos表示prefix中j所在transaction的起始位置。
	int currentTsp = 0;	//记录当前i所在位置的timestamp。

	while ((i < Length())&&(j < prefix.Length()))
	{
		//考虑到每个transaction中的items按照下标递增的顺序排列，
		//如果当前本串中i位置的item下标大于prefix中j位置的item下
		//标，则需要到本串的下一个transaction中搜索。
		if (seq_[i].subscript_ > prefix[j].subscript_)
		{
			currentTsp = seq_[i].timestamp_;
			while(seq_[i].timestamp_ == currentTsp)
				if(++i >= Length())
					return npos();	//此时j没有到达prefix的尾部，而i已经到达本串的尾部，故返回npos。
			//j = prePos;
		}

		//如果当前本串中i位置的item下标小于prefix中j位置的item
		//下标，递增本串的i位置。判断溢出。
		if (seq_[i].subscript_ < prefix[j].subscript_)
		{
			if (++i >= Length())
				return npos();
		}

		//如果当前本串中i位置的item下标等于prefix中j位置的item
		//下标，同时递增i和j。判断溢出。
		if (seq_[i].subscript_ == prefix[j].subscript_)
		{
			if ((++i >= Length())||(++j >= prefix.Length()))
				break;
			//如果prefix进入下一个transaction
			if (prefix[j].timestamp_ != prefix[j-1].timestamp_)
			{
				//prePos重新设置为j。
				prePos = j;

				//本串也需要进入下一个rtansaction。
				//如果没有下一个transaction，则返回npos。
				currentTsp = seq_[i-1].timestamp_;
				while(seq_[i].timestamp_ == currentTsp)
					if(++i >= Length())
						return npos();
			}
		}

		//如果发现i已经是本串中一个新的transaction的起始位置，
		//j要重置成prePos。
		if (seq_[i].timestamp_ != seq_[i-1].timestamp_)
			j = prePos;
	}//end while
	
	return (i>=Length()) ? npos() : i;
}