Need help with Quash

[MasterShihoChief]

Hi everyone,

Ive been working on this Quash program for a couple days. I'm honestly a little confused due to the professor giving us this program and basically saying go and dont come to me for help. I am not expecting to be fed the answer but i learn visually, and i need to play with example code to learn how to use something. If you look at the code linked below, i finally figured out what a comparator was and how to use it to make a min heap. Now i need to figure out why i cant have these two data structures(the compiler says the template arguments are invalid) I am trying to make a min heap using a vector and a hashtable using a map. I want to insert the numbers into each and then have pointers going each way and store those as paired. For the hashtable i also need a boolean for his required "lazy deletion" style. Any help would be greatly appreciated, im really frustrated right now.

http://codepad.org/iNS2CJUF

[hamsterman]

What is the program supposed to do. Also, why doesn't Quash have it's members declared ?

[MasterShihoChief]

The program is supposed have 2 data structures. A hash table and a min heap. what im currently working on is the insert command. It is supposed to insert a given number into the hash table and the min heap and link them together using pointers in each direction. The hash table also requires a boolean to be used as a "lazy deletion" method. Honestly i am so confused right now i have no idea what to do, and what to declare. I have tried updating the Quash member function by putting the vector and map inside and a lot of scope issues went away as expected, however im so confused with the setup that i cant use it and it throws up errors about all these template arguments being corrupted, and there being no Quash object.

[hamsterman]

After you've put member declarations in the class declaration, remove names form template arguments. Inside <> only names of types can be written. pair<int, unsigned* hashPtr> becomes pair<int, unsigned*>. Also, note line 144, which does the same thing and should use the usual constructor syntax (+ the <type1, type2> before (argument1, argument2) ) or a function make_pair (which is good for often being able to deduce the types of arguments).
When you do that, post the code again. You can post it here as there isn't too much of it. Don't forget to use [code][/code] tags. Separate the files to make this easier to read.
Instead of all those pairs, you might want to use structures of your own. vector<pair<,>> is somewhat fine, but map<,pair<,pair<,>>> is quite ugly.

Now, about the actual purpose of your code, note that map is not really a hashmap. There is no hashing involved. I don't know if that is a problem. If it is not, then I guess this part shouldn't be of any trouble.
A heap might be more complicated, but wikipedia seems to have it well explained..
A thing to note is that a vector will need to reallocate itself many times, so having a pointer to a value in it is futile. I don't think the same is true for maps, but I can't say for sure. It would be better maybe to not store values but pointers to dynamically allocated memory. Though I can't say I understand what is the purpose of their having pointer to each other.. My suggestion might narrow the uses..

[MasterShihoChief]

Ok, this is what i came up with, but now im having problems with the compiler saying i cant use my variables as a constant expression.

I couldnt fit the code into the max word limit so i pasted it here: http://codepad.org/Grtki15K

I guess i should explain the program requirements, and you guys can maybe get me back on track, cuz it looks like i might be way off.

Overview

Hashing is useful if we are only interested in insert, delete, and find operations; e.g., delete(10) or insert(5) or find(100). But a hash table provides no assistance for searches that depend on the order or rank of an element in a set, e.g., find the smallest element, delete the smallest element, etc. For the latter type of operation, you have learned that priority queues are more appropriate. On the other hand priority queues do not support a general delete operation, e.g., delete(100); they only support deleting the minimum (or maximum) element.

The goals of this programming assignment are
to review your knowledge and understanding of the concepts of file I/O, formatted output, and string parsing with C++;
to give you experience in combining features of multiple data structures in order to accomplish a specific task; and
to get you acquainted with the C++ Standard Template Library (STL) - I recommend cplusplus.com and cppreference.com as solid C++ STL references ...


Description

In this programming assignment, you will develop a “compound” data structure called a Quash, which is composed of both a min-heap (priority queue) and a hash table. The Quash supports insert, delete and lookup operations using its hash component, and a deleteMin operation using its heap component. In particular, each element in a Quash will be inserted in both the heap and the hash table components. Note that to facilitate the two delete operations, you will need to include pointers in both directions between the 2 instances of the element in the heap and in the hash table.

Operations should be executed as follows:

insert(x): Insert element x in both the heap and the hash table components, and link them correctly. Your driver/program (not the operation) should return either “item x successfully inserted” or “item x already present” (no duplicates allowed), depending on the success or failure of the operation.

lookup(x): Use the hash table component to determine if x is in the Quash. Your driver/program should return either “item x found” or “item x not found” after executing this operation.

deleteMin(): Use the heap component to delete the minimum element, and use the pointer to delete the element in the hash table component. Your driver/program should report the key value of the item deleted, such as “min item x deleted,” or an error message such as “empty Quash; no minimum item,” if the Quash is empty.

delete(x): Use the hash table component to determine where x is, delete it from the hash table and use the pointer to delete it from the heap. (Note that you will need to generalize the heap operations to support this “internal,” non-root, delete operation.) Your driver/program should return either “item x successfully deleted” or “item x not found.”

print(): Prints out the hash table as well as the heap (in the array format) on two separate lines, with elements separated by a blank.


Instructions

Your executable will be called quashTest. You will design, implement, and test your implementation of a quash class that implements the Quash data structure described above. Features of your driver/program are described below. All source code should be well-documented (at the least, with your name, brief description of the problem and your implementation, etc.). Solutions with source code that is not documented will receive no credit. All solutions must be submitted by uploading to your turnin directory in the ECC Unix server by the due date and time indicated above. Late submissions will not be accepted, so be sure you upload even partial solutions to receive some partial credit.

Be sure to start working on this assignment early. It is highly recommended that you spend a couple of days fully understanding the problem, perhaps with hand-drawn mock-ups of the data (and data structures) you think you will need to solve this problem, and hand-tracing through the various options to ensure you can provide the required functionality. You may use and modify any of the code available for our class to assist you in implementing your solution. Additionally

familiarize yourself with Dr. J's Coding Standards
you are expected to use the target executable filename given in the sample runs below (Note: No .exe file extension!)
your name must be displayed by your executable each time it is run
your executable must be designed take command-line arguments and must have the following specific implementation requirements:

Assume all elements to be inserted are unsigned integers.
Use the array implementation for the min heap component of your quash class.
Use “modulo 2011” (2011 happens to be the 305th prime number) as your hash function. In general, it would be better to use an internal resize() operation, which doubles the hash table size when the tables becomes too full, and shrinks it when it becomes too empty, using appropriate load factor thresholds for“too full” and “too empty.” In this assignment, the table size will be fixed; hence, inserting more items into an already full table should be rejected.
For collision resolution, use linear probing.
Use a “lazy deletion” method by marking slots in the hash table component as deleted; you may use a boolean flag called deleted to indicate that a slot was once used but is now deleted.
The sole command-line argument to your driver is a text file that contains commands that match the operations on a Quash object. Here is a sample run:

 $ quashTest commands.txt
 quashTest, by Your_Name_Goes_Here
 Reading input file sample.txt ...

 item 10 successfully inserted
 item 50 successfully inserted
 item 76 successfully inserted
 Additional messages appear based on commands in commands.txt

 $ _

Input text files contain commands that match the operations on a Quash object. Any invalid commands should result in an appropriate error message. Here are the contents of the file commands.txt:
 insert 10
 insert 50
 insert 76
 print
 lookup 12
 insert 12
 lookup 12
 deleteMin
 delete 76
 insert 12
 deleteMin
 lookup 76
 print 

[hamsterman]

I couldnt fit the code into the max word limit

I wonder if that's in any way related to that drawing you've got there :). Not that it's a problem..

Also, when you post something that is not code, use [quote] or [output] tags to avoid silly colours and allow line wrapping ([output] doesn't wrap them though).

How much time do you have for this ?

Where did you put the Quash class ? It's a requirement, isn't it ?

In this assignment, the table size will be fixed; hence, inserting more items into an already full table should be rejected

What's this? 2011? If the size is constant, you can use a plain array for the heap. That solves the vector reallocation problem.. I also think that you'll have to implement hash table of your own. std::map is a tree, does no hashing, would make lazy deletion hard and can't possibly get full. And it would be just too easy.. Assuming that, though, I have no clue how the project would familiarise you with STL..

What you should do is separately implement a heap and a hash table. It seems that you may have enough trouble with just that, without dealing with their interaction. When you have an understanding how they work, you can start thinking about combining them.

[MasterShihoChief]

This assignment is due next friday, dont know if ill have anything to turn in by then. We only get a week and a half to work on it. Sometimes he gives extra time so it can be turned in the following monday.

I got rid of the quash class so i could just work on this and because the class wasnt working the way i was doing it.

The class tutor which the compsci dept has provided was the one who told me to use maps and vectors for this problem so a lot of help that was.

So if i understand this correctly, i dont have to have a vector for min heap and i can still use make_heap with a standard array? Doesnt it still have to reorder it when it gets heapified? I also assume i would have to keep track of the current fullness of the array to track what gets heapified and not the initial 0's i will set it to.

Since map is not a hash table, im not supposed to use a map for hashing after all? can i just use an array with 2011 slots just like the min heap array? I can initially set it to 0 and fill it up according to what bucket. I can linear probe, and for deletion, i can just set the bucket = -1 for lazy deletion correct?

Final question. I was only taught about using arrays for one thing like chars or ints. How would i even start to put pointers between data structures, unless there is a way to store more than value in the array. I guess i could create a hashtable and min heap class with multiple members. Can i insert a class with multiple elements into an array. How would i access them later, and how would i tell make_heap to use greater<int> on the number i want it to sort by if it only stores a pointer to the class element. I know i can access it using the node class but how would i go about using a comparator to do that


Thanks for the help.

[hamsterman]

If you were told to use maps and vectors then it's fine.

Yes, you can. Iterator mimics a pointer, so when you have a function which takes two iterators, you can pass it two pointers (to the first element in the array and to the memory after the last one). But if you were told, use a vector.

I guess you can (have to) add the hashing yourself. And if you were told, use a map. Though, can there be two elements with the same hash? That would be problematic.. (slightly)

Arrays can be used for any type you like. To store several values, you would write a class (/struct) containing the members you need and make an array of it.
Here's an example:

#include <algorithm>

struct Apple{
   int banana;
   double cinnamon;
};

bool less( const Apple& a, const Apple& b ){
   return a.banana < b.banana;
}

int main(){
   Apple arr[10];
   arr[5].banana = 7;
   //... set the values of elements
   std::make_heap( arr, arr+10, less );
}

Code not tested. Sorry if I got anything wrong.

[MasterShihoChief]

(main) Quashtest.cpp http://codepad.org/Lk7Rn9ge
Quash.cpp http://codepad.org/htGkc8Yu
Quash.h http://codepad.org/IkTcZtry
Hashtable.cpp http://codepad.org/VmUOVDj1
Hashtable.h http://codepad.org/Wq2bW01M
Minheap.cpp http://codepad.org/pko4TtDp
Minheap.h http://codepad.org/9MwtaGZI

Compile Errors:

jlhunter@jaguar:~/311/P3$ jlhunter@jaguar:~/311/P3$ make
-bash: jlhunter@jaguar:~/311/P3$: No such file or directory
jlhunter@jaguar:~/311/P3$ make: Warning: File `makefile' has modification time 58 s in the future
> g++ -Wall -g -c quashTest.cpp
> In file included from quashTest.cpp:11:
> quash.h:29: error: ISO C++ forbids declaration of 'heapArr' with no type
> quash.h:29: error: expected ',' or '...' before '&' token
> quash.h: In member function 'bool Quash::less(int)':
> quash.h:30: error: 'a' was not declared in this scope
> quash.h:30: error: 'b' was not declared in this scope
> quashTest.cpp: In function 'int main(int, char**)':
> quashTest.cpp:76: error: no matching function for call to 'Quash::Quash()'
> quash.h:21: note: candidates are: Quash::Quash(Minheap*, Hashtable*)
> quash.h:19: note: Quash::Quash(const Quash&)
> quashTest.cpp:81: error: expected ',' or ';' before 'if'
> quashTest.cpp:74: warning: unused variable 'p'
> quashTest.cpp:75: warning: unused variable 'q'
> make: *** [quashTest.o] Error 1
> jlhunter@jaguar:~/311/P3$
>
Makefile:

# makefile for the 112 p3 assignment
# the -g option is for the debugger
# the -Wall is for showing all warnings

quashTest: quashTest.o quash.o
	g++ -Wall -g -o quashTest quashTest.o quash.o

quashTest.o: quashTest.cpp quash.h
	g++ -Wall -g -c quashTest.cpp

quash.o: quash.cpp quash.h Minheap.h Hashtable.h
	g++ -Wall -g -c quash.cpp
	
Minheap.o: Minheap.cpp Minheap.h
	g++ -Wall -g -c Minheap.cpp

Hashtable.o: Hashtable.cpp Hashtable.h
	g++ -Wall -g -c Hashtable.cpp
# "$ make clean" will delete all the files generated by this Makefile
clean:
	rm -f quashTest quashTest.o quash.o Minheap.o Hashtable.o

I ended up changing to the array implementation for both since there is nothing in the directions that specifically tells me i have to use vectors and maps. To be honest they were becoming too confusing and your above example made it look extremely easy. I think i have put a few things in the wrong place and maybe didnt do the quash class correctly. I havent done much programming with secondary classes, so im guessing i did it wrong cuz it says quash doesnt exist. Again i appreciate the help you have given me ^^.

[hamsterman]

Your errors:
in quash.h, in declaration of less(), your arguments have no types. They should be const Minheap& a and b. heapArr is not a type. It is only an argument of the constructor. Note that it is not a member. If you want it to be a member, declare it in the class.
Also, note that you will not be able to pass this function to make_heap. It is a member function and requires an object to be called. You should declare it as static bool less( const Minheap& a, const Minheap& b )

in quashTest.cpp, line Quash myQuash; is supposed to call a constructor of Quash, however there is only one constructor (two with copy constructor) and it takes two arguments. You have to pass them to the constructor. Though the arguments aren't needed here, so I suggest that you change the constructor.

in quashTest.cpp, line int size=0 simply doesn't have a ;.


Despite what I might have said, you shouldn't do this with an array. The task did say that it is supposed to get you acquainted with STL ... And it really won't be any easier..

Since you seem to have trouble seeing how to combine classes, here's an example (assume necessary includes and header guards):

//Minheap.h
class Minheap{
   std::vector<unsigned> heap;
   
public:
   bool insert(unsigned u);
   bool deleteMin();
   void print();
};

//Hashtable.h
struct TableEntry{
   unsigned value;
   bool deleted;

   TableEntry();
   TableEntry( unsigned val );
};

class Hashtable{
   std::map<unsigned, TableEntry> table;

public:
   bool insert(unsigned u);
   bool lookup(unsigned u);
   bool delete(unsigned u);
   void print();
};

//Quash.h
class Quash{
   Minheap heap;
   Hashtable table;

public:
   bool insert(unsigned u);
   bool lookup(unsigned u);
   bool deleteMin();
   bool delete(unsigned u);
   void print();
};

From methods of Quash, only call methods of Minheap and Hashtable. It might be inevitable to do something else, but try to keep main functionality inside those two.
Note that these headers are not designed for interaction between Hashtable and Minheap. First do them separately. Combining is a bit harder.

[MasterShihoChief]

ERROR: http://codepad.org/N2SQnNWt <<< i had a problem with a make file and i fixed it so some weird bugs went away

(main) Quashtest.cpp http://codepad.org/dvPdYL9C

Quash.cpp http://codepad.org/5eJHNKF5

Quash.h http://codepad.org/uuJG0E3y

Hashtable.cpp http://codepad.org/GSjMyZVJ

Hashtable.h http://codepad.org/ZAkKiXT4

Minheap.cpp http://codepad.org/UyNKZlsS

Minheap.h http://codepad.org/6ZcouN5C


Ok so ya i figured out i derped hard about the constructors and objects and what not. That is all fixed. I also fixed the makefile which didnt have proper dependencies causing out of scope errors. Now there are only 3 errors left for the insert command, and if i comment them out it compiles and i get debug output.

1. I have a problem insert into the vector and map, dont know if its just a syntax problem with the vector being a vector of subclass minheap or the map being a map of hashtable class.

2. of course i tried playing around with the pointers but unsigned int and unsigned int * dont work when i try to get a pointer to the other data structure.

3. the boolean comparator for making the min heap called less errors.

All errors are in the text file 1 for each problem i isolated.

Thanks again for all the help, i really appreciate it.

[hamsterman]

About the errors.
The first one is because Quash::less takes const reference arguments. This means that the arguments will not be modified, however the compiler doesn't know whether Minheap::get_Number() will modify anything or not, so it complains.
One solution is to tell that to the compiler by declaring get_Number() as a const method:
int get_Number() const; Note that you need to put this 'const' in the implementation too.
Another solution is to simply pass the two Minheaps by value.

The second one seems to be because you passed heap.begin(), which is an iterator, to a constructor which asks for a pointer. While iterators behave like pointers, they are not the same. You could say that every pointer is an iterator, but not every iterator is a pointer. This could be &(*heap.begin()) or &heap.front() or &heap[0]

The third one I can't make out, since that paste has the ends of lines cut off, at least for me.. I have a feeling that it is a consequence of the second one.

About the code.
You have your classes wrong. Your heap is a vector. So why did you call the thing you put in that vector a heap as well ? It would make sense if you renamed your Minheap as MinheapElement or something like that. Now that I look at it, I don't see a requirement that you write wrapper classes for the heap and the hash table, even though it would look cleaner, so if you feel more comfortable with dealing with the vector and the map in Quash then it's fine.

_{edit: I should probably note that I won't be able to help any more for a while. If you have more things to ask, you might want to start a new thread, as this one isn't very likely to get new posters..}

[MasterShihoChief]

i did post a new one here, but havent got a single reply :(
http://www.cplusplus.com/forum/general/47722/