Simplifier/Neatifier cette boucle bidirectionnelle?

Question

J'ai mes fils croisés quelque part (ou je n'ai pas assez dormi). J'ai besoin d'une boucle à double sens, et mon code actuel est tout simplement moche. Problème: Je cours le long d'un datastructre linéaire en utilisant un index. J'ai un index de départ, disons 120. Je veux courir alternativement dans les deux sens.

Exemple: 120.121.119.122.118.123.117, ...

j'ai un critère d'arrêt qui doit être rencontré pour chaque sens séparément. Si elle est rencontrée dans une direction, je veux seulement courir dans l'autre sens, si les deux sont rencontrés, j'ai besoin de quitter la boucle. De plus, je dois m'arrêter si l'indice suivant est invalide (fin de la structure des données, disons plus petit que 0 ou plus grand que 200). Exemple: Arrêt de l'exécution à 116 vers l'arrière et 130 vers l'avant: 120,121,119,122,118,123,117,124,116 (break), 125,126,127,128,129,130.

En cours d'exécution dans une direction d'abord, puis l'autre n'est malheureusement pas une option.

Mon code actuel est carrément moche. C'est beaucoup de lignes sans contenir de code "productif". Seule la logique d'itération:

int start_idx = 120; 
    int forward_idx = start_idx; 
    int backward_idx = start_idx; 

    bool next_step_forward = true; //should next step be forward or backward? 

    int cur_idx; 
    while(backward_idx >= 0 || forward_idx >= 0) 
    { 
    if(next_step_forward //if we should step forward 
     && forward_idx >= 0) //and we still can step forward 
    { 
     cur_idx = ++forward_idx; 

     if(forward_idx >= 200) //200 is fictive "max index" 
     { 
     next_step_forward = false; 
     forward_idx = -1; //end of data reached, no more stepping forward 
     continue; 
     } 

     if(backward_idx >= 0) 
     { 
     next_step_forward = false; 
     } 
    } 
    else if(!next_step_forward 
      && backward_idx >= 0) 
    { 
     cur_idx = --backward_idx; 
     if(backward_idx < 0) //beginning of data reached, no more stepping backward 
     { 
     next_step_forward = true; 
     continue; 
     } 

     if(forward_idx >= 0) 
     { 
     next_step_forward = true; 
     } 
    } 
    else 
    { 
     next_step_forward = !next_step_forward; //ever hit?, just security case 
     continue; 
    } 

    //loop body 
    //do something with cur_idx here 

    if(stoppingCriterionMet()) 
    { 

     if(cur_idx > start_idx) 
     { //this was a forward step, stop forward stepping 
     forward_idx = -1; 
     } 
     else 
     { //this was backward step, stop backward stepping 
     backward_idx = -1; 
     } 
    } 
    } 

Suis-je manque quelque chose? Toutes les astuces appréciées. Merci.

Édition 1: Il y a beaucoup de très belles réponses, qui mettent "faire quelque chose avec cur_idx" dans une fonction séparée. Bien que ce soit une idée parfaite pour la façon dont ma question a été posée, je préfère mettre le code itéré ailleurs et laisser le code productif là. J'ai un long algorithme et je veux le diviser après qu'il soit fini pour minimiser le travail de réaménagement.

Answer 1

Il est arrivé que j'ai codé presque ce problème aujourd'hui. Et j'ai utilisé une fonction d'itérateur C# pour le faire. Mais je pense que vous voulez une solution plus générique.

Si vous utilisez une langue dans laquelle vous pouvez créer vos propres itérateurs (C++, Java, C#), c'est facile. Vous venez de créer un itérateur personnalisé qui crache initialement les nombres en commençant par le centre. Ensuite, vous donnez à l'itérateur une fonction supplémentaire pour lui dire d'arrêter de courir dans la direction actuelle. Si vous faites quelque chose comme ça en C (ça me semble C), vous pouvez imiter ceci avec une structure contenant l'état de l'itérateur, et les fonctions que vous appelez pour l'avancer ou l'arrêter.

Answer 2

passe d'abord au piratage (en supposant C - adaptations nécessaires pour d'autres langues, mais les concepts sont fondamentalement un langage neutre):

void pass1(int start_x, int lo_limit, int hi_limit) 
{ 
    assert(start_x >= lo_limit && start_x <= hi_limit); 
    int lo_x = start_x - 1; 
    int hi_x = start_x + 1; 

    Process(start_x); 
    if (StopCriterion(start_x)) 
     return; // Is that correct? 

    while (lo_x >= lo_limit && hi_x <= hi_limit) 
    { 
     Process(lo_x); 
     if (StopCriterion(lo_x)) 
      lo_x = lo_limit - 1; 
     else 
      lo_x--; 
     Process(hi_x); 
     if (StopCriterion(hi_x)) 
      hi_x = hi_limit + 1; 
     else 
      hi_x++; 
    } 
    while (lo_x >= lo_limit) 
    { 
     Process(lo_x); 
     if (StopCriterion(lo_x)) 
      lo_x = lo_limit - 1; 
     else 
      lo_x--; 
    } 
    while (hi_x <= hi_limit) 
    { 
     Process(hi_x); 
     if (StopCriterion(hi_x)) 
      hi_x = hi_limit + 1; 
     else 
      hi_x++; 
    } 
} 

On ne sait pas ce qui devrait se produire si la position de départ correspond au critère d'arrêt . La recherche devrait-elle s'arrêter complètement, ou devrait-elle continuer vers le haut, ou vers le bas, ou les deux. J'ai choisi «arrêter complètement», mais un cas pourrait être fait pour l'une des options énumérées. Dans le cas de 'both', vous ne vous soucieriez même pas d'exécuter la vérification des critères d'arrêt. J'ai également choisi de faire le bas avant la direction supérieure; il est clairement trivialement inversé. L'ordre des deux dernières boucles n'a pas d'importance car si les deux directions se terminent par la même itération, aucune boucle de fin n'est exécutée; si une seule direction est terminée, la boucle correspondante ne s'exécutera pas du tout - seule l'autre le sera.

Comme il est encore le code répété là:

void pass2(int start_x, int lo_limit, int hi_limit) 
{ 
    assert(start_x >= lo_limit && start_x <= hi_limit); 
    int lo_x = start_x - 1; 
    int hi_x = start_x + 1; 

    Process(start_x); 
    if (StopCriterion(start_x)) 
     return; // Is that correct? 

    while (lo_x >= lo_limit && hi_x <= hi_limit) 
    { 
     Process_lo(&lo_x, lo_limit); 
     Process_hi(&hi_x, hi_limit); 
    } 
    while (lo_x >= lo_limit) 
     Process_lo(&lo_x, lo_limit); 
    while (hi_x <= hi_limit) 
     Process_hi(&hi_x, hi_limit); 
} 

void Process_lo(int *lo_x, int lo_limit) 
{ 
    Process(*lo_x); 
    if (StopCriterion(*lo_x)) 
     *lo_x = lo_limit - 1; 
    else 
     *lo_x--; 
} 

void Process_hi(int *hi_x, int hi_limit) 
{ 
    Process(*hi_x); 
    if (StopCriterion(*hi_x)) 
     *hi_x = hi_limit + 1; 
    else 
     *hi_x++; 
} 

contrôles de visibilité (fonctions statiques) etc gauche comme les détails de la langue de mise en œuvre.

Answer 3

Que pensez-vous de cela?

void do_loop(SomeType *arr, int start, int low, int high, int arr_max) 
{ 
    int downwardIndex, upwardIndex; 
    downwardIndex = upwardIndex = start; 
    while (downwardIndex > 0 && upwardIndex < arr_max) { 
     if (downwardIndex < low && upwardIndex > high) { 
      break; 
     } 
     if (downwardIndex > low) { 
      processElement(arr[downwardIndex]); 
      downwardIndex--; 
     } 
     if (upwardIndex < high) { 
      processElement(arr[upwardIndex]); 
      upwardIndex++; 
     } 
    } 
} 

Answer 4

Voici comment j'approche en C#:

const int UPPER_BOUND = 200; 
const int LOWER_BOUND = 0; 
const int START = 120; 
bool foundlower = false, foundupper = false; 
int upper, lower; 
upper = lower = START; 

while (!foundlower || !foundupper) { 
    if (!foundlower) { 
     if (--lower <= LOWER_BOUND) foundlower = true; 
     if (stoppingCriterionMet(lower)) foundlower = true; 
    } 

    if (!foundupper) { 
     if (++upper >= UPPER_BOUND) foundupper = true; 
     if (stoppingCriterionMet(upper)) foundupper = true; 
    } 
}