externalsort.h

tools.03b.zip

// 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:
//    [e-mail]

#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 */