/* -*- C++ -*- */ // $Id$ // ============================================================================ // // = LIBRARY // ace // // = FILENAME // Containers.h // // = AUTHOR // Doug Schmidt // // ============================================================================ #if !defined (ACE_CONTAINERS_T_H) #define ACE_CONTAINERS_T_H #include "ace/ACE.h" #include "ace/Containers.h" /* Need ACE_DLList_Node */ class ACE_Allocator; template class ACE_Bounded_Stack { // = TITLE // Implement a generic LIFO abstract data type. // // = DESCRIPTION // This implementation of a Stack uses a bounded array // that is allocated dynamically. public: // = Initialization, assignemnt, and termination methods. ACE_Bounded_Stack (size_t size); // Initialize a new stack so that it is empty. ACE_Bounded_Stack (const ACE_Bounded_Stack &s); // The copy constructor (performs initialization). void operator= (const ACE_Bounded_Stack &s); // Assignment operator (performs assignment). ~ACE_Bounded_Stack (void); // Perform actions needed when stack goes out of scope. // = Classic Stack operations. int push (const T &new_item); // Place a new item on top of the stack. Returns -1 if the stack // is already full, 0 if the stack is not already full, and -1 if // failure occurs. int pop (T &item); // Remove and return the top stack item. Returns -1 if the stack is // already empty, 0 if the stack is not already empty, and -1 if // failure occurs. int top (T &item) const; // Return top stack item without removing it. Returns -1 if the // stack is already empty, 0 if the stack is not already empty, and // -1 if failure occurs. // = Check boundary conditions. int is_empty (void) const; // Returns 1 if the container is empty, otherwise returns 0. int is_full (void) const; // Returns 1 if the container is full, otherwise returns 0. size_t size (void) const; // The number of items in the stack. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: size_t size_; // Size of the dynamically allocated data. size_t top_; // Keeps track of the current top of stack. T *stack_; // Holds the stack's contents. }; //---------------------------------------- template class ACE_Fixed_Stack { // = TITLE // Implement a generic LIFO abstract data type. // // = DESCRIPTION // This implementation of a Stack uses a fixed array // with the size fixed at instantiation time. public: // = Initialization, assignemnt, and termination methods. ACE_Fixed_Stack (void); // Initialize a new stack so that it is empty. ACE_Fixed_Stack (const ACE_Fixed_Stack &s); // The copy constructor (performs initialization). void operator= (const ACE_Fixed_Stack &s); // Assignment operator (performs assignment). ~ACE_Fixed_Stack (void); // Perform actions needed when stack goes out of scope. // = Classic Stack operations. int push (const T &new_item); // Place a new item on top of the stack. Returns -1 if the stack // is already full, 0 if the stack is not already full, and -1 if // failure occurs. int pop (T &item); // Remove and return the top stack item. Returns -1 if the stack is // already empty, 0 if the stack is not already empty, and -1 if // failure occurs. int top (T &item) const; // Return top stack item without removing it. Returns -1 if the // stack is already empty, 0 if the stack is not already empty, and // -1 if failure occurs. // = Check boundary conditions. int is_empty (void) const; // Returns 1 if the container is empty, otherwise returns 0. int is_full (void) const; // Returns 1 if the container is full, otherwise returns 0. size_t size (void) const; // The number of items in the stack. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: size_t size_; // Size of the allocated data. size_t top_; // Keeps track of the current top of stack. T stack_[ACE_SIZE]; // Holds the stack's contents. }; //---------------------------------------- // Forward declarations. template class ACE_Unbounded_Set; template class ACE_Unbounded_Set_Iterator; template class ACE_Unbounded_Queue; template class ACE_Unbounded_Queue_Iterator; template class ACE_Unbounded_Stack; template class ACE_Unbounded_Stack_Iterator; template class ACE_Ordered_MultiSet; template class ACE_Ordered_MultiSet_Iterator; template class ACE_Node { // = TITLE // Implementation element in a Queue, Set, and Stack. public: friend class ACE_Unbounded_Queue; friend class ACE_Unbounded_Queue_Iterator; friend class ACE_Unbounded_Set; friend class ACE_Unbounded_Set_Iterator; friend class ACE_Unbounded_Stack; friend class ACE_Unbounded_Stack_Iterator; # if ! defined (ACE_HAS_BROKEN_NOOP_DTORS) ~ACE_Node (void); // This isn't necessary, but it keeps some compilers happy. # endif /* ! defined (ACE_HAS_BROKEN_NOOP_DTORS) */ private: // = Initialization methods ACE_Node (const T &i, ACE_Node *n); ACE_Node (ACE_Node *n = 0, int = 0); ACE_Node (const ACE_Node &n); ACE_Node *next_; // Pointer to next element in the list of s. T item_; // Current value of the item in this node. }; template class ACE_DNode { // = TITLE // Implementation element in a bilinked list. friend class ACE_Ordered_MultiSet; friend class ACE_Ordered_MultiSet_Iterator; public: ~ACE_DNode (void); // This isn't necessary, but it keeps the compiler happy. private: // = Initialization methods ACE_DNode (const T &i, ACE_DNode *n = 0, ACE_DNode *p = 0); ACE_DNode *next_; // Pointer to next element in the list of s. ACE_DNode *prev_; // Pointer to previous element in the list of s. T item_; // Current value of the item in this node. }; template class ACE_Unbounded_Stack { // = TITLE // Implement a generic LIFO abstract data type. // // = DESCRIPTION // This implementation of an unbounded Stack uses a linked list. public: friend class ACE_Unbounded_Stack_Iterator; // Trait definition. typedef ACE_Unbounded_Stack_Iterator ITERATOR; // = Initialization, assignemnt, and termination methods. ACE_Unbounded_Stack (ACE_Allocator *alloc = 0); // Initialize a new stack so that it is empty. Use user defined // allocation strategy if specified. ACE_Unbounded_Stack (const ACE_Unbounded_Stack &s); // The copy constructor (performs initialization). void operator= (const ACE_Unbounded_Stack &s); // Assignment operator (performs assignment). ~ACE_Unbounded_Stack (void); // Perform actions needed when stack goes out of scope. // = Classic Stack operations. int push (const T &new_item); // Place a new item on top of the stack. Returns -1 if the stack // is already full, 0 if the stack is not already full, and -1 if // failure occurs. int pop (T &item); // Remove and return the top stack item. Returns -1 if the stack is // already empty, 0 if the stack is not already empty, and -1 if // failure occurs. int top (T &item) const; // Return top stack item without removing it. Returns -1 if the // stack is already empty, 0 if the stack is not already empty, and // -1 if failure occurs. // = Check boundary conditions. int is_empty (void) const; // Returns 1 if the container is empty, otherwise returns 0. int is_full (void) const; // Returns 1 if the container is full, otherwise returns 0. // = Auxiliary methods (not strictly part of the Stack ADT). int insert (const T &new_item); // Insert into the Stack at the head (but doesn't allow // duplicates). Returns -1 if failures occur, 1 if item is already // present, else 0. int remove (const T &item); // Remove from the Stack. Returns 0 if it removes the item, // -1 if it can't find the item, and -1 if a failure occurs. int find (const T &item) const; // Finds if occurs the set. Returns 0 if finds, else -1. size_t size (void) const; // The number of items in the stack. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: void delete_all_nodes (void); // Delete all the nodes in the stack. void copy_all_nodes (const ACE_Unbounded_Stack &s); // Copy all nodes from to . ACE_Node *head_; // Head of the linked list of Nodes. size_t cur_size_; // Current size of the stack. ACE_Allocator *allocator_; // Allocation strategy of the stack. }; template class ACE_Unbounded_Stack_Iterator { // = TITLE // Implement an iterator over an unbounded Stack. public: // = Initialization method. ACE_Unbounded_Stack_Iterator (ACE_Unbounded_Stack &); // = Iteration methods. int next (T *&next_item); // Pass back the that hasn't been seen in the Stack. // Returns 0 when all items have been seen, else 1. int advance (void); // Move forward by one element in the Stack. Returns 0 when all the // items in the Stack have been seen, else 1. int first (void); // Move to the first element in the Stack. Returns 0 if the // Stack is empty, else 1. int done (void) const; // Returns 1 when all items have been seen, else 0. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: ACE_Node *current_; // Pointer to the current node in the iteration. ACE_Unbounded_Stack &stack_; // Pointer to the Stack we're iterating over. }; template class ACE_Unbounded_Queue; template class ACE_Unbounded_Queue_Iterator { // = TITLE // Implement an iterator over an unbounded queue. public: // = Initialization method. ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue &q, int end = 0); // = Iteration methods. int next (T *&next_item); // Pass back the that hasn't been seen in the queue. // Returns 0 when all items have been seen, else 1. int advance (void); // Move forward by one element in the set. Returns 0 when all the // items in the queue have been seen, else 1. int first (void); // Move to the first element in the queue. Returns 0 if the // queue is empty, else 1. int done (void) const; // Returns 1 when all items have been seen, else 0. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: ACE_Node *current_; // Pointer to the current node in the iteration. ACE_Unbounded_Queue &queue_; // Pointer to the queue we're iterating over. }; template class ACE_Unbounded_Queue { // = TITLE // A Queue of "infinite" length. // // = DESCRIPTION // This implementation of an unbounded queue uses a circular // linked list with a dummy node. public: friend class ACE_Unbounded_Queue_Iterator; // Trait definition. typedef ACE_Unbounded_Queue_Iterator ITERATOR; // = Initialization and termination methods. ACE_Unbounded_Queue (ACE_Allocator *alloc = 0); // construction. Use user specified allocation strategy // if specified. ACE_Unbounded_Queue (const ACE_Unbounded_Queue &); // Copy constructor. void operator= (const ACE_Unbounded_Queue &); // Assignment operator. ~ACE_Unbounded_Queue (void); // construction. // = Check boundary conditions. int is_empty (void) const; // Returns 1 if the container is empty, otherwise returns 0. int is_full (void) const; // Returns 1 if the container is full, otherwise returns 0. // = Classic queue operations. int enqueue_tail (const T &new_item); // Adds to the tail of the queue. Returns 0 on success, // -1 on failure. int enqueue_head (const T &new_item); // Adds to the head of the queue. Returns 0 on success, // -1 on failure. int dequeue_head (T &item); // Removes and returns the first on the queue. Returns 0 on // success, -1 if the queue was empty. // = Additional utility methods. void reset (void); // Reset the to be empty. int get (T *&item, size_t index = 0) const; // Get the th element in the set. Returns -1 if the element // isn't in the range <0..size() - 1>, else 0. int set (const T &item, size_t index); // Set the th element in the set. Will pad out the set with // empty nodes if is beyond the range <0..size() - 1>. // Returns -1 on failure, 0 if isn't initially in range, and // 0 otherwise. size_t size (void) const; // The number of items in the queue. void dump (void) const; // Dump the state of an object. // = STL-styled unidirectional iterator factory. ACE_Unbounded_Queue_Iterator begin (void); ACE_Unbounded_Queue_Iterator end (void); ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. protected: void delete_nodes (void); // Delete all the nodes in the queue. void copy_nodes (const ACE_Unbounded_Queue &); // Copy nodes into this queue. ACE_Node *head_; // Pointer to the dummy node in the circular linked Queue. size_t cur_size_; // Current size of the queue. ACE_Allocator *allocator_; // Allocation Strategy of the queue. }; template class ACE_Double_Linked_List; template class ACE_Double_Linked_List_Iterator { // = TITLE // Implement an iterator over a container double-linked list // // = DESCRIPTION // Iterate thru the double-linked list. This class provide // an interface that let users access the internal element // addresses directly, which (IMHO) seems to break the // encasulation. Notice must delcare // ACE_Double_Linked_List and // ACE_Double_Linked_List_Iterator as friend classes and class T // should also have data members T* next_ and T* prev_. public: // = Initialization method. ACE_Double_Linked_List_Iterator (ACE_Double_Linked_List &); // = Iteration methods. T *next (void) const; // Return the address of next (current) unvisited item in the list. // 0 if there is no more element available. int advance (void); // Move forward by one element in the list. Returns 0 when all the // items in the list have been seen, else 1. T* advance_and_remove (int dont_remove); // Advance the iterator while removing the original item from the list. // Return a pointer points to the original (removed) item. If // equals 0, this function behaves like advance() but // return 0 (NULL) instead. int first (void); // Move to the first element in the list. Returns 0 if the // list is empty, else 1. int done (void) const; // Returns 1 when all items have been seen, else 0. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. protected: T *not_done (void) const ; // Check if we reach the end of the list. Can also be used to get // the *current* element in the list. Return the address of the // current item if there are still elements left , 0 if we run out // of element. T *do_advance (void); // Advance to the next element in the list. Return the address of the // next element if there are more, 0 otherwise. T *current_; // Remember where we are. ACE_Double_Linked_List &dllist_; }; template class ACE_Double_Linked_List { // = TITLE // A double-linked list implementation. // // = DESCRIPTION // This implementation of an unbounded double-linked list uses a // circular linked list with a dummy node. It is pretty much // like the ACE_Unbounded_Queue except that it allows removing // of a specific element from a specific location. public: friend class ACE_Double_Linked_List_Iterator; // Trait definition. typedef ACE_Double_Linked_List_Iterator ITERATOR; // = Initialization and termination methods. ACE_Double_Linked_List (ACE_Allocator *alloc = 0); // construction. Use user specified allocation strategy // if specified. ACE_Double_Linked_List (ACE_Double_Linked_List &); // Copy constructor. void operator= (ACE_Double_Linked_List &); // Assignment operator. ~ACE_Double_Linked_List (void); // Destructor. // = Check boundary conditions. int is_empty (void) const; // Returns 1 if the container is empty, otherwise returns 0. int is_full (void) const; // Returns 1 if the container is full, otherwise returns 0. // = Classic queue operations. T *insert_tail (T *new_item); // Adds to the tail of the list. Returns the new item // that was inserted. T *insert_head (T *new_item); // Adds to the head of the list.Returns the new item that // was inserted. T* delete_head (void); // Removes and returns the first in the list. Returns // internal node's address on success, 0 if the queue was empty. // This method will *not* free the internal node. T *delete_tail (void); // Removes and returns the last in the list. Returns // internal nodes's address on success, 0 if the queue was // empty. This method will *not* free the internal node. // = Additional utility methods. void reset (void); // Reset the to be empty. // Notice that since no one is interested in the items within, // This operation will delete all items. int get (T *&item, size_t index = 0); // Get the th element in the set. Returns -1 if the element // isn't in the range <0..size() - 1>, else 0. size_t size (void) const; // The number of items in the queue. void dump (void) const; // Dump the state of an object. int remove (T *n); // Use DNode address directly. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. protected: void delete_nodes (void); // Delete all the nodes in the list. void copy_nodes (ACE_Double_Linked_List &); // Copy nodes into this list. void init_head (void); // Setup header pointer. Called after we create the head node in ctor. int insert_element (T *new_item, int before = 0, T *old_item = 0); // Insert a into the list. It will be added before // or after . Default is to insert the new item *after* // . Return 0 if succeed, -1 if error occured. int remove_element (T *item); // Remove an from the list. Return 0 if succeed, -1 otherwise. // Notice that this function checks if item is and either its // or is NULL. The function resets item's and // to 0 to prevent clobbering the double-linked list if a user // tries to remove the same node again. T *head_; // Head of the circular double-linked list. size_t size_; // Size of this list. ACE_Allocator *allocator_; // Allocation Strategy of the queue. }; template class ACE_DLList; template class ACE_DLList_Iterator; typedef ACE_Double_Linked_List ACE_DLList_Base; typedef ACE_Double_Linked_List_Iterator ACE_DLList_Iterator_Base; template class ACE_DLList : public ACE_DLList_Base { // = TITLE // A double-linked list container class. // // = DESCRIPTION // This implementation uses ACE_Double_Linked_List to perform // the logic behind this container class. It delegates all of its // calls to ACE_Double_Linked_List. friend class ACE_DLList_Node; friend class ACE_DLList_Iterator; public: void operator= (ACE_DLList &l); // Delegates to ACE_Double_Linked_List. // = Classic queue operations. T *insert_tail (T *new_item); // Delegates to ACE_Double_Linked_List. T *insert_head (T *new_item); // Delegates to ACE_Double_Linked_List. T* delete_head (void); // Delegates to ACE_Double_Linked_List. T *delete_tail (void); // Delegates to ACE_Double_Linked_List. // = Additional utility methods. int get (T *&item, size_t index = 0); // Delegates to ACE_Double_Linked_List. void dump (void) const; // Delegates to ACE_Double_Linked_List. // = Initialization and termination methods. ACE_DLList (ACE_Allocator *alloc = 0); // Delegates to ACE_Double_Linked_List. ACE_DLList (ACE_DLList &l); // Delegates to ACE_Double_Linked_List. ~ACE_DLList (void); // Deletes the list starting from the head. }; template class ACE_DLList_Iterator : public ACE_DLList_Iterator_Base { // = TITLE // A double-linked list container class iterator. // // = DESCRIPTION // This implementation uses ACE_Double_Linked_List_Iterator to // perform the logic behind this container class. It delegates // all of its calls to ACE_Double_Linked_List_Iterator. friend class ACE_DLList; friend class ACE_DLList_Node; public: // = Initialization method. ACE_DLList_Iterator (ACE_DLList &l); // = Iteration methods. T *next (void) const; // Delegates to ACE_Double_Linked_List_Iterator. int remove (void); // Removes the current item (i.e., this->next()) from the list. void dump (void) const; // Delegates to ACE_Double_Linked_List_Iterator. }; template class ACE_Unbounded_Set_Iterator { // = TITLE // Implement an iterator over an unbounded set. public: // = Initialization method. ACE_Unbounded_Set_Iterator (ACE_Unbounded_Set &s, int end = 0); // = Iteration methods. int next (T *&next_item); // Pass back the that hasn't been seen in the Set. // Returns 0 when all items have been seen, else 1. int advance (void); // Move forward by one element in the set. Returns 0 when all the // items in the set have been seen, else 1. int first (void); // Move to the first element in the set. Returns 0 if the // set is empty, else 1. int done (void) const; // Returns 1 when all items have been seen, else 0. void dump (void) const; // Dump the state of an object. // = STL styled iteration, compare, and reference functions. ACE_Unbounded_Set_Iterator operator++ (void); // Postfix advance. ACE_Unbounded_Set_Iterator& operator++ (int); // Prefix advance. T& operator* (void); // Returns a reference to the interal element is pointing to. int operator== (const ACE_Unbounded_Set_Iterator &) const; int operator!= (const ACE_Unbounded_Set_Iterator &) const; // Check if two iterators point to the same position ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: ACE_Node *current_; // Pointer to the current node in the iteration. ACE_Unbounded_Set *set_; // Pointer to the set we're iterating over. }; template class ACE_Unbounded_Set { // = TITLE // Implement a simple unordered set of of unbounded size. // // = DESCRIPTION // This implementation of an unordered set uses a circular // linked list with a dummy node. This implementation does not // allow duplicates, but it maintains FIFO ordering of insertions. public: friend class ACE_Unbounded_Set_Iterator; // Trait definition. typedef ACE_Unbounded_Set_Iterator ITERATOR; typedef ACE_Unbounded_Set_Iterator iterator; // = Initialization and termination methods. ACE_Unbounded_Set (ACE_Allocator *alloc = 0); // Constructor. Use user specified allocation strategy // if specified. ACE_Unbounded_Set (const ACE_Unbounded_Set &); // Copy constructor. void operator= (const ACE_Unbounded_Set &); // Assignment operator. ~ACE_Unbounded_Set (void); // Destructor. // = Check boundary conditions. int is_empty (void) const; // Returns 1 if the container is empty, otherwise returns 0. int is_full (void) const; // Returns 1 if the container is full, otherwise returns 0. // = Classic unordered set operations. int insert (const T &new_item); // Insert into the set (doesn't allow duplicates). // Returns -1 if failures occur, 1 if item is already present, else // 0. int remove (const T &item); // Remove first occurrence of from the set. Returns 0 if // it removes the item, -1 if it can't find the item, and -1 if a // failure occurs. int find (const T &item) const; // Finds if occurs in the set. Returns 0 if find succeeds, // else -1. size_t size (void) const; // Size of the set. void dump (void) const; // Dump the state of an object. void reset (void); // Reset the to be empty. // = STL-styled unidirectional iterator factory. ACE_Unbounded_Set_Iterator begin (void); ACE_Unbounded_Set_Iterator end (void); ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: int insert_tail (const T &item); // Insert at the tail of the set (doesn't check for // duplicates). void delete_nodes (void); // Delete all the nodes in the Set. void copy_nodes (const ACE_Unbounded_Set &); // Copy nodes into this set. ACE_Node *head_; // Head of the linked list of Nodes. size_t cur_size_; // Current size of the set. ACE_Allocator *allocator_; // Allocation strategy of the set. }; // Forward declaration. template class ACE_Fixed_Set; template class ACE_Fixed_Set_Iterator { // = TITLE // Interates through an unordered set. // // = DESCRIPTION // This implementation of an unordered set uses a fixed array. // Allows deletions while iteration is occurring. public: // = Initialization method. ACE_Fixed_Set_Iterator (ACE_Fixed_Set &s); // = Iteration methods. int next (T *&next_item); // Pass back the that hasn't been seen in the Set. // Returns 0 when all items have been seen, else 1. int advance (void); // Move forward by one element in the set. Returns 0 when all the // items in the set have been seen, else 1. int first (void); // Move to the first element in the set. Returns 0 if the // set is empty, else 1. int done (void) const; // Returns 1 when all items have been seen, else 0. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: ACE_Fixed_Set &s_; // Set we are iterating over. ssize_t next_; // How far we've advanced over the set. }; template class ACE_Fixed_Set { // = TITLE // Implement a simple unordered set of with maximum . // // = DESCRIPTION // This implementation of an unordered set uses a fixed array. // This implementation does not allow duplicates... public: friend class ACE_Fixed_Set_Iterator; // Trait definition. typedef ACE_Fixed_Set_Iterator ITERATOR; // = Initialization and termination methods. ACE_Fixed_Set (void); // Constructor. ACE_Fixed_Set (const ACE_Fixed_Set &); // Copy constructor. void operator= (const ACE_Fixed_Set &); // Assignment operator. ~ACE_Fixed_Set (void); // Destructor. // = Check boundary conditions. int is_empty (void) const; // Returns 1 if the container is empty, otherwise returns 0. int is_full (void) const; // Returns 1 if the container is full, otherwise returns 0. // = Classic unordered set operations. int insert (const T &new_item); // Insert into the set (doesn't allow duplicates). // Returns -1 if failures occur, 1 if item is already present, else // 0. int remove (const T &item); // Remove first occurrence of from the set. Returns 0 if // it removes the item, -1 if it can't find the item, and -1 if a // failure occurs. int find (const T &item) const; // Finds if occurs in the set. Returns 0 if finds, else -1. size_t size (void) const; // Size of the set. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: struct { T item_; // Item in the set. int is_free_; // Keeps track of whether this item is in use or not. } search_structure_[ACE_SIZE]; // Holds the contents of the set. size_t cur_size_; // Current size of the set. size_t max_size_; // Maximum size of the set. }; // Forward declaration. template class ACE_Bounded_Set; template class ACE_Bounded_Set_Iterator { // = TITLE // Interates through an unordered set. // // = DESCRIPTION // This implementation of an unordered set uses a Bounded array. // Allows deletions while iteration is occurring. public: // = Initialization method. ACE_Bounded_Set_Iterator (ACE_Bounded_Set &s); // = Iteration methods. int next (T *&next_item); // Pass back the that hasn't been seen in the Set. // Returns 0 when all items have been seen, else 1. int advance (void); // Move forward by one element in the set. Returns 0 when all the // items in the set have been seen, else 1. int first (void); // Move to the first element in the set. Returns 0 if the // set is empty, else 1. int done (void) const; // Returns 1 when all items have been seen, else 0. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: ACE_Bounded_Set &s_; // Set we are iterating over. ssize_t next_; // How far we've advanced over the set. }; template class ACE_Bounded_Set { // = TITLE // Implement a simple unordered set of with maximum // set at creation time. // // = DESCRIPTION // This implementation of an unordered set uses a Bounded array. // This implementation does not allow duplicates... public: friend class ACE_Bounded_Set_Iterator; // Trait definition. typedef ACE_Bounded_Set_Iterator ITERATOR; enum { DEFAULT_SIZE = 10 }; // = Initialization and termination methods. ACE_Bounded_Set (void); // Constructor. ACE_Bounded_Set (size_t size); // Constructor. ACE_Bounded_Set (const ACE_Bounded_Set &); // Copy constructor. void operator= (const ACE_Bounded_Set &); // Assignment operator. ~ACE_Bounded_Set (void); // Destructor // = Check boundary conditions. int is_empty (void) const; // Returns 1 if the container is empty, otherwise returns 0. int is_full (void) const; // Returns 1 if the container is full, otherwise returns 0. // = Classic unordered set operations. int insert (const T &new_item); // Insert into the set (doesn't allow duplicates). // Returns -1 if failures occur, 1 if item is already present, else // 0. int remove (const T &item); // Remove first occurrence of from the set. Returns 0 if it // removes the item, -1 if it can't find the item, and -1 if a // failure occurs. int find (const T &item) const; // Finds if occurs in the set. Returns 0 if finds, else -1. size_t size (void) const; // Size of the set. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: struct Search_Structure { T item_; // Item in the set. int is_free_; // Keeps track of whether this item is in use or not. }; Search_Structure *search_structure_; // Holds the contents of the set. size_t cur_size_; // Current size of the set. size_t max_size_; // Maximum size of the set. }; template class ACE_Ordered_MultiSet_Iterator { // = TITLE // Implement a bidirectional iterator over an ordered multiset. // This class template requires that < operator semantics be defined // for the parameterized type , but does not impose any restriction // on how that ordering operator is implemented. public: friend class ACE_Ordered_MultiSet; // = Initialization method. ACE_Ordered_MultiSet_Iterator (ACE_Ordered_MultiSet &s); // = Iteration methods. int next (T *&next_item) const; // Pass back the that hasn't been seen in the ordered multiset. // Returns 0 when all items have been seen, else 1. int first (void); // Repositions the iterator at the first item in the ordered multiset // Returns 0 if the list is empty else 1. int last (void); // Repositions the iterator at the last item in the ordered multiset // Returns 0 if the list is empty else 1. int advance (void); // Move forward by one element in the set. Returns 0 when all the // items in the set have been seen, else 1. int retreat (void); // Move backward by one element in the set. Returns 0 when all the // items in the set have been seen, else 1. int done (void) const; // Returns 1 when all items have been seen, else 0. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: ACE_DNode *current_; // Pointer to the current node in the iteration. ACE_Ordered_MultiSet &set_; // Pointer to the set we're iterating over. }; template class ACE_Ordered_MultiSet { // = TITLE // Implement a simple ordered multiset of of unbounded size. // This class template requires that < operator semantics be defined // for the parameterized type , but does not impose any restriction // on how that ordering operator is implemented. // // = DESCRIPTION // This implementation of an unordered set uses a circular // linked list with a dummy node. This implementation does not // allow duplicates, but it maintains FIFO ordering of insertions. public: friend class ACE_Ordered_MultiSet_Iterator; // Trait definition. typedef ACE_Ordered_MultiSet_Iterator ITERATOR; // = Initialization and termination methods. ACE_Ordered_MultiSet (ACE_Allocator *alloc = 0); // Constructor. Use user specified allocation strategy // if specified. ACE_Ordered_MultiSet (const ACE_Ordered_MultiSet &); // Copy constructor. ~ACE_Ordered_MultiSet (void); // Destructor. void operator= (const ACE_Ordered_MultiSet &); // Assignment operator. // = Check boundary conditions. int is_empty (void) const; // Returns 1 if the container is empty, otherwise returns 0. size_t size (void) const; // Size of the set. // = Classic unordered set operations. int insert (const T &new_item); // Insert into the ordered multiset. // Returns -1 if failures occur, else 0. int insert (const T &new_item, ITERATOR &iter); // Insert into the ordered multiset, starting its search at // the node pointed to by the iterator, and if insetion was successful, // updates the iterator to point to the newly inserted node. // Returns -1 if failures occur, else 0. int remove (const T &item); // Remove first occurrence of from the set. Returns 0 if // it removes the item, -1 if it can't find the item. int find (const T &item, ITERATOR &iter) const; // Finds first occurrance of in the multiset, using the iterator's // current position as a hint to improve performance. If find succeeds, // it positions the iterator at that node and returns 0, or if it cannot // locate the node, it leaves the iterator alone and just returns -1. void reset (void); // Reset the to be empty. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: int insert_from (const T &item, ACE_DNode *start_position, ACE_DNode **new_position); // Insert , starting its search at the position given, // and if successful updates the passed pointer to point to // the newly inserted item's node. int locate (const T &item, ACE_DNode *start_position, ACE_DNode *&new_position) const; // looks for first occurance of in the ordered set, using the // passed starting position as a hint: if there is such an instance, it // updates the new_position pointer to point to this node and returns 0; // if there is no such node, then if there is a node before where the // item would have been, it updates the new_position pointer to point // to this node and returns -1; if there is no such node, then if there // is a node after where the item would have been, it updates the // new_position pointer to point to this node (or 0 if there is no such // node) and returns 1; void delete_nodes (void); // Delete all the nodes in the Set. void copy_nodes (const ACE_Ordered_MultiSet &); // Copy nodes into this set. ACE_DNode *head_; // Head of the bilinked list of Nodes. ACE_DNode *tail_; // Head of the bilinked list of Nodes. size_t cur_size_; // Current size of the set. ACE_Allocator *allocator_; // Allocation strategy of the set. }; // Forward declaration. template class ACE_Array_Iterator; template class ACE_Array { // = TITLE // Implement a dynamic array class. public: // Define a "trait" typedef T TYPE; // = Exceptions. // = Initialization and termination methods. ACE_Array (size_t size = 0); // Dynamically create an uninitialized array. ACE_Array (size_t size, const T &default_value); // Dynamically initialize the entire array to the . ACE_Array (const ACE_Array &s); // The copy constructor performs initialization by making an exact // copy of the contents of parameter , i.e., *this == s will // return true. void operator= (const ACE_Array &s); // Assignment operator performs an assignment by making an exact // copy of the contents of parameter , i.e., *this == s will // return true. Note that if the of is >= than // we can copy it without reallocating. However, if // is < we must delete the , // reallocate a new , and then copy the contents of . ~ACE_Array (void); // Clean up the array (e.g., delete dynamically allocated memory). // = Set/get methods. T &operator [] (size_t index); // Set item in the array at location . Doesn't // perform range checking. const T &operator [] (size_t index) const; // Get item in the array at location . Doesn't // perform range checking. int set (const T &new_item, size_t index); // Set an item in the array at location . Returns // -1 if is not in range, else returns 0. int get (T &item, size_t index) const; // Get an item in the array at location . Returns -1 if // is not in range, else returns 0. Note that this function // copies the item. If you want to avoid the copy, you can use // the const operator [], but then you'll be responsible for range checking. size_t size (void) const; // Returns the of the array. int size (size_t new_size); // Changes the size of the array to match . // It copies the old contents into the new array. // Return -1 on failure. int operator== (const ACE_Array &s) const; // Compare this array with for equality. Two arrays are equal // if their size()'s are equal and all the elements from 0 .. size() // are equal. int operator!= (const ACE_Array &s) const; // Compare this array with for inequality such that <*this> != // is always the complement of the boolean return value of // <*this> == . private: int in_range (size_t index) const; // Returns 1 if is within range, i.e., 0 >= < // , else returns 0. size_t max_size_; // Maximum size of the array, i.e., the total number of elements // in . size_t cur_size_; // Current size of the array. This starts out being == to // . However, if we are assigned a smaller array, then // will become less than . The purpose of // keeping track of both sizes is to avoid reallocating memory if we // don't have to. T *array_; // Pointer to the array's storage buffer. friend class ACE_Array_Iterator; }; template class ACE_Array_Iterator { // = TITLE // Implement an iterator over an ACE_Array. // // = DESCRIPTION // This iterator is safe in the face of array element deletions. // But it is NOT safe if the array is resized (via the ACE_Array // assignment operator) during iteration. That would be very // odd, and dangerous. public: // = Initialization method. ACE_Array_Iterator (ACE_Array &); // = Iteration methods. int next (T *&next_item); // Pass back the that hasn't been seen in the Array. // Returns 0 when all items have been seen, else 1. int advance (void); // Move forward by one element in the Array. Returns 0 when all the // items in the Array have been seen, else 1. int done (void) const; // Returns 1 when all items have been seen, else 0. void dump (void) const; // Dump the state of an object. ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. private: u_int current_; // Pointer to the current item in the iteration. ACE_Array &array_; // Pointer to the Array we're iterating over. }; #if defined (__ACE_INLINE__) #include "ace/Containers_T.i" #endif /* __ACE_INLINE__ */ #if defined (ACE_TEMPLATES_REQUIRE_SOURCE) #include "ace/Containers_T.cpp" #endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) #pragma implementation ("Containers_T.cpp") #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ #endif /* ACE_CONTAINERS_T_H */