src/ui/inc/FUiCtrl_LinkedList.h

   1 //
   2 // Open Service Platform
   3 // Copyright (c) 2012-2013 Samsung Electronics Co., Ltd.
   4 //
   5 // Licensed under the Flora License, Version 1.0 (the License);
   6 // you may not use this file except in compliance with the License.
   7 // You may obtain a copy of the License at
   8 //
   9 //     http://floralicense.org/license/
  10 //
  11 // Unless required by applicable law or agreed to in writing, software
  12 // distributed under the License is distributed on an AS IS BASIS,
  13 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 // See the License for the specific language governing permissions and
  15 // limitations under the License.
  16 //
  17
  18 /**
  19  * @file        FUiCtrl_LinkedList.h
  20  * @brief       This is the header file for the _LinkedList template.
  21  *
  22  * This file contains the declarations and implementation of
  23  * _LinkedList template.
  24  */
  25
  26 #ifndef _FUI_CTRL_INTERNAL_LINKEDLIST_H
  27 #define _FUI_CTRL_INTERNAL_LINKEDLIST_H
  28
  29 #include <new>
  30
  31 template<class T>
  32 class _LinkedList
  33 {
  34 private:
  35         class _ListNode
  36         {
  37         public:
  38                 _ListNode(void)
  39                         : pPrev(null)
  40                         , pNext(null)
  41                         , val(T())
  42                 {
  43                 }
  44
  45                 _ListNode* pPrev;
  46                 _ListNode* pNext;
  47                 T val;
  48         }; // _ListNode
  49
  50         _ListNode* __pHead;
  51         _ListNode* __pTail;
  52         int __length;
  53
  54 public:
  55         class _Iterator
  56         {
  57         private:
  58                 friend class _LinkedList;
  59                 _ListNode* __pPos;
  60
  61         public:
  62                 _Iterator(_ListNode& _lnr)
  63                         : __pPos(&_lnr) {}
  64                 _Iterator(_ListNode* _p = null)
  65                         : __pPos(_p) {}
  66
  67                 _Iterator& operator ++(void)
  68                 {
  69                         __pPos = __pPos->pNext;
  70                         return *this;
  71                 } //pre
  72
  73                 _Iterator operator ++(int)
  74                 {
  75                         _Iterator _retval = *this;
  76                         ++*this;
  77                         return _retval;
  78                 } //post
  79
  80                 _Iterator& operator +(int cnt)
  81                 {
  82                         while (cnt--)
  83                         {
  84                                 __pPos = __pPos->pNext;
  85                         }
  86                         return *this;
  87                 }
  88
  89                 _Iterator& operator --(void)
  90                 {
  91                         __pPos = __pPos->pPrev;
  92                         return *this;
  93                 } //pre
  94
  95                 _Iterator operator --(int)
  96                 {
  97                         _Iterator _retval = *this;
  98                         --*this;
  99                         return _retval;
 100                 } //post
 101
 102                 _Iterator& operator -(int cnt)
 103                 {
 104                         while (cnt--)
 105                         {
 106                                 __pPos = __pPos->pPrev;
 107                         }
 108                         return *this;
 109                 }
 110
 111                 T* operator ->() const { return &__pPos->val;}
 112                 T& operator *() const { return __pPos->val;}
 113                 bool operator ==(const _Iterator& _rhs) const { return __pPos == _rhs.__pPos;}
 114                 bool operator !=(const _Iterator& _rhs) const { return __pPos != _rhs.__pPos;}
 115         }; // _Iterator
 116
 117         class _ReverseIterator
 118         {
 119         private:
 120                 friend class _LinkedList;
 121                 _ListNode* __pPos;
 122
 123         public:
 124                 _ReverseIterator(_ListNode& _lnr)
 125                         : __pPos(&_lnr) {}
 126                 _ReverseIterator(_ListNode* _p = null)
 127                         : __pPos(_p) {}
 128
 129                 _ReverseIterator& operator ++(void)
 130                 {
 131                         __pPos = __pPos->pPrev;
 132                         return *this;
 133                 } //pre
 134
 135                 _ReverseIterator operator ++(int)
 136                 {
 137                         _ReverseIterator _retval = *this;
 138                         ++*this;
 139                         return _retval;
 140                 } //post
 141
 142                 _ReverseIterator& operator --(void)
 143                 {
 144                         __pPos = __pPos->pNext;
 145                         return *this;
 146                 } //pre
 147
 148                 _ReverseIterator operator --(int)
 149                 {
 150                         _Iterator _retval = *this;
 151                         --*this;
 152                         return _retval;
 153                 } //post
 154
 155                 T* operator ->() const { return &__pPos->val;}
 156                 T& operator *() const { return __pPos->val;}
 157                 bool operator ==(const _ReverseIterator& _rhs) const { return __pPos == _rhs.__pPos;}
 158                 bool operator !=(const _ReverseIterator& _rhs) const { return __pPos != _rhs.__pPos;}
 159         }; // _ReverseIterator
 160
 161         _LinkedList(void);
 162         ~_LinkedList(void);
 163
 164         _LinkedList& operator =(_LinkedList& rhs)
 165         {
 166                 //destruct
 167                 clear();
 168
 169                 delete __pHead;
 170                 __pHead = null;
 171                 delete __pTail;
 172                 __pTail = null;
 173
 174                 // copy
 175                 __pHead = rhs.__pHead;
 176                 __pTail = rhs.__pTail;
 177                 __length = rhs.__length;
 178
 179                 // initializing
 180                 rhs.__pHead = new (std::nothrow) _ListNode();
 181                 rhs.__pTail = new (std::nothrow) _ListNode();
 182
 183                 rhs.__pHead->pNext = rhs.__pTail;
 184                 rhs.__pTail->pPrev = rhs.__pHead;
 185                 rhs.__length = 0;
 186
 187                 return *this;
 188         }
 189
 190         void insert(_Iterator&, const T &);
 191         void erase(_Iterator&);
 192         void remove(const T&);
 193         void push_front(const T&);
 194         void push_back(const T&);
 195         void pop_front(void);
 196         void pop_back(void);
 197         void clear(void);
 198         bool empty(void) const;
 199         int size(void) const { return __length;}
 200         void sort(bool (*)(T, T));
 201         void advance(_Iterator& _where, int _index);
 202         T& front(void) const { return __pHead->pNext->val;}
 203         T& back(void) const { return __pTail->pPrev->val;}
 204         T& at(int) const;
 205
 206         _Iterator begin(void) const { return _Iterator(__pHead->pNext);}
 207         _Iterator end(void) const { return _Iterator(__pTail);}
 208         _ReverseIterator rbegin(void) const { return _ReverseIterator(__pTail->pPrev);}
 209         _ReverseIterator rend(void) const { return _ReverseIterator(__pHead);}
 210
 211 private:
 212         void insert_node(_Iterator, _ListNode *, _ListNode *, const T &);
 213         void delete_node(_Iterator, _ListNode *, _ListNode*);
 214         void swap_node(_ListNode*, _ListNode*);
 215         void sort_node(bool (*)(T, T), _ListNode *, _ListNode*);
 216         int count_node(_ListNode*, _ListNode*);
 217
 218 private:
 219         _LinkedList(const _LinkedList& rhs);
 220 }; // _LinkedList
 221
 222 template<class T>
 223 _LinkedList <T>::_LinkedList(void)
 224         : __pHead(null)
 225         , __pTail(null)
 226         , __length(0)
 227 {
 228         __pHead = new (std::nothrow) _ListNode();
 229         __pTail = new (std::nothrow) _ListNode();
 230
 231         __pHead->pNext = __pTail;
 232         __pTail->pPrev = __pHead;
 233 }
 234
 235 template<class T>
 236 _LinkedList <T>::~_LinkedList(void)
 237 {
 238         clear();
 239
 240         delete __pHead;
 241         __pHead = null;
 242         delete __pTail;
 243         __pTail = null;
 244 }
 245
 246 template<class T>
 247 void
 248 _LinkedList <T>::insert(_Iterator& _where, const T& _val)
 249 {
 250         insert_node(_where, null, null, _val);
 251 }
 252
 253 template<class T>
 254 void
 255 _LinkedList <T>::erase(_Iterator& _where)
 256 {
 257         delete_node(_where, null, null);
 258 }
 259
 260 template<class T>
 261 void
 262 _LinkedList <T>::remove(const T& _val)
 263 {
 264         if (__length <= 0)
 265         {
 266                 return;
 267         }
 268
 269         _ListNode* _pTempNode = __pHead->pNext;
 270
 271         //while(_val != _pTempNode->val)
 272         while (memcmp(&(_val), &(_pTempNode->val), sizeof(T)))
 273         {
 274                 if (_pTempNode == __pTail)
 275                 {
 276                         _pTempNode = null;
 277                         break;
 278                 }
 279
 280                 _pTempNode = _pTempNode->pNext;
 281         }
 282
 283         if ((_pTempNode == __pHead->pNext) && (_pTempNode == __pTail->pPrev))
 284         {
 285                 delete __pHead->pNext;
 286                 __pHead->pNext = __pTail;
 287                 __pTail->pPrev = __pHead;
 288         }
 289         else if (_pTempNode != null)
 290         {
 291                 _pTempNode->pPrev->pNext = _pTempNode->pNext;
 292                 _pTempNode->pNext->pPrev = _pTempNode->pPrev;
 293                 delete _pTempNode;
 294                 _pTempNode = null;
 295         }
 296         else
 297         {
 298                 return;
 299         }
 300
 301         __length--;
 302 }
 303
 304 template<class T>
 305 void
 306 _LinkedList <T>::push_front(const T& _val)
 307 {
 308         insert_node(null, __pHead->pNext, null, _val);
 309 }
 310
 311 template<class T>
 312 void
 313 _LinkedList <T>::push_back(const T& _val)
 314 {
 315         insert_node(null, null, __pTail->pPrev, _val);
 316 }
 317
 318 template<class T>
 319 void
 320 _LinkedList <T>::pop_front(void)
 321 {
 322         delete_node(null, __pHead->pNext, null);
 323 }
 324
 325 template<class T>
 326 void
 327 _LinkedList <T>::pop_back(void)
 328 {
 329         delete_node(null, null, __pTail->pPrev);
 330 }
 331
 332 template<class T>
 333 void
 334 _LinkedList <T>::clear(void)
 335 {
 336         _ListNode* _pTempNode;
 337
 338         while (__pHead->pNext != __pTail)
 339         {
 340                 _pTempNode = __pHead->pNext;
 341                 __pHead->pNext = __pHead->pNext->pNext;
 342                 delete _pTempNode;
 343                 _pTempNode = null;
 344         }
 345
 346         __pTail->pPrev = __pHead;
 347         __length = 0;
 348 }
 349
 350 template<class T>
 351 bool
 352 _LinkedList <T>::empty(void) const
 353 {
 354         if (__length <= 0)
 355         {
 356                 return true;
 357         }
 358
 359         return false;
 360 }
 361
 362 template<class T>
 363 void
 364 _LinkedList <T>::sort(bool (* _compare)(T _a, T _b))
 365 {
 366         if (__length <= 0)
 367         {
 368                 return;
 369         }
 370
 371         sort_node(_compare, __pHead->pNext, __pTail->pPrev);
 372 }
 373
 374 template<class T>
 375 void
 376 _LinkedList <T>::advance(_Iterator& _where, int _index)
 377 {
 378         while (_index--)
 379         {
 380                 ++_where;
 381         }
 382 }
 383
 384 template<class T>
 385 void
 386 _LinkedList <T>::insert_node(_Iterator _where, _ListNode* _first, _ListNode* _last, const T& _val)
 387 {
 388         _ListNode* _pNewNode = new (std::nothrow) _ListNode;
 389         _pNewNode->val = _val;
 390
 391         if (_where == null)
 392         {
 393                 if (!_first && !_last)
 394                 {
 395                         __pHead->pNext = _pNewNode;
 396                         __pTail->pPrev = _pNewNode;
 397                 }
 398                 else if (_first)
 399                 {
 400                         _pNewNode->pPrev = __pHead;
 401                         _pNewNode->pNext = __pHead->pNext;
 402                         __pHead->pNext->pPrev = _pNewNode;
 403                         __pHead->pNext = _pNewNode;
 404                 }
 405                 else
 406                 {
 407                         _pNewNode->pPrev = __pTail->pPrev;
 408                         _pNewNode->pNext = __pTail;
 409                         __pTail->pPrev->pNext = _pNewNode;
 410                         __pTail->pPrev = _pNewNode;
 411                 }
 412         }
 413         else
 414         {
 415                 if (_where.__pPos == __pHead->pNext)
 416                 {
 417                         _pNewNode->pPrev = __pHead;
 418                         _pNewNode->pNext = __pHead->pNext;
 419                         __pHead->pNext->pPrev = _pNewNode;
 420                         __pHead->pNext = _pNewNode;
 421                 }
 422                 else if (_where.__pPos == __pTail)
 423                 {
 424                         _pNewNode->pPrev = __pTail->pPrev;
 425                         _pNewNode->pNext = __pTail;
 426                         __pTail->pPrev->pNext = _pNewNode;
 427                         __pTail->pPrev = _pNewNode;
 428                 }
 429                 else
 430                 {
 431                         _pNewNode->pPrev = _where.__pPos->pPrev;
 432                         _where.__pPos->pPrev->pNext = _pNewNode;
 433                         _pNewNode->pNext = _where.__pPos;
 434                         _where.__pPos->pPrev = _pNewNode;
 435                 }
 436
 437                 _where++;
 438         }
 439
 440         __length++;
 441 }
 442
 443 template<class T>
 444 void
 445 _LinkedList <T>::delete_node(_Iterator _where, _ListNode* _first, _ListNode* _last)
 446 {
 447         if (__length <= 0)
 448         {
 449                 return;
 450         }
 451
 452         if (_where == null)
 453         {
 454                 if ((_first == __pHead->pNext) && (_first == __pTail->pPrev)) // only one node
 455                 {
 456                         delete __pHead->pNext;
 457                         __pHead->pNext = __pTail;
 458                         __pTail->pPrev = __pHead;
 459                 }
 460                 else if (_first)    // pop_front
 461                 {
 462                         __pHead->pNext = __pHead->pNext->pNext;
 463                         delete __pHead->pNext->pPrev;
 464                         __pHead->pNext->pPrev = __pHead;
 465                 }
 466                 else if (_last) // pop_back
 467                 {
 468                         __pTail->pPrev = __pTail->pPrev->pPrev;
 469                         delete __pTail->pPrev->pNext;
 470                         __pTail->pPrev->pNext = __pTail;
 471                 }
 472                 else
 473                 {
 474                         return;
 475                 }
 476         }
 477         else
 478         {
 479                 if ((_where.__pPos == __pHead->pNext) && (_where.__pPos == __pTail->pPrev))
 480                 {
 481                         delete __pHead->pNext;
 482                         __pHead->pNext = __pTail;
 483                         __pTail->pPrev = __pHead;
 484                 }
 485                 else
 486                 {
 487                         if (_where.__pPos == __pHead->pNext)
 488                         {
 489                                 __pHead->pNext = __pHead->pNext->pNext;
 490                                 delete __pHead->pNext->pPrev;
 491                                 __pHead->pNext->pPrev = __pHead;
 492                         }
 493                         else if (_where.__pPos == __pTail->pPrev)
 494                         {
 495                                 __pTail->pPrev = __pTail->pPrev->pPrev;
 496                                 delete __pTail->pPrev->pNext;
 497                                 __pTail->pPrev->pNext = __pTail;
 498                         }
 499                         else
 500                         {
 501                                 _where.__pPos->pPrev->pNext = _where.__pPos->pNext;
 502                                 _where.__pPos->pNext->pPrev = _where.__pPos->pPrev;
 503                                 delete _where.__pPos;
 504                                 _where.__pPos = null;
 505                         }
 506                 }
 507         }
 508
 509         __length--;
 510 }
 511
 512 template<class T>
 513 void
 514 _LinkedList <T>::swap_node(_ListNode* _a, _ListNode* _b)
 515 {
 516         T _temp;
 517
 518         _temp = _a->val;
 519         _a->val = _b->val;
 520         _b->val = _temp;
 521 }
 522
 523 template<class T>
 524 void
 525 _LinkedList <T>::sort_node(bool (* _compare)(T _a, T _b), _ListNode* _low, _ListNode* _hight)
 526 {
 527         // FIXME : This function implement using quick sort algorithm.
 528         //         You should remember that _Iterator is invalid after sorting.
 529         _ListNode* _left, * _right, * _pivot;
 530
 531         int _total = count_node(_low, _hight);
 532         int _leftCount = 1;
 533         int _rightCount = _total - 1;
 534
 535         if (_rightCount > 0)
 536         {
 537                 _left = _low;
 538                 _right = _hight->pPrev;
 539                 _pivot = _hight;
 540
 541                 while (1)
 542                 {
 543                         while (_compare(_left->val, _pivot->val))
 544                         {
 545                                 _left = _left->pNext;
 546                                 _leftCount++;
 547                         }
 548
 549                         while (!_compare(_right->val, _pivot->val))
 550                         {
 551                                 if ((_rightCount <= 1) || (_right->pPrev == null))
 552                                 {
 553                                         break;
 554                                 }
 555
 556                                 _right = _right->pPrev;
 557                                 _rightCount--;
 558                         }
 559
 560                         if ((_leftCount >= _rightCount) || (_right->pPrev == null))
 561                         {
 562                                 break;
 563                         }
 564
 565                         swap_node(_left, _right);
 566
 567                         _left = _left->pNext;
 568                         _leftCount++;
 569
 570                         _right = _right->pPrev;
 571                         _rightCount--;
 572                 }
 573
 574                 swap_node(_pivot, _left);
 575
 576                 if ((_left->pPrev != null) && (_leftCount - 1 > 0))
 577                         if ((_left->pNext != _low) && (_low->pPrev != _left))
 578                                 sort_node(_compare, _low, _left->pPrev);
 579
 580                 if ((_left->pNext != null) && (_leftCount < _total))
 581                         if ((_left->pPrev != _hight) && (_hight->pNext != _left))
 582                                 sort_node(_compare, _left->pNext, _hight);
 583         }
 584 }
 585
 586 template<class T>
 587 int
 588 _LinkedList <T>::count_node(_ListNode* _left, _ListNode* _right)
 589 {
 590         int _count = 0;
 591         _ListNode* _pTempNode = _left;
 592
 593         while (_pTempNode != _right)
 594         {
 595                 _pTempNode = _pTempNode->pNext;
 596                 _count++;
 597         }
 598
 599         return ++_count;
 600 }
 601
 602 template<class T>
 603 T&
 604 _LinkedList <T>::at(int _index) const
 605 {
 606         if ((__length <= 0) || (_index >= __length))
 607         {
 608                 return __pHead->val;
 609         }
 610
 611         _ListNode* _pTempNode = __pHead->pNext;
 612
 613         for (int i = 0; i < _index; i++)
 614         {
 615                 _pTempNode = _pTempNode->pNext;
 616         }
 617
 618         return _pTempNode->val;
 619 }
 620
 621 #endif // _FUI_CTRL_INTERNAL_LINKEDLIST_H