/* $Id: sorting.c,v 1.1.1.1 2003/11/04 23:34:57 mjames Exp $
 *
 * $Log: sorting.c,v $
 * Revision 1.1.1.1  2003/11/04 23:34:57  mjames
 * Imported into local repositrory
 *
 * Revision 1.14  2002/10/02 18:39:54  MJAMES
 * Stopped copying pin_col to index on every node
 *
 * Revision 1.13  2002/09/16 14:41:43  mjames
 * Merge back pin indexing bug that meant
 * pin AZ12 was indistinguishable from pin Z12 in
 * rename ident/name commands
 *
 * Revision 1.12  2002/09/09 10:10:21  mjames
 * Moved pin remapping function to pin ident editing function from
 * sorting pin name routine.
 *
 * Revision 1.11  2002/09/09 09:53:01  mjames
 * Moved pin remapping function to pin ident editing function from
 * sorting pin name routine.
 *
 * Revision 1.10  2002/08/23 14:13:55  mjames
 * Added legal/illegal pin identifying letters to the header file.
 * Upgraded sort to determine row/column locations of pins identified like
 * 'a1' and '1a' etc or '1' , '2'
 *
 * Revision 1.9  2001/10/31 22:33:27  mjames
 * Suppress diagnostic print
 *
 * Revision 1.8  2001/10/31 22:20:17  mjames
 * Tidying up problematical comments caused by CVS
 * 'intelligent' comment guessing
 *
 * Revision 1.7  2001/10/31 16:15:36  mjames
 * Added a datastructure to hide regular expression information from programs.
 *
 * Revision 1.6  2001/10/22 10:53:50  mjames
 * Added a declaration of the Vertical regular expression compiler
 * which validates and complains about older 'regular expressions'
 * used by Vertical prior to using regexp in the C library
 *
 * Revision 1.5  2001/10/10 20:17:59  mjames
 * Added a vert_regcomp function to compile regular expressions
 * with '^' (match start string) and  '$' (match end string) bracketing
 * this => wildcard must match entire string not just a part of it.
 *
 * Revision 1.4  2001/09/16 20:36:03  mjames
 * Second attempt to modify wire bundles to be connector rather than net
 * centric. Allows more than one connector to carry the same net,
 *
 * Revision 1.3  2001/09/16 19:48:53  mjames
 * Modified sorting algorithm to have sideffect of calculating pin rows and
 * columns for sockets.
 *
 * Revision 1.2  2001/06/06 12:10:17  mjames
 * Move from HPUX
 *
 * Revision 1.1.1.1  2000/10/19 21:58:40  mjames
 * Mike put it here
 *
 *
 * Revision 1.24  2000/10/04  10:37:10  10:37:10  mjames (Mike James)
 * Modified for Vertical2 : support COMPONENTS and SIGNALS
 * 
 * Revision 1.24  2000/10/04  10:37:10  10:37:10  mjames (Mike James)
 * Part of Release PSAVAT01
 * 
 * Revision 1.23  2000/10/02  11:04:21  11:04:21  mjames (Mike James)
 * new_vhdl
 * 
 * Revision 1.22  2000/09/27  14:42:21  14:42:21  mjames (Mike James)
 * Part of Release Sep_27_ST_2000
 * 
 * Revision 1.21  2000/09/21  10:15:51  10:15:51  mjames (Mike James)
 * Part of Release Sep21Alpha
 * 
 * Revision 1.20  2000/08/25  09:57:16  09:57:16  mjames (Mike James)
 * Part of Release Aug25_alpha
 * 
 * Revision 1.19  2000/08/16  08:57:33  08:57:33  mjames (Mike James)
 * Part of Release CD01_Aug2000
 * 
 * Revision 1.18  2000/08/14  14:45:13  14:45:13  mjames (Mike James)
 * Part of Release Aug_14_2000
 * 
 * Revision 1.17  2000/08/11  08:30:34  08:30:34  mjames (Mike James)
 * Part of Release Aug_11_2000
 * 
 * Revision 1.16  2000/08/09  10:31:49  10:31:49  mjames (Mike James)
 * Part of Release Aug__9_2000
 * 
 * Revision 1.15  2000/05/31  11:43:00  11:43:00  mjames (Mike James)
 * Part of Release May_31_2000
 * 
 * Revision 1.14  2000/05/08  17:01:40  17:01:40  mjames (Mike James)
 * Part of Release May__8_2000
 * 
 * Revision 1.13  2000/05/08  16:59:33  16:59:33  mjames (Mike James)
 * Part of Release May__8_2000
 * 
 * Revision 1.12  2000/05/08  16:57:10  16:57:10  mjames (Mike James)
 * Part of Release May__8_2000
 * 
 * Revision 1.11  2000/03/08  16:19:31  16:19:31  mjames (Mike James)
 * New version including PC
 * 
 * Revision 1.8  2000/01/20  15:58:50  15:58:50  mjames (Mike James)
 * Part of Release R22
 * 
 * Revision 1.7  99/12/22  11:15:31  11:15:31  mjames (Mike James)
 * Part of Release Dec_22_1999
 * 
 * Revision 1.6  99/06/25  14:35:51  14:35:51  mjames (Mike James)
 * Added in reference to expression.h, but no changes made 
 * to the function of acfread yet.
 * 
 * Revision 1.5  99/05/04  09:52:52  09:52:52  mjames (Mike James)
 * General checkin
 * 
 * Revision 1.4  98/02/11  11:27:19  11:27:19  mjames (Mike James)
 * Checked in for version 6.2a
 * 
 * Revision 1.3  97/04/23  08:43:25  08:43:25  mjames (Mike James)
 * CHecked in for release rel23041997
 * 
 * Revision 1.2  96/12/23  15:17:00  15:17:00  mjames (Mike James)
 * Altered because find_socket takes a reference
 * to the head-of-list-pointer noth the pointer itself.
 * 
 * Revision 1.1  96/12/23  10:26:21  10:26:21  mjames (Mike James)
 * Initial revision *  */
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#include <sys/types.h>
#include <regex.h>

/* TCL/Tk declarations */
#include "vertcl_main.h" 
#include "expression.h"
#include "generic.h"
#include "database.h"
#include "routing.h"
#include "cmdparse.h"
#include "cmdlog.h"
#include "sorting.h"


#ident "@(#)$Header: c:\\cygwin\\cvsroot/Vert03/vertlib/sorting.c,v 1.1.1.1 2003/11/04 23:34:57 mjames Exp $";


/* the comparison function  : requires upgrade for checking :
   A1...A10 then B1..B10 or is it   1a..10a then 1b..10b */
#if defined SORT_ORIGINAL
static int sort_nodes_compar(const void * p,const void * q)
{ char * s1 = (*(node_t **)p)->identifier; 
  char * s2 = (*(node_t **)q)->identifier;

  int l1 = strlen(s1);
  int l2 = strlen(s2);
  if(l1==l2) /* only call strcmp() for same length strings 
                This makes '2' smaller than '19' */
    return strcmp(s1,s2);
  else
    return l1-l2; /* if different lengths, use the shorter name */
}
#else


/* this sort works for alpha - numeric strings : A1 A2 
   use SWAP command to swap identifiers  */
static int sort_nodes_compar(const void * p,const void * q)
{
  char * s1 = (*(node_t **)p)->id_alpha_chars; 
  char * s2 = (*(node_t **)q)->id_alpha_chars;

  int l1    = (*(node_t **)p)->id_alpha_cnt;
  int l2    = (*(node_t **)q)->id_alpha_cnt;
  int diff = 0;
/*
  printf("cmp p: a %3s[%2d] n %3s[%2d]\n",
   (*(node_t **)p)->id_alpha_chars,
    (*(node_t **)p)->id_alpha_cnt,
    (*(node_t **)p)->id_numeric_chars,
    (*(node_t **)p)->id_numeric_cnt);
  printf("cmp q: a %3s[%2d] n %3s[%2d]\n",
   (*(node_t **)q)->id_alpha_chars,
    (*(node_t **)q)->id_alpha_cnt,
    (*(node_t **)q)->id_numeric_chars,
    (*(node_t **)q)->id_numeric_cnt);
*/

  if(l1==l2)
    {
    /* only call strcmp() for same length strings */ 
    diff = strncmp(s1,s2,l1);
/*
    printf("alpha cmp (%s,%s,%d) different %d\n",s1,s2,l1,diff);
*/
    if (diff==0) /* alpha same */
      { 
      /* otherwise check the numeric parts of the strings */
      /* these have been decoded already */
      l1    = (*(node_t **)p)->pin_row;
      l2    = (*(node_t **)q)->pin_row;
      diff  = l1-l2;
/*
      printf("num different %d\n",diff);
*/
      }
    }
  else
    {
    diff = l1-l2; /* if different alpha lengths, use the shorter name */
/*
    printf("alpha len different %d\n",diff);
*/
    }
/*
  printf("diff: %d  string %7s row %2d and %7s row%2d\n",diff,
    (*(node_t **)p)->identifier,
    (*(node_t **)p)->pin_row,
    (*(node_t **)q)->identifier,
    (*(node_t **)q)->pin_row);
*/
  return diff;
  }

#endif





/* this function sorts all of the pin references on a chip
   into alphanumeric order, and also generates a unique pin index for each pin
   in the case of alphanumeric pin identifiers : pin A1 or 1A will become index 1 */
#define BIG 1000000

/* mapping table has no letter 'I' or 'O' in it */
static unsigned char illegal_chars[] = PIN_MAP_ILLEGAL_CHARS;
  
void sort_nodes(socket_t * chip,extract_xy_t mode) {
  node_t * nodes = chip-> nodes;
  node_t ** sort_list;
  
  int alpha_seen = 0;
  int numeric_seen = 0;
/* Use generics to find out if the user has defined pin row/column 
   limits (in the case where top or bottom connector rows are not
   connected at all */

  generic_info_t gen[1];


/*
  printf("chip %s\n",chip->identifier);
*/
  int nodecnt = 0;

  int max_row = -BIG;
  int min_row =  BIG;
  int max_col = -BIG;
  int min_col =  BIG;

  while(nodes) {
/* to do  need to identify the pattern of node identifiers */
/* numeric only ? */
/* alpha only   ? */
/* alpha number */
/* number alpha */
/* highest pin number ? */
/* number of different alphas */
/* assign an ordinal automatically to each node element */

/* sorting data structure */
/* the form is 23A */
    if (nodes->identifier) 
      {
      if (isdigit(nodes->identifier[0]))
        {
        nodes->id_numeric_chars  = nodes->identifier;
        nodes->id_numeric_cnt    = 0;              /* the numeric part of the identifier */
        while(isdigit(nodes->identifier[nodes->id_numeric_cnt]))
          nodes->id_numeric_cnt++;  /* the number of numeric chars in this part of the identifier */
        nodes->id_alpha_chars    = nodes->identifier+nodes->id_numeric_cnt;
        nodes->id_alpha_cnt      = strlen(nodes->identifier)-nodes->id_numeric_cnt;
        }
      else
        {
        nodes->id_alpha_chars  = nodes->identifier;
        nodes->id_alpha_cnt    = 0;              /* the numeric part of the identifier */
        while(isalpha (nodes->identifier[nodes->id_alpha_cnt]))
          nodes->id_alpha_cnt++;  /* the number of numeric chars in this part of the identifier */
        nodes->id_numeric_chars    = nodes->identifier+nodes->id_alpha_cnt;
        nodes->id_numeric_cnt      = strlen(nodes->identifier)-nodes->id_alpha_cnt;
        }
    
/*
      printf("node : %s : alpha=%d num=%d\n",nodes->identifier,nodes->id_alpha_cnt,nodes->id_numeric_cnt);
*/
      }
    else
      {
      nodes->id_alpha_chars  = NULL;              /* the numeric part of the identifier */
      nodes->id_alpha_cnt    = 0;  /* the number of numeric chars in this part of the identifier */
      nodes->id_numeric_chars= NULL;
      nodes->id_numeric_cnt  = 0;
      }

/* dont touch the row/col indices unless asked to */
   if(mode == EXTRACT_XY)
     {
/* if digits seen these are assigned as row 1..n */
    if(nodes->id_numeric_cnt)
      {
      int index = atoi(nodes->id_numeric_chars);
      numeric_seen = 1;
      nodes->pin_row = index;
      if(index > max_row) 
        {
        max_row=index;
        }
      else if(index < min_row)    
        {
        min_row=index;
        }
      }
    else
      {
/* default is on row 1 */
      nodes->pin_row = 1;
      }
    if(nodes->id_alpha_cnt > 0)
      {
      alpha_seen = 1;
      }
    
    /* between 1 and a few letters can be processed */
    if(nodes->id_alpha_cnt > 0 && nodes->id_alpha_cnt <= MAX_ID_ALPHA_SORT )
      {
      int index; 
      int charcnt;
      index = 0;
      for (charcnt=0;charcnt<nodes->id_alpha_cnt;charcnt++)
        {
        int  i;
        char c,d;
        d = 0;
        c = toupper(nodes->id_alpha_chars[charcnt]);
        /* work out how many illegal chars are before this one */
        /* this mapping actually collapses I onto J and O onto P */
        /* I am assuming those two chars dont exist in the pin ID .... */
        /* flag an error and continue for the present */
        /* characters are actually coded as 1..n so that IDs like 'AA' look */
        /* different to 'A', which they wont be if the leading 'A' is coded as 0 */
        for (i=0;i< PIN_MAP_ILLEGAL_CHAR_COUNT; i++)
          {
          if(c==illegal_chars[i])
            {
            Log(LOG_GENERAL,"-- Warning : illegal pin ident character in %s(%d)\n",
               chip->identifier,nodes->identifier);
            }
          if(c>=illegal_chars[i])
            {
            d++;
            }
          }
        index *= (PIN_MAP_LEGAL_CHAR_COUNT+1); 
        index +=  (c-d-'A'+1);
        
        }
/*
      printf("'\n");
*/      nodes->pin_col = index;
      if(index > max_col) 
        {
        max_col=index;
        }
      else if(index < min_col)    
        {
        min_col=index;
        }
      }
    else
      {
/* default is column zero */
      nodes->pin_col = 0;    
      }
     }
    nodecnt++;
    nodes=nodes->sktnext;
    }
  
  
  chip-> max_pin_col = max_col== -BIG ? 0 : max_col;
  chip-> min_pin_col = min_col==  BIG ? 0 : min_col;
  chip-> max_pin_row = max_row== -BIG ? 0 : max_row;
  chip-> min_pin_row = min_row==  BIG ? 0 : min_row;
/*
  printf("chip %10s col %3d to %3d , row %3d to %3d\n",chip->identifier,max_col,min_col,max_row,min_row);
*/
  /* know the number of nodes now allocate storage for the pointers
     to be used by qsort() */
     
  sort_list = calloc(nodecnt,sizeof(node_t *));
  

  /* grab hold of all of the pointers */
  nodes = chip-> nodes;
  nodecnt = 0;
  while(nodes) {
    sort_list[nodecnt++]=nodes;
    nodes=nodes->sktnext;
    }
   
  /* sort them */
  
  if(nodecnt) {
    int i;

    qsort((void *)sort_list,
          nodecnt,sizeof(node_t *),&sort_nodes_compar);
    
    /* and now rebuild the list based on the sorted list */  
    chip->nodes    = sort_list[0];
    chip->lastnode = sort_list[nodecnt-1];
    
    /* relink the list */
    for(i=0;i<(nodecnt-1);i++) {
      sort_list[i]->sktnext = sort_list[i+1];
      }
    sort_list[nodecnt-1]->sktnext = NULL; 
    
    }

  free(sort_list);

  /* check for overrides in case there are missing rows/cols */

  if (get_generic_value(&chip->generics, "min_pin_row",gen) == IS_ATTRIBUTE) 
    {
    chip->min_pin_row = eval_expression(gen->expr, &chip->generics);
    }
  if (get_generic_value(&chip->generics, "max_pin_row",gen) == IS_ATTRIBUTE) 
    {
    chip->max_pin_row = eval_expression(gen->expr, &chip->generics );
    }
  if (get_generic_value(&chip->generics, "min_pin_col",gen) == IS_ATTRIBUTE) 
    {
    chip->min_pin_col = eval_expression(gen->expr, &chip->generics ); 
    }
  if (get_generic_value(&chip->generics, "max_pin_col",gen) == IS_ATTRIBUTE) 
    {
    chip->max_pin_col = eval_expression(gen->expr, &chip->generics ); 
    }
}
    
/* we have a pair of pointers to array elements */
    
static int sort_socket_compar(const void * p,const void * q)
{
  return strcmp((*(socket_t **)p)->identifier,(*(socket_t **)q)->identifier);
}


/* this function sorts all of  sockets into alphanumeric order */

socket_t * sort_sockets(socket_t ** head) {
  socket_t ** sort_list,* chip= *head;
  int sktcnt = 0;

  while(chip) {
    sktcnt++;
    chip=chip->next;
    }
  /* know the number of nodes now allocate storage for the pointers
     to be used by qsort() */
  sort_list = calloc(sktcnt,sizeof(socket_t *));

  /* grab hold of all of the pointers */
  chip = *head;
  sktcnt = 0;
  while(chip) {
    sort_list[sktcnt++]=chip;
    chip=chip->next;
    }
   
  /* sort them */
  
  if(sktcnt) {
    int i;
    qsort((char *)sort_list,
          sktcnt,
          sizeof(socket_t *),
          &sort_socket_compar);
    
    /* and now rebuild the list based on the sorted list */  
    *head    = sort_list[0];
    
    /* relink the list */
    for(i=0;i<(sktcnt-1);i++)  {
      sort_list[i]->next = sort_list[i+1];
      }
    sort_list[sktcnt-1]->next = NULL; 
    
    }
  free(sort_list);
  return * head;
}



/* compile regular expression according
   to Vertical expectations */
/* What is required is a whole string match. In order to 
   achieve this, the regular expression is bracketed with
   ^ and $ which mean in this context 'match start of string'
   and 'match end of string' */


int vert_regcomp(vert_regex_t ** vert_preg,char * expr)
  {    
  int rc;  
  vert_regex_t * preg; 
/* allocate structure members */
  preg          = calloc(1,sizeof(vert_regex_t));
  *vert_preg    = preg;
  rc = check_wildcard(expr);
  if (rc!=TCL_OK)
    {
    preg->buff = malloc(3);
    strcpy(preg->buff,"^$");
    }
  else 
    {
    preg->buff = malloc(strlen(expr)+3);
    sprintf(preg->buff,"^%s$",expr);
    }
/*  printf("-- compare '%s'\n",preg->buff); */
  rc = regcomp(preg->preg,preg->buff,REG_EXTENDED | REG_ICASE);
  return rc;
  }
 
/* tidy up */ 
int vert_regfree(vert_regex_t ** vert_preg)
   {
   regfree((*vert_preg)->preg);
   free((*vert_preg)->buff);
   free(*vert_preg);
   *vert_preg = NULL;
   return 0;
   }