---

PSet.hpp

Go to the documentation of this file.

/*==========================================================================
 * Copyright (c) 2001 Carnegie Mellon University.  All Rights Reserved.
 *
 * Use of the Lemur Toolkit for Language Modeling and Information Retrieval
 * is subject to the terms of the software license set forth in the LICENSE
 * file included with this software, and also available at
 * http://www.lemurproject.org/license.html
 *
 *==========================================================================
*/


// -------------------------------------------------------------------
// PSet.hpp (Plain set)
// ALB
//
// Template set class (base class of family of set classes)
//    . add objects using operator+() or add()
//    . remove objects using operator-() or remove()
//    . query for the presence of an object in set via operator[object]
//    . if user specifies no removals will occur, uses (efficient) block memory
//
// Required member functions of template ObjType:
//     hash(): returns a 32-bit hash of object
//         ==: returns 1 if objects are equal
//          =: assignment operator
// 
// Note also: ISet (set with index)
// -------------------------------------------------------------------

#ifndef _PSETH_
#define _PSETH_

#include "common_headers.hpp"
#include <cmath>
#include <memory.h>
#include <cassert>

static const float SPARSENESS = 1.5;
static const float GROW_FACTOR = 2.0;


template <class ObjType>
class PSet
{
protected:
  struct SET_NODE {
    ObjType          u;
    int              idx;           // used in derived classes, but not here
    struct SET_NODE *next;
  } ;
    
public:
  PSet(): currentSize(0),maxSize(0),hashTable(0) {}
  PSet(const int maxSize_p) : currentSize(0),hashTable(0) { open(maxSize_p); }
  ~PSet() { close(); }
  
  const int size()    const { return currentSize; }
  const int maxsize() const { return maxSize;     }

  void open(const int maxSize_p) {
    assert(hashTable==0);   // cannot call open() twice!
    assert(maxSize_p>0); 
    maxSize = maxSize_p;
    if (maxSize<2) maxSize=2;
    hashTableSize = smallestPrimeGreaterThan((int) (maxSize*SPARSENESS));
    hashTable = new SET_NODE * [hashTableSize];
    memset(hashTable, 0, hashTableSize*sizeof(SET_NODE *));
    setNodeSize = sizeof(SET_NODE);
  }
  
  void close() {
    if (hashTable) {
      for (int i=0; i<hashTableSize; i++) {
        SET_NODE *node=hashTable[i]; 
        while (node) {
          SET_NODE *next = node->next; 
          delete node;
          node = next;
        }
      }
      delete [] hashTable; 
    }
    hashTable=0;
    currentSize=0;
  }
  
  void clear() {
    if (maxSize==0) return;
    close();
    open(maxSize);
  }
  
  int add(const ObjType& u) {
    SET_NODE *sn = internalAdd(u);
    if (sn==0) return -1;                       // already a member
    assert(currentSize++<=maxSize);   
    return sn->idx;                            // new member
  }

  int remove(const ObjType& u) { // remove u from set: returns 1 iff u was in set
    const int idx = internalRemove(u);
    if (idx==-1) return 0;                 // not a member
    currentSize--;
    return 1;                              // was a member (not anymore)
  }
  
  int operator+=(const ObjType& u)  // add an elt to set: returns 1 if added. 
  { return add(u); }
  
  int operator-=(const ObjType& u)// remove elt from set: returns 1 if removed.
  { return remove(u); }
  
  const ObjType &operator[](const int idx) const {
    int a;
    a=idx; // suppress compiler warnings about not using idx
    cerr <<"PSet: operator[] (int) not supported!"<<endl;
    abort();
  }

  int operator[] (const ObjType& u) const { // returns +1 if found in set, -1 o/w
    int hashval = computeHash(u);
    SET_NODE *p = hashTable[hashval];
    while(p!=0 && !(p->u==u)) p=p->next;
    return ((p==0)? -1: 1);
  }
  

protected:
  SET_NODE *internalAdd(const ObjType &u) {
    int hashval = computeHash(u);

    // look for this object in the appropriate linked list
    for (SET_NODE* p=hashTable[hashval]; p!=0; p=p->next)
      if (p->u==u) return 0;                 // already a member
    
    // create new node and stick at head of linked list
    SET_NODE *sn = createNode(u);
    sn->idx  = currentSize;
    sn->next = hashTable[hashval];
    hashTable[hashval] = sn;    
    return sn;
  }
  
  int internalRemove(const ObjType &u) {
    // returns index of extracted object, or -1 if not there.
    int hashval = computeHash(u);
    SET_NODE* sn = hashTable[hashval];
    SET_NODE** pLast = &(hashTable[hashval]);
    while (sn) {
      if (sn->u == u) {
        int idx = sn->idx;
        *pLast = sn->next;
        deleteNode(sn);
        return idx;
      }
      pLast = &(sn->next);
      sn = sn->next;
    }
    return -1;
  }
  
  long smallestPrimeGreaterThan(const int n) {
    for (int i=n+1;; i++) {   
      // look for a j<sqrt(i) which divides evenly into i
      int s = (int) sqrt((float) i);
      int j;
      for (j=2; j<=s; j++)
        if ((i % j)==0) break; 
      if (j>s) return i;
    }
  }
  
protected:
  int computeHash(const ObjType &u) const {
    int h = u.hash() % hashTableSize;
    if (h<0) h*=-1;
    return h;
  }
  
  // memory management of nodes
  SET_NODE *createNode(const ObjType &u) {
    SET_NODE *n = new SET_NODE;
    n->u = u;              
    return n;
  }
  
 void deleteNode(SET_NODE *node) { delete node; }
  
protected:
  int currentSize;                    // # of elts currently in set 
  int maxSize;                        // # of elts allowable in set 
  int hashTableSize;              // size of hash table containing set  
  SET_NODE** hashTable;
  int setNodeSize;
};

#endif

---