/*  File: keyset.c
 *  Author: Jean Thierry-Mieg (mieg@mrc-lmb.cam.ac.uk)
 *  Copyright (C) J Thierry-Mieg and R Durbin, 1992
 * -------------------------------------------------------------------
 * Acedb is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 * or see the on-line version at http://www.gnu.org/copyleft/gpl.txt
 * -------------------------------------------------------------------
 * This file is part of the ACEDB genome database package, written by
 * 	Richard Durbin (MRC LMB, UK) rd@mrc-lmb.cam.ac.uk, and
 *	Jean Thierry-Mieg (CRBM du CNRS, France) mieg@kaa.cnrs-mop.fr
 *
 * Description:
 ** public :  keySetAND OR XOR MINUS Order
 **   In addition keyset.h defines as macros                 
 **   keySetInsert/Remove, Create/Destroy , Max, Sort, Find  
 **  consider also w7/ksetdisp.c                             

        A KEYSET is an orderd Array of KEYs                  

 * Exported functions:
 * HISTORY:
 * Last edited: Apr 22 12:35 1999 (fw)
 * Created: Fri Jun  5 16:18:58 1992 (mieg)
 *-------------------------------------------------------------------
 */

/* $Id: keyset.c,v 1.5 1999/09/01 10:49:27 fw Exp $ */

#include "acedb.h"
#include "bs.h"
#include "pick.h"
#include "a.h"

#define KEYSIZE sizeof(KEY)

/**************************************************************/
      /* Pure chronologic order */

int keySetOrder(void *a,void *b)
{
  return
    (*(KEY*)a) > (*(KEY*)b)  ?
      1 : (*(KEY*)a) == (*(KEY*)b) ? 0 : -1 ;
}

/**************************************************************/
  /* This routine returns */
  /* the intersect (logical AND) of the first and second KEYSET */

KEYSET keySetAND(KEYSET x, KEYSET y)
{ 
  register int i = 0 , j = 0, k= 0 ;
  KEYSET z = keySetCreate();

  if(!x || !y )
    return z ;
  
  if ((x && x->size != KEYSIZE) || (y && y->size != KEYSIZE))
     messcrash ("keySetOR called on non KEY Array") ;

  while((i<keySetMax(x)) && (j<keySetMax(y)))
    { 
                      /*success, skip further in the 3 index */
      if(arr(x,i,KEY) == arr(y,j,KEY))
	{ array(z,k++,KEY) = arr(x,i++,KEY) ; 
	  j++ ;
	}
      else      /*recall that every index is in increasing order*/
	(keySetOrder(arrp(x,i,KEY),arrp(y,j,KEY)) < 0) ?  i++ : j++ ;
    }
 return z ;
}

/**************************************************************/
  /* This routine returns */
  /* the union (logical OR) of the first and second KEYSET */

KEYSET keySetOR(KEYSET x, KEYSET y)
{ 
  register int i = 0 , j = 0, k= 0 ;
  KEYSET z = keySetCreate();

  if(!x && !y )
    return z ;
  
  if ((x && x->size != KEYSIZE) || (y && y->size != KEYSIZE))
     messcrash ("keySetOR called on non KEY Array") ;

  if(!x)
    { keySetDestroy(z);
      z = arrayCopy(y) ;
      return z ;
    }

  if(!y)
    { keySetDestroy(z);
      z = arrayCopy(x) ;
      return z ;
    }


  while((i<keySetMax(x)) && (j<keySetMax(y)))
    { 
                      /*no doubles, skip further in the 3 index */
      if(arr(x,i,KEY) == arr(y,j,KEY))
	{ array(z,k++,KEY) = arr(x,i++,KEY) ; 
	  j++ ;
	}
      else      /*recall that every index is in increasing order*/
	if (keySetOrder(arrp(x,i,KEY),arrp(y,j,KEY)) < 0) 
	  array(z,k++,KEY) =  arr(x,i++,KEY) ;
	else
	  array(z,k++,KEY) =  arr(y,j++,KEY) ;
    }

 if(i == keySetMax(x))
   while(j<keySetMax(y))
     array(z,k++,KEY) =  arr(y,j++,KEY) ;
 else if(j == keySetMax(y))
   while(i<keySetMax(x))
     array(z,k++,KEY) =  arr(x,i++,KEY) ;
 
 return z ;
}

/**************************************************************/
  /* This routine returns */
  /* the exclusive union (logical XOR) of the first and second KEYSET */

KEYSET keySetXOR(KEYSET x, KEYSET y)
{ 
  register int i = 0 , j = 0, k= 0 ;
  KEYSET z = keySetCreate();


  if(!x && !y )
    return z ;
  
  if ((x && x->size != KEYSIZE) || (y && y->size != KEYSIZE))
     messcrash ("keySetXOR called on non KEY Array") ;

  if(!x)
    { keySetDestroy(z);
      z = arrayCopy(y) ;
      return z ;
    }

  if(!y)
    { keySetDestroy(z);
      z = arrayCopy(x) ;
      return z ;
    }

  while((i<keySetMax(x)) && (j<keySetMax(y)))
    { 
                /*discard the intersect */
      if(arr(x,i,KEY) == arr(y,j,KEY))
	{ i++; j++ ;
	}
	
      else      /*recall that every index is in increasing order*/
	{ 
	  if (keySetOrder(arrp(x,i,KEY),arrp(y,j,KEY)) < 0)
	    array(z,k++,KEY) =  arr(x,i++,KEY) ;
	  else
	    array(z,k++,KEY) =  arr(y,j++,KEY) ;
	}
    }

 if(i == keySetMax(x))
   while(j<keySetMax(y))
     array(z,k++,KEY) =  arr(y,j++,KEY) ;
 else if(j == keySetMax(y))
   while(i<keySetMax(x))
     array(z,k++,KEY) =  arr(x,i++,KEY) ;

 return z ;
}

/**************************************************************/
  /* This routine returns */
  /* the difference (logical AND NOT) of the first and second KEYSET */

KEYSET keySetMINUS(KEYSET x, KEYSET y)
{ 
  register int i = 0 , j = 0, k= 0 ;
  KEYSET z = keySetCreate();

  if(!x)
    return z ;
  
  if(!y)
    { keySetDestroy(z);
      z = arrayCopy(x) ;
      return z ;
    }

  if ((x && x->size != KEYSIZE) || (y && y->size != KEYSIZE))
     messcrash ("keySetOR called on non KEY Array") ;

  while((i<keySetMax(x)) && (j<keySetMax(y)))
     { 
                      /*no doubles, skip further in x y */
      if(arr(x,i,KEY) == arr(y,j,KEY))
	{ i++ ; j++ ;
	}
      else      /*recall that every index is in increasing order*/
	if (keySetOrder(arrp(x,i,KEY),arrp(y,j,KEY)) < 0) 
	  array(z,k++,KEY) =  arr(x,i++,KEY) ;
	else
	  j++ ;
    }

  while(i<keySetMax(x))
     array(z,k++,KEY) =  arr(x,i++,KEY) ;
 
 return z ;
}

/**************************************************************/
/* kill all 'a' and 'b' type members of given keyset */
void keySetKill (KEYSET ks) 
{
  int i ;
  KEY key ;

  i = keySetExists (ks) ? keySetMax (ks) : 0 ;
   while (i--)
    { key = keySet (ks, i) ;
    switch ( pickType(key))
      {
      case 'A':
        arrayKill (key) ;
        break ;
      case 'B':
        { OBJ obj ;
        if ((obj = bsUpdate (key)))
          bsKill (obj) ;              
        }
        break ;
      }
    }
}


/**************************************************************/
/**************************************************************/