extension.java

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

/*----------------------------------------------------------------------
  File    : Extension.java
  Contents: Molecular fragment extension management
  Author  : Christian Borgelt
  History : 11.03.2002 file created as file submol.java
            02.04.2002 function compareTo added
            19.02.2003 extension by carbon chains added
            01.08.2003 first version of ring extensions added
            05.08.2003 ring flag processing optimized (field "all")
            06.08.2003 file split, this part renamed to Extension.java
            07.08.2003 complete rewrite of extension functions
            09.06.2005 carbon chain bonds required to be bridges
            21.07.2005 element manager added, excluded check removed
            22.07.2005 handling of incomplete rings and trimming added
            24.07.2005 orientation check added to ring extension
            10.08.2005 wrapper functions makeFragment added
            11.08.2005 made abstract, subclasses MaxSrcExt and RightExt
            11.04.2006 function cmp added (for fragment reorganization)
            02.05.2006 parameters if function isCanonic changed
            03.05.2006 functions makeCanonic and makeWord added
            10.05.2006 function makeString added (code word printing)
            11.05.2006 second function isCanonic added
            12.05.2006 function compareRing added (part of compareTo)
            18.05.2006 field Extension.dst added, chain simplified
            31.05.2006 function isCanonic extended, result changed
            06.06.2006 adapted to changed type of bond flags
            07.06.2006 function compareWord added
            01.07.2006 adaptation of ring extensions moved here
            06.07.2006 generation of equivalent ring variants added
            08.08.2006 bug in definition of Extension.curr fixed
            10.08.2006 bug in function chain fixed (trimmed bonds)
----------------------------------------------------------------------*/
package moss;

/*----------------------------------------------------------------------
An extension structure records all relevant information about an
extension of a fragment and also information about the next extension
to be considered. Extensions are later turned into fragments and/or
embeddings (depending on whether an equivalent fragment exists).
----------------------------------------------------------------------*/

/*--------------------------------------------------------------------*/
public abstract class Extension {
/*--------------------------------------------------------------------*/

  /* --- constants: extension mode flags --- */
  public static final int BOND   = 1;  /* single bond */
  public static final int RING   = 2;  /* ring (must be marked) */
  public static final int CHAIN  = 4;  /* carbon chain */
  public static final int EQVARS = 8;  /* equivalent ring variants */

  /* --- instance variables --- */
  protected int       mode;     /* extension mode */
  protected int       max;      /* maximum fragment size */
  protected int       rgmin;    /* minimum ring size */
  protected int       rgmax;    /* maximum ring size */
  protected Fragment  frag;     /* base fragment  that is extended */
  protected Embedding base;     /* base embedding that is extended */
  protected Atom[]    atoms;    /* (relevant) atoms of extension */
  protected Bond[]    bonds;    /* (relevant) bonds of extension */
  protected int       size;     /* number of atoms in ring/chain */
  protected int       atnew;    /* number of new atoms in ring */
  protected int       bdnew;    /* number of new bonds in ring */
  protected int       chns;     /* number of carbon chains */
  protected int       src;      /* index of current anchor atom */
  protected int       idx;      /* current bond index in anchor atom */
  protected int       dst;      /* index of current destination atom */
  protected long      all;      /* all ring flags of current bond */
  protected long      curr;     /* current ring flag */
  protected int       pmin;     /* minimal position of ring bond */
  protected int       pmax;     /* maximal position of ring bond */
  protected int       pos1;     /* current positions of equivalent */
  protected int       pos2;     /* bonds for ring extensions */
  protected int       ccode;    /* code for a carbon atom */
  protected int[]     word;     /* code word for is/makeCanonic */

  /*--------------------------------------------------------------------
  The "size" field is also used to indicate the type of the extension.
  A negative size indicates a carbon chain extension, with the absolute
  value of the size being the chain length. A zero size indicates a
  single bond extension. Finally, a positive size indicates a ring
  extension, with the size being the number of atoms/bonds in the ring.
  --------------------------------------------------------------------*/

  public Extension (int mode, int max, TypeMap map)
  {                             /* -- create an extension structure */
    if ((mode & RING) == 0) mode &= ~EQVARS;
    this.mode  = mode;          /* note the extension mode and */
    this.max   = max;           /* the maximum fragment size */
    this.rgmin = this.rgmax = 0;
    this.atoms = new Atom[256]; /* initialize atom/bond vectors with */
    this.bonds = new Bond[256]; /* a maximum number of bonds/atoms */
    this.ccode = (map == null)  /* finally get the code for carbon */
               ? Atom.CARBON : map.encode(Atom.CARBON);
    this.word  = new int[1024]; /* initialize the code word */
  }  /* Extension() */

  /*--------------------------------------------------------------------
  The same extension object is reused to create extensions instead of
  creating a new extension object for each extension. As a consequence
  the fragment and embedding to extend are not passed directly to the
  constructor, but to an initialization function (see below).
  --------------------------------------------------------------------*/

  public void setRingSizes (int rgmin, int rgmax)
  { this.rgmin = rgmin; this.rgmax = rgmax; }

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

  public Fragment makeFragment ()
  { return new Fragment(this); }

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

  protected boolean ring ()
  {                             /* --- create a ring extension */
    int  i;                     /* loop variable */
    Atom a, s;                  /* to traverse the atoms of the ring */
    Bond b, r = null;           /* to traverse the bonds of the ring */

    this.chns = this.frag.chns; /* copy the chain counter and */
    s = this.atoms[0];          /* get the anchor atom (source) */
    while (this.all != 0) {     /* while there is another ring flag */
      while ((this.all & this.curr) == 0)
        this.curr <<= 1;        /* find the next ring flag and */
      this.all  &= ~this.curr;  /* remove it (it is processed now) */
      this.size  = 1;           /* initialize the ring size */
      this.bdnew = 1;           /* and the counters for */
      this.atnew = 0;           /* the new bonds and atoms */
      b = this.bonds[0];        /* get the first  ring bond */
      a = this.atoms[1];        /* and the second ring atom */
      do {                      /* traverse the ring */
        for (i = a.bondcnt; --i >= 0; ) {
          r = a.bonds[i];       /* traverse the bonds of the atom */
          if (((r.flags & this.curr) != 0) && (r != b))
            break;              /* find the next bond */
        }                       /* of the ring to be added */
        if ((i < 0) || (r.mark < -1))
          break;                /* if the ring is incomplete, abort */
        /* If r.mark < -1, the bond has been removed from the */
        /* molecule by trimming and thus cannot be followed.  */
        this.atoms[this.size  ] = a;   /* collect the atoms */
        if (a.mark < 0) this.atnew++;  /* and count new ones */
        this.bonds[this.size++] = r;   /* collect the bonds */
        if (r.mark < 0) this.bdnew++;  /* and count new ones */
        b = r;                  /* go to the next bond and atom */
        a = (b.src != a) ? b.src : b.dst;
      } while (a != s);         /* while the ring is not closed */
      if (a != s) continue;     /* check whether the ring was closed */
      if (this.base.atoms.length +this.chns +this.atnew > this.max)
        continue;               /* check the size of the fragment */