bucketedqueue.cpp
Go to the documentation of this file.
00001 #include "bucketedqueue.h"
00002 
00003 #include "limits.h"
00004 #include <stdio.h>
00005 #include <stdlib.h>
00006 
00007 std::vector<int> BucketPrioQueue::sqrIndices;
00008 int BucketPrioQueue::numBuckets;
00009 
00010 
00011 BucketPrioQueue::BucketPrioQueue() {
00012   // make sure the index array is created
00013   if (sqrIndices.size()==0) initSqrIndices();
00014   nextBucket = INT_MAX;
00015     
00016   // now create the buckets
00017   //    buckets = std::vector<MyQueue2<INTPOINT> >(numBuckets);
00018   buckets = std::vector<std::queue<INTPOINT> >(numBuckets);
00019 
00020   // reset element counter 
00021   count = 0;
00022 }
00023 
00024 bool BucketPrioQueue::empty() {
00025   return (count==0);
00026 }
00027 
00028 
00029 void BucketPrioQueue::push(int prio, INTPOINT t) {
00030   if (prio>=(int)sqrIndices.size()) {
00031     fprintf(stderr, "error: priority %d is not a valid squared distance x*x+y*y, or x>MAXDIST or y>MAXDIST.\n", prio);
00032     exit(-1);
00033   }
00034   int id = sqrIndices[prio];
00035   if (id<0) {
00036     fprintf(stderr, "error: priority %d is not a valid squared distance x*x+y*y, or x>MAXDIST or y>MAXDIST.\n", prio);
00037     exit(-1);
00038   }
00039   buckets[id].push(t);
00040   //    printf("pushing %d with prio %d into %d. Next: %d\n", t.x, prio, id, nextBucket);
00041   if (id<nextBucket) nextBucket = id;
00042   //    printf("push new next is %d\n", nextBucket);
00043   count++;
00044 }
00045 
00046 INTPOINT BucketPrioQueue::pop() {
00047   int i;
00048   assert(count>0);
00049   //    printf("next: %d\n", nextBucket);
00050   for (i = nextBucket; i<(int)buckets.size(); i++) {
00051     if (!buckets[i].empty()) break;     
00052   }
00053   assert(i<(int)buckets.size());
00054   nextBucket = i;
00055   //    printf("pop new next %d\n", nextBucket);
00056   count--;
00057   INTPOINT p = buckets[i].front();
00058   buckets[i].pop();
00059   return p;
00060 }
00061 
00062 
00063 void BucketPrioQueue::initSqrIndices() {
00064   //    std::cout << "BUCKETQUEUE Starting to build the index array...\n";
00065   //  std::set<int> sqrNumbers;
00066 
00067   sqrIndices = std::vector<int>(2*MAXDIST*MAXDIST+1, -1);
00068 
00069   int count=0;
00070   for (int x=0; x<=MAXDIST; x++) {
00071     for (int y=0; y<=x; y++) {
00072       int sqr = x*x+y*y;
00073       sqrIndices[sqr] = count++;
00074     }
00075   }
00076   numBuckets = count;
00077   //    std::cout << "BUCKETQUEUE Done with building the index arrays.\n";
00078 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines


dynamicvoronoi
Author(s): Boris Lau, Christoph Sprunk, Wolfram Burgard
autogenerated on Wed Dec 26 2012 16:35:02