Revision 64 (by gdshaw@RISCPKG.ORG, 2007/05/21 05:44:33) Disabled exceptions and enabled optimisation to reduce code size.
// This file is part of the free Filer module for RISC OS.
// Copyright � 2007 Graham Shaw.
// Redistribution and modification are permitted under the terms of the
// GNU General Public License (version 2 or any later version).

#include <new>

#include "window.h"
#include "window_table.h"

window_table::window_table(size_type capacity):
	_size(0),
	_capacity(capacity),
	_nodes(new(std::nothrow) node[_capacity])
{}

void window_table::insert(window& w)
{
	// Ensure that table has sufficient capacity.
	if (_size==_capacity)
	{
		_capacity*=2;
		node* nodes=new(std::nothrow) node[_capacity];
		for (size_type i=0;i!=_size;++i)
		{
			nodes[i]=_nodes[i];
		}
		delete[] _nodes;
		_nodes=nodes;
	}

	// Search for insertion point.
	wimp_w handle=w.handle();
	size_type f=lower_bound(handle);

	// Make space for new node.
	for (size_type i=_size;i!=f;--i)
	{
		_nodes[i]=_nodes[i-1];
	}
	++_size;

	// Insert node.
	_nodes[f].handle=handle;
	_nodes[f].w=&w;
}

void window_table::erase(window& w)
{
	// Search for window.
	size_type f=lower_bound(w.handle());

	// Check whether window has been found.
	if ((f!=_size)&&(_nodes[f].w==&w))
	{
		// If found then delete node.
		--_size;
		for (size_type i=f;i!=_size;++i)
		{
			_nodes[i]=_nodes[i+1];
		}
	}
}

window* window_table::find(wimp_w handle)
{
	// Search for handle.
	size_type f=lower_bound(handle);

	// Return window if handle found, otherwise return 0.
	window* w=(f!=_size)?_nodes[f].w:0;
	return (w&&(w->handle()==handle))?w:0;
}

window_table::size_type window_table::lower_bound(wimp_w handle)
{
	// Initially, it is known only that the result lies in the range
	// 0 to _size inclusive.
	size_type lbound=0;
	size_type ubound=_size;

	// Repeat until the result is known exactly.
	while (ubound!=lbound)
	{
		// Probe at centre of range, rounding down (lbound<=i<ubound).
		size_type i=(lbound+ubound)/2;

		// If required handle is higher than the handle at i then the
		// result must be greater than i so adjust lbound, otherwise
		// the result must be less than or equal to i so adjust ubound.
		// Either way the range will be narrowed by this operation
		// (ensuring that the loop will terminate).
		if (handle>_nodes[i].handle) lbound=i+1;
		else ubound=i;
	}

	// Can return either lbound or ubound, as they should now be equal.
	return lbound;
}