inc/FBaseColLinkedList.h

   1 //
   2 // Copyright (c) 2012 Samsung Electronics Co., Ltd.
   3 //
   4 // Licensed under the Apache License, Version 2.0 (the License);
   5 // you may not use this file except in compliance with the License.
   6 // You may obtain a copy of the License at
   7 //
   8 // http://www.apache.org/licenses/LICENSE-2.0
   9 //
  10 // Unless required by applicable law or agreed to in writing, software
  11 // distributed under the License is distributed on an "AS IS" BASIS,
  12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13 // See the License for the specific language governing permissions and
  14 // limitations under the License.
  15 //
  16
  17 /**
  18  * @file                FBaseColLinkedList.h
  19  * @brief               This is the header file for the %LinkedList class.
  20  *
  21  * This header file contains the declarations of the %LinkedList class.
  22  */
  23 #ifndef _FBASE_COL_LINKED_LIST_H_
  24 #define _FBASE_COL_LINKED_LIST_H_
  25
  26 #include <FBaseColIComparer.h>
  27 #include <FBaseColIList.h>
  28
  29 namespace Tizen { namespace Base { namespace Collection
  30 {
  31
  32 class _ListNode;
  33
  34 /**
  35  * @class LinkedList
  36  * @brief This class represents a collection of objects that can be individually accessed by index.
  37  *
  38  * @since 2.0
  39  *
  40  * The %LinkedList class represents a collection of objects that can be individually accessed by index.
  41  *
  42  * For more information on the class features, see <a href="../org.tizen.native.appprogramming/html/guide/base/arraylist_linkedlist.htm">ArrayList and LinkedList</a>.
  43  *
  44  * The following example demonstrates how to use the %LinkedList class.
  45  *
  46  * @code
  47  *      #include <FBase.h>
  48  *
  49  *      using namespace Tizen::Base;
  50  *      using namespace Tizen::Base::Collection;
  51  *
  52  *      void
  53  *      MyClass::LinkedListSample(void)
  54  *      {
  55  *              LinkedList list(SingleObjectDeleter);
  56  *
  57  *              list.Add(new Integer(1));       // 1
  58  *              list.Add(new Integer(2));       // 1,2
  59  *              list.Add(new Integer(3));       // 1,2,3
  60  *
  61  *              Integer*        pInt = static_cast< Integer* > (list.GetAt(0));
  62  *
  63  *              if (pValue->Equals(Integer(1))
  64  *              {
  65  *                      // Must be here
  66  *              }
  67  *
  68  *              list.InsertAt(new Integer(4), 1);       // 1,4,2,3
  69  *
  70  *              list.Remove(Integer(3));                // 1,4,2
  71  *
  72  *              list.RemoveAt(0);                               // 4,2
  73  *
  74  *              list.Sort(IntegerComparer());   // 2,4
  75  *
  76  *              // Uses an enumerator to access elements in the list
  77  *              IEnumerator*    pEnum = list.GetEnumeratorN();
  78  *              Object* pObj = null;
  79  *              while (pEnum->MoveNext() == E_SUCCESS)
  80  *              {
  81  *                      pObj = pEnum->GetCurrent();
  82  *              }
  83  *
  84  *              delete pEnum;
  85  *
  86  *              // Deallocates all objects
  87  *              // Because the destructor calls RemoveAll() internally, you do not need to call RemoveAll() to destroy all elements at the end.
  88  *              // list.RemoveAll();
  89  *      }
  90  * @endcode
  91  */
  92 class _OSP_EXPORT_ LinkedList
  93         : public IList
  94         , public Object
  95 {
  96 public:
  97         using IList::Add;
  98         using IList::InsertAt;
  99         using IList::Remove;
 100         using IList::RemoveAt;
 101         using IList::RemoveItems;
 102         using IList::RemoveAll;
 103         using IList::SetAt;
 104         using IList::ContainsAll;
 105         /**
 106          * This is the default constructor for this class.
 107          *
 108          * @since 2.0
 109          *
 110          * @param[in]   deleter The function pointer to type of the element deleter
 111          * @remarks     To create an owning collection, set the element deleter value as @c SingleObjectDeleter. This gives the collection the ownership of elements and the collection will destroy elements. @n
 112          *                      On the other hand, to create a non-owning collection, you do not need to set the element deleter value, as @c NoOpDeleter is the default element deleter.
 113          *                      It means that you do not transfer the ownership of elements to the collection.
 114          * @see         NoOpDeleter()
 115          * @see         SingleObjectDeleter()
 116          * @see         ArrayDeleter()
 117          */
 118         explicit LinkedList(DeleterFunctionType deleter = NoOpDeleter);
 119
 120         /**
 121          * This destructor overrides Tizen::Base::Object::~Object().
 122          *
 123          * @since 2.0
 124          */
 125         virtual ~LinkedList(void);
 126
 127         /**
 128          * Adds the given object to the end of this list.
 129          *
 130          * @since 2.0
 131          *
 132          * @return              An error code
 133          * @param[in]   pObj                    An pointer to object to add
 134          * @exception   E_SUCCESS               The method is successful.
 135          * @exception   E_INVALID_ARG   The specified input parameter is invalid.
 136          * @remarks             This method performs a shallow copy. It adds just the pointer; not the element itself.
 137          * @see Remove()
 138          */
 139         virtual result Add(Object* pObj);
 140
 141         /**
 142          * Adds the elements of the given collection to the end of this list.
 143          *
 144          * @since 2.0
 145          *
 146          * @return              An error code
 147          * @param[in]   collection                      A collection to add
 148          * @exception   E_SUCCESS                       The method is successful.
 149          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
 150          *                                                                      the @c collection is modified during the operation of this method.
 151          * @remarks             This method performs a shallow copy. It adds just the pointer; not the element itself.
 152          * @see                 RemoveItems()
 153          */
 154         virtual result AddItems(const ICollection& collection);
 155
 156         /**
 157          * Gets an enumerator (an instance of the IEnumerator derived class) to the list.
 158          *
 159          * @since 2.0
 160          *
 161          * @return              An enumerator of the calling list object, @n
 162          *                              else @c null if an exception occurs
 163          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 164          * @see                 Tizen::Base::Collection::IEnumerator
 165          */
 166         virtual IEnumerator* GetEnumeratorN(void) const;
 167
 168         /**
 169          * Gets a bidirectional enumerator (an instance of the IBidirectionalEnumerator derived class) of this list.
 170          *
 171          * @since 2.0
 172          *
 173          * @return                      An instance of the IBidirectionalEnumerator derived class, @n
 174          *                                      else @c null if some exception occurs
 175          * @remarks                     Use this method to obtain a bidirectional enumerator (an instance of the IBidirectionalEnumerator derived class)
 176          *                                      to iterate over a collection (an instance of the IList derived class).
 177          *                                      The specific error code can be accessed using GetLastResult() method.
 178          * @see                         Tizen::Base::Collection::IBidirectionalEnumerator
 179          */
 180         virtual IBidirectionalEnumerator* GetBidirectionalEnumeratorN(void) const;
 181
 182         /**
 183          * Gets the object at the specified index of the calling list.
 184          *
 185          * @since 2.0
 186          *
 187          * @return              A pointer to the object at the specified index of the list, @n
 188          *                              else @c null if the index is not valid
 189          * @param[in]   index                                   The index of the object to read
 190          * @exception   E_SUCCESS                               The method is successful.
 191          * @exception   E_OUT_OF_RANGE                  The specified index is outside the bounds of the data structure, or
 192          *                                                                              the specified @c index is equal to or greater than the number of elements or less than @c 0.
 193          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 194          * @see                 SetAt()
 195          */
 196         virtual const Object* GetAt(int index) const;
 197
 198         /**
 199          * Gets the object at the specified index of the calling list.
 200          *
 201          * @since 2.0
 202          *
 203          * @return              A pointer to the object at the specified index of the list, @n
 204          *                              else @c null if the index is not valid
 205          * @param[in]   index                                   The index of the object to read
 206          * @exception   E_SUCCESS                               The method is successful.
 207          * @exception   E_OUT_OF_RANGE                  The specified index is outside the bounds of the data structure, or
 208          *                                                                              the specified @c index is equal to or greater than the number of elements or less than @c 0.
 209          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 210          * @see                 SetAt()
 211          */
 212         virtual Object* GetAt(int index);
 213
 214         /**
 215          * Gets an IList with the specified range from the calling list object.
 216          *
 217          * @since 2.0
 218          *
 219          * @return              An IList pointer if successful, @n
 220          *                              else @c null if an exception occurs
 221          * @param[in]   startIndex      The starting index of the range
 222          * @param[in]   count           The number of elements to read
 223          * @exception   E_SUCCESS                               The method is successful.
 224          * @exception   E_OUT_OF_RANGE                  Either of the following conditions has occurred: @n
 225          *                                                                              - The specified index is outside the bounds of the data structure. @n
 226          *                                                                              - The specified @c startIndex is either equal to or greater than the number of elements or less than @c 0. @n
 227          *                                                                              - The specified @c count is either greater than the number of elements starting from @c startIndex or less than @c 0.
 228          * @remarks             The IList stores just the pointers to the elements in the list, not the elements themselves.
 229          *                      The specific error code can be accessed using the GetLastResult() method.
 230          */
 231         virtual IList* GetItemsN(int startIndex, int count) const;
 232
 233         /**
 234          * Searches for an object in this list. @n
 235          * Gets the index of the object if found.
 236          *
 237          * @since 2.0
 238          *
 239          * @return              An error code
 240          * @param[in]   obj                     The object to locate
 241          * @param[out]  index           The index of the object
 242          * @exception   E_SUCCESS                       The method is successful.
 243          * @exception   E_OBJ_NOT_FOUND         The specified @c obj is not found.
 244          */
 245         virtual result IndexOf(const Object& obj, int& index) const;
 246
 247         /**
 248          * Searches for an object starting from the specified index. @n
 249          * Gets the index of the object if found.
 250          *
 251          * @since 2.0
 252          *
 253          * @return              An error code
 254          * @param[in]   obj             The object to locate
 255          * @param[in]   startIndex      The starting index for the search @n
 256          *                                                      It must be less than the number of elements.
 257          * @param[out]  index           The index of the object
 258          * @exception   E_SUCCESS                               The method is successful.
 259          * @exception   E_OUT_OF_RANGE                  The specified index is outside the bounds of the data structure, or
 260          *                                                                              the specified @c startIndex is either equal to or greater than the number of elements in the list or less than @c 0.
 261          * @exception   E_OBJ_NOT_FOUND                 The specified @c obj is not found.
 262          * @see                 LastIndexOf()
 263          */
 264         virtual result IndexOf(const Object& obj, int startIndex, int& index) const;
 265
 266         /**
 267          * Searches for an object within the specified range. @n
 268          * Gets the index of the object if found.
 269          *
 270          * @since 2.0
 271          *
 272          * @return              An error code
 273          * @param[in]   obj             The object to locate
 274          * @param[in]   startIndex      The starting index of the range
 275          * @param[in]   count           The number of elements to read
 276          * @param[out]  index           The index of the object
 277          * @exception   E_SUCCESS                               The method is successful.
 278          * @exception   E_OUT_OF_RANGE                  Either of the following conditions has occurred: @n
 279          *                                                                              - The specified index is outside the bounds of the data structure. @n
 280          *                                                                              - The specified @c startIndex is either equal to or greater than the number of elements in the list or less than @c 0. @n
 281          *                                                                              - The specified @c count is either greater than the number of elements starting from @c startIndex or less than @c 0.
 282          * @exception   E_OBJ_NOT_FOUND                 The specified @c obj is not found.
 283          * @see                 LastIndexOf()
 284          */
 285         virtual result IndexOf(const Object& obj, int startIndex, int count, int& index) const;
 286
 287         /**
 288          * Searches for the last occurrence of an object in this list. @n
 289          * Gets the index of the object if found.
 290          *
 291          * @since 2.0
 292          *
 293          * @return              An error code
 294          * @param[in]   obj             The object to locate
 295          * @param[out]  index           The index of the last occurrence of the specified object
 296          * @exception   E_SUCCESS                       The method is successful.
 297          * @exception   E_OBJ_NOT_FOUND         The specified @c obj is not found.
 298          * @see                 IndexOf()
 299          */
 300         virtual result LastIndexOf(const Object& obj, int& index) const;
 301
 302         /**
 303          * Inserts the object at the specified location.
 304          *
 305          * @since 2.0
 306          *
 307          * @return              An error code
 308          * @param[in]   pObj            The pointer to object to insert
 309          * @param[in]   index           The index at which the object must be inserted
 310          * @exception   E_SUCCESS                               The method is successful.
 311          * @exception   E_INVALID_ARG                   The specified input parameter is invalid.
 312          * @exception   E_OUT_OF_RANGE                  The specified index is outside the bounds of the data structure, or
 313          *                                                                              the specified @c index is greater than the number of elements or less than @c 0.
 314          * @remarks             If the @c index equals to the number of elements, then the new element
 315          *                              is added at the end of this list.
 316          *                      This method performs a shallow copy. It inserts just the pointer; not the element itself.
 317          * @see         Add()
 318          * @see         RemoveAt()
 319          */
 320         virtual result InsertAt(Object* pObj, int index);
 321
 322         /**
 323          * Inserts the elements of the collection at the specified location.
 324          *
 325          * @since 2.0
 326          *
 327          * @return              An error code
 328          * @param[in]   collection      The collection to insert elements from
 329          * @param[in]   startIndex      The starting index at which the elements must be inserted
 330          * @exception   E_SUCCESS                               The method is successful.
 331          * @exception   E_OUT_OF_RANGE                  The specified index is outside the bounds of the data structure, or
 332          *                                                                              the specified @c startIndex is either greater than the number of elements or less than @c 0.
 333          * @exception   E_INVALID_OPERATION             The current state of the instance prohibits the execution of the specified operation, or
 334          *                                                                              the @c collection is modified during the operation of this method.
 335          * @remarks             If the @c startIndex equals to the number of elements then the new elements
 336          *                              are added at the end of this list.
 337          *                              This method performs a shallow copy. It inserts just the pointer; not the element itself.
 338          * @see                 RemoveItems()
 339          * @see                 AddItems()
 340          */
 341         virtual result InsertItemsFrom(const ICollection& collection, int startIndex);
 342
 343         /**
 344          * Removes the first occurrence of the specified object from the list.
 345          *
 346          * @since 2.0
 347          *
 348          * @return              An error code
 349          * @param[in]   obj                             An object to remove
 350          * @exception   E_SUCCESS               The method is successful.
 351          * @exception   E_OBJ_NOT_FOUND The specified @c obj is not found.
 352          * @see                 Add()
 353          * @see                 RemoveAt()
 354          */
 355         virtual result Remove(const Object& obj);
 356
 357         /**
 358          * Removes the object at the specified location in the list.
 359          *
 360          * @since 2.0
 361          *
 362          * @return              An error code
 363          * @param[in]   index                           The index at which the object must be removed
 364          * @exception   E_SUCCESS                       The method is successful.
 365          * @exception   E_OUT_OF_RANGE          The specified index is outside the bounds of the data structure, or
 366          *                                                                      The specified @c index is equal to or greater than the number of elements or less than @c 0.
 367          * @see         InsertAt()
 368          */
 369         virtual result RemoveAt(int index);
 370
 371         /**
 372          * Removes all elements within the specified range from the list.
 373          *
 374          * @since 2.0
 375          *
 376          * @return              An error code
 377          * @param[in]   startIndex      The starting index of the range
 378          * @param[in]   count           The number of element to remove
 379          * @exception   E_SUCCESS                       The method is successful.
 380          * @exception   E_OUT_OF_RANGE          Either of the following conditions has occurred: @n
 381          *                                                                      - The specified index is outside the bounds of the data structure. @n
 382          *                                                                      - The specified @c startIndex is either equal to or greater than the number of elements or less than @c 0. @n
 383          *                                                                      - The specified @c count is either greater than the number of elements starting from @c startIndex or less than @c 0.
 384          * @see                 AddItems()
 385          * @see                 InsertItemsFrom()
 386          */
 387         virtual result RemoveItems(int startIndex, int count);
 388
 389         /**
 390          * Removes all the elements that are common in the specified @c collection
 391          * and the list.
 392          *
 393          * @since 2.0
 394          *
 395          * @return              An error code
 396          * @param[in]   collection                      The collection to remove from this list
 397          * @exception   E_SUCCESS                       The method is successful.
 398          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
 399          *                                                                      the @c collection is modified during the operation of this method.
 400          * @see                 Remove()
 401          * @see                 RemoveAt()
 402          */
 403         virtual result RemoveItems(const ICollection& collection);
 404
 405
 406         /**
 407          * Removes all of the object pointers in the collection and also removes all of the objects depending on the specified element deleter.
 408          * This method can be called before deleting the objects in a collection.
 409          *
 410          * @since 2.0
 411          *
 412          */
 413         virtual void RemoveAll(void);
 414
 415         /**
 416          * Replaces the object at the specified index with the given object.
 417          *
 418          * @since 2.0
 419          *
 420          * @return              An error code
 421          * @param[in]   pObj            The pointer to object to set
 422          * @param[in]   index           The index at which the object must be set
 423          * @exception   E_SUCCESS                       The method is successful.
 424          * @exception   E_INVALID_ARG           The specified input parameter is invalid.
 425          * @exception   E_OUT_OF_RANGE          The specified index is outside the bounds of the data structure, or
 426          *                                                                      the specified @c index is equal to or greater than the number of elements or less than @c 0.
 427          * @see                 GetAt()
 428          */
 429         virtual result SetAt(Object* pObj, int index);
 430
 431         /**
 432          * Sorts the elements of this list using the comparer provided.
 433          *
 434          * @since 2.0
 435          *
 436          * @return              An error code
 437          * @param[in]   comparer                The IComparer implementation to use when comparing elements
 438          * @exception   E_SUCCESS               The method is successful.
 439          * @exception   E_INVALID_ARG   The specified input parameter is invalid, or
 440          *                                                              the @c comparer is not valid.
 441          */
 442         virtual result Sort(const IComparer& comparer);
 443
 444         /**
 445          * Gets the number of objects currently stored in this list.
 446          *
 447          * @since 2.0
 448          *
 449          * @return              The number of objects currently stored in this list
 450          */
 451         virtual int GetCount(void) const;
 452
 453         /**
 454          * Checks whether the list contains the specified object.
 455          *
 456          * @since 2.0
 457          *
 458          * @return              @c true if the list contains the specified object, @n
 459          *                              else @c false
 460          * @param[in]   obj     The object to locate
 461          * @see                 ContainsAll()
 462          */
 463         virtual bool Contains(const Object& obj) const;
 464
 465         /**
 466          * Checks whether the list contains all the elements of the specified collection.
 467          *
 468          * @since 2.0
 469          *
 470          * @return              @c true if this list contains all of the elements in the specified collection, @n
 471          *                              else @c false
 472          * @param[in]   collection                      The collection to check for containment in this list
 473          * @exception   E_SUCCESS                       The method is successful.
 474          * @exception   E_INVALID_OPERATION     The current state of the instance prohibits the execution of the specified operation, or
 475          *                                                                      the @c collection is modified during the operation of this method.
 476          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 477          * @remarks             If the given @c collection is empty, this method will return @c true.
 478          * @see                 Contains()
 479          */
 480         virtual bool ContainsAll(const ICollection& collection) const;
 481
 482         /**
 483          * Compares the given object with the calling %LinkedList object.
 484          *
 485          * @since 2.0
 486          *
 487          * @return              @c true if the specified instance equals the current instance, @n
 488          *                              else @c false
 489          * @param[in]   obj The object to compare with the calling object
 490          * @remarks             This method returns @c true only if the specified object is also an instance of the %LinkedList class,
 491          *                              both lists have the same size, and all corresponding pairs of elements in the two lists are equal.
 492          *                              In other words, two lists are equal if they contain the same elements in the same order.
 493          */
 494         virtual bool Equals(const Object& obj) const;
 495
 496         /**
 497          * Gets the hash value of the current instance.
 498          *
 499          * @since 2.0
 500          *
 501          * @return      The hash value of the current instance
 502          * @remarks     The two Tizen::Base::Object::Equals() instances must return the same hash value. For better performance, @n
 503          *                      the used hash function must generate a random distribution for all inputs.
 504          */
 505         virtual int GetHashCode(void) const;
 506
 507         /**
 508          * Gets the element deleter of the collection.
 509          *
 510          * @since 2.0
 511          *
 512          * @return      A function pointer to the existing element deleter
 513          */
 514         virtual DeleterFunctionType GetDeleter(void) const;
 515
 516 private:
 517         /**
 518          * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
 519          *
 520          * @param[in]   list The %LinkedList object to initialize the new object
 521          */
 522         LinkedList(const LinkedList& list);
 523
 524         /**
 525          * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
 526          *
 527          * @param[in]   list An instance of %LinkedList
 528          */
 529         LinkedList& operator =(const LinkedList& list);
 530
 531         /**
 532          * Allocates and adds a memory block.
 533          *
 534          * @return              An error code
 535          * @param[in]   blockSize               The size of block to allocate
 536          * @exception   E_SUCCESS               The method is successful.
 537          */
 538         result AddBlock(int blockSize = DEFAULT_CAPACITY);
 539
 540         /**
 541          * Frees memory blocks of the list.
 542          *
 543          */
 544         void DeleteBlock(void);
 545
 546         /**
 547          * Inserts an object to the beginning of the %LinkedList.
 548          *
 549          * @return              An error code
 550          * @param[in]   pObj                    The pointer to object to insert
 551          * @exception   E_SUCCESS               The method is successful.
 552          */
 553         result InsertFirst(Object* pObj);
 554
 555         /**
 556          * Inserts an object to the end of the %LinkedList.
 557          *
 558          * @return              An error code
 559          * @param[in]   pObj                    The pointer to object to insert
 560          * @exception   E_SUCCESS               The method is successful.
 561          */
 562         result InsertLast(Object* pObj);
 563
 564         /**
 565          * Inserts an object after the specified node.
 566          *
 567          * @return              An error code
 568          * @param[in]   pObj                    The pointer to object to insert
 569          * @param[in]   pPrevNode               The node after which the object must inserted
 570          * @exception   E_SUCCESS               The method is successful.
 571          */
 572         result InsertNext(Object* pObj, _ListNode* pPrevNode);
 573
 574         /**
 575          * Gets a node from Available node list.
 576          *
 577          * @return              A pointer to a new List Node if successful, @n
 578          *                              else @c null if no node is available
 579          */
 580         _ListNode* GetNewNode(void);
 581
 582         /**
 583          * Gets the node at the specified index.
 584          *
 585          * @return              A node at the specified index
 586          * @param[in]   index The index of the node to read
 587          */
 588         _ListNode* GetNode(int index) const;
 589
 590         /**
 591          * Removes the specified node.
 592          *
 593          * @param[in]   pNode The pointer of the node to remove
 594          */
 595         void RemoveNode(_ListNode* pNode);
 596
 597         /**
 598          * Sets the element deleter of the collection.
 599          *
 600          * @since 2.0
 601          *
 602          * @param[in]   deleter A function pointer to the element deleter to set
 603          */
 604         virtual void SetDeleter(DeleterFunctionType deleter);
 605
 606         _ListNode* __pListHead;
 607         _ListNode* __pListTail;
 608         _ListNode* __pAvailableHead;
 609         _ListNode* __pAvailableTail;
 610         _ListNode* __pBlocks;
 611         int __count;
 612         int __capacity;
 613         int __modCount;
 614         static const int DEFAULT_CAPACITY = 10;
 615         DeleterFunctionType __deleter;
 616
 617         friend class _LinkedListEnumerator;
 618         friend class _LinkedListImpl;
 619         class _LinkedListImpl* __pLinkedListImpl;
 620
 621 }; // LinkedList
 622
 623 }}} // Tizen::Base::Collection
 624
 625 #endif // _FBASE_COL_LINKED_LIST_H_