haiku.git

/*
 * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de.
 * All rights reserved. Distributed under the terms of the MIT license.
 */
#ifndef TEMPLATE_LIST_H
#define TEMPLATE_LIST_H

#ifdef _KERNEL_MODE
	#include <kernel_cpp.h>
#else
	#include <new>
#endif

#include <stdlib.h>
#include <string.h>

#include <SupportDefs.h>

template<typename ITEM>
class DefaultDefaultItemCreator {
public:
	static inline ITEM GetItem() { return ITEM(0); }
};

/*!
	\class TemplateList
	\brief A generic list implementation.
*/
template<typename ITEM,
		 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> >
class TemplateList {
public:
	typedef ITEM					item_t;
	typedef TemplateList			list_t;

private:
	static item_t					sDefaultItem;
	static const size_t				kDefaultChunkSize = 10;
	static const size_t				kMaximalChunkSize = 1024 * 1024;

public:
	TemplateList(size_t chunkSize = kDefaultChunkSize);
	~TemplateList();

	inline const item_t &GetDefaultItem() const;
	inline item_t &GetDefaultItem();

	bool AddItem(const item_t &item, int32 index);
	bool AddItem(const item_t &item);
//	bool AddList(list_t *list, int32 index);
//	bool AddList(list_t *list);

	bool RemoveItem(const item_t &item);
	bool RemoveItem(int32 index);

	bool ReplaceItem(int32 index, const item_t &item);

	bool MoveItem(int32 oldIndex, int32 newIndex);

	void MakeEmpty();

	int32 CountItems() const;
	bool IsEmpty() const;
	const item_t &ItemAt(int32 index) const;
	item_t &ItemAt(int32 index);
	const item_t *Items() const;
	int32 IndexOf(const item_t &item) const;
	bool HasItem(const item_t &item) const;

	// debugging
	int32 GetCapacity() const	{ return fCapacity; }

private:
	inline static void _MoveItems(item_t* items, int32 offset, int32 count);
	bool _Resize(size_t count);

private:
	size_t	fCapacity;
	size_t	fChunkSize;
	int32	fItemCount;
	item_t	*fItems;
};

// sDefaultItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t
	TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem(
		DEFAULT_ITEM_SUPPLIER::GetItem());

// constructor
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::TemplateList(size_t chunkSize)
	: fCapacity(0),
	  fChunkSize(chunkSize),
	  fItemCount(0),
	  fItems(NULL)
{
	if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
		fChunkSize = kDefaultChunkSize;
	_Resize(0);
}

// destructor
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::~TemplateList()
{
	MakeEmpty();
	free(fItems);
}

// GetDefaultItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
inline
const typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const
{
	return sDefaultItem;
}

// GetDefaultItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
inline
typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem()
{
	return sDefaultItem;
}

// _MoveItems
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
inline
void
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count)
{
	if (count > 0 && offset != 0)
		memmove(items + offset, items, count * sizeof(item_t));
}

// AddItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index)
{
	bool result = (index >= 0 && index <= fItemCount
				   && _Resize(fItemCount + 1));
	if (result) {
		_MoveItems(fItems + index, 1, fItemCount - index - 1);
		new(fItems + index) item_t(item);
	}
	return result;
}

// AddItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item)
{
	bool result = true;
	if ((int32)fCapacity > fItemCount) {
		new(fItems + fItemCount) item_t(item);
		fItemCount++;
	} else {
		if ((result = _Resize(fItemCount + 1)))
			new(fItems + (fItemCount - 1)) item_t(item);
	}
	return result;
}

// These don't use the copy constructor!
/*
// AddList
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index)
{
	bool result = (list && index >= 0 && index <= fItemCount);
	if (result && list->fItemCount > 0) {
		int32 count = list->fItemCount;
		result = _Resize(fItemCount + count);
		if (result) {
			_MoveItems(fItems + index, count, fItemCount - index - count);
			memcpy(fItems + index, list->fItems,
				   list->fItemCount * sizeof(item_t));
		}
	}
	return result;
}

// AddList
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list)
{
	bool result = (list);
	if (result && list->fItemCount > 0) {
		int32 index = fItemCount;
		int32 count = list->fItemCount;
		result = _Resize(fItemCount + count);
		if (result) {
			memcpy(fItems + index, list->fItems,
				   list->fItemCount * sizeof(item_t));
		}
	}
	return result;
}
*/

// RemoveItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item)
{
	int32 index = IndexOf(item);
	bool result = (index >= 0);
	if (result)
		RemoveItem(index);
	return result;
}

// RemoveItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index)
{
	if (index >= 0 && index < fItemCount) {
		fItems[index].~item_t();
		_MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
		_Resize(fItemCount - 1);
		return true;
	}
	return false;
}

// ReplaceItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::ReplaceItem(int32 index, const item_t &item)
{
	if (index >= 0 && index < fItemCount) {
		fItems[index] = item;
		return true;
	}
	return false;
}

// MoveItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::MoveItem(int32 oldIndex, int32 newIndex)
{
	if (oldIndex >= 0 && oldIndex < fItemCount
		&& newIndex >= 0 && newIndex <= fItemCount) {
		if (oldIndex < newIndex - 1) {
			item_t item = fItems[oldIndex];
			_MoveItems(fItems + oldIndex + 1, -1, newIndex - oldIndex - 1);
			fItems[newIndex] = item;
		} else if (oldIndex > newIndex) {
			item_t item = fItems[oldIndex];
			_MoveItems(fItems + newIndex, 1, oldIndex - newIndex);
			fItems[newIndex] = item;
		}
		return true;
	}
	return false;
}

// MakeEmpty
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
void
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty()
{
	for (int32 i = 0; i < fItemCount; i++)
		fItems[i].~item_t();
	_Resize(0);
}

// CountItems
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
int32
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const
{
	return fItemCount;
}

// IsEmpty
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const
{
	return (fItemCount == 0);
}

// ItemAt
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
const typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const
{
	if (index >= 0 && index < fItemCount)
		return fItems[index];
	return sDefaultItem;
}

// ItemAt
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index)
{
	if (index >= 0 && index < fItemCount)
		return fItems[index];
	return sDefaultItem;
}

// Items
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
const typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t *
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const
{
	return fItems;
}

// IndexOf
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
int32
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const
{
	for (int32 i = 0; i < fItemCount; i++) {
		if (fItems[i] == item)
			return i;
	}
	return -1;
}

// HasItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const
{
	return (IndexOf(item) >= 0);
}

// _Resize
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count)
{
	bool result = true;
	// calculate the new capacity
	int32 newSize = count;
	if (newSize <= 0)
		newSize = 1;
	newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
	// resize if necessary
	if ((size_t)newSize != fCapacity) {
		item_t* newItems
			= (item_t*)realloc(fItems, newSize * sizeof(item_t));
		if (newItems) {
			fItems = newItems;
			fCapacity = newSize;
		} else
			result = false;
	}
	if (result)
		fItemCount = count;
	return result;
}

#endif	// LIST_H