1 /*---------------------------------------------------------------------------* 2 Project: NintendoWare 3 File: ut_LinkList.h 4 5 Copyright (C)2009-2011 Nintendo/HAL Laboratory, Inc. All rights reserved. 6 7 These coded instructions, statements, and computer programs contain proprietary 8 information of Nintendo and/or its licensed developers and are protected by 9 national and international copyright laws. They may not be disclosed to third 10 parties or copied or duplicated in any form, in whole or in part, without the 11 prior written consent of Nintendo. 12 13 The content herein is highly confidential and should be handled accordingly. 14 15 $Revision: $ 16 *---------------------------------------------------------------------------*/ 17 18 #ifndef NW_UT_LINKLIST_H_ 19 #define NW_UT_LINKLIST_H_ 20 21 #include <nw/types.h> 22 #include <nw/assert.h> 23 #include <nw/ut/ut_Inlines.h> 24 #include <nw/ut/ut_Iterator.h> 25 #include <nw/ut/ut_Preprocessor.h> 26 27 namespace nw { 28 namespace ut { 29 30 class LinkListNode; 31 32 namespace internal { 33 34 class LinkListImpl; 35 36 } // namespace internal 37 38 //-------------------------------------------------------------------------- 39 //! @brief 双方向リンクリストノードです。 40 //--------------------------------------------------------------------------- 41 class LinkListNode 42 { 43 private: 44 NW_DISALLOW_COPY_AND_ASSIGN(LinkListNode); 45 46 public: 47 48 typedef LinkListNode Self; //!< @details :private 49 50 //-------------------------------------------------------------------------- 51 //! @brief コンストラクタです。 52 //--------------------------------------------------------------------------- LinkListNode()53 /* ctor */ explicit LinkListNode() : m_pNext(NULL), m_pPrev(NULL) {} 54 55 //-------------------------------------------------------------------------- 56 //! @brief 次のノードを取得します。 57 //! 58 //! @return 次のノードのポインタを返します。 59 //--------------------------------------------------------------------------- GetNext()60 Self* GetNext() const { return m_pNext; } 61 62 //-------------------------------------------------------------------------- 63 //! @brief １つ前のノードを取得します。 64 //! 65 //! @return １つ前のノードのポインタを返します。 66 //--------------------------------------------------------------------------- GetPrev()67 Self* GetPrev() const { return m_pPrev; } 68 69 //-------------------------------------------------------------------------- 70 //! @brief 比較演算子のオーバーロードです。 71 //! 72 //! @param[in] &r1 １つ目の比較値です。 73 //! @param[in] &r2 ２つ目の比較値です。 74 //! 75 //! @return 等しい場合には true、そうでない場合には false を返します。 76 //--------------------------------------------------------------------------- 77 friend bool operator==(const Self &r1,const Self &r2) { return &r1 == &r2; } 78 79 //-------------------------------------------------------------------------- 80 //! @brief 否定の比較演算子のオーバーロードです。 81 //! 82 //! @param[in] r1 １つ目の比較値です。 83 //! @param[in] r2 ２つ目の比較値です。 84 //! 85 //! @return 等しい場合には false、そうでない場合には true を返します。 86 //--------------------------------------------------------------------------- 87 friend bool operator!=(const Self &r1,const Self &r2) { return !(r1 == r2); } 88 89 private: 90 Self* m_pNext; 91 Self* m_pPrev; 92 93 friend class internal::LinkListImpl; // m_pNext, m_pPrevを使用するため。 94 }; 95 96 namespace internal { 97 98 //-------------------------------------------------------------------------- 99 //! @brief 双方向リンクリスト実装クラス 100 //--------------------------------------------------------------------------- 101 class LinkListImpl 102 { 103 private: 104 NW_DISALLOW_COPY_AND_ASSIGN(LinkListImpl); 105 106 public: 107 108 typedef LinkListImpl Self; 109 typedef u32 size_type; 110 typedef PtrDiff difference_type; 111 112 // リンクリストノードクラス。 113 typedef LinkListNode Node; 114 typedef Node value_type; 115 typedef value_type* pointer; 116 typedef const value_type* const_pointer; 117 typedef value_type& reference; 118 typedef const value_type& const_reference; 119 typedef std::bidirectional_iterator_tag iterator_category; 120 121 //=========================================================================== 122 // イテレータ 123 //=========================================================================== 124 class iterator; 125 class const_iterator; 126 127 class iterator : public internal::iterator<iterator_category, value_type> 128 { 129 public: 130 131 typedef iterator TIt; 132 typedef internal::iterator<iterator_category, value_type> TBaseIt; 133 iterator()134 /* ctor */ explicit iterator() : m_pPointer(NULL) {} 135 136 reference operator*() const { NW_NULL_ASSERT(m_pPointer); return *m_pPointer; } 137 pointer operator->() const { return m_pPointer; } 138 139 TIt &operator++() { m_pPointer = m_pPointer->GetNext(); return *this; } 140 TIt operator++(int) { const TIt it(*this); (void)++*this; return it; } 141 TIt &operator--() { m_pPointer = m_pPointer->GetPrev(); return *this; } 142 TIt operator--(int) { const TIt it(*this); (void)--*this; return it; } 143 144 friend bool operator==(TIt it1, TIt it2) { return it1.m_pPointer == it2.m_pPointer; } 145 friend bool operator!=(TIt it1, TIt it2) { return !(it1 == it2); } 146 147 private: 148 iterator(pointer p)149 explicit iterator(pointer p) : m_pPointer(p) {} 150 151 pointer m_pPointer; 152 153 friend class LinkListImpl; // コンストラクタを使用するため。 154 friend class const_iterator; // m_pPointerを使用するため。 155 }; 156 157 //! @details :private 158 typedef iterator Iterator_alias_; // const_iterator内部で使用。 159 160 class const_iterator 161 : public internal::iterator<iterator_category, value_type> 162 { 163 public: 164 165 typedef const_iterator TIt; 166 typedef internal::iterator<iterator_category, value_type> TBaseIt; 167 typedef const_pointer pointer; 168 typedef const_reference reference; 169 const_iterator()170 explicit const_iterator() : m_pPointer(NULL) {} const_iterator(Iterator_alias_ it)171 const_iterator(Iterator_alias_ it) : m_pPointer(it.m_pPointer) {} 172 173 reference operator*() const { NW_NULL_ASSERT(m_pPointer); return *m_pPointer;} 174 pointer operator->() const { return m_pPointer;} 175 176 TIt &operator++() { m_pPointer = m_pPointer->GetNext(); return *this; } 177 TIt operator++(int) { const TIt it(*this); (void)++*this; return it; } 178 TIt &operator--() { m_pPointer = m_pPointer->GetPrev(); return *this; } 179 TIt operator--(int) { const TIt it(*this); (void)--*this; return it; } 180 181 friend bool operator==(TIt it1, TIt it2) {return it1.m_pPointer == it2.m_pPointer; } 182 friend bool operator!=(TIt it1, TIt it2) {return !(it1 == it2);} 183 184 private: 185 const_iterator(pointer p)186 explicit const_iterator(pointer p) : m_pPointer(p) {} 187 188 pointer m_pPointer; 189 190 friend class LinkListImpl; // コンストラクタを使用するため。 191 }; 192 193 typedef internal::reverse_iterator<iterator> reverse_iterator; 194 typedef internal::reverse_iterator<const_iterator> const_reverse_iterator; 195 196 //---------------------------------------- 197 //! @name コンストラクタ/デストラクタ。 198 //@{ 199 LinkListImpl()200 /* ctor */ explicit LinkListImpl() { Initialize_(); } ~LinkListImpl()201 /* dtor */ ~LinkListImpl() { clear(); } 202 203 //@} 204 205 //---------------------------------------- 206 //! @name 状態の問い合わせ、イテレータの取得 207 //@{ 208 size()209 size_type size() const { return m_Size; } empty()210 bool empty() const { return m_Size == 0; } 211 begin()212 iterator begin() { return iterator(m_BaseNode.GetNext()); } begin()213 const_iterator begin() const { return const_iterator(m_BaseNode.GetNext()); } end()214 iterator end() { return iterator(&m_BaseNode); } end()215 const_iterator end() const { return const_iterator(const_cast<Node*>(&m_BaseNode)); } 216 rbegin()217 reverse_iterator rbegin() { return reverse_iterator(end()); } rbegin()218 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } rend()219 reverse_iterator rend() { return reverse_iterator(begin()); } rend()220 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 221 front()222 reference front() 223 { 224 NW_ASSERT(!empty()); 225 return *begin(); 226 } front()227 const_reference front() const 228 { 229 NW_ASSERT(!empty()); 230 return *begin(); 231 } back()232 reference back() 233 { 234 NW_ASSERT(!empty()); 235 return *--end(); 236 } back()237 const_reference back() const 238 { 239 NW_ASSERT(!empty()); 240 return *--end(); 241 } 242 243 //@} 244 245 //---------------------------------------- 246 //! @name 要素の挿入/削除。 247 //@{ 248 push_front(pointer p)249 void push_front(pointer p) { (void)insert( begin(), p ); } push_back(pointer p)250 void push_back(pointer p) { (void)insert( end(), p ); } pop_front()251 void pop_front() { (void)erase( begin() ); } pop_back()252 void pop_back() { (void)erase( --end() ); } 253 254 iterator insert(iterator it,pointer p); 255 256 iterator erase(pointer p); 257 iterator erase(iterator it); 258 iterator erase(iterator itFirst,iterator itLast); 259 clear()260 void clear() { (void)this->erase(begin(), end()); } 261 262 //@} 263 264 //---------------------------------------- 265 //! @name 要素の順序の変更 266 //@{ 267 268 void reverse(); 269 270 //@} 271 272 //---------------------------------------- 273 //! @name 要素とノードとの変換 274 //@{ 275 GetIteratorFromPointer(pointer p)276 static iterator GetIteratorFromPointer(pointer p) 277 { 278 NW_NULL_ASSERT(p); 279 return iterator(p); 280 } 281 GetIteratorFromPointer(const_pointer p)282 static const_iterator GetIteratorFromPointer(const_pointer p) 283 { 284 NW_NULL_ASSERT(p); 285 return const_iterator(p); 286 } 287 //@} 288 289 protected: GetBaseNode()290 Node* GetBaseNode() { return &m_BaseNode; } GetBaseNode()291 const Node* GetBaseNode() const { return &m_BaseNode; } 292 293 private: 294 Initialize_()295 void Initialize_() 296 { 297 m_Size=0; 298 m_BaseNode.m_pNext = &m_BaseNode; 299 m_BaseNode.m_pPrev = &m_BaseNode; 300 } 301 302 303 size_type m_Size; // 現在の要素数。 304 Node m_BaseNode; // ノードリンクリストの[先端 - 1]兼[終端]。 305 }; 306 307 } // namespace internal 308 309 310 //-------------------------------------------------------------------------- 311 //! @brief リンクリストクラスです。 312 //! 313 //! @tparam T リストの要素となるクラスの型です。 314 //! @tparam TNOffset 要素 T の型の中での LinkListNode へのオフセットです。 315 //--------------------------------------------------------------------------- 316 template < typename T, PtrDiff TNOffset > 317 class LinkList : private internal::LinkListImpl 318 { 319 private: 320 321 typedef internal::LinkListImpl Base; 322 323 public: 324 325 typedef LinkList Self; //!< @details :private 326 using Base::Node; 327 328 using Base::size_type; 329 using Base::difference_type; 330 331 typedef T value_type; //!< @details :private 332 typedef value_type* pointer; //!< @details :private 333 typedef const value_type* const_pointer; //!< @details :private 334 typedef value_type& reference; //!< @details :private 335 typedef const value_type& const_reference; //!< @details :private 336 typedef std::bidirectional_iterator_tag iterator_category; //!< @details :private 337 338 private: 339 340 typedef Base::iterator TIt_base_; 341 typedef Base::const_iterator TItC_base_; 342 343 public: 344 345 //=========================================================================== 346 // イテレータ 347 //=========================================================================== 348 349 class iterator; 350 class const_iterator; 351 352 //-------------------------------------------------------------------------- 353 //! @brief リンクリストのイテレータです。 354 //--------------------------------------------------------------------------- 355 class iterator : public internal::iterator<iterator_category, value_type> 356 { 357 public: 358 359 typedef iterator TIt; //!< @details :private 360 typedef internal::iterator<iterator_category, value_type> TBaseIt; //!< @details :private 361 362 //-------------------------------------------------------------------------- 363 //! @brief コンストラクタです。 364 //--------------------------------------------------------------------------- iterator()365 /* ctro */ explicit iterator() {} 366 367 //---------------------------------------- 368 //! @name 演算子オーバーロード 369 //@{ 370 371 //-------------------------------------------------------------------------- 372 //! @brief イテレータの指している要素の値を取得するポインタ演算子です。 373 //! 374 //! @return 要素の参照を返します。 375 //--------------------------------------------------------------------------- 376 reference operator*() const { pointer p = operator->(); NW_NULL_ASSERT(p); return *p;} 377 378 //-------------------------------------------------------------------------- 379 //! @brief イテレータの指している要素のアドレスを取得するアロー演算子です。 380 //! 381 //! @return 要素のポインタを返します。 382 //--------------------------------------------------------------------------- 383 pointer operator->() const { return GetPointerFromNode(it_.operator->());} 384 385 //-------------------------------------------------------------------------- 386 //! @brief イテレータの前置のインクリメント演算子です。 387 //! 388 //! @return インクリメントされたイテレータを返します。 389 //--------------------------------------------------------------------------- 390 TIt &operator++() { (void)++it_; return *this; } 391 392 //-------------------------------------------------------------------------- 393 //! @brief イテレータの後置のインクリメント演算子です。 394 //! 395 //! @return インクリメント前のイテレータを返します。 396 //--------------------------------------------------------------------------- 397 TIt operator++(int) { const TIt it(*this); (void)++*this; return it; } 398 399 //-------------------------------------------------------------------------- 400 //! @brief イテレータの前置のデクリメント演算子です。 401 //! 402 //! @return デクリメントされたイテレータを返します。 403 //--------------------------------------------------------------------------- 404 TIt &operator--() { (void)--it_; return *this; } 405 406 //-------------------------------------------------------------------------- 407 //! @brief イテレータの後置のデクリメント演算子です。 408 //! 409 //! @return デクリメント前のイテレータを返します。 410 //--------------------------------------------------------------------------- 411 TIt operator--(int) { const TIt it(*this); (void)--*this; return it; } 412 413 //-------------------------------------------------------------------------- 414 //! @brief 比較演算子です。 415 //! 416 //! @param[in] it1 比較対象の１つ目のイテレータです。 417 //! @param[in] it2 比較対象の２つ目のイテレータです。 418 //! 419 //! @return 等しい場合には true, そうでない場合には false を返します。 420 //--------------------------------------------------------------------------- 421 friend bool operator == (TIt it1, TIt it2) { return it1.it_== it2.it_; } 422 423 //-------------------------------------------------------------------------- 424 //! @brief 否定の比較演算子です。 425 //! 426 //! @param[in] it1_ 比較対象の１つ目のイテレータです。 427 //! @param[in] it2_ 比較対象の２つ目のイテレータです。 428 //! 429 //! @return 等しい場合には false, そうでない場合には true を返します。 430 //--------------------------------------------------------------------------- 431 friend bool operator != (TIt it1_, TIt it2_) { return !(it1_ == it2_); } // it1, it2 にすると何故かコンパイラに警告される。 432 433 //@} 434 435 private: 436 iterator(TIt_base_ it)437 /* ctor */ explicit iterator(TIt_base_ it) : it_(it) {} 438 TIt_base_ it_; 439 440 #ifdef NW_PLATFORM_CTR 441 friend class LinkList; 442 #else 443 friend class Self; // コンストラクタを使用するため。 444 #endif 445 friend class const_iterator; // it_を使用するため。 446 }; 447 448 typedef iterator Iterator_alias_; // const_iterator内部で使用。 449 450 //-------------------------------------------------------------------------- 451 //! @brief リンクリストのコンストイテレータです。 452 //--------------------------------------------------------------------------- 453 class const_iterator 454 : public internal::iterator<iterator_category, value_type> 455 { 456 public: 457 458 typedef const_iterator TIt; //!< @details :private 459 typedef internal::iterator<iterator_category, value_type> TBaseIt; //!< @details :private 460 typedef const_pointer pointer; //!< @details :private 461 typedef const_reference reference; //!< @details :private 462 463 //-------------------------------------------------------------------------- 464 //! @brief コンストラクタです。 465 //--------------------------------------------------------------------------- const_iterator()466 /* ctor */ explicit const_iterator() {} 467 468 //-------------------------------------------------------------------------- 469 //! @brief コピーコンストラクタです。 470 //--------------------------------------------------------------------------- const_iterator(Iterator_alias_ it)471 /* ctor */ const_iterator(Iterator_alias_ it) : it_(it.it_) {} 472 473 //---------------------------------------- 474 //! @name 演算子オーバーロード 475 //@{ 476 477 //-------------------------------------------------------------------------- 478 //! @brief イテレータの指している要素の値を取得するポインタ演算子です。 479 //! 480 //! @return 要素の参照を返します。 481 //--------------------------------------------------------------------------- 482 reference operator*() const { pointer p = operator->(); NW_NULL_ASSERT(p); return *p; } 483 484 //-------------------------------------------------------------------------- 485 //! @brief イテレータの指している要素のアドレスを取得するアロー演算子です。 486 //! 487 //! @return 要素のポインタを返します。 488 //--------------------------------------------------------------------------- 489 pointer operator->() const { return GetPointerFromNode(it_.operator->());} 490 491 //-------------------------------------------------------------------------- 492 //! @brief イテレータの前置のインクリメント演算子です。 493 //! 494 //! @return インクリメントされたイテレータを返します。 495 //--------------------------------------------------------------------------- 496 TIt &operator++() { (void)++it_; return *this; } 497 498 //-------------------------------------------------------------------------- 499 //! @brief イテレータの後置のインクリメント演算子です。 500 //! 501 //! @return インクリメント前のイテレータを返します。 502 //--------------------------------------------------------------------------- 503 TIt operator++(int) { const TIt it(*this); (void)++*this; return it; } 504 505 //-------------------------------------------------------------------------- 506 //! @brief イテレータの前置のデクリメント演算子です。 507 //! 508 //! @return デクリメントされたイテレータを返します。 509 //--------------------------------------------------------------------------- 510 TIt &operator--() { (void)--it_; return *this;} 511 512 //-------------------------------------------------------------------------- 513 //! @brief イテレータの後置のデクリメント演算子です。 514 //! 515 //! @return デクリメント前のイテレータを返します。 516 //--------------------------------------------------------------------------- 517 TIt operator--(int) { const TIt it(*this); (void)--*this; return it; } 518 519 //-------------------------------------------------------------------------- 520 //! @brief 比較演算子です。 521 //! 522 //! @param[in] it1 比較対象の１つ目のイテレータです。 523 //! @param[in] it2 比較対象の２つ目のイテレータです。 524 //! 525 //! @return 等しい場合には true, そうでない場合には false を返します。 526 //--------------------------------------------------------------------------- 527 friend bool operator == (TIt it1, TIt it2) { return it1.it_== it2.it_; } 528 529 //-------------------------------------------------------------------------- 530 //! @brief 否定の比較演算子です。 531 //! 532 //! @param[in] it1_ 比較対象の１つ目のイテレータです。 533 //! @param[in] it2_ 比較対象の２つ目のイテレータです。 534 //! 535 //! @return 等しい場合には false, そうでない場合には true を返します。 536 //--------------------------------------------------------------------------- 537 friend bool operator != (TIt it1_, TIt it2_) { return !(it1_ == it2_); } 538 539 //@} 540 541 protected: 542 const_iterator(TItC_base_ it)543 /* ctor */ explicit const_iterator(TItC_base_ it) : it_(it) {} 544 545 TItC_base_ it_; 546 547 548 #if defined(NW_PLATFORM_CTR) 549 friend class LinkList; // コンストラクタを使用するため。 550 #else 551 friend class Self; // コンストラクタを使用するため。 552 #endif 553 }; 554 555 typedef internal::reverse_iterator<iterator> reverse_iterator; //!< @details :private 556 typedef internal::reverse_iterator<const_iterator> const_reverse_iterator; //!< @details :private 557 558 //---------------------------------------- 559 //! @name コンストラクタ/デストラクタ。 560 //@{ 561 562 //-------------------------------------------------------------------------- 563 //! @brief コンストラクタです。 564 //--------------------------------------------------------------------------- LinkList()565 /* ctor */ explicit LinkList() {} 566 567 //@} 568 569 //---------------------------------------- 570 //! @name 状態の問い合わせ、イテレータの取得 571 //@{ 572 573 //-------------------------------------------------------------------------- 574 //! @fn u32 LinkList::size() 575 //! 576 //! @brief リストのサイズを取得します。 577 //! 578 //! @return リストのサイズを返します。 579 //--------------------------------------------------------------------------- 580 using Base::size; 581 582 //-------------------------------------------------------------------------- 583 //! @fn bool LinkList::empty() 584 //! 585 //! @brief リストが空であるかどうかを取得します。 586 //! 587 //! @return リストが空の場合には true, 要素が存在する場合には false を返します。 588 //--------------------------------------------------------------------------- 589 using Base::empty; 590 591 //-------------------------------------------------------------------------- 592 //! @brief 先頭の要素へのイテレータを取得します。 593 //! 594 //! @return 先頭の要素へのイテレータを返します。 595 //--------------------------------------------------------------------------- begin()596 iterator begin() { return iterator(Base::begin()); } begin()597 const_iterator begin() const { return const_iterator(const_cast<Self*>(this)->begin()); } 598 599 //-------------------------------------------------------------------------- 600 //! @brief イテレータの終端を取得します。 601 //! 602 //! @return イテレータの終端を返します。 603 //--------------------------------------------------------------------------- end()604 iterator end() { return iterator(Base::end()); } end()605 const_iterator end() const { return const_iterator(const_cast<Self*>(this)->end()); } 606 607 //-------------------------------------------------------------------------- 608 //! @brief 末尾の要素へのリバースイテレータを取得します。 609 //! 610 //! @return 末尾の要素へのリバースイテレータを返します。 611 //--------------------------------------------------------------------------- rbegin()612 reverse_iterator rbegin() { return reverse_iterator(end()); } rbegin()613 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 614 615 //-------------------------------------------------------------------------- 616 //! @brief リバースイテレータの終端を取得します。 617 //! 618 //! @return リバースイテレータの終端を返します。 619 //--------------------------------------------------------------------------- rend()620 reverse_iterator rend() { return reverse_iterator(begin()); } rend()621 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 622 623 //-------------------------------------------------------------------------- 624 //! @brief 先頭の要素の参照を取得します。 625 //! 626 //! @return 先頭の要素の参照を返します。 627 //--------------------------------------------------------------------------- front()628 reference front() { NW_ASSERT(!empty()); return *begin(); } front()629 const_reference front() const { NW_ASSERT(!empty()); return *begin(); } 630 631 //-------------------------------------------------------------------------- 632 //! @brief 末尾の要素の参照を取得します。 633 //! 634 //! @return 末尾の要素の参照を返します。 635 //--------------------------------------------------------------------------- back()636 reference back() { NW_ASSERT(!empty()); return *--end(); } back()637 const_reference back() const { NW_ASSERT(!empty()); return *--end(); } 638 639 //@} 640 641 //---------------------------------------- 642 //! @name 挿入/削除 643 //@{ 644 645 //-------------------------------------------------------------------------- 646 //! @brief リストに要素を挿入します。 647 //! 648 //! @param[in] it 要素を挿入位置のイテレータです。 it の直前に要素が挿入されます。 649 //! @param[in] p 挿入する要素のポインタです。 650 //! 651 //! @return 追加された要素のイテレータを返します。 652 //--------------------------------------------------------------------------- insert(iterator it,pointer p)653 iterator insert(iterator it, pointer p) { return iterator(Base::insert(it.it_,GetNodeFromPointer(p)));} 654 655 //-------------------------------------------------------------------------- 656 //! @brief リストにの先頭に要素を追加します。 657 //! 658 //! @param[in] p 挿入する要素のポインタです。 659 //--------------------------------------------------------------------------- push_front(pointer p)660 void push_front(pointer p) { (void)insert(begin(),p);} 661 662 //-------------------------------------------------------------------------- 663 //! @brief リストにの末尾に要素を追加します。 664 //! 665 //! @param[in] p 挿入する要素のポインタです。 666 //--------------------------------------------------------------------------- push_back(pointer p)667 void push_back(pointer p) { (void)insert(end(),p);} 668 669 using Base::pop_front; 670 using Base::pop_back; 671 672 //-------------------------------------------------------------------------- 673 //! @brief 指定されたメンバを削除します。 674 //! 675 //! @param[in] it 削除する要素のイテレータです。 676 //! 677 //! @return 削除した要素の次のノードへのイテレータを返します。 678 //--------------------------------------------------------------------------- erase(iterator it)679 iterator erase(iterator it) { return iterator(Base::erase(it.it_)); } 680 681 //-------------------------------------------------------------------------- 682 //! @brief 指定されたメンバを削除します。 683 //! 684 //! 685 //! 終了位置に指定された要素は削除されません。 686 //! 687 //! @param[in] itFirst 削除開始位置を示すイテレータです。 688 //! @param[in] itLast 削除終了位置を示すイテレータです。 689 //! 690 //! @return 削除した要素の次のノードへのイテレータを返します。 691 //--------------------------------------------------------------------------- erase(iterator itFirst,iterator itLast)692 iterator erase(iterator itFirst,iterator itLast) { return iterator(Base::erase(itFirst.it_, itLast.it_)); } 693 694 //-------------------------------------------------------------------------- 695 //! @brief 指定されたメンバを削除します。 696 //! 697 //! @param[in] p 削除する要素のポインタです。 698 //! 699 //! @return 削除した要素の次のノードへのイテレータを返します。 700 //--------------------------------------------------------------------------- erase(pointer p)701 iterator erase(pointer p) { return iterator(Base::erase(GetNodeFromPointer(p))); } 702 703 //-------------------------------------------------------------------------- 704 //! @brief 一つ前の要素を取得します。 705 //! 706 //! @param[in] p 基点となる要素のポインタです。 707 //! 708 //! @return 一つ前の要素を返します。 存在しない場合は NULL を返します。 709 //--------------------------------------------------------------------------- GetPrev(pointer p)710 pointer GetPrev(pointer p) 711 { 712 Node* baseNode = GetBaseNode(); 713 Node* node = ( p == NULL )? baseNode : GetNodeFromPointer( p ); 714 node = node->GetPrev(); 715 return ( node == baseNode )? NULL : GetPointerFromNode( node ); 716 } 717 GetPrev(const_pointer p)718 const_pointer GetPrev(const_pointer p) const 719 { 720 const Node* baseNode = GetBaseNode(); 721 const Node* node = ( p == NULL )? baseNode : GetNodeFromPointer( p ); 722 node = node->GetPrev(); 723 return ( node == baseNode )? NULL : GetPointerFromNode( node ); 724 } 725 726 //-------------------------------------------------------------------------- 727 //! @brief 一つ後の要素を取得します。 728 //! 729 //! @param[in] p 基点となる要素のポインタです。 730 //! 731 //! @return 一つ後の要素を返します。 存在しない場合は NULL を返します。 732 //--------------------------------------------------------------------------- GetNext(pointer p)733 pointer GetNext(pointer p) 734 { 735 Node* baseNode = GetBaseNode(); 736 Node* node = ( p == NULL )? baseNode : GetNodeFromPointer( p ); 737 node = node->GetNext(); 738 return ( node == baseNode )? NULL : GetPointerFromNode( node ); 739 } 740 GetNext(const_pointer p)741 const_pointer GetNext(const_pointer p) const 742 { 743 const Node* baseNode = GetBaseNode(); 744 const Node* node = ( p == NULL )? baseNode : GetNodeFromPointer( p ); 745 node = node->GetNext(); 746 return ( node == baseNode )? NULL : GetPointerFromNode( node ); 747 } 748 749 //-------------------------------------------------------------------------- 750 //! @fn void nw::ut::LinkList::clear() 751 //! 752 //! @brief リストを空にします。 753 //--------------------------------------------------------------------------- 754 using Base::clear; 755 756 //@} 757 758 //---------------------------------------- 759 //! @name 順序の変更 760 //@{ 761 762 //-------------------------------------------------------------------------- 763 //! @fn void LinkList::reverse() 764 //! 765 //! @brief リストの並びを反転します。 766 //--------------------------------------------------------------------------- 767 using Base::reverse; 768 769 //@} 770 771 //---------------------------------------- 772 //! @name 要素とノードとの変換 773 //@{ 774 775 //-------------------------------------------------------------------------- 776 //! @brief ノードのポインタからイテレータを取得します。 777 //! 778 //! @param[in] p ノードのポインタです。 779 //! 780 //! @return イテレータです。 781 //--------------------------------------------------------------------------- GetIteratorFromPointer(Node * p)782 static iterator GetIteratorFromPointer(Node *p) 783 { 784 NW_NULL_ASSERT(p); 785 return iterator(Base::GetIteratorFromPointer(p)); 786 } GetIteratorFromPointer(const Node * p)787 static const_iterator GetIteratorFromPointer(const Node *p) 788 { 789 NW_NULL_ASSERT(p); 790 return const_iterator(Base::GetIteratorFromPointer(p)); 791 } 792 793 //-------------------------------------------------------------------------- 794 //! @brief 要素のポインタからイテレータを取得します。 795 //! 796 //! @param[in] p 要素のポインタです。 797 //! 798 //! @return イテレータです。 799 //--------------------------------------------------------------------------- GetIteratorFromPointer(pointer p)800 static iterator GetIteratorFromPointer(pointer p) 801 { 802 NW_NULL_ASSERT(p); 803 return GetIteratorFromPointer(GetNodeFromPointer(p)); 804 } GetIteratorFromPointer(const_pointer p)805 static const_iterator GetIteratorFromPointer(const_pointer p) 806 { 807 NW_NULL_ASSERT(p); 808 return GetIteratorFromPointer(GetNodeFromPointer(p)); 809 } 810 811 //-------------------------------------------------------------------------- 812 //! @brief 要素のポインタからノードのポインタを取得します。 813 //! 814 //! @param[in] p 要素のポインタです。 815 //! 816 //! @return ノードのポインタです。 817 //--------------------------------------------------------------------------- GetNodeFromPointer(pointer p)818 static Node* GetNodeFromPointer(pointer p) 819 { 820 NW_NULL_ASSERT(p); 821 return reinterpret_cast<Node*>(reinterpret_cast<IntPtr>(p) + TNOffset); 822 } GetNodeFromPointer(const_pointer p)823 static const Node* GetNodeFromPointer(const_pointer p) 824 { 825 NW_NULL_ASSERT(p); 826 return reinterpret_cast<const Node*>(reinterpret_cast<IntPtr>(p) + TNOffset); 827 } 828 829 //-------------------------------------------------------------------------- 830 //! @brief ノードのポインタから要素のポインタを取得します。 831 //! 832 //! @param[in] p ノードのポインタです。 833 //! 834 //! @return 要素のポインタです。 835 //--------------------------------------------------------------------------- GetPointerFromNode(Node * p)836 static pointer GetPointerFromNode(Node* p) 837 { 838 NW_NULL_ASSERT(p); 839 return reinterpret_cast<pointer>(reinterpret_cast<IntPtr>(p) - TNOffset); 840 } GetPointerFromNode(const Node * p)841 static const_pointer GetPointerFromNode(const Node* p) 842 { 843 NW_NULL_ASSERT(p); 844 return reinterpret_cast<const_pointer>( reinterpret_cast<IntPtr>(p) - TNOffset); 845 } 846 847 //@} 848 849 //------------------------------------ 850 // NW4R 互換用のalias 851 //------------------------------------ 852 typedef iterator Iterator; //!< @details :private 853 typedef const_iterator ConstIterator; //!< @details :private 854 typedef reverse_iterator ReverseIterator; //!< @details :private 855 typedef const_reverse_iterator ConstReverseIterator; //!< @details :private 856 GetSize()857 size_type GetSize() const { return this->size(); } //!< @details :private IsEmpty()858 bool IsEmpty() const { return this->empty(); } //!< @details :private 859 GetBeginIter()860 iterator GetBeginIter() { return this->begin(); } //!< @details :private GetBeginIter()861 const_iterator GetBeginIter() const { return this->begin(); } //!< @details :private GetEndIter()862 iterator GetEndIter() { return this->end(); } //!< @details :private GetEndIter()863 const_iterator GetEndIter() const { return this->end(); } //!< @details :private 864 GetBeginReverseIter()865 reverse_iterator GetBeginReverseIter() { return this->rbegin(); } //!< @details :private GetBeginReverseIter()866 const_reverse_iterator GetBeginReverseIter() const { return this->rbegin(); } //!< @details :private GetEndReverseIter()867 reverse_iterator GetEndReverseIter() { return this->rend(); } //!< @details :private GetEndReverseIter()868 const_reverse_iterator GetEndReverseIter() const { return this->rend(); } //!< @details :private 869 GetFront()870 reference GetFront() { return this->front(); } //!< @details :private GetFront()871 const_reference GetFront() const { return this->front(); } //!< @details :private GetBack()872 reference GetBack() { return this->back(); } //!< @details :private GetBack()873 const_reference GetBack() const { return this->back(); } //!< @details :private 874 Insert(iterator it,pointer p)875 iterator Insert(iterator it, pointer p) { return this->insert(it, p); } //!< @details :private PushFront(pointer p)876 void PushFront(pointer p) { this->push_front(p); } //!< @details :private PushBack(pointer p)877 void PushBack(pointer p) { this->push_back(p); } //!< @details :private 878 PopFront()879 void PopFront() { this->pop_front(); } //!< @details :private PopBack()880 void PopBack() { this->pop_back(); } //!< @details :private 881 Erase(iterator it)882 iterator Erase(iterator it) { return this->erase(it); } //!< @details :private Erase(iterator itFirst,iterator itLast)883 iterator Erase(iterator itFirst,iterator itLast) { return this->erase(itFirst, itLast); } //!< @details :private Erase(pointer p)884 iterator Erase(pointer p) { return this->erase(p); } //!< @details :private 885 Clear()886 void Clear() { this->clear(); } //!< @details :private Reverse()887 void Reverse() { this->reverse(); } //!< @details :private 888 }; 889 890 891 } // namespace ut 892 } // namespace nw 893 894 #endif /* NW_UT_LINKLIST_H_ */ 895