#include <iostream>

template <typename T>
struct DLListElem {
	T data;
	DLListElem<T> *next, *prev;
	DLListElem(const T& data, DLListElem<T>* next = nullptr, DLListElem<T>* prev = nullptr) : data(data), next(next), prev(prev) {}
};

template <typename T>
void freeList(DLListElem<T>* l) {
	DLListElem<T>* temp;
	while (l != nullptr) {
		temp = l;
		l = l->next;
		delete temp;
	}
}

// A <-> i <-> j <-> D

template <typename T>
void swap(DLListElem<T>* i, DLListElem<T>* j) {
	if (i == j) return;
	if (i->prev != nullptr) i->prev->next = j;
	if (j->next != nullptr) j->next->prev = i;
	DLListElem<T>* iPrev = i->prev;
	i->next = j->next;
	i->prev = j;
	j->next = i;
	j->prev = iPrev;
}
template <typename T>
void swapNext(DLListElem<T>* i, DLListElem<T>* j) {
	if (i == j) return;
	if (i->prev != nullptr) i->prev->next = j;
	i->next = j->next;
	j->next = i;
}

// O(n^2) time complexity
template <typename T>
void sortDescending(DLListElem<T>* start, DLListElem<T>* end) {
	for (DLListElem<T>* i = end; i != start && i != nullptr; i = i->prev) {
		DLListElem<T>* toSwap = i;
		for (DLListElem<T>* j = i->prev; j != start && j != nullptr; j = j->prev) {
			if (j->data < toSwap->data) toSwap = j;
		}
		//swap(i, toSwap);
		swapNext(i, toSwap);
	}
	// TODO: update prevs
}

int main() {
	DLListElem<int>* l1 = new DLListElem<int>(1);
	DLListElem<int>* l2 = new DLListElem<int>(2);
	DLListElem<int>* l3 = new DLListElem<int>(3);
	DLListElem<int>* l4 = new DLListElem<int>(4);
	DLListElem<int>* l5 = new DLListElem<int>(5);
	DLListElem<int>* l6 = new DLListElem<int>(6);
	DLListElem<int>* l7 = new DLListElem<int>(7);
	DLListElem<int>* l8 = new DLListElem<int>(8);
	
	// 8 7 2 5 6 1 4 3
	               l8->next = l7;
	l7->prev = l8; l7->next = l2;
	l2->prev = l7; l2->next = l5;
	l5->prev = l2; l5->next = l6;
	l6->prev = l5; l6->next = l1;
	l1->prev = l6; l1->next = l4;
	l4->prev = l1; l4->next = l3;
	l3->prev = l4;

	sortDescending(l8, l3);
	for (DLListElem<int>* i = l8; i != nullptr; i = i->next)
		std::cout << i->data << ", ";
	std::cout << std::endl;

	freeList(l1);
}