Appendix 5: C++ Classes for Searching

The following is a complete listing of the C++ integer set representation classes discussed in Column 13. The complete code can be found at this book’s web site.

Click here to view code image

class IntSetSTL {
private:
    set<int> S;
public:
    IntSetSTL(int maxelms, int maxval) { }
    int size() { return S.size(); }
    void insert(int t) { S.insert(t);}
    void report(int *v)
    {   int j = 0;
        set<int>::iterator i;
        for (i = S.begin(); i != S.end(); ++i)
            v[j++] = *i;
    }
};

Click here to view code image

class IntSetArray {
private:
    int n, *x;
public:
    IntSetArray(int maxelms, int maxval)
    {   x = new int[l + maxelms];
        n = 0;
        x[0] = maxval;
    }
    int size() { return n; }
    void insert(int t)
    {   for (int i = 0; x[i] < t; i++)
            ;
        if (x[i] == t)
            return;
        for (int j = n; j >= i; j--)
            x[j+l] = x[j];
        x[i] = t;
        n++;
    }


    void report(int *v)
    {   for (int i = 0; i < n; i++)
            v[i] = x[i];
    }
};

Click here to view code image

class IntSetList {
private:
    int n;
    struct node {
        int val;
        node *next;
        node(int v, node *p) { val = v; next = p; }
    };
    node *head, *sentinel;
    node *rinsert(node *p, int t)
    {   if (p->val < t) {
            p->next = rinsert(p->next, t);
        } else if (p->val > t) {
            p = new node(t, p);
            n++;
        }
        return p;
    }
public:
    IntSetList(int maxelms, int maxval)
    {   sentinel = head = new node(maxval, 0);
        n = 0;
    }
    int size() { return n; }
    void insert(int t) { head = rinsert(head, t); }
    void report(int *v)
    {   int j = 0;
        for (node *p = head; p != sentinel; p = p->next)
            v[j++] = p->val;
    }
};

Click here to view code image

class IntSetBST {
private:
    int n, *v, vn;
    struct node {
        int val;
        node *left, *right;
        node(int v) { val = v; left = right = 0; }
    };
    node *root;
    node *rinsert(node *p, int t)
    {   if (P == 0) {
            p = new node(t);
            n++;
        } else if (t < p->val) {
            p->left = rinsert(p->left, t);
        } else if (t > p->val) {
            p->right = rinsert(p->right, t);
        } // do nothing if p->val == t
        return p;
    }
    void traverse(node *p)
    {   if (P == 0)
            return;
        traverse(p->left);
        v[vn++] = p->val;
        traverse(p->right);
    }
public:
    IntSetBST(int maxelms, int maxval) { root =0; n = 0; }
    int size() { return n; }
    void insert(int t) { root = rinsert(root, t); }
    void report(int *x) { v = x; vn = 0; traverse(root); }
};

Click here to view code image

class IntSetBitVec {
private:
    enum { BITSPERWORD = 32, SHIFT = 5, MASK = OxlF };
    int n, hi, *x;
    void set(int i)  {        x[i»SHIFT] |=  (l<<(i & MASK)); }
    void clr(int i)  {        x[i»SHIFT] &= ~(l<<(i & MASK)); }
    int  test(int i) { return x[i»SHIFT] &   (l<<(i & MASK)); }
public:
    IntSetBitVec(int maxelms, int maxval)
    {   hi = maxval;
        x = new int[l + hi/BITSPERWORD];
        for (int i = 0; i < hi; i++)
            clr(i);
        n = 0;
    }
    int size() { return n; }
    void insert(int t)
    {   if (test(t))
            return;
        set(t);
        n++;
    }
    void report(int *v)
    {   int j = 0;
        for (int i = 0; i < hi; i++)
            if (test(i))
                v[j++] = i;
    }
};

Click here to view code image

class IntSetBins {
private:
    int n, bins, maxval;
    struct node {
        int val;
        node *next;
        node(int v, node *p) { val = v; next = p; }
    };
    node **bin, *sentinel;
    node *rinsert(node *p, int t)
    {   if (p->val < t) {
            p->next = rinsert(p->next, t);
        } else if (p->val > t) {
            p = new node(t, p);
            n++;
        }
        return p;
    }
public:
    IntSetBins(int maxelms, int pmaxval)
    {   bins = maxelms;
        maxval = pmaxval;
        bin = new node*[bins];
        sentinel = new node(maxval, 0);
        for (int i = 0; i < bins; i++)
            bin[i] = sentinel;
        n = 0;
    }
    int size() { return n; }
    void insert(int t)
    {   int i = t / (1 + maxval/bins);
        bin[i] = rinsert(bin[i], t);
    }
    void report(int *v)
    {   int j = 0;
        for (int i = 0; i < bins; i++)
            for (node *p = bin[i]; p != sentinel; p = p->next)
                v[j++] = p->val;
    }
};