#ifndef __MovableTextOverlay_H__
#define __MovableTextOverlay_H__
 
#include "Ogre.h"
#include "OgreFont.h"
#include "OgreFontManager.h"
 
using namespace Ogre;
 
class MovableTextOverlayAttributes
{
public:
	MovableTextOverlayAttributes(const Ogre::String & name, const Ogre::Camera *cam,
						 const Ogre::String & fontName = "BlueHighway", int charHeight = 16, const Ogre::ColourValue & color = Ogre::ColourValue::White, const Ogre::String & materialName = "");
	~MovableTextOverlayAttributes();
 
	void setFontName(const Ogre::String & fontName);
	void setMaterialName(const Ogre::String & materialName);
	void setColor(const Ogre::ColourValue & color);
	void setCharacterHeight(unsigned int height);
 
	const Ogre::String& getName() const {return mName;}
	const Ogre::Camera* getCamera() const {return mpCam;}
	const Ogre::Font* getFont() const {return mpFont;}
	const Ogre::String& getFontName() const {return mFontName;}
	const Ogre::String& getMaterialName() const {return mMaterialName;}
	const Ogre::ColourValue& getColor() const {return mColor;}
	const Ogre::Real getCharacterHeight() const {return mCharHeight;}
 
	const Ogre::String mName;
	const Ogre::Camera *mpCam;
 
	Ogre::Font* mpFont;
	Ogre::String mFontName;
	Ogre::String mMaterialName;
	Ogre::ColourValue mColor;
	Ogre::Real mCharHeight;
};
 
class MovableTextOverlay {
public:
	MovableTextOverlay(const Ogre::String & name, const Ogre::String & caption,
						const Ogre::MovableObject *mov, MovableTextOverlayAttributes *attrs);
 
	virtual ~MovableTextOverlay();
 
	void setCaption(const Ogre::String & caption);
	void setUpdateFrequency(Ogre::Real updateFrequency) {mUpdateFrequency = updateFrequency;}
	void setAttributes(MovableTextOverlayAttributes *attrs)
	{
		mAttrs = attrs;
		_updateOverlayAttrs();
	}
 
	const Ogre::String&	getName() const {return mName;}
	const Ogre::String&	getCaption() const {return mCaption;}
	const Ogre::Real getUpdateFrequency() const {return mUpdateFrequency;}
	const bool isOnScreen() const {return mOnScreen;}
	const bool isEnabled() const {return mEnabled;}
	const MovableTextOverlayAttributes* getAttributes() const {return mAttrs;}
 
	void enable(bool enable);
	void update(Ogre::Real timeSincelastFrame);
 
	// Needed for RectLayoutManager.
	int getPixelsTop() {return Ogre::OverlayManager::getSingleton().getViewportHeight() * (mpOvContainer->getTop());}
	int getPixelsBottom() {return Ogre::OverlayManager::getSingleton().getViewportHeight() * (mpOvContainer->getTop() + mpOvContainer->getHeight());}
	int getPixelsLeft() {return Ogre::OverlayManager::getSingleton().getViewportWidth() * mpOvContainer->getLeft();}
	int getPixelsRight() {return Ogre::OverlayManager::getSingleton().getViewportWidth() * (mpOvContainer->getLeft() + mpOvContainer->getWidth());}
 
	void setPixelsTop(int px) {mpOvContainer->setTop((Ogre::Real)px / Ogre::OverlayManager::getSingleton().getViewportHeight());}
	// end
 
protected:
	void _computeTextWidth();
	void _updateOverlayAttrs();
	void _getMinMaxEdgesOfTopAABBIn2D(Ogre::Real& MinX, Ogre::Real& MinY, Ogre::Real& MaxX, Ogre::Real& MaxY);
	void _getScreenCoordinates(const Ogre::Vector3& position, Ogre::Real& x, Ogre::Real& y);
 
	const Ogre::String mName;
	const Ogre::MovableObject* mpMov;
 
	Ogre::Overlay* mpOv;
	Ogre::OverlayContainer* mpOvContainer;
	Ogre::OverlayElement* mpOvText;
 
	// true if mpOvContainer is visible, false otherwise
	bool mEnabled;
 
	// true if mTextWidth needs to be recalculated
	bool mNeedUpdate;
 
	// Text width in pixels
	Ogre::Real mTextWidth;
 
	// the Text
	Ogre::String mCaption;
 
	// true if the upper vertices projections of the -MovableObject are on screen
	bool mOnScreen;
 
	// the update frequency in seconds
	// mpOvContainer coordinates get updated each mUpdateFrequency seconds.
	Ogre::Real mUpdateFrequency;
 
	// the Font/Material/Color text attributes
	MovableTextOverlayAttributes *mAttrs;
};
#endif /* __MovableTextOverlay_H__ */

#include <OgreFontManager.h>
#include <OgrePrerequisites.h>
#include "MovableTextOverlay.h"
 
MovableTextOverlay::MovableTextOverlay(const Ogre::String & name, const Ogre::String & caption,
						const Ogre::MovableObject *mov, MovableTextOverlayAttributes *attrs)
: mpMov(mov)
, mpOv(NULL)
, mpOvContainer(NULL)
, mpOvText(NULL)
, mAttrs(attrs)
, mName(name)
, mCaption("")
, mUpdateFrequency(0.01)
, mNeedUpdate(TRUE)
, mOnScreen(FALSE)
, mEnabled(FALSE)
{
	if (name == "")
        Ogre::Exception(Ogre::Exception::ERR_INVALIDPARAMS, "Trying to create MovableTextOverlay without name", "MovableTextOverlay::MovableTextOverlay");
 
    if (caption == "")
        Ogre::Exception(Ogre::Exception::ERR_INVALIDPARAMS, "Trying to create MovableTextOverlay without caption", "MovableTextOverlay::MovableTextOverlay");
 
	if (mAttrs == NULL)
		Ogre::Exception(Ogre::Exception::ERR_INVALIDPARAMS, "Trying to create MovableTextOverlay without Attributes", "MovableTextOverlay::MovableTextOverlay");
/*
    if(Ogre::OverlayManager::getSingleton().getByName(name + "_Ov")) 
    { 
        Ogre::Exception(Ogre::Exception::ERR_INVALIDPARAMS, "Trying to create MovableTextOverlay with a duplicate name", "MovableTextOverlay::MovableTextOverlay");
    }
*/
	// create an overlay that we can use for later
	mpOv = Ogre::OverlayManager::getSingleton().create(name+"_Ov");
	mpOv->hide();
	mpOvContainer = static_cast<Ogre::OverlayContainer*>(Ogre::OverlayManager::getSingleton().createOverlayElement(
              "Panel", name+"_OvC"));
	mpOvContainer->setDimensions(0.0, 0.0);
 
	mpOv->add2D(mpOvContainer);
 
	mpOvText = Ogre::OverlayManager::getSingleton().createOverlayElement("TextArea", name+"_OvTxt");
	mpOvContainer->addChild(mpOvText);
 
	mpOvText->setMetricsMode(Ogre::GMM_RELATIVE);
	mpOvText->setDimensions(1.0, 1.0);
	mpOvText->setMetricsMode(Ogre::GMM_PIXELS);
	mpOvText->setPosition(0, 0);
 
	_updateOverlayAttrs();
 
	setCaption(caption);
}
 
MovableTextOverlay::~MovableTextOverlay()
{
	// overlay cleanup -- Ogre would clean this up at app exit but if your app 
	// tends to create and delete these objects often it's a good idea to do it here.
 
	mpOv->hide();
	Ogre::OverlayManager *overlayManager = Ogre::OverlayManager::getSingletonPtr();
	mpOvContainer->removeChild(mName+"_OvTxt");
	mpOv->remove2D(mpOvContainer);
	overlayManager->destroyOverlayElement(mpOvText);
	overlayManager->destroyOverlayElement(mpOvContainer);
	overlayManager->destroy(mpOv);
}
 
void MovableTextOverlay::setCaption(const Ogre::String & caption)
{
    if (caption != mCaption)
    {
        mCaption = caption;
		mpOvText->setCaption(mCaption);
        mNeedUpdate = true;
    }
}
 
void MovableTextOverlay::_computeTextWidth()
{
	const Font *pFont = mAttrs->getFont();
	mTextWidth = 0;
 
	for(Ogre::String::iterator i = mCaption.begin(); i < mCaption.end();i++)
	{   
		if (*i == 0x0020)
			mTextWidth += pFont->getGlyphAspectRatio(0x0030);
		else
		{
			mTextWidth += pFont->getGlyphAspectRatio(*i);
		}
	}
 
	mTextWidth *= mAttrs->getCharacterHeight();
}
 
void MovableTextOverlay::_getMinMaxEdgesOfTopAABBIn2D(Ogre::Real& MinX, Ogre::Real& MinY, Ogre::Real& MaxX, Ogre::Real& MaxY)
{
	const Ogre::Camera* mpCam = mAttrs->getCamera();
 
	MinX = 0;
	MinY = 0;
	MaxX = 0;
	MaxY = 0;
 
	Ogre::Real X[4];// the 2D dots of the AABB in screencoordinates
	Ogre::Real Y[4];
 
	if (!mpMov->isInScene())
	   return;
 
	const Ogre::AxisAlignedBox &AABB = mpMov->getWorldBoundingBox(true);// the AABB of the target
	const Ogre::Vector3 CornersOfTopAABB[4] = {	AABB.getCorner(AxisAlignedBox::FAR_LEFT_TOP),
										AABB.getCorner(AxisAlignedBox::FAR_RIGHT_TOP),
										AABB.getCorner(AxisAlignedBox::NEAR_LEFT_TOP),
										AABB.getCorner(AxisAlignedBox::NEAR_RIGHT_TOP)};
 
	Ogre::Vector3 CameraPlainNormal = mpCam->getDerivedOrientation().zAxis();//The normal vector of the plaine.this points directly infront of the cam
 
	Ogre::Plane CameraPlain = Plane(CameraPlainNormal,mpCam->getDerivedPosition());//the plaine that devides the space bevor and behin the cam
 
	for (int i = 0; i < 4; i++)
	{
	  X[i] = 0;
	  Y[i] = 0;
 
	  _getScreenCoordinates(CornersOfTopAABB[i],X[i],Y[i]);// transfor into 2d dots
 
 
	  if (CameraPlain.getSide(CornersOfTopAABB[i]) == Plane::NEGATIVE_SIDE)
	  {
 
		 if (i == 0)// accept the first set of values, no matter how bad it might be.
		 {
			MinX = X[i];
			MinY = Y[i];
			MaxX = X[i];
			MaxY = Y[i];
		 }
		 else// now compare if you get "better" values
		 {
			if (MinX > X[i])// get the x minimum
			{
			   MinX = X[i];
			}
			if (MinY > Y[i])// get the y minimum
			{
			   MinY = Y[i];
			}
			if (MaxX < X[i])// get the x maximum
			{
			   MaxX = X[i];
			}
			if (MaxY < Y[i])// get the y maximum
			{
			   MaxY = Y[i];
			}
		 }
	  }
	  else
	  {
		MinX = 0;
		MinY = 0;
		MaxX = 0;
		MaxY = 0;
		break;
	  }
	}
} 
 
void MovableTextOverlay::_getScreenCoordinates(const Ogre::Vector3& position, Ogre::Real& x, Ogre::Real& y)
{
	const Ogre::Camera* mpCam = mAttrs->getCamera();
	Vector3 hcsPosition = mpCam->getProjectionMatrix() * (mpCam->getViewMatrix() * position);
 
	x = 1.0f - ((hcsPosition.x * 0.5f) + 0.5f);// 0 <= x <= 1 // left := 0,right := 1
	y = ((hcsPosition.y * 0.5f) + 0.5f);// 0 <= y <= 1 // bottom := 0,top := 1
}
 
void MovableTextOverlay::enable(bool enable)
{
	if (mEnabled == enable)
		return;
 
	mEnabled = enable;
	if (mEnabled)
		mpOv->show();
	else
		mpOv->hide();
}
 
void MovableTextOverlay::update(Real timeSincelastFrame)
{
	static Real timeTillUpdate = 0;
 
	timeTillUpdate -= timeSincelastFrame;
	if (timeTillUpdate > 0)
		return;
	timeTillUpdate = mUpdateFrequency;
 
	Ogre::Real min_x, max_x, min_y, max_y;
	_getMinMaxEdgesOfTopAABBIn2D(min_x, min_y, max_x, max_y);
 
	if ((min_x>0.0) && (max_x<1.0) && (min_y>0.0) && (max_y<1.0))
	   mOnScreen = true;
	else
	   mOnScreen = false;
 
	if (mNeedUpdate)
	{
		_computeTextWidth();
		mNeedUpdate = false;
	}
 
	Real relTextWidth = mTextWidth / Ogre::OverlayManager::getSingleton().getViewportWidth();
	Real relTextHeight = mAttrs->getCharacterHeight() / Ogre::OverlayManager::getSingleton().getViewportHeight();
 
	mpOvContainer->setPosition(1-(min_x + max_x + relTextWidth)/2, 1-max_y);
	mpOvContainer->setDimensions(relTextWidth, relTextHeight);
}
 
void MovableTextOverlay::_updateOverlayAttrs()
{
	const String &newMatName = mAttrs->getMaterialName();
	const String &oldMatName = mpOvContainer->getMaterialName();
	if (oldMatName != newMatName)
	{
		if (oldMatName.length())
			mpOvContainer->getMaterial()->unload();
 
		if (newMatName.length())
			mpOvContainer->setMaterialName(newMatName);
 
	}
 
	mpOvText->setColour(mAttrs->getColor());
 
	mpOvText->setParameter("font_name", mAttrs->getFontName());
	mpOvText->setParameter("char_height", Ogre::StringConverter::toString(mAttrs->getCharacterHeight()));
	mpOvText->setParameter("horz_align", "left");
	mpOvText->setParameter("vert_align", "top");
}
 
 
MovableTextOverlayAttributes::MovableTextOverlayAttributes(const Ogre::String & name, const Ogre::Camera *cam,
						 const Ogre::String & fontName, int charHeight, const Ogre::ColourValue & color, const Ogre::String & materialName)
: mpCam(cam)
, mpFont(NULL)
, mName(name)
, mFontName("")
, mMaterialName("")
, mCharHeight(charHeight)
, mColor(ColourValue::ZERO)
{
	if (fontName.length() == 0)
        Ogre::Exception(Ogre::Exception::ERR_INVALIDPARAMS, "Invalid font name", "MovableTextOverlayAttributes::MovableTextOverlayAttributes");
 
	setFontName(fontName);
	setMaterialName(materialName);
	setColor(color);
}
 
MovableTextOverlayAttributes::~MovableTextOverlayAttributes()
{
	setFontName("");
	setMaterialName("");
}
 
void MovableTextOverlayAttributes::setFontName(const Ogre::String & fontName)
{
    if (mFontName != fontName || !mpFont)
    {
		if (mpFont)
		{
			mpFont->unload();
			mpFont = NULL;
		}
 
		mFontName = fontName;
		if (mFontName.length())
		{
			mpFont = dynamic_cast<Ogre::Font*>(Ogre::FontManager::getSingleton().getByName(mFontName).getPointer());
			if (!mpFont)
				Ogre::Exception(Ogre::Exception::ERR_ITEM_NOT_FOUND, "Could not find font " + fontName, "MovableTextOverlay::setFontName");
			mpFont->load();
		}
    }
}
 
void MovableTextOverlayAttributes::setMaterialName(const Ogre::String & materialName)
{
	if (mMaterialName != materialName)
	{
		if (mMaterialName.length())
			Ogre::MaterialManager::getSingletonPtr()->getByName(mMaterialName).getPointer()->unload();
 
		mMaterialName = materialName;
		if (mMaterialName.length())
		{
			Ogre::Material *mpMaterial = dynamic_cast<Ogre::Material*>(Ogre::MaterialManager::getSingletonPtr()->getByName(mMaterialName).getPointer());
			if (!mpMaterial)
				Ogre::Exception(Ogre::Exception::ERR_ITEM_NOT_FOUND, "Could not find font " + materialName, "MovableTextOverlay::setMaterialName");
			mpMaterial->load();
		}
	}
}
 
void MovableTextOverlayAttributes::setColor(const Ogre::ColourValue & color)
{
        mColor = color;
}
 
void MovableTextOverlayAttributes::setCharacterHeight(unsigned int height)
{
        mCharHeight = height;
}

#ifndef __RectLayoutManager_H__
#define __RectLayoutManager_H__
 
#include <list>
#include <algorithm>
 
using namespace std;
 
// It moves the rectangles on the Y axis so they won't overlap.
class RectLayoutManager
{
public:
 
	enum MethodType 
	{
		PLACE_ABOVE = 0,	// the overlapping rectangles are placed above the non-overlapping ones
		PLACE_BELOW			// the overlapping rectangles are placed below the non-overlapping ones
	};
 
	class Rect
	{
	public:
		Rect(short left, short top, short right, short bottom)
			: mLeft(left)
			, mTop(top)
			, mRight(right)
			, mBottom(bottom)
			, dy(0)
		{
			if (mBottom <= mTop)
				throw std::exception("Condition Failure (top < bottom) in RectLayoutManager::Rect::Rect");
 
			if (mRight <= mLeft)
				throw std::exception("Condition Failure (left < right) in RectLayoutManager::Rect::Rect");
		}
 
		inline const short getTop() const {return mTop + dy;}
		inline const short getBottom() const {return mBottom + dy;}
		inline const short getLeft() const {return mLeft;}
		inline const short getRight() const {return mRight;}
 
		// STL needs this
		inline bool operator <(const RectLayoutManager::Rect &R) const {return getBottom() < R.getBottom();}
 
		// displacement on Y axis
		short dy;
 
		// original rectangle coordinates
		short mBottom;
		short mTop;
		short mLeft;
		short mRight;
	};
 
	typedef list<RectLayoutManager::Rect> RectList;
 
	RectLayoutManager(	unsigned short leftBound,
						unsigned short topBound,
						unsigned short rightBound,
						unsigned short bottomBound,
						MethodType method = PLACE_ABOVE)
	: mMethod(method)
	, mBoundTop(topBound)
	, mBoundLeft(leftBound)
	, mBoundBottom(bottomBound)
	, mBoundRight(rightBound)
	, mMinDistance(1)
	, mMaxRectHeight(0)
	, mDepth(0)
	{
		if (mBoundBottom <= mBoundTop)
			throw std::exception("Condition Failure (mBoundTop < mBoundBottom) in RectLayoutManager::RectLayoutManager");
 
		if (mBoundRight <= mBoundLeft)
			throw std::exception("Condition Failure (mBoundLeft < mBoundRight) in RectLayoutManager::RectLayoutManager");
	}
 
	~RectLayoutManager(){clear();}
 
	const unsigned short getMinDistance() const {return mMinDistance;}
	const unsigned short getMaxRectHeight() const {return mMaxRectHeight;}
	const unsigned short getDepth() const {return mDepth;}
	void getBounds(	unsigned short &left,
					unsigned short &top,
					unsigned short &right,
					unsigned short &bottom)
	{
		left = mBoundLeft;
		top = mBoundTop;
		right = mBoundRight;
		bottom = mBoundBottom;
	}
 
	void setMinDistance(unsigned short minDistance){mMinDistance = minDistance;}
	void setDepth(unsigned short depth){mDepth = depth;}
 
	bool isOutOfBounds(RectLayoutManager::Rect &r)
	{
		if (r.getTop() < mBoundTop ||
			r.getBottom() > mBoundBottom ||
			r.getLeft() < mBoundLeft ||
			r.getRight() > mBoundRight)
			return true;
		else
			return false;
	}
 
	RectList::iterator getListBegin(){return mList.begin();}
	RectList::iterator getListEnd(){return mList.end();}
 
	void clear(){mList.clear();}
 
	RectList::iterator addData(Rect &Data)
	{
		if (isOutOfBounds(Data))
			return mList.end(); // out of bounds, error
 
		switch (mMethod)
		{
		case PLACE_ABOVE:
			return addDataAbove(Data);
		case PLACE_BELOW:
			return addDataBelow(Data);
		default:
			return mList.end(); // incorrect method type, error
		}
	}
 
protected:
	// List of orderedd rectangles
	// All items in list are assumed ordered and within established Bounds
	RectList mList;
 
	// The overlapping rectangles are placed at a mMinDistance from the other ones
	unsigned short mMinDistance;
 
	// This gets calculated "on the fly"
	unsigned short mMaxRectHeight;
 
	// An overlapping rectangle is moved on Y axis (Above or Below) untill
	//  a place is found where it doesn't overlap any other rectangle.
	// mDepth is the number of times an overlapping rectangle will be moved
	//  in order to find a non-overlapping place.
	//
	// (mDepth = 0) - the search will go on untill a place is found.
	// (mDepth > 0) - the search will go on <mDepth> times
	unsigned short mDepth;	
 
	// Don't use these directly, use addData instead
	RectList::iterator addDataAbove(Rect &Data);
	RectList::iterator addDataBelow(Rect &Data);
 
	// Const variables can only be set in the constructor and certify the RectList integrity.
 
	// Method Type
	const MethodType mMethod;
 
	// Bounds
	const unsigned short mBoundTop;
	const unsigned short mBoundLeft;
	const unsigned short mBoundBottom;
	const unsigned short mBoundRight;
};
 
static bool _fLessBottom(const RectLayoutManager::Rect &L, const RectLayoutManager::Rect &R) {return L.getBottom() < R.getBottom();}
 
RectLayoutManager::RectList::iterator RectLayoutManager::addDataBelow(RectLayoutManager::Rect &Data)
{
	bool MoveIt = false;
	bool FoundIt = false;
	RectList::iterator itStart;
	RectList::iterator itLastChecked;
	RectList::iterator itCurrent;
	RectList::iterator itInsert;
 
	unsigned short depth = 0;
	RectLayoutManager::Rect &r = Data;
	short height = r.getBottom() - r.getTop();
 
	if (height > mMaxRectHeight)
		mMaxRectHeight = height;
 
	// find the first RECT  that has .bottom > r.top
	// first possible intersect
	r.dy -= height;
	itStart = lower_bound(mList.begin(), mList.end(), r, &_fLessBottom);
	r.dy += height;
 
	// it's safe to add it at the back of the list
	if (itStart == mList.end())
	{
		mList.push_back(r);
		return --(mList.end());
	}
 
	// insert it temporarily (we will move it at the right place, afterwords)
	itInsert = mList.insert(itStart,r);
 
	for (itCurrent = itStart, itLastChecked = itInsert;itCurrent != mList.end();itCurrent++)
	{
		// Can't intersect r so i skip it
		if ((*itCurrent).getRight() < r.getLeft())
			continue;
 
		// Can't intersect r so i skip it
		if (r.getRight() < (*itCurrent).getLeft())
			continue;
 
		// Can't intersect r so i skip it
		if (r.getTop() > (*itCurrent).getBottom())
			continue;
 
		short diff = (*itCurrent).getTop() - (*itLastChecked).getBottom();
		short diff2 = mMaxRectHeight - ((*itCurrent).getBottom() - (*itCurrent).getTop());
		if (diff > 0) // above the last checked
		{
			// If no rect overlapped r, then there is no need to move it
			if (!MoveIt && (diff > diff2))
			{	
				FoundIt = true;
				itLastChecked = itStart;
				break;
			}
			else
				MoveIt = true;
 
			if (mDepth && (depth >= mDepth))
				break;
 
			// This is above r, so i check if its enought space to move r
			if (diff > height + diff2 + 2*mMinDistance)
			{
				r.dy = ((*itLastChecked).getBottom() + mMinDistance + 1) - r.getTop();
				FoundIt = true;
				break;
			}
 
			depth++;
		}
		else // it overlaps
			MoveIt = true;
 
		itLastChecked = itCurrent;
	}
 
	if (itCurrent == mList.end())
	{
		if (MoveIt)
			r.dy = ((*itLastChecked).getBottom() + mMinDistance + 1) - r.getTop();
		else
			itLastChecked = itStart;
 
		FoundIt = true;
	}
 
	mList.erase(itInsert);
 
	if (FoundIt)
	{
		if (r.getBottom() > mBoundBottom)
			return mList.end(); // out of bounds
 
		itInsert = lower_bound(itLastChecked, itCurrent, r);			
		itInsert = mList.insert(itInsert,r);
 
		return itInsert;
	};
 
	return mList.end();
}
 
static bool _fGreaterTop(const RectLayoutManager::Rect &L, const RectLayoutManager::Rect &R) {return L.getTop() > R.getTop();}
 
RectLayoutManager::RectList::iterator RectLayoutManager::addDataAbove(RectLayoutManager::Rect &Data)
{
	bool MoveIt = false;
	bool FoundIt = false;
	RectList::iterator itStart;
	RectList::iterator itLastChecked;
	RectList::iterator itCurrent;
	RectList::iterator itInsert;
 
	unsigned short depth = 0;
	RectLayoutManager::Rect &r = Data;
	short height = r.getBottom() - r.getTop();
 
	if (height > mMaxRectHeight)
		mMaxRectHeight = height;
 
	// find the first RECT  that has .bottom > r.top
	// first possible intersect
	r.dy += height;
	itStart = lower_bound(mList.begin(), mList.end(), r, &_fGreaterTop);
	r.dy -= height;
 
	// it's safe to add it at the back of the list
	if (itStart == mList.end())
	{
		mList.push_back(r);
		return --(mList.end());
	}
 
	// insert it temporarily (we will move it at the right place, afterwords)
	itInsert = mList.insert(itStart,r);
 
	for (itCurrent = itStart, itLastChecked = itInsert;itCurrent != mList.end();itCurrent++)
	{
		// Can't intersect r so i skip it
		if ((*itCurrent).getRight() < r.getLeft())
			continue;
 
		// Can't intersect r so i skip it
		if (r.getRight() < (*itCurrent).getLeft())
			continue;
 
		// Can't intersect r so i skip it
		if (r.getBottom() < (*itCurrent).getTop())
			continue;
 
		short diff = (*itLastChecked).getTop() - (*itCurrent).getBottom();
		short diff2 = mMaxRectHeight - ((*itCurrent).getBottom() - (*itCurrent).getTop());
		if (diff > 0) // above the last checked
		{
			// If no rect overlapped r, then there is no need to move it
			if (!MoveIt && (diff > diff2))
			{	
				FoundIt = true;
				itLastChecked = itStart;
				break;
			}
			else
				MoveIt = true;
 
			if (mDepth && (depth >= mDepth))
				break;
 
			// This is above r, so i check if its enought space to move r
			if (diff > height + diff2 + 2*mMinDistance)
			{
				r.dy = -(r.getBottom() - ((*itLastChecked).getTop() - mMinDistance - 1));
				FoundIt = true;
				break;
			}
 
			depth++;
		}
		else // it overlaps
			MoveIt = true;
 
		itLastChecked = itCurrent;
	}
 
	if (itCurrent == mList.end())
	{
		if (MoveIt)
			r.dy = -(r.getBottom() - ((*itLastChecked).getTop() - mMinDistance - 1));
		else
			itLastChecked = itStart;
 
 
		FoundIt = true;
	}
 
	mList.erase(itInsert);
 
	if (FoundIt)
	{
		if (r.getTop() < mBoundTop)
			return mList.end(); // out of bounds
 
		itInsert = lower_bound(itLastChecked, itCurrent, r, _fGreaterTop);			
		itInsert = mList.insert(itInsert,r);
 
		return itInsert;
	};
 
	return mList.end();
}
#endif /* __RectLayoutManager_H__ */

vector<MovableTextOverlay*> myVect;

Entity *ent = mSceneMgr->createEntity( "Robot", "robot.mesh" );
 
// get terrain height under the camera
RaySceneQuery* raySceneQuery2 = mSceneMgr->createRayQuery(Ray(mCamera->getPosition(), Vector3::NEGATIVE_UNIT_Y));
RaySceneQueryResult& qryResult = raySceneQuery2->execute();
RaySceneQueryResult::iterator i = qryResult.begin();
if (i != qryResult.end() && i->worldFragment)
{       
	// create the attributes used by MovableTextOverlay
	MovableTextOverlayAttributes *attrs = new MovableTextOverlayAttributes("Attrs1",mCamera,"BlueHighway",16,ColourValue::White,"RedTransparent");
 
	// add 10 MovableTextOverlay pointers to myVect
	for (int j=0; j<10;j++)
	{
		String k = StringConverter::toString(j);
		Entity *ent2 = ent->clone("Ent"+k);
		SceneNode *node = mSceneMgr->getRootSceneNode()->createChildSceneNode( "Node"+k);
		node->setPosition(i->worldFragment->singleIntersection + Ogre::Vector3(j*10,0,0));
		node->scale(Ogre::Vector3(0.1,0.1,0.1));
		node->attachObject( ent2 );
		MovableTextOverlay*p = new MovableTextOverlay("Text"+k," Robot"+k+" ", ent2, attrs);
		p->enable(false); // make it invisible for now
		p->setUpdateFrequency(0.01);// set update frequency to 0.01 seconds
		myVect.push_back(p); 
	}
}

RectLayoutManager m(0,0,mCamera->getViewport()->getActualWidth(),
		mCamera->getViewport()->getActualHeight());
m.setDepth(0);
 
int visible=0;
MovableTextOverlay *p=0;
for (vector<MovableTextOverlay*>::iterator i = myMap.begin();i<myMap.end();i++)
{
	p = *i;
	p->update(evt.timeSinceLastFrame);
	if (p->isOnScreen())
	{
		visible++;
 
		RectLayoutManager::Rect r(	p->getPixelsLeft(),
									p->getPixelsTop(),
									p->getPixelsRight(),
									p->getPixelsBottom());
 
		RectLayoutManager::RectList::iterator it = m.addData(r);
		if (it != m.getListEnd())
		{
			p->setPixelsTop((*it).getTop());
			p->enable(true);
		}
		else
			p->enable(false);
	}
	else
		p->enable(false);
}

material RedTransparent
{
   technique
   {
      pass
      {
         scene_blend alpha_blend
         lighting off
         depth_write off
         texture_unit
         {
            colour_op_ex source1 src_manual src_current 1 0 0
            alpha_op_ex source1 src_manual src_current 0.4
         }
      }
 
   }
}