2 // Copyright (c) 2012 Samsung Electronics Co., Ltd.
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
8 // http://www.apache.org/licenses/LICENSE-2.0
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.
18 * @file FBaseColLinkedList.h
19 * @brief This is the header file for the %LinkedList class.
21 * This header file contains the declarations of the %LinkedList class.
23 #ifndef _FBASE_COL_LINKED_LIST_H_
24 #define _FBASE_COL_LINKED_LIST_H_
26 #include <FBaseColIComparer.h>
27 #include <FBaseColIList.h>
29 namespace Tizen { namespace Base { namespace Collection
36 * @brief This class represents a collection of objects that can be individually accessed by an index.
40 * The %LinkedList class represents a collection of objects that can be individually accessed by an index.
42 * 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 * The following example demonstrates how to use the %LinkedList class.
49 * using namespace Tizen::Base;
50 * using namespace Tizen::Base::Collection;
53 * MyClass::LinkedListSample(void)
55 * LinkedList list(SingleObjectDeleter);
57 * list.Add(new Integer(1)); // 1
58 * list.Add(new Integer(2)); // 1,2
59 * list.Add(new Integer(3)); // 1,2,3
61 * Integer* pInt = static_cast< Integer* > (list.GetAt(0));
63 * if (pValue->Equals(Integer(1))
68 * list.InsertAt(new Integer(4), 1); // 1,4,2,3
70 * list.Remove(Integer(3)); // 1,4,2
72 * list.RemoveAt(0); // 4,2
74 * list.Sort(IntegerComparer()); // 2,4
76 * // Uses an enumerator to access elements in the list
77 * IEnumerator* pEnum = list.GetEnumeratorN();
78 * Object* pObj = null;
79 * while (pEnum->MoveNext() == E_SUCCESS)
81 * pObj = pEnum->GetCurrent();
86 * // Deallocates all objects
87 * // Because the destructor calls RemoveAll() internally, you do not need to call RemoveAll() to destroy all elements at the end.
88 * // list.RemoveAll();
92 class _OSP_EXPORT_ LinkedList
98 using IList::InsertAt;
100 using IList::RemoveAt;
101 using IList::RemoveItems;
102 using IList::RemoveAll;
104 using IList::ContainsAll;
106 * This is the default constructor for this class.
110 * @param[in] deleter A function pointer to the type of the element deleter
111 * @remarks To create an owing collection, set the element deleter value as @c SingleObjectDeleter. @n
112 * This gives the collection the ownership of the elements and the collection destroys the elements. @n
113 * On the other hand, to create a non-owning collection, do not set the element deleter value, as @c NoOpDeleter is the default element deleter. @n
114 * It means that you do not transfer the ownership of the elements to the collection.
116 * @see SingleObjectDeleter()
117 * @see ArrayDeleter()
119 explicit LinkedList(DeleterFunctionType deleter = NoOpDeleter);
122 * This destructor overrides Tizen::Base::Object::~Object().
126 virtual ~LinkedList(void);
129 * Adds the given object to the end of this list.
133 * @return An error code
134 * @param[in] pObj A pointer to the 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 and not the element itself.
140 virtual result Add(Object* pObj);
143 * Adds the elements of the given collection to the end of this list.
147 * @return An error code
148 * @param[in] collection The collection to add
149 * @exception E_SUCCESS The method is successful.
150 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
151 * - The current state of the instance prohibits the execution of the specified operation.
152 * - The specified @c collection is modified during the operation of this method.
153 * @remarks This method performs a shallow copy. It adds just the pointer and not the element itself.
156 virtual result AddItems(const ICollection& collection);
159 * Gets the enumerator (an instance of the IEnumerator derived class) of the list.
163 * @return The enumerator of the calling list object, @n
164 * else @c null if an exception occurs
165 * @remarks The specific error code can be accessed using the GetLastResult() method.
167 virtual IEnumerator* GetEnumeratorN(void) const;
170 * Gets the bidirectional enumerator (an instance of the IBidirectionalEnumerator derived class) of the list.
174 * @return An instance of the IBidirectionalEnumerator derived class, @n
175 * else @c null if an exception occurs
177 * - Use this method to obtain a bidirectional enumerator (an instance of the IBidirectionalEnumerator derived class)
178 * to iterate over a collection (an instance of the IList derived class).
179 * - The specific error code can be accessed using GetLastResult() method.
181 virtual IBidirectionalEnumerator* GetBidirectionalEnumeratorN(void) const;
184 * Gets the object at the specified @c index of the calling list.
188 * @return A pointer to the object at the specified index of the list, @n
189 * else @c null if the index is invalid
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 Either of the following conditions has occurred:
193 * - The specified @c index is outside the bounds of the data structure.
194 * - The specified @c index is either greater than or equal to the number of elements.
195 * - The specified @c index is less than @c 0.
196 * @remarks The specific error code can be accessed using the GetLastResult() method.
199 virtual const Object* GetAt(int index) const;
202 * Gets the object at the specified @c index of the calling list.
206 * @return A pointer to the object at the specified index of the list, @n
207 * else @c null if the index is invalid
208 * @param[in] index The index of the object to read
209 * @exception E_SUCCESS The method is successful.
210 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred:
211 * - The specified @c index is outside the bounds of the data structure.
212 * - The specified @c index is either greater than or equal to the number of elements.
213 * - The specified @c index is less than @c 0.
214 * @remarks The specific error code can be accessed using the GetLastResult() method.
217 virtual Object* GetAt(int index);
220 * Gets the IList with the specified range from the calling list object.
224 * @return An IList pointer , @n
225 * else @c null if an exception occurs
226 * @param[in] startIndex The starting index of the range
227 * @param[in] count The number of elements to read
228 * @exception E_SUCCESS The method is successful.
229 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred:
230 * - The specified @c index is outside the bounds of the data structure.
231 * - The specified @c startIndex is either greater than or equal to the number of elements.
232 * - The specified @c startIndex is less than @c 0.
233 * - The specified @c count is either greater than the number of elements starting from @c startIndex.
234 * - The specified @c count is less than @c 0.
236 * - The IList stores just the pointers to the elements in the list and not the elements themselves.
237 * - The specific error code can be accessed using the GetLastResult() method.
239 virtual IList* GetItemsN(int startIndex, int count) const;
242 * Searches for an object in this list. @n
243 * Gets the @c index of the object if found.
247 * @return An error code
248 * @param[in] obj The object to locate
249 * @param[out] index The index of the object
250 * @exception E_SUCCESS The method is successful.
251 * @exception E_OBJ_NOT_FOUND The specified @c obj has not been found.
253 virtual result IndexOf(const Object& obj, int& index) const;
256 * Searches for an object starting from the specified @c startIndex. @n
257 * Gets the @c index of the object if found.
261 * @return An error code
262 * @param[in] obj The object to locate
263 * @param[in] startIndex The starting index for the search @n
264 * It must be less than the number of elements.
265 * @param[out] index The index of the object
266 * @exception E_SUCCESS The method is successful.
267 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred:
268 * - The specified @c index is outside the bounds of the data structure.
269 * - The specified @c startIndex is either greater than or equal to the number of elements in the list.
270 * - The specified @c startIndex is less than @c 0.
271 * @exception E_OBJ_NOT_FOUND The specified @c obj has not been found.
274 virtual result IndexOf(const Object& obj, int startIndex, int& index) const;
277 * Searches for an object within the specified range. @n
278 * Gets the @c index of the object if found.
282 * @return An error code
283 * @param[in] obj The object to locate
284 * @param[in] startIndex The starting index of the range
285 * @param[in] count The number of elements to read
286 * @param[out] index The index of the object
287 * @exception E_SUCCESS The method is successful.
288 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred:
289 * - The specified @c index is outside the bounds of the data structure.
290 * - The specified @c startIndex is either greater than or equal to the number of elements in the list.
291 * - The specified @c startIndex is less than @c 0.
292 * - The specified @c count is greater than the number of elements starting from @c startIndex.
293 * - The specified @c count is less than @c 0.
294 * @exception E_OBJ_NOT_FOUND The specified @c obj has not been found.
297 virtual result IndexOf(const Object& obj, int startIndex, int count, int& index) const;
300 * Searches for the last occurrence of an object in this list. @n
301 * Gets the @c index of the object if found.
305 * @return An error code
306 * @param[in] obj The object to locate
307 * @param[out] index The index of the last occurrence of the specified object
308 * @exception E_SUCCESS The method is successful.
309 * @exception E_OBJ_NOT_FOUND The specified @c obj has not been found.
312 virtual result LastIndexOf(const Object& obj, int& index) const;
315 * Inserts the object at the specified location.
319 * @return An error code
320 * @param[in] pObj A pointer to the object to insert
321 * @param[in] index The index at which the object is inserted
322 * @exception E_SUCCESS The method is successful.
323 * @exception E_INVALID_ARG A specified input parameter is invalid.
324 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred:
325 * - The specified @c index is outside the bounds of the data structure.
326 * - The specified @c index is greater than the number of elements.
327 * - The specified @c index is less than @c 0.
329 * - If the @c index is equal to the number of elements, then the new elements
330 * is added at the end of this list.
331 * - This method performs a shallow copy. It inserts just the pointer and not the element itself.
335 virtual result InsertAt(Object* pObj, int index);
338 * Inserts the elements of the collection at the specified location.
342 * @return An error code
343 * @param[in] collection The collection to insert elements from
344 * @param[in] startIndex The starting index at which the elements are inserted
345 * @exception E_SUCCESS The method is successful.
346 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred:
347 * - The specified index is outside the bounds of the data structure.
348 * - The specified @c startIndex is greater than the number of elements.
349 * - The specified @c startIndex is less than @c 0.
350 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
351 * - The current state of the instance prohibits the execution of the specified operation.
352 * - The specified @c collection is modified during the operation of this method.
354 * - If the specified @c startIndex is equal to the number of elements, then the new elements
355 * are added at the end of this list.
356 * - This method performs a shallow copy. It inserts just the pointer and not the element itself.
360 virtual result InsertItemsFrom(const ICollection& collection, int startIndex);
363 * Removes the first occurrence of the specified object from the list.
367 * @return An error code
368 * @param[in] obj The object to remove
369 * @exception E_SUCCESS The method is successful.
370 * @exception E_OBJ_NOT_FOUND The specified @c obj has not been found.
374 virtual result Remove(const Object& obj);
377 * Removes the object at the specified location in the list.
381 * @return An error code
382 * @param[in] index The index at which the object is removed
383 * @exception E_SUCCESS The method is successful.
384 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred:
385 * - The specified @c index is outside the bounds of the data structure.
386 * - The specified @c index is either greater than or equal to the number of elements.
387 * - The specified @c index is less than @c 0.
390 virtual result RemoveAt(int index);
393 * Removes all the elements within the specified range from the list.
397 * @return An error code
398 * @param[in] startIndex The starting index of the range
399 * @param[in] count The number of elements to remove
400 * @exception E_SUCCESS The method is successful.
401 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred:
402 * - The specified @c index is outside the bounds of the data structure.
403 * - The specified @c startIndex is either greater than or equal to the number of elements.
404 * - The specified @c startIndex is less than @c 0.
405 * - The specified @c count is greater than the number of elements starting from @c startIndex.
406 * - The specified @c count is less than @c 0.
408 * @see InsertItemsFrom()
410 virtual result RemoveItems(int startIndex, int count);
413 * Removes all the elements that are common in the specified @c collection
418 * @return An error code
419 * @param[in] collection The collection to remove from this list
420 * @exception E_SUCCESS The method is successful.
421 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
422 * - The current state of the instance prohibits the execution of the specified operation.
423 * - The specified @c collection is modified during the operation of this method.
427 virtual result RemoveItems(const ICollection& collection);
431 * Removes all of the object pointers in the collection and also removes all the objects depending on the specified element deleter.
432 * This method can be called before deleting the objects in a collection.
437 virtual void RemoveAll(void);
440 * Replaces the object at the specified @c index with the given object.
444 * @return An error code
445 * @param[in] pObj A pointer to the object to set
446 * @param[in] index The index at which the object is set
447 * @exception E_SUCCESS The method is successful.
448 * @exception E_INVALID_ARG A specified input parameter is invalid.
449 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred:
450 * - The specified @c index is outside the bounds of the data structure.
451 * - The specified @c index is either greater than or equal to the number of elements.
452 * - The specified @c index is less than @c 0.
455 virtual result SetAt(Object* pObj, int index);
458 * Sorts the elements of this list using the @c comparer provided.
462 * @return An error code
463 * @param[in] comparer The IComparer implementation to use when comparing the elements
464 * @exception E_SUCCESS The method is successful.
465 * @exception E_INVALID_ARG Either of the following conditions has occurred:
466 * - The specified input parameter is invalid.
467 * - The specified @c comparer is invalid.
469 virtual result Sort(const IComparer& comparer);
472 * Gets the number of objects currently stored in this list.
476 * @return The number of objects currently stored in this list
478 virtual int GetCount(void) const;
481 * Checks whether the list contains the specified object.
485 * @return @c true if the list contains the specified object, @n
487 * @param[in] obj The object to locate
490 virtual bool Contains(const Object& obj) const;
493 * Checks whether the list contains all the elements of the specified @c collection.
497 * @return @c true if this list contains all the elements in the specified collection, @n
499 * @param[in] collection The collection to check for containment in this list
500 * @exception E_SUCCESS The method is successful.
501 * @exception E_INVALID_OPERATION Either of the following conditions has occurred:
502 * - The current state of the instance prohibits the execution of the specified operation.
503 * - The @c collection is modified during the operation of this method.
505 * - The specific error code can be accessed using the GetLastResult() method.
506 * - If the given @c collection is empty, this method returns @c true.
509 virtual bool ContainsAll(const ICollection& collection) const;
512 * Compares the given object with the calling %LinkedList object.
516 * @return @c true if the specified instance equals the current instance, @n
518 * @param[in] obj The object to compare with the calling object
520 * - This method returns @c true only if the specified object is also an instance of the %LinkedList class,
521 * both lists have the same size, and all corresponding pairs of elements in the two lists are equal.
522 * - In other words, two lists are equal if they contain the same elements in the same order.
524 virtual bool Equals(const Object& obj) const;
527 * Gets the hash value of the current instance.
531 * @return The hash value of the current instance
532 * @remarks The two Tizen::Base::Object::Equals() instances must return the same hash value. @n
533 * For better performance, the used hash function must generate a random distribution for all the inputs.
535 virtual int GetHashCode(void) const;
538 * Gets the element deleter of the collection.
542 * @return A function pointer to the existing element deleter
544 virtual DeleterFunctionType GetDeleter(void) const;
548 * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
550 * @param[in] list The %LinkedList object to initialize the new object
552 LinkedList(const LinkedList& list);
555 * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
557 * @param[in] list An instance of %LinkedList
559 LinkedList& operator =(const LinkedList& list);
562 * Allocates and adds a memory block.
564 * @return An error code
565 * @param[in] blockSize The size of block to allocate
566 * @exception E_SUCCESS The method is successful.
568 result AddBlock(int blockSize = DEFAULT_CAPACITY);
571 * Frees memory blocks of the list.
574 void DeleteBlock(void);
577 * Inserts an object to the beginning of the %LinkedList.
579 * @return An error code
580 * @param[in] pObj The pointer to object to insert
581 * @exception E_SUCCESS The method is successful.
583 result InsertFirst(Object* pObj);
586 * Inserts an object to the end of the %LinkedList.
588 * @return An error code
589 * @param[in] pObj The pointer to object to insert
590 * @exception E_SUCCESS The method is successful.
592 result InsertLast(Object* pObj);
595 * Inserts an object after the specified node.
597 * @return An error code
598 * @param[in] pObj The pointer to object to insert
599 * @param[in] pPrevNode The node after which the object must inserted
600 * @exception E_SUCCESS The method is successful.
602 result InsertNext(Object* pObj, _ListNode* pPrevNode);
605 * Gets a node from Available node list.
607 * @return A pointer to a new List Node, @n
608 * else @c null if no node is available
610 _ListNode* GetNewNode(void);
613 * Gets the node at the specified index.
615 * @return A node at the specified index
616 * @param[in] index The index of the node to read
618 _ListNode* GetNode(int index) const;
621 * Removes the specified node.
623 * @param[in] pNode The pointer of the node to remove
625 void RemoveNode(_ListNode* pNode);
628 * Sets the element deleter of the collection.
632 * @param[in] deleter A function pointer to the element deleter to set
634 virtual void SetDeleter(DeleterFunctionType deleter);
636 _ListNode* __pListHead;
637 _ListNode* __pListTail;
638 _ListNode* __pAvailableHead;
639 _ListNode* __pAvailableTail;
640 _ListNode* __pBlocks;
644 static const int DEFAULT_CAPACITY = 10;
645 DeleterFunctionType __deleter;
647 friend class _LinkedListEnumerator;
648 friend class _LinkedListImpl;
649 class _LinkedListImpl* __pLinkedListImpl;
653 }}} // Tizen::Base::Collection
655 #endif // _FBASE_COL_LINKED_LIST_H_