briand@infmx.UUCP (brian donat) (06/01/90)
Hello again, and welcome back to Beginner's Corner....
where an absolute novice beginner at C++ programming (me),
displays his meager attempts at the language for your purusal
and criticism, thereby hoping to wring some greater insight
out of what's gotta be a new and exciting way to build software
tools.
This week, your host (me), has expanded his previous code, to
create a hash-table class.
Two unique problems presented themselves beyond the simple
implementation of methods for the hash-table class.
First, constructors of the form X(const X&) were explored;
these, it was hoped, would allow assignments of the form:
Objtype NewObj = OldObj
such that automatic memberwise initialization is
defeated in those cases where pointers are part of
the class definition. A very nasty C++ shortcoming
was found here when dealing with a pointer to an
array of type Obj.
Secondly, a method was explored for pulling nodes (intact)
out of one list, and sticking them in another, without
having to copy them.
If you figure you know already what I'm talking about here,
don't just punch out, at least read far enough to see what
my beginner questions and doubts are. Share your wisdom on
these matters if you can.
If you saved my previous code, add-in or edit-in the following
changes to upgrade it to reflect the current discussion:
------------------------------ CUT HERE ----------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// vlist.h Version 3.00 \\
// A linked-list object: May 30, 1990, Brian L. Donat \\
// \\
... [ everything stays the same here up to here ...]
////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\
// VLIST is the actual doubly linked list class
//
class VLIST {
int listsize;
_VLIST_NODE *head, *tail;
_VLIST_NODE *cnode; // current _VLIST_NODE or copy _VLIST_NODE.
public:
VLIST();
// add in the X(const X&) constructor.
VLIST(const VLIST&);
~VLIST();
....
// Redefine these member functions with default initializations
// as shown here.
virtual void insert(ELEMENT E = 0, _VLIST_NODE *newptr = 0);
virtual void add(ELEMENT E = 0, _VLIST_NODE *newptr = 0) {
cnode = tail; insert(E, newptr);
}
virtual _VLIST_NODE *remove(int mode = 0);
....
};
------------------------------ CUT HERE ----------------------------------
As you can see, besides providing an explicit X(const X&)
constructor for VLIST,
insert() has been altered so that it can except either
an ELEMENT or a _VLIST_NODE as input. This is
in turn propagated to add().
remove() has been altered to that it can either delete
the current node or optionally, extract it.
Of course, once you pull a node out, you can always put
it back, but in the meantime, can remember it's address
external to the list, and in this way, maintain more
(as one person said) bookmarks on the list.
This should at least suggest a better way of obtaining such
bookmarks, since removing and re-inserting isn't the
most efficient way of doing that sort of thing.
Note that I nulled the pointers on the node if it's extracted.
Otherwise, it might still point, dangerously, into the list.
Here're the changes to vlist.c. The other files for stacks,
queues and lists remain unaltered.
------------------------------ CUT HERE ----------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// vlist.c Version 3.00 \\
// VLIST class member functions: May 30, 1990, Brian L. Donat \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#include <stdlib.h>
#include "vlist.h"
#define FALSE 0
#define TRUE 1
int listError = FALSE;
... [ No changes till here ]
// X(const X&) to duplicate a list.
VLIST::VLIST(const VLIST &cList) : listsize(cList.listsize),
head(new _VLIST_NODE),
tail(new _VLIST_NODE),
cnode(head) {
// Build an empty list to start.
if(!head || !tail) abort(); // No Memory?!
head->previous = tail->next = 0;
head->next = tail; tail->previous = head;
// Add each node from cList.
int i = listsize; listsize = 0;
for(_VLIST_NODE *nptr = cList.head->next; i > 0; i--, nptr = nptr->next) {
add(nptr->data);
}
}
VLIST::~VLIST() { ...
// The above kinda looks like VLIST::VLIST(), but look again!
// In order to copy node per node, one VLIST object to assign
// it to another, completely duplicating it, not just sharing
// a pointer, we have to
//
// 1. Get the size of the former.
// 2. Start out the new VLIST object.
// 3. Sequentially duplicate each node in the former.
//
// When we're all done, we can do the following:
//
// VLIST newOBJ = oldOBJ;
//
// and get a new object with identical list nodes as the first.
// Changes in one, will not be reflected in the other.
//
.... [ no more changes til ...]
// Now here, we can insert either a new ELEMENT or a
// new _VLIST_NODE as follows:
//
// _VLIST_NODE *vp = intList.remove(1);
// .....
// intList.insert(0, vp);
//
// My only headache here, is that I must use syntax
// which includes both the ELEMENT and the _VLIST_NODE
// when inserting a _VLIST_NODE. I can't just do
// intList.insert(vp);
// not without rewriting a completely new overloaded
// version of insert().
//
// Any body know of a way around this?
void VLIST::insert(ELEMENT E, _VLIST_NODE *newptr) {
// If at the head of an empty list, fake an add().
_VLIST_NODE *pptr = cnode->previous;
if(!listsize && !cnode->previous) { cnode = tail; pptr = head; }
// build new _VLIST_NODE
if((int)(void *)newptr != 0) ;
else { newptr = new _VLIST_NODE;
newptr->data = E;
}
newptr->next = cnode;
newptr->previous = cnode->previous;
// Update Adjacent Nodes
pptr->next = newptr;
cnode->previous = newptr;
cnode = newptr;
listsize++;
}
_VLIST_NODE *VLIST::remove(int mode) { listError = FALSE;
_VLIST_NODE *rptr = 0;
if(!listsize) listError = TRUE;
else if(!cnode->previous) listError = TRUE;
else if(!cnode->next) listError = TRUE;
else { _VLIST_NODE *pptr = cnode->previous;
_VLIST_NODE *nptr = cnode->next;
// let the previous and next _VLIST_NODEs reference each other.
pptr->next = cnode->next;
nptr->previous = cnode->previous;
// remove or take the current node.
if(mode) { rptr = cnode; rptr->next = rptr->previous = 0; }
else delete cnode;
// If the next pointer is not tail, make it current,
// else make the previous pointer the current _VLIST_NODE.
cnode = (nptr->next) ? nptr : pptr;
listsize--;
}
return rptr;
}
... [ no more changes till end of vlist.c]
ELEMENT VLIST::getval(void) const { listError = FALSE;
if(!cnode->previous || !cnode->next) listError = TRUE;
return cnode->data;
}
// end
------------------------------ CUT HERE ----------------------------------
Here's the new hash table class.
It features a function to deliver a prime number >= to the desired
table size, because hash tables work best when their size == prime.
There is also a function to generate a hashvalue which more or less
gives a fairly good distribution over the table for both random and
ordered insertion sequences.
The particularly nasty part of this object is X(const X&). htable
starts out a pointer, but is used as representing the table itself
as an array. You'll find, if you experiment a bit with this,
that you can't use X(X&). You must use X(const X&). And ...
You can't change the index of the array inside of X(const X&)
because X is qualified as const. This is apparently the case
with all array types declared 'const'.
Therefore when you say
HASH newhash = oldhash;
You never get an exact copy. Only a new table with at best,
the same size.
Intuitively, you find yourself thinking that changing the array
index has nothing to do with disturbing the array contents. But
remember, htable is a pointer. 'It' must remain constant.
------------------------------ CUT HERE ----------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// hash.h Version 1.00 \\
// HASH class derived from VLIST: May 29, 1990, Brian L. Donat \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#define MAXHASH 20
#define hashError listError
extern int listError;
extern class VLIST;
class HASH : private VLIST {
int size;
VLIST *htable;
int prime(int&);
int hashval(int);
public:
HASH();
HASH(const HASH&);
HASH(int);
~HASH();
void store(ELEMENT);
void update(ELEMENT, ELEMENT);
void kill(ELEMENT);
ELEMENT retrieve(ELEMENT);
void hdump();
};
------------------------------ CUT HERE ----------------------------------
Here are the members of HASH. I've left some commented out code,
a for-loop in the X(const X&) constructor so that anybody willing to
can experiment along that same lines that I was, trying to get the
thing to do a list per list, node per node duplication on assignment.
Also, pay careful attention to the comments above hashval(). I
haven't yet decided on how to get this function to support genericity,
as you can see.
Operation of the hash table methods should be obvious enough.
You might want to add some random find '*' and next '*' type
methods, if you don't implement this object in such a way that
its contents are remembered externally.
Remember, you can say
HASH hashobj;
or
HASH hashobj = <size>;
or
HASH hashobj(size);
------------------------------ CUT HERE ----------------------------------
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
// \\
// hash.c Version 1.00 \\
// HASH member functions : May 29, 1990, Brian L. Donat \\
// \\
/////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
#define TRUE 1
#define FALSE 0
#define MINHASH 11
#include <stream.h>
#include "vlist.h"
#include "hash.h"
const ELEMENT EDUMMY = 0;
// Convert requested table size to a prime number >= size.
// Hash Tables work better with prime number table sizes.
int HASH::prime(int &size) {
if(size < MINHASH) size = MINHASH; // Assure a minimum table size.
for(int i = 2; i <= size; i++) {
for(int j = 2; i % j; j++) ;
if(j < size && i >= size) { size++; continue; } // prime >= size.
}
return (HASH::size = --i);
}
// Very Simple Hashing Function.
// Careful! Notice that ELEMENT is currently 'int'.
// There's a definite need for conversion functions
// here, if genericity is to be supported.
int HASH::hashval(ELEMENT E) { return ((E ^= 0xf0) << 4) % size; }
// Hash Table uses array of VLIST Objets of size = prime(size);
HASH::HASH() : size(MAXHASH), htable(new VLIST[prime(size)]) {}
HASH::HASH(int size) : htable(new VLIST[prime(size)]) {}
HASH::HASH(const HASH &cHT) : size(cHT.size), htable(new VLIST[prime(size)]) {
/*
for(int i = 0; i < size; i++) {
cHT[i].headend();
for(int j = cHT[i].getsize(); j > 0; j--) {
htable[i].add(cHT[i].getval()); cHT[i].step();
}
}
*/
}
HASH::~HASH() { // You've got to delete the lists first.
for(int i = 0; i < size; i++) { VLIST *vp = &htable[i];
vp->VLIST::~VLIST();
}
delete [size] htable;
}
void HASH::store(ELEMENT E) { htable[hashval(E)].insert(E); }
void HASH::kill(ELEMENT E) { hashError = FALSE;
if(htable[hashval(E)].find(E)) htable[hashval(E)].remove();
else hashError = TRUE;
}
void HASH::update(ELEMENT E, ELEMENT F) { hashError = FALSE;
kill(E); if(!hashError) store(F);
}
ELEMENT HASH::retrieve(ELEMENT E) { hashError = FALSE;
if(htable[hashval(E)].find(E)) return htable[hashval(E)].getval();
else { hashError = TRUE; return EDUMMY; }
}
// This is more of a diagnostic than
// anything else, but its structure
// should indicate a means for checking
// the table for forgotten entries.
void HASH::hdump() { hashError = FALSE;
for(int i = 0; i < size; i++) {
htable[i].headend();
cout << "\nList #" << i << ": ";
for(int j = htable[i].getsize(); j > 0; j--) {
ELEMENT E = htable[i].getval();
if(hashError) {
cout << " End of List" << flush;
hashError = FALSE;
break;
}
cout << E;
if(j > 1) cout << ",";
htable[i].step();
}
}
}
------------------------------ CUT HERE ----------------------------------
--infmx!briand@pyramid