// SortedTable.h
// a table of pointers to objects which is sortable by key
// 11/16/97 Mori Tetsuya
// 12/16/97 Add removeAll()
#ifndef __SortedTable_H
#define __SortedTable_H
#pragma interface "SortedTable.h"
#include <iostream.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#ifndef __BASIC_TYPES__
#define __BASIC_TYPES__
typedef int Integer32;
typedef Integer32 SizeType;
typedef Integer32 OffsetType;
typedef Integer32 CounterType;
typedef Integer32 ArenaID;
typedef Integer32 EntryID;
typedef Integer32 BoolType;
enum { True = 1, False = 0 };
typedef Integer32 ComparisonType;
enum { GreaterThan = 1, EqualTo = 0, LessThan = 1 };
typedef void *PointerType;
#endif // __BASIC_TYPES__
#define CACHE
template<class DerivedSortableObject, class Key>
class SortableObject {
public:
virtual ~SortableObject() {}
virtual ComparisonType compare(Key &k) = 0;
virtual ComparisonType compare(DerivedSortableObject &o) = 0;
virtual Key getKey() = 0;
// static DerivedSortableObject nullObject;
virtual BoolType isNull() = 0;
};
// Object must be one of the basic objects of C++ language
// the Object itself is identical to its key
// null object is 0
template<class Object>
class SimpleSortableObject {
protected:
Object obj;
public:
SimpleSortableObject() {}
SimpleSortableObject(Object o): obj(o) {}
~SimpleSortableObject() {}
inline Object &operator =(Object o) {
return obj = o;
}
inline int compare(Object &o) {
// cout << "comparing " << obj << " with " << o << endl;
return obj > o ? 1 : obj < o ? -1 : 0;
}
inline int compare(SimpleSortableObject &e) {
// cout << "comparing " << obj << " with " << e.obj << endl;
return obj > e.obj ? 1 : obj < e.obj ? -1 : 0;
}
inline Object getKey() {
return obj;
}
static SimpleSortableObject nullObject;
inline int isNull() {
// cout << "investigating if " << obj << " is null" << endl;
return obj == (Object)0;
}
};
template <class Element, class Key>
class SortedPointerTable {
protected:
Element **table;
SizeType size; // # of elements in the table
SizeType allocatedSize; // # of affordable elements in the table
#ifdef CACHE
Key last;
SizeType cache;
#endif
public:
SortedPointerTable(Element **p, SizeType s) {
if (!p) return;
SizeType as;
for (as = 1 << 7; as <= s; as <<= 1)
;
if (table) {
removeAll();
delete table;
}
table = (Element **)new char[sizeof(Element *) * as];
if (!table) return;
allocatedSize = as;
memcpy((void *)table, (void *)p, sizeof(Element *) * s);
size = s;
sortElements();
#ifdef CACHE
cache = -1;
#endif
}
SortedPointerTable(SortedPointerTable &st) {
if (st.table == 0)
return;
SizeType as;
for (as = 1 << 7; as <= st.size; as <<= 1)
;
table = (Element **)new char[sizeof(Element *) * as];
if (!table) return;
allocatedSize = as;
if (st.size > 0) {
memcpy((void *)table, (void *)table, sizeof(Element *) * st.size);
}
size = st.size;
sortElements();
#ifdef CACHE
cache = -1;
#endif
}
SortedPointerTable(SizeType s = 1 << 7) {
SizeType as;
for (as = 1 << 7; as <= s; as <<= 1)
;
table = (Element **)new char[sizeof(Element *) * as];
if (!table) return;
allocatedSize = as;
size = 0;
#ifdef CACHE
cache = -1;
#endif
}
~SortedPointerTable() {
if (table)
delete (char *)table;
}
inline SizeType getSize() {
if (table)
return size;
else
return 0;
}
inline SizeType getCapacity() {
if (table)
return allocatedSize;
else
return 0;
}
Element *findElement(Key key) {
return (*this)[key];
}
inline Element *operator[](Key key) {
#ifdef CACHE
if (cache >= 0 && key == last)
return table[cache];
#endif
SizeType index = searchByKey(key);
if (index < size) {
if (table[index]->compare(key) == 0) {
#ifdef CACHE
last = key;
cache = index;
#endif
return table[index];
} else {
return 0;
}
} else {
return 0;
}
}
SizeType searchByKey(Key key) {
if (size == 0)
return 0;
SizeType bottom = 0;
SizeType top = size - 1;
SizeType middle;
int cmp;
while (bottom < top) {
middle = (bottom + top) / 2;
cmp = table[middle]->compare(key);
if (cmp < 0)
bottom = middle + 1;
else
top = middle;
}
// bottom == top
cmp = table[bottom]->compare(key);
if (cmp < 0)
bottom++;
// printStatus(key, bottom);
return bottom;
}
SizeType searchByElement(Element *e) {
if (size == 0)
return 0;
if (e == 0)
return 0;
SizeType bottom = 0;
SizeType top = size - 1;
SizeType middle;
int cmp = 0;
while (bottom < top) {
middle = (bottom + top) / 2;
cmp = table[middle]->compare(*e);
if (cmp < 0)
bottom = middle + 1;
else
top = middle;
}
// bottom == top
cmp = table[bottom]->compare(*e);
if (cmp < 0)
bottom++;
return bottom;
}
inline Element *pickupElement(SizeType index) {
return (*this)(index);
}
inline Element *operator()(SizeType index) {
return (0 <= index && index < size) ? table[index] : 0;
}
Element *insertElement(Element *e) {
return *this += e;
}
Element *operator+=(Element *e) {
if (!e) return 0; // cannot insert null element
#ifdef CACHE
cache = -1;
#endif
SizeType index = searchByElement(e);
if (index < size) {
if (table[index]->compare(*e) <= 0)
return 0; // elements must be unique or something is wrong
}
if(insertSpace(index) >= allocatedSize)
return 0; // out of memory or something is wrong
return table[index] = e;
}
inline Element *removeElement(Key key) {
return *this -= key;
}
Element *operator-=(Key key) {
SizeType index = searchByKey(key);
if (index < size) {
if (table[index]->compare(key) != 0)
return 0; // no elements with such key
#ifdef CACHE
cache = -1;
#endif
// find the element with the key
Element *e = table[index];
if (removeSpace(index) >= allocatedSize)
return 0; // something is wrong
return e; // removal is succesful
} else {
return 0; // Element e is bigger than the last
}
}
inline Element *removeElement(Element *e) {
return *this -= e;
}
Element *operator-=(Element *e) {
SizeType index = searchByElement(e);
if (index < size) {
if (table[index]->compare(*e) != 0)
return 0; // no elements with such key
// find the element with the key
#ifdef CACHE
cache = -1;
#endif
Element *e = table[index];
if (removeSpace(index) >= allocatedSize)
return 0; // something is wrong
return e; // removal is succesful
} else {
return 0; // Element e is bigger than the last
}
}
SizeType removeAll() {
#ifdef CACHE
cache = -1;
#endif
SizeType index;
Element *e;
for (index = 0; index < size; index++) {
e = table[index];
if (e != 0) {
delete e;
}
}
size = 0;
return index;
}
protected:
static int compare(const void *a, const void *b) {
return (*(Element **)a)->compare(**(Element **)b);
}
void sortElements() {
qsort((void *)table, size, sizeof(Element *), compare);
}
void printStatus(Key key, SizeType bottom) {
SizeType i;
cout << "size = " << size << endl;
for (i = 0; i < size; i++) {
cout << "[" << i << "] = " << table[i]->getKey() << endl;
}
cout << "searchByKey(" << key << ") = " << bottom << endl;
cout << endl;
}
SizeType insertSpace(SizeType index) {
if (size < index)
return allocatedSize; // index is too high
if (!(size < allocatedSize))
grow(); // if there is no space left grow it
if (!(size < allocatedSize))
return allocatedSize; // unable to grow
if (index < size) {
memmove(&table[index + 1], &table[index],
sizeof(Element *) * (size - index + 1));
}
size++;
return index;
}
SizeType removeSpace(SizeType index) {
if (size < index)
return allocatedSize;
if (index < size - 1) {
memmove(&table[index], &table[index + 1],
sizeof(Element *) * (size - index));
}
size--;
return index;
}
void grow() {
if (size < allocatedSize / 2)
return;
SizeType newas = allocatedSize << 1;
Element **newtable =
(Element **)new char[sizeof(Element *) * newas];
if (newtable == 0)
return;
memcpy((void *)newtable, (void *)table, sizeof(Element *) * size);
delete (char *)table;
table = newtable;
allocatedSize = newas;
}
};
template <class Element, class Key>
class SortedObjectTable {
protected:
Element *table;
SizeType size; // # of elements in the table
SizeType allocatedSize; // # of affordable elements in the table
#ifdef CACHE
Key last;
SizeType cache;
#endif
public:
SortedObjectTable(Element *p, SizeType s) {
if (!p) return;
SizeType as;
for (as = 1 << 7; as <= s; as <<= 1)
;
if (table) {
removeAll();
delete table;
}
table = (Element *)new char[sizeof(Element) * as];
if (!table) return;
allocatedSize = as;
memcpy((void *)table, (void *)p, sizeof(Element) * s);
size = s;
sortElements();
#ifdef CACHE
cache = -1;
#endif
}
SortedObjectTable(SortedObjectTable &st) {
if (st.table == 0)
return;
SizeType as;
for (as = 1 << 7; as <= st.size; as <<= 1)
;
table = (Element *)new char[sizeof(Element) * as];
if (!table) return;
allocatedSize = as;
if (st.size > 0) {
memcpy((void *)table, (void *)table, sizeof(Element) * st.size);
}
size = st.size;
sortElements();
#ifdef CACHE
cache = -1;
#endif
}
SortedObjectTable(SizeType s = 1 << 7) {
SizeType as;
for (as = 1 << 7; as <= s; as <<= 1)
;
table = (Element *)new char[sizeof(Element) * as];
if (!table) return;
allocatedSize = as;
size = 0;
#ifdef CACHE
cache = -1;
#endif
}
~SortedObjectTable() {
if (table)
delete (char *)table;
}
inline SizeType getSize() {
if (table)
return size;
else
return 0;
}
inline SizeType getCapacity() {
if (table)
return allocatedSize;
else
return 0;
}
inline Element *getTable() {
return table;
}
Element &findElement(Key key) {
return (*this)[key];
}
inline Element &operator[](Key key) {
#ifdef CACHE
if (cache >= 0 && key == last)
return table[cache];
#endif
SizeType index = searchByKey(key);
if (index < size) {
if (table[index].compare(key) == 0) {
#ifdef CACHE
last = key;
cache = index;
#endif
return table[index];
} else {
return Element::nullObject;
}
} else {
return Element::nullObject;
}
}
SizeType searchByKey(Key key) {
if (size == 0)
return 0;
SizeType bottom = 0;
SizeType top = size - 1;
SizeType middle;
int cmp;
while (bottom < top) {
middle = (bottom + top) / 2;
cmp = table[middle].compare(key);
if (cmp < 0)
bottom = middle + 1;
else
top = middle;
}
// bottom == top
cmp = table[bottom].compare(key);
if (cmp < 0)
bottom++;
// printStatus(key, bottom);
return bottom;
}
inline Element &pickupElement(SizeType index) {
if (index >= size)
return Element::nullObject; // index is out of range
return table[index];
}
Element &operator()(SizeType index) {
if (index >= size)
return Element::nullObject; // index is out of range
return table[index];
}
Element &insertElement(Element e) {
return *this += e;
}
inline Element &operator+=(Element e) {
if (e.isNull())
return Element::nullObject; // cannot insert null element
Key key = e.getKey();
SizeType index = searchByKey(key);
if (index < size) {
if (table[index].compare(key) <= 0)
return Element::nullObject;
// elements must be unique or something is wrong
}
#ifdef CACHE
cache = -1;
#endif
if(insertSpace(index) >= allocatedSize)
return Element::nullObject; // out of memory or something is wrong
return table[index] = e;
}
Element removeElement(Key key) {
return *this -= key;
}
inline Element operator-=(Key key) {
SizeType index = searchByKey(key);
if (index < size) {
if (table[index].compare(key) != 0)
return Element::nullObject; // no elements with such key
// find the element with the key
Element e = table[index];
if (removeSpace(index) >= allocatedSize)
return Element::nullObject; // something is wrong
#ifdef CACHE
cache = -1;
#endif
return e; // removal is succesful
} else {
return Element::nullObject; // Element e is bigger than the last
}
}
SizeType removeAll() {
SizeType i;
#ifdef CACHE
cache = -1;
#endif
for (i = 0; i < size; i++) {
table[i].~Element();
}
size = 0;
return i;
}
protected:
static int compare(const void *a, const void *b) {
return ((Element *)a)->compare(*(Element *)b);
}
void sortElements() {
qsort((void *)table, size, sizeof(Element), compare);
}
void printStatus(Key key, SizeType bottom) {
SizeType i;
cout << "size = " << size << endl;
for (i = 0; i < size; i++) {
cout << "[" << i << "] = " << table[i].getKey() << endl;
}
cout << "searchByKey(" << key << ") = " << bottom << endl;
cout << endl;
}
SizeType insertSpace(SizeType index) {
if (size < index)
return allocatedSize; // index is too high
if (!(size < allocatedSize))
grow(); // if there is no space left grow it
if (!(size < allocatedSize))
return allocatedSize; // unable to grow
if (index < size) {
memmove(&table[index + 1], &table[index],
sizeof(Element) * (size - index + 1));
}
size++;
return index;
}
SizeType removeSpace(SizeType index) {
if (size < index)
return allocatedSize;
if (index < size - 1) {
memmove(&table[index], &table[index + 1],
sizeof(Element) * (size - index));
}
size--;
return index;
}
void grow() {
if (size < allocatedSize / 2)
return;
SizeType newas = allocatedSize << 1;
Element *newtable =
(Element *)new char[sizeof(Element) * newas];
if (newtable == 0)
return;
memcpy((void *)newtable, (void *)table, sizeof(Element) * size);
delete (char *)table;
table = newtable;
allocatedSize = newas;
}
};
#endif // __SortedTable_H