dynlist.h

swain-0.5.2.zip的源代码,比较好用,希望大家喜欢.

/*
This file is part of SWAIN (http://sourceforge.net/projects/swain).
Copyright (C) 2006  Daniel Lindstr鰉 and Daniel Nilsson

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., 51 Franklin Street, Fifth Floor,
Boston, MA  02110-1301, USA.
*/
#pragma once

#include <stdlib.h>

#define START_SIZE 16

template <class T>
class DynList
{
private:
	T *list;
	T nullItem;
	int size;
	int lowest_item;
	int num_items;

	int doubleSize(void);
public:
	DynList(T nullItem, int size = START_SIZE);
	~DynList(void);
	int addItem(T item);
	T removeItem(T item);
	T removeIndex(int index);
	int getIndex(T item);
	T getItem(int index);
	int getSize(void);
	int getCount(void);
	bool exists(T item);
};

template <class T>
DynList<T>::DynList(T nullItem, int startsize){
	this->nullItem = nullItem;
	this->size = startsize;
	this->list = NULL;
	this->doubleSize();
	this->lowest_item = 0;
	this->num_items = 0;
	for(int i=0; i<this->size; i++)
		this->list[i] = nullItem;
}

template <class T>
DynList<T>::~DynList(void){
	free(this->list);
}

template <class T>
int DynList<T>::doubleSize(void){
	T *tmp;
	int i = this->size;
	if(list == NULL)
		this->list = (T *)malloc(this->size*sizeof(T));
	else{
		this->size *= 2;
 		tmp = (T*)realloc(this->list, this->size*sizeof(T));
		if(tmp != NULL)
			list = tmp;
		else{
			this->size /= 2;
			return -1;
		}
		for( ; i<this->size; i++)
			this->list[i] = nullItem;


	}
	return(this->size);
}

template <class T>
int DynList<T>::addItem(T item){
	int i;
	if(this->lowest_item == this->size)
		this->doubleSize();
	for(i = this->lowest_item; i < this->size; i++){
		if( this->list[i] == nullItem ){
			this->list[i] = item;
			break;
		}
	}
	this->lowest_item = i + 1;
	if (item != nullItem) {
		this->num_items++;
	}
	return i;
}

template <class T>
T DynList<T>::removeItem(T item){
	int index = getIndex(item);
	if(index == -1)
		return nullItem;
	return removeIndex(index);
}

template <class T>
T DynList<T>::removeIndex(int index){
	T ret = list[index];
	this->list[index] = nullItem;
	if(this->lowest_item > index)
		this->lowest_item = index;
	this->num_items--;
	return(ret);	
}

template <class T>
int DynList<T>::getIndex(T item){
	for(int i=0; i< this->size; i++){
		if(this->list[i] == item)
			return(i);
	}
	return(-1);
}

template <class T>
T DynList<T>::getItem(int index){
	if(index<0||index>=size)
		return(nullItem);
	return(this->list[index]);
}

template <class T>
int DynList<T>::getSize(void){
	return(this->size);
}

template <class T>
int DynList<T>::getCount(void){
	return(this->num_items);
}

template <class T>
bool DynList<T>::exists(T item) {
	return this->getIndex(item) != -1;
}