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