haiku.git

// SLList.h

#ifndef SL_LIST_H
#define SL_LIST_H

#include <SupportDefs.h>

namespace UserlandFSUtil {

// SLListLink
template<typename Element>
class SLListLink {
public:
	SLListLink() : next(NULL) {}
	~SLListLink() {}

	Element	*next;
};

// SLListLinkImpl
template<typename Element>
class SLListLinkImpl {
private:
	typedef SLListLink<Element> Link;

public:
	SLListLinkImpl() : fSLListLink()	{}
	~SLListLinkImpl()					{}

	Link *GetSLListLink()				{ return &fSLListLink; }
	const Link *GetSLListLink() const	{ return &fSLListLink; }

private:
	Link	fSLListLink;
};

// SLListStandardGetLink
template<typename Element>
class SLListStandardGetLink {
private:
	typedef SLListLink<Element> Link;

public:
	inline Link *operator()(Element *element) const
	{
		return element->GetSLListLink();
	}

	inline const Link *operator()(const Element *element) const
	{
		return element->GetSLListLink();
	}
};

// for convenience
#define SL_LIST_TEMPLATE_LIST template<typename Element, typename GetLink>
#define SL_LIST_CLASS_NAME SLList<Element, GetLink>

// SLList
template<typename Element, typename GetLink = SLListStandardGetLink<Element> >
class SLList {
private:
	typedef SLList<Element, GetLink>	List;
	typedef SLListLink<Element>			Link;

public:
	class Iterator {
	public:
		Iterator(List *list)
			: fList(list),
			  fPrevious(NULL),
			  fCurrent(NULL),
			  fNext(fList->GetFirst())
		{
		}

		Iterator(const Iterator &other)
		{
			*this = other;
		}

		bool HasNext() const
		{
			return fNext;
		}
		
		Element *Next()
		{
			if (fCurrent)
				fPrevious = fCurrent;

			fCurrent = fNext;

			if (fNext)
				fNext = fList->GetNext(fNext);

			return fCurrent;
		}
	
		Element *Remove()
		{
			Element *element = fCurrent;
			if (fCurrent) {
				fList->_Remove(fPrevious, fCurrent);
				fCurrent = NULL;
			}
			return element;
		}

		Iterator &operator=(const Iterator &other)
		{
			fList = other.fList;
			fPrevious = other.fPrevious;
			fCurrent = other.fCurrent;
			fNext = other.fNext;
			return *this;
		}
	
	private:
		List	*fList;
		Element *fPrevious;
		Element	*fCurrent;
		Element	*fNext;
	};

	class ConstIterator {
	public:
		ConstIterator(const List *list)
			: fList(list),
			  fNext(list->GetFirst())
		{
		}

		ConstIterator(const ConstIterator &other)
		{
			*this = other;
		}

		bool HasNext() const
		{
			return fNext;
		}
		
		Element *Next()
		{
			Element *element = fNext;
			if (fNext)
				fNext = fList->GetNext(fNext);
			return element;
		}
	
		ConstIterator &operator=(const ConstIterator &other)
		{
			fList = other.fList;
			fNext = other.fNext;
			return *this;
		}
	
	private:
		const List	*fList;
		Element		*fNext;
	};

public:
	SLList() : fFirst(NULL), fLast(NULL) {}
	SLList(const GetLink &getLink)
		: fFirst(NULL), fLast(NULL), fGetLink(getLink) {}
	~SLList() {}

	inline bool IsEmpty() const			{ return (fFirst == NULL); }

	inline void Insert(Element *element, bool back = true);
	inline void InsertAfter(Element *previous, Element *element);
	inline void Remove(Element *element);
		// O(n)!

	inline void MoveFrom(SL_LIST_CLASS_NAME *fromList);

	inline void RemoveAll();

	inline Element *GetFirst() const	{ return fFirst; }
	inline Element *GetLast() const		{ return fLast; }

	inline Element *GetHead() const		{ return fFirst; }
	inline Element *GetTail() const		{ return fLast; }

	inline Element *GetNext(Element *element) const;

	inline int32 Size() const;
		// O(n)!

	inline Iterator GetIterator()				{ return Iterator(this); }
	inline ConstIterator GetIterator() const	{ return ConstIterator(this); }

private:
	friend class Iterator;

	inline void _Remove(Element *previous, Element *element);

private:
	Element	*fFirst;
	Element	*fLast;
	GetLink	fGetLink;
};

}	// namespace UserlandFSUtil

using UserlandFSUtil::SLList;
using UserlandFSUtil::SLListLink;
using UserlandFSUtil::SLListLinkImpl;


// inline methods

// Insert
SL_LIST_TEMPLATE_LIST
void
SL_LIST_CLASS_NAME::Insert(Element *element, bool back)
{
	InsertAfter((back ? fLast : NULL), element);
}

// InsertAfter
SL_LIST_TEMPLATE_LIST
void
SL_LIST_CLASS_NAME::InsertAfter(Element *previous, Element *element)
{
	if (element) {
		Link *elLink = fGetLink(element);
		if (previous) {
			// insert after previous element
			Link *prevLink = fGetLink(previous);
			elLink->next = prevLink->next;
			prevLink->next = element;
		} else {
			// no previous element given: prepend
			elLink->next = fFirst;
			fFirst = element;
		}

		// element may be new last element
		if (fLast == previous)
			fLast = element;
	}
}

// Remove
SL_LIST_TEMPLATE_LIST
void
SL_LIST_CLASS_NAME::Remove(Element *element)
{
	if (!element)
		return;

	for (Iterator it = GetIterator(); it.HasNext();) {
		if (element == it.Next()) {
			it.Remove();
			return;
		}
	}
}

// MoveFrom
SL_LIST_TEMPLATE_LIST
void
SL_LIST_CLASS_NAME::MoveFrom(SL_LIST_CLASS_NAME *fromList)
{
	if (fromList && fromList->fFirst) {
		if (fFirst) {
			fGetLink(fLast)->next = fromList->fFirst;
			fLast = fromList->fLast;
		} else {
			fFirst = fromList->fFirst;
			fLast = fromList->fLast;
		}
		fromList->fFirst = NULL;
		fromList->fLast = NULL;
	}
}

// RemoveAll
SL_LIST_TEMPLATE_LIST
void
SL_LIST_CLASS_NAME::RemoveAll()
{
	Element *element = fFirst;
	while (element) {
		Link *elLink = fGetLink(element);
		element = elLink->next;
		elLink->next = NULL;
	}
	fFirst = NULL;
	fLast = NULL;
}

// GetNext
SL_LIST_TEMPLATE_LIST
Element *
SL_LIST_CLASS_NAME::GetNext(Element *element) const
{
	return (element ? fGetLink(element)->next : NULL);
}

// _Remove
SL_LIST_TEMPLATE_LIST
void
SL_LIST_CLASS_NAME::_Remove(Element *previous, Element *element)
{
	Link *elLink = fGetLink(element);
	if (previous)
		fGetLink(previous)->next = elLink->next;
	else
		fFirst = elLink->next;

	if (element == fLast)
		fLast = previous;

	elLink->next = NULL;
}

// Size
SL_LIST_TEMPLATE_LIST
int32
SL_LIST_CLASS_NAME::Size() const
{
	int32 count = 0;
	for (Element* element = GetFirst(); element; element = GetNext(element))
		count++;
	return count;
}

#endif	// SL_LIST_H