| 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() |