Project

General

Profile

Statistics
| Branch: | Revision:

root / include / cqueue.h @ 2f5cc443

History | View | Annotate | Download (10.4 KB)

1
//==========================================================================
2
//  CQUEUE.H - part of
3
//                     OMNeT++/OMNEST
4
//            Discrete System Simulation in C++
5
//
6
//
7
//  Declaration of the following classes:
8
//    cQueue : queue of cObject descendants
9
//
10
//==========================================================================
11

    
12
/*--------------------------------------------------------------*
13
  Copyright (C) 1992-2008 Andras Varga
14
  Copyright (C) 2006-2008 OpenSim Ltd.
15

16
  This file is distributed WITHOUT ANY WARRANTY. See the file
17
  `license' for details on this and other legal matters.
18
*--------------------------------------------------------------*/
19

    
20
#ifndef __CQUEUE_H
21
#define __CQUEUE_H
22

    
23
#include "cownedobject.h"
24

    
25
NAMESPACE_BEGIN
26

    
27

    
28
/**
29
 * Type for comparison functions for cObject. Return value should be:
30
 * - less than zero if a < b
31
 * - greater than zero if a > b
32
 * - zero if a == b
33
 *
34
 * @ingroup EnumsTypes
35
 */
36
typedef int (*CompareFunc)(cObject *a, cObject *b);
37

    
38

    
39
/**
40
 * Queue class for objects derived from cObject. The default behaviour of
41
 * cQueue is a FIFO: you insert elements at the back using insert(), and
42
 * remove them at the front using pop().
43
 *
44
 * cQueue may be set up to act as a priority queue. This requires the user to
45
 * supply a comparison function.
46
 *
47
 * Ownership of cOwnedObjects may be controlled by invoking setTakeOwnership()
48
 * prior to inserting objects. Objects that cannot track their ownership
49
 * (cObject but not cOwnedObject) are always treated as owned. Whether an
50
 * object is owned or not affects the operation of the destructor, clean(),
51
 * the copy constructor and the dup() method.
52
 *
53
 * @see Iterator
54
 * @ingroup Containers
55
 */
56
class SIM_API cQueue : public cOwnedObject
57
{
58
  private:
59
    struct QElem
60
    {
61
        cObject *obj; // the contained object
62
        QElem *prev;  // element towards the front of the queue
63
        QElem *next;  // element towards the back of the queue
64
    };
65

    
66
  public:
67
    /**
68
     * Walks along a cQueue.
69
     */
70
    class Iterator
71
    {
72
      private:
73
        QElem *p;
74

    
75
      public:
76
        /**
77
         * Constructor. Iterator will walk on the queue passed as argument.
78
         * The iterator can be initialized for forward (front-to-back, using
79
         * <tt>++</tt>) or reverse (back-to-front, using <tt>--</tt>) iteration.
80
         */
81
        Iterator(const cQueue& q, bool reverse=false)
82
                {p=&q ? (reverse ? q.backp : q.frontp) : NULL;}
83

    
84
        /**
85
         * Reinitializes the iterator object.
86
         */
87
        void init(const cQueue& q, bool reverse=false)
88
                {p=&q ? (reverse ? q.backp : q.frontp) : NULL;}
89

    
90
        /**
91
         * Returns the current object.
92
         */
93
        cObject *operator()()  {return p ? p->obj : NULL;}
94

    
95
        /**
96
         * Returns true if the iterator has reached either end of the queue.
97
         */
98
        bool end() const   {return (bool)(p==NULL);}
99

    
100
        /**
101
         * Returns the current object, then moves the iterator to the next item
102
         * (towards the back of the queue). If the iterator has previously
103
         * reached either end of the queue, nothing happens, and one has to
104
         * call init() to restart iterating.
105
         */
106
        cObject *operator++(int)  {if (!p) return NULL; cObject *r=p->obj; p=p->next; return r;}
107

    
108
        /**
109
         * Returns the current object, then moves the iterator to the previous item
110
         * (towards the front of the queue). If the iterator has previously
111
         * reached either end of the queue, nothing happens, and one has to
112
         * call init() to restart iterating.
113
         */
114
        cObject *operator--(int)  {if (!p) return NULL; cObject *r=p->obj; p=p->prev; return r;}
115
    };
116

    
117
    friend class Iterator;
118

    
119
  private:
120
    bool tkownership; //FIXME move it info flags
121
    QElem *frontp, *backp;  // inserting at back(), removal at front()
122
    int n;  // number of items in the queue
123
    CompareFunc compare;   // comparison function; NULL for FIFO
124

    
125
  protected:
126
    // internal functions
127
    QElem *find_qelem(cObject *obj) const;
128
    QElem *find_qelemByName(const char *name) const;
129
    void insbefore_qelem(QElem *p, cObject *obj);
130
    void insafter_qelem(QElem *p, cObject *obj);
131
    cObject *remove_qelem(QElem *p);
132

    
133
  public:
134
    /** @name Constructors, destructor, assignment. */
135
    //@{
136
    /**
137
     * Constructor. When comparison function argument is NULL, the queue will
138
     * act as FIFO, otherwise as priority queue.
139
     */
140
    cQueue(const char *name=NULL, CompareFunc cmp=NULL);
141

    
142
    /**
143
     * Copy constructor. Contained objects that are owned by the queue
144
     * will be duplicated so that the new queue will have its own copy
145
     * of them.
146
     */
147
    cQueue(const cQueue& queue);
148

    
149
    /**
150
     * Destructor. Deletes all contained objects that were owned by it.
151
     */
152
    virtual ~cQueue();
153

    
154
    /**
155
     * Assignment operator. Duplication and assignment work all right with cQueue.
156
     * Contained objects that are owned by the queue will be duplicated
157
     * so that the new queue will have its own copy of them.
158
     *
159
     * The name member is not copied; see cNamedObject's operator=() for more details.
160
     */
161
    cQueue& operator=(const cQueue& queue);
162
    //@}
163

    
164
    /** @name Redefined cObject member functions. */
165
    //@{
166

    
167
    /**
168
     * Duplication and assignment are supported by cQueue.
169
     * Contained objects that are owned by the queue will be duplicated
170
     * so that the new queue will have its own copy of them.
171
     */
172
    virtual cQueue *dup() const  {return new cQueue(*this);}
173

    
174
    /**
175
     * Produces a one-line description of the object's contents.
176
     * See cObject for more details.
177
     */
178
    virtual std::string info() const;
179

    
180
    /**
181
     * Calls v->visit(this) for each contained object.
182
     * See cObject for more details.
183
     */
184
    virtual void forEachChild(cVisitor *v);
185

    
186
    /**
187
     * Serializes the object into an MPI send buffer.
188
     * Used by the simulation kernel for parallel execution.
189
     * See cObject for more details.
190
     */
191
    virtual void parsimPack(cCommBuffer *buffer);
192

    
193
    /**
194
     * Deserializes the object from an MPI receive buffer
195
     * Used by the simulation kernel for parallel execution.
196
     * See cObject for more details.
197
     */
198
    virtual void parsimUnpack(cCommBuffer *buffer);
199
    //@}
200

    
201
    /** @name Setup, insertion and removal functions. */
202
    //@{
203
    /**
204
     * Sets the comparator function. This only affects future insertions,
205
     * i.e. the queue's current content will not be re-sorted.
206
     */
207
    virtual void setup(CompareFunc cmp);
208

    
209
    /**
210
     * Adds an element to the back of the queue. Trying to insert a
211
     * NULL pointer is an error (throws cRuntimeError).
212
     */
213
    virtual void insert(cObject *obj);
214

    
215
    /**
216
     * Inserts exactly before the given object. If the given position
217
     * does not exist or if you try to insert a NULL pointer,
218
     * cRuntimeError is thrown.
219
     */
220
    virtual void insertBefore(cObject *where, cObject *obj);
221

    
222
    /**
223
     * Inserts exactly after the given object. If the given position
224
     * does not exist or if you try to insert a NULL pointer,
225
     * cRuntimeError is thrown.
226
     */
227
    virtual void insertAfter(cObject *where, cObject *obj);
228

    
229
    /**
230
     * Unlinks and returns the object given. If the object is not in the
231
     * queue, NULL pointer is returned.
232
     */
233
    virtual cObject *remove(cObject *obj);
234

    
235
    /**
236
     * Searches for an object by the given name. If found, unlinks and returns
237
     * the object. If the object is not in the queue, NULL pointer is returned.
238
     */
239
    virtual cObject* removeByName(const char* name);
240

    
241

    
242
    /**
243
     * Unlinks and returns the front element in the queue. If the queue
244
     * was empty, cRuntimeError is thrown.
245
     */
246
    virtual cObject *pop();
247

    
248
    /**
249
     * Empties the container. Contained objects that were owned by the
250
     * queue (see getTakeOwnership()) will be deleted.
251
     */
252
    virtual void clear();
253
    //@}
254

    
255
    /** @name Query functions. */
256
    //@{
257
    /**
258
     * Returns pointer to the object at the front of the queue.
259
     * This is the element to be returned by pop().
260
     * Returns NULL if the queue is empty.
261
     */
262
    virtual cObject *front() const;
263

    
264
    /**
265
     * Returns pointer to the last (back) element in the queue.
266
     * This is the element most recently added by insert().
267
     * Returns NULL if the queue is empty.
268
     */
269
    virtual cObject *back() const;
270

    
271
    /**
272
     * Returns the number of objects contained in the queue.
273
     */
274
    virtual int getLength() const;
275

    
276
    /**
277
     * Returns true if the queue is empty.
278
     */
279
    bool isEmpty() const {return getLength()==0;}
280

    
281
    /**
282
     * Alias for getLength().
283
     */
284
    int length() const {return getLength();}
285

    
286
    /**
287
     * Alias for isEmpty().
288
     */
289
    bool empty() const {return isEmpty();}
290

    
291
    /**
292
     * Returns the ith element in the queue, or NULL if i is out of range.
293
     * get(0) returns the front element. This method performs linear
294
     * search.
295
     */
296
    cObject *get(int i) const;
297

    
298
    /**
299
     * Returns true if the queue contains the given object.
300
     */
301
    virtual bool contains(cObject *obj) const;
302

    
303
    /**
304
     * Returns true if the queue contains the object with the given name.
305
     */
306
    virtual bool containsByName(const char* name) const;
307

    
308
    /**
309
     * Returns the object with the given name.
310
     */
311
    virtual cObject* findObjectByName(const char* name) const;
312
    //@}
313

    
314
    /** @name Ownership control flag. */
315
    //@{
316

    
317
    /**
318
     * Sets the flag which determines whether the container object should
319
     * automatically take ownership of the objects that are inserted into it.
320
     * It does not affect objects already in the queue. When an inserted
321
     * object is owned by the queue, that means it will be deleted when
322
     * the queue object is deleted or cleared, and will be duplicated when
323
     * the queue object is duplicated or copied.
324
     *
325
     * Setting the flag to false does not affect the treatment of objects
326
     * that are NOT cOwnedObject. Since they do not support the ownership
327
     * protocol, they will always be treated by the queue as owned objects.
328
     */
329
    void setTakeOwnership(bool tk) {tkownership=tk;}
330

    
331
    /**
332
     * Returns the flag which determines whether the container object
333
     * should automatically take ownership of the objects that are inserted
334
     * into it. See setTakeOwnedship() for more details.
335
     */
336
    bool getTakeOwnership() const {return tkownership;}
337
    //@}
338
};
339

    
340
NAMESPACE_END
341

    
342

    
343
#endif
344