CListCtrl and sorting rows

#include "stdafx.h"

#include "CListCtrl_StableSort.h"

#include <algorithm>

BEGIN_MESSAGE_MAP(CListCtrl_StableSort, CListCtrl)
	ON_NOTIFY_REFLECT_EX(LVN_GETDISPINFO, OnGetDispInfo)	// Text Callback
	ON_NOTIFY_REFLECT_EX(LVN_COLUMNCLICK, OnHeaderClick)	// Column Click
END_MESSAGE_MAP()

BOOL CListCtrl_StableSort::OnGetDispInfo(NMHDR* pNMHDR, LRESULT* pResult)
{
	NMLVDISPINFO* pNMW = reinterpret_cast<NMLVDISPINFO*>(pNMHDR);
	int nItem = pNMW->item.iItem;
	int nSubItem = pNMW->item.iSubItem;

	if (nItem< 0 || nItem >= GetItemCount())
		return FALSE;	// requesting invalid item

	if (nSubItem < 0 || nSubItem >= GetHeaderCtrl()->GetItemCount())
		return FALSE;	// requesting invalid column

	int columnData = GetColumnData(nSubItem);
	size_t itemData = (size_t)GetItemData(nItem);

	if(pNMW->item.mask & LVIF_TEXT)
	{
		// Request text
		const string& result = m_DataModel.GetCellText(itemData, columnData);
		_tcsncpy(pNMW->item.pszText, result.c_str(), pNMW->item.cchTextMax);
	}

	return FALSE;	// Let parent-dialog get chance
}

namespace {
	bool AscSortFunc(const pair<string,size_t>& left, const pair<string,size_t>& right)
	{
		return left.first < right.first;
	}
	bool DescSortFunc(const pair<string,size_t>& left, const pair<string,size_t>& right)
	{
		return right.first < left.first;
	}
}

bool CListCtrl_StableSort::SortColumn(int columnIndex, bool ascending)
{
	if (GetItemCount()!=m_DataModel.GetRowIds())
		return false;

	int columnData = GetColumnData(columnIndex);

	// Sorting optimized for a datamodel where lookup is slow
	//	- Uses more memory during sort, because it takes a copy of an entire column
	//	- Even faster if one can iterate over the datamodel without lookup
	vector< pair<string,size_t> > entireColumn;
	if (m_StableSort)
	{
		// Extract original order from the list-control
		vector< pair<size_t,int> > orignalOrder;
		orignalOrder.reserve(GetItemCount());
		for(int nItem = 0; nItem < GetItemCount(); ++nItem)
		{
			orignalOrder.push_back( make_pair((size_t)GetItemData(nItem), nItem) );
		}
		sort(orignalOrder.begin(), orignalOrder.end());

		// Extract entire column from datamodel and place in original order
		entireColumn.resize( m_DataModel.GetRowIds() );
		int listPos = 0;
		for(size_t rowId = 0; rowId < m_DataModel.GetRowIds(); ++rowId)
		{
			entireColumn[orignalOrder[listPos++].second] = make_pair(m_DataModel.GetCellText(rowId,columnData),rowId);
		}

		// Sort entire column, while trying to preserve original order
		if (ascending)
			stable_sort(entireColumn.begin(), entireColumn.end(), AscSortFunc);
		else
			stable_sort(entireColumn.begin(), entireColumn.end(), DescSortFunc);
	}
	else
	{
		// Extract entire column from datamodel
		entireColumn.reserve( m_DataModel.GetRowIds() );
		for(size_t rowId = 0; rowId < m_DataModel.GetRowIds(); ++rowId)
		{
			entireColumn.push_back( make_pair(m_DataModel.GetCellText(rowId,columnData),rowId) );
		}

		// Sort entire column
		if (ascending)
			sort(entireColumn.begin(), entireColumn.end(), AscSortFunc);
		else
			sort(entireColumn.begin(), entireColumn.end(), DescSortFunc);
	}

	// Update list-control with new column-order
	for(int nItem = 0; nItem < GetItemCount(); ++nItem)
	{
		SetItemData(nItem, entireColumn[nItem].second);
	}

	return true;
}

void CListCtrl_StableSort::LoadData()
{
	if (GetHeaderCtrl()->GetItemCount()==0)
	{
		// Create Columns
		for(int col = 0; col < m_DataModel.GetColCount() ; ++col)
		{
			const string& title = m_DataModel.GetColTitle(col);
			VERIFY( InsertColumn(col, title.c_str(), LVCFMT_LEFT, 100, col) != -1);
		}
	}
	else
	{
		// Empty list-control and force refresh
		DeleteAllItems();
		ResetSortOrder();
		Invalidate();
		UpdateWindow();
	}

	// Insert data with callback
	SetRedraw(FALSE);	// Disable redraw as InsertItem becomes so much faster
	int nItem = 0;
	for(size_t rowId = 0; rowId < m_DataModel.GetRowIds() ; ++rowId)
	{
		nItem = InsertItem(++nItem, "");	// Fastest to insert at the end
		VERIFY(nItem!=-1);
		VERIFY( SetItemData(nItem, rowId) );
		for(int col = 0; col < m_DataModel.GetColCount() ; ++col)
		{
			VERIFY( SetItemText(nItem, col, LPSTR_TEXTCALLBACK) );
		}
	}
	SetRedraw(TRUE);
	Invalidate();
	UpdateWindow();
}