2 Copyright 2004 John Tsiombikas <nuclear@siggraph.org>
4 This file is part of the eternal demo.
6 The eternal library is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2 of the License, or
9 (at your option) any later version.
11 The eternal demo is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with the eternal demo; if not, write to the Free Software
18 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 #ifndef _LINKEDLIST_H_
21 #define _LINKEDLIST_H_
26 ListNode<T> *next, *prev;
33 ListNode<T> *head, *tail;
41 inline ListNode<T> *begin();
42 inline const ListNode<T> *begin() const;
43 inline ListNode<T> *end();
44 inline const ListNode<T> *end() const;
46 void push_back(ListNode<T> *node);
47 void push_back(T data);
49 void insert(ListNode<T> *pos, ListNode<T> *node);
50 void insert(ListNode<T> *pos, T data);
52 void remove(ListNode<T> *node);
53 ListNode<T> *erase(ListNode<T> *node);
55 ListNode<T> *find(T key);
58 inline int size() const;
60 void operator =(LinkedList &rhs);
64 /////////// implementation //////////
66 LinkedList<T>::LinkedList() {
73 LinkedList<T>::~LinkedList() {
81 ListNode<T> *LinkedList<T>::begin() {
86 const ListNode<T> *LinkedList<T>::begin() const {
91 ListNode<T> *LinkedList<T>::end() {
96 const ListNode<T> *LinkedList<T>::end() const {
101 void LinkedList<T>::push_back(ListNode<T> *node) {
103 if(!head) { // empty list
105 node->next = node->prev = 0;
117 void LinkedList<T>::push_back(T data) {
119 ListNode<T> *node = new ListNode<T>;
122 if(!head) { // empty list
124 node->next = node->prev = 0;
136 void LinkedList<T>::insert(ListNode<T> *pos, ListNode<T> *node) {
140 node->next = node->prev = 0;
142 node->prev = pos->prev;
145 if(head == pos) head = node; else node->prev->next = node;
152 void LinkedList<T>::insert(ListNode<T> *pos, T data) {
154 ListNode<T> *node = new ListNode<T>;
159 node->next = node->prev = 0;
161 node->prev = pos->prev;
164 if(head == pos) head = node; else node->prev->next = node;
171 void LinkedList<T>::remove(ListNode<T> *node) {
173 if(!node) return; // e.g. remove(head) on an empty list
176 node->prev->next = node->next;
182 node->next->prev = node->prev;
191 ListNode<T> *LinkedList<T>::erase(ListNode<T> *node) {
193 if(!node) return 0; // e.g. erase(head) on an empty list
196 node->prev->next = node->next;
202 node->next->prev = node->prev;
207 ListNode<T> *destr = node;
218 ListNode<T> *LinkedList<T>::find(T key) {
220 ListNode<T> *iter = head;
222 if(iter->data == key) return iter;
226 return 0; // null pointer if not found
230 int LinkedList<T>::count_nodes() {
234 ListNode<T> *iter = head;
244 int LinkedList<T>::size() const {
250 void LinkedList<T>::operator =(LinkedList<T> &rhs) {
252 ListNode<T> *src = rhs.begin();
254 push_back(src->data);
260 #endif // _LINKEDLIST_H_