linkedlist.cpp

finite element mesh 参数化有限元网格划分

// LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <stdlib.h>

/*** ListElement ***/

#ifndef SKIP_THIS
template<class T> 
class ListElement {
public:
	ListElement() : next(NULL), prev(NULL) {}
	ListElement(const T& _value) : value(_value), next(NULL), prev(NULL) {}
	~ListElement() {}
	T value;
	ListElement* next;
	ListElement* prev;
};
#endif

/*** LinkedList ***/

/** Defines a template for a linked list. A list can only hold values of one type, T, defined when the list is created. For example, the following list: 
\code LinkedList<int> mylist \endcode
can only hold values of type int 
*/

template<class T> 
class LinkedList {

private:

	ListElement<T>* head;
	ListElement<T>* tail;
	long Size;
	
public:

	/** Defines an iterator of a list of type LinkedList. 
		The iterator is used to iterate over the elements of a list. The iterator at each moment is pointing to an element in the list. 
		Example of usage: 
 \code	
LinkedList<int> list;
LinkedList<int>::iterator iter;
int val;
for (iter=list.begin(); iter!=list.end(); iter++) { // iterating over the elements
	val = (int)(*iter); // extracting the value
	.
	.
	.
} \endcode
	*/
	class iterator { 
		friend LinkedList<T>;
	public:
		/** Default constructor. Initializes the iterator to point to nothing. */
		iterator() : ptr(NULL) {}
		#ifndef SKIP_THIS
		/** Constructor */
		iterator(ListElement<T>* _ptr) : ptr(_ptr) {}
		#endif
		/** Copy constructor. Initializes the iterator to point at the same element as \e iter 
			\param iter A reference to a list iterator to copy 
		*/
		iterator(const iterator& iter) {
			ptr = iter.ptr;
		}
		/** Returns the value of the element pointed to by this iterator. 
			\return A reference of the value pointed by the iterator
		*/
		T& operator*() {
			return ptr->value;
		}
		/** Updates the iterator to point on the next list element (prefix operator). 
			\return A reference of the current iterator
		*/
		iterator& operator++() {
			ptr = ptr->next;
			return (*this); 
		}
		/** Updates the iterator to point on the next list element (postfix operator). 
			\return A copy of the iterator
		*/
		iterator operator++(int) { 
			iterator iter = *this;
			++(*this);
			return (iter); 
		}
		/** Updates the iterator to more forward \e inc elements in the list (postfix operator). 
			\param inc The number of steps to move forward in the list  
			\return A copy of the iterator
		*/
		iterator operator+(int inc) {  
			iterator iter = *this;
			for (int i=0; i<inc; i++)
				iter++;
			return (iter); 
		}
		/** Updates the iterator to point on the previous list element (prefix operator). 
			\return A reference of the current iterator
		*/
		iterator& operator--() {
			ptr = ptr->prev;
			return (*this); 
		}
		/** Updates the iterator to point on the previous list element (postfix operator). 
			\return A copy of the iterator
		*/
		iterator operator--(int) {  
			iterator iter = *this;
			--(*this);
			return (iter); 
		}
		/** Updates the iterator to more backwards \e inc elements in the list (postfix operator). 
			\param inc The number of steps to move backwards in the list  
			\return A copy of the iterator
		*/
		iterator operator-(int inc) {  // postfix
			iterator iter = *this;
			for (int i=0; i<inc; i++)
				iter--;
			return (iter); 
		}
		/** Updates the current iterator to point to the same element pointed by the given iterator. 
			\param iter  The iterator to copy  
			\return A reference of the current iterator
		*/
		iterator& operator=(const iterator& iter) {
			ptr = iter.ptr;
			return (*this); 
		}
		/** Compares the 2 iterators (by the elements they're pointing to. 
			\param iter The iterator to compare to  
			\retval true The 2 iterators point to the same element  
			\retval false The 2 iterators point to different elements 
		*/
		bool operator==(const iterator& iter) {
			return (ptr==iter.ptr);
		}
		/** Compares the 2 iterators (by the elements they're pointing to. 
			\param iter The iterator to compare to  
			\retval true The 2 iterators point to different elements  
			\retval false The 2 iterators point to the same element 
		*/
		bool operator!=(const iterator& iter) {
			return (ptr!=iter.ptr);
		}
	private:
		ListElement<T>* ptr;
	};

	/** Constructor. Initializes an empty list */
	LinkedList() {
		head = new ListElement<T>();
		tail = new ListElement<T>();
		head->next = tail;
		tail->prev = head;
		Size=0;
	}
	/** Copy constructor. Initializes the list with a copy of \e list */
	LinkedList(const LinkedList<T>& list) {
		head = new ListElement<T>();
		tail = new ListElement<T>();
		head->next = tail;
		tail->prev = head;
		Size=0;
		push_back_list((LinkedList<T>*)&list);
	}
	/** Destructor, clears the list and frees memory. */
	~LinkedList() {
		clear();
		delete head;
		delete tail;
	}

	/** Copies all elements of \e list to the current list (clears current list first). 
		\param list The list to copy 
	*/
	void operator=(LinkedList<T>& list) {
		clear();
		push_back_list(&list);
	}
	/** Checks if list is empty.
		\retval true The list is empty  
		\retval false The list is not empty (at least one element) 
	*/
	bool empty() const {
		return (Size==0);
	}
	/** Returns the list size (number of elements in the list). 
		\return The list size
	*/
	long size() const {
		return Size;
	}
	/** Checks if the given value is found in the list. 
		\param value The value to check for existence in the list  
		\retval true \e value is found in the list  
		\retval false \e value is not found in the list 
	*/
	bool contains(const T& value) {
		for (iterator iter = begin(); iter != end(); ++iter) {
			if (*iter == value) {
				return true;
			}
		}
		return false;
	}
	/** Checks if the given value is found in the list, and if so, returns an iterator pointing to it. 
		\param value  The value to check for existence in the list  
		\param iter \out An iterator pointing to the element in the list with the given value  
		\retval true \e value is found in the list  
		\retval false \e value is not found in the list 
	*/
	bool contains(const T& value, iterator &iter) {
		for (iterator iter1 = begin(); iter1 != end(); ++iter1) {
			if (*iter1 == value) {
				iter=iter1;
				return true;
			}
		}
		return false;
	}
	/** Clears the list (removes all elements). */
	void clear() {
		if (Size==0) return;
		iterator iter(head->next);
		ListElement<T>* val;
		while (iter.ptr!=tail) {
			val = iter.ptr;
			++iter;
			delete val;
		}
		Size=0;
		head->next = tail;
		tail->prev = head;
	}
	/** Remove the element pointed by \e iter. 
		\param iter An iterator pointing to the element to erase  
		\retval true Element removed succesfully  
		\retval false Operation failed (\e iter was not pointing to a valid element) 
	*/
	bool erase(iterator iter) {
		if (iter.ptr==NULL) return false;
		iter.ptr->prev->next = iter.ptr->next;
		iter.ptr->next->prev = iter.ptr->prev;
		delete iter.ptr;
		Size--;
		return true;
	}