gordon%stats.ucl.ac.uk@NSS.CS.UCL.AC.UK (Gordon Joly) (04/11/89)
Config.g++ sun3, no FPA used at all. G++ 1.34.2, libg++ 1.34.0
all with gcc 1.34. On SUN3-/160, I get the following.
Gordon.
karl:/stats/staff/karl/gordon/c++/otto/table.gnu[17] g++ -c fib.try.cc
In function struct Integer fib (int):
fib.try.cc:17: aggregate type mismatch in conditional expression
karl:/stats/staff/karl/gordon/c++/otto/table.gnu[18] cat !$
cat fib.try.cc
//
// Example for B11b - of use of tables.
//
// A memo-ising function - using doubly recursive fibonacci as example
//
// G. P. Otto, 1987
#include "table.h"
static table fibresults; // table of known results
Integer
fib(int n)
{
Integer res = fibresults.lookup(n); // lookup answer
if (!fibresults.lastlookupOK){ // if not yet known
/* BUG? */ res = (n < 2)? Integer(1) : (fib(n-1) + fib(n-2)); // calculate it
fibresults.insert(n,res); // and note the result
}
return(res);
}
// PS didn't use "dispose"!
karl:/stats/staff/karl/gordon/c++/otto/table.gnu[19] cat table.cc
//
// a simple "table" class, written for B11b by G. P. Otto, 1987
//
// The data-type for "keytype" is almost arbitrary, but you must be able
// to check equality. (Actually assume that "==" works for keys.)
// IMPORTANT: the hash function needs to be re-designed for some different
// types & frequencies of keys. (See below.)
// The implementation used here uses a hash table, with chaining for
// overflow. (i.e. Have an array of lists which the data can be stored
// in - we use a "hash" function to transform the key into an array
// index, and then store that data on that list. In this implementation,
// the lists are not ordered.)
// If the hash function distributes the data around the lists reasonably,
// then the access & update operations are O((# items in table)/(size of
// hash table)) - however, worst possible case is O(# items in table).
// Thus, picking a good hash function is vital for good performance.
// See (e.g.) Sedgewick or Knuth.
#include <stream.h> // for error messages
#include "table.h"
// for readability ...
static const true = 1;
static const false = 0;
// and now, the code for the functions. See header for descriptions
// of what they do
table::table()
{
// init all the lists
for (int i = 0; i < hash_tab_size; i++)
list[i] = 0;
lastlookupOK = false; // since it didn't succeed!
// (somewhat arbitary)
}
table::~table()
{
// delete all the lists ...
for (int i = 0; i < hash_tab_size; i++)
while (list[i] != 0){
cell *p = list[i];
list[i] = list[i]->next;
delete p;
}
}
//
// hash function - maps keys as evenly as possible into the range
// [0, has_tab_size)
// NB IS LIKELY TO NEED RECODING FOR NEW KEYTYPES OR NEW FREQUENCY
// DISTRIBUTIONS OF KEYS.
//
static int
hash(keytype k)
{
return ((unsigned int)k % hash_tab_size);
// coercion to unsigned guarantees a non-negative answer
}
void
table::insert(keytype k, datumtype d)
{
int i = hash(k); // index of list to work on
// check whether already item with that key
for (cell *p = list[i]; p != 0; p = p->next){
if (p->key == k){ // if there is
p->datum = d; // overwrite previous
return; // and return
}
}
// otherwise, insert item, if there is room
p = new cell;
if (p != 0){
p->key = k;
p->datum = d;
p->next = list[i];
list[i] = p;
} else {
cerr << "ERROR: insert failed - can't get space for new data\n";
}
}
datumtype
table::lookup(keytype k)
{
for (cell *p = list[hash(k)]; p != 0; p = p->next){
if (p->key == k){
lastlookupOK = true;
return(p->datum);
}
}
lastlookupOK = false;
datumtype d;
return d; // return something, anyway
}
void
table::dispose(keytype k)
{
int i = hash(k); // index of list to work on
cell *cur; // will point to cell whose key is being examined
cell *prev; // will point to the previous cell, if any
for (cur=list[i], prev=0; cur != 0; prev=cur, cur=cur->next){
if (cur->key == k){
/*
* now want to remove the item pointed to by p
* from the list.
*/
if (prev == 0){ // at beginning of list
list[i] = cur->next;
} else {
prev->next = cur->next;
}
delete cur;
return;
}
}
// if we get here, the item wasn't in the table, so nothing to do
}
karl:/stats/staff/karl/gordon/c++/otto/table.gnu[20] tower@WHEATIES.AI.MIT.EDU (04/21/89)
Config.g++ sun3, no FPA used at all. G++ 1.34.2, libg++ 1.34.0
all with gcc 1.34. On SUN3-/160, I get the following.
Gordon.
karl:/stats/staff/karl/gordon/c++/otto/table.gnu[17] g++ -c fib.try.cc
In function struct Integer fib (int):
fib.try.cc:17: aggregate type mismatch in conditional expression
karl:/stats/staff/karl/gordon/c++/otto/table.gnu[18] cat !$
cat fib.try.cc
//
// Example for B11b - of use of tables.
//
// A memo-ising function - using doubly recursive fibonacci as example
//
// G. P. Otto, 1987
#include "table.h"
static table fibresults; // table of known results
Integer
fib(int n)
{
Integer res = fibresults.lookup(n); // lookup answer
if (!fibresults.lastlookupOK){ // if not yet known
/* BUG? */ res = (n < 2)? Integer(1) : (fib(n-1) + fib(n-2)); // calculate it
fibresults.insert(n,res); // and note the result
}
return(res);
}
I can tell you why you get this error: because Integer(1) returns an
object of type Integer, and Integer+Integer returns an object of type
IntTmp. I will fix the compiler to deal with this problem. In the
mean time, I am not sure whether I should have the compiler try to
guess what it is supposed to do, or to suggest that you cast the
result of the + operator to Integer. I will fix the compiler to give
a more instructive error message.
Aside to dl: this is what happens when classes get too smart...
Michael