00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #ifndef __SEAL_MAP_H__
00030 #define __SEAL_MAP_H__
00031
00032 #include "collection.h"
00033 #include "node.h"
00034 #include "dataptr.h"
00035
00036 namespace seal
00037 {
00038
00043 template <typename IndexType, typename DataType>
00044 class Map : public Collection<DataType>
00045 {
00046 public:
00047
00050 class Iterator : public AbstractIterator<DataType>
00051 {
00052
00053 friend class Map<IndexType, DataType>;
00054
00055 public:
00058 Iterator(void) : AbstractIterator<DataType>(), _firstPtr(NULL), _lastPtr(NULL), _currPtr(NULL)
00059 {}
00060
00063 virtual ~Iterator() {}
00064
00067 virtual bool hasNext(void);
00068
00071 virtual DataType next(void) throw (OutOfBoundsException);
00072
00075 virtual void reset(void) { _currPtr = _firstPtr; }
00076
00079 IndexType getCurrentIndex(void) throw (OutOfBoundsException);
00080
00081 private:
00084 Iterator(MapNode<IndexType, DataType> *f, MapNode<IndexType, DataType> *l)
00085 : AbstractIterator<DataType>(), _firstPtr(f), _lastPtr(l), _currPtr(f)
00086 {}
00087
00088 MapNode<IndexType, DataType> *_firstPtr, *_lastPtr, *_currPtr;
00089 };
00090
00091 public:
00094 Map();
00095
00098 Map(const Map<IndexType, DataType> &map);
00099
00102 virtual ~Map();
00103
00106 virtual unsigned int size(void) const { return *_sizePtr; }
00107
00110 virtual bool isEmpty(void) const { if (*_sizePtr == 0) return true; else return false; }
00111
00114 virtual AbstractIterator<DataType>* iteratorPtr(void) const
00115 {
00116 return new typename Map<IndexType, DataType>::Iterator(_firstNodePtr->data, _lastNodePtr->data);
00117 }
00118
00121 typename Map<IndexType, DataType>::Iterator iterator(void) const
00122 {
00123 return typename Map<IndexType, DataType>::Iterator(_firstNodePtr->data, _lastNodePtr->data);
00124 }
00125
00128 virtual void purge(void);
00129
00133 DataType& operator[](const IndexType &index);
00134
00138 const DataType& operator[](const IndexType &index) const;
00139
00143 void remove(const IndexType &index);
00144
00149 bool hasIndex(const IndexType &index) const;
00150
00153 virtual DataType& first(void) throw (EmptyCollectionException);
00154
00157 virtual const DataType& first(void) const throw (EmptyCollectionException);
00158
00161 virtual DataType& last(void) throw (EmptyCollectionException);
00162
00165 virtual const DataType& last(void) const throw (EmptyCollectionException);
00166
00169 void operator=(const Map<IndexType, DataType> &map);
00170
00171 private:
00172 unsigned int *_sizePtr, *_refCountPtr;
00173 DataPtr< MapNode<IndexType, DataType> > *_firstNodePtr;
00174 DataPtr< MapNode<IndexType, DataType> > *_lastNodePtr;
00175 };
00176
00177 template <typename IndexType, typename DataType>
00178 Map<IndexType, DataType>::Map(void)
00179 : Collection<DataType>()
00180 {
00181 _sizePtr = new unsigned int; *_sizePtr = 0;
00182 _refCountPtr = new unsigned int; *_refCountPtr = 1;
00183
00184 _firstNodePtr = new DataPtr< MapNode<IndexType, DataType> >();
00185 _firstNodePtr->data = NULL;
00186
00187 _lastNodePtr = new DataPtr< MapNode<IndexType, DataType> >();
00188 _lastNodePtr->data = NULL;
00189 }
00190
00191 template <typename IndexType, typename DataType>
00192 Map<IndexType, DataType>::Map(const Map<IndexType, DataType> &m)
00193 : Collection<DataType>(),
00194 _sizePtr(m._sizePtr), _refCountPtr(m._refCountPtr),
00195 _firstNodePtr(m._firstNodePtr), _lastNodePtr(m._lastNodePtr)
00196 {
00197 (*_refCountPtr)++;
00198 }
00199
00200
00201 template <typename IndexType, typename DataType>
00202 Map<IndexType, DataType>::~Map(void)
00203 {
00204 if (*_refCountPtr > 1)
00205 (*_refCountPtr)--;
00206 else
00207 {
00208 purge();
00209 delete _sizePtr; delete _refCountPtr;
00210 delete _firstNodePtr; delete _lastNodePtr;
00211 }
00212 }
00213
00214 template <typename IndexType, typename DataType>
00215 void Map<IndexType, DataType>::operator=(const Map<IndexType, DataType> &map)
00216 {
00217 if (_refCountPtr == map._refCountPtr)
00218 return;
00219
00220 if (*_refCountPtr > 1)
00221 (*_refCountPtr)--;
00222 else
00223 {
00224 purge();
00225 delete _sizePtr; delete _refCountPtr;
00226 delete _firstNodePtr; delete _lastNodePtr;
00227 }
00228
00229 _sizePtr = map._sizePtr;
00230 _refCountPtr = map._refCountPtr;
00231 _firstNodePtr = map._firstNodePtr;
00232 _lastNodePtr = map._lastNodePtr;
00233
00234 (*_refCountPtr)++;
00235 }
00236
00237 template <typename IndexType, typename DataType>
00238 DataType& Map<IndexType, DataType>::operator[](const IndexType &index)
00239 {
00240 MapNode< IndexType, DataType > *nodePtr = _firstNodePtr->data;
00241 while (nodePtr != NULL)
00242 {
00243 if (nodePtr->index == index)
00244 {
00245 return nodePtr->data;
00246 }
00247
00248 nodePtr = nodePtr->nextPtr;
00249 }
00250
00251 MapNode<IndexType, DataType> *newNodePtr = new MapNode<IndexType, DataType>();
00252 newNodePtr->index = index;
00253
00254 if (*_sizePtr == 0)
00255 {
00256 _firstNodePtr->data = newNodePtr;
00257 _lastNodePtr->data = newNodePtr;
00258 }
00259 else
00260 {
00261 _lastNodePtr->data->nextPtr = newNodePtr;
00262 newNodePtr->prevPtr = _lastNodePtr->data;
00263
00264 _lastNodePtr->data = newNodePtr;
00265 }
00266
00267 (*_sizePtr)++;
00268 return newNodePtr->data;
00269 }
00270
00271 template <typename IndexType, typename DataType>
00272 const DataType& Map<IndexType, DataType>::operator[](const IndexType &index) const
00273 {
00274 MapNode< IndexType, DataType > *nodePtr = _firstNodePtr->data;
00275 while (nodePtr != NULL)
00276 {
00277 if (nodePtr->index == index)
00278 {
00279 return nodePtr->data;
00280 }
00281
00282 nodePtr = nodePtr->nextPtr;
00283 }
00284
00285 MapNode<IndexType, DataType> *newNodePtr = new MapNode<IndexType, DataType>();
00286 newNodePtr->index = index;
00287
00288 if (*_sizePtr == 0)
00289 {
00290 _firstNodePtr->data = newNodePtr;
00291 _lastNodePtr->data = newNodePtr;
00292 }
00293 else
00294 {
00295 _lastNodePtr->data->nextPtr = newNodePtr;
00296 newNodePtr->prevPtr = _lastNodePtr->data;
00297
00298 _lastNodePtr->data = newNodePtr;
00299 }
00300
00301 (*_sizePtr)++;
00302 return newNodePtr->data;
00303 }
00304
00305 template <typename IndexType, typename DataType>
00306 bool Map<IndexType, DataType>::hasIndex(const IndexType &index) const
00307 {
00308 MapNode<IndexType, DataType> *nodePtr = _firstNodePtr->data;
00309 while (nodePtr != NULL)
00310 {
00311 if (nodePtr->index == index)
00312 return true;
00313
00314 nodePtr = nodePtr->nextPtr;
00315 }
00316
00317 return false;
00318 }
00319
00320 template <typename IndexType, typename DataType>
00321 void Map<IndexType, DataType>::purge(void)
00322 {
00323 MapNode<IndexType, DataType> *nodePtr = _lastNodePtr->data;
00324 while (nodePtr != NULL)
00325 {
00326 MapNode<IndexType, DataType> *tempPtr = nodePtr->prevPtr;
00327
00328 delete nodePtr;
00329 nodePtr = tempPtr;
00330 }
00331
00332 _lastNodePtr->data = NULL;
00333 _firstNodePtr->data = NULL;
00334
00335 *_sizePtr = 0;
00336 return;
00337 }
00338
00339 template <typename IndexType, typename DataType>
00340 void Map<IndexType, DataType>::remove(const IndexType &index)
00341 {
00342 MapNode<IndexType, DataType> *nodePtr = _firstNodePtr->data;
00343 while (nodePtr != NULL)
00344 {
00345 if (nodePtr->index == index)
00346 break;
00347
00348 nodePtr = nodePtr->nextPtr;
00349 }
00350
00351 if (nodePtr != NULL)
00352 {
00353 if (nodePtr->prevPtr != NULL)
00354 {
00355 nodePtr->prevPtr->nextPtr = nodePtr->nextPtr;
00356 if (nodePtr->nextPtr != NULL)
00357 nodePtr->nextPtr->prevPtr = nodePtr->prevPtr;
00358
00359 if (nodePtr == _lastNodePtr->data)
00360 {
00361 _lastNodePtr->data = nodePtr->prevPtr;
00362 }
00363
00364 delete nodePtr;
00365 }
00366 else if (nodePtr->nextPtr != NULL)
00367 {
00368 nodePtr->nextPtr->prevPtr = nodePtr->prevPtr;
00369 if (nodePtr->prevPtr != NULL)
00370 nodePtr->prevPtr->nextPtr = nodePtr->nextPtr;
00371
00372 if (nodePtr == _firstNodePtr->data)
00373 {
00374 _firstNodePtr->data = nodePtr->nextPtr;
00375 }
00376
00377 delete nodePtr;
00378 }
00379 else
00380 {
00381 delete nodePtr;
00382 _firstNodePtr->data = _lastNodePtr->data = NULL;
00383 }
00384
00385 (*_sizePtr)--;
00386 }
00387 }
00388
00389 template <typename IndexType, typename DataType>
00390 DataType& Map<IndexType, DataType>::first() throw (EmptyCollectionException)
00391 {
00392 if (*_sizePtr == 0)
00393 throw EmptyCollectionException();
00394
00395 return _firstNodePtr->data->data;
00396 }
00397
00398 template <typename IndexType, typename DataType>
00399 const DataType& Map<IndexType, DataType>::first() const throw (EmptyCollectionException)
00400 {
00401 if (*_sizePtr == 0)
00402 throw EmptyCollectionException();
00403
00404 return _firstNodePtr->data->data;
00405 }
00406
00407 template <typename IndexType, typename DataType>
00408 DataType& Map<IndexType, DataType>::last() throw (EmptyCollectionException)
00409 {
00410 if (*_sizePtr == 0)
00411 throw EmptyCollectionException();
00412
00413 return _lastNodePtr->data->data;
00414 }
00415
00416 template <typename IndexType, typename DataType>
00417 const DataType& Map<IndexType, DataType>::last() const throw (EmptyCollectionException)
00418 {
00419 if (*_sizePtr == 0)
00420 throw EmptyCollectionException();
00421
00422 return _lastNodePtr->data->data;
00423 }
00424
00425
00426
00427
00428
00429 template <typename IndexType, typename DataType>
00430 bool Map<IndexType, DataType>::Iterator::hasNext()
00431 {
00432 if (_currPtr == NULL)
00433 return false;
00434 else
00435 return true;
00436 }
00437
00438 template <typename IndexType, typename DataType>
00439 DataType Map<IndexType, DataType>::Iterator::next(void) throw (OutOfBoundsException)
00440 {
00441 if (_currPtr == NULL)
00442 throw OutOfBoundsException();
00443
00444 MapNode<IndexType, DataType> *tempPtr = _currPtr;
00445 _currPtr = _currPtr->nextPtr;
00446
00447 return tempPtr->data;
00448 }
00449
00450 template <typename IndexType, typename DataType>
00451 IndexType Map<IndexType, DataType>::Iterator::getCurrentIndex(void) throw (OutOfBoundsException)
00452 {
00453 if (_currPtr == NULL)
00454 {
00455 if (_lastPtr == NULL)
00456 throw OutOfBoundsException();
00457 else
00458 return _lastPtr->index;
00459 }
00460
00461 if (_currPtr->prevPtr == NULL)
00462 throw OutOfBoundsException();
00463
00464 return _currPtr->prevPtr->index;
00465 }
00466
00467 }
00468 #endif // __SEAL_MAP_H__
00469
