/*
 * Queue Class
 * Written by Aaron J. Miller (20110911)
 */
#include <cstdio>
#include <cassert>

//==============================================================================
// Queue Class
//==============================================================================
template<typename T> class CQueue {
protected:
	struct item_s {
		T obj;
		struct item_s *next;
	} *m_head, *m_tail;

public:
	inline CQueue(): m_head((item_s *)0), m_tail((item_s *)0) {
	}
	inline ~CQueue() {
		while(!IsEmpty())
			Pop();
	}

	inline bool IsEmpty() {
		return m_head!=(item_s *)0?false:true;
	}
	inline void Push(const T &obj) {
		item_s *p;

		p = new item_s();
		p->obj = obj;
		p->next = (struct item_s *)0;

		if (m_tail)
			m_tail->next = p;
		else
			m_head = p;
		m_tail = p;
	}
	inline T Pop() {
		item_s *next;
		T obj;

		assert(!IsEmpty());

		next = m_head->next;

		obj = m_head->obj;
		delete m_head;

		if (!(m_head = next))
			m_tail = (item_s *)0;

		return obj;
	}
	inline void Sort() {
		item_s *prev, *before, *current;
		bool try_again;

		if (m_head==m_tail)
			return;

L_do_sort:
		try_again = false;
		prev = (item_s *)0;

		for
		(
			before=m_head,current=m_head->next;
			current;
			prev=before,before=current,current=current->next
		) {
			if (current->obj < before->obj) {
				try_again = true;
				if (!(before->next = current->next))
					m_tail = before;
				current->next = before;
				if (prev)
					prev->next = current;
				else
					m_head = current;
			}
		}

		if (try_again)
			goto L_do_sort;
	}
};

//==============================================================================
// Test Code
//==============================================================================
struct test_s {
  int x, y;

  inline test_s(int _x=0, int _y=0): x(_x), y(_y) {}

  inline bool operator<(const struct test_s &rhs) {
    int a, b;

    a = x+y; b = rhs.x+rhs.y;

    if (a==b)
      return (bool)(x < rhs.x);

    return (bool)(a < b);
  }
};

int main() {
  CQueue<test_s> q;

  q.Push(test_s(2, 5));
  q.Push(test_s(3, 4));
  q.Push(test_s(4, 8));
  q.Push(test_s(0, 9));
  q.Push(test_s(14,9));
  q.Push(test_s(9, 5));
  q.Push(test_s(5, 9));
  q.Push(test_s(12,13));
  q.Push(test_s(2, 2));
  q.Push(test_s(2, 2));

  q.Sort();

  while(!q.IsEmpty()) {
    test_s t;
    t = q.Pop();

    printf("%d %d (%d)\n", t.x, t.y, t.x+t.y);
  }

  return 0;
}

2 2 (4)
2 2 (4)
2 5 (7)
3 4 (7)
0 9 (9)
4 8 (12)
5 9 (14)
9 5 (14)
14 9 (23)
12 13 (25)