Changes to attempt to silence bcc64x
[ACE_TAO.git] / ACE / ace / Containers_T.h
blob533a48924bb3699648613fb1874e71f7afe964e3
1 // -*- C++ -*-
3 //=============================================================================
4 /**
5 * @file Containers_T.h
7 * @author Douglas C. Schmidt <d.schmidt@vanderbilt.edu>
8 */
9 //=============================================================================
11 #ifndef ACE_CONTAINERS_T_H
12 #define ACE_CONTAINERS_T_H
14 #include /**/ "ace/pre.h"
16 #include /**/ "ace/config-all.h"
18 #if !defined (ACE_LACKS_PRAGMA_ONCE)
19 # pragma once
20 #endif /* ACE_LACKS_PRAGMA_ONCE */
22 // Need by ACE_DLList_Node.
23 #include "ace/Containers.h"
25 // Shared with "ace/Unbounded_Set.h"
26 #include "ace/Node.h"
28 // Backwards compatibility, please include "ace/Array_Base.h" directly.
29 #include "ace/Array_Base.h"
31 // Backwards compatibility, please include "ace/Unbounded_Set.h" directly.
32 #include "ace/Unbounded_Set.h"
34 // Backwards compatibility, please include "ace/Unbounded_Queue.h" directly.
35 #include "ace/Unbounded_Queue.h"
37 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
39 class ACE_Allocator;
42 /**
43 * @class ACE_Bounded_Stack
45 * @brief Implement a generic LIFO abstract data type.
47 * This implementation of a Stack uses a bounded array
48 * that is allocated dynamically. The Stack interface
49 * provides the standard constant time push, pop, and top
50 * operations.
52 * <b> Requirements and Performance Characteristics</b>
53 * - Internal Structure
54 * Dynamic array
55 * - Duplicates allowed?
56 * Yes
57 * - Random access allowed?
58 * No
59 * - Search speed
60 * N/A
61 * - Insert/replace speed
62 * N/A
63 * - Iterator still valid after change to container?
64 * N/A
65 * - Frees memory for removed elements?
66 * No
67 * - Items inserted by
68 * Value
69 * - Requirements for contained type
70 * -# Default constructor
71 * -# Copy constructor
72 * -# operator=
74 template <class T>
75 class ACE_Bounded_Stack
77 public:
78 // = Initialization, assignment, and termination methods.
80 /// Initialize a new empty stack with the provided size..
81 /**
82 * Initialize and allocate space for a new Bounded_Stack with the provided
83 * size.
85 ACE_Bounded_Stack (size_t size);
87 /// Initialize the stack to be a copy of the stack provided.
88 /**
89 * Initialize the stack to be an exact copy of the Bounded_Stack provided
90 * as a parameter.
92 ACE_Bounded_Stack (const ACE_Bounded_Stack<T> &s);
94 /// Assignment operator
95 /**
96 * Perform a deep copy operation using the Bounded_Stack parameter. If the
97 * capacity of the lhs isn't sufficient for the rhs, then the underlying data
98 * structure will be reallocated to accomadate the larger number of elements.
100 void operator= (const ACE_Bounded_Stack<T> &s);
102 /// Perform actions needed when stack goes out of scope.
104 * Deallocate the memory used by the Bounded_Stack.
106 ~ACE_Bounded_Stack ();
108 // = Classic Stack operations.
110 ///Add an element to the top of the stack.
112 * Place a new item on top of the stack. Returns -1 if the stack
113 * is already full, 0 if the stack is not already full, and -1 if
114 * failure occurs.
116 int push (const T &new_item);
118 ///Remove an item from the top of stack.
120 * Remove and return the top stack item. Returns -1 if the stack is
121 * already empty, 0 if the stack is not already empty, and -1 if
122 * failure occurs.
124 int pop (T &item);
126 ///Examine the contents of the top of stack.
128 * Return top stack item without removing it. Returns -1 if the
129 * stack is already empty, 0 if the stack is not already empty, and
130 * -1 if failure occurs.
132 int top (T &item) const;
134 // = Check boundary conditions.
136 /// Returns 1 if the container is empty, otherwise returns 0.
138 * Performs constant time check to determine if the stack is empty.
140 int is_empty () const;
142 /// Returns 1 if the container is full, otherwise returns 0.
144 * Performs constant time check to determine if the stack is at capacity.
146 int is_full () const;
148 /// The number of items in the stack.
150 * Return the number of items currently in the stack.
152 size_t size () const;
154 /// Dump the state of an object.
155 void dump () const;
157 /// Declare the dynamic allocation hooks.
158 ACE_ALLOC_HOOK_DECLARE;
160 private:
161 /// Size of the dynamically allocated data.
162 size_t size_;
164 /// Keeps track of the current top of stack.
165 size_t top_;
167 /// Holds the stack's contents.
168 T *stack_;
171 //----------------------------------------
175 * @class ACE_Fixed_Stack
177 * @brief Implement a generic LIFO abstract data type.
179 * This implementation of a Stack uses a fixed array
180 * with the size fixed at instantiation time.
182 * <b> Requirements and Performance Characteristics</b>
183 * - Internal Structure
184 * Fixed array
185 * - Duplicates allowed?
186 * Yes
187 * - Random access allowed?
188 * No
189 * - Search speed
190 * N/A
191 * - Insert/replace speed
192 * N/A
193 * - Iterator still valid after change to container?
194 * N/A
195 * - Frees memory for removed elements?
196 * No
197 * - Items inserted by
198 * Value
199 * - Requirements for contained type
200 * -# Default constructor
201 * -# Copy constructor
202 * -# operator=
204 template <class T, size_t ACE_SIZE>
205 class ACE_Fixed_Stack
207 public:
208 // = Initialization, assignment, and termination methods.
209 /// Initialize a new stack so that it is empty.
211 * Initialize an empty stack.
213 ACE_Fixed_Stack ();
215 /// The copy constructor (performs initialization).
217 * Initialize the stack and copy the provided stack into the current stack.
219 ACE_Fixed_Stack (const ACE_Fixed_Stack<T, ACE_SIZE> &s);
221 /// Assignment operator (performs assignment).
223 * Perform a deep copy of the provided stack.
225 void operator= (const ACE_Fixed_Stack<T, ACE_SIZE> &s);
227 /// Perform actions needed when stack goes out of scope.
229 * Destroy the stack.
231 ~ACE_Fixed_Stack ();
233 // = Classic Stack operations.
235 ///Constant time placement of element on top of stack.
237 * Place a new item on top of the stack. Returns -1 if the stack
238 * is already full, 0 if the stack is not already full, and -1 if
239 * failure occurs.
241 int push (const T &new_item);
243 ///Constant time removal of top of stack.
245 * Remove and return the top stack item. Returns -1 if the stack is
246 * already empty, 0 if the stack is not already empty, and -1 if
247 * failure occurs.
249 int pop (T &item);
251 ///Constant time examination of top of stack.
253 * Return top stack item without removing it. Returns -1 if the
254 * stack is already empty, 0 if the stack is not already empty, and
255 * -1 if failure occurs.
257 int top (T &item) const;
259 // = Check boundary conditions.
261 /// Returns 1 if the container is empty, otherwise returns 0.
263 * Performs constant time check to see if stack is empty.
265 int is_empty () const;
267 /// Returns 1 if the container is full, otherwise returns 0.
269 * Performs constant time check to see if stack is full.
271 int is_full () const;
273 /// The number of items in the stack.
275 * Constant time access to the current size of the stack.
277 size_t size () const;
279 /// Dump the state of an object.
280 void dump () const;
282 /// Declare the dynamic allocation hooks.
283 ACE_ALLOC_HOOK_DECLARE;
285 private:
286 /// Size of the allocated data.
287 size_t size_;
289 /// Keeps track of the current top of stack.
290 size_t top_;
292 /// Holds the stack's contents.
293 T stack_[ACE_SIZE];
296 //----------------------------------------
298 template<class T> class ACE_Ordered_MultiSet;
299 template<class T> class ACE_Ordered_MultiSet_Iterator;
302 * @class ACE_DNode
304 * @brief Implementation element in a bilinked list.
306 template<class T>
307 class ACE_DNode
309 friend class ACE_Ordered_MultiSet<T>;
310 friend class ACE_Ordered_MultiSet_Iterator<T>;
312 public:
313 /// This isn't necessary, but it keeps some compilers happy.
314 ~ACE_DNode ();
316 /// Declare the dynamic allocation hooks.
317 ACE_ALLOC_HOOK_DECLARE;
319 private:
320 ACE_DNode (const T &i, ACE_DNode<T> *n = 0, ACE_DNode<T> *p = 0);
322 /// Pointer to next element in the list of {ACE_DNode}s.
323 ACE_DNode<T> *next_;
325 /// Pointer to previous element in the list of {ACE_DNode}s.
326 ACE_DNode<T> *prev_;
328 /// Current value of the item in this node.
329 T item_;
334 * @class ACE_Unbounded_Stack
336 * @brief Implement a generic LIFO abstract data type.
338 * This implementation of an unbounded Stack uses a linked list.
339 * If you use the {insert} or {remove} methods you should keep
340 * in mind that duplicate entries aren't allowed. In general,
341 * therefore, you should avoid the use of these methods since
342 * they aren't really part of the ADT stack. The stack is implemented
343 * as a doubly linked list.
345 * <b> Requirements and Performance Characteristics</b>
346 * - Internal Structure
347 * Double linked list
348 * - Duplicates allowed?
349 * No
350 * - Random access allowed?
351 * No
352 * - Search speed
353 * Linear
354 * - Insert/replace speed
355 * Linear
356 * - Iterator still valid after change to container?
357 * Yes
358 * - Frees memory for removed elements?
359 * Yes
360 * - Items inserted by
361 * Value
362 * - Requirements for contained type
363 * -# Default constructor
364 * -# Copy constructor
365 * -# operator=
367 template <class T>
368 class ACE_Unbounded_Stack
370 public:
371 friend class ACE_Unbounded_Stack_Iterator<T>;
373 // Trait definition.
374 typedef ACE_Unbounded_Stack_Iterator<T> ITERATOR;
376 // = Initialization, assignment, and termination methods.
377 /// Initialize a new stack so that it is empty. Use user defined
378 /// allocation strategy if specified.
380 * Initialize an empty stack using the user specified allocation strategy
381 * if provided.
383 ACE_Unbounded_Stack (ACE_Allocator *the_allocator = 0);
385 /// The copy constructor (performs initialization).
387 * Initialize this stack to be an exact copy of {s}.
389 ACE_Unbounded_Stack (const ACE_Unbounded_Stack<T> &s);
391 /// Assignment operator (performs assignment).
393 * Perform a deep copy of the rhs into the lhs.
395 void operator= (const ACE_Unbounded_Stack<T> &s);
397 /// Perform actions needed when stack goes out of scope.
399 * Destroy the underlying list for the stack.
401 ~ACE_Unbounded_Stack ();
403 // = Classic Stack operations.
406 ///Push an element onto the top of stack.
408 * Place a new item on top of the stack. Returns -1 if the stack
409 * is already full, 0 if the stack is not already full, and -1 if
410 * failure occurs.
412 int push (const T &new_item);
414 ///Pop the top element of the stack.
416 * Remove and return the top stack item. Returns -1 if the stack is
417 * already empty, 0 if the stack is not already empty, and -1 if
418 * failure occurs.
420 int pop (T &item);
422 ///Examine the top of the stack.
424 * Return top stack item without removing it. Returns -1 if the
425 * stack is already empty, 0 if the stack is not already empty, and
426 * -1 if failure occurs.
428 int top (T &item) const;
430 // = Check boundary conditions.
432 /// Returns 1 if the container is empty, otherwise returns 0.
434 * Constant time check to see if the stack is empty.
436 int is_empty () const;
438 /// Returns 1 if the container is full, otherwise returns 0.
440 * Always resturns 0 since the stack is unbounded.
442 int is_full () const;
444 // = Auxiliary methods (not strictly part of the Stack ADT).
446 ///Linear Insert of an item.
448 * Insert {new_item} into the Stack at the head (but doesn't allow
449 * duplicates). Returns -1 if failures occur, 1 if item is already
450 * present (i.e., no duplicates are allowed), else 0.
452 int insert (const T &new_item);
454 /// Remove @a item from the Stack. Returns 0 if it removes the item,
455 /// -1 if it can't find the item, and -1 if a failure occurs.
457 * Linear remove operation.
459 int remove (const T &item);
461 /// Finds if @a item occurs the set. Returns 0 if finds, else -1.
463 * Linear find operation.
465 int find (const T &item) const;
467 /// The number of items in the stack.
469 * Constant time access to the current stack size.
471 size_t size () const;
473 /// Dump the state of an object.
474 void dump () const;
476 /// Declare the dynamic allocation hooks.
477 ACE_ALLOC_HOOK_DECLARE;
479 private:
480 /// Delete all the nodes in the stack.
481 void delete_all_nodes ();
483 /// Copy all nodes from {s} to {this}.
484 void copy_all_nodes (const ACE_Unbounded_Stack<T> &s);
486 /// Head of the linked list of Nodes.
487 ACE_Node<T> *head_;
489 /// Current size of the stack.
490 size_t cur_size_;
492 /// Allocation strategy of the stack.
493 ACE_Allocator *allocator_;
497 * @class ACE_Unbounded_Stack_Iterator
499 * @brief Implement an iterator over an unbounded Stack.
501 template <class T>
502 class ACE_Unbounded_Stack_Iterator
504 public:
505 /// Move to the first element in the {stack}.
506 ACE_Unbounded_Stack_Iterator (ACE_Unbounded_Stack<T> &stack);
508 // = Iteration methods.
510 /// Pass back the @a next_item that hasn't been seen in the Stack.
511 /// Returns 0 when all items have been seen, else 1.
512 int next (T *&next_item);
514 /// Move forward by one element in the Stack. Returns 0 when all the
515 /// items in the Stack have been seen, else 1.
516 int advance ();
518 /// Move to the first element in the Stack. Returns 0 if the
519 /// Stack is empty, else 1.
520 int first ();
522 /// Returns 1 when all items have been seen, else 0.
523 int done () const;
525 /// Dump the state of an object.
526 void dump () const;
528 /// Declare the dynamic allocation hooks.
529 ACE_ALLOC_HOOK_DECLARE;
531 private:
532 /// Pointer to the current node in the iteration.
533 ACE_Node<T> *current_;
535 /// Pointer to the Stack we're iterating over.
536 ACE_Unbounded_Stack<T> &stack_;
539 template <class T>
540 class ACE_Double_Linked_List;
543 * @class ACE_Double_Linked_List_Iterator_Base
545 * @brief Implements a common base class for iterators for a double
546 * linked list ADT
548 template <class T>
549 class ACE_Double_Linked_List_Iterator_Base
551 public:
552 // = Iteration methods.
554 /// Passes back the {entry} under the iterator. Returns 0 if the
555 /// iteration has completed, otherwise 1
556 int next (T *&) const;
559 * @deprecated Return the address of next (current) unvisited item in
560 * the list. 0 if there is no more element available.
562 T *next () const;
564 /// Returns 1 when all items have been seen, else 0.
565 int done () const;
567 /// STL-like iterator dereference operator: returns a reference
568 /// to the node underneath the iterator.
569 T & operator* () const ;
572 * Retasks the iterator to iterate over a new
573 * Double_Linked_List. This allows clients to reuse an iterator
574 * without incurring the constructor overhead. If you do use this,
575 * be aware that if there are more than one reference to this
576 * iterator, the other "clients" may be very bothered when their
577 * iterator changes. @@ Here be dragons. Comments?
579 void reset (ACE_Double_Linked_List<T> &);
581 /// Declare the dynamic allocation hooks.
582 ACE_ALLOC_HOOK_DECLARE;
584 protected:
585 /// Constructor
586 ACE_Double_Linked_List_Iterator_Base (const ACE_Double_Linked_List<T> &);
588 /// Copy constructor.
589 ACE_Double_Linked_List_Iterator_Base (const
590 ACE_Double_Linked_List_Iterator_Base<T>
591 &iter);
593 // = Iteration methods.
595 * Move to the first element of the list. Returns 0 if the list is
596 * empty, else 1.
597 * @note the head of the ACE_DLList is actually a null entry, so the
598 * first element is actually the 2n'd entry
600 int go_head ();
602 /// Move to the last element of the list. Returns 0 if the list is
603 /// empty, else 1.
604 int go_tail ();
607 * Check if we reach the end of the list. Can also be used to get
608 * the *current* element in the list. Return the address of the
609 * current item if there are still elements left , 0 if we run out
610 * of element.
612 T *not_done () const ;
614 /// Advance to the next element in the list. Return the address of the
615 /// next element if there are more, 0 otherwise.
616 T *do_advance ();
618 /// Retreat to the previous element in the list. Return the address
619 /// of the previous element if there are more, 0 otherwise.
620 T *do_retreat ();
622 /// Dump the state of an object.
623 void dump_i () const;
625 /// Remember where we are.
626 T *current_;
628 const ACE_Double_Linked_List<T> *dllist_;
632 * @class ACE_Double_Linked_List_Iterator
634 * @brief Implements an iterator for a double linked list ADT
636 * Iterate thru the double-linked list. This class provides
637 * an interface that let users access the internal element
638 * addresses directly. Notice {class T} must declare
639 * ACE_Double_Linked_List&lt;T&gt;,
640 * ACE_Double_Linked_List_Iterator_Base &lt;T&gt; and
641 * ACE_Double_Linked_List_Iterator as friend classes and class T
642 * should also have data members T* next_ and T* prev_.
644 template <class T>
645 class ACE_Double_Linked_List_Iterator : public ACE_Double_Linked_List_Iterator_Base <T>
647 public:
648 ACE_Double_Linked_List_Iterator (const ACE_Double_Linked_List<T> &);
651 * Retasks the iterator to iterate over a new
652 * Double_Linked_List. This allows clients to reuse an iterator
653 * without incurring the constructor overhead. If you do use this,
654 * be aware that if there are more than one reference to this
655 * iterator, the other "clients" may be very bothered when their
656 * iterator changes.
657 * @@ Here be dragons. Comments?
659 void reset (ACE_Double_Linked_List<T> &);
661 /// Move to the first element in the list. Returns 0 if the
662 /// list is empty, else 1.
663 int first ();
665 /// Move forward by one element in the list. Returns 0 when all the
666 /// items in the list have been seen, else 1.
667 int advance ();
670 * Advance the iterator while removing the original item from the
671 * list. Return a pointer points to the original (removed) item.
672 * If @a dont_remove equals false, this function behaves like {advance}
673 * but return 0 (NULL) instead.
675 T* advance_and_remove (bool dont_remove);
677 // = STL-style iteration methods
679 /// Prefix advance.
680 ACE_Double_Linked_List_Iterator<T> & operator++ ();
682 /// Postfix advance.
683 ACE_Double_Linked_List_Iterator<T> operator++ (int);
685 /// Prefix reverse.
686 ACE_Double_Linked_List_Iterator<T> & operator-- ();
688 /// Postfix reverse.
689 ACE_Double_Linked_List_Iterator<T> operator-- (int);
691 /// Dump the state of an object.
692 void dump () const;
694 /// Declare the dynamic allocation hooks.
695 ACE_ALLOC_HOOK_DECLARE;
699 * @class ACE_Double_Linked_List_Reverse_Iterator
701 * @brief Implements a reverse iterator for a double linked list ADT
703 * Iterate backwards over the double-linked list. This class
704 * provide an interface that let users access the internal
705 * element addresses directly, which seems to break the
706 * encapsulation. Notice {class T} must declare
707 * ACE_Double_Linked_List&lt;T&gt;,
708 * ACE_Double_Linked_List_Iterator_Base &lt;T&gt; and
709 * ACE_Double_Linked_List_Iterator as friend classes and class T
710 * should also have data members T* next_ and T* prev_.
712 template <class T>
713 class ACE_Double_Linked_List_Reverse_Iterator : public ACE_Double_Linked_List_Iterator_Base <T>
715 public:
716 ACE_Double_Linked_List_Reverse_Iterator (ACE_Double_Linked_List<T> &);
719 * Retasks the iterator to iterate over a new
720 * Double_Linked_List. This allows clients to reuse an iterator
721 * without incurring the constructor overhead. If you do use this,
722 * be aware that if there are more than one reference to this
723 * iterator, the other "clients" may be very bothered when their
724 * iterator changes.
725 * @@ Here be dragons. Comments?
727 void reset (ACE_Double_Linked_List<T> &);
729 /// Move to the first element in the list. Returns 0 if the
730 /// list is empty, else 1.
731 int first ();
733 /// Move forward by one element in the list. Returns 0 when all the
734 /// items in the list have been seen, else 1.
735 int advance ();
738 * Advance the iterator while removing the original item from the
739 * list. Return a pointer points to the original (removed) item.
740 * If @a dont_remove equals false, this function behaves like {advance}
741 * but return 0 (NULL) instead.
743 T* advance_and_remove (bool dont_remove);
745 // = STL-style iteration methods
747 /// Prefix advance.
748 ACE_Double_Linked_List_Reverse_Iterator<T> & operator++ ();
750 /// Postfix advance.
751 ACE_Double_Linked_List_Reverse_Iterator<T> operator++ (int);
753 /// Prefix reverse.
754 ACE_Double_Linked_List_Reverse_Iterator<T> & operator-- ();
756 /// Postfix reverse.
757 ACE_Double_Linked_List_Reverse_Iterator<T> operator-- (int);
759 /// Dump the state of an object.
760 void dump () const;
762 /// Declare the dynamic allocation hooks.
763 ACE_ALLOC_HOOK_DECLARE;
768 * @class ACE_Double_Linked_List
770 * @brief A double-linked list implementation.
772 * This implementation of an unbounded double-linked list uses a
773 * circular linked list with a dummy node. It is pretty much
774 * like the {ACE_Unbounded_Queue} except that it allows removing
775 * of a specific element from a specific location.
776 * Notice that this class is an implementation of a very simple
777 * data structure. This is *NOT* a container class. You can use the
778 * class to implement other contains classes but it is *NOT* a
779 * general purpose container class.
780 * The parameter class *MUST* have members T* prev and T* next
781 * and users of this class are responsible to follow the general
782 * rules of using double-linked lists to maintaining the list
783 * integrity.
784 * If you need a double linked container class, use the DLList
785 * class which is a container but delegates to the Double_Linked_List
786 * class.
788 * <b> Requirements and Performance Characteristics</b>
789 * - Internal Structure
790 * Double Linked List
791 * - Duplicates allowed?
792 * Yes
793 * - Random access allowed?
794 * No
795 * - Search speed
796 * N/A
797 * - Insert/replace speed
798 * Linear
799 * - Iterator still valid after change to container?
800 * Yes
801 * - Frees memory for removed elements?
802 * No
803 * - Items inserted by
804 * Value
805 * - Requirements for contained type
806 * -# Default constructor
807 * -# Copy constructor
808 * -# operator=
810 template <class T>
811 class ACE_Double_Linked_List
813 public:
814 friend class ACE_Double_Linked_List_Iterator_Base<T>;
815 friend class ACE_Double_Linked_List_Iterator<T>;
816 friend class ACE_Double_Linked_List_Reverse_Iterator<T>;
818 // Trait definition.
819 typedef ACE_Double_Linked_List_Iterator<T> ITERATOR;
820 typedef ACE_Double_Linked_List_Reverse_Iterator<T> REVERSE_ITERATOR;
822 /// construction. Use user specified allocation strategy
823 /// if specified.
825 * Initialize an empy list using the allocation strategy specified by the user.
826 * If none is specified, then use default allocation strategy.
828 ACE_Double_Linked_List (ACE_Allocator *the_allocator = 0);
830 /// Copy constructor.
832 * Create a double linked list that is a copy of the provided
833 * parameter.
835 ACE_Double_Linked_List (const ACE_Double_Linked_List<T> &);
837 /// Assignment operator.
839 * Perform a deep copy of the provided list by first deleting the nodes of the
840 * lhs and then copying the nodes of the rhs.
842 void operator= (const ACE_Double_Linked_List<T> &);
844 /// Destructor.
846 * Clean up the memory allocated for the nodes of the list.
848 ~ACE_Double_Linked_List ();
850 // = Check boundary conditions.
852 /// Returns 1 if the container is empty, 0 otherwise.
854 * Performs constant time check to determine if the list is empty.
856 int is_empty () const;
858 /// The list is unbounded, so this always returns 0.
860 * Since the list is unbounded, the method simply returns 0.
862 int is_full () const;
864 // = Classic queue operations.
866 /// Adds @a new_item to the tail of the list. Returns the new item
867 /// that was inserted.
869 * Provides constant time insertion at the end of the list structure.
871 T *insert_tail (T *new_item);
873 /// Adds @a new_item to the head of the list.Returns the new item that
874 /// was inserted.
876 * Provides constant time insertion at the head of the list.
878 T *insert_head (T *new_item);
880 /// Removes the head of the list and returns a pointer to that item.
882 * Removes and returns the first {item} in the list. Returns
883 * internal node's address on success, 0 if the queue was empty.
884 * This method will *not* free the internal node.
886 T* delete_head ();
888 /// Removes the tail of the list and returns a pointer to that item.
890 * Removes and returns the last {item} in the list. Returns
891 * internal nodes's address on success, 0 if the queue was
892 * empty. This method will *not* free the internal node.
894 T *delete_tail ();
896 // = Additional utility methods.
898 ///Empty the list.
900 * Reset the {ACE_Double_Linked_List} to be empty.
901 * Notice that since no one is interested in the items within,
902 * This operation will delete all items.
904 void reset ();
906 /// Get the {slot}th element in the set. Returns -1 if the element
907 /// isn't in the range {0..{size} - 1}, else 0.
909 * Iterates through the list to the desired index and assigns the provides pointer
910 * with the address of the node occupying that index.
912 int get (T *&item, size_t slot = 0);
914 /// The number of items in the queue.
916 * Constant time call to return the current size of the list.
918 size_t size () const;
920 /// Dump the state of an object.
921 void dump () const;
923 /// Use DNode address directly.
925 * Constant time removal of an item from the list using it's address.
927 int remove (T *n);
929 /// Declare the dynamic allocation hooks.
930 ACE_ALLOC_HOOK_DECLARE;
932 protected:
933 /// Delete all the nodes in the list.
935 * Removes and deallocates memory for all of the list nodes.
937 void delete_nodes ();
939 /// Copy nodes from {rhs} into this list.
941 * Copy the elements of the provided list by allocated new nodes and assigning
942 * them with the proper data.
944 void copy_nodes (const ACE_Double_Linked_List<T> &rhs);
946 /// Setup header pointer. Called after we create the head node in ctor.
948 * Initialize the head pointer so that the list has a dummy node.
950 void init_head ();
952 ///Constant time insert a new item into the list structure.
954 * Insert a @a new_item into the list. It will be added before
955 * or after @a old_item. Default is to insert the new item *after*
956 * {head_}. Return 0 if succeed, -1 if error occurred.
958 int insert_element (T *new_item,
959 int before = 0,
960 T *old_item = 0);
962 ///Constant time delete an item from the list structure.
964 * Remove @a item from the list. Return 0 if succeed, -1 otherwise.
965 * Notice that this function checks if item is {head_} and either its
966 * {next_} or {prev_} is NULL. The function resets item's {next_} and
967 * {prev_} to 0 to prevent clobbering the double-linked list if a user
968 * tries to remove the same node again.
970 int remove_element (T *item);
972 /// Head of the circular double-linked list.
973 T *head_;
975 /// Size of this list.
976 size_t size_;
978 /// Allocation Strategy of the queue.
979 ACE_Allocator *allocator_;
983 template <class T> class ACE_DLList;
984 template <class T> class ACE_DLList_Iterator;
985 template <class T> class ACE_DLList_Reverse_Iterator;
987 typedef ACE_Double_Linked_List<ACE_DLList_Node> ACE_DLList_Base;
990 * @class ACE_DLList
992 * @brief A double-linked list container class.
994 * ACE_DLList is a simple, unbounded container implemented using a
995 * double-linked list. It is critical to remember that ACE_DLList inherits
996 * from ACE_Double_Linked_List, wrapping each T pointer in a ACE_DLList_Node
997 * object which satisfies the next/prev pointer requirements imposed by
998 * ACE_Double_Linked_List.
1000 * Each item inserted to an ACE_DLList is a pointer to a T object. The
1001 * caller is responsible for lifetime of the T object. ACE_DLList takes no
1002 * action on the T object; it is not copied on insertion and it is not
1003 * deleted on removal from the ACE_DLList.
1005 template <class T>
1006 class ACE_DLList : public ACE_DLList_Base
1008 friend class ACE_DLList_Node;
1009 friend class ACE_Double_Linked_List_Iterator<T>;
1010 friend class ACE_DLList_Iterator<T>;
1011 friend class ACE_DLList_Reverse_Iterator<T>;
1013 public:
1014 /// Delegates to ACE_Double_Linked_List.
1015 void operator= (const ACE_DLList<T> &l);
1018 * @name Queue-like insert and delete methods
1020 //@{
1022 * Insert pointer for a new item at the tail of the list.
1024 * @return Pointer to item inserted; 0 on error.
1026 T *insert_tail (T *new_item);
1029 * Insert pointer for a new item at the head of the list.
1031 * @return Pointer to item inserted; 0 on error.
1033 T *insert_head (T *new_item);
1036 * Removes the item at the head of the list and returns its pointer.
1038 * @return Pointer to previously inserted item; 0 if the list is empty,
1039 * an error occurred, or the original pointer inserted was 0.
1041 T *delete_head ();
1044 * Removes the item at the tail of the list and returns its pointer.
1046 * @return Pointer to previously inserted item; 0 if the list is empty,
1047 * an error occurred, or the original pointer inserted was 0.
1049 T *delete_tail ();
1050 //@}
1053 * Provide random access to any item in the list.
1055 * @param item Receives a pointer to the T object pointer held at the
1056 * specified position in the list.
1057 * @param slot Position in the list to access. The first position is 0.
1059 * @retval 0 Success; T pointer returned in item.
1060 * @retval -1 Error, most likely slot is outside the range of the list.
1062 int get (T *&item, size_t slot = 0);
1064 /// Delegates to ACE_Double_Linked_List.
1065 void dump () const;
1067 /// Delegates to ACE_Double_Linked_List.
1068 int remove (ACE_DLList_Node *n);
1071 * Constructor.
1073 * @param the_allocator Allocator to use for allocating ACE_DLList_Node
1074 * objects that wrap T objects for inclusion in the
1075 * list. If nullptr, ACE_Allocator::instance() is used.
1077 ACE_DLList (ACE_Allocator *the_allocator = nullptr);
1079 /// Delegates to ACE_Double_Linked_List.
1080 ACE_DLList (const ACE_DLList<T> &l);
1083 * Deletes all ACE_DLList_Node objects in the list starting from the head.
1084 * No T objects referred to by the deleted ACE_DLList_Node objects are
1085 * modified or freed. If you desire all of the T objects in the list to
1086 * be deleted as well, code such as this should be used prior to destroying
1087 * the ACE_DLList:
1088 * @code
1089 ACE_DLList<Item> list;
1090 ... // insert dynamically allocated Items...
1091 Item *p = nullptr;
1092 while ((p = list.delete_head()) != nullptr)
1093 delete p;
1094 @endcode
1096 ~ACE_DLList ();
1100 * @class ACE_DLList_Iterator
1102 * @brief A double-linked list container class iterator.
1104 * This implementation uses ACE_Double_Linked_List_Iterator to
1105 * perform the logic behind this container class. It delegates
1106 * all of its calls to ACE_Double_Linked_List_Iterator.
1108 template <class T>
1109 class ACE_DLList_Iterator : public ACE_Double_Linked_List_Iterator <ACE_DLList_Node>
1111 friend class ACE_DLList<T>;
1112 friend class ACE_DLList_Node;
1114 public:
1115 ACE_DLList_Iterator (ACE_DLList<T> &l);
1118 * Retasks the iterator to iterate over a new
1119 * Double_Linked_List. This allows clients to reuse an iterator
1120 * without incurring the constructor overhead. If you do use this,
1121 * be aware that if there are more than one reference to this
1122 * iterator, the other "clients" may be very bothered when their
1123 * iterator changes.
1124 * @@ Here be dragons. Comments?
1126 void reset (ACE_DLList<T> &l);
1128 // = Iteration methods.
1129 /// Move forward by one element in the list. Returns 0 when all the
1130 /// items in the list have been seen, else 1.
1131 int advance ();
1133 /// Pass back the {next_item} that hasn't been seen in the list.
1134 /// Returns 0 when all items have been seen, else 1.
1135 int next (T *&);
1138 * @deprecated Delegates to ACE_Double_Linked_List_Iterator, except that
1139 * whereas the Double_Linked_List version of next returns the node, this next
1140 * returns the contents of the node
1142 T *next () const;
1145 * Removes the current item (i.e., {next}) from the list.
1146 * Note that DLList iterators do not support {advance_and_remove}
1147 * directly (defined in its base class) and you will need to
1148 * release the element returned by it.
1150 int remove ();
1152 /// Delegates to ACE_Double_Linked_List_Iterator.
1153 void dump () const;
1155 private:
1156 ACE_DLList<T> *list_;
1160 * @class ACE_DLList_Reverse_Iterator
1162 * @brief A double-linked list container class iterator.
1164 * This implementation uses ACE_Double_Linked_List_Iterator to
1165 * perform the logic behind this container class. It delegates
1166 * all of its calls to ACE_Double_Linked_List_Iterator.
1168 template <class T>
1169 class ACE_DLList_Reverse_Iterator : public ACE_Double_Linked_List_Reverse_Iterator <ACE_DLList_Node>
1171 friend class ACE_DLList<T>;
1172 friend class ACE_DLList_Node;
1174 public:
1175 ACE_DLList_Reverse_Iterator (ACE_DLList<T> &l);
1178 * Retasks the iterator to iterate over a new
1179 * Double_Linked_List. This allows clients to reuse an iterator
1180 * without incurring the constructor overhead. If you do use this,
1181 * be aware that if there are more than one reference to this
1182 * iterator, the other "clients" may be very bothered when their
1183 * iterator changes.
1184 * @@ Here be dragons. Comments?
1186 void reset (ACE_DLList<T> &l);
1188 // = Iteration methods.
1189 /// Move forward by one element in the list. Returns 0 when all the
1190 /// items in the list have been seen, else 1.
1191 int advance ();
1193 /// Pass back the {next_item} that hasn't been seen in the list.
1194 /// Returns 0 when all items have been seen, else 1.
1195 int next (T *&);
1197 /// @deprecated Delegates to ACE_Double_Linked_List_Iterator.
1198 T *next () const;
1200 /// Removes the current item (i.e., {next}) from the list.
1201 /// Note that DLList iterators do not support {advance_and_remove}
1202 /// directly (defined in its base class) and you will need to
1203 /// release the element returned by it.
1204 int remove ();
1206 /// Delegates to ACE_Double_Linked_List_Iterator.
1207 void dump () const;
1209 private:
1210 ACE_DLList<T> *list_;
1213 // Forward declaration.
1214 template <class T, size_t ACE_SIZE>
1215 class ACE_Fixed_Set;
1218 * @class ACE_Fixed_Set_Iterator_Base
1220 * @brief Implements a common base class for iterators for a unordered set.
1222 template <class T, size_t ACE_SIZE>
1223 class ACE_Fixed_Set_Iterator_Base
1225 public:
1226 // = Iteration methods.
1228 /// Pass back the {next_item} that hasn't been seen in the Set.
1229 /// Returns 0 when all items have been seen, else 1.
1230 int next (T *&next_item);
1232 /// Move forward by one element in the set. Returns 0 when all the
1233 /// items in the set have been seen, else 1.
1234 int advance ();
1236 /// Move to the first element in the set. Returns 0 if the
1237 /// set is empty, else 1.
1238 int first ();
1240 /// Returns 1 when all items have been seen, else 0.
1241 int done () const;
1243 /// Declare the dynamic allocation hooks.
1244 ACE_ALLOC_HOOK_DECLARE;
1246 protected:
1247 ACE_Fixed_Set_Iterator_Base (ACE_Fixed_Set<T, ACE_SIZE> &s);
1249 /// Set we are iterating over.
1250 ACE_Fixed_Set<T, ACE_SIZE> &s_;
1252 /// How far we've advanced over the set.
1253 ssize_t next_;
1255 /// The number of non free items that the iterator had pointed at.
1256 size_t iterated_items_;
1258 /// Dump the state of an object.
1259 void dump_i () const;
1261 /// Pass back the {next_item} that hasn't been seen in the Set.
1262 /// Returns 0 when all items have been seen, else 1.
1263 int next_i (T *&next_item);
1267 * @class ACE_Fixed_Set_Iterator
1269 * @brief Iterates through an unordered set.
1271 * This implementation of an unordered set uses a fixed array.
1272 * Allows deletions while iteration is occurring.
1274 template <class T, size_t ACE_SIZE>
1275 class ACE_Fixed_Set_Iterator : public ACE_Fixed_Set_Iterator_Base <T, ACE_SIZE>
1277 public:
1278 ACE_Fixed_Set_Iterator (ACE_Fixed_Set<T, ACE_SIZE> &s);
1280 // = Iteration methods.
1282 /// Pass back the {next_item} that hasn't been seen in the Set.
1283 /// Returns 0 when all items have been seen, else 1.
1284 int next (T *&next_item);
1286 /// Dump the state of an object.
1287 void dump () const;
1289 /// Remove the item where the itearetor is located at.
1290 /// Returns 1 if it removes a item, else 0.
1291 /// Pass back the removed {item}.
1292 int remove (T *&item);
1294 /// STL-like iterator dereference operator: returns a reference
1295 /// to the node underneath the iterator.
1296 T & operator* ();
1298 /// Declare the dynamic allocation hooks.
1299 ACE_ALLOC_HOOK_DECLARE;
1303 * @class ACE_Fixed_Set_Const_Iterator
1305 * @brief Iterates through a const unordered set.
1307 * This implementation of an unordered set uses a fixed array.
1309 template <class T, size_t ACE_SIZE>
1310 class ACE_Fixed_Set_Const_Iterator : public ACE_Fixed_Set_Iterator_Base <T, ACE_SIZE>
1312 public:
1313 ACE_Fixed_Set_Const_Iterator (const ACE_Fixed_Set<T, ACE_SIZE> &s);
1315 // = Iteration methods.
1317 /// Pass back the {next_item} that hasn't been seen in the Set.
1318 /// Returns 0 when all items have been seen, else 1.
1319 int next (const T *&next_item);
1321 /// Dump the state of an object.
1322 void dump () const;
1324 /// STL-like iterator dereference operator: returns a reference
1325 /// to the node underneath the iterator.
1326 const T & operator* () const ;
1328 /// Declare the dynamic allocation hooks.
1329 ACE_ALLOC_HOOK_DECLARE;
1333 * @class ACE_Fixed_Set
1335 * @brief Implement a simple unordered set of {T} with maximum {ACE_SIZE}.
1337 * This implementation of an unordered set uses a fixed array.
1338 * It does not allow duplicate members. The set provides linear insertion/deletion
1339 * operations.
1341 * <b> Requirements and Performance Characteristics</b>
1342 * - Internal Structure
1343 * Fixed array
1344 * - Duplicates allowed?
1345 * No
1346 * - Random access allowed?
1347 * No
1348 * - Search speed
1349 * Linear
1350 * - Insert/replace speed
1351 * Linear
1352 * - Iterator still valid after change to container?
1353 * Yes
1354 * - Frees memory for removed elements?
1355 * No
1356 * - Items inserted by
1357 * Value
1358 * - Requirements for contained type
1359 * -# Default constructor
1360 * -# Copy constructor
1361 * -# operator=
1362 * -# operator==
1364 template <class T, size_t ACE_SIZE>
1365 class ACE_Fixed_Set
1367 public:
1368 friend class ACE_Fixed_Set_Iterator_Base<T, ACE_SIZE>;
1369 friend class ACE_Fixed_Set_Iterator<T, ACE_SIZE>;
1370 friend class ACE_Fixed_Set_Const_Iterator<T, ACE_SIZE>;
1372 // Trait definitions.
1373 typedef ACE_Fixed_Set_Iterator<T, ACE_SIZE> ITERATOR;
1374 typedef ACE_Fixed_Set_Const_Iterator<T, ACE_SIZE> CONST_ITERATOR;
1376 /// Default Constructor.
1378 * Creates an empy set
1380 ACE_Fixed_Set ();
1382 /// Copy constructor.
1384 * Initializes a set to be a copy of the set parameter.
1386 ACE_Fixed_Set (const ACE_Fixed_Set<T, ACE_SIZE> &);
1388 /// Assignment operator.
1390 * Deep copy of one set to another.
1392 void operator= (const ACE_Fixed_Set<T, ACE_SIZE> &);
1394 /// Destructor.
1396 * Destroys a set.
1398 ~ACE_Fixed_Set ();
1400 // = Check boundary conditions.
1402 /// Returns 1 if the container is empty, otherwise returns 0.
1404 * Performs constant time check to determine if a set is empty.
1406 int is_empty () const;
1408 /// Returns 1 if the container is full, otherwise returns 0.
1410 * Performs a constant time check to see if the set is full.
1412 int is_full () const;
1414 // = Classic unordered set operations.
1416 ///Linear time insertion of an item unique to the set.
1418 * Insert @a new_item into the set (doesn't allow duplicates).
1419 * Returns -1 if failures occur, 1 if item is already present, else
1420 * 0.
1422 int insert (const T &new_item);
1424 ///Linear time removal operation of an item.
1426 * Remove first occurrence of {item} from the set. Returns 0 if
1427 * it removes the item, -1 if it can't find the item, and -1 if a
1428 * failure occurs. Removal doesn't reclaim memory for the @a item.
1430 int remove (const T &item);
1432 /// Finds if @a item occurs in the set. Returns 0 if finds, else -1.
1434 * Performs a linear find operation for the specified @a item.
1436 int find (const T &item) const;
1438 /// Size of the set.
1440 * Returns the current size of the set.
1442 size_t size () const;
1444 /// Dump the state of an object.
1445 void dump () const;
1447 /// Declare the dynamic allocation hooks.
1448 ACE_ALLOC_HOOK_DECLARE;
1450 private:
1451 /// Holds the contents of the set.
1452 struct
1454 /// Item in the set.
1455 T item_;
1457 /// Keeps track of whether this item is in use or not.
1458 int is_free_;
1459 } search_structure_[ACE_SIZE];
1461 /// Current size of the set.
1462 size_t cur_size_;
1464 /// Maximum size of the set.
1465 size_t max_size_;
1468 // Forward declaration.
1469 template <class T>
1470 class ACE_Bounded_Set;
1473 * @class ACE_Bounded_Set_Iterator
1475 * @brief Iterates through an unordered set.
1477 * This implementation of an unordered set uses a Bounded array.
1478 * Allows deletions while iteration is occurring.
1480 template <class T>
1481 class ACE_Bounded_Set_Iterator
1483 public:
1484 ACE_Bounded_Set_Iterator (ACE_Bounded_Set<T> &s);
1486 // = Iteration methods.
1488 /// Pass back the {next_item} that hasn't been seen in the Set.
1489 /// Returns 0 when all items have been seen, else 1.
1490 int next (T *&next_item);
1492 /// Move forward by one element in the set. Returns 0 when all the
1493 /// items in the set have been seen, else 1.
1494 int advance ();
1496 /// Move to the first element in the set. Returns 0 if the
1497 /// set is empty, else 1.
1498 int first ();
1500 /// Returns 1 when all items have been seen, else 0.
1501 int done () const;
1503 /// Dump the state of an object.
1504 void dump () const;
1506 /// Declare the dynamic allocation hooks.
1507 ACE_ALLOC_HOOK_DECLARE;
1509 private:
1510 /// Set we are iterating over.
1511 ACE_Bounded_Set<T> &s_;
1513 /// How far we've advanced over the set.
1514 ssize_t next_;
1519 * @class ACE_Bounded_Set
1521 * @brief Implement a simple unordered set of {T} with maximum
1522 * set at creation time.
1524 * This implementation of an unordered set uses a Bounded array.
1525 * This implementation does not allow duplicates. It provides
1526 * linear insert/remove/find operations. Insertion/removal does not
1527 * invalidate iterators, but caution should be taken to ensure
1528 * expected behavior. Once initialized, the object has a maximum size
1529 * which can only be increased by the assignment of another larger Bounded_Set.
1531 * <b> Requirements and Performance Characteristics</b>
1532 * - Internal Structure
1533 * Bounded array which can grow via assignment
1534 * - Duplicates allowed?
1535 * No
1536 * - Random access allowed?
1537 * No
1538 * - Search speed
1539 * Linear
1540 * - Insert/replace speed
1541 * Linear
1542 * - Iterator still valid after change to container?
1543 * Yes
1544 * - Frees memory for removed elements?
1545 * No
1546 * - Items inserted by
1547 * Value
1548 * - Requirements for contained type
1549 * -# Default constructor
1550 * -# Copy constructor
1551 * -# operator=
1552 * -# operator==
1554 template <class T>
1555 class ACE_Bounded_Set
1557 public:
1558 friend class ACE_Bounded_Set_Iterator<T>;
1560 // Trait definition.
1561 typedef ACE_Bounded_Set_Iterator<T> ITERATOR;
1563 enum
1565 DEFAULT_SIZE = 10
1568 /// Construct a Bounded_Set using the default size.
1570 * The default constructor initializes the Bounded_Set to a maximum size
1571 * specified by the DEFAULT_SIZE.
1573 ACE_Bounded_Set ();
1575 /// Construct a Bounded_Set with the provided sizeB.
1577 * Initialize the Bounded_Set to have a maximum size equal to the size
1578 * parameter specified.
1580 ACE_Bounded_Set (size_t size);
1582 /// Construct a Bounded_Set that is a copy of the provides Bounded_Set.
1584 * Initialize the Bounded_Set to be a copy of the Bounded_Set parameter.
1586 ACE_Bounded_Set (const ACE_Bounded_Set<T> &);
1588 /// Assignment operator.
1590 * The assignment will make a deep copy of the Bounded_Set provided. If the
1591 * rhs has more elements than the capacity of the lhs, then the lhs will be
1592 * deleted and reallocated to accomadate the larger number of elements.
1594 void operator= (const ACE_Bounded_Set<T> &);
1596 /// Destructor
1598 * Clean up the underlying dynamically allocated memory that is used by
1599 * the Bounded_Set.
1601 ~ACE_Bounded_Set ();
1603 // = Check boundary conditions.
1605 /// Returns 1 if the container is empty, otherwise returns 0.
1607 * A constant time check is performed to determine if the Bounded_Set is
1608 * empty.
1610 int is_empty () const;
1612 /// Returns 1 if the container is full, otherwise returns 0.
1614 * Performs a constant time check to determine if the Bounded_Set is at
1615 * capacity.
1617 int is_full () const;
1619 // = Classic unordered set operations.
1621 ///Inserts a new element unique to the set.
1623 * Insert @a new_item into the set (doesn't allow duplicates) in linear
1624 * time.
1625 * Returns -1 if failures occur, 1 if item is already present, else
1626 * 0.
1628 int insert (const T &new_item);
1630 ///Finds the specified element and removes it from the set.
1632 * Remove first occurrence of @a item from the set. Returns 0 if it
1633 * removes the item, -1 if it can't find the item, and -1 if a
1634 * failure occurs. The linear remove operation does not reclaim the
1635 * memory associated with the removed item.
1637 int remove (const T &item);
1639 /// Finds if @a item occurs in the set. Returns 0 if finds, else -1.
1641 * find preforms a linear search for {item} and returns 0 on successful
1642 * find and -1 otherwise.
1644 int find (const T &item) const;
1646 /// Size of the set.
1648 * Returns a size_t representing the current size of the set.
1650 size_t size () const;
1652 /// Dump the state of an object.
1653 void dump () const;
1655 /// Declare the dynamic allocation hooks.
1656 ACE_ALLOC_HOOK_DECLARE;
1658 private:
1659 struct Search_Structure
1661 /// Item in the set.
1662 T item_;
1664 /// Keeps track of whether this item is in use or not.
1665 int is_free_;
1668 /// Holds the contents of the set.
1669 Search_Structure *search_structure_;
1671 /// Current size of the set.
1672 size_t cur_size_;
1674 /// Maximum size of the set.
1675 size_t max_size_;
1679 * @class ACE_Ordered_MultiSet_Iterator
1681 * @brief Implement a bidirectional iterator over an ordered multiset.
1682 * This class template requires that < operator semantics be
1683 * defined for the parameterized type {T}, but does not impose
1684 * any restriction on how that ordering operator is implemented.
1686 template <class T>
1687 class ACE_Ordered_MultiSet_Iterator
1689 public:
1690 friend class ACE_Ordered_MultiSet<T>;
1692 ACE_Ordered_MultiSet_Iterator (ACE_Ordered_MultiSet<T> &s);
1694 // = Iteration methods.
1696 /// Pass back the {next_item} that hasn't been seen in the ordered multiset.
1697 /// Returns 0 when all items have been seen, else 1.
1698 int next (T *&next_item) const;
1700 /// Repositions the iterator at the first item in the ordered multiset
1701 /// Returns 0 if the list is empty else 1.
1702 int first ();
1704 /// Repositions the iterator at the last item in the ordered multiset
1705 /// Returns 0 if the list is empty else 1.
1706 int last ();
1708 /// Move forward by one element in the set. Returns 0 when all the
1709 /// items in the set have been seen, else 1.
1710 int advance ();
1712 /// Move backward by one element in the set. Returns 0 when all the
1713 /// items in the set have been seen, else 1.
1714 int retreat ();
1716 /// Returns 1 when all items have been seen, else 0.
1717 int done () const;
1719 /// Dump the state of an object.
1720 void dump () const;
1722 /// Returns a reference to the internal element {this} is pointing to.
1723 T& operator* ();
1725 /// Declare the dynamic allocation hooks.
1726 ACE_ALLOC_HOOK_DECLARE;
1728 private:
1729 /// Pointer to the current node in the iteration.
1730 ACE_DNode<T> *current_;
1732 /// Pointer to the set we're iterating over.
1733 ACE_Ordered_MultiSet<T> &set_;
1738 * @class ACE_Ordered_MultiSet
1740 * @brief Implement a simple ordered multiset of {T} of unbounded size
1741 * that allows duplicates. This class template requires that <
1742 * operator semantics be defined for the parameterized type {T}, but
1743 * does not impose any restriction on how that ordering operator is
1744 * implemented. The set is implemented as a linked list.
1746 * <b> Requirements and Performance Characteristics</b>
1747 * - Internal Structure
1748 * Double linked list
1749 * - Duplicates allowed?
1750 * Yes
1751 * - Random access allowed?
1752 * No
1753 * - Search speed
1754 * Linear
1755 * - Insert/replace speed
1756 * Linear
1757 * - Iterator still valid after change to container?
1758 * Yes
1759 * - Frees memory for removed elements?
1760 * Yes
1761 * - Items inserted by
1762 * Value
1763 * - Requirements for contained type
1764 * -# Default constructor
1765 * -# Copy constructor
1766 * -# operator=
1767 * -# operator==
1768 * -# operator<
1770 template <class T>
1771 class ACE_Ordered_MultiSet
1773 public:
1774 friend class ACE_Ordered_MultiSet_Iterator<T>;
1776 // Trait definition.
1777 typedef ACE_Ordered_MultiSet_Iterator<T> ITERATOR;
1779 /// Constructor. Use user specified allocation strategy
1780 /// if specified.
1782 * Initialize the set using the allocation strategy specified. If none, use the
1783 * default strategy.
1785 ACE_Ordered_MultiSet (ACE_Allocator *the_allocator = 0);
1787 /// Copy constructor.
1789 * Initialize the set to be a copy of the provided set.
1791 ACE_Ordered_MultiSet (const ACE_Ordered_MultiSet<T> &);
1793 /// Destructor.
1795 * Delete the nodes of the set.
1797 ~ACE_Ordered_MultiSet ();
1799 /// Assignment operator.
1801 * Delete the nodes in lhs, and copy the nodes from the rhs.
1803 void operator= (const ACE_Ordered_MultiSet<T> &);
1805 // = Check boundary conditions.
1807 /// Returns 1 if the container is empty, otherwise returns 0.
1809 * Constant time check to determine if the set is empty.
1811 int is_empty () const;
1813 /// Size of the set.
1815 * Constant time check to determine the size of the set.
1817 size_t size () const;
1819 // = Classic unordered set operations.
1821 /// Insert @a new_item into the ordered multiset.
1822 /// Returns -1 if failures occur, else 0.
1824 * Linear time, order preserving insert into the set beginning at the head.
1826 int insert (const T &new_item);
1828 ///Linear time insert beginning at the point specified by the provided iterator.
1830 * Insert @a new_item into the ordered multiset, starting its search at
1831 * the node pointed to by the iterator, and if insertion was successful,
1832 * updates the iterator to point to the newly inserted node.
1833 * Returns -1 if failures occur, else 0.
1835 int insert (const T &new_item, ITERATOR &iter);
1837 /// Remove first occurrence of @a item from the set. Returns 0 if
1838 /// it removes the item, -1 if it can't find the item.
1840 * Linear time search operation which removes the item from the set if found .
1842 int remove (const T &item);
1844 ///Linear find operation.
1846 * Finds first occurrence of @a item in the multiset, using the iterator's
1847 * current position as a hint to improve performance. If find succeeds,
1848 * it positions the iterator at that node and returns 0, or if it cannot
1849 * locate the node, it leaves the iterator alone and just returns -1.
1851 int find (const T &item, ITERATOR &iter) const;
1853 /// Reset the ACE_Ordered_MultiSet to be empty.
1855 * Delete the nodes inside the set.
1857 void reset ();
1859 /// Dump the state of an object.
1860 void dump () const;
1862 /// Declare the dynamic allocation hooks.
1863 ACE_ALLOC_HOOK_DECLARE;
1865 private:
1867 * Insert @a item, starting its search at the position given,
1868 * and if successful updates the passed pointer to point to
1869 * the newly inserted item's node.
1871 int insert_from (const T &item, ACE_DNode<T> *start_position,
1872 ACE_DNode<T> **new_position);
1875 * Looks for first occurrence of @a item in the ordered set, using the
1876 * passed starting position as a hint: if there is such an instance, it
1877 * updates the new_position pointer to point to this node and returns 0;
1878 * if there is no such node, then if there is a node before where the
1879 * item would have been, it updates the new_position pointer to point
1880 * to this node and returns -1; if there is no such node, then if there
1881 * is a node after where the item would have been, it updates the
1882 * new_position pointer to point to this node (or 0 if there is no such
1883 * node) and returns 1;
1885 int locate (const T &item, ACE_DNode<T> *start_position,
1886 ACE_DNode<T> *&new_position) const;
1888 /// Delete all the nodes in the Set.
1889 void delete_nodes ();
1891 /// Copy nodes into this set.
1892 void copy_nodes (const ACE_Ordered_MultiSet<T> &);
1894 /// Head of the bilinked list of Nodes.
1895 ACE_DNode<T> *head_;
1897 /// Head of the bilinked list of Nodes.
1898 ACE_DNode<T> *tail_;
1900 /// Current size of the set.
1901 size_t cur_size_;
1903 /// Allocation strategy of the set.
1904 ACE_Allocator *allocator_;
1907 // ****************************************************************
1910 * @class ACE_Array
1912 * @brief A dynamic array class.
1914 * This class extends ACE_Array_Base, adding comparison operators.
1916 * <b> Requirements and Performance Characteristics</b>
1917 * - Internal Structure
1918 * Dynamic array
1919 * - Duplicates allowed?
1920 * Yes
1921 * - Random access allowed?
1922 * Yes
1923 * - Search speed
1924 * N/A
1925 * - Insert/replace speed
1926 * O(1)
1927 * - Iterator still valid after change to container?
1928 * - In general, yes.
1929 * - If array size is changed during iteration, no.
1930 * - Frees memory for removed elements?
1931 * No
1932 * - Items inserted by
1933 * Value
1934 * - Requirements for contained type
1935 * -# Default constructor
1936 * -# Copy constructor
1937 * -# operator=
1938 * -# operator!=
1940 * @sa ACE_Array_Base. This class inherits its operations and requirements.
1942 template <class T>
1943 class ACE_Array : public ACE_Array_Base<T>
1945 public:
1946 // Define a "trait"
1947 typedef T TYPE;
1948 typedef ACE_Array_Iterator<T> ITERATOR;
1950 /// Dynamically create an uninitialized array.
1952 * Initialize an empty array of the specified size using the provided
1953 * allocation strategy.
1955 ACE_Array (size_t size = 0,
1956 ACE_Allocator* alloc = 0);
1958 /// Dynamically initialize the entire array to the {default_value}.
1960 * Initialize an array the given size placing the default_value in each index.
1962 ACE_Array (size_t size,
1963 const T &default_value,
1964 ACE_Allocator* alloc = 0);
1966 ///Copy constructor.
1968 * The copy constructor performs initialization by making an exact
1969 * copy of the contents of parameter {s}, i.e., *this == s will
1970 * return true.
1972 ACE_Array (const ACE_Array<T> &s);
1974 ///Assignment operator
1976 * Assignment operator performs an assignment by making an exact
1977 * copy of the contents of parameter {s}, i.e., *this == s will
1978 * return true. Note that if the {max_size_} of {array_} is >= than
1979 * {s.max_size_} we can copy it without reallocating. However, if
1980 * {max_size_} is < {s.max_size_} we must delete the {array_},
1981 * reallocate a new {array_}, and then copy the contents of {s}.
1983 void operator= (const ACE_Array<T> &s);
1985 // = Compare operators
1987 ///Equality comparison operator.
1989 * Compare this array with {s} for equality. Two arrays are equal
1990 * if their {size}'s are equal and all the elements from 0 .. {size}
1991 * are equal.
1993 bool operator== (const ACE_Array<T> &s) const;
1995 ///Inequality comparison operator.
1997 * Compare this array with {s} for inequality such that {*this} !=
1998 * {s} is always the complement of the boolean return value of
1999 * {*this} == {s}.
2001 bool operator!= (const ACE_Array<T> &s) const;
2004 ACE_END_VERSIONED_NAMESPACE_DECL
2006 #if defined (__ACE_INLINE__)
2007 #include "ace/Containers_T.inl"
2008 #endif /* __ACE_INLINE__ */
2010 #include "ace/Containers_T.cpp"
2012 #include /**/ "ace/post.h"
2014 #endif /* ACE_CONTAINERS_T_H */