#include <iostream>
struct Node {
int val;
Node* prev;
Node* next;
Node( ) :
val( 0 ),
prev( NULL ),
next( NULL ) {
}
};
void swap(Node * n1, Node * n2){
if(n1 == n2)
return;
if(n1 == 0 || n2 == 0){
std::cout << "\nPRIORITYQUEUE ERROR: Trying to swap with non-existent node\n";
return;
}
Node * temp = new Node;
temp->prev = n1->prev;
temp->next = n1->next;
n1->prev = n2->prev;
n1->next = n2->next;
n2->prev = temp->prev;
n2->next = temp->next;
if(n1->next != 0)
n1->next->prev = n1;
if(n1->prev != 0)
n1->prev->next = n1;
if(n2->next != 0)
n2->next->prev = n2;
if(n2->prev != 0)
n2->prev->next = n2;
delete temp;
}
void print( Node* r ) {
Node* p = r->next;
while( p != NULL ) {
printf( "%d ", p->val );
p = p->next;
}
}
Node* end( Node* r ) {
Node* p = r;
while( p->next != NULL ) {
p = p->next;
}
return p;
}
void print_reverse( Node* r ) {
Node* p = r;
while( p->prev != NULL ) {
printf( "%d ", p->val );
p = p->prev;
}
}
int main() {
Node* r1 = new Node( );
Node* r2 = new Node( );
Node* p1 = r1; Node* p2 = r2;
for( int i = 0; i < 10; ++i ) {
p1->next = new Node( );
p1->next->val = i;
p1->next->prev = p1;
p1 = p1->next;
}
for( int i = 0; i < 10; ++i ) {
p2->next = new Node( );
p2->next->val = 10 - i - 1;
p2->next->prev = p2;
p2 = p2->next;
}
printf( "old r1 forward " );
print( r1 );
printf( "\n" );
printf( "old r1 backword " );
print_reverse( end( r1 ) );
printf( "\n" );
printf( "old r2 forward " );
print( r2 );
printf( "\n" );
printf( "old r2 backword " );
print_reverse( end( r2 ) );
printf( "\n" );
p1 = r1;
while( p1->val != 3 ) { p1 = p1->next; }
p2 = r2;
while( p2->val != 7 ) { p2 = p2->next; }
swap( p1, p2 );
printf( "new r1 forward " );
print( r1 );
printf( "\n" );
printf( "new r1 backword " );
print_reverse( end( r1 ) );
printf( "\n" );
printf( "new r2 forward " );
print( r2 );
printf( "\n" );
printf( "new r2 backword " );
print_reverse( end( r2 ) );
printf( "\n" );
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKc3RydWN0IE5vZGUgewoJaW50ICAgdmFsOwoJTm9kZSogcHJldjsKCU5vZGUqIG5leHQ7CgkKCU5vZGUoICkgOgoJCXZhbCggMCApLAoJCXByZXYoIE5VTEwgKSwKCQluZXh0KCBOVUxMICkgewoJfQp9OwoKdm9pZCBzd2FwKE5vZGUgKiBuMSwgTm9kZSAqIG4yKXsKICAgIGlmKG4xID09IG4yKQogICAgICAgIHJldHVybjsKICAgIGlmKG4xID09IDAgfHwgbjIgPT0gMCl7CiAgICAgICAgc3RkOjpjb3V0IDw8ICJcblBSSU9SSVRZUVVFVUUgRVJST1I6IFRyeWluZyB0byBzd2FwIHdpdGggbm9uLWV4aXN0ZW50IG5vZGVcbiI7CiAgICAgICAgcmV0dXJuOwogICAgfQoKICAgIE5vZGUgKiB0ZW1wID0gbmV3IE5vZGU7CgogICAgdGVtcC0+cHJldiA9IG4xLT5wcmV2OwogICAgdGVtcC0+bmV4dCA9IG4xLT5uZXh0OwoKICAgIG4xLT5wcmV2ID0gbjItPnByZXY7CiAgICBuMS0+bmV4dCA9IG4yLT5uZXh0OwoKICAgIG4yLT5wcmV2ID0gdGVtcC0+cHJldjsKICAgIG4yLT5uZXh0ID0gdGVtcC0+bmV4dDsKCiAgICBpZihuMS0+bmV4dCAhPSAwKQogICAgICAgIG4xLT5uZXh0LT5wcmV2ID0gbjE7CiAgICBpZihuMS0+cHJldiAhPSAwKQogICAgICAgIG4xLT5wcmV2LT5uZXh0ID0gbjE7CiAgICBpZihuMi0+bmV4dCAhPSAwKQogICAgICAgIG4yLT5uZXh0LT5wcmV2ID0gbjI7CiAgICBpZihuMi0+cHJldiAhPSAwKQogICAgICAgIG4yLT5wcmV2LT5uZXh0ID0gbjI7CgogICAgZGVsZXRlIHRlbXA7Cgp9Cgp2b2lkIHByaW50KCBOb2RlKiByICkgewoJTm9kZSogcCA9IHItPm5leHQ7Cgl3aGlsZSggcCAhPSBOVUxMICkgewoJCXByaW50ZiggIiVkICIsIHAtPnZhbCApOwoJCXAgPSBwLT5uZXh0OwoJfQp9CgpOb2RlKiBlbmQoIE5vZGUqIHIgKSB7CglOb2RlKiBwID0gcjsKCXdoaWxlKCBwLT5uZXh0ICE9IE5VTEwgKSB7CgkJcCA9IHAtPm5leHQ7Cgl9CglyZXR1cm4gcDsKfQoKdm9pZCBwcmludF9yZXZlcnNlKCBOb2RlKiByICkgewoJTm9kZSogcCA9IHI7Cgl3aGlsZSggcC0+cHJldiAhPSBOVUxMICkgewoJCXByaW50ZiggIiVkICIsIHAtPnZhbCApOwoJCXAgPSBwLT5wcmV2OwoJfQp9CgppbnQgbWFpbigpIHsKCU5vZGUqIHIxID0gbmV3IE5vZGUoICk7CglOb2RlKiByMiA9IG5ldyBOb2RlKCApOwoJTm9kZSogcDEgPSByMTsgTm9kZSogcDIgPSByMjsKCWZvciggaW50IGkgPSAwOyBpIDwgMTA7ICsraSApIHsKCQlwMS0+bmV4dCA9IG5ldyBOb2RlKCApOwoJCXAxLT5uZXh0LT52YWwgPSBpOwoJCXAxLT5uZXh0LT5wcmV2ID0gcDE7CgkJcDEgPSBwMS0+bmV4dDsKCX0KCWZvciggaW50IGkgPSAwOyBpIDwgMTA7ICsraSApIHsKCQlwMi0+bmV4dCA9IG5ldyBOb2RlKCApOwoJCXAyLT5uZXh0LT52YWwgPSAxMCAtIGkgLSAxOwoJCXAyLT5uZXh0LT5wcmV2ID0gcDI7CgkJcDIgPSBwMi0+bmV4dDsKCX0KCQoJcHJpbnRmKCAib2xkIHIxICBmb3J3YXJkICIgKTsKCXByaW50KCByMSApOwoJcHJpbnRmKCAiXG4iICk7CgkKCXByaW50ZiggIm9sZCByMSBiYWNrd29yZCAiICk7CglwcmludF9yZXZlcnNlKCBlbmQoIHIxICkgKTsKCXByaW50ZiggIlxuIiApOwoJCglwcmludGYoICJvbGQgcjIgIGZvcndhcmQgIiApOwoJcHJpbnQoIHIyICk7CglwcmludGYoICJcbiIgKTsKCQoJcHJpbnRmKCAib2xkIHIyIGJhY2t3b3JkICIgKTsKCXByaW50X3JldmVyc2UoIGVuZCggcjIgKSApOwoJcHJpbnRmKCAiXG4iICk7CgkKCXAxID0gcjE7Cgl3aGlsZSggcDEtPnZhbCAhPSAzICkgeyBwMSA9IHAxLT5uZXh0OyB9CgkKCXAyID0gcjI7Cgl3aGlsZSggcDItPnZhbCAhPSA3ICkgeyBwMiA9IHAyLT5uZXh0OyB9CgkKCXN3YXAoIHAxLCBwMiApOwoJCglwcmludGYoICJuZXcgcjEgIGZvcndhcmQgIiApOwoJcHJpbnQoIHIxICk7CglwcmludGYoICJcbiIgKTsKCQoJcHJpbnRmKCAibmV3IHIxIGJhY2t3b3JkICIgKTsKCXByaW50X3JldmVyc2UoIGVuZCggcjEgKSApOwoJcHJpbnRmKCAiXG4iICk7CgkKCXByaW50ZiggIm5ldyByMiAgZm9yd2FyZCAiICk7CglwcmludCggcjIgKTsKCXByaW50ZiggIlxuIiApOwoJCglwcmludGYoICJuZXcgcjIgYmFja3dvcmQgIiApOwoJcHJpbnRfcmV2ZXJzZSggZW5kKCByMiApICk7CglwcmludGYoICJcbiIgKTsKCglyZXR1cm4gMDsKfQ==