HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_LinkList.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: Utility Library (C++)
7  *
8  * COMMENTS:
9  * This class implements a doubly linked list that maintains
10  * a replacement list of nodes.
11  *
12  */
13 
14 #ifndef __UT_LinkList_h__
15 #define __UT_LinkList_h__
16 
17 #include "UT_API.h"
18 #include "UT_Swap.h"
19 #include <iosfwd>
20 
22 public:
23  // Constructor and destructor:
24  UT_LinkNode(void) { predNode = succNode = 0; }
25  virtual ~UT_LinkNode(void);
26 
27  // Query/set methods:
28  UT_LinkNode *&prev() { return predNode; }
29  UT_LinkNode *&next() { return succNode; }
30  const UT_LinkNode *prev() const { return predNode; }
31  const UT_LinkNode *next() const { return succNode; }
32 
33  // I/O friends:
34  friend std::ostream &operator<<(std::ostream &os, const UT_LinkNode &n)
35  {
36  n.outTo(os);
37  return os;
38  }
39 
40 protected:
41  // Query the name of this class:
42  virtual const char *className(void) const;
43 
44  // Our own I/O methods, so we can redefine them in derived classes:
45  virtual void outTo (std::ostream &os) const;
46 
47 private:
48  // Pointers to predecessor and successor respectively:
49  UT_LinkNode *predNode;
50  UT_LinkNode *succNode;
51 };
52 
53 
55 public:
56  // Trivial class constructor and destructor. The destructor
57  // deallocates every node in the active and replacement lists.
58  UT_LinkList(void) { first=last=stashHead=0; count=0; }
59  virtual ~UT_LinkList(void);
60 
61  void swap( UT_LinkList &other );
62 
63  // Reverse the order of the active nodes:
64  virtual void reverse(void);
65 
66  // Add nodes to the list, or delete them:
67  // append() appends a node, insert() inserts it at index 'where';
68  // remove() deletes the node from the list and leaves it intact;
69  // destroy() deletes the node from the list and deallocates it.
70  // If the node is not in the list, or if nodeIdx is invalid,
71  // both remove() and destroy() return 0. If the node is 0,
72  // remove() and destroy() will act upon the last element in the
73  // list. None of the functions below checks whether the node
74  // is or is not in the list at the time it is deleted or added.
75  // To check for existence, see inList().
76  void append (UT_LinkNode *node);
77  void insert (UT_LinkNode *node, int where);
78  // node is the node to insert, before and after are the node already
79  // in the list that you wish to insert before/after.
80  void insertBefore(UT_LinkNode *node, UT_LinkNode *before);
81  void insertAfter(UT_LinkNode *node, UT_LinkNode *after);
82 
83  UT_LinkNode *remove (UT_LinkNode *node = 0);
84  UT_LinkNode *remove (int nodeIdx);
85  void destroy(UT_LinkNode *node = 0);
86  void destroy(int nodeIdx);
87 
88  // Take a node from the active list and stash it into the
89  // replacement list. recall() performs the inverse procedure.
90  // If the node parameter is 0, stash and recall will act upon
91  // the last elemenent added to the respective list.
92  UT_LinkNode *stash (UT_LinkNode *node = 0);
93  UT_LinkNode *stash (int nodeIdx);
94  UT_LinkNode *recall(UT_LinkNode *node = 0);
95  UT_LinkNode *recall(UT_LinkNode *node, int nodeIdx);
96 
97  // Return the index of the node in the list or vice-versa.
98  // The first method returns -1 if not found; the 2nd method
99  // returns 0 if unsuccessful.
100  int find(UT_LinkNode *node) const;
101  UT_LinkNode *find(int nodeIdx) const;
102 
103  // Check if the node is in the active list: return 1 if true, o if
104  // false.
105  int inList(UT_LinkNode *node) const;
106 
107 
108  // Return the predecessor or the successor of a node, or the
109  // first or last node in the list respectively.
110  UT_LinkNode *prev(UT_LinkNode *node) const { return node->prev(); }
111  UT_LinkNode *next(UT_LinkNode *node) const { return node->next(); }
112  UT_LinkNode *head() const { return first; }
113  UT_LinkNode *tail() const { return last; }
114 
115  // Some iteration functions, in case you are not using the separate
116  // iterator class:
117  UT_LinkNode *iterateInit() const { return first; }
119  {
120  return curr ? curr->next() : first;
121  }
123  {
124  return curr ? curr->prev() : last;
125  }
126  UT_LinkNode *iterateFastNext(UT_LinkNode *curr) const {return curr->next();}
127  UT_LinkNode *iterateFastPrev(UT_LinkNode *curr) const {return curr->prev();}
128 
129  // Clear the linked list: the list of stashed nodes, the active
130  // list, or both.
131  void clearStashed();
132  void clearActive();
133  void clear() { clearActive(); clearStashed(); }
134 
135  // Return the length of the list or just find out whether it's empty.
136  int length() const { return count; }
137  int isEmpty() const { return count == 0; }
138 
139  // Apply a user-defined function to each element of the linked
140  // list, as long as the function returns zero. If applyFct returns
141  // 0, apply() stops traversing the list and returns the current
142  // node; otherwise, apply() returns 0.
143  UT_LinkNode *apply(int (*applyFct)(UT_LinkNode *n, void *d), void *d);
144 
145  // Copy the other list's data into us. The source gets cleared.
146  UT_LinkList &operator=(UT_LinkList &src);
147 
148  // Append the other list's data to ours. The source gets cleared.
149  UT_LinkList &operator+=(UT_LinkList &src);
150 
151  // I/O friends:
152  friend std::ostream &operator<<(std::ostream &os, const UT_LinkList &v)
153  {
154  v.outTo(os);
155  return os;
156  }
157 
158 protected:
159  // Current node of iteration, in case you are not using the iterator class.
160  // Remove a node from the replacement list. Remove the last
161  // one inserted if 0.
162  UT_LinkNode *unStash(UT_LinkNode *node = 0);
163 
164  // Query the stash head:
165  UT_LinkNode *firstStash() const { return stashHead; }
166 
167  // Query the name of this class:
168  virtual const char *className(void) const;
169 
170  // Our own I/O methods, so we can redefine them in derived classes:
171  virtual void outTo (std::ostream &os) const;
172 
173  // Head of the stash list.
175 
176  // Just reset the state of the link list
177  // Not, this will cause memory leaks unless used with caution,
178  // ie. list sorting
179  void reset() { first = last = 0; count = 0; }
180 
181 
182 private:
183 
184  // DATA
185 
186  // First and last nodes in the active list.
188  UT_LinkNode *last;
189 
190  // Number of nodes in the active list.
191  int count;
192 };
193 
195 
196 #endif
GLint first
Definition: glcorearb.h:404
const GLdouble * v
Definition: glcorearb.h:836
#define UT_API
Definition: UT_API.h:13
GLdouble n
Definition: glcorearb.h:2007
GLint GLsizei count
Definition: glcorearb.h:404
#define UT_SWAPPER_CLASS(T)
Definition: UT_Swap.h:60
void swap(TfErrorTransport &l, TfErrorTransport &r)
GLenum src
Definition: glcorearb.h:1792