/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 */

#include "sci/console.h"
#include "sci/resource.h"
#include "sci/engine/kernel.h"
#include "sci/engine/selector.h"
#include "sci/engine/state.h"
#include "sci/graphics/celobj32.h"
#include "sci/graphics/frameout.h"
#include "sci/graphics/screen_item32.h"
#include "sci/graphics/view.h"

namespace Sci {
#pragma mark ScreenItem

uint16 ScreenItem::_nextObjectId = 20000;

ScreenItem::ScreenItem(const reg_t object) :
_celObj(nullptr),
_object(object),
_pictureId(-1),
_created(g_sci->_gfxFrameout->getScreenCount()),
_updated(0),
_deleted(0),
_mirrorX(false) {
	SegManager *segMan = g_sci->getEngineState()->_segMan;

	setFromObject(segMan, object, true, true);
	_plane = readSelector(segMan, object, SELECTOR(plane));
}

ScreenItem::ScreenItem(const reg_t plane, const CelInfo32 &celInfo) :
_plane(plane),
_useInsetRect(false),
_z(0),
_celInfo(celInfo),
_celObj(nullptr),
_fixedPriority(false),
_position(0, 0),
_object(make_reg(0, _nextObjectId++)),
_pictureId(-1),
_created(g_sci->_gfxFrameout->getScreenCount()),
_updated(0),
_deleted(0),
_mirrorX(false) {}

ScreenItem::ScreenItem(const reg_t plane, const CelInfo32 &celInfo, const Common::Rect &rect) :
_plane(plane),
_useInsetRect(false),
_z(0),
_celInfo(celInfo),
_celObj(nullptr),
_fixedPriority(false),
_position(rect.left, rect.top),
_object(make_reg(0, _nextObjectId++)),
_pictureId(-1),
_created(g_sci->_gfxFrameout->getScreenCount()),
_updated(0),
_deleted(0),
_mirrorX(false) {
	if (celInfo.type == kCelTypeColor) {
		_insetRect = rect;
	}
}

ScreenItem::ScreenItem(const reg_t plane, const CelInfo32 &celInfo, const Common::Point &position, const ScaleInfo &scaleInfo) :
_plane(plane),
_scale(scaleInfo),
_useInsetRect(false),
_z(0),
_celInfo(celInfo),
_celObj(nullptr),
_fixedPriority(false),
_position(position),
_object(make_reg(0, _nextObjectId++)),
_pictureId(-1),
_created(g_sci->_gfxFrameout->getScreenCount()),
_updated(0),
_deleted(0),
_mirrorX(false) {}

ScreenItem::ScreenItem(const ScreenItem &other) :
_plane(other._plane),
_scale(other._scale),
_useInsetRect(other._useInsetRect),
_celInfo(other._celInfo),
_celObj(nullptr),
_object(other._object),
_mirrorX(other._mirrorX),
_scaledPosition(other._scaledPosition),
_screenRect(other._screenRect) {
	if (other._useInsetRect) {
		_insetRect = other._insetRect;
	}
}

void ScreenItem::operator=(const ScreenItem &other) {
	// NOTE: The original engine did not check for differences in `_celInfo`
	// to clear `_celObj` here; instead, it unconditionally set `_celInfo`,
	// didn't clear `_celObj`, and did hacky stuff in `kIsOnMe` to avoid
	// testing a mismatched `_celObj`. See `GfxFrameout::kernelIsOnMe` for
	// more detail.
	if (_celInfo != other._celInfo) {
		_celInfo = other._celInfo;
		delete _celObj;
		_celObj = nullptr;
	}

	_screenRect = other._screenRect;
	_mirrorX = other._mirrorX;
	_useInsetRect = other._useInsetRect;
	if (other._useInsetRect) {
		_insetRect = other._insetRect;
	}
	_scale = other._scale;
	_scaledPosition = other._scaledPosition;
}

ScreenItem::~ScreenItem() {
	delete _celObj;
}

void ScreenItem::init() {
	_nextObjectId = 20000;
}

void ScreenItem::setFromObject(SegManager *segMan, const reg_t object, const bool updateCel, const bool updateBitmap) {
	_position.x = readSelectorValue(segMan, object, SELECTOR(x));
	_position.y = readSelectorValue(segMan, object, SELECTOR(y));
	_scale.x = readSelectorValue(segMan, object, SELECTOR(scaleX));
	_scale.y = readSelectorValue(segMan, object, SELECTOR(scaleY));
	_scale.max = readSelectorValue(segMan, object, SELECTOR(maxScale));
	_scale.signal = (ScaleSignals32)(readSelectorValue(segMan, object, SELECTOR(scaleSignal)) & 3);

	if (updateCel) {
		_celInfo.resourceId = (GuiResourceId)readSelectorValue(segMan, object, SELECTOR(view));
		_celInfo.loopNo = readSelectorValue(segMan, object, SELECTOR(loop));
		_celInfo.celNo = readSelectorValue(segMan, object, SELECTOR(cel));

		if (_celInfo.resourceId <= kPlanePic) {
			// TODO: Enhance GfxView or ResourceManager to allow
			// metadata for resources to be retrieved once, from a
			// single location
			Resource *view = g_sci->getResMan()->findResource(ResourceId(kResourceTypeView, _celInfo.resourceId), false);
			if (!view) {
				error("Failed to load resource %d", _celInfo.resourceId);
			}

			// NOTE: +2 because the header size field itself is excluded from
			// the header size in the data
			const uint16 headerSize = READ_SCI11ENDIAN_UINT16(view->data) + 2;
			const uint8 loopCount = view->data[2];
			const uint8 loopSize = view->data[12];

			if (_celInfo.loopNo >= loopCount) {
				const int maxLoopNo = loopCount - 1;
				_celInfo.loopNo = maxLoopNo;
				writeSelectorValue(segMan, object, SELECTOR(loop), maxLoopNo);
			}

			byte *loopData = view->data + headerSize + (_celInfo.loopNo * loopSize);
			const int8 seekEntry = loopData[0];
			if (seekEntry != -1) {
				loopData = view->data + headerSize + (seekEntry * loopSize);
			}
			const uint8 celCount = loopData[2];
			if (_celInfo.celNo >= celCount) {
				const int maxCelNo = celCount - 1;
				_celInfo.celNo = maxCelNo;
				writeSelectorValue(segMan, object, SELECTOR(cel), maxCelNo);
			}
		}
	}

	if (updateBitmap) {
		const reg_t bitmap = readSelector(segMan, object, SELECTOR(bitmap));
		if (!bitmap.isNull()) {
			_celInfo.bitmap = bitmap;
			_celInfo.type = kCelTypeMem;
		} else {
			_celInfo.bitmap = NULL_REG;
			_celInfo.type = kCelTypeView;
		}
	}

	if (updateCel || updateBitmap) {
		delete _celObj;
		_celObj = nullptr;
	}

	if (readSelectorValue(segMan, object, SELECTOR(fixPriority))) {
		_fixedPriority = true;
		_priority = readSelectorValue(segMan, object, SELECTOR(priority));
	} else {
		_fixedPriority = false;
		writeSelectorValue(segMan, object, SELECTOR(priority), _position.y);
	}

	_z = readSelectorValue(segMan, object, SELECTOR(z));
	_position.y -= _z;

	if (readSelectorValue(segMan, object, SELECTOR(useInsetRect))) {
		_useInsetRect = true;
		_insetRect.left = readSelectorValue(segMan, object, SELECTOR(inLeft));
		_insetRect.top = readSelectorValue(segMan, object, SELECTOR(inTop));
		_insetRect.right = readSelectorValue(segMan, object, SELECTOR(inRight)) + 1;
		_insetRect.bottom = readSelectorValue(segMan, object, SELECTOR(inBottom)) + 1;
	} else {
		_useInsetRect = false;
	}

	segMan->getObject(object)->clearInfoSelectorFlag(kInfoFlagViewVisible);
}

void ScreenItem::calcRects(const Plane &plane) {
	const int16 scriptWidth = g_sci->_gfxFrameout->getCurrentBuffer().scriptWidth;
	const int16 scriptHeight = g_sci->_gfxFrameout->getCurrentBuffer().scriptHeight;
	const int16 screenWidth = g_sci->_gfxFrameout->getCurrentBuffer().screenWidth;
	const int16 screenHeight = g_sci->_gfxFrameout->getCurrentBuffer().screenHeight;

	const CelObj &celObj = getCelObj();

	Common::Rect celRect(celObj._width, celObj._height);
	if (_useInsetRect) {
		if (_insetRect.intersects(celRect)) {
			_insetRect.clip(celRect);
		} else {
			_insetRect = Common::Rect();
		}
	} else {
		_insetRect = celRect;
	}

	Ratio scaleX, scaleY;

	if (_scale.signal & kScaleSignalDoScaling32) {
		if (_scale.signal & kScaleSignalUseVanishingPoint) {
			int num = _scale.max * (_position.y - plane._vanishingPoint.y) / (scriptWidth - plane._vanishingPoint.y);
			scaleX = Ratio(num, 128);
			scaleY = Ratio(num, 128);
		} else {
			scaleX = Ratio(_scale.x, 128);
			scaleY = Ratio(_scale.y, 128);
		}
	}

	if (scaleX.getNumerator() && scaleY.getNumerator()) {
		_screenItemRect = _insetRect;

		const Ratio celToScreenX(screenWidth, celObj._scaledWidth);
		const Ratio celToScreenY(screenHeight, celObj._scaledHeight);

		// Cel may use a coordinate system that is not the same size as the
		// script coordinate system (usually this means high-resolution
		// pictures with low-resolution scripts)
		if (celObj._scaledWidth != kLowResX || celObj._scaledHeight != kLowResY) {
			// high resolution coordinates

			if (_useInsetRect) {
				const Ratio scriptToCelX(celObj._scaledWidth, scriptWidth);
				const Ratio scriptToCelY(celObj._scaledHeight, scriptHeight);
				mulru(_screenItemRect, scriptToCelX, scriptToCelY, 0);

				if (_screenItemRect.intersects(celRect)) {
					_screenItemRect.clip(celRect);
				} else {
					_screenItemRect = Common::Rect();
				}
			}

			int displaceX = celObj._displace.x;
			int displaceY = celObj._displace.y;

			if (_mirrorX != celObj._mirrorX && _celInfo.type != kCelTypePic) {
				displaceX = celObj._width - celObj._displace.x - 1;
			}

			if (!scaleX.isOne() || !scaleY.isOne()) {
				mulinc(_screenItemRect, scaleX, scaleY);
				displaceX = (displaceX * scaleX).toInt();
				displaceY = (displaceY * scaleY).toInt();
			}

			mulinc(_screenItemRect, celToScreenX, celToScreenY);
			displaceX = (displaceX * celToScreenX).toInt();
			displaceY = (displaceY * celToScreenY).toInt();

			const Ratio scriptToScreenX = Ratio(screenWidth, scriptWidth);
			const Ratio scriptToScreenY = Ratio(screenHeight, scriptHeight);

			if (/* TODO: dword_C6288 */ false && _celInfo.type == kCelTypePic) {
				_scaledPosition.x = _position.x;
				_scaledPosition.y = _position.y;
			} else {
				_scaledPosition.x = (_position.x * scriptToScreenX).toInt() - displaceX;
				_scaledPosition.y = (_position.y * scriptToScreenY).toInt() - displaceY;
			}

			_screenItemRect.translate(_scaledPosition.x, _scaledPosition.y);

			if (_mirrorX != celObj._mirrorX && _celInfo.type == kCelTypePic) {
				Common::Rect temp(_insetRect);

				if (!scaleX.isOne()) {
					mulinc(temp, scaleX, Ratio());
				}

				mulinc(temp, celToScreenX, Ratio());

				CelObjPic *celObjPic = dynamic_cast<CelObjPic *>(_celObj);
				if (celObjPic == nullptr) {
					error("Expected a CelObjPic");
				}
				temp.translate((celObjPic->_relativePosition.x * scriptToScreenX).toInt() - displaceX, 0);

				// TODO: This is weird.
				int deltaX = plane._planeRect.width() - temp.right - 1 - temp.left;

				_scaledPosition.x += deltaX;
				_screenItemRect.translate(deltaX, 0);
			}

			_scaledPosition.x += plane._planeRect.left;
			_scaledPosition.y += plane._planeRect.top;
			_screenItemRect.translate(plane._planeRect.left, plane._planeRect.top);

			_ratioX = scaleX * celToScreenX;
			_ratioY = scaleY * celToScreenY;
		} else {
			// low resolution coordinates

			int displaceX = celObj._displace.x;
			if (_mirrorX != celObj._mirrorX && _celInfo.type != kCelTypePic) {
				displaceX = celObj._width - celObj._displace.x - 1;
			}

			if (!scaleX.isOne() || !scaleY.isOne()) {
				mulinc(_screenItemRect, scaleX, scaleY);
				// TODO: This was in the original code, baked into the
				// multiplication though it is not immediately clear
				// why this is the only one that reduces the BR corner
				_screenItemRect.right -= 1;
				_screenItemRect.bottom -= 1;
			}

			_scaledPosition.x = _position.x - (displaceX * scaleX).toInt();
			_scaledPosition.y = _position.y - (celObj._displace.y * scaleY).toInt();
			_screenItemRect.translate(_scaledPosition.x, _scaledPosition.y);

			if (_mirrorX != celObj._mirrorX && _celInfo.type == kCelTypePic) {
				Common::Rect temp(_insetRect);

				if (!scaleX.isOne()) {
					mulinc(temp, scaleX, Ratio());
					temp.right -= 1;
				}

				CelObjPic *celObjPic = dynamic_cast<CelObjPic *>(_celObj);
				if (celObjPic == nullptr) {
					error("Expected a CelObjPic");
				}
				temp.translate(celObjPic->_relativePosition.x - (displaceX * scaleX).toInt(), celObjPic->_relativePosition.y - (celObj._displace.y * scaleY).toInt());

				// TODO: This is weird.
				int deltaX = plane._gameRect.width() - temp.right - 1 - temp.left;

				_scaledPosition.x += deltaX;
				_screenItemRect.translate(deltaX, 0);
			}

			_scaledPosition.x += plane._gameRect.left;
			_scaledPosition.y += plane._gameRect.top;
			_screenItemRect.translate(plane._gameRect.left, plane._gameRect.top);

			if (celObj._scaledWidth != screenWidth || celObj._scaledHeight != screenHeight) {
				mulru(_scaledPosition, celToScreenX, celToScreenY);
				mulru(_screenItemRect, celToScreenX, celToScreenY, 1);
			}

			_ratioX = scaleX * celToScreenX;
			_ratioY = scaleY * celToScreenY;
		}

		_screenRect = _screenItemRect;

		if (_screenRect.intersects(plane._screenRect)) {
			_screenRect.clip(plane._screenRect);
		} else {
			_screenRect.right = 0;
			_screenRect.bottom = 0;
			_screenRect.left = 0;
			_screenRect.top = 0;
		}

		if (!_fixedPriority) {
			_priority = _z + _position.y;
		}
	} else {
		_screenRect.left = 0;
		_screenRect.top = 0;
		_screenRect.right = 0;
		_screenRect.bottom = 0;
	}
}

CelObj &ScreenItem::getCelObj() const {
	if (_celObj == nullptr) {
		switch (_celInfo.type) {
			case kCelTypeView:
				_celObj = new CelObjView(_celInfo.resourceId, _celInfo.loopNo, _celInfo.celNo);
			break;
			case kCelTypePic:
				error("Internal error, pic screen item with no cel.");
			break;
			case kCelTypeMem:
				_celObj = new CelObjMem(_celInfo.bitmap);
			break;
			case kCelTypeColor:
				_celObj = new CelObjColor(_celInfo.color, _insetRect.width(), _insetRect.height());
			break;
		}
	}

	return *_celObj;
}

void ScreenItem::printDebugInfo(Console *con) const {
	con->debugPrintf("%04x:%04x (%s), prio %d, x %d, y %d, z: %d, scaledX: %d, scaledY: %d flags: %d\n",
		_object.getSegment(), _object.getOffset(),
		g_sci->getEngineState()->_segMan->getObjectName(_object),
		_priority,
		_position.x,
		_position.y,
		_z,
		_scaledPosition.x,
		_scaledPosition.y,
		_created | (_updated << 1) | (_deleted << 2)
	);
	con->debugPrintf("    screen rect (%d, %d, %d, %d)\n", PRINT_RECT(_screenRect));
	if (_useInsetRect) {
		con->debugPrintf("    inset rect: (%d, %d, %d, %d)\n", PRINT_RECT(_insetRect));
	}

	Common::String celType;
	switch (_celInfo.type) {
		case kCelTypePic:
			celType = "pic";
			break;
		case kCelTypeView:
			celType = "view";
			break;
		case kCelTypeColor:
			celType = "color";
			break;
		case kCelTypeMem:
			celType = "mem";
			break;
	}

	con->debugPrintf("    type: %s, res %d, loop %d, cel %d, bitmap %04x:%04x, color: %d\n",
		celType.c_str(),
		_celInfo.resourceId,
		_celInfo.loopNo,
		_celInfo.celNo,
		PRINT_REG(_celInfo.bitmap),
		_celInfo.color
	);
	if (_celObj != nullptr) {
		con->debugPrintf("    width %d, height %d, scaledWidth %d, scaledHeight %d\n",
			_celObj->_width,
			_celObj->_height,
			_celObj->_scaledWidth,
			_celObj->_scaledHeight
		);
	}
}

void ScreenItem::update(const reg_t object) {
	SegManager *segMan = g_sci->getEngineState()->_segMan;

	const GuiResourceId view = readSelectorValue(segMan, object, SELECTOR(view));
	const int16 loopNo = readSelectorValue(segMan, object, SELECTOR(loop));
	const int16 celNo = readSelectorValue(segMan, object, SELECTOR(cel));

	const bool updateCel = (
		_celInfo.resourceId != view ||
		_celInfo.loopNo != loopNo ||
		_celInfo.celNo != celNo
	);

	const bool updateBitmap = !readSelector(segMan, object, SELECTOR(bitmap)).isNull();

	setFromObject(segMan, object, updateCel, updateBitmap);

	if (!_created) {
		_updated = g_sci->_gfxFrameout->getScreenCount();
	}

	_deleted = 0;
}

void ScreenItem::update() {
	Plane *plane = g_sci->_gfxFrameout->getPlanes().findByObject(_plane);
	if (plane == nullptr) {
		error("ScreenItem::update: Invalid plane %04x:%04x", PRINT_REG(_plane));
	}

	if (plane->_screenItemList.findByObject(_object) == nullptr) {
		error("ScreenItem::update: %04x:%04x not in plane %04x:%04x", PRINT_REG(_object), PRINT_REG(_plane));
	}

	if (!_created) {
		_updated = g_sci->_gfxFrameout->getScreenCount();
	}
	_deleted = 0;

	delete _celObj;
	_celObj = nullptr;
}

// TODO: This code is quite similar to calcRects, so try to deduplicate
// if possible
Common::Rect ScreenItem::getNowSeenRect(const Plane &plane) const {
	CelObj &celObj = getCelObj();

	Common::Rect celObjRect(celObj._width, celObj._height);
	Common::Rect nsRect;

	if (_useInsetRect) {
		// TODO: This is weird. Checking to see if the inset rect is
		// fully inside the bounds of the celObjRect, and then
		// clipping to the celObjRect, is pretty useless.
		if (_insetRect.right > 0 && _insetRect.bottom > 0 && _insetRect.left < celObj._width && _insetRect.top < celObj._height) {
			nsRect = _insetRect;
			nsRect.clip(celObjRect);
		} else {
			nsRect = Common::Rect();
		}
	} else {
		nsRect = celObjRect;
	}

	const uint16 scriptWidth = g_sci->_gfxFrameout->getCurrentBuffer().scriptWidth;
	const uint16 scriptHeight = g_sci->_gfxFrameout->getCurrentBuffer().scriptHeight;

	Ratio scaleX, scaleY;
	if (_scale.signal & kScaleSignalDoScaling32) {
		if (_scale.signal & kScaleSignalUseVanishingPoint) {
			int num = _scale.max * (_position.y - plane._vanishingPoint.y) / (scriptWidth - plane._vanishingPoint.y);
			scaleX = Ratio(num, 128);
			scaleY = Ratio(num, 128);
		} else {
			scaleX = Ratio(_scale.x, 128);
			scaleY = Ratio(_scale.y, 128);
		}
	}

	if (scaleX.getNumerator() == 0 || scaleY.getNumerator() == 0) {
		return Common::Rect();
	}

	int16 displaceX = celObj._displace.x;
	int16 displaceY = celObj._displace.y;

	if (_mirrorX != celObj._mirrorX && _celInfo.type != kCelTypePic) {
		displaceX = celObj._width - displaceX - 1;
	}

	if (celObj._scaledWidth != kLowResX || celObj._scaledHeight != kLowResY) {
		// high resolution coordinates

		if (_useInsetRect) {
			Ratio scriptToCelX(celObj._scaledWidth, scriptWidth);
			Ratio scriptToCelY(celObj._scaledHeight, scriptHeight);
			mulru(nsRect, scriptToCelX, scriptToCelY, 0);

			// TODO: This is weird. Checking to see if the inset rect is
			// fully inside the bounds of the celObjRect, and then
			// clipping to the celObjRect, is pretty useless.
			if (nsRect.right > 0 && nsRect.bottom > 0 && nsRect.left < celObj._width && nsRect.top < celObj._height) {
				nsRect.clip(celObjRect);
			} else {
				nsRect = Common::Rect();
			}
		}

		if (!scaleX.isOne() || !scaleY.isOne()) {
			mulinc(nsRect, scaleX, scaleY);
			// TODO: This was in the original code, baked into the
			// multiplication though it is not immediately clear
			// why this is the only one that reduces the BR corner
			nsRect.right -= 1;
			nsRect.bottom -= 1;
		}

		Ratio celToScriptX(scriptWidth, celObj._scaledWidth);
		Ratio celToScriptY(scriptHeight, celObj._scaledHeight);

		displaceX = (displaceX * scaleX * celToScriptX).toInt();
		displaceY = (displaceY * scaleY * celToScriptY).toInt();

		mulinc(nsRect, celToScriptX, celToScriptY);
		nsRect.translate(_position.x - displaceX, _position.y - displaceY);
	} else {
		// low resolution coordinates

		if (!scaleX.isOne() || !scaleY.isOne()) {
			mulinc(nsRect, scaleX, scaleY);
			// TODO: This was in the original code, baked into the
			// multiplication though it is not immediately clear
			// why this is the only one that reduces the BR corner
			nsRect.right -= 1;
			nsRect.bottom -= 1;
		}

		displaceX = (displaceX * scaleX).toInt();
		displaceY = (displaceY * scaleY).toInt();
		nsRect.translate(_position.x - displaceX, _position.y - displaceY);

		if (_mirrorX != celObj._mirrorX && _celInfo.type != kCelTypePic) {
			nsRect.translate(plane._gameRect.width() - nsRect.width(), 0);
		}
	}

	return nsRect;
}

#pragma mark -
#pragma mark ScreenItemList
ScreenItem *ScreenItemList::findByObject(const reg_t object) const {
	const_iterator screenItemIt = Common::find_if(begin(), end(), FindByObject<ScreenItem *>(object));

	if (screenItemIt == end()) {
		return nullptr;
	}

	return *screenItemIt;
}
void ScreenItemList::sort() {
	if (size() < 2) {
		return;
	}

	for (size_type i = 0; i < size(); ++i) {
		_unsorted[i] = i;
	}

	for (size_type i = size() - 1; i > 0; --i) {
		bool swap = false;

		for (size_type j = 0; j < i; ++j)  {
			value_type &a = operator[](j);
			value_type &b = operator[](j + 1);

			if (a == nullptr || *a > *b) {
				SWAP(a, b);
				SWAP(_unsorted[j], _unsorted[j + 1]);
				swap = true;
			}
		}

		if (!swap) {
			break;
		}
	}
}
void ScreenItemList::unsort() {
	if (size() < 2) {
		return;
	}

	for (size_type i = 0; i < size(); ++i) {
		while (_unsorted[i] != i) {
			SWAP(operator[](_unsorted[i]), operator[](i));
			SWAP(_unsorted[_unsorted[i]], _unsorted[i]);
		}
	}
}

} // End of namespace Sci