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 index.
40 * The %LinkedList class represents a collection of objects that can be individually accessed by 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 The function pointer to type of the element deleter
111 * @remarks To create an owing collection, set the element deleter value as @c SingleObjectDeleter. This gives the collection the ownership of elements and the collection will destroy elements. @n
112 * On the other hand, to create a non-owning collection, you do not need to set the element deleter value, as @c NoOpDeleter is the default element deleter.
113 * It means that you do not transfer the ownership of elements to the collection.
115 * @see SingleObjectDeleter()
116 * @see ArrayDeleter()
118 explicit LinkedList(DeleterFunctionType deleter = NoOpDeleter);
121 * This destructor overrides Tizen::Base::Object::~Object().
125 virtual ~LinkedList(void);
128 * Adds the given object to the end of this list.
132 * @return An error code
133 * @param[in] pObj An pointer to object to add
134 * @exception E_SUCCESS The method is successful.
135 * @exception E_INVALID_ARG The specified input parameter is invalid.
136 * @remarks This method performs a shallow copy. It adds just the pointer; not the element itself.
139 virtual result Add(Object* pObj);
142 * Adds the elements of the given collection to the end of this list.
146 * @return An error code
147 * @param[in] collection A collection to add
148 * @exception E_SUCCESS The method is successful.
149 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
150 * the @c collection is modified during the operation of this method.
151 * @remarks This method performs a shallow copy. It adds just the pointer; not the element itself.
154 virtual result AddItems(const ICollection& collection);
157 * Gets an enumerator (an instance of the IEnumerator derived class) to the list.
161 * @return An enumerator of the calling list object, @n
162 * else @c null if an exception occurs
163 * @remarks The specific error code can be accessed using the GetLastResult() method.
164 * @see Tizen::Base::Collection::IEnumerator
166 virtual IEnumerator* GetEnumeratorN(void) const;
169 * Gets a bidirectional enumerator (an instance of the IBidirectionalEnumerator derived class) of this list.
173 * @return An instance of the IBidirectionalEnumerator derived class, @n
174 * else @c null if some exception occurs
175 * @remarks Use this method to obtain a bidirectional enumerator (an instance of the IBidirectionalEnumerator derived class)
176 * to iterate over a collection (an instance of the IList derived class).
177 * The specific error code can be accessed using GetLastResult() method.
178 * @see Tizen::Base::Collection::IBidirectionalEnumerator
180 virtual IBidirectionalEnumerator* GetBidirectionalEnumeratorN(void) const;
183 * Gets the object at the specified index of the calling list.
187 * @return A pointer to the object at the specified index of the list, @n
188 * else @c null if the index is not valid
189 * @param[in] index The index of the object to read
190 * @exception E_SUCCESS The method is successful.
191 * @exception E_OUT_OF_RANGE The specified index is outside the bounds of the data structure, or
192 * the specified @c index is equal to or greater than the number of elements or less than @c 0.
193 * @remarks The specific error code can be accessed using the GetLastResult() method.
196 virtual const Object* GetAt(int index) const;
199 * Gets the object at the specified index of the calling list.
203 * @return A pointer to the object at the specified index of the list, @n
204 * else @c null if the index is not valid
205 * @param[in] index The index of the object to read
206 * @exception E_SUCCESS The method is successful.
207 * @exception E_OUT_OF_RANGE The specified index is outside the bounds of the data structure, or
208 * the specified @c index is equal to or greater than the number of elements or less than @c 0.
209 * @remarks The specific error code can be accessed using the GetLastResult() method.
212 virtual Object* GetAt(int index);
215 * Gets an IList with the specified range from the calling list object.
219 * @return An IList pointer if successful, @n
220 * else @c null if an exception occurs
221 * @param[in] startIndex The starting index of the range
222 * @param[in] count The number of elements to read
223 * @exception E_SUCCESS The method is successful.
224 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred: @n
225 * - The specified index is outside the bounds of the data structure. @n
226 * - The specified @c startIndex is either equal to or greater than the number of elements or less than @c 0. @n
227 * - The specified @c count is either greater than the number of elements starting from @c startIndex or less than @c 0.
228 * @remarks The IList stores just the pointers to the elements in the list, not the elements themselves.
229 * The specific error code can be accessed using the GetLastResult() method.
231 virtual IList* GetItemsN(int startIndex, int count) const;
234 * Searches for an object in this list. @n
235 * Gets the index of the object if found.
239 * @return An error code
240 * @param[in] obj The object to locate
241 * @param[out] index The index of the object
242 * @exception E_SUCCESS The method is successful.
243 * @exception E_OBJ_NOT_FOUND The specified @c obj is not found.
245 virtual result IndexOf(const Object& obj, int& index) const;
248 * Searches for an object starting from the specified index. @n
249 * Gets the index of the object if found.
253 * @return An error code
254 * @param[in] obj The object to locate
255 * @param[in] startIndex The starting index for the search @n
256 * It must be less than the number of elements.
257 * @param[out] index The index of the object
258 * @exception E_SUCCESS The method is successful.
259 * @exception E_OUT_OF_RANGE The specified index is outside the bounds of the data structure, or
260 * the specified @c startIndex is either equal to or greater than the number of elements in the list or less than @c 0.
261 * @exception E_OBJ_NOT_FOUND The specified @c obj is not found.
264 virtual result IndexOf(const Object& obj, int startIndex, int& index) const;
267 * Searches for an object within the specified range. @n
268 * Gets the index of the object if found.
272 * @return An error code
273 * @param[in] obj The object to locate
274 * @param[in] startIndex The starting index of the range
275 * @param[in] count The number of elements to read
276 * @param[out] index The index of the object
277 * @exception E_SUCCESS The method is successful.
278 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred: @n
279 * - The specified index is outside the bounds of the data structure. @n
280 * - The specified @c startIndex is either equal to or greater than the number of elements in the list or less than @c 0. @n
281 * - The specified @c count is either greater than the number of elements starting from @c startIndex or less than @c 0.
282 * @exception E_OBJ_NOT_FOUND The specified @c obj is not found.
285 virtual result IndexOf(const Object& obj, int startIndex, int count, int& index) const;
288 * Searches for the last occurrence of an object in this list. @n
289 * Gets the index of the object if found.
293 * @return An error code
294 * @param[in] obj The object to locate
295 * @param[out] index The index of the last occurrence of the specified object
296 * @exception E_SUCCESS The method is successful.
297 * @exception E_OBJ_NOT_FOUND The specified @c obj is not found.
300 virtual result LastIndexOf(const Object& obj, int& index) const;
303 * Inserts the object at the specified location.
307 * @return An error code
308 * @param[in] pObj The pointer to object to insert
309 * @param[in] index The index at which the object must be inserted
310 * @exception E_SUCCESS The method is successful.
311 * @exception E_INVALID_ARG The specified input parameter is invalid.
312 * @exception E_OUT_OF_RANGE The specified index is outside the bounds of the data structure, or
313 * the specified @c index is greater than the number of elements or less than @c 0.
314 * @remarks If the @c index equals to the number of elements, then the new element
315 * is added at the end of this list.
316 * This method performs a shallow copy. It inserts just the pointer; not the element itself.
320 virtual result InsertAt(Object* pObj, int index);
323 * Inserts the elements of the collection at the specified location.
327 * @return An error code
328 * @param[in] collection The collection to insert elements from
329 * @param[in] startIndex The starting index at which the elements must be inserted
330 * @exception E_SUCCESS The method is successful.
331 * @exception E_OUT_OF_RANGE The specified index is outside the bounds of the data structure, or
332 * the specified @c startIndex is either greater than the number of elements or less than @c 0.
333 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
334 * the @c collection is modified during the operation of this method.
335 * @remarks If the @c startIndex equals to the number of elements then the new elements
336 * are added at the end of this list.
337 * This method performs a shallow copy. It inserts just the pointer; not the element itself.
341 virtual result InsertItemsFrom(const ICollection& collection, int startIndex);
344 * Removes the first occurrence of the specified object from the list.
348 * @return An error code
349 * @param[in] obj An object to remove
350 * @exception E_SUCCESS The method is successful.
351 * @exception E_OBJ_NOT_FOUND The specified @c obj is not found.
355 virtual result Remove(const Object& obj);
358 * Removes the object at the specified location in the list.
362 * @return An error code
363 * @param[in] index The index at which the object must be removed
364 * @exception E_SUCCESS The method is successful.
365 * @exception E_OUT_OF_RANGE The specified index is outside the bounds of the data structure, or
366 * The specified @c index is equal to or greater than the number of elements or less than @c 0.
369 virtual result RemoveAt(int index);
372 * Removes all elements within the specified range from the list.
376 * @return An error code
377 * @param[in] startIndex The starting index of the range
378 * @param[in] count The number of element to remove
379 * @exception E_SUCCESS The method is successful.
380 * @exception E_OUT_OF_RANGE Either of the following conditions has occurred: @n
381 * - The specified index is outside the bounds of the data structure. @n
382 * - The specified @c startIndex is either equal to or greater than the number of elements or less than @c 0. @n
383 * - The specified @c count is either greater than the number of elements starting from @c startIndex or less than @c 0.
385 * @see InsertItemsFrom()
387 virtual result RemoveItems(int startIndex, int count);
390 * Removes all the elements that are common in the specified @c collection
395 * @return An error code
396 * @param[in] collection The collection to remove from this list
397 * @exception E_SUCCESS The method is successful.
398 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
399 * the @c collection is modified during the operation of this method.
403 virtual result RemoveItems(const ICollection& collection);
407 * Removes all of the object pointers in the collection and also removes all of the objects depending on the specified element deleter.
408 * This method can be called before deleting the objects in a collection.
413 virtual void RemoveAll(void);
416 * Replaces the object at the specified index with the given object.
420 * @return An error code
421 * @param[in] pObj The pointer to object to set
422 * @param[in] index The index at which the object must be set
423 * @exception E_SUCCESS The method is successful.
424 * @exception E_INVALID_ARG The specified input parameter is invalid.
425 * @exception E_OUT_OF_RANGE The specified index is outside the bounds of the data structure, or
426 * the specified @c index is equal to or greater than the number of elements or less than @c 0.
429 virtual result SetAt(Object* pObj, int index);
432 * Sorts the elements of this list using the comparer provided.
436 * @return An error code
437 * @param[in] comparer The IComparer implementation to use when comparing elements
438 * @exception E_SUCCESS The method is successful.
439 * @exception E_INVALID_ARG The specified input parameter is invalid, or
440 * the @c comparer is not valid.
442 virtual result Sort(const IComparer& comparer);
445 * Gets the number of objects currently stored in this list.
449 * @return The number of objects currently stored in this list
451 virtual int GetCount(void) const;
454 * Checks whether the list contains the specified object.
458 * @return @c true if the list contains the specified object, @n
460 * @param[in] obj The object to locate
463 virtual bool Contains(const Object& obj) const;
466 * Checks whether the list contains all the elements of the specified collection.
470 * @return @c true if this list contains all of the elements in the specified collection, @n
472 * @param[in] collection The collection to check for containment in this list
473 * @exception E_SUCCESS The method is successful.
474 * @exception E_INVALID_OPERATION The current state of the instance prohibits the execution of the specified operation, or
475 * the @c collection is modified during the operation of this method.
476 * @remarks The specific error code can be accessed using the GetLastResult() method.
477 * @remarks If the given @c collection is empty, this method will return @c true.
480 virtual bool ContainsAll(const ICollection& collection) const;
483 * Compares the given object with the calling %LinkedList object.
487 * @return @c true if the specified instance equals the current instance, @n
489 * @param[in] obj The object to compare with the calling object
490 * @remarks This method returns @c true only if the specified object is also an instance of the %LinkedList class,
491 * both lists have the same size, and all corresponding pairs of elements in the two lists are equal.
492 * In other words, two lists are equal if they contain the same elements in the same order.
494 virtual bool Equals(const Object& obj) const;
497 * Gets the hash value of the current instance.
501 * @return The hash value of the current instance
502 * @remarks The two Tizen::Base::Object::Equals() instances must return the same hash value. For better performance, @n
503 * the used hash function must generate a random distribution for all inputs.
505 virtual int GetHashCode(void) const;
508 * Gets the element deleter of the collection.
512 * @return A function pointer to the existing element deleter
514 virtual DeleterFunctionType GetDeleter(void) const;
518 * The implementation of this copy constructor is intentionally blank and declared as private to prohibit copying of objects.
520 * @param[in] list The %LinkedList object to initialize the new object
522 LinkedList(const LinkedList& list);
525 * The implementation of this copy assignment operator is intentionally blank and declared as private to prohibit copying of objects.
527 * @param[in] list An instance of %LinkedList
529 LinkedList& operator =(const LinkedList& list);
532 * Allocates and adds a memory block.
534 * @return An error code
535 * @param[in] blockSize The size of block to allocate
536 * @exception E_SUCCESS The method is successful.
538 result AddBlock(int blockSize = DEFAULT_CAPACITY);
541 * Frees memory blocks of the list.
544 void DeleteBlock(void);
547 * Inserts an object to the beginning of the %LinkedList.
549 * @return An error code
550 * @param[in] pObj The pointer to object to insert
551 * @exception E_SUCCESS The method is successful.
553 result InsertFirst(Object* pObj);
556 * Inserts an object to the end of the %LinkedList.
558 * @return An error code
559 * @param[in] pObj The pointer to object to insert
560 * @exception E_SUCCESS The method is successful.
562 result InsertLast(Object* pObj);
565 * Inserts an object after the specified node.
567 * @return An error code
568 * @param[in] pObj The pointer to object to insert
569 * @param[in] pPrevNode The node after which the object must inserted
570 * @exception E_SUCCESS The method is successful.
572 result InsertNext(Object* pObj, _ListNode* pPrevNode);
575 * Gets a node from Available node list.
577 * @return A pointer to a new List Node if successful, @n
578 * else @c null if no node is available
580 _ListNode* GetNewNode(void);
583 * Gets the node at the specified index.
585 * @return A node at the specified index
586 * @param[in] index The index of the node to read
588 _ListNode* GetNode(int index) const;
591 * Removes the specified node.
593 * @param[in] pNode The pointer of the node to remove
595 void RemoveNode(_ListNode* pNode);
598 * Sets the element deleter of the collection.
602 * @param[in] deleter A function pointer to the element deleter to set
604 virtual void SetDeleter(DeleterFunctionType deleter);
606 _ListNode* __pListHead;
607 _ListNode* __pListTail;
608 _ListNode* __pAvailableHead;
609 _ListNode* __pAvailableTail;
610 _ListNode* __pBlocks;
614 static const int DEFAULT_CAPACITY = 10;
615 DeleterFunctionType __deleter;
617 friend class _LinkedListEnumerator;
618 friend class _LinkedListImpl;
619 class _LinkedListImpl* __pLinkedListImpl;
623 }}} // Tizen::Base::Collection
625 #endif // _FBASE_COL_LINKED_LIST_H_