inc/FBaseColLinkedList.h

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