#pragma once
//
// Exchange Sort Realization of Sorting_Machine_Template using One_Way_List
// Author: Dr. NUTSACK
//

#include "RECORD\Rec1.hpp"
#include "OWList\OWL1.hpp"

//-----------------------------------------------------------------------
// Template Class Specification
//-----------------------------------------------------------------------

template <class Item, class Item_Compare>
class Sorting_Machine_2
{
public: // Standard Operations
	Sorting_Machine_2 ();
	~Sorting_Machine_2 ();
	void Clear (void);
	void operator &= (alters Sorting_Machine_2& rhs);

	// Sorting_Machine_2 Specific Operations
	void Insert (consumes Item& x);
	void Change_To_Extraction_Phase (void);
	void Extract (produces Item& x);
	Integer Size (void);
	Boolean Is_In_Insertion_Phase (void);

private: // Representation
	typedef One_Way_List_1 <Item> Item_List;

	class SM_Rep_Class {
	public:
		Boolean insertion_phase;
		Item_List item_keeper;
	};
	typedef Record_1 <SM_Rep_Class> SM_Rep_Record;
	object SM_Rep_Record rep;

private: // Local Operations
	void Merge_Sort (alters Item_List& s);
	void Split (consumes Item_List & s, 
		produces Item_List& h1, 
		produces Item_List& h2
		);
	void Merge (
		produces Item_List& s,
		consumes Item_List& h1,
		consumes Item_List& h2
		);

	// Disallowed Sorting_Machine_2 Operations
	Sorting_Machine_2& operator = (const Sorting_Machine_2& rhs);
	Sorting_Machine_2 (const Sorting_Machine_2& s);
	Sorting_Machine_2* operator & (void) {return (this);};
	const Sorting_Machine_2* operator & (void) const {return (this);};
};

//-----------------------------------------------------------------------
// Member Function Implementations
//-----------------------------------------------------------------------

// Convention
// rep->item_keeper.left = < >
//

//----------------------------------------------------------------
// Local Operations
//----------------------------------------------------------------

template <class Item, class Item_Compare>
void Sorting_Machine_2<Item, Item_Compare>::Merge_Sort (
		alters Item_List& s
		)
// pre: any Item_List
// post: sorted Item_List
{
	//s.Move_To_Start();

	if (s.Right_Size () > 1) {
		object Item_List h1, h2;
		s.Move_To_Start();
		Split (s, h1, h2);
		Merge_Sort (h1);
		Merge_Sort (h2);
		Merge (s, h1, h2);
	}   // end if
}	// Merge_Sort

//----------------------------------------------------------------

template <class Item, class Item_Compare>
void Sorting_Machine_2<Item, Item_Compare>::Split (
         consumes Item_List& s, 
         produces Item_List& h1, 
         produces Item_List& h2
		 )
//  pre: s.left = < >
//  post: s = < > < >  and  1/2 of the items in #s are in h1,
//     and   the other 1/2 of the items in #s are in h2
{
	object Integer i, size;
	object Item x;

	size = s.Right_Size ();

	for (i = 0; i < size; i++) {
		s.Remove_Right (x);
		if (Item_Compare::Are_Ordered (s[0], x)) {
			h1.Add_Right (s[0]);
			h1.Advance ();
		} // end if
		else {
			h2.Add_Right (s[0]);
			h2.Advance ();
		} // end else
	} // end for
	h1.Move_To_Start ();
	h2.Move_To_Start ();
} // Split

//----------------------------------------------------------------

template <class Item, class Item_Compare>
void Sorting_Machine_2<Item, Item_Compare>::Merge (
         produces Item_List& s,
         consumes Item_List& h1,
         consumes Item_List& h2
		 )
//   pre: s = < > < >  and  h1.left = < >  and  h2.left = < >
//		and  h1.right is sorted  and  h2.right is sorted
//   post: h1 = < > < >  and  h2 = < > < >  and all items in
//		#h1 and #h2 are in s, and s is sorted
{
	h1.Move_To_Finish ();
	h1.Swap_Rights (h2);
	h1.Move_To_Start ();
	s &= h1;
}	// Merge

//----------------------------------------------------------------
// Exported Operations
//----------------------------------------------------------------

template <class Item, class Item_Compare>
Sorting_Machine_2<Item, Item_Compare>::Sorting_Machine_2 ()
{
	rep->insertion_phase = true;
}	// Sorting_Machine_2

//----------------------------------------------------------------

template <class Item, class Item_Compare>
Sorting_Machine_2<Item, Item_Compare>::~Sorting_Machine_2 ()
{
}	// ~Sorting_Machine_2

//----------------------------------------------------------------

template <class Item, class Item_Compare>
void Sorting_Machine_2<Item, Item_Compare>::operator &= (Sorting_Machine_2& rhs)
{
	rep &= rhs.rep;
} 	// operator &=

//----------------------------------------------------------------

template <class Item, class Item_Compare>
void Sorting_Machine_2<Item, Item_Compare>::Clear (void)
{
	rep->item_keeper.Clear ();
	rep->insertion_phase = true;
}	// Clear

//----------------------------------------------------------------

template <class Item, class Item_Compare>
void Sorting_Machine_2<Item, Item_Compare>::Insert (Item& x)
{
	rep->item_keeper.Add_Right (x);
}	// Insert

//----------------------------------------------------------------

template <class Item, class Item_Compare>
void Sorting_Machine_2<Item, Item_Compare>::Change_To_Extraction_Phase (void)
{
	Merge_Sort (rep->item_keeper);
	rep->insertion_phase = false;
}	// Change_To_Extraction_Phase

//----------------------------------------------------------------

template <class Item, class Item_Compare>
void Sorting_Machine_2<Item, Item_Compare>::Extract (Item& x)
{
	rep->item_keeper.Remove_Right (x);
}	// Extract

//----------------------------------------------------------------

template <class Item, class Item_Compare>
Integer Sorting_Machine_2<Item, Item_Compare>::Size (void)
{
   return (rep->item_keeper.Right_Size ());
}	// Size

//----------------------------------------------------------------

template <class Item, class Item_Compare>
Boolean Sorting_Machine_2<Item, Item_Compare>::Is_In_Insertion_Phase (void)
{
   return (rep->insertion_phase);
}	// Is_In_Insertion_Phase