SORTTABLE(3X) — Subroutines

NAME

sorttable − generic sorted table for C++

SYNOPSIS

#include <codelibs/boolean.h>
#include <codelibs/sorttable.h>
// usage:
declare_sorttable(SORTTABLE, ELEMENT, KEY);
implement_sorttable(SORTTABLE, ELEMENT, KEY, BUMP, COMPARE);
// prerequisites:
int COMPARE(KEY k1, KEY k2);
class ELEMENT
{
public:
ELEMENT(ELEMENT &);
ELEMENT(KEY);
operator KEY();
operator=(ELEMENT &);
};
// the macros create:
class SORTTABLE
{
public:
SORTTABLE(long size = 0);
SORTTABLE(SORTTABLE &);
~SORTTABLE();
boolean find(KEY key);
boolean insert(KEY key);
boolean remove();
boolean remove(KEY key);
boolean operator+=(KEY key) { return insert(key); }
boolean operator-=(KEY key) { return remove(key); }
// operators += and -= are overloaded below
boolean operator==(KEY key) { return find(key); }
boolean operator!=(KEY key) { return !find(key); }
SORTTABLE &clear();
SORTTABLE &operator=(SORTTABLE &);
boolean &operator==(SORTTABLE &tab);
// operators += and -= are overloaded above
SORTTABLE &operator+=(SORTTABLE &tab);
SORTTABLE &operator-=(SORTTABLE &tab);
SORTTABLE &operator&=(SORTTABLE &tab);
// operator[] is overloaded:
ELEMENT &operator[](KEY key);
ELEMENT &operator[](long e);
ELEMENT &operator()();
ELEMENT &operator∗();
ELEMENT ∗operator->();
long currloc();
long size();
};
CC ... -lcodelibs

DESCRIPTION

Sorttable is a generic sorted table package for C++. It is much like hashtable(3X) but maintains an ordered list rather than a hashed list. It also allows treating the list as an array to directly access any item in the list. The use of hashtable(3X) is recommended instead of sorttable for performance reasons if ordering is not too important. Furthermore, qsort(3C) may be used to sort a hashtable if ordered lists aren’t needed too frequently.

DECLARATION

The declare_sorttable macro needs a name SORTTABLE for the new class, an ELEMENT class that describes each element of the table, and a KEY to access the ELEMENT.

The implement_sorttable macro also needs a BUMP value for controlling growth of the table, and a COMPARE function. The internal table is doubled in size until it reaches the BUMP value, after which the table is only grown in BUMP increments.

PRECONDITIONS

The COMPARE function must take two KEY arguments and return -1, 0, or 1 if the KEY k1 is less than, equal to, or greater than k2 (whatever THAT means). This is (conveniently enough) exactly what strcmp(3C) returns, making it easy to handle char∗ keys.

The ELEMENT class must have two constructors for both an ELEMENT and a KEY arguments, an operator KEY, and one assignment operator for an ELEMENT. The return values from operator= functions are unimportant. They probably should take reference arguments for ELEMENT and KEY classes, if appropriate.

USAGE

SORTTABLE ~SORTTABLE

A SORTTABLE may be constructed from another SORTTABLE or optionally by specifying its initial size. The SORTTABLE will grow beyond the initial size if necessary, so specifying a size is most useful for fine-tuning control of memory usage. Deleting a SORTTABLE deletes all ELEMENTs within it. All operations on a table update a current location pointer. This pointer always points to the last symbol accessed in any manner, making it handy to use in chaining together various operations.

find operator== operator!=

Search for an ELEMENT with the KEY key in the table. Return TRUE if found, or FALSE if not. Sets the current object to the one found, or where it should be inserted if it wasn’t found.

insert operator+=

Insert an ELEMENT with the key into the table. Return TRUE if it was inserted, and FALSE if it was already at the table. The current object pointer is set to the entry in either case. Operator+= is overloaded below for merging SORTTABLEs.

remove operator-=

Remove the ELEMENT pointed to by the key from the table. If there is no argument, then the current symbol, whatever it is, is removed. The current object pointer points to the next item in the list, or the end of the list. Operator-= is also overloaded below.

clear

Remove all elements from the SORTTABLE. Returns a reference to the cleared table to allow chaining of operations.

operator=

Set all the elements in this table to all the elements in the argument. This basically copies the specified SORTTABLE and returns a reference to this.

operator==

Compare two SORTTABLEs to see if they are the same. Return TRUE if they contain the same elements and FALSE if they don’t.

operator+=

Add all elements in the argument table to this SORTTABLE. This is useful for merging tables. Returns a reference to this. This operator is overloaded above for adding elements to a SORTTABLE.

operator-=

Remove all elements in the argument table from this SORTTABLE. Returns a reference to this. This operators is overloaded above for deleting elements from a SORTTABLE.

operator&=

This makes this the intersection of the two tables. Only the elements common to both tables are left within this. Returns a reference to this.

operator() operator∗

Return the current object, whatever it is. Generally only useful after a call to the find, or insert member functions.

operator->

Return a pointer to the current object. (Included for completeness.)

operator[]

(This operator is overloaded.) If the argument is a KEY, this is the equivalent of calling insert and operator∗ in sequence. The key is inserted into the table if it isn’t already there. By definition, this operator always succeeds and always returns an ELEMENT.

If the argument is a long, that ELEMENT in the table is returned. This allows array-like access to the ordered list. Sets the current location to the long argument. If the argument is out-of-bounds, the return value is undefined and will likely cause a core-dump.

currloc

Return the integer location of the current object.

size

Returns the number of items in the table.

EXAMPLE

#include <stdio.h>
#include <string.h>
#include <codelibs/sorttable.h>
class Symbol
{
char ∗name;
int value;
public:
Symbol(Symbol &s) { name = s.name; value = s.value; }
Symbol(char ∗nm) { name = nm; value = 0; }
Symbol &operator=(Symbol &s)
{ name = s.name; value = s.value; return ∗this; }
operator char∗() { return name; }
};
declare_sorttable(Table,Symbol,char∗)
implement_sorttable(Table,Symbol,char∗,1024,strcmp);
main(int argc, char ∗argv[])
{
Table tab;
int i;
// put all the command-line arguments into the table
for (i = 1; i < argc; i++)
tab += argv[i];
// delete these items, if they are there
tab -= "b";
tab -= "y";
// print the size of the table, then all its elements
printf("size = %d\n", tab.size());
for (i = 0; i < tab.size(); i++)
printf("%d: %s\n", i, (char∗)tab[i]);
return 0;
}

Museum

Related Articles