inc/FBaseColQueueT.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                FBaseColQueueT.h
  19  * @brief               This is the header file for the %QueueT class.
  20  *
  21  * This header file contains the declarations of the %QueueT class.
  22  *
  23  */
  24 #ifndef _FBASE_COL_QUEUE_T_H_
  25 #define _FBASE_COL_QUEUE_T_H_
  26
  27 #include <FBaseObject.h>
  28 #include <FBaseResult.h>
  29 #include <FBaseColICollectionT.h>
  30
  31 namespace Tizen { namespace Base { namespace Collection
  32 {
  33
  34 template< class Type > class __QueueEnumeratorT;
  35
  36 /**
  37  * @class       QueueT
  38  * @brief       This class represents a template-based queue (a first-in-first-out collection of objects).
  39  *
  40  * @since 2.0
  41  *
  42  * The %QueueT class represents a template-based queue (a first-in-first-out collection of objects).
  43  *
  44  * For more information on the class features, see <a href="../org.tizen.native.appprogramming/html/guide/base/queue_stack.htm">Stack and Queue</a>.
  45  *
  46  * The following example demonstrates how to use the %QueueT 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::QueueTSample(void)
  56  *      {
  57  *              QueueT< String > queue;
  58  *              queue.Construct();
  59  *
  60  *              String str1(L"First");
  61  *              String str2(L"Second");
  62  *              String str3(L"Third");
  63  *
  64  *              queue.Enqueue(str1);
  65  *              queue.Enqueue(str2);
  66  *              queue.Enqueue(str3);
  67  *
  68  *              // Reads the element at the beginning
  69  *              String temp;
  70  *              queue.Peek(temp);               // temp: "First", queue.GetCount(): 3
  71  *
  72  *              // Reads and removes the element at the beginning
  73  *              queue.Dequeue(temp);    // temp: "First", queue.GetCount(): 2
  74  *      }
  75  * @endcode
  76  */
  77 template< class Type >
  78 class QueueT
  79         : public virtual ICollectionT< Type >
  80         , public Object
  81 {
  82 public:
  83         /**
  84          * The object is not fully constructed after this constructor is called. For full construction, @n
  85          * the Construct() method must be called right after calling this constructor.
  86          *
  87          * @since 2.0
  88          */
  89         QueueT(void)
  90                 : __capacity(0)
  91                 , __head(0)
  92                 , __tail(0)
  93                 , __pObjArray(null)
  94                 , __modCount(0)
  95         {
  96         }
  97
  98         /**
  99          * This destructor overrides Tizen::Base::Object::~Object().
 100          *
 101          * @since 2.0
 102          */
 103         virtual ~QueueT(void)
 104         {
 105                 __modCount++;
 106                 RemoveAll();
 107         }
 108
 109         /**
 110          * Initializes this instance of %QueueT with the specified capacity.
 111          *
 112          * @since 2.0
 113          *
 114          * @return              An error code
 115          * @param[in]   capacity                        The number of elements in the queue @n
 116          *                                  The default capacity is @c 10.
 117          * @exception   E_SUCCESS                       The method is successful.
 118          * @exception   E_OUT_OF_MEMORY         The memory is insufficient.
 119          * @exception   E_INVALID_ARG           Either of the following conditions has occurred:
 120          *                                                                      - The specified input parameter is invalid.
 121          *                                                                      - The specified @c capacity is negative.
 122          */
 123         result Construct(int capacity = DEFAULT_CAPACITY)
 124         {
 125                 TryReturn(capacity >= 0, E_INVALID_ARG, "[%s] The capacity(%d) MUST be greater than or equal to 0.", GetErrorMessage(E_INVALID_ARG), capacity);
 126
 127                 if (capacity > 0)
 128                 {
 129                         __pObjArray = new Type[capacity];
 130                         TryReturn(__pObjArray != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 131                 }
 132                 __capacity = capacity;
 133
 134                 return E_SUCCESS;
 135         }
 136
 137         /**
 138          * Initializes this instance of %QueueT that contains the elements of the specified @c collection. @n
 139          * The capacity of the queue is the same as the number of elements copied.
 140          *
 141          * @since 2.0
 142          *
 143          * @return              An error code
 144          * @param[in]   collection                      The collection to copy the elements from
 145          * @exception   E_SUCCESS                       The method is successful.
 146          * @exception   E_OUT_OF_MEMORY         The memory is insufficient.
 147          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
 148          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
 149          *                                                                      - The specified @c collection is modified during the operation of this method.
 150          * @see                 QueueT()
 151          */
 152         result Construct(const ICollectionT< Type >& collection)
 153         {
 154                 result r = E_SUCCESS;
 155
 156                 IEnumeratorT< Type >* pEnum = null;
 157                 if (collection.GetCount() > 0)
 158                 {
 159                         ICollectionT< Type >* pCol = const_cast< ICollectionT< Type >* >(&collection);
 160                         pEnum = pCol->GetEnumeratorN();
 161                         TryCatch(pEnum != null, r = GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
 162
 163                         while (true)
 164                         {
 165                                 Type temp;
 166                                 r = pEnum->MoveNext();
 167
 168                                 if (E_OUT_OF_RANGE == r)
 169                                 {
 170                                         r = E_SUCCESS;
 171                                         break;
 172                                 }
 173                                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 174
 175                                 r = pEnum->GetCurrent(temp);
 176                                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 177
 178                                 r = Enqueue(temp);
 179                                 TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 180                         }
 181                 }
 182
 183                 if (null != pEnum)
 184                 {
 185                         delete pEnum;
 186                 }
 187                 return r;
 188
 189 CATCH:
 190                 RemoveAll();
 191
 192                 if (null != pEnum)
 193                 {
 194                         delete pEnum;
 195                 }
 196                 return r;
 197         }
 198
 199         /**
 200          * Reads and removes the element at the beginning of this queue.
 201          *
 202          * @since 2.0
 203          *
 204          * @return              An error code
 205          * @param[out]  obj                     The element at the beginning of this queue
 206          * @exception   E_SUCCESS       The method is successful.
 207          * @exception   E_UNDERFLOW     Either of the following conditions has occurred:
 208          *                                                      - The operation (arithmetic/casting/conversion) has caused an underflow.
 209          *                                                      - The queue is empty.
 210          * @see                 Enqueue()
 211          */
 212         virtual result Dequeue(Type& obj)
 213         {
 214                 if (__head <= __tail)
 215                         return E_UNDERFLOW;
 216
 217                 __modCount++;
 218                 int index = (__tail) % __capacity;
 219                 obj = __pObjArray[index];
 220
 221                 __tail++;
 222
 223                 return E_SUCCESS;
 224         }
 225
 226         /**
 227          * Inserts an object at the end of this queue.
 228          *
 229          * @since 2.0
 230          *
 231          * @return              An error code
 232          * @param[in]   obj                             The object to add to this queue
 233          * @exception   E_SUCCESS               The method is successful.
 234          * @exception   E_OUT_OF_MEMORY The memory is insufficient.
 235          * @see                 Dequeue()
 236          */
 237         virtual result Enqueue(const Type& obj)
 238         {
 239                 if (null == __pObjArray)
 240                 {
 241                         __pObjArray = new Type[DEFAULT_CAPACITY];
 242                         TryReturn(__pObjArray != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 243                         __capacity = DEFAULT_CAPACITY;
 244                 }
 245                 else if ((__head - __tail) >= __capacity)
 246                 {
 247                         Type* pArrayTemp = new Type[__capacity + DEFAULT_CAPACITY];
 248                         TryReturn(pArrayTemp != null, E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 249
 250                         for (int i = 0, j = __tail; i < __capacity; i++, j++)
 251                         {
 252                                 pArrayTemp[i] = __pObjArray[j % __capacity];
 253                         }
 254
 255                         delete[] __pObjArray;
 256                         __pObjArray = pArrayTemp;
 257                         __tail = 0;
 258                         __head = __capacity;
 259                         __capacity += DEFAULT_CAPACITY;
 260                 }
 261
 262                 __modCount++;
 263                 __pObjArray[__head % __capacity] = obj;
 264                 __head++;
 265
 266                 return E_SUCCESS;
 267         }
 268
 269         /**
 270          * Removes all the elements from this queue.
 271          *
 272          * @since 2.0
 273          */
 274         virtual void RemoveAll(void)
 275         {
 276                 if (__pObjArray != null)
 277                 {
 278                         delete[] __pObjArray;
 279                 }
 280
 281                 __pObjArray = null;
 282
 283                 __modCount++;
 284                 __capacity = 0;
 285                 __head = 0;
 286                 __tail = 0;
 287         }
 288
 289         /**
 290          * Gets the enumerator of this queue.
 291          *
 292          * @since 2.0
 293          *
 294          * @return              The enumerator (an instance of the IEnumeratorT derived class) of this queue, @n
 295          *                              else @c null if an exception occurs
 296          * @exception   E_SUCCESS               The method is successful.
 297          * @exception   E_OUT_OF_MEMORY The memory is insufficient.
 298          * @remarks             The specific error code can be accessed using the GetLastResult() method.
 299          */
 300         virtual IEnumeratorT< Type >* GetEnumeratorN(void) const
 301         {
 302                 ClearLastResult();
 303
 304                 result r = E_SUCCESS;
 305
 306                 __QueueEnumeratorT< Type >* pEnum = new __QueueEnumeratorT< Type >(*this, __modCount);
 307                 TryCatch(pEnum != null, r = E_OUT_OF_MEMORY, "[%s] Memory allocation failed.", GetErrorMessage(E_OUT_OF_MEMORY));
 308
 309                 return pEnum;
 310
 311 CATCH:
 312                 SetLastResult(r);
 313                 return null;
 314         }
 315
 316         /**
 317          * Reads the element at the beginning of this queue without removing it.
 318          *
 319          * @since 2.0
 320          *
 321          * @return              An error code
 322          * @param[out]  obj                     The element at the beginning of this queue
 323          * @exception   E_SUCCESS       The method is successful.
 324          * @exception   E_UNDERFLOW     Either of the following conditions has occurred:
 325          *                                                      - The operation (arithmetic/casting/conversion) has caused an underflow.
 326          *                                                      - The queue is empty.
 327          */
 328         virtual result Peek(Type& obj) const
 329         {
 330                 if (__head <= __tail)
 331                 {
 332                         return E_UNDERFLOW;
 333                 }
 334
 335                 obj = __pObjArray[__tail % __capacity];
 336
 337                 return E_SUCCESS;
 338         }
 339
 340         /**
 341          * Gets the number of objects currently stored in this queue.
 342          *
 343          * @since 2.0
 344          *
 345          * @return              The number of objects currently stored in this queue
 346          */
 347         virtual int GetCount(void) const
 348         {
 349                 return __head - __tail;
 350         }
 351
 352         /**
 353          * Checks whether this queue contains the specified object.
 354          *
 355          * @since 2.0
 356          *
 357          * @return              @c true if this queue contains the specified object, @n
 358          *                              else @c false
 359          * @param[in]   obj  The object to locate
 360          */
 361         virtual bool Contains(const Type& obj) const
 362         {
 363                 bool out = false;
 364                 for (int i = 0; i < GetCount(); i++)
 365                 {
 366                         if (__pObjArray[(__tail + i) % __capacity] == obj)
 367                         {
 368                                 out = true;
 369                                 break;
 370                         }
 371                 }
 372
 373                 return out;
 374         }
 375
 376         /**
 377          * Checks whether this queue contains all of the elements in the specified collection.
 378          *
 379          * @since 2.0
 380          *
 381          * @return              An error code
 382          * @param[in]   collection                      The collection to locate
 383          * @param[out]  out                                     Set to @c true if this queue contains all of the elements in the specified collection, @n
 384          *                                                                      else @c false
 385          * @exception   E_SUCCESS                       The method is successful.
 386          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
 387          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
 388          *                                                                      - The specified @c collection is modified during the operation of this method.
 389          * @exception   E_OUT_OF_MEMORY         The memory is insufficient.
 390          */
 391         virtual result ContainsAll(const ICollectionT< Type >& collection, bool& out) const
 392         {
 393                 result r = E_SUCCESS;
 394
 395                 ICollectionT< Type >* pCol = const_cast< ICollectionT< Type >* >(&collection);
 396                 IEnumeratorT< Type >* pEnum = pCol->GetEnumeratorN();
 397                 TryCatch(pEnum != null, r = GetLastResult(), "[%s] Propagating.", GetErrorMessage(GetLastResult()));
 398
 399                 while (true)
 400                 {
 401                         Type temp;
 402                         r = pEnum->MoveNext();
 403
 404                         if (E_OUT_OF_RANGE == r)
 405                         {
 406                                 r = E_SUCCESS;
 407                                 out = true;
 408                                 break;
 409                         }
 410                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 411
 412                         r = pEnum->GetCurrent(temp);
 413                         TryCatch(r == E_SUCCESS, , "[%s] Propagating.", GetErrorMessage(r));
 414
 415                         if (false == Contains(temp))
 416                         {
 417                                 out = false;
 418                                 break;
 419                         }
 420                 }
 421
 422                 if (null != pEnum)
 423                 {
 424                         delete pEnum;
 425                 }
 426                 return r;
 427
 428 CATCH:
 429                 if (null != pEnum)
 430                 {
 431                         delete pEnum;
 432                 }
 433                 return r;
 434         }
 435
 436         /**
 437          * Compares the specified instance to the current instance for equality.
 438          *
 439          * @since 2.0
 440          *
 441          * @return              @c true if the specified instance equals the current instance, @n
 442          *                              else @c false
 443          * @param[in]   obj The object to compare with the current instance
 444          * @remarks     This method returns @c true if and only if the specified object is also an instance of the %QueueT class,
 445          *                              both queues have the same size, and all the corresponding pairs of elements in the two queues are equal. @n
 446          *                              In other words, two queues are equal if they contain the same elements in the same order.
 447          */
 448         virtual bool Equals(const Object& obj) const
 449         {
 450                 bool out = true;
 451
 452                 const QueueT< Type >* other = dynamic_cast< const QueueT< Type >* >(&obj);
 453                 if (null == other)
 454                 {
 455                         out = false;
 456                 }
 457                 else if (other == this)
 458                 {
 459                         out = true;
 460                 }
 461                 else if (GetCount() != other->GetCount())
 462                 {
 463                         out = false;
 464                 }
 465                 else
 466                 {
 467                         for (int i = 0; i < GetCount(); i++)
 468                         {
 469                                 if (!(__pObjArray[(__tail + i) % __capacity] == other->__pObjArray[(other->__tail + i) % other->__capacity]))
 470                                 {
 471                                         out = false;
 472                                         break;
 473                                 }
 474                         }
 475                 }
 476
 477                 return out;
 478         }
 479
 480         /**
 481          * Gets the hash value of the current instance.
 482          *
 483          * @since 2.0
 484          *
 485          * @return      The hash value of the current instance
 486          * @remarks     The two Tizen::Base::Object::Equals() instances must return the same hash value. @n
 487          *                      For better performance, the used hash function must generate a random distribution for all the inputs.
 488          */
 489         virtual int GetHashCode(void) const
 490         {
 491                 int hash = 0;
 492                 int count = GetCount();
 493                 for (int i = 0; i < count; i++)
 494                 {
 495                         if (&(__pObjArray[(__tail + i) % __capacity]) != null)
 496                         {
 497                                 hash += reinterpret_cast< int >(&(__pObjArray[(__tail + i) % __capacity]));
 498                         }
 499                 }
 500                 return hash;
 501         }
 502
 503 private:
 504         /**
 505          * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
 506          *
 507          * @param[in]   queue The specified instance of %QueueT to initialize the current instance
 508          */
 509         QueueT(const QueueT< Type >& queue);
 510
 511         /**
 512          * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
 513          *
 514          * @param[in]   queue An instance of %QueueT
 515          */
 516         QueueT< Type >& operator =(const QueueT< Type >& queue);
 517
 518         int __capacity;
 519         int __head;
 520         int __tail;
 521         Type* __pObjArray;
 522         int __modCount;
 523         static const int DEFAULT_CAPACITY = 10;
 524
 525         friend class __QueueEnumeratorT< Type >;
 526
 527 }; // QueueT
 528
 529 //
 530 // @class       __QueueEnumeratorT
 531 // @brief       This class is an implementation of IEnumeratorT for %QueueT.
 532 // @since 2.0
 533 //
 534 template< class Type >
 535 class __QueueEnumeratorT
 536         : public IEnumeratorT< Type >
 537         , public Object
 538 {
 539 public:
 540         /**
 541          * Initializes this instance of __QueueEnumeratorT with the specified parameters.
 542          *
 543          * @since 2.0
 544          *
 545          * @param[in]   queue           The queue to enumerate
 546          * @param[in]   modeCount       The modification count to detect the change in the queue
 547          */
 548         __QueueEnumeratorT(const QueueT< Type >& queue, int modeCount)
 549                 : __queue(queue)
 550                 , __modCount(modeCount)
 551                 , __position(-1)
 552         {
 553         }
 554
 555         /**
 556          * This is the destructor for this class.
 557          *
 558          * @since 2.0
 559          */
 560         virtual ~__QueueEnumeratorT(void)
 561         {
 562         }
 563
 564         /**
 565          * Gets the current object in the queue.
 566          *
 567          * @since 2.0
 568          *
 569          * @return              An error code
 570          * @param[out]  obj                                     The current object
 571          * @exception   E_INVALID_OPERATION             Either of the following conditions has occurred:
 572          *                                                                              - The current state of the instance prohibits the execution of the specified operation. @n
 573          *                                                                              - This enumerator is currently positioned before the first element or
 574          *                                                                              past the last element.
 575          *                                                                              - The queue is modified after this enumerator is created.
 576          * @exception   E_SUCCESS                               The method is successful.
 577          */
 578         result GetCurrent(Type& obj) const
 579         {
 580                 TryReturn((__modCount == __queue.__modCount), E_INVALID_OPERATION,
 581                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
 582                 TryReturn((__position >= __queue.__tail) && (__position < __queue.__head), E_INVALID_OPERATION,
 583                         "[%s] Current position is before the first element or past the last element.", GetErrorMessage(E_INVALID_OPERATION));
 584
 585                 obj = __queue.__pObjArray[__position % __queue.__capacity];
 586
 587                 return E_SUCCESS;
 588         }
 589
 590         /**
 591          * Moves this enumerator to the next element of the queue. @n
 592          * When this enumerator is first created or after the call to Reset(),
 593          * the first call to MoveNext() positions this enumerator to the first element in the queue.
 594          *
 595          * @since 2.0
 596          *
 597          * @return              An error code
 598          * @exception   E_SUCCESS                       The method is successful.
 599          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
 600          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
 601          *                                                                      - The queue is modified after this enumerator is created.
 602          * @exception   E_OUT_OF_RANGE          The enumerator has passed the end of the queue.
 603          * @see                 Reset()
 604          */
 605         result MoveNext(void)
 606         {
 607                 TryReturn((__modCount == __queue.__modCount), E_INVALID_OPERATION,
 608                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
 609
 610                 if ((__position + 1) >= __queue.__head)
 611                 {
 612                         return E_OUT_OF_RANGE;
 613                 }
 614                 else
 615                 {
 616                         if (__position == -1)
 617                         {
 618                                 __position = __queue.__tail;
 619                         }
 620                         else
 621                         {
 622                                 __position++;
 623                         }
 624                 }
 625
 626                 return E_SUCCESS;
 627         }
 628
 629         /**
 630          * Positions this enumerator before the first element in the queue.
 631          *
 632          * @since 2.0
 633          *
 634          * @return              An error code
 635          * @exception   E_SUCCESS                       The method is successful.
 636          * @exception   E_INVALID_OPERATION     Either of the following conditions has occurred:
 637          *                                                                      - The current state of the instance prohibits the execution of the specified operation.
 638          *                                                                      - The queue is modified after this enumerator is created.
 639          */
 640         result Reset(void)
 641         {
 642                 TryReturn((__modCount == __queue.__modCount), E_INVALID_OPERATION,
 643                         "[%s] The source collection is modified after the creation of this enumerator.", GetErrorMessage(E_INVALID_OPERATION));
 644
 645                 __position = -1;
 646
 647                 return E_SUCCESS;
 648         }
 649
 650 private:
 651         const QueueT< Type >& __queue;
 652         int __modCount;
 653         int __position;
 654
 655 }; // __QueueEnumeratorT
 656
 657 }}} // Tizen::Base::Collection
 658
 659 #endif //_FBASE_COL_QUEUE_T_H_