Debian Codegraph @

protolib/examples/queueExample.cpp

raw
1 // This example illustrates some use of the ProtoQueue classes
2 // that enable an "Item" to a member of multiple queues
3 // (lists, trees, etc) simultaneously _and_ be aware which
4 // queues in which it is included. The ProtoQueue::Item
5 // also gracefully removes itself from all the queues it
6 // is included when it is deleted. The item can be indexed
7 // or sorted in different ways in each queue as well.
8 // The queue classes can be subclassed and customized to
9 // provide different sorting behavior on different
10 // item attributes.
11
12 // We use a "ProductRecord" example class that has some
13 // different attributes (name, model number, cost) to
14 // illustrate the use of the ProtoQueue classes.
15
16
17 #include "protoQueue.h"
18
19 #include <stdlib.h> // for rand()
20 #include <arpa/inet.h> // for htonl()
21
22
23 class ProductRecord : public ProtoQueue::Item
24 {
25 public:
26 ProductRecord(const char* theName,
27 unsigned int theModel,
28 double theCost);
29
30 const char* GetName() const
31 {return name;}
32 unsigned int GetModel() const
33 {return model;}
34 double GetCost() const
35 {return cost;}
36
37 enum {PRODUCT_NAME_MAX = 31};
38
39 // These are used by our various queues to
40 // access the attributes used for indexing
41 const unsigned int* GetModelPtr() const
42 {return &model;}
43 const double* GetCostPtr() const
44 {return &cost;}
45
46 private:
47 char name[PRODUCT_NAME_MAX+1];
48 unsigned int model;
49 double cost;
50
51 }; // end class ProductRecord
52
53 ProductRecord::ProductRecord(const char* theName,
54 unsigned int theModel,
55 double theCost)
56 : model(theModel), cost(theCost)
57 {
58 name[PRODUCT_NAME_MAX] = '\0';
59 strncpy(name, theName, PRODUCT_NAME_MAX);
60 }
61
62 // I) The first here is a simple linked list of the products ...
63 class ProductList : public ProtoSimpleQueueTemplate<ProductRecord> {};
64
65 // II) The second is a queue indexed by product "name"
66 // NOTES:
67 // 1) A "ProtoIndexedQueue" derivative can only contain values
68 // with unique keys/indexes (product "name" in this case)
69 //
70 // 2) The override of the "GetKey()" and "GetKeysize()" determine how
71 // items in the "ProtoIndexedQueue" are indexed. (Here we set
72 // the queue up to index by Product "name").
73 //
74 // 3) Note the "keysize" is in units of bits (_not_ bytes)
75 //
76 class ProductNameQueue : public ProtoIndexedQueueTemplate<ProductRecord>
77 {
78 public:
79 ProductNameQueue(bool usePool = false)
80 : ProtoIndexedQueueTemplate<ProductRecord>(usePool) {}
81
82 const char* GetKey(const Item& item) const
83 {return static_cast<const ProductRecord&>(item).GetName();}
84 // returns length of name in bits
85 unsigned int GetKeysize(const Item& item) const
86 {return (8*strlen(static_cast<const ProductRecord&>(item).GetName()));}
87
88 }; // end class ProductNameQueue
89
90 // III) The third is a queue sorted by product "model" number
91 // NOTES:
92 // 1) A "sorted queue" can have multiple entries with the same key
93 class ProductModelQueue : public ProtoSortedQueueTemplate<ProductRecord>
94 {
95 public:
96 ProductModelQueue(bool usePool = false)
97 : ProtoSortedQueueTemplate<ProductRecord>(usePool) {}
98
99 const char* GetKey(const Item& item) const
100 {return ((const char*)static_cast<const ProductRecord&>(item).GetModelPtr());}
101 // returns length of name in bits
102 unsigned int GetKeysize(const Item& item) const
103 {return (sizeof(unsigned int) << 3);}
104 // For sorting "unsigned int", the following sorting criteria are used
105 // native machine endian, useSignBit = false, useComplement2 = true
106 // (the latter two are default for ProtoSortedQueue, so we just override one
107 ProtoTree::Endian GetEndian() const
108 {return ProtoTree::GetNativeEndian();}
109
110 }; // end class ProductModelQueue
111
112 // IV) The fourth is a queue sorted by product "cost"
113 // NOTES
114 // 1) Here we sort by "cost", a "double" floating point value, and we
115 // set up the sorting accordingly.
116 class ProductCostQueue : public ProtoSortedQueueTemplate<ProductRecord>
117 {
118 public:
119 ProductCostQueue(bool usePool = false)
120 : ProtoSortedQueueTemplate<ProductRecord>(usePool) {}
121
122 const char* GetKey(const Item& item) const
123 {return ((const char*)static_cast<const ProductRecord&>(item).GetCostPtr());}
124 // returns length of name in bits
125 unsigned int GetKeysize(const Item& item) const
126 {return (sizeof(double) << 3);}
127 // For sorting "double", the following sorting criteria are used
128 // native machine endian, useSignBit = true, useComplement2 = false
129 ProtoTree::Endian GetEndian() const
130 {return ProtoTree::GetNativeEndian();}
131 bool GetUseSignBit() const
132 {return true;}
133 bool GetUseComplement2() const
134 {return false;}
135
136 }; // end class ProductCostQueue
137
138
139
140 class TestItem : public ProtoTree::Item
141 {
142 public:
143 TestItem(UINT32 theValue)
144 : value(htonl(theValue)) {}
145 ~TestItem() {}
146
147 UINT32 GetValue() const
148 {return ntohl(value);}
149
150 const char* GetKey() const
151 {return ((const char*)&value);}
152 unsigned int GetKeysize() const
153 {return (sizeof(UINT32) << 3);}
154
155 private:
156 UINT32 value;
157 }; // end class TestItem
158
159 class TestTree : public ProtoTreeTemplate<TestItem> {};
160
161 int main(int argc, char* argv[])
162 {
163
164 //struct timeval currentTime;
165 //ProtoSystemTime(currentTime);
166 //srand(currentTime.tv_usec);
167
168
169 TestTree testTree;
170
171 int i = 0;
172 for (i = i; i <= 20; i++)
173 {
174 TestItem* item = new TestItem((UINT32)rand());
175 //TestItem* item = new TestItem((UINT32)i);
176 if (!testTree.Insert(*item))
177 {
178 delete item;
179 i--;
180 }
181 }
182
183 TestItem* savedItem = NULL;
184 TestItem* item;
185 TestItem* pitem;
186 TestTree::Iterator it(testTree, true);
187
188 for (i = 1; i <= 10; i++)
189 {
190 pitem = it.PeekPrevItem();
191 item = it.GetPrevItem();
192 TRACE("item %d value %lu (pitem value %lu)\n", i, item->GetValue(), pitem->GetValue());
193 }
194 savedItem = item;
195 for (i = 9; i >= 5; i--)
196 {
197 pitem = it.PeekNextItem();
198 item = it.GetNextItem();
199 TRACE("item %d value %lu (pitem value %lu)\n", i, item->GetValue(), pitem->GetValue());
200 }
201 for (i = 6; i <= 20; i++)
202 {
203 pitem = it.PeekPrevItem();
204 item = it.GetPrevItem();
205 TRACE("item %d value %lu (pitem value %lu)\n", i, item->GetValue(), pitem->GetValue());
206 }
207
208
209 TRACE("setting cursor to %lu\n", savedItem->GetValue());
210 it.SetCursor(*savedItem);
211
212 TestItem* prev = static_cast<TestItem*>(it.prev);
213 TestItem* next = static_cast<TestItem*>(it.next);
214 TestItem* curr = static_cast<TestItem*>(it.curr_hop);
215 TRACE("iterator prev:%lu next:%lu curr:%lu\n",
216 prev ? prev->GetValue() : 0,
217 next ? next->GetValue() : 0,
218 curr ? curr->GetValue() : 0);
219
220
221 TRACE("removing item %lu ...\n", savedItem->GetValue());
222 testTree.Remove(*savedItem);
223
224 prev = static_cast<TestItem*>(it.prev);
225 next = static_cast<TestItem*>(it.next);
226 curr = static_cast<TestItem*>(it.curr_hop);
227 TRACE("iterator prev:%lu next:%lu curr:%lu\n",
228 prev ? prev->GetValue() : 0,
229 next ? next->GetValue() : 0,
230 curr ? curr->GetValue() : 0);
231
232
233 /*
234 it.GetNextItem();
235 ProtoTree::Item* snext = it.prev;
236 TRACE("\ngot one item\n");
237 prev = static_cast<TestItem*>(it.prev);
238 next = static_cast<TestItem*>(it.next);
239 curr = static_cast<TestItem*>(it.curr_hop);
240 TRACE("iterator prev:%lu next:%lu curr:%lu\n",
241 prev ? prev->GetValue() : 0,
242 next ? next->GetValue() : 0,
243 curr ? curr->GetValue() : 0);
244
245
246 it.GetNextItem();
247 TRACE("\ngot another item\n");
248 prev = static_cast<TestItem*>(it.prev);
249 next = static_cast<TestItem*>(it.next);
250 curr = static_cast<TestItem*>(it.curr_hop);
251 TRACE("iterator prev:%lu next:%lu curr:%lu\n",
252 prev ? prev->GetValue() : 0,
253 next ? next->GetValue() : 0,
254 curr ? curr->GetValue() : 0);
255
256 //
257 //it.prev = sprev;
258 //it.next = snext;
259 //it.reversed = true;
260 //it.GetPrevItem();
261 //it.reversed = true;
262 it.GetPrevItem();
263
264 //item = it.GetNextItem();
265
266 //TRACE("next item = %lu\n", item->GetValue());
267 TRACE("\nready to go ...\n");
268 prev = static_cast<TestItem*>(it.prev);
269 next = static_cast<TestItem*>(it.next);
270 curr = static_cast<TestItem*>(it.curr_hop);
271 TRACE("iterator prev:%lu next:%lu curr:%lu\n",
272 prev ? prev->GetValue() : 0,
273 next ? next->GetValue() : 0,
274 curr ? curr->GetValue() : 0);
275 */
276 for (i = 1; i <= 20; i++)
277 {
278 pitem = it.PeekPrevItem();
279 item = it.GetPrevItem();
280 if ((NULL == pitem) || (NULL == item)) break;
281 TRACE("item %d value %lu (pitem value %lu)\n", i, item->GetValue(), pitem->GetValue());
282 }
283 TRACE("\n");
284
285 i = 0;
286 TestTree::SimpleIterator sit(testTree);
287 while (NULL != (item = sit.GetNextItem()))
288 {
289 i++;
290 //TRACE("stem %d value %lu\n", i, item->GetValue());
291 }
292
293
294 //return 0;
295
296
297 // Instantiate our various queues
298 ProductList productList;
299 ProductNameQueue nameList;
300 ProductModelQueue modelList;
301 ProductCostQueue costList;
302
303 TRACE("ProtoList::Item size = %d bytes\n", sizeof(ProtoList::Item));
304 TRACE("ProtoTree::Item size = %d bytes\n", sizeof(ProtoTree::Item));
305 TRACE("ProductList container size = %d bytes\n", sizeof(ProductList::Container));
306 TRACE("ProductNameQueue container size = %d bytes\n", sizeof(ProductNameQueue::Container));
307 TRACE("ProductCostQueue container size = %d bytes\n", sizeof(ProductCostQueue::Container));
308
309 // Randomly generate some products
310 for (int i = 0; i < 10 ; i++)
311 {
312 char name[9];
313 for (int j = 0; j < 8; j++)
314 name[j] = (rand() % 26) + 'a';
315 name[8] = '\0';
316 unsigned int model = (unsigned int)rand();
317 double cost = 100.0 * ((double)rand()/(double) RAND_MAX);
318
319 TRACE("creating product name:\"%s\" model:%u cost:%lf\n", name, model, cost);
320
321 ProductRecord* product = new ProductRecord(name, model, cost);
322 productList.Append(*product);
323 nameList.Insert(*product);
324 modelList.Insert(*product);
325 ProductModelQueue::Iterator moderator(modelList);
326 costList.Insert(*product);
327 }
328
329 ProductRecord* product;
330
331 // Test iteration manipulation stuff
332 ProductList::Iterator iterator(productList);
333 product = productList.RemoveHead();
334 if (NULL != product)
335 TRACE("Removed head name:\"%s\" model:%u cost:%lf\n",
336 product->GetName(), product->GetModel(), product->GetCost());
337 while (NULL != (product = iterator.GetNextItem()))
338 {
339 TRACE(" name:\"%s\" model:%u cost:%lf\n",
340 product->GetName(), product->GetModel(), product->GetCost());
341 }
342 product = productList.RemoveTail();
343 if (NULL != product)
344 TRACE("Removed tail name:\"%s\" model:%u cost:%lf\n",
345 product->GetName(), product->GetModel(), product->GetCost());
346 while (NULL != (product = iterator.GetPrevItem()))
347 {
348 TRACE(" name:\"%s\" model:%u cost:%lf\n",
349 product->GetName(), product->GetModel(), product->GetCost());
350 }
351 //while (NULL != (product = iterator.GetNextItem()))
352 // delete product;
353
354 //return 0;
355
356 TRACE("\nProduct List Iteration:\n");
357 ProductList::Iterator listerator(productList);
358 while (NULL != (product = listerator.GetNextItem()))
359 {
360 TRACE(" name:\"%s\" model:%u cost:%lf\n",
361 product->GetName(), product->GetModel(), product->GetCost());
362 }
363
364 //nameList.Destroy();
365
366 TRACE("\nProduct Name Iteration:\n");
367 ProductNameQueue::Iterator namerator(nameList);
368 while (NULL != (product = namerator.GetNextItem()))
369 {
370 TRACE(" name:\"%s\" model:%u cost:%lf\n",
371 product->GetName(), product->GetModel(), product->GetCost());
372 }
373
374 TRACE("\nProduct Model Iteration:\n");
375 ProductModelQueue::Iterator moderator(modelList);
376 while (NULL != (product = moderator.GetNextItem()))
377 {
378 TRACE(" name:\"%s\" model:%u cost:%lf\n",
379 product->GetName(), product->GetModel(), product->GetCost());
380 }
381
382 TRACE("\nProduct Cost Iteration:\n");
383 ProductCostQueue::Iterator costerator(costList);
384 while (NULL != (product = costerator.GetNextItem()))
385 {
386 TRACE(" name:\"%s\" model:%u cost:%lf\n",
387 product->GetName(), product->GetModel(), product->GetCost());
388 }
389
390 } // end main()