#include "basic.h"



#include <string.h>
#include <values.h>
#include <math.h>



#define Debug true




/////////////////////////////////// General /////////////////////////////////

tcT void Exchange (T &X,
		   T &Y)
{
  if (& X == & Y)
    return;

  T Z = X;
  X = Y;
  Y = Z;
}




/////////////////////////////////// Boolean /////////////////////////////////

const char Bool2Char [3] = {'-', '+', '?'}; 


void Toggle (boolean& B)
{
  if (B != BooleanDontKnow)
    B = ! B;
}




/////////////////////////////////// Array ///////////////////////////////////

tcT T* ArrayInsert (uint Index, 
		    T*   &Data, 
		    uint &DataSize)
{  
  DataSize++;

  T* NewData = new T [DataSize];
  For (i, DataSize)
    if (i < Index)
      NewData [i] = Data [i];
    else if (i == Index)
      memset (& NewData [i], 0, sizeof (T));
    else
      NewData [i] = Data [i - 1];
  
  delete [] Data;
  Data = NewData;
  assert (Data != NULL);  
  

  return  & Data [Index];
}


tcT T* ArrayAppend (T*   &Data,
		    uint &DataSize)
{
  return  ArrayInsert (DataSize, Data, DataSize);
}


tcT void ArrayAugment (T*   &Data,
		       uint &DataSize,
		       uint Inc)
{
  if (Inc == 0)
    return;
  
  uint OldDataSize = DataSize;
  DataSize += Inc;
  
  T* NewData = new T [DataSize];
  assert (NewData != NULL);
  For (i, OldDataSize)
    NewData [i] = Data [i];
  memset (& NewData [OldDataSize], 0, sizeof (T) * Inc);
  
  delete [] Data;
  Data = NewData;
}


tcT void ArrayDelete (uint Index,
		      T*   &Data,
		      uint &DataSize)
{
  DataSize--;
  
  T* NewData = new T [DataSize];
  For (i, DataSize + 1)
    if (i < Index)
      NewData [i] = Data [i];
    else if (i > Index)
      NewData [i - 1] = Data [i];
  
  delete [] Data;
  Data = NewData;
  assert (Data != NULL);  
}


tcT void ArrayReduce (T*   &Data,
		      uint &DataSize,
		      uint Dec)
{
  if (Dec == 0)
    return;

  assert (Dec <= DataSize);
  DataSize -= Dec;
  
  T* NewData = new T [DataSize];
  assert (NewData != NULL);
  For (i, DataSize)
    NewData [i] = Data [i];
  
  delete [] Data;
  Data = NewData;
}




/////////////////////////////////// NAMED //////////////////////////////////

NAMED::NAMED (const char *initName):
  ROOT ()
{
  Name = StrNew (initName);
}


NAMED::~NAMED ()
{
  free (Name);
}




////////////////////////////////// String /////////////////////////////////

char* StrNew (const char* S)
{
  if (S == NULL)
    return NULL;
  else
    return strdup (S);
}



char *StrRename (char* &S,
		 const char* NewS)
{
  free (S);
  S = StrNew (NewS);

  return S;
}



char* StrEnd (char* S)
{
  return  & S [strlen (S)];
}



boolean  StrIsEmpty (const char* S)
{
  return (S == NULL || 
	  strlen (S) == 0);  
}



boolean  StrIsBlank (const char* S)
{
  For (i, strlen (S))
    if (S [i] != ' ')
      return false;
  
  return true;  
}



char*    StrChar (char C,
		  uint Len,
		  char* S)
{
  For (i, Len)
    S [i] = C;
  S [i] = 0;

  return S;
}



char*    StrBlank (uint  Len,
		   char* S)
{
  return StrChar (' ', Len, S);
}



char    *Long2Str (lint X,
		   char *S)
{
  sprintf (S, "%ld", X);
  return S;
}



boolean String2Boolean (const char* S)
{
       if (strcmp (S, "0") == 0)
    return false;
  else if (strcmp (S, "1") == 0)
    return true;
  else 
    return BooleanDontKnow;       
}



char* StrTrimLeading (char* S)
{
  for (uint i = 0; i < strlen (S) && S [i] == ' '; i++);
  memmove (S, & S [i], strlen (& S [i]) + 1);

  return S;
}



char* StrTrimTrailing (char* S)
{
  for (int i = (int) strlen (S) - 1; i >= 0 && S [i] == ' '; i--)
    S [i] = 0;

  return S;
}



char* StrTrim (char* S)
{
  return StrTrimLeading (StrTrimTrailing (S));
}



boolean StrIsLeft (const char* S,
		const char* Left)
{
  return (strncmp (S, Left, strlen (Left)) == 0);  
}




char* StrDeleteBlanks (char* S)
{
  for (int i = (int) strlen (S) - 1; i >= 0; i--)
    if (S [i] == ' ' ||
	S [i] == '\t')
      memmove (& S [i], & S [i + 1], strlen (S) - i);

  return S;
}



void StrReplace (char* Target,
		 uint Len,
		 const char* Source)
{
  const char* Tail = & Target [Len];
  memmove (& Target [strlen (Source)], Tail, strlen (Tail) + 1);
  memmove (Target, Source, strlen (Source));
}



char* StrVarIndex (const char* VarName,
		   uint  Index,
		   uint  Len,
		   char* Res)
{
  assert (Res != NULL);  
  assert (strlen (VarName) <= Len);

  
  sprintf (Res, "%*u", Len, Index);

  int i;  
  for (i = 0; i < Len && Res [i] == ' '; i++);
  i--;

  for (int j = strlen (VarName) - 1; j >= 0 && i >= 0; j--, i--)
    Res [i] = VarName [j];  


  return Res;  
}




/////////////////////////////////// I/O //////////////////////////////////

void PrintLn ()
{
  printf ("\n");
}



void PrintLines (uint LineNum)
{
  For (i, LineNum)
    PrintLn ();
}



void SkipLine (FILE* F)
{
  char C;  
  while (fscanf (F, "%c", &C) == 1)
    if (C == '\n')
      return;
}



void SkipLines (FILE* F,
		uint LineNum)
{
  For (i, LineNum)
    SkipLine (F);  
}



char SkipBlanks (FILE* F)
{
  char C;  
  while (fscanf (F, "%c", &C) == 1 &&
	 (C == ' ' || C == '\t'));
  ungetc (C, F);
  
  return C;
}



boolean ReadLine (FILE* F, 
		  char* S, 
		  uint Len)
{  
  assert (Len > 0);  

  char C = 0;  
  uint i;
  for (i = 0; fscanf (F, "%c", &C) == 1 && C != '\n'; i++)
    if (i < Len - 1)
      S [i] = C;
  S [minimum (i, Len - 1)] = 0;

  return (i > 0 || C != 0);
}



boolean ReadDouble (FILE* F, 
		    double &N)
{
  N = 0;

  // Skip spaces 
  char C = ' ';
  while (C == ' ' || C == '\t' || C == '\r')
    if (fscanf (F, "%c", &C) != 1)
      return false;
  ungetc (C, F);

    
  switch (C)
  {
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
    case '-':
      if (fscanf (F, "%lf", & N) != 1)
        return false;
      else
        return true;  
  
 /* Case ',':
      *N = UndefInt;  
      return true; */

    Case '\n':
      SkipLine (F);
      return false;  

    Default:
      return false;  
  }    
}



boolean ReadFloat (FILE* F, 
		   float &N)
{
  N = 0;  
  double R;
  if (! ReadDouble (F, R) 
      || fabs (R) > MAXFLOAT)
    return false;

  N = R;
  return true;  
}



boolean ReadInt (FILE* F, 
		 int &N)
{
  N = 0;  
  double R;
  if (! ReadDouble (F, R) 
      || R > MAXINT || R < MININT)
    return false;

  N = R;
  return true;  
}



boolean ReadUint (FILE* F, 
		  uint &N)
{
  N = 0;  
  double R;
  if (! ReadDouble (F, R) 
      || R < 0 || R > MAXUINT)
    return false;

  N = R;
  return true;  
}



boolean ReadString (FILE* F,
		    char* S,
		    uint Len)
{
  SkipBlanks (F);
  
  char C;  
  uint i;
  for (i = 0; 
       i < Len && fscanf (F, "%c", &C) == 1 && 
                  ! (C == ' ' || C == '\t' || C == '\n' || C == '\r'); 
       i++)
    S [i] = C;
  S [i] = 0;
  
  
  return  ! StrIsEmpty (S);
}



boolean FileExists (const char* FName)
{
  FILE* F = fopen (FName, "r");
  boolean Yes = (F != NULL);
  fclose (F);
  
  return Yes;
}



lint FileSize (FILE* F)
{
  assert (F != NULL);
  
  int Res = fseek (F, 0, SEEK_END);
  assert (Res == 0);

  return ftell (F);
}



boolean FileEmpty (FILE* F)
{
  return FileSize (F) == 0;
}




////////////////////////////////// Mathematics ////////////////////////////

const int  MININT  = -MAXINT - 1;
const uint MAXUINT = 2 * (uint) MAXINT + 1;



boolean Between (lint N,
		 lint L, 
		 lint U)
{ 
  return (L <= N && N < U); 
}



boolean BetweenEqual (lint N,
		      lint L, 
		      lint U)
{ 
  return (L <= N && N <= U); 
}



lint nint (double X)
{
  lint i;
  if (X > 0)  
    i = X + 0.5;  
  else
    i = X - 0.5;

  return i;  
}



lint lceil (double f)
{  
  lint i = f;
  if (i < f) return i+1; else return i; 
}



lint lfloor (double f)
{ 	
  lint i = f;
  if (i > f) return i-1; else return i; 
}



double Sqr (double X)  
{ 
  return X * X; 
}



static const double Epsilon = 1e-5;



boolean EqualFloat (double X, double Y)
{
  return (X == Y ||
	  fabs (X - Y) < Epsilon);
}



boolean NullFloat (double X)
{
  return EqualFloat (X, 0);
}



boolean GreaterEqualFloat (double X, double Y)
{
  return (X > Y || EqualFloat (X, Y));
}



boolean LessEqualFloat (double X, double Y)
{
  return (X < Y || EqualFloat (X, Y));
}




// Infinities, NaN

const double INF = HUGE_VAL;
const double NAN = INF - INF;



static dnan Double2Dnan (double X)
{
  dnan Y;
  double Z = X;
  memmove (& Y, & Z, sizeof (Z));

  return Y;
}



boolean IsNanOrInf (double X)
{
  return IsNANorINF (Double2Dnan (X));
}



boolean IsInf (double X)
{
  dnan Y = Double2Dnan (X);
  return IsNANorINF (Y) && IsINF (Y);
}



/*
boolean IsNan (double X)
{
  dnan Y = Double2Dnan (X);
  return IsNANorINF (Y) && ! IsINF (Y);
}
*/




// Random
#ifdef _turbo_C
  extern "C" int rand();
  double  randomR () 	   { return double(rand())/32768.0; }
  uint    randomI(uint n)  { return rand() % n; }
  boolean flipAtail ()	   { return rand() < 16384; }
//void    fixSeed ()	   { fixSeed??; }
#else
  extern "C" { double drand48(); void srand48(long seedval); }
  double  randomR ()	          { return drand48(); }
  uint    randomI (uint n)        { return int(drand48() * n) % n; }
  boolean flipAtail ()	          { return drand48() < 0.5; }
  void    fixSeed (lint SeedVal)  { srand48 (SeedVal); }
#endif


double RandomExponential (double Mean)
{
  assert (! Negative (Mean));

  double R = randomR ();
  return  Mean * log (1 / (1 - R));
}