typemap.java

A program to find frequent molecular substructures and discriminative fragments in a database of mol

/*----------------------------------------------------------------------
  File    : TypeMap.java
  Contents: map for node/atom types to consecutive codes
  Author  : Christian Borgelt
  History : 10.08.2006 file created from file Elements.java
----------------------------------------------------------------------*/
package moss;

import java.util.Arrays;

/*--------------------------------------------------------------------*/
class Type implements Comparable {
/*--------------------------------------------------------------------*/

  protected int  type;          /* value of the type */
  protected int  code;          /* code  of the type */
  protected int  frq;           /* frequency in graph database */
  protected int  supp;          /* support   in graph database */
  protected int  idx;           /* index of last processed graph */
  protected Type succ;          /* successor in hash bin list */

  /*------------------------------------------------------------------*/

  public Type (int type, int code)
  {                             /* --- create a type object */
    this.type = type;           /* note the type value */
    this.code = code;           /* and  the type code */
    this.supp = this.frq = 0;   /* initialize the frequencies */
    this.idx  = -1;             /* clear the graph index */
  }  /* Type() */

  /*------------------------------------------------------------------*/

  public int compareTo (Object obj)
  {                             /* --- compare two type frequencies */
    if (this.frq < ((Type)obj).frq) return -1;
    if (this.frq > ((Type)obj).frq) return +1;
    return 0;                   /* return sign of freq. difference */
  }  /* compareTo() */

}  /* class Type */

/*----------------------------------------------------------------------
The above class is needed for sorting the types w.r.t. their frequency
in the graph database to process and for recoding the graphs.
----------------------------------------------------------------------*/

/*--------------------------------------------------------------------*/
public class TypeMap {
/*--------------------------------------------------------------------*/

  /* --- instance variables --- */
  protected Type[] types;       /* types and their frequencies */
  protected Type[] bins;        /* hash table for type to code map */
  protected int    max;         /* maximum number of types */
  protected int    size;        /* current number of types */
  protected int    idx;         /* index of current graph */

  /*------------------------------------------------------------------*/

  public TypeMap ()
  {                             /* --- create a type map */
    this.types = new Type[256]; /* create a vector for the types */
    this.bins  = new Type[255]; /* and a hash table */
    this.max   = (int)(0.75 *255);
    this.size  = this.idx = 0;  /* init. counters and graph index */
  }  /* TypeMap() */

  /*------------------------------------------------------------------*/

  public int size () { return this.size; }

  /*------------------------------------------------------------------*/

  private void rehash ()
  {                             /* --- reorganize the hash table */
    int  i, k, n;               /* loop variable, index, bin count */
    Type t;                     /* to traverse the types */

    n = (this.bins.length << 1) +1;
    this.bins = new Type[n];    /* create a new hash table */
    for (i = this.size; --i >= 0; ) {
      t      = this.types[i];   /* traverse the types */
      t.succ = this.bins[k = t.type % n];
      this.bins[k] = t;         /* add the type at the head */
    }                           /* of the approriate hash bin list */
    this.max = (int)(0.75 *n);  /* compute a new maximum number */
  }  /* rehash() */             /* of elements for rehashing */

  /*------------------------------------------------------------------*/

  public int add (int type)
  {                             /* --- add a type */
    int  i, code;               /* hash bin index, type code */
    Type t, v[];                /* new type object, realloc. buffer */

    code = this.encode(type);   /* get the type code */
    if (code >= 0)              /* if the type value is known, */
      return code;              /* simply return the type code */
    code = this.size++;         /* compute a new type code */
    if (code >= this.types.length) {
      i = code +((code > 256) ? code >> 1 : 256);
      v = new Type[i];          /* enlarge the type vector */
      for (i = this.size; --i >= 0; )
        v[i] = this.types[i];   /* copy the existing type objects */
      this.types = v;           /* and set the new vector */
    }
    this.types[code] = t = new Type(type, code);
    t.succ = this.bins[i = type % this.bins.length];
    this.bins[i] = t;           /* add a new type to the hash table */
    if (this.size >= this.max)  /* if the hash table is full, */
      this.rehash();            /* reorganize the hash table */
    return code;                /* return the type code */
  }  /* add() */

  /*------------------------------------------------------------------*/

  public int encode (int type)
  {                             /* --- encode a type value */
    int  i = type % this.bins.length;
    Type t = this.bins[i];      /* compute hash code and get bin list */
    while ((t != null) && (type != t.type))
      t = t.succ;               /* traverse the hash bin list */
    return (t != null) ? t.code : -1;
  }  /* encode() */             /* return the type code */

  /*------------------------------------------------------------------*/

  public int decode (int code)
  {                             /* --- decode a type code */
    if ((code < 0) || (code >= this.size))
      return code;              /* if code is unknown, return it */
    return this.types[code].type;
  }  /* decode() */             /* otherwise return corresp. value */

  /*------------------------------------------------------------------*/

  public void count (int code)
  {                             /* --- count occurrence of a type */
    Type t = this.types[code];  /* get the corresponding type object */
    t.frq++;                    /* and increment the counters */
    if (t.idx < this.idx) { t.idx = this.idx; t.supp++; }
  }  /* count() */

  /*------------------------------------------------------------------*/

  public void commit ()
  {                             /* --- commit support counting */
    if (++this.idx < Integer.MAX_VALUE)
      return;                   /* if there is no overflow, abort */
    for (int i = this.size; --i >= 0; )
      this.types[i].idx = -1;   /* reinitialize graph indices */
    this.idx = 0;               /* (per element and globally) */
  }  /* commit() */

  /*------------------------------------------------------------------*/

  public void trim (int min)
  {                             /* --- trim types w.r.t. frequency */ 
    for (int i = this.size; --i >= 0; ) {
      Type t = this.types[i];   /* traverse all types */
      if (t.supp < min) t.supp = t.frq = -1;
    }                           /* exclude infrequent types */
  }  /* trim() */

  /*------------------------------------------------------------------*/

  public void    clear      (int code)
  { Type e = this.types[code]; e.supp = e.frq =  0; }

  public void    exclude    (int code)
  { Type e = this.types[code]; e.supp = e.frq = -1; }

  public boolean isExcluded (int code)
  { return this.types[code].supp < 0; }

  public void    maximize   (int code)
  { Type e = this.types[code]; e.supp = e.frq = Integer.MAX_VALUE; }

  public boolean isMaximal  (int code)
  { return this.types[code].supp >= Integer.MAX_VALUE; }

  /*------------------------------------------------------------------*/

  public void sort ()
  {                             /* --- sort types w.r.t. frequency */ 
    Arrays.sort(this.types, 0, this.size);
    for (int i = this.size; --i >= 0; )
      this.types[i].code = i;   /* sort and recode the types */
  }  /* sort() */

}  /* class TypeMap */