1// SLList.h 2// 3// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de) 4// 5// Permission is hereby granted, free of charge, to any person obtaining a 6// copy of this software and associated documentation files (the "Software"), 7// to deal in the Software without restriction, including without limitation 8// the rights to use, copy, modify, merge, publish, distribute, sublicense, 9// and/or sell copies of the Software, and to permit persons to whom the 10// Software is furnished to do so, subject to the following conditions: 11// 12// The above copyright notice and this permission notice shall be included in 13// all copies or substantial portions of the Software. 14// 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21// DEALINGS IN THE SOFTWARE. 22// 23// Except as contained in this notice, the name of a copyright holder shall 24// not be used in advertising or otherwise to promote the sale, use or other 25// dealings in this Software without prior written authorization of the 26// copyright holder. 27 28#ifndef SL_LIST_H 29#define SL_LIST_H 30 31#include <new> 32 33// SLListStandardNode 34template<typename Value> 35struct SLListStandardNode { 36 SLListStandardNode(const Value &a) 37 : value(a), 38 next(NULL) 39 { 40 } 41 42 Value value; 43 SLListStandardNode<Value> *next; 44}; 45 46// SLListStandardNodeAllocator 47template<typename Value, typename Node> 48class SLListStandardNodeAllocator 49{ 50public: 51 inline Node *Allocate(const Value &a) const 52 { 53 return new(nothrow) SLListStandardNode<Value>(a); 54 } 55 56 inline void Free(Node *node) const 57 { 58 delete node; 59 } 60}; 61 62// SLListValueNodeAllocator 63template<typename Value, typename Node> 64class SLListValueNodeAllocator 65{ 66public: 67 inline Node *Allocate(const Value &a) const 68 { 69 return a; 70 } 71 72 inline void Free(Node *node) const 73 { 74 } 75}; 76 77// SLListStandardGetValue 78template<typename Value, typename Node> 79class SLListStandardGetValue 80{ 81public: 82 inline Value &operator()(Node *node) const 83 { 84 return node->value; 85 } 86}; 87 88// SLListValueNodeGetValue 89template<typename Value, typename Node> 90class SLListValueNodeGetValue 91{ 92public: 93 inline Value &operator()(Node *node) const 94 { 95 return *node; 96 } 97}; 98 99// for convenience 100#define SL_LIST_TEMPLATE_LIST template<typename Value, typename Node, \ 101 typename NodeAllocator, typename GetValue> 102#define SL_LIST_CLASS_NAME SLList<Value, Node, NodeAllocator, GetValue> 103 104// SLList 105template<typename Value, typename Node = SLListStandardNode<Value>, 106 typename NodeAllocator = SLListStandardNodeAllocator<Value, Node>, 107 typename GetValue = SLListStandardGetValue<Value, Node> > 108class SLList { 109public: 110 class Iterator; 111 112public: 113 SLList(); 114 SLList(const NodeAllocator &nodeAllocator, const GetValue &getValue); 115 ~SLList(); 116 117 bool Insert(const Value &value, Iterator *iterator = NULL); 118 bool Remove(const Value &value); 119 void Remove(Iterator &iterator); 120 void RemoveAll(); 121 122 bool Find(const Value &value, Iterator *iterator = NULL) const; 123 void GetIterator(Iterator *iterator) const; 124 125private: 126 friend class Iterator; 127 128 Node *fHead; 129 NodeAllocator fNodeAllocator; 130 GetValue fGetValue; 131}; 132 133// Iterator 134SL_LIST_TEMPLATE_LIST 135class SL_LIST_CLASS_NAME::Iterator { 136public: 137 Iterator() : fList(NULL), fCurrent(NULL) {} 138 ~Iterator() {} 139 140 inline Value *GetCurrent() 141 { 142 return (fList && fCurrent ? &fList->fGetValue(fCurrent) : NULL); 143 } 144 145 inline Value *GetNext() 146 { 147 if (fCurrent) 148 fCurrent = fCurrent->next; 149 return GetCurrent(); 150 } 151 152 inline void Remove() 153 { 154 if (fList) 155 fList->Remove(*this); 156 } 157 158private: 159 friend class SL_LIST_CLASS_NAME; 160 161 inline void _SetTo(SL_LIST_CLASS_NAME *list, Node *previous, Node *node) 162 { 163 fList = list; 164 fPrevious = previous; 165 fCurrent = node; 166 } 167 168 inline SL_LIST_CLASS_NAME *_GetList() const { return fList; } 169 inline Node *_GetPreviousNode() const { return fPrevious; } 170 inline Node *_GetCurrentNode() const { return fCurrent; } 171 172private: 173 SL_LIST_CLASS_NAME *fList; 174 Node *fPrevious; 175 Node *fCurrent; 176}; 177 178// constructor 179SL_LIST_TEMPLATE_LIST 180SL_LIST_CLASS_NAME::SLList() 181 : fHead(NULL)/*, 182 fNodeAllocator(), 183 fGetValue()*/ 184{ 185} 186 187// constructor 188SL_LIST_TEMPLATE_LIST 189SL_LIST_CLASS_NAME::SLList(const NodeAllocator &nodeAllocator, 190 const GetValue &getValue) 191 : fHead(NULL), 192 fNodeAllocator(nodeAllocator), 193 fGetValue(getValue) 194{ 195} 196 197// destructor 198SL_LIST_TEMPLATE_LIST 199SL_LIST_CLASS_NAME::~SLList() 200{ 201 RemoveAll(); 202} 203 204// Insert 205SL_LIST_TEMPLATE_LIST 206bool 207SL_LIST_CLASS_NAME::Insert(const Value &value, Iterator *iterator) 208{ 209 Node *node = fNodeAllocator.Allocate(value); 210 if (node) { 211 node->next = fHead; 212 fHead = node; 213 if (iterator) 214 iterator->_SetTo(this, NULL, node); 215 } 216 return node; 217} 218 219// Remove 220SL_LIST_TEMPLATE_LIST 221bool 222SL_LIST_CLASS_NAME::Remove(const Value &value) 223{ 224 Iterator iterator; 225 bool result = Find(value, &iterator); 226 if (result) 227 iterator.Remove(); 228 return result; 229} 230 231// Remove 232SL_LIST_TEMPLATE_LIST 233void 234SL_LIST_CLASS_NAME::Remove(Iterator &iterator) 235{ 236 Node *node = iterator._GetCurrentNode(); 237 if (iterator._GetList() == this && node) { 238 Node *previous = iterator._GetPreviousNode(); 239 iterator._SetTo(this, previous, node->next); 240 if (previous) 241 previous->next = node->next; 242 else 243 fHead = node->next; 244 fNodeAllocator.Free(node); 245 } 246} 247 248// RemoveAll 249SL_LIST_TEMPLATE_LIST 250void 251SL_LIST_CLASS_NAME::RemoveAll() 252{ 253 for (Node *node = fHead; node; ) { 254 Node *next = node->next; 255 fNodeAllocator.Free(node); 256 node = next; 257 } 258 fHead = NULL; 259} 260 261// Find 262SL_LIST_TEMPLATE_LIST 263bool 264SL_LIST_CLASS_NAME::Find(const Value &value, Iterator *iterator) const 265{ 266 Node *node = fHead; 267 Node *previous = NULL; 268 while (node && fGetValue(node) != value) { 269 previous = node; 270 node = node->next; 271 } 272 if (node && iterator) { 273 iterator->_SetTo(const_cast<SL_LIST_CLASS_NAME*>(this), previous, 274 node); 275 } 276 return node; 277} 278 279// GetIterator 280SL_LIST_TEMPLATE_LIST 281void 282SL_LIST_CLASS_NAME::GetIterator(Iterator *iterator) const 283{ 284 if (iterator) 285 iterator->_SetTo(const_cast<SL_LIST_CLASS_NAME*>(this), NULL, fHead); 286} 287 288#endif // SL_LIST_H 289