// SortedChain.h: interface for the SortedChain class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_SORTEDCHAIN_H__68536A56_5C90_4A8D_977B_6E97554174D1__INCLUDED_)
#define AFX_SORTEDCHAIN_H__68536A56_5C90_4A8D_977B_6E97554174D1__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

template<class E,class K>
class SortedChainNode{
	public:
		E data;
		SortedChainNode<E,K>* link;
};

template<class E,class K>
class SortedChain  
{
public:
	SortedChain(){first=0;}
	~SortedChain(){
		SortedChainNode<E,K>* p;
		while(first){
		p=first->link;
		delete first;
		first=p;
		}
	}


	bool IsEmpty(){return first==0;}
//	int Length();
	bool Search(const K& k,E& e){
		SortedChainNode<E,K>* p=first;
		for(;p&&p->data<k;p=p->link);
		if(p&&p->data==k){
			e=p->data;
			return true;
		}
		return false;
	}

	SortedChain<E,K>& DistinctInsert( E& e);
private:
	SortedChainNode<E,K>* first;

};
template<class E,class K>
SortedChain<E,K>& SortedChain<E,K>::DistinctInsert( E& e){
		SortedChainNode<E,K>* p=first,*tp=0;
		for(;p&&p->data<e;tp=p,p=p->link);
		if(p&&p->data==e) return *this;
		SortedChainNode<E,K>* q=new SortedChainNode<E,K>;
		q->data=e;
		q->link=p;
		if(tp) tp->link=p;
		else first=q;
		return *this;
	}

#endif // !defined(AFX_SORTEDCHAIN_H__68536A56_5C90_4A8D_977B_6E97554174D1__INCLUDED_)