#include <stdio.h>

#include <stdlib.h>

struct list {
    char data;
    struct list *next, *prev;
};

//функции работы с двунаправленным списком
struct list *add(struct list *, char);//добавление нового элемента в начало списка

void print(struct list *);//вывод списка на экран

void swap(struct list *, struct list *);//мееняет местами два элемента списка

int main() {
    struct list *l = 0;
//ввод начальных данных
    char data = 0;
    printf("%s", "Enter the sequence of balls [\'R\'ed/\'B\'lue/\'W\'hite]\nFor example: RWBBWRWB\n");
    while (data != '\n') {
        scanf("%c", &data);
        if ((data == 'R') || (data == 'B') || (data == 'W'))
            l = add(l, data);
        else if (data != '\n') //если введен символ, отличный от 'R', 'B' или 'W'
            printf("%s %c %s", "\n>Error: Invalid character [", data, "] will be ignored");
    }
//вывод получившегося списка
    printf("%s", "\nList: ");
    print(l);
//перестановка шаров
    int transpos = 0; //счетчик перестановок
    struct list *curr_el = l; //указатель на текущий элемент;
    struct list *first_2sw = l; //указатель на первый элемент с которым можно поменять текущий, при
//необходимости
    struct list *temp;
//сначала проходим список слева направо, переставляя в начало красные шары



while (curr_el) {
        if ((curr_el->data) == 'R')//если текущий красный
        {
//если указатель на первый не красный ссылается на тот же элемент что и текущий
            if (curr_el == first_2sw) {
//сдвигаем указатель на первый не красный шар вправо
                if (first_2sw->next)
                    first_2sw = first_2sw->next;
                else break;
            } else {
                swap(curr_el, first_2sw);
//если поменяли указатель на начало списка -- вернем на место ЧТОБЫ ЭТО ХЕРНЯ НЕ НАЧИНАЛА РАБОТАТЬ СНОВА С ТОГО ЧЛЕНА
                if (curr_el == l)
                    l = first_2sw;
                else if (first_2sw == l)
                    l = curr_el;
                temp = first_2sw;
                first_2sw = curr_el;
                curr_el = temp;
                first_2sw = first_2sw->next;
                transpos++;
                printf("%s %d %s", "\nList after", transpos, "transpositions:\t");
                print(l);
            }
        }
        curr_el = curr_el->next;
    }




//теперь пройдем список справа налево, переставляя в конец синие шары
    curr_el = l;
    if (curr_el)
        while (curr_el->next) //найдем последний элемент
            curr_el = curr_el->next;
    first_2sw = curr_el;
    while ((curr_el)) {
        if ((curr_el->data) == 'B')//если текущий синий
        {
//если указатель на первый не синий ссылается на тот же элемент что и текущий
            if (curr_el == first_2sw) {
//сдвигаем указатель на первый не синий шар влево
                first_2sw = first_2sw->prev;
            } else {
                swap(curr_el, first_2sw);
//если поменяли указатель на начало списка -- вернем на место
                if (curr_el == l)
                    l = first_2sw;
                else if (first_2sw == l)
                    l = curr_el;
                temp = first_2sw;
                first_2sw = curr_el;
                curr_el = temp;
                first_2sw = first_2sw->prev;
                transpos++;
                printf("%s %d %s", "\nList after", transpos, "transpositions:\t");
                print(l);
            }
        }
        curr_el = curr_el->prev;
    }
    printf("%s", "\nTo exit press Enter...");
    scanf("%c", &data);
    return 0;
}

struct list *add(struct list *first, char data) {
    struct list *new_el, *last = first;
    new_el = (struct list *) malloc(sizeof(struct list)); //выделяем память под новый элемент
    new_el->data = data;//присваиваем значение новому элементу списка
//если передан непустой указатель -- ищем последний элемент в списке
    if (first) {
//ищем последний элемент
        while ((last->next))
            last = last->next;
//вставляем новый элемент после последнего
        last->next = new_el;
        new_el->prev = last;
    } else {
        first = new_el;
        new_el->prev = 0;
    }
    new_el->next = 0;
    return first;//возвращаем указатель на начало списка
}

void print(struct list *l) {
    struct list *ll = l;
    while (ll) {
        printf("%c", ll->data);
        ll = ll->next;
    }
}

void swap(struct list *a, struct list *b) {
    struct list *temp;
    if (b->prev == a) {
        if (a->prev)
            a->prev->next = b;
        if (b->next)
            b->next->prev = a;
        b->prev = a->prev;
        a->prev = b;
        a->next = b->next;
        b->next = a;
    } else if (a->prev == b) {
        if (b->prev)
            b->prev->next = a;
        if (a->next)
            a->next->prev = b;
        a->prev = b->prev;
        b->prev = a;
        b->next = a->next;
        a->next = b;
    } else {
        if (b->prev)
            b->prev->next = a;
        if (b->next)
            b->next->prev = a;
        if (a->prev)
            a->prev->next = b;
        if (a->next)
            a->next->prev = b;
        temp = b->prev;
        b->prev = a->prev;
        a->prev = temp;
        temp = b->next;
        b->next = a->next;
        a->next = temp;
    }
}