//
// All exhanges are done on data 
// easy to code, but not recommended for sizeof (data) >> sizeof (Node*)
// see the other file 
//

#include <iostream>

class Node {
public:
  int data;
  Node* next, *prev;
  Node (int a, Node* p, Node* n) { next = n; prev = p; data = a; }
};

void
Swap (Node* A, Node* B)
{
  if (A == B) return;
  int tmp = A->data;
  A->data = B->data;
  B->data = tmp;
}

bool
Partition (Node& Front, Node& Rear, Node& Pivot)
{
  int direction = 0;
  Node *L = &Front, *R = &Rear;

  while (L != R)
    {
      if (L->data > R->data)
        {
          direction = 1 - direction;
          Swap (L, R); 
        }
      if (direction)
        R = R->prev;
      else
        L = L->next;
    }
  Pivot = *L;
  Pivot.next = NULL;
  Pivot.prev = NULL;
}

bool 
PrintNodes (Node* Front)
{
  for (; Front != NULL; Front = Front->next)
    cout << Front->data << " ";
  cout << endl;
}

int
main (int argn, char *argv[])
{
  Node Front (1, NULL, NULL);
  Node N1 (2, &Front, NULL);
  Node N2 (3, &N1, NULL);
  Node N3 (5, &N2, NULL);
  Node Rear (4, &N3, NULL);

  Node Pivot (0, NULL, NULL);

  Front.next = &N1;
  N1.next = &N2;
  N2.next = &N3;
  N3.next = &Rear;

  cout << "Initial: ";
  PrintNodes (&Front);
  Partition (Front, Rear, Pivot);
  cout << "Pivot: " << Pivot.data << endl << "Partioned: ";
  PrintNodes (&Front);

  return 0;
}