1 /*
2 pblIterator.c - C implementation of an Iterator similar
3 to the Java Iterator and Java ListIterator.
4
5 Copyright (C) 2009 Peter Graf
6
7 This file is part of PBL - The Program Base Library.
8 PBL is free software.
9
10 This library is free software; you can redistribute it and/or
11 modify it under the terms of the GNU Lesser General Public
12 License as published by the Free Software Foundation; either
13 version 2.1 of the License, or (at your option) any later version.
14
15 This library is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 Lesser General Public License for more details.
19
20 You should have received a copy of the GNU Lesser General Public
21 License along with this library; if not, write to the Free Software
22 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23
24 For more information on the Program Base Library or Peter Graf,
25 please see: http://www.mission-base.com/.
26
27 $Log: pblIterator.c,v $
28 Revision 1.9 2010/05/30 20:06:45 peter
29 Removed warnings found by 'Microsoft Visual C++ 2010'.
30
31 Revision 1.8 2009/03/15 21:29:29 peter
32 *** empty log message ***
33
34 Revision 1.7 2009/03/11 23:48:44 peter
35 More tests and clean up.
36
37 Revision 1.6 2009/03/08 20:56:50 peter
38 port to gcc (Ubuntu 4.3.2-1ubuntu12) 4.3.2.
39 Exposing the hash set and tree set interfaces.
40
41 */
42
43 /*
44 * Make sure "strings <exe> | grep Id | sort -u" shows the source file versions
45 */
46 char* pblIterator_c_id = "$Id: pblIterator.c,v 1.9 2010/05/30 20:06:45 peter Exp $";
47
48 char * PblIteratorMagic = "PblIteratorMagic";
49
50 #include <stdio.h>
51 #include <memory.h>
52
53 #ifndef __APPLE__
54 #include <stdlib.h>
55 #endif
56
57 #include <stdlib.h>
58
59 #include "pbl.h"
60
61 /*****************************************************************************/
62 /* Typedefs */
63 /*****************************************************************************/
64
65 /*
66 * The tree iterator type.
67 */
68 typedef struct PblTreeIterator_s
69 {
70 char * magic; /* The magic string of iterators */
71 unsigned long changeCounter; /* The number of changes on the collection */
72 PblCollection * collection; /* The collection the iterator works on */
73 int index; /* The current index of the iterator */
74
75 int lastIndexReturned; /* Index of element that was returned last */
76
77 PblTreeNode * current; /* The current node in the tree set */
78
79 PblTreeNode * prev; /* The previous node in the tree set */
80 PblTreeNode * next; /* The next node in the tree set */
81
82 } PblTreeIterator;
83
84 /*
85 * The hash iterator type.
86 */
87 typedef struct PblHashIterator_s
88 {
89 char * magic; /* The magic string of iterators */
90 unsigned long changeCounter; /* The number of changes on the collection */
91 PblCollection * collection; /* The collection the iterator works on */
92 int index; /* The current index of the iterator */
93
94 int lastIndexReturned; /* Index of element that was returned last */
95
96 void ** current; /* The current element in the hash */
97
98 void ** prev; /* The previous element in the hash */
99 void ** next; /* The next element in the hash */
100
101 } PblHashIterator;
102
103 /*****************************************************************************/
104 /* Functions */
105 /*****************************************************************************/
106
107 /**
108 * Returns an iterator over the elements in this collection in proper sequence.
109 *
110 * The iterator starts the iteration at the beginning of the collection.
111 *
112 * <B>Note</B>: The memory allocated by this method for the iterator returned needs to be released
113 * by calling pblIteratorFree() once the iterator is no longer needed.
114 *
115 * The iterators returned by the this method are fail-fast:
116 * if the collection is structurally modified at any time after the iterator is created,
117 * in any way except through the Iterator's own remove or add methods,
118 * the iterator will return a PBL_ERROR_CONCURRENT_MODIFICATION error.
119 *
120 * Thus, in the face of concurrent modification,
121 * the iterator fails quickly and cleanly,
122 * rather than risking arbitrary, non-deterministic
123 * behavior at an undetermined time in the future.
124 *
125 * This method has a time complexity of O(1).
126 *
127 * @return void * retptr != NULL: The iterator.
128 * @return void * retptr == NULL: An error, see pbl_errno:
129 *
130 * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
131 * <BR>PBL_ERROR_PARAM_COLLECTION - The collection cannot be iterated.
132 */
pblIteratorNew(PblCollection * collection)133 PblIterator * pblIteratorNew(
134 PblCollection * collection /** The collection to create the iterator for */
135 )
136 {
137 PblIterator * iterator;
138
139 if( !PBL_COLLECTION_IS_COLLECTION( collection ) )
140 {
141 pbl_errno = PBL_ERROR_PARAM_COLLECTION;
142 return NULL;
143 }
144
145 iterator = (PblIterator *)pbl_malloc( "pblIteratorNew", sizeof(PblIterator) );
146 if( !iterator )
147 {
148 return NULL;
149 }
150
151 if( pblIteratorInit( collection, iterator ) < 0 )
152 {
153 PBL_FREE( iterator );
154 return NULL;
155 }
156
157 return (PblIterator *)iterator;
158 }
159
160 /*
161 * Initializes an iterator over the elements in this collection in proper sequence.
162 *
163 * The iterator starts the iteration at the beginning of the collection.
164 *
165 * The iterators returned by the this method are fail-fast:
166 * if the collection is structurally modified at any time after the iterator is created,
167 * in any way except through the Iterator's own remove or add methods,
168 * the iterator will return a PBL_ERROR_CONCURRENT_MODIFICATION error.
169 *
170 * Thus, in the face of concurrent modification,
171 * the iterator fails quickly and cleanly,
172 * rather than risking arbitrary, non-deterministic
173 * behavior at an undetermined time in the future.
174 *
175 * This method has a time complexity of O(1).
176 *
177 * @return int rc == 0: Ok, the iterator is initialized.
178 * @return int rc < 0: An error, see pbl_errno:
179 *
180 * <BR>PBL_ERROR_PARAM_COLLECTION - The collection cannot be iterated.
181 */
pblIteratorInit(PblCollection * collection,PblIterator * iterator)182 int pblIteratorInit(
183 PblCollection * collection, /** The collection to create the iterator for */
184 PblIterator * iterator /** The iterator to initialize */
185 )
186 {
187 if( !PBL_COLLECTION_IS_COLLECTION( collection ) )
188 {
189 pbl_errno = PBL_ERROR_PARAM_COLLECTION;
190 return -1;
191 }
192
193 iterator->magic = PblIteratorMagic;
194 iterator->collection = collection;
195 iterator->index = 0;
196 iterator->lastIndexReturned = -1;
197 iterator->changeCounter = collection->changeCounter;
198
199 iterator->current = NULL;
200 iterator->prev = NULL;
201
202 if( PBL_SET_IS_HASH_SET( collection ) )
203 {
204 PblHashIterator * hashIterator = (PblHashIterator *)iterator;
205 hashIterator->next = pblHashElementFirst( (PblHashSet*)collection );
206 }
207 else if( PBL_SET_IS_TREE_SET( collection ) )
208 {
209 PblTreeIterator * treeIterator = (PblTreeIterator *)iterator;
210 PblTreeSet * treeSet = (PblTreeSet*)collection;
211 treeIterator->next
212 = treeSet->rootNode ? pblTreeNodeFirst( treeSet->rootNode )
213 : NULL;
214 }
215 else if( PBL_LIST_IS_LINKED_LIST( collection ) )
216 {
217 PblLinkedList * linkedList = (PblLinkedList*)collection;
218 iterator->next = linkedList->head;
219 }
220 else
221 {
222 iterator->next = NULL;
223 }
224
225 return 0;
226 }
227
228 /**
229 * Returns a reverse iterator over the elements in this collection in proper sequence.
230 *
231 * The reverse iterator starts the iteration at the end of the collection.
232 *
233 * <B>Note:</B> The memory allocated by this method for the iterator returned needs to be released
234 * by calling pblIteratorFree() once the iterator is no longer needed.
235 *
236 * The iterators returned by the this method are fail-fast:
237 * if the collection is structurally modified at any time after the iterator is created,
238 * in any way except through the Iterator's own remove or add methods,
239 * the iterator will return a PBL_ERROR_CONCURRENT_MODIFICATION error.
240 *
241 * Thus, in the face of concurrent modification,
242 * the iterator fails quickly and cleanly,
243 * rather than risking arbitrary, non-deterministic
244 * behavior at an undetermined time in the future.
245 *
246 * This method has a time complexity of O(1).
247 *
248 * @return void * retptr != NULL: The iterator.
249 * @return void * retptr == NULL: An error, see pbl_errno:
250 *
251 * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
252 * <BR>PBL_COLLECTION_IS_COLLECTION - The collection cannot be iterated.
253 */
pblIteratorReverseNew(PblCollection * collection)254 PblIterator * pblIteratorReverseNew(
255 PblCollection * collection /** The collection to create the iterator for */
256 )
257 {
258 PblIterator * iterator;
259
260 if( !PBL_COLLECTION_IS_COLLECTION( collection ) )
261 {
262 pbl_errno = PBL_ERROR_PARAM_COLLECTION;
263 return NULL;
264 }
265
266 iterator = (PblIterator *)pbl_malloc( "pblIteratorReverseNew", sizeof(PblIterator) );
267 if( !iterator )
268 {
269 return NULL;
270 }
271
272 if( pblIteratorReverseInit( collection, iterator ) < 0 )
273 {
274 PBL_FREE( iterator );
275 return NULL;
276 }
277
278 return (PblIterator *)iterator;
279 }
280
281 /*
282 * Initializes a reverse iterator over the elements in this collection in proper sequence.
283 *
284 * The reverse iterator starts the iteration at the end of the collection.
285 *
286 * <B>Note:</B> The memory allocated by this method for the iterator returned needs to be released
287 * by calling pblIteratorFree() once the iterator is no longer needed.
288 *
289 * The iterators returned by the this method are fail-fast:
290 * if the collection is structurally modified at any time after the iterator is created,
291 * in any way except through the Iterator's own remove or add methods,
292 * the iterator will return a PBL_ERROR_CONCURRENT_MODIFICATION error.
293 *
294 * Thus, in the face of concurrent modification,
295 * the iterator fails quickly and cleanly,
296 * rather than risking arbitrary, non-deterministic
297 * behavior at an undetermined time in the future.
298 *
299 * This method has a time complexity of O(1).
300 *
301 * @return int rc == 0: Ok, the iterator is initialized.
302 * @return int rc < 0: An error, see pbl_errno:
303 *
304 * <BR>PBL_COLLECTION_IS_COLLECTION - The collection cannot be iterated.
305 */
pblIteratorReverseInit(PblCollection * collection,PblIterator * iterator)306 int pblIteratorReverseInit(
307 PblCollection * collection, /** The collection to create the iterator for */
308 PblIterator * iterator /** The iterator to initialize */
309 )
310 {
311 if( !PBL_COLLECTION_IS_COLLECTION( collection ) )
312 {
313 pbl_errno = PBL_ERROR_PARAM_LIST;
314 return -1;
315 }
316
317 iterator->magic = PblIteratorMagic;
318 iterator->collection = collection;
319 iterator->index = collection->size;
320 iterator->lastIndexReturned = -1;
321 iterator->changeCounter = collection->changeCounter;
322
323 iterator->current = NULL;
324 iterator->next = NULL;
325
326 if( PBL_SET_IS_HASH_SET( collection ) )
327 {
328 PblHashIterator * hashIterator = (PblHashIterator *)iterator;
329 hashIterator->prev = pblHashElementLast( (PblHashSet*)collection );
330 }
331 else if( PBL_SET_IS_TREE_SET( collection ) )
332 {
333 PblTreeIterator * treeIterator = (PblTreeIterator *)iterator;
334 PblTreeSet * treeSet = (PblTreeSet*)collection;
335 treeIterator->prev
336 = treeSet->rootNode ? pblTreeNodeLast( treeSet->rootNode )
337 : NULL;
338 }
339 else if( PBL_LIST_IS_LINKED_LIST( collection ) )
340 {
341 PblLinkedList * linkedList = (PblLinkedList*)collection;
342 iterator->prev = linkedList->tail;
343 }
344 else
345 {
346 iterator->prev = NULL;
347 }
348
349 return 0;
350 }
351
352 /**
353 * Returns true if this iterator has more elements when traversing the collection in the reverse direction.
354 *
355 * In other words, returns a value > 0 if pblIteratorPrevious would return
356 * an element rather than returning (void*)-1.
357 *
358 * This method has a time complexity of O(1).
359 *
360 * @return int rc > 0: The iterator has more elements.
361 * @return int rc == 0: The iteration has no more elements.
362 * @return int rc < 0: An error, see pbl_errno:
363 *
364 * <BR>PBL_ERROR_CONCURRENT_MODIFICATION - The underlying collection was modified concurrently.
365 *
366 */
pblIteratorHasPrevious(PblIterator * iterator)367 int pblIteratorHasPrevious(
368 PblIterator * iterator /** The iterator to check the previous element for */
369 )
370 {
371 if( iterator->changeCounter != iterator->collection->changeCounter )
372 {
373 pbl_errno = PBL_ERROR_CONCURRENT_MODIFICATION;
374 return -1;
375 }
376
377 if( iterator->index > 0 && iterator->index <= iterator->collection->size )
378 {
379 return 1;
380 }
381 return 0;
382 }
383
384 /**
385 * Returns true if this iterator has more elements.
386 *
387 * In other words, returns a value > 0 if pblIteratorNext would return
388 * an element rather than returning (void*)-1.
389 *
390 * This method has a time complexity of O(1).
391 *
392 * @return int rc > 0: The iterator has more elements.
393 * @return int rc == 0: The iteration has no more elements.
394 * @return int rc < 0: An error, see pbl_errno:
395 *
396 * <BR>PBL_ERROR_CONCURRENT_MODIFICATION - The underlying collection was modified concurrently.
397 */
pblIteratorHasNext(PblIterator * iterator)398 int pblIteratorHasNext(
399 PblIterator * iterator /** The iterator to check the next element for */
400 )
401 {
402 if( iterator->changeCounter != iterator->collection->changeCounter )
403 {
404 pbl_errno = PBL_ERROR_CONCURRENT_MODIFICATION;
405 return -1;
406 }
407
408 if( iterator->index >= 0 && iterator->index < iterator->collection->size )
409 {
410 return 1;
411 }
412 return 0;
413 }
414
415 /**
416 * Returns the next element in the iteration.
417 *
418 * Calling this method repeatedly until the hasNext()
419 * method returns false will return each element
420 * in the underlying collection exactly once.
421 *
422 * This method has a time complexity of O(1).
423 *
424 * @return void * retptr != (void*)-1: The next element in the iteration.
425 * May be NULL.
426 * @return void * retptr == (void*)-1: An error, see pbl_errno:
427 *
428 * <BR>PBL_ERROR_NOT_FOUND - The iteration has no more elements.
429 * <BR>PBL_ERROR_CONCURRENT_MODIFICATION - The underlying collection was modified concurrently.
430 */
pblIteratorNext(PblIterator * iterator)431 void * pblIteratorNext(
432 PblIterator * iterator /** The iterator to return the next element for */
433 )
434 {
435 void * element;
436 int hasNext = pblIteratorHasNext( iterator );
437 if( hasNext < 0 )
438 {
439 return (void*)-1;
440 }
441
442 if( !hasNext )
443 {
444 pbl_errno = PBL_ERROR_NOT_FOUND;
445 return (void*)-1;
446 }
447
448 if( PBL_SET_IS_HASH_SET( iterator->collection ) )
449 {
450 PblHashIterator * hashIterator = (PblHashIterator *)iterator;
451
452 if( !hashIterator->next )
453 {
454 pbl_errno = PBL_ERROR_NOT_FOUND;
455 return (void*)-1;
456 }
457
458 hashIterator->current = hashIterator->next;
459 hashIterator->prev = hashIterator->next;
460 hashIterator->next
461 = pblHashElementNext( (PblHashSet *)hashIterator->collection,
462 hashIterator->next );
463
464 element = *( hashIterator->current );
465 }
466 else if( PBL_SET_IS_TREE_SET( iterator->collection ) )
467 {
468 PblTreeIterator * treeIterator = (PblTreeIterator *)iterator;
469
470 if( !treeIterator->next )
471 {
472 pbl_errno = PBL_ERROR_NOT_FOUND;
473 return (void*)-1;
474 }
475
476 treeIterator->current = treeIterator->next;
477 treeIterator->prev = treeIterator->next;
478 treeIterator->next = pblTreeNodeNext( treeIterator->next );
479
480 element = treeIterator->current->element;
481 }
482 else if( PBL_LIST_IS_LINKED_LIST( iterator->collection ) )
483 {
484 if( !iterator->next )
485 {
486 pbl_errno = PBL_ERROR_NOT_FOUND;
487 return (void*)-1;
488 }
489
490 iterator->current = iterator->next;
491 iterator->prev = iterator->next;
492 iterator->next = iterator->next->next;
493
494 element = iterator->current->element;
495 }
496 else
497 {
498 element = pblListGet( (PblList*)iterator->collection, iterator->index );
499 if( element == (void*)-1 )
500 {
501 pbl_errno = PBL_ERROR_NOT_FOUND;
502 return (void*)-1;
503 }
504 }
505
506 iterator->lastIndexReturned = iterator->index;
507 iterator->index++;
508
509 return element;
510 }
511
512 /**
513 * Returns the previous element in the iteration.
514 *
515 * This method may be called repeatedly to iterate through the list backwards,
516 * or intermixed with calls to next to go back and forth.
517 * (Note that alternating calls to next and previous will return the same element repeatedly.)
518 *
519 * This method has a time complexity of O(1).
520 *
521 * @return void * retptr != (void*)-1: The previous element in the iteration.
522 * May be NULL.
523 * @return void * retptr == (void*)-1: An error, see pbl_errno:
524 *
525 * <BR>PBL_ERROR_NOT_FOUND - The iteration has no more elements.
526 * <BR>PBL_ERROR_CONCURRENT_MODIFICATION - The underlying collection was modified concurrently.
527 */
pblIteratorPrevious(PblIterator * iterator)528 void * pblIteratorPrevious(
529 PblIterator * iterator /** The iterator to return the previous element for */
530 )
531 {
532 void * element;
533 int hasPrevious = pblIteratorHasPrevious( iterator );
534 if( hasPrevious < 0 )
535 {
536 return (void*)-1;
537 }
538 if( !hasPrevious )
539 {
540 pbl_errno = PBL_ERROR_NOT_FOUND;
541 return (void*)-1;
542 }
543
544 if( PBL_SET_IS_HASH_SET( iterator->collection ) )
545 {
546 PblHashIterator * hashIterator = (PblHashIterator *)iterator;
547
548 if( !hashIterator->prev )
549 {
550 pbl_errno = PBL_ERROR_NOT_FOUND;
551 return (void*)-1;
552 }
553
554 hashIterator->current = hashIterator->prev;
555 hashIterator->next = hashIterator->prev;
556 hashIterator->prev
557 = pblHashElementPrevious(
558 (PblHashSet *)hashIterator->collection,
559 hashIterator->prev );
560
561 element = *( hashIterator->current );
562 }
563 else if( PBL_SET_IS_TREE_SET( iterator->collection ) )
564 {
565 PblTreeIterator * treeIterator = (PblTreeIterator *)iterator;
566
567 if( !treeIterator->prev )
568 {
569 pbl_errno = PBL_ERROR_NOT_FOUND;
570 return (void*)-1;
571 }
572
573 treeIterator->current = treeIterator->prev;
574 treeIterator->next = treeIterator->prev;
575 treeIterator->prev = pblTreeNodePrevious( treeIterator->prev );
576
577 element = treeIterator->current->element;
578 }
579 else if( PBL_LIST_IS_LINKED_LIST( iterator->collection ) )
580 {
581 if( !iterator->prev )
582 {
583 pbl_errno = PBL_ERROR_NOT_FOUND;
584 return (void*)-1;
585 }
586
587 iterator->current = iterator->prev;
588 iterator->next = iterator->prev;
589 iterator->prev = iterator->prev->prev;
590
591 element = iterator->current->element;
592 }
593 else
594 {
595 element = pblListGet( (PblList*)iterator->collection, iterator->index
596 - 1 );
597
598 if( element == (void*)-1 )
599 {
600 pbl_errno = PBL_ERROR_NOT_FOUND;
601 return (void*)-1;
602 }
603 }
604
605 iterator->index--;
606 iterator->lastIndexReturned = iterator->index;
607
608 return element;
609 }
610
611 /**
612 * Inserts the specified element into the underlying collection.
613 *
614 * The element is inserted immediately before the next element that would be returned by next,
615 * if any, and after the next element that would be returned by previous, if any.
616 *
617 * If the list contains no elements, the new element becomes the sole element on the list.
618 *
619 * The new element is inserted before the implicit cursor:
620 * a subsequent call to next would be unaffected,
621 * and a subsequent call to previous would return the new element.
622 * This call increases by one the value that would be returned by a
623 * call to nextIndex or previousIndex.
624 *
625 * For array lists this method has a time complexity of O(N),
626 * with N being the number of elements in the underlying list.
627 *
628 * For linked lists this method has a time complexity of O(1).
629 *
630 * @return int rc >= 0: The size of the list.
631 * @return int rc < 0: An error, see pbl_errno:
632 *
633 * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
634 * <BR>PBL_ERROR_CONCURRENT_MODIFICATION - The underlying list was modified concurrently.
635 * <BR>PBL_ERROR_PARAM_LIST - The underlying collection is not a list.
636 */
pblIteratorAdd(PblIterator * iterator,void * element)637 int pblIteratorAdd(
638 PblIterator * iterator, /** The iterator to add the element to */
639 void * element /** Element to be added to this list */
640 )
641 {
642 PblList * list = (PblList*)iterator->collection;
643
644 if( !PBL_LIST_IS_LIST( list ) )
645 {
646 pbl_errno = PBL_ERROR_PARAM_LIST;
647 return -1;
648 }
649
650 if( iterator->changeCounter != list->changeCounter )
651 {
652 pbl_errno = PBL_ERROR_CONCURRENT_MODIFICATION;
653 return -1;
654 }
655
656 if( list->size == 0 )
657 {
658 if( pblListAdd( (PblList*)list, element ) < 1 )
659 {
660 return -1;
661 }
662
663 iterator->index = 1;
664 iterator->next = NULL;
665
666 iterator->lastIndexReturned = -1;
667 iterator->current = NULL;
668
669 if( PBL_LIST_IS_LINKED_LIST( list ) )
670 {
671 PblLinkedList * linkedList = (PblLinkedList*)list;
672 iterator->prev = linkedList->tail;
673 }
674 iterator->changeCounter = list->changeCounter;
675 return 1;
676 }
677
678 if( PBL_LIST_IS_ARRAY_LIST( list ) )
679 {
680 int rc = pblListAddAt( (PblList*)list, iterator->index, element );
681 if( rc < 0 )
682 {
683 return -1;
684 }
685 }
686 else
687 {
688 PblLinkedList * linkedList = (PblLinkedList*)list;
689 PblLinkedNode * newNode = (PblLinkedNode *)pbl_malloc( "pblIteratorAdd",
690 sizeof(PblLinkedNode) );
691 if( !newNode )
692 {
693 return -1;
694 }
695 newNode->element = element;
696
697 if( !iterator->next )
698 {
699 PBL_LIST_APPEND( linkedList->head, linkedList->tail, newNode, next, prev );
700 }
701 else
702 {
703 PBL_LIST_INSERT( linkedList->head, iterator->next, newNode, next, prev );
704 }
705 linkedList->genericList.size++;
706 linkedList->genericList.changeCounter++;
707
708 iterator->prev = newNode;
709 }
710
711 iterator->lastIndexReturned = -1;
712 iterator->current = NULL;
713
714 iterator->index++;
715
716 iterator->changeCounter = list->changeCounter;
717 return list->size;
718 }
719
720 /**
721 * Removes from the underlying list or tree set the last element returned by the iterator.
722 *
723 * This method can be called only once per call to next or previous.
724 * It can be made only if pblIteratorAdd() has not been called after the last call to next or previous.
725 *
726 * For array lists this method has a time complexity of O(N),
727 * with N being the number of elements in the underlying list.
728 *
729 * For linked lists and hash sets this method has a time complexity of O(1).
730 *
731 * For tree sets this method has a time complexity of O(Log N),
732 * with N being the number of elements in the underlying collection.
733 *
734 * @return int rc >= 0: The size of the collection.
735 * @return int rc < 0: An error, see pbl_errno:
736 *
737 * <BR>PBL_ERROR_NOT_ALLOWED - The the next or previous method has not yet been called,
738 * or the remove method has already been called after the last call to the next or previous method.
739 *
740 * <BR>PBL_ERROR_CONCURRENT_MODIFICATION - The underlying list or tree set was modified concurrently.
741 * <BR>PBL_ERROR_PARAM_LIST - The underlying collection is neither a list nor a tree set.
742 */
pblIteratorRemove(PblIterator * iterator)743 int pblIteratorRemove(
744 PblIterator * iterator /** The iterator to remove the next element from */
745 )
746 {
747 if( iterator->changeCounter != iterator->collection->changeCounter )
748 {
749 pbl_errno = PBL_ERROR_CONCURRENT_MODIFICATION;
750 return -1;
751 }
752
753 if( PBL_SET_IS_TREE_SET( iterator->collection ) )
754 {
755 PblTreeIterator * treeIterator = (PblTreeIterator *)iterator;
756
757 if( !treeIterator->current )
758 {
759 pbl_errno = PBL_ERROR_NOT_ALLOWED;
760 return -1;
761 }
762 else
763 {
764 if( treeIterator->next == treeIterator->current )
765 {
766 treeIterator->next = pblTreeNodeNext( treeIterator->next );
767 }
768 else if( treeIterator->prev == treeIterator->current )
769 {
770 treeIterator->prev = pblTreeNodePrevious( treeIterator->prev );
771 }
772
773 pblSetRemoveElement( (PblSet*)treeIterator->collection,
774 treeIterator->current->element );
775 }
776 }
777 else if( PBL_LIST_IS_LINKED_LIST( iterator->collection ) )
778 {
779 if( !iterator->current )
780 {
781 pbl_errno = PBL_ERROR_NOT_ALLOWED;
782 return -1;
783 }
784 else
785 {
786 PblLinkedList * linkedList = (PblLinkedList *)iterator->collection;
787 PblLinkedNode * nodeToFree = iterator->current;
788
789 if( iterator->next == iterator->current )
790 {
791 iterator->next = iterator->next->next;
792 }
793 else if( iterator->prev == iterator->current )
794 {
795 iterator->prev = iterator->prev->prev;
796 }
797
798 PBL_LIST_UNLINK( linkedList->head, linkedList->tail, nodeToFree, next, prev );
799 linkedList->genericList.size--;
800 linkedList->genericList.changeCounter++;
801
802 PBL_FREE( nodeToFree );
803 }
804 }
805 else if( PBL_LIST_IS_ARRAY_LIST( iterator->collection ) )
806 {
807 if( iterator->lastIndexReturned < 0 )
808 {
809 pbl_errno = PBL_ERROR_NOT_ALLOWED;
810 return -1;
811 }
812
813 if( pblArrayListRemoveAt( (PblArrayList*)iterator->collection,
814 iterator->lastIndexReturned ) == (void*)-1 )
815 {
816 return -1;
817 }
818 }
819 else
820 {
821 pbl_errno = PBL_ERROR_PARAM_LIST;
822 return -1;
823 }
824
825 if( iterator->lastIndexReturned < iterator->index )
826 {
827 iterator->index--;
828 }
829
830 iterator->current = NULL;
831 iterator->lastIndexReturned = -1;
832
833 iterator->changeCounter = iterator->collection->changeCounter;
834
835 return iterator->collection->size;
836 }
837
838 /**
839 * Replaces in the underlying list the last element returned by next or previous with the specified element.
840 *
841 * This call can be made only if neither pblIteratorRemove() nor pblIteratorAdd() have
842 * been called after the last call to next or previous.
843 *
844 * This method has a time complexity of O(1).
845 *
846 * @return void * retptr != (void*)-1: The element replaced, may be NULL.
847 * @return void * retptr == (void*)-1: An error, see pbl_errno:
848 *
849 * <BR>PBL_ERROR_NOT_ALLOWED - Neither the next nor previous have been called,
850 * or remove or add have been called after the last
851 * call to next or previous.
852 *
853 * <BR>PBL_ERROR_CONCURRENT_MODIFICATION - The underlying list was modified concurrently.
854 * <BR>PBL_ERROR_PARAM_LIST - The underlying collection is not a list.
855 */
pblIteratorSet(PblIterator * iterator,void * element)856 void * pblIteratorSet(
857 PblIterator * iterator, /** The iterator to replace the element of. */
858 void * element /** Element with which to replace the last element returned by next or previous. */
859 )
860 {
861 void * retptr = (void*)-1;
862
863 if( !PBL_LIST_IS_LIST( iterator->collection ) )
864 {
865 pbl_errno = PBL_ERROR_PARAM_LIST;
866 return retptr;
867 }
868
869 if( iterator->changeCounter != iterator->collection->changeCounter )
870 {
871 pbl_errno = PBL_ERROR_CONCURRENT_MODIFICATION;
872 return retptr;
873 }
874
875 if( PBL_LIST_IS_LINKED_LIST( iterator->collection ) )
876 {
877 if( !iterator->current )
878 {
879 pbl_errno = PBL_ERROR_NOT_ALLOWED;
880 return retptr;
881 }
882 else
883 {
884 retptr = iterator->current->element;
885 iterator->current->element = element;
886 }
887 }
888 else
889 {
890 if( iterator->lastIndexReturned < 0 )
891 {
892 pbl_errno = PBL_ERROR_NOT_ALLOWED;
893 return retptr;
894 }
895
896 retptr = pblListSet( (PblList*)iterator->collection,
897 iterator->lastIndexReturned, element );
898 }
899
900 return retptr;
901 }
902
903 /**
904 * Returns the index of the element that would be returned by a subsequent call to next.
905 *
906 * Returns list size if the list iterator is at the end of the list.
907 *
908 * This method has a time complexity of O(1).
909 *
910 * @return int rc: The index of the element that would be returned by a subsequent call to next,
911 * or list size if list iterator is at end of list.
912 */
pblIteratorNextIndex(PblIterator * iterator)913 int pblIteratorNextIndex(
914 PblIterator * iterator /** The iterator to use */
915 )
916 {
917 return iterator->index;
918 }
919
920 /**
921 * Returns the index of the element that would be returned by a subsequent call to previous.
922 *
923 * Returns -1 if the list iterator is at the beginning of the list.
924 *
925 * This method has a time complexity of O(1).
926 *
927 * @return int rc: The index of the element that would be returned by a subsequent call to previous,
928 * or -1 if list iterator is at beginning of list.
929 */
pblIteratorPreviousIndex(PblIterator * iterator)930 int pblIteratorPreviousIndex(
931 PblIterator * iterator /** The iterator to use */
932 )
933 {
934 return iterator->index - 1;
935 }
936
937 /**
938 * Returns the number of elements in the underlying collection of the iterator.
939 *
940 * This method has a time complexity of O(1).
941 *
942 * @return int rc: The number of elements in the collection.
943 */
pblIteratorSize(PblIterator * iterator)944 int pblIteratorSize(
945 PblIterator * iterator /** The iterator to use */
946 )
947 {
948 return iterator->collection->size;
949 }
950
951 /**
952 * Frees the memory used by the iterator.
953 *
954 * This method has a time complexity of O(1).
955 *
956 * Must be called once the iterator is no longer needed.
957 */
pblIteratorFree(PblIterator * iterator)958 void pblIteratorFree(
959 PblIterator * iterator /** The iterator to free */
960 )
961 {
962 PBL_FREE(iterator);
963 }
964
965
966
967
968