/////////////////////////////////////////////////////////////////////
//
// LLIST.H
//
// class Node;																| _prev, _next
// template<class T> class ListNode : public Node;							| _val	
// template<class T> class List;											| header, win, _length
// template<class T> class Stack											| push, pop
// template<class T> class TreeNode;										| _lchild, _rchild, val
// template<class T> class BraidedNode : public Node, public TreeNode<T>;
// template<class T> class RandomizedNode : public BraidedNode<T>;			| _parent,_priority
// template<class T> class SearchTree;										| root, fnCmp
// template<class T> class BraidedSearchTree								| root, win, fnCmp
// template<class T> class RandomizedSearchTree;							| root, win, fnCmp
// template<class T> List<T> *arrayToList(T a[], int n);
// template<class T> T leastItem(List<T> &s, int (*cmp)(T,T) );
//
// RomaNets Text Windows Library (RTWL)
//
// version 0.60
//
// Michael J.Laszlo
// Sergey RomaNets
//
// -------------------------------------------------------------------
// added length() to RandomizedSearchTree
// added empty()  to List
// -------------------------------------------------------------------



#ifndef _LLIST_H_
#define _LLIST_H_

#define Dictionary RandomizedSearchTree
//*
typedef int bool;
#define true 1
#define false 0
//*/

////////////////////////////////////////////////////////////
class Node
{
protected:
	Node* _next;
	Node* _prev;

public:
	Node(void);
	virtual ~Node(void);
	Node* next(void);
	Node* prev(void);
	Node* insert(Node*);
	Node* remove(void);
	void splice(Node*);
};

////////////////////////////////////////////////////////////
template<class T> class ListNode : public Node
{
	public:
		T _val;
		ListNode( T val);
		friend class List<T>;
};

////////////////////////////////////////////////////////////
template<class T> class List
{
	private:
		ListNode<T> *header;
		ListNode<T> *win;
		int _length;
	
	public:
		List (void);
		~List (void);
		T insert(T);
		T append(T);
		List<T>* append(List<T>* l);
		T prepend(T);
		T remove(void);
		void empty(void);
		void val(T);
		T val(void);
		T next(void);
		T prev(void);
		T first(void);
		T last(void);
		int length(void);
		bool isFirst(void);
		bool isLast(void);
		bool isHead(void);
};

////////////////////////////////////////////////////////////
template<class T> class Stack
{
	private:
		List<T> *s;
	public:
		Stack(void);
		~Stack(void);
		void push(T v);
		T pop(void);
		bool empty(void);
		int size(void);
		T top(void);
		T nextToTop(void);
		T bottom(void);
};

////////////////////////////////////////////////////////////
template<class T> class TreeNode
{
	protected:
		TreeNode *_lchild;
		TreeNode *_rchild;
		T val;
	public:
		TreeNode(T);
		virtual ~TreeNode(void);
		friend class SearchTree<T>;
		friend class BraidedSearchTree<T>;
};

////////////////////////////////////////////////////////////
template<class T> class SearchTree
{
	private:
		TreeNode<T> *root;
		int (*cmp)(T,T);
		TreeNode<T>* _findMin( TreeNode<T> *);
		void _remove(T, TreeNode<T> * &);
		void _inorder(TreeNode<T>*, void (*)(T));
	
	public:
		SearchTree(int(*c)(T,T));
		~SearchTree(void);
		int isEmpty(void);
		T find(T);
		T findMin(void);
		void inorder(void(*visit)(T));
		void insert(T);
		void remove(T);
		T removeMin(void);
};

/////////////////////////////////////////////////////////////////////
template<class T> class BraidedNode : public Node, public TreeNode<T>
{
	public:
		BraidedNode (T);
		BraidedNode<T> *rchild(void);
		BraidedNode<T> *lchild(void);
		BraidedNode<T> *next(void);
		BraidedNode<T> *prev(void);
		friend class BraidedSearchTree<T>;
};

/////////////////////////////////////////////////////////////////////
template<class T> class BraidedSearchTree
{
	private:
		BraidedNode<T> *root;
		BraidedNode<T> *win;
		int (*cmp) (T,T);
		void _remove( T, TreeNode<T>* &);
	public:
		BraidedSearchTree(int(*) (T,T));
		~BraidedSearchTree(void);
		T next(void);
		T prev(void);
		void inorder(void(*) (T));
		T val(void);
		bool isFirst(void);
		bool isLast(void);
		bool isHead(void);
		bool isEmpty(void);
		T find(T);
		T findMin(void);
		T insert(T);
		void remove(void);
		T removeMin(void);
};

////////////////////////////////////////////////////////////
template<class T> class RandomizedNode : public BraidedNode<T>
{
	protected:
		RandomizedNode *_parent;
		double _priority;
		void rotateRight(void);
		void rotateLeft(void);
		void bubbleUp(void);
		void bubbleDown(void);
	public:
		RandomizedNode( T v, int seed = -1);
		RandomizedNode *lchild(void);
		RandomizedNode *rchild(void);
		RandomizedNode *next(void);
		RandomizedNode *prev(void);
		RandomizedNode *parent(void);
		double priority(void);
		friend class RandomizedSearchTree<T>;
};

////////////////////////////////////////////////////////////
template<class T> class RandomizedSearchTree
{
	private:
		RandomizedNode<T> *root;
		RandomizedNode<T> *win;
		int _length;
		int (*cmp)(T,T);
		void _remove(RandomizedNode<T>*);
	public:
		RandomizedSearchTree(int(*)(T,T), int = -1);
		~RandomizedSearchTree(void);
		T next(void);
		T prev(void);
		void inorder(void(*)(T));
		T val (void);
		bool isFirst(void);
		bool isLast(void);
		bool isHead(void);
		bool isEmpty(void);
		T find(T);
		T findMin(void);
		T locate(T);
		T insert(T);
		void remove(void);
		T remove(T);
		T removeMin(void);
		int length(void) { return _length;}
};

// .........................................................
template<class T> ListNode<T>::ListNode(T val) :
	_val(val)
{
}

// .........................................................
template<class T> List<T>::List(void)
{
	_length = 0;
	header = new ListNode<T> (NULL);
	win = header;
}

// .........................................................
template<class T> List<T>::~List(void)
{
	last();
	while (length())
		remove();

	delete header;
}

// .........................................................
template<class T> void List<T>::empty(void)
{
	last();
	while (length())
		delete remove();
}

// .........................................................
template<class T> T List<T>::insert(T val)
{
	win->insert( new ListNode<T>(val));
	++_length;
	return val;
}

// .........................................................
template<class T> T List<T>::prepend(T val)
{
	header->insert( new ListNode<T>(val));
	++_length;
	return val;
}

// .........................................................
template<class T> T List<T>::append(T val)
{
	header->prev()->insert( new ListNode<T>(val));
	++_length;
	return val;
}

// .........................................................
template<class T> List<T>* List<T>::append(List<T> *l)
{
	ListNode<T> *a = (ListNode<T>*)header->prev();
	a->splice(l->header);
	_length += l->_length;
	l->header->remove();
	l->_length = 0;
	l->win = header;
	return this;
}

// .........................................................
template<class T> T List<T>::remove(void)
{
	if (win == header)
		return NULL;
	T val = win->_val;
	win = (ListNode<T>*)win->prev();
	delete (ListNode<T>*)win->next()->remove();
	--_length;
	return val;
}

// .........................................................
template<class T> void List<T>::val(T v)
{
	if (win != header)
		win->_val = v;
}

// .........................................................
template<class T> T List<T>::val(void)
{
	return win->_val;
}

// .........................................................
template<class T> T List<T>::next(void)
{
	win = (ListNode<T>*) win->next();
	return win->_val;
}

// .........................................................
template<class T> T List<T>::prev(void)
{
	win = (ListNode<T>*) win->prev();
	return win->_val;
}

// .........................................................
template<class T> T List<T>::first(void)
{
	win = (ListNode<T>*) header->next();
	return win->_val;
}

// .........................................................
template<class T> T List<T>::last(void)
{
	win = (ListNode<T>*) header->prev();
	return win->_val;
}

// .........................................................
template<class T> int List<T>::length(void)
{
	return _length;
}

// .........................................................
template<class T> bool List<T>::isFirst(void)
{
	return ( (win == header->next() ) && (_length > 0) );
}

// .........................................................
template<class T> bool List<T>::isLast(void)
{
	return ( (win == header->prev() ) && (_length > 0) );
}

// .........................................................
template<class T> bool List<T>::isHead(void)
{
	return ( win == header);
}

// .........................................................
template<class T> Stack<T>::Stack(void) :
	s(new List<T>)
{
}

// .........................................................
template<class T> Stack<T>::~Stack(void)
{
	delete s;
}

// .........................................................
template<class T> void Stack<T>::push( T v)
{
	s->prepend(v);
}

// .........................................................
template<class T> T Stack<T>::pop( void)
{
	s->first();
	return s->remove();
}

// .........................................................
template<class T> bool Stack<T>::empty( void)
{
	return (s->length() == 0);
}

// .........................................................
template<class T> int Stack<T>::size( void)
{
	return s->length();
}

// .........................................................
template<class T> T Stack<T>::top( void)
{
	return s->first();
}

// .........................................................
template<class T> T Stack<T>::nextToTop( void)
{
	s->first();
	return s->next();
}

// .........................................................
template<class T> T Stack<T>::bottom( void)
{
	return s->last();
}

// .........................................................
template<class T> TreeNode<T>::TreeNode(T v) :
	val(v), _lchild(NULL), _rchild(NULL)
{
}

// .........................................................
template<class T> TreeNode<T>::~TreeNode(void)
{
	if (_lchild) delete _lchild;
	if (_rchild) delete _rchild;
}

// .........................................................
template<class T> SearchTree<T>::SearchTree(int(*c)(T,T) ) :
	cmp(c), root(NULL)
{
}

// .........................................................
template<class T> int SearchTree<T>::isEmpty(void)
{
	return (root == NULL);
}

// .........................................................
template<class T> SearchTree<T>::~SearchTree(void)
{
	if (root) delete root;
}

// .........................................................
template<class T> T SearchTree<T>::find(T val)
{
	TreeNode<T> *n= root;
	while (n)
	{
		int result = (*cmp)(val, n->val);
		
		if (result < 0) n = n->_lchild;
		else
		if ( result > 0) n = n->_rchild;
		else
			return n->val;
	}
	return NULL;
}

// .........................................................
template<class T> T SearchTree<T>::findMin(void)
{
	TreeNode<T> *n = _findMin(root);
	return (n ? n->val : NULL);
}

// .........................................................
template<class T>
TreeNode<T> *SearchTree<T>::_findMin(TreeNode<T> *n)
{
	if ( n == NULL)
		return NULL;
	while ( n->_lchild)
		n = n->_lchild;
	return n;
}

// .........................................................
template<class T>
void SearchTree<T>::inorder(void(*visit) (T))
{
	_inorder (root, visit);
}

// ............................................................................
template<class T>
void SearchTree<T>::_inorder(TreeNode<T> *n, void(*visit)(T))

{
	if (n)
	{
		_inorder(n->_lchild, visit);
		(*visit)(n->val);
		_inorder(n->_rchild, visit);
	}
}

// .........................................................
template<class T> void SearchTree<T>::insert(T val)
{
	if (root == NULL)
	{
		root = new TreeNode<T>(val);
		return;
	}
	else
	{
		int result;
		TreeNode<T> *p, *n = root;
		while (n)
		{
			p = n;
			result = (*cmp)(val,p->val);
			if ( result < 0 )
				n = p->_lchild;
			else
			if ( result > 0 )
				n = p->_rchild;
			else
				return;
		}
		if (result < 0)
			p->_lchild = new TreeNode<T>(val);
		else
			p->_rchild = new TreeNode<T>(val);
	}
}

// .........................................................
template<class T> void SearchTree<T>::remove(T val)
{
	_remove(val, root);
}

// ............................................................................
template<class T>
void SearchTree<T>::_remove( T val, TreeNode<T> * &n)
{
	if ( n== NULL)
		return;
	int result = (*cmp)(val, n->val);
	
	if ( result < 0)
		_remove( val, n->_lchild);
	else
	if ( result > 0)
		_remove( val, n->_rchild);
	else
	{
		if (n->_lchild == NULL)
		{
			TreeNode<T> *old = n;
			n = old->_rchild;
			//delete old;				// don't work
			return;
		}
		else
		if (n->_rchild == NULL)
		{
			TreeNode<T> *old = n;
			n = old->_lchild;
			//delete old;
			return;
		}
		else
		{
			TreeNode<T> *m = _findMin(n->_rchild);
			n->val = m->val;
			_remove(m->val, n->_rchild);
		}
	}
}

// .........................................................
template<class T> T SearchTree<T>::removeMin(void)
{
	T v = findMin();
	remove(v);
	return v;
}

// .........................................................
template<class T> BraidedNode<T>::BraidedNode( T val) :
	TreeNode<T>(val)
{
}

// .........................................................
template<class T>
BraidedNode<T> *BraidedNode<T>::rchild(void)
{
	return (BraidedNode<T> *) _rchild;
}
// .........................................................
template<class T>
BraidedNode<T> *BraidedNode<T>::lchild(void)
{
	return (BraidedNode<T> *) _lchild;
}

// .........................................................
template<class T>
BraidedNode<T> *BraidedNode<T>::next(void)
{
	return (BraidedNode<T> *) _next;
}

// .........................................................
template<class T>
BraidedNode<T> *BraidedNode<T>::prev(void)
{
	return (BraidedNode<T> *) _prev;
}

// .........................................................
template<class T>
BraidedSearchTree<T>::BraidedSearchTree( int(*c) (T,T)) :
	cmp(c)
{
	win = root = new BraidedNode<T>(NULL);
}

// .........................................................
template<class T>
BraidedSearchTree<T>::~BraidedSearchTree(void)
{
	delete root;
}

// .........................................................
template<class T> T BraidedSearchTree<T>::next(void)
{
	win = win->next();
	return win->val;
}

// .........................................................
template<class T> T BraidedSearchTree<T>::prev(void)
{
	win = win->prev();
	return win->val;
}

// .........................................................
template<class T> T BraidedSearchTree<T>::val(void)
{
	return win->val;
}

// .........................................................
template<class T>
void BraidedSearchTree<T>::inorder(void (*visit) (T))
{
	BraidedNode<T> *n = root->next();
	while ( n != root)
	{
		(*visit)(n->val);
		n = n->next();
	}
}

// .........................................................
template<class T> bool BraidedSearchTree<T>::isFirst(void)
{
	return (win == root->next() ) && (root != root->next() );
}

// .........................................................
template<class T> bool BraidedSearchTree<T>::isLast(void)
{
	return (win == root->prev() ) && (root != root->next() );
}

// .........................................................
template<class T> bool BraidedSearchTree<T>::isHead(void)
{
	return (win == root);
}

// .........................................................
template<class T> bool BraidedSearchTree<T>::isEmpty(void)
{
	return (win == root->next());
}

// .........................................................
template<class T> T BraidedSearchTree<T>::find(T val)
{
	BraidedNode<T> *n= root->rchild();
	while (n)
	{
		int result = (*cmp)(val, n->val);
		
		if (result < 0) n = n->lchild();
		else
		if ( result > 0) n = n->rchild();
		else
		{
			win = n;
			return n->val;
		}
	}
	return NULL;
}

// .........................................................
template<class T> T BraidedSearchTree<T>::findMin(void)
{
	win = root->next();
	return win->val;
}

// .........................................................
template<class T> T BraidedSearchTree<T>::insert(T val)
{
	int result = 1;
	BraidedNode<T> *p = root;
	BraidedNode<T> *n = root->rchild();
		
	while (n)
	{
		p = n;
		result = (*cmp)(val,p->val);
		if ( result < 0 )
			n = p->lchild();
		else
		if ( result > 0 )
			n = p->rchild();
		else
			return NULL;
	}
	win = new BraidedNode<T>(val);
	if ( result < 0)
	{
		p->_lchild = win;
		p->prev()->Node::insert(win);
	}
	else
	{
		p->_rchild = win;
		p->Node::insert(win);
	}
	return val;
}

// .........................................................
template<class T> void BraidedSearchTree<T>::remove(void)
{
	if ( win != root)
	_remove(win->val, root->_rchild);
}

// ............................................................................
template<class T>
void BraidedSearchTree<T>::_remove( T val, TreeNode<T> * &n)
{
	int result = (*cmp)(val, n->val);
	
	if ( result < 0)
		_remove( val, n->_lchild);
	else
	if ( result > 0)
		_remove( val, n->_rchild);
	else
	{
		if (n->_lchild == NULL)
		{
			BraidedNode<T> *old = (BraidedNode<T>*)n;
			if ( win == old)
				win = old->prev();
			n = old->rchild();
			old->Node::remove();
			//delete old;
			return;
		}
		else
		if (n->_rchild == NULL)
		{
			BraidedNode<T> *old = (BraidedNode<T>*)n;
			if ( win == old)
				win = old->prev();
			n = old->lchild();
			old->Node::remove();
			//delete old;
			return;
		}
		else
		{
			BraidedNode<T> *m = ( (BraidedNode<T>*)n)->next();
			n->val = m->val;
			_remove(m->val, n->_rchild);
		}
	}
}

// .........................................................
template<class T> T BraidedSearchTree<T>::removeMin(void)
{
	T val = root->next()->val;
	if (root != root->next() )
	_remove(val, root->_rchild);
	return val;
}

// .........................................................
template<class T>
RandomizedNode<T>::RandomizedNode( T v, int seed) :
	BraidedNode<T>(v)
{
	if ( seed != -1) srand(seed);
	_priority = (rand()%32767)/32767.0;
	_parent = NULL;
}

// .........................................................
template<class T> void RandomizedNode<T>::rotateRight(void)
{
	RandomizedNode<T> *y = this;
	RandomizedNode<T> *x = y->lchild();
	RandomizedNode<T> *p = y->parent();
	y->_lchild = x->rchild();
	if ( y->lchild() != NULL)
		y->lchild()->_parent = y;
	if ( p->rchild() == y)
		p->_rchild = x;
	else
		p->_lchild = x;
	x->_parent = p;
	x->_rchild = y;
	y->_parent = x;
}

// .........................................................
template<class T> void RandomizedNode<T>::rotateLeft(void)
{
	RandomizedNode<T> *x = this;
	RandomizedNode<T> *y = x->rchild();
	RandomizedNode<T> *p = x->parent();
	x->_rchild = y->lchild();
	if ( x->rchild() != NULL)
		x->rchild()->_parent = x;
	if ( p->lchild() == x)
		p->_lchild = y;
	else
		p->_rchild = y;
	y->_parent = p;
	y->_lchild = x;
	x->_parent = y;
}

// .........................................................
template<class T> void RandomizedNode<T>::bubbleUp(void)
{
	RandomizedNode<T> *p = parent();
	if (priority() < p->priority() )
	{
		if (p->lchild() == this)
			p->rotateRight();
		else
			p->rotateLeft();
		bubbleUp();
	}
}

// .........................................................
template<class T> void RandomizedNode<T>::bubbleDown(void)
{
	double lcPriority = lchild() ? lchild()->priority() : 2.0;
	double rcPriority = rchild() ? rchild()->priority() : 2.0;
	double minPriority = (lcPriority < rcPriority) ? lcPriority : rcPriority;
	if ( priority() <= minPriority)
		return;
	if ( lcPriority < rcPriority)
		rotateRight();
	else
		rotateLeft();
	bubbleDown();
}

// .........................................................
template<class T>
RandomizedNode<T> *RandomizedNode<T>::rchild(void)
{
	return (RandomizedNode<T>*) _rchild;
}

// .........................................................
template<class T>
RandomizedNode<T> *RandomizedNode<T>::lchild(void)
{
	return (RandomizedNode<T>*) _lchild;
}

// .........................................................
template<class T>
RandomizedNode<T> *RandomizedNode<T>::next(void)
{
	return (RandomizedNode<T>*) _next;
}

// .........................................................
template<class T>
RandomizedNode<T> *RandomizedNode<T>::prev(void)
{
	return (RandomizedNode<T>*) _prev;
}

// .........................................................
template<class T>
RandomizedNode<T> *RandomizedNode<T>::parent(void)
{
	return (RandomizedNode<T>*) _parent;
}

// .........................................................
template<class T>
double RandomizedNode<T>::priority(void)
{
	return _priority;
}

// .........................................................
template<class T>
RandomizedSearchTree<T>::RandomizedSearchTree(int (*c)(T,T),int seed) :
	cmp(c)
{
	win = root = new RandomizedNode<T> (NULL,seed);
	root->_priority = -1.0;
	_length = 0;
}

// .........................................................
template<class T>
RandomizedSearchTree<T>::~RandomizedSearchTree(void)
{
	delete root;
}

// .........................................................
template<class T> T RandomizedSearchTree<T>::next(void)
{
	win = win->next();
	return win->val;
}

// .........................................................
template<class T> T RandomizedSearchTree<T>::prev(void)
{
	win = win->prev();
	return win->val;
}

// .........................................................
template<class T> T RandomizedSearchTree<T>::val(void)
{
	return win->val;
}

// .........................................................
template<class T>
void RandomizedSearchTree<T>::inorder(void (*visit) (T))
{
	RandomizedNode<T> *n = root->next();
	while ( n != root)
	{
		(*visit)(n->val);
		n = n->next();
	}
}

// .........................................................
template<class T> bool RandomizedSearchTree<T>::isFirst(void)
{
	return (win == root->next() ) && (root != root->next() );
}

// .........................................................
template<class T> bool RandomizedSearchTree<T>::isLast(void)
{
	return (win == root->prev() ) && (root != root->next() );
}

// .........................................................
template<class T> bool RandomizedSearchTree<T>::isHead(void)
{
	return (win == root);
}

// .........................................................
template<class T> bool RandomizedSearchTree<T>::isEmpty(void)
{
	return (root == root->next());
}

// .........................................................
template<class T> T RandomizedSearchTree<T>::find(T val)
{
	RandomizedNode<T> *n= root->rchild();
	while (n)
	{
		int result = (*cmp)(val, n->val);
		
		if (result < 0) n = n->lchild();
		else
		if ( result > 0) n = n->rchild();
		else
		{
			win = n;
			return n->val;
		}
	}
	return NULL;
}

// .........................................................
template<class T> T RandomizedSearchTree<T>::findMin(void)
{
	win = root->next();
	return win->val;
}

// .........................................................
template<class T> T RandomizedSearchTree<T>::locate(T val)
{
	RandomizedNode<T> *b = root;
	RandomizedNode<T> *n = root->rchild();
	while (n)
	{
		int result = (*cmp)(val, n->val);
		if ( result < 0)
			n = n->lchild();
		else
		if ( result > 0)
		{
			b = n;
			n = n->rchild();
		}
		else
		{
			win = n;
			return win->val;
		}
	}
	win = b;
	return win->val;
}

// .........................................................
template<class T> T RandomizedSearchTree<T>::insert(T val)
{
	int result = 1;
	RandomizedNode<T> *p = root;
	RandomizedNode<T> *n = root->rchild();
		
	while (n)
	{
		p = n;
		result = (*cmp)(val,p->val);
		if ( result < 0 )
			n = p->lchild();
		else
		if ( result > 0 )
			n = p->rchild();
		else
			return NULL;
	}
	win = new RandomizedNode<T>(val);
	win->_parent = p;
	if ( result < 0)
	{
		p->_lchild = win;
		p->prev()->Node::insert(win);
	}
	else
	{
		p->_rchild = win;
		p->Node::insert(win);
	}
	win->bubbleUp();
	
	++_length;

	return val;
}

// .........................................................
template<class T> void RandomizedSearchTree<T>::remove(void)
{
	if ( win != root)
	_remove(win);
}

// .........................................................
template<class T> T RandomizedSearchTree<T>::removeMin(void)
{
	T val = root->next()->val;
	if (root != root->next() )
	_remove( root->next());
	return val;
}

// .........................................................
template<class T>
void RandomizedSearchTree<T>::_remove(RandomizedNode<T> *n)
{
	n->_priority = 1.5;
	n->bubbleDown();
	RandomizedNode<T> *p = n->parent();
	if (p->lchild() == n)
		p->_lchild = NULL;
	else
		p->_rchild = NULL;
	if ( win == n)
		win = n->prev();
	n->Node::remove();
	delete n;
	
	--_length;
}

// .........................................................
template<class T> T RandomizedSearchTree<T>::remove( T val)
{
	T v = find(val);
	if (v)
	{
		remove();
		return v;
	}
	return NULL;
}

////////////////////////////////////////////////////////////
template<class T> List<T> *arrayToList(T a[], int n)
{
	List<T> *s = new List<T>;
	for ( int i=0; i<n; i++)
		s->append(a[i]);
	return s;
}

////////////////////////////////////////////////////////////
template<class T> T leastItem(List<T> &s, int (*cmp)(T,T) )
{
	if (s.length()==0)
		return NULL;
	T v=s.first();
	for (s.next(); !s.isHead(); s.next() )
		if ( (*cmp)(s.val(), v) < 0)
			v=s.val();
		return v;
}

#endif // _LLIST_H_