// Tools Library//// Copyright (C) 2004  Navel Ltd.//// This library is free software; you can redistribute it and/or// modify it under the terms of the GNU Lesser General Public// License as published by the Free Software Foundation; either// version 2.1 of the License, or (at your option) any later version.//// This library is distributed in the hope that it will be useful,// but WITHOUT ANY WARRANTY; without even the implied warranty of// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU// Lesser General Public License for more details.//// You should have received a copy of the GNU Lesser General Public// License along with this library; if not, write to the Free Software// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA//// Contact information://  Mailing address://    Marios Hadjieleftheriou//    University of California, Riverside//    Department of Computer Science//    Surge Building, Room 310//    Riverside, CA 92521////  Email://    marioh@cs.ucr.edu
#ifndef __tools_external_sort_h
#define __tools_external_sort_h

namespace Tools
{
	class ExternalSort : public IObjectStream
	{
	public:
		ExternalSort(Tools::IObjectStream& source, unsigned long bufferSize);
		ExternalSort(Tools::IObjectStream& source, Tools::IObjectComparator& comp, unsigned long bufferSize);
		virtual ~ExternalSort();

		virtual IObject* getNext();
		virtual bool hasNext();
		virtual unsigned long size() throw (NotSupportedException);
		virtual bool rewind() throw (NotSupportedException);

	private:
		class PQEntry
		{
		public:
			PQEntry(SmartPointer<ISerializable>& r, IObjectComparator* pComp, SmartPointer<TemporaryFile>& f);

			struct ascendingComparator: public std::binary_function<SmartPointer<PQEntry>, SmartPointer<PQEntry>, bool>
			{
				bool operator()(SmartPointer<PQEntry> x, SmartPointer<PQEntry> y) const;
			};

			SmartPointer<ISerializable> m_spRecord;
			IObjectComparator* m_pComp;
			SmartPointer<TemporaryFile> m_spFile;
		};

		void initializeRuns(std::deque<SmartPointer<TemporaryFile> >& runs);
		void mergeRuns();

		Tools::IObjectStream* m_pExternalSource;
		unsigned long m_cMaxBufferSize;
		SmartPointer<IObject> m_spTemplateRecord;
		SmartPointer<TemporaryFile> m_spSortedFile;
		std::priority_queue<SmartPointer<PQEntry>, std::vector<SmartPointer<PQEntry> >, PQEntry::ascendingComparator> m_buffer;
		bool m_bFitsInBuffer;
		unsigned long m_cNumberOfSortedRecords;
		ISerializable* m_pNextRecord;
		bool m_bCustomComp;
		IObjectComparator* m_pComp;
		#ifndef NDEBUG
		unsigned long m_cReturnedRecords;
		#endif
	}; // ExternalSort
}

#endif /* __tools_external_sort_h */