// List.h
//
// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// You can alternatively use *this file* under the terms of the the MIT
// license included in this package.

#ifndef LIST_H
#define LIST_H

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

#include <SupportDefs.h>

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

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

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

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

        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);

        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;

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 List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t
        List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem(
                DEFAULT_ITEM_SUPPLIER::GetItem());

// constructor
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
List<ITEM, DEFAULT_ITEM_SUPPLIER>::List(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>
List<ITEM, DEFAULT_ITEM_SUPPLIER>::~List()
{
        MakeEmpty();
        free(fItems);
}

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

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

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

// AddItem
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
List<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
List<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
List<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
List<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
List<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
List<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;
}

// MakeEmpty
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
void
List<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
List<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const
{
        return fItemCount;
}

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

// ItemAt
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
List<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 List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
List<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 List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t *
List<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const
{
        return fItems;
}

// IndexOf
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
int32
List<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
List<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const
{
        return (IndexOf(item) >= 0);
}

// _Resize
template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
bool
List<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