#include <stdio.h>          /* podkluchenie bibliotek*/
#include <string.h>
#include <conio.h>
#include <alloc.h>
#include <math.h>
#include <dos.h>
#define LIST struct list


LIST {
  int Nomer;          /*nomer poezda*/
  char Stanc[25];     /*stanciya naznacheniya*/
  float Vremya;       /*vremya otpravleniya*/

  LIST *next, *prev;  /*ykazateli na sledyushii i predudyshii elementu*/
};

LIST *ptr_Beg;


/* dobavlenie novogo elementa */
void Insert_List(char Stc[], int Nmr, float Vrm,
     int before) {

  LIST *ptrX, *ptr_Ls;
  int i;

  if(!ptr_Beg) {
    ptr_Beg = (LIST *)malloc(sizeof(LIST));

    strcpy(ptr_Beg->Stanc, Stc);
    ptr_Beg->Nomer = Nmr;
    ptr_Beg->Vremya = Vrm;
    ptr_Beg->next = ptr_Beg;
    ptr_Beg->prev = ptr_Beg;
    return;
  }

  ptrX = (LIST *)malloc(sizeof(LIST));
  before = (before < 0) ? abs(before) : (before + 1);
  // for(ptr_Ls = ptr_Beg; ptr_Ls -> next != ptr_Beg; ptr_Ls = ptr_Ls -> next);
  for(i = 1, ptr_Ls = ptr_Beg;
      (i < before);
      ptr_Ls = ptr_Ls -> next, i += 1);

  ptr_Ls -> prev -> next = ptrX;
  ptrX -> prev = ptr_Ls -> prev;

  ptrX -> next = ptr_Ls;
  ptr_Ls -> prev = ptrX;

  strcpy(ptrX->Stanc, Stc);
  ptrX->Nomer = Nmr;
  ptrX->Vremya = Vrm;

}

void Sortirovka() {

  int more;
  LIST *p;
  char *str;
  int i; float f;

  do {

    more = 0;

    for(p = ptr_Beg; p -> next != ptr_Beg; p = p -> next) {

      if((p -> next != ptr_Beg) && (p -> Nomer > p -> next -> Nomer)) {

        // copy string
        str = strdup(p -> Stanc);
        strcpy(p -> Stanc, p -> next -> Stanc);
        strcpy(p -> next -> Stanc, str);
        free(str);

        // other data
        i = p -> Nomer;
        p -> Nomer = p -> next -> Nomer;
        p -> next -> Nomer = i;

        f = p -> Vremya;
        p -> Vremya = p -> next -> Vremya;
        p -> next -> Vremya = f;

        more = 1;
      }

    }

  } while(more);

}

void Del_List(int n) {

  LIST *p, *p2;
  int found;

  do {
    found = 0;

    if(ptr_Beg -> Nomer >= n) {
      found = 1;
      p = ptr_Beg;
      if(ptr_Beg -> next == ptr_Beg) {
        free(ptr_Beg); ptr_Beg = NULL; return;
      }

      for(; p -> next != ptr_Beg; p = p -> next);
      p2 = ptr_Beg;
      ptr_Beg = p2 -> next;
      p -> next = ptr_Beg;
      free(p2); continue;
    }

    p = ptr_Beg;
    do {

      if(p -> next -> Nomer >= n) {
        found = 1;

        p2 = p -> next;
        p -> next = p2 -> next;
        free(p2); // return;
      }
      else p = p -> next;

    } while(p != ptr_Beg);

  } while(found);

}

/*podschet kolichestva poezdov do opredelennogo goroda*/
int Pynkt_List(char *Stc)
{
    int Count = 0;
    LIST *ptr_Ls;

    ptr_Ls = ptr_Beg;
    do {

      if( !strcmp(ptr_Ls -> Stanc, Stc) ) Count += 1;
      ptr_Ls = ptr_Ls -> next;

    } while(ptr_Ls != ptr_Beg);

    return Count;
};

void Print_List()
{
    LIST *ptr_Ls;

    if(!ptr_Beg) {
      printf("<empty queue>\n");
      return;
    }

    ptr_Ls = ptr_Beg;
    do {

      printf("   %-15s%-12d%-4.2f\n",
        ptr_Ls->Stanc, ptr_Ls->Nomer, ptr_Ls->Vremya);
      ptr_Ls = ptr_Ls -> next;

    } while(ptr_Ls != ptr_Beg);
};


int main() {                  /* osnovnaya programma */

    char c,Stc[25];
    int Count,Nmr;
    float Vrm;
    LIST *ptr,*ptrX,*ptr_Ls;
    int before;

    /*inicializaciya spiska*/
    ptr_Beg = NULL;

    clrscr();
    do {                      /*vuvod na ekran menu*/
     window(41,1,80,9);
     gotoxy(1,1);puts("1.Formirovanie spiska");
     gotoxy(1,2);puts("2.Vkluchenie elementa v spisok");
     gotoxy(1,3);puts("3.Ydalenie elementa iz spiska");
     gotoxy(1,4);puts("4.Nahojdenie kol-va poezdov do pynkta");
     gotoxy(1,5);puts("5.Pechat' spiska");
     gotoxy(1,6);puts("6.Sort");
     gotoxy(1,7);puts("7.Exit");
        c = getch();              /*ojidanie najatiya klavishi*/
        window(1,1,40,25);
        clrscr();
        switch(c) {             /*vubor punkta menu*/
            case '1':           /*formirovanie spiska*/

              while(1) {

                printf("Vvedite pynkt naznacheniya: "); scanf("%s",Stc);

                if(strcmp(Stc,"*")) {
                    printf("Vvedite nomer poezda: ");        scanf("%d", &Nmr);
                    printf("Vvedite vremya otpravleniya: "); scanf("%f", &Vrm);
                    Insert_List(Stc, Nmr, Vrm, 0);
                }
                else break;

              }
              break;

            case '2':
              printf("Vvedite pynkt nazn-ya, nomer i vremya: \n");
              scanf("%s%d%f",Stc,&Nmr,&Vrm);
              printf("add before(-)/after(+) #");
              scanf("%d", &before);
              Insert_List(Stc,Nmr,Vrm, before);
              break;

            case '3':            /*ydalenie elementa iz spiska*/
              Del_List(300);
              break;

            case '4':
              printf("Vvedite pynkt naznacheniya");
              scanf("%s",Stc);
              Count = Pynkt_List(Stc);
              printf("Kol-vo poezdov do pynkta nazn-ya = %d\n",Count);
              break;

            case '5':            /*pechat' vseh elementov spiska*/
              printf("Pynkt nazn-ya Nomer p-da Vremya otpr-ya \n");
              Print_List();
              break;

            case '6':
              Sortirovka();
              break;

//            case '7':           /*vuhod*/
//                break;
         }
     } while(c>'0' && c<'7');

  return 0;
}