alg/nway_refine.cpp

   1 //  This file is part of the Mussa source distribution.
   2 //  http://mussa.caltech.edu/
   3 //  Contact author: Tristan  De Buysscher, tristan@caltech.edu
   4
   5 // This program and all associated source code files are Copyright (C) 2005
   6 // the California Institute of Technology, Pasadena, CA, 91125 USA.  It is
   7 // under the GNU Public License; please see the included LICENSE.txt
   8 // file for more information, or contact Tristan directly.
   9
  10
  11 PathList
  12 ExtendPathWindows(PathList raw_list)
  13 {
  14   // to keep track of everything, this function acts like a finite state
  15   // automata:  3 bitfields: reset, extending, scanning - ie 8 states
  16   int reset = 0, extending = 0, scanning = 0;
  17
  18   int species_num = raw_list.SpeciesNum();
  19   int win_num = raw_list.WinNum();
  20
  21   int *cur_path, *next_path;
  22
  23   cur_path = new int[species_num];
  24   next_path = new int[species_num];
  25
  26   raw_list.ResetIndex();
  27
  28   while (no more windows avaible)
  29   {
  30     //cur_indices[0] + ref_ext == next_indices[0] + 1:
  31
  32     // state 000 - start/nominal search
  33     //
  34     if !reset && !extending && !scanning
  35     {
  36       if cur_path[0] == next_path[0]
  37       {
  38         scanning = 1;                   // go to state 001
  39         raw_list.IncreIndex();
  40       }
  41       else if cur_path[0] + 1 == next_path[0]
  42       {
  43         extending = 1;                  // go to state 010
  44         win_ext = 1;
  45         raw_list.SetDirty();
  46         raw_list.IncreIndex();
  47       }
  48       else
  49         reset = 1;                      // go to state 100
  50     }
  51
  52     // state 001 - scanning for ext window thru possible interleaving
  53     //
  54     else if !reset && !extending && scanning
  55     {
  56       if cur_path[0] == next_path[0]
  57         raw_list.IncreIndex();
  58       else if cur_path[0] + 1 == next_path[0]
  59       {
  60         extending = 1;                  // go to state 011
  61         win_ext = 1;
  62         raw_list.SetDirty();
  63         raw_list.IncreIndex();
  64       }
  65       else
  66         reset = 1;                      // go to state 101
  67     }
  68
  69     // state 010 - extending window with no interleaving
  70     //
  71     else if !reset && extending && !scanning
  72     {
  73       if (cur_path[0] + win_ext) == next_path[0]
  74       {
  75         extending = 1;                  // go to state 011
  76         raw_list.IncreIndex();
  77       }
  78       else if (cur_path[0] + win_ext + 1) == next_path[0]
  79       {
  80         win_ext++;
  81         raw_list.SetDirty();
  82         raw_list.IncreIndex();
  83       }
  84       else
  85         reset = 1;                      // go to state 110
  86     }
  87
  88     // state 011 - extending window with interleaving
  89     //
  90     else if !reset && extending && scanning
  91     {
  92       if (cur_path[0] + win_ext) == next_path[0]
  93         raw_list.IncreIndex();
  94       else if (cur_path[0] + win_ext + 1) == next_path[0]
  95       {
  96         win_ext++;
  97         raw_list.SetDirty();
  98         raw_list.IncreIndex();
  99       }
 100       else
 101         reset = 1;                      // go to state 111
 102     }
 103
 104
 105     // reset condition states, return to 000 after taking appropiate action
 106
 107     // state 100 - no extended window, no scanning happened
 108     // save basic window to extended window list
 109     if reset && !extending && !scanning
 110     {
 111       // return to start/nominal search state
 112       reset = 0;
 113     }
 114
 115     // state 101 - no extended window, scanned for interleaving
 116     // save basic window to extended window list, return to first clean
 117     else if reset && !extending && scanning
 118     {
 119       // return to start/nominal search state
 120       reset = 0;
 121       scanning = 0;
 122     }
 123
 124     // state 110 - extended window, no interleaving
 125     // calc extended window, save to extended window list
 126     else if reset && extending && !scanning
 127     {
 128       // return to start/nominal search state
 129       reset = 0;
 130       extending = 0;
 131     }
 132
 133     // state 111 - extended window, interleaved
 134     // calc extended window, save to ext win list, return to first clean
 135     else if reset && extending && scanning
 136     {
 137       // return to start/nominal search state
 138       reset = 0;
 139       extending = 0;
 140       scanning = 0;
 141      }
 142
 143   return ext_win;
 144 }