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