/*! First increase or decrease zombie's alertness depending
 on player proximity. Then use alertness to check whether
 the zombie starts actively hunting. */
void update_alertness( game g ) {
    creature Z = g->ZombieListHead;
    int d;
    while( Z != NULL ) {
        chr z = Z->Character;
        // If a zombie sees another zombie hunting, it increases
        // alertness.
        creature Z1 = g->ZombieListHead;
        int num_alert = 0;
        while(Z1 != NULL) {
            chr z1 = Z1->Character; 
            d = distance(z1->pos, z->pos);
            num_alert += z1->alert && d <= zombie_sight_range && d > 0;
            Z1 = Z1->Next;
        }
        if(!z->alert) z->alertness += (randint(0, num_alert) != 0);

        d = distance( g->pc->pos, z->pos );
        if( d <= zombie_sight_range ) {
            if( z->alertness < max_alertness ) {
                z->alertness++;
            }
        } else if( z->alertness > 0 ) {
            if(randint(0, (d - z->alert)/(zombie_sight_range + z->alertness))) z->alertness--;
        }
        int check = randint( 0, max_alertness );
        if( ( z->alert && d > zombie_sight_range ) || ! z->alert ) {
            z->alert = ( check < z->alertness );
        }
        Z = Z->Next;
    }
}

void test() {
  /* Field testing: NWERC 2012 Problem I, Kattis pieceittogether */
  /* TODO: UVa 11294, UVa 10319 */

  for (int n = 1; n <= 15; n++) {
    for (int iter = 0; iter < 100; iter++) {
      int cnt = randint(1, 100);
      vii clauses(cnt);
      for (int i = 0; i < cnt; i++) {
        int a = randint(1, n) * (randint(1, 2) == 1 ? 1 : -1);
        int b = randint(1, n) * (randint(1, 2) == 1 ? 1 : -1);
        clauses[i] = ii(a, b);
      }
      // cout << n << " " << iter << " " << cnt << endl;

      TwoSat ts(n);
      iter(it,clauses) {
        ts.add_or(it->first, it->second);
      }
      if (ts.sat()) {
        vector<bool> is_true(n+1, false);
        // for (int i = 0; i < size(all_truthy); i++) if (all_truthy[i] > 0) is_true[all_truthy[i]] = true;
        rep(i,0,n) if (V[n+(i+1)].val == 1) is_true[i+1] = true;
        for (int i = 0; i < cnt; i++) {
          bool a = is_true[abs(clauses[i].first)],
             b = is_true[abs(clauses[i].second)];
          assert_true((clauses[i].first > 0 ? a : !a) || (clauses[i].second > 0 ? b : !b), true);
        }
      } else {
        for (int j = 0; j < (1<<n); j++) {

// Spawns a food source by rolling against the spawn rate
void spawn_food_source() {
  if (randreal() <= food_source_spawn_rate) {
    add_food_source(randint(1, grid_size), randint(1, grid_size), food_source_radius, food_source_rations);
    if (global_debug) {
      printf("Spawned food source at %i,%i with %i rations\n", food_list.back()->x, food_list.back()->y, food_list.back()->rations);
    }
  }
}

int test_F_mpn_mul_precache()
{
   mp_limb_t * int1, * int2, * product, * product2;
   F_mpn_precache_t precache;
   mp_limb_t msl;
   int result = 1;
   
   unsigned long count;
   for (count = 0; (count < 30) && (result == 1); count++)
   {
      unsigned long limbs2 = randint(2*FLINT_FFT_LIMBS_CROSSOVER)+1;
      unsigned long limbs1 = randint(2*FLINT_FFT_LIMBS_CROSSOVER)+1;
   
      int1 = (mp_limb_t *) malloc(sizeof(mp_limb_t)*limbs1);

      mpn_random2(int1, limbs1);
   
      F_mpn_mul_precache_init(precache, int1, limbs1, limbs2);   
           
      unsigned long count2;
      for (count2 = 0; (count2 < 30) && (result == 1); count2++)
      {    
#if DEBUG
         printf("%ld, %ld\n",limbs1, limbs2);
#endif

         unsigned long limbs3 = randint(limbs2)+1;
         int2 = (mp_limb_t *) malloc(sizeof(mp_limb_t)*limbs3);
         product = (mp_limb_t *) malloc(sizeof(mp_limb_t)*(limbs1+limbs2));
         product2 = (mp_limb_t *) malloc(sizeof(mp_limb_t)*(limbs1+limbs2));
         
         F_mpn_clear(int2, limbs3);
         mpn_random2(int2, limbs3);
      
         F_mpn_mul_precache(product, int2, limbs3, precache);
         
         if (limbs1 > limbs3) msl = mpn_mul(product2, int1, limbs1, int2, limbs3);
         else msl = mpn_mul(product2, int2, limbs3, int1, limbs1);
      
         unsigned long j;
         for (j = 0; j < limbs1+limbs3 - (msl == 0); j++)
         {
            if (product[j] != product2[j]) result = 0;
         }
      
         free(product2);
         free(product);
         free(int2);
      }
   
      F_mpn_mul_precache_clear(precache);
      
      free(int1);
   }   
   
   return result;
}

void Population::nextgen()
{
	int nchildren = 0;
	Genome** children = 0;
	
	if (nspecies > MAXSPECIES)
	{
		nspecies = MAXSPECIES;
		listshorten<Species*>(species, nspecies);
	}
	
	for (int i = 0; i < nspecies; i++)
	{
		species[i]->ngenomes /= 2;
		listshorten<Genome*>(species[i]->genomes, species[i]->ngenomes);
		
		int nbreed = globalfitness ? species[i]->avgfitness / globalfitness * NPOP - 1 : 1;
		if (species[i]->ngenomes == 0 || (nspecies > MINSPECIES && ((nbreed <= 0 && nspecies) || (species[i]->staleness > StaleLimit && i != 0))))
		{
			delete species[i];
			listremove<Species*>(species, nspecies, i);
			continue;
		}
		
		for (int j = 0; j < nbreed; j++)
		{
			Genome* child = 0;
			if (randfloat() < CrossoverChance)
			{
				Genome* g1 = species[i]->genomes[randint(0, species[i]->ngenomes-1)];
				Genome* g2 = species[i]->genomes[randint(0, species[i]->ngenomes-1)];
				child = mutate(cross(g1, g2));
			}
			else
			{
				Genome* g1 = species[i]->genomes[randint(0, species[i]->ngenomes-1)];
				child = mutate(g1);
			}
			
			listappend<Genome*>(children, nchildren, child);
		}
		
		species[i]->ngenomes = std::min(KEEPOLD, species[i]->ngenomes);
		listshorten<Genome*>(species[i]->genomes, species[i]->ngenomes);
	}

	if (nchildren > NPOP - KEEPOLD * nspecies)
	{
		nchildren = NPOP - KEEPOLD * nspecies;
		listshorten<Genome*>(children, nchildren);
	}
	
	addtospecies(children, nchildren);
	
	generation++;
}

    /****************************************************************
    SampleImage
        Samples the entire image and stores the sample in a list.
        Based on width,height it randomly samples the entire image.
    Exceptions:
        None
    ****************************************************************/
    void    SampleSet::SampleImage(Matrixu*    pGrayImageMatrix,
                                   uint        numberOfSamples, 
                                   int        w,
                                   int        h,
                                   Matrixu*    pRGBImageMatrix,
                                   Matrixu*    pHSVImageMatrix,
                                   float    scaleX, 
                                   float    scaleY )
    {
        try
        {
            ASSERT_TRUE( pGrayImageMatrix != NULL || pRGBImageMatrix != NULL || pHSVImageMatrix    != NULL );
            //find the width and height based on the current scale
            int scaledWidth        = cvRound( float(w) * scaleX );
            int scaledHeight    = cvRound( float(h) * scaleY );

            int numberOfRows;    
            int numberOfColumns;
            if ( pGrayImageMatrix != NULL ) 
            {        
                numberOfRows = pGrayImageMatrix->rows() - scaledHeight - 1;
                numberOfColumns = pGrayImageMatrix->cols() - scaledWidth - 1;
            }
            else if( pRGBImageMatrix != NULL )
            {
                numberOfRows = pRGBImageMatrix->rows() - scaledHeight - 1;
                numberOfColumns = pRGBImageMatrix->cols() - scaledWidth - 1;
            }
            else
            {
                numberOfRows = pHSVImageMatrix->rows() - scaledHeight - 1;
                numberOfColumns = pHSVImageMatrix->cols() - scaledWidth - 1;
            }

            ASSERT_TRUE( numberOfSamples <= ( numberOfRows * numberOfColumns ) );

            //resize the sample list to the required number of samples
            m_sampleList.resize( numberOfSamples );

            #pragma omp for
            for ( int i = 0; i < (int)numberOfSamples; i++ )
            {
                m_sampleList[i].m_pImgGray    = pGrayImageMatrix;
                m_sampleList[i].m_col        = randint( 0, numberOfColumns );
                m_sampleList[i].m_row        = randint( 0, numberOfRows );
                m_sampleList[i].m_height    = h;
                m_sampleList[i].m_width        = w;
                m_sampleList[i].m_pImgColor = pRGBImageMatrix;
                m_sampleList[i].m_pImgHSV    = pHSVImageMatrix;
                m_sampleList[i].m_scaleX    = scaleX;
                m_sampleList[i].m_scaleY    = scaleY;
            }
        }
        EXCEPTION_CATCH_AND_ABORT( "Failed to random sample entire image for the number of samples" );
    }

int Game::room_number()
{
	//	need to improve  ending if run out of possible rooms
	n1 = randint(2, 20);
	n2 = randint(2, 20);
	n3 = randint(2, 20);
	
	if(n1==n2 || n2==n3 || n3==n1) {
		cerr << "\nRandomizer engine fail: numbers are equal";
		n1 = randint(2, 20);
		n2 = randint(2, 20);
		n3 = randint(2, 20);
	}		//need to improve rerandom if finds equal int
	
	for(int i = 0; i != curr_rooms.size(); ++i) {	// iterate trough rooms vector and check if was before
		if (n1 == curr_rooms[i])	{
			n1 = randint(2, 20);
		} else if (n2 == curr_rooms[i])	{
			n2 = randint(2, 20);
		} else if (n3 == curr_rooms[i])	{
			n3 = randint(2, 20);
		}	
		if(n1 == curr_rooms[i] && n2 == curr_rooms[i] && n3 == curr_rooms[i]) {		// simulate full curr_rooms vector // need to improve
			cerr << "\nRun out of room numbers";
			cout << "\nYou`ve found the exit!";
			return -1;
		}
		//else 	{
		//	cerr << "\nRun out of room numbers";
		//	cout << "\nYou`ve found the exit!";
		//}
		
	}
	return n1, n2, n3;
}

void test() {
    /* Field testing: SPOJ HORRIBLE */

    int n = 100000;
    vi arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = randint(-1000, 1000);
    }

    segment_tree x(arr);
    segment_tree_slow xslow(arr);

    for (int i = 0; i < 100000; i++) {
        int op = randint(0, 2);
        if (op == 0) {
            int a = randint(0, n-1),
                b = randint(a, n-1);
            assert_equal(xslow.query(a, b), x.query(a, b));
        } else if (op == 1) {
            int idx = randint(0, n-1),
                val = randint(-1000, 1000);
            x.update(idx, val);
            xslow.update(idx, val);
        } else if (op == 2) {
            int a = randint(0, n-1),
                b = randint(a, n-1),
                v = randint(-1000, 1000);

            x.range_update(a, b, v);
            xslow.range_update(a, b, v);
        }
    }
}

int
rate_next(iter_t *iter)
{
	if (iter->i1) {
		iter->i1 = 0;
		return (int)randint(0,3);
	} else {
		iter->i1 = 1;
		return (int)randint(5,9);
	}
}

word_t test_randword1(rand_t state)
{
	word_t res = 0;
    int bits = (int) randint(7, state);
	int i;

	for (i = 0; i < bits; i++)
		res |= (WORD(1) << randint(WORD_BITS, state));

	return res;
}

void test5() {
  const int n = 97;
  int count = 0;
  perm root(*range(n));
  int a = 0, b = 0;
  while (a == b) {
    a = randint(1, n);
    b = randint(1, n);
  }
  swap(root[a], root[b]);  
  dfs(root, -1);
}

const char *
response(response_t type)
{
  if (!type)
    type = randint(RES_TYPES) + 1;

  /* wait to count the totals until it's used for the first time */
  if (!response_totals[type])
    count_responses(type);

  return res[type][randint(response_totals[type])];
}

int getch(int h, int ch)
{
	if (randint(0,2)!=0) return ch;
	int nch;
	if (ch < 3)
		nch = ch + randint(1,2);
	else if (ch > h-4)
		nch = ch + randint(-2,0);
	else
		nch = ch + randint(-2,2);
	return nch;
}

int test_F_mpn_mul()
{
   mp_limb_t * int1, * int2, * product, * product2;
   mp_limb_t msl, msl2;
   int result = 1;
   
   unsigned long count;
   for (count = 0; (count < 30) && (result == 1); count++)
   {
      unsigned long limbs2 = randint(2*FLINT_FFT_LIMBS_CROSSOVER)+1;
      unsigned long limbs1 = limbs2 + randint(1000);
   
      int1 = (mp_limb_t *) malloc(sizeof(mp_limb_t)*limbs1);

      mpn_random2(int1, limbs1);
        
      unsigned long count2;
      for (count2 = 0; (count2 < 30) && (result == 1); count2++)
      {    
#if DEBUG
         printf("%ld, %ld\n",limbs1, limbs2);
#endif

         int2 = (mp_limb_t *) malloc(sizeof(mp_limb_t)*limbs2);
         product = (mp_limb_t *) malloc(sizeof(mp_limb_t)*(limbs1+limbs2));
         product2 = (mp_limb_t *) malloc(sizeof(mp_limb_t)*(limbs1+limbs2));
         
         F_mpn_clear(int2, limbs2);
         mpn_random2(int2, randint(limbs2-1)+1);
      
         msl = F_mpn_mul(product, int1, limbs1, int2, limbs2);
         
         msl2 = mpn_mul(product2, int1, limbs1, int2, limbs2);
      
         unsigned long j;
         for (j = 0; j < limbs1+limbs2 - (msl == 0); j++)
         {
            if (product[j] != product2[j]) result = 0;
         }
         
         result &= (msl == msl2);
         
         free(product2);
         free(product);
         free(int2);
      }
   
      free(int1);
   }   
   
   return result;
}

// Creates the starting bacteria and populates the list
void create_starting_bacteria() {
  
  int s, i;
  Strain* strain;
  
  for (s = 0; s < num_strains; s++) {
    strain = strains[s];
    for (i = 1; i <= start_population_per_strain; i++) {
      add_bacterium(strain, randint(1,grid_size), randint(1,grid_size));
    }
  }

}

int test_F_mpn_splitcombine_bits()
{
    mp_limb_t * int1, * int2;
    ZmodF_poly_t poly;
    int result = 1;
    
    unsigned long count;
    for (count = 0; (count < 30000) && (result == 1); count++)
    {
        unsigned long limbs = randint(300)+1;
        unsigned long bits = randint(500)+1;
        unsigned long coeff_limbs = randint(100) + (bits-1)/FLINT_BITS + 1;
        unsigned long length = (FLINT_BITS*limbs - 1)/bits + 1;
        unsigned long log_length = 0;
        while ((1L << log_length) < length) log_length++;
        
#if DEBUG
        printf("limbs = %ld, bits = %ld, coeff_limbs = %ld\n", limbs, bits, coeff_limbs);
#endif
        
        int1 = (mp_limb_t *) malloc(sizeof(mp_limb_t)*limbs);
        int2 = (mp_limb_t *) malloc(sizeof(mp_limb_t)*limbs);
        ZmodF_poly_init(poly, log_length, coeff_limbs, 0);
        
        mpn_random2(int1, limbs);
        F_mpn_FFT_split_bits(poly, int1, limbs, bits, coeff_limbs);
        F_mpn_clear(int2, limbs);
        F_mpn_FFT_combine_bits(int2, poly, bits, coeff_limbs, limbs);

#if DEBUG
        F_mpn_printx(int1, limbs); printf("\n\n");
        unsigned long i;
        for (i = 0; i < length; i++) { F_mpn_printx(poly->coeffs[i], coeff_limbs); printf("\n");}
        printf("\n");
        F_mpn_printx(int2, limbs); printf("\n\n");
#endif

        unsigned long j;
        for (j = 0; j < limbs; j++)
        {
           if (int1[j] != int2[j]) result = 0;
        }
        
        ZmodF_poly_clear(poly);
        free(int2);
        free(int1);
    }
    
    return result;
}

string randstr(int llen, int rlen, int lc, int rc){

	string res = "";
	
	int len = randint(llen, rlen);
	for (int i = 0; i < len; ++i){
	
		char ch = randint(lc, rc);
		res.push_back(ch);
		
	}
	
	return res;

}

char *mkalphanum(int len) {
 //returns an alphanumeric string of len length
  int size = len + 1;
  char *s = malloc(sizeof(char) * size);
  char c;
  s[size] = 0;
  for (int i = 0; i < size;i++) {
    int typeflag = randint(1);
    if (typeflag == 0)
       s[i] = randalpha();
    else
       s[i] = randint(9) + '0';
  }
  s[size] = '\0';
  return s;
}

bool make_decision(int n)
{
	if (n > 100 || n < 1) error("Wrong percentage");
	int t = randint(1, 100);
	if (t <= n) return true;
	else return false;
}

Link* Link::insert(Link* n)   // insert n before this object; return n
{
	if (n->value < 1 || n->value > system_length) error("Too low/high value in inserted link");
	if (n == 0) return this;
	if (this == 0) return n;

	while (true)
	{
		while (this->find(n) != 0) // Проверка на присутствие свободных слотов на этом уровне.
		{
			if (n->value >= system_length) n->level++;
			else n->value = randint(1, 10);
		}
		if (n->value > this->value) // Если элемент больше по значению, добавляем его после данного элемента.
		{
			if (succ) succ->prev = n;
			n->succ = succ;
			n->prev = this;
			succ = n;

			return n;
		}
		else						// Если элемент меньше по значению, вставляем его до этого элемента.
		{
			n->succ = this;           // this object comes after n
			if (prev) prev->succ = n;
			n->prev = prev;           // this object's predecessor becomes n's predecessor
			prev = n;                 // n becomes this object's predecessor

			return n;
		}
	}
}