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