This is all about priority queue problems with using different techniques for storing the data in a queue, the priority queue could be similar to a queue in a hospital ER ward where the people with the biggest of problems are treated first.
So the CS106B course does two versions which use a vector and a single linked list to do and then we have to implement a chunk list and and a heap implementation, here I am going to do a chunk list and the next post will be the heap version.
So to explain what a chunk list is instead of a having just a single value within a linked list we will have a chunk of values within a block of memory and then once that chunk is filled to then create a new chunk and link to that one. So it is very similar to a linked list, but the main parts of how to store data within the chunk array (without using a vector but a array of data that we have to manage) and how to split the chunks once they reach there maximum storage capacity. It is explained in the PDF assignment attached in the zip file.
Anyway, here is the interface/header file of the priority queue that we have to implement so that if the program will use any of the different versions to store data linked list, chunk, heap, vector.
class PQueue { public: PQueue(); ~PQueue(); int size(); bool isEmpty(); void add(int elem); int extractMin(); private: // implementation dependent member variables and helper methods }; |
To start with, I need to find out where the chunk to insert the value into, this would accomplished by searching the present chunks and if the inserting value is lower than highest value in that chunk then this is the chunk to insert into since they are already in sorted order then the searching process will always find the correct place to insert into. So here is how I find that highest chunk to insert into, it uses recursive technique to find the chunk
// find the highest chunk of space where newElem could be placed into the best chunk PQueue::chunkSpace* PQueue::findHighestChunk(chunkSpace *&space, int newElem) { if (space == NULL) return NULL; // found the previous chunk to insert into if (space->values[space->lastBlock-1] > newElem && space->lastBlock > 0) return space; else { chunkSpace *retPlace = findHighestChunk(space->nextBlock, newElem); if (retPlace == NULL) return space; else return retPlace; } } |
could have used a for loop to search thought like
for (chunkSpace *head = chunks, *pre = chunks; head != NULL; head = head->nextBlock) { if (head->values[head->lastBlock-1] > newElem) break; pre = head; } |
but then you would need to check for NULLs etc so just thought that I would use recursive since it is just a nice thing :). once found the highest chunk to insert into then we can insert a value if there is space, if not then split the chunk into two and then insert the new value into the correct chunk
if (space->lastBlock == MaxElemsPerBlock) { // split into two, divide the blocks in half and rebuild the structures int insertI=0; int div = MaxElemsPerBlock/2; chunkSpace *newSpace = new chunkSpace(); // rebuild links newSpace->nextBlock = space->nextBlock; newSpace->values = new int[MaxElemsPerBlock]; space->nextBlock = newSpace; // copy over values space->lastBlock -=div; for (int i =div; i < MaxElemsPerBlock; i++) newSpace->values[insertI++] = space->values[i]; newSpace->lastBlock = div; // find out where to insert, new space or previous space if (newSpace->values[0] < newElem) space = newSpace; } |
which the code above will split the present chunk into 2 and then rebuild the links and place the data from the first one (half way forwards) into the second chunk, of course we need to insert the new value into the correct chunk which is why there is a test at the end to see if the new value is greater than the second chunks first value.
Here the full source of the pqchunk.cpp which does all of the pqueue for chunks and also some have included below the bits that I added into the pqueue.h file.
#include "pqueue.h" #include "genlib.h" #include <iostream> /* chunk memory implementation */ // constant max allocation of the const int MaxElemsPerBlock = 4; PQueue::PQueue() { // setup the first instance of chunks chunks = new chunkSpace(); chunks->nextBlock = NULL; chunks->lastBlock = 0; chunks->values = new int[MaxElemsPerBlock]; theSize = 0; } PQueue::~PQueue() { // deallocate the memory of the chunks deleteChunks(chunks); } // delete the chunks and recursive call itself to loop down the list void PQueue::deleteChunks(chunkSpace *space) { if (space == NULL) return; else { deleteChunks(space->nextBlock); deleteBlock(space); } } void PQueue::deleteBlock(chunkSpace *space) { delete[] space->values; delete space; } bool PQueue::isEmpty() { if (theSize == 0) return true; else return false; } int PQueue::size() { return theSize; } void PQueue::add(int newElem) { chunkSpace *space = findHighestChunk(chunks, newElem); // split the block if at the maxiumum of elements allowed once the insertation has taken place. if (space->lastBlock == MaxElemsPerBlock) { // split into two, divide the blocks in half and rebuild the structures int insertI=0; int div = MaxElemsPerBlock/2; chunkSpace *newSpace = new chunkSpace(); // rebuild links newSpace->nextBlock = space->nextBlock; newSpace->values = new int[MaxElemsPerBlock]; space->nextBlock = newSpace; // copy over values space->lastBlock -=div; for (int i =div; i < MaxElemsPerBlock; i++) newSpace->values[insertI++] = space->values[i]; newSpace->lastBlock = div; // find out where to insert, new space or previous space if (newSpace->values[0] < newElem) space = newSpace; } insertIntoBlock(space, newElem, space->lastBlock); space->lastBlock++; theSize++; } void PQueue::insertIntoBlock(chunkSpace *space, int newElem, int blockIndex) { // base case of nothing already if (blockIndex == 0) { space->values[0] = newElem; return; } if (space->values[blockIndex-1] <= newElem) { space->values[blockIndex] = newElem; return; } if (space->values[blockIndex-1] > newElem) { space->values[blockIndex] = space->values[blockIndex-1]; return insertIntoBlock(space, newElem, (blockIndex-1)); } } void PQueue::printOutBlocks(chunkSpace *block) { if (block == NULL) return; else { cout << "print out block " << endl; for (int i =0; i < block->lastBlock; i++) cout << "i " << i << " value =" << block->values[i] << endl; printOutBlocks(block->nextBlock); } } // find the highest chunk of space where newElem could be placed into the best chunk PQueue::chunkSpace* PQueue::findHighestChunk(chunkSpace *&space, int newElem) { if (space == NULL) return NULL; // found the previous chunk to insert into if (space->values[space->lastBlock-1] > newElem && space->lastBlock > 0) return space; else { chunkSpace *retPlace = findHighestChunk(space->nextBlock, newElem); if (retPlace == NULL) return space; else return retPlace; } } int PQueue::extractMin() { if (isEmpty()) Error("no more values left"); else { int returnValue = chunks->values[0]; theSize--; for (int i =1; i < chunks->lastBlock; i++) chunks->values[i-1] = chunks->values[i]; chunks->lastBlock--; if (chunks->lastBlock == 0) { // if chunks->nextBlock != NULL then remove this block and repoint the chunks to the nextBlock if (chunks->nextBlock != NULL) { chunkSpace *old = chunks; chunks = chunks->nextBlock; deleteBlock(old); } } return returnValue; } return 0; } |
and here is the bits that I added to the private
struct chunkSpace { int lastBlock; int *values; chunkSpace *nextBlock; }; chunkSpace *chunks; int theSize; void deleteChunks(chunkSpace *space); void deleteBlock(chunkSpace *space); chunkSpace *findHighestChunk(chunkSpace *&space, int newElem); void printOutBlocks(chunkSpace *block); void insertIntoBlock(chunkSpace *space, int newElem, int blockIndex); |
which hides my local variables as such and methods.