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