src/util/string.h

/*
Minetest
Copyright (C) 2013 celeron55, Perttu Ahola <celeron55@gmail.com>

This program 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 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 Lesser General Public License for more details.

You should have received a copy of the GNU Lesser 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 "guiTable.h"
#include <queue>
#include <sstream>
#include <utility>
#include <string.h>
#include <IGUISkin.h>
#include <IGUIFont.h>
#include <IGUIScrollBar.h>
#include "debug.h"
#include "log.h"
#include "tile.h"
#include "gettime.h"
#include "util/string.h"
#include "util/numeric.h"
#include "util/string.h" // for parseColorString()
#include "main.h"
#include "settings.h" // for settings
#include "porting.h" // for dpi

/*
	GUITable
*/

GUITable::GUITable(gui::IGUIEnvironment *env,
		gui::IGUIElement* parent, s32 id,
		core::rect<s32> rectangle,
		ISimpleTextureSource *tsrc
):
	gui::IGUIElement(gui::EGUIET_ELEMENT, env, parent, id, rectangle),
	m_tsrc(tsrc),
	m_is_textlist(false),
	m_has_tree_column(false),
	m_selected(-1),
	m_sel_column(0),
	m_sel_doubleclick(false),
	m_keynav_time(0),
	m_keynav_buffer(L""),
	m_border(true),
	m_color(255, 255, 255, 255),
	m_background(255, 0, 0, 0),
	m_highlight(255, 70, 100, 50),
	m_highlight_text(255, 255, 255, 255),
	m_rowheight(1),
	m_font(NULL),
	m_scrollbar(NULL)
{
	assert(tsrc != NULL);

	gui::IGUISkin* skin = Environment->getSkin();

	m_font = skin->getFont();
	if (m_font) {
		m_font->grab();
		m_rowheight = m_font->getDimension(L"A").Height + 4;
		m_rowheight = MYMAX(m_rowheight, 1);
	}

	const s32 s = skin->getSize(gui::EGDS_SCROLLBAR_SIZE);
	m_scrollbar = Environment->addScrollBar(false,
			core::rect<s32>(RelativeRect.getWidth() - s,
					0,
					RelativeRect.getWidth(),
					RelativeRect.getHeight()),
			this, -1);
	m_scrollbar->setSubElement(true);
	m_scrollbar->setTabStop(false);
	m_scrollbar->setAlignment(gui::EGUIA_LOWERRIGHT, gui::EGUIA_LOWERRIGHT,
			gui::EGUIA_UPPERLEFT, gui::EGUIA_LOWERRIGHT);
	m_scrollbar->setVisible(false);
	m_scrollbar->setPos(0);

	setTabStop(true);
	setTabOrder(-1);
	updateAbsolutePosition();

	core::rect<s32> relative_rect = m_scrollbar->getRelativePosition();
	s32 width = (relative_rect.getWidth()/(2.0/3.0)) * porting::getDisplayDensity() *
			g_settings->getFloat("gui_scaling");
	m_scrollbar->setRelativePosition(core::rect<s32>(
			relative_rect.LowerRightCorner.X-width,relative_rect.UpperLeftCorner.Y,
			relative_rect.LowerRightCorner.X,relative_rect.LowerRightCorner.Y
			));
}

GUITable::~GUITable()
{
	for (size_t i = 0; i < m_rows.size(); ++i)
		delete[] m_rows[i].cells;

	if (m_font)
		m_font->drop();
	
	m_scrollbar->remove();
}

GUITable::Option GUITable::splitOption(const std::string &str)
{
	size_t equal_pos = str.find('=');
	if (equal_pos == std::string::npos)
		return GUITable::Option(str, "");
	else
		return GUITable::Option(str.substr(0, equal_pos),
				str.substr(equal_pos + 1));
}

void GUITable::setTextList(const std::vector<std::string> &content,
		bool transparent)
{
	clear();

	if (transparent) {
		m_background.setAlpha(0);
		m_border = false;
	}

	m_is_textlist = true;

	s32 empty_string_index = allocString("");

	m_rows.resize(content.size());
	for (s32 i = 0; i < (s32) content.size(); ++i) {
		Row *row = &m_rows[i];
		row->cells = new Cell[1];
		row->cellcount = 1;
		row->indent = 0;
		row->visible_index = i;
		m_visible_rows.push_back(i);

		Cell *cell = row->cells;
		cell->xmin = 0;
		cell->xmax = 0x7fff;  // something large enough
		cell->xpos = 6;
		cell->content_type = COLUMN_TYPE_TEXT;
		cell->content_index = empty_string_index;
		cell->tooltip_index = empty_string_index;
		cell->color.set(255, 255, 255, 255);
		cell->color_defined = false;
		cell->reported_column = 1;

		// parse row content (color)
		const std::string &s = content[i];
		if (s[0] == '#' && s[1] == '#') {
			// double # to escape
			cell->content_index = allocString(s.substr(2));
		}
		else if (s[0] == '#' && s.size() >= 7 &&
				parseColorString(
					s.substr(0,7), cell->color, false)) {
			// single # for color
			cell->color_defined = true;
			cell->content_index = allocString(s.substr(7));
		}
		else {
			// no #, just text
			cell->content_index = allocString(s);
		}

	}

	allocationComplete();

	// Clamp scroll bar position
	updateScrollBar();
}

void GUITable::setTable(const TableOptions &options,
		const TableColumns &columns,
		std::vector<std::string> &content)
{
	clear();

	// Naming conventions:
	// i is always a row index, 0-based
	// j is always a column index, 0-based
	// k is another index, for example an option index

	// Handle a stupid error case... (issue #1187)
	if (columns.empty()) {
		TableColumn text_column;
		text_column.type = "text";
		TableColumns new_columns;
		new_columns.push_back(text_column);
		setTable(options, new_columns, content);
		return;
	}

	// Handle table options
	video::SColor default_color(255, 255, 255, 255);
	s32 opendepth = 0;
	for (size_t k = 0; k < options.size(); ++k) {
		const std::string &name = options[k].name;
		const std::string &value = options[k].value;
		if (name == "color")
			parseColorString(value, m_color, false);
		else if (name == "background")
			parseColorString(value, m_background, false);
		else if (name == "border")
			m_border = is_yes(value);
		else if (name == "highlight")
			parseColorString(value, m_highlight, false);
		else if (name == "highlight_text")
			parseColorString(value, m_highlight_text, false);
		else if (name == "opendepth")
			opendepth = stoi(value);
		else
			errorstream<<"Invalid table option: \""<<name<<"\""
				<<" (value=\""<<value<<"\")"<<std::endl;
	}

	// Get number of columns and rows
	// note: error case columns.size() == 0 was handled above
	s32 colcount = columns.size();
	assert(colcount >= 1);
	// rowcount = ceil(cellcount / colcount) but use integer arithmetic
	s32 rowcount = (content.size() + colcount - 1) / colcount;
	assert(rowcount >= 0);
	// Append empty strings to content if there is an incomplete row
	s32 cellcount = rowcount * colcount;
	while (content.size() < (u32) cellcount)
		content.push_back("");

	// Create temporary rows (for processing columns)
	struct TempRow {
		// Current horizontal position (may different between rows due
		// to indent/tree columns, or text/image columns with width<0)
		s32 x;
		// Tree indentation level
		s32 indent;
		// Next cell: Index into m_strings or m_images
		s32 content_index;
		// Next cell: Width in pixels
		s32 content_width;
		// Vector of completed cells in this row
		std::vector<Cell> cells;
		// Stores colors and how long they last (maximum column index)
		std::vector<std::pair<video::SColor, s32> > colors;

		TempRow(): x(0), indent(0), content_index(0), content_width(0) {}
	};
	TempRow *rows = new TempRow[rowcount];

	// Get em width. Pedantically speaking, the width of "M" is not
	// necessarily the same as the em width, but whatever, close enough.
	s32 em = 6;
	if (m_font)
		em = m_font->getDimension(L"M").Width;

	s32 default_tooltip_index = allocString("");

	std::map<s32, s32> active_image_indices;

	// Process content in column-major order
	for (s32 j = 0; j < colcount; ++j) {
		// Check column type
		ColumnType columntype = COLUMN_TYPE_TEXT;
		if (columns[j].type == "text")
			columntype = COLUMN_TYPE_TEXT;
		else if (columns[j].type == "image")
			columntype = COLUMN_TYPE_IMAGE;
		else if (columns[j].type == "color")
			columntype = COLUMN_TYPE_COLOR;
		else if (columns[j].type == "indent")
			columntype = COLUMN_TYPE_INDENT;
		else if (columns[j].type == "tree")
			columntype = COLUMN_TYPE_TREE;
		else
			errorstream<<"Invalid table column type: \""
				<<columns[j].type<<"\""<<std::endl;

		// Process column options
		s32 padding = myround(0.5 * em);
		s32 tooltip_index = default_tooltip_index;
		s32 align = 0;
		s32 width = 0;
		s32 span = colcount;

		if (columntype == COLUMN_TYPE_INDENT) {
			padding = 0; // default indent padding
		}
		if (columntype == COLUMN_TYPE_INDENT ||
				columntype == COLUMN_TYPE_TREE) {
			width = myround(em * 1.5); // default indent width
		}

		for (size_t k = 0; k < columns[j].options.size(); ++k) {
			const std::string &name = columns[j].options[k].name;
			const std::string &value = columns[j].options[k].value;
			if (name == "padding")
				padding = myround(stof(value) * em);
			else if (name == "tooltip")
				tooltip_index = allocString(value);
			else if (name == "align" && value == "left")
				align = 0;
			else if (name == "align" && value == "center")
				align = 1;
			else if (name == "align" && value == "right")
				align = 2;
			else if (name == "align" && value == "inline")
				align = 3;
			else if (name == "width")
				width = myround(stof(value) * em);
			else if (name == "span" && columntype == COLUMN_TYPE_COLOR)
				span = stoi(value);
			else if (columntype == COLUMN_TYPE_IMAGE &&
					!name.empty() &&
					string_allowed(name, "0123456789")) {
				s32 content_index = allocImage(value);
				active_image_indices.insert(std::make_pair(
							stoi(name),
							content_index));
			}
			else {
				errorstream<<"Invalid table column option: \""<<name<<"\""
					<<" (value=\""<<value<<"\")"<<std::endl;
			}
		}

		// If current column type can use information from "color" columns,
		// find out which of those is currently active
		if (columntype == COLUMN_TYPE_TEXT) {
			for (s32 i = 0; i < rowcount; ++i) {
				TempRow *row = &rows[i];
				while (!row->colors.empty() && row->colors.back().second < j)
					row->colors.pop_back();
			}
		}

		// Make template for new cells
		Cell newcell;
		memset(&newcell, 0, sizeof newcell);
		newcell.content_type = columntype;
		newcell.tooltip_index = tooltip_index;
		newcell.reported_column = j+1;

		if (columntype == COLUMN_TYPE_TEXT) {
			// Find right edge of column
			s32 xmax = 0;
			for (s32 i = 0; i < rowcount; ++i) {
				TempRow *row = &rows[i];
				row->content_index = allocString(content[i * colcount + j]);
				const core::stringw &text = m_strings[row->content_index];
				row->content_width = m_font ?
					m_font->getDimension(text.c_str()).Width : 0;
				row->content_width = MYMAX(row->content_width, width);
				s32 row_xmax = row->x + padding + row->content_width;
				xmax = MYMAX(xmax, row_xmax);
			}
			// Add a new cell (of text type) to each row
			for (s32 i = 0; i < rowcount; ++i) {
				newcell.xmin = rows[i].x + padding;
				alignContent(&newcell, xmax, rows[i].content_width, align);
				newcell.content_index = rows[i].content_index;
				newcell.color_defined = !rows[i].colors.empty();
				if (newcell.color_defined)
					newcell.color = rows[i].colors.back().first;
				rows[i].cells.push_back(newcell);
				rows[i].x = newcell.xmax;
			}
		}
		else if (columntype == COLUMN_TYPE_IMAGE) {
			// Find right edge of column
			s32 xmax = 0;
			for (s32 i = 0; i < rowcount; ++i) {
				TempRow *row = &rows[i];
				row->content_index = -1;

				// Find content_index. Image indices are defined in
				// column options so check active_image_indices.
				s32 image_index = stoi(content[i * colcount + j]);
				std::map<s32, s32>::iterator image_iter =
					active_image_indices.find(image_index);
				if (image_iter != active_image_indices.end())
					row->content_index = image_iter->second;

				// Get texture object (might be NULL)
				video::ITexture *image = NULL;
				if (row->content_index >= 0)
					image = m_images[row->content_index];

				// Get content width and update xmax
				row->content_width = image ? image->getOriginalSize().Width : 0;
				row->content_width = MYMAX(row->content_width, width);
				s32 row_xmax = row->x + padding + row->content_width;
				xmax = MYMAX(xmax, row_xmax);
			}
			// Add a new cell (of image type) to each row
			for (s32 i = 0; i < rowcount; ++i) {
				newcell.xmin = rows[i].x + padding;
				alignContent(&newcell, xmax, rows[i].content_width, align);
				newcell.content_index = rows[i].content_index;
				rows[i].cells.push_back(newcell);
				rows[i].x = newcell.xmax;
			}
			active_image_indices.clear();
		}
		else if (columntype == COLUMN_TYPE_COLOR) {
			for (s32 i = 0; i < rowcount; ++i) {
				video::SColor cellcolor(255, 255, 255, 255);
				if (parseColorString(content[i * colcount + j], cellcolor, true))
					rows[i].colors.push_back(std::make_pair(cellcolor, j+span));
			}
		}
		else if (columntype == COLUMN_TYPE_INDENT ||
				columntype == COLUMN_TYPE_TREE) {
			// For column type "tree", reserve additional space for +/-
			// Also enable special processing for treeview-type tables
			s32 content_width = 0;
			if (columntype == COLUMN_TYPE_TREE) {
				content_width = m_font ? m_font->getDimension(L"+").Width : 0;
				m_has_tree_column = true;
			}
			// Add a new cell (of indent or tree type) to each row
			for (s32 i = 0; i < rowcount; ++i) {
				TempRow *row = &rows[i];

				s32 indentlevel = stoi(content[i * colcount + j]);
				indentlevel = MYMAX(indentlevel, 0);
				if (columntype == COLUMN_TYPE_TREE)
					row->indent = indentlevel;

				newcell.xmin = row->x + padding;
				newcell.xpos = newcell.xmin + indentlevel * width;
				newcell.xmax = newcell.xpos + content_width;
				newcell.content_index = 0;
				newcell.color_defined = !rows[i].colors.empty();
				if (newcell.color_defined)
					newcell.color = rows[i].colors.back().first;
				row->cells.push_back(newcell);
				row->x = newcell.xmax;
			}
		}
	}

	// Copy temporary rows to not so temporary rows
	if (rowcount >= 1) {
		m_rows.resize(rowcount);
		for (s32 i = 0; i < rowcount; ++i) {
			Row *row = &m_rows[i];
			row->cellcount = rows[i].cells.size();
			row->cells = new Cell[row->cellcount];
			memcpy((void*) row->cells, (void*) &rows[i].cells[0],
					row->cellcount * sizeof(Cell));
			row->indent = rows[i].indent;
			row->visible_index = i;
			m_visible_rows.push_back(i);
		}
	}

	if (m_has_tree_column) {
		// Treeview: convert tree to indent cells on leaf rows
		for (s32 i = 0; i < rowcount; ++i) {
			if (i == rowcount-1 || m_rows[i].indent >= m_rows[i+1].indent)
				for (s32 j = 0; j < m_rows[i].cellcount; ++j)
					if (m_rows[i].cells[j].content_type == COLUMN_TYPE_TREE)
						m_rows[i].cells[j].content_type = COLUMN_TYPE_INDENT;
		}

		// Treeview: close rows according to opendepth option
		std::set<s32> opened_trees;
		for (s32 i = 0; i < rowcount; ++i)
			if (m_rows[i].indent < opendepth)
				opened_trees.insert(i);
		setOpenedTrees(opened_trees);
	}

	// Delete temporary information used only during setTable()
	delete[] rows;
	allocationComplete();

	// Clamp scroll bar position
	updateScrollBar();
}

void GUITable::clear()
{
	// Clean up cells and rows
	for (size_t i = 0; i < m_rows.size(); ++i)
		delete[] m_rows[i].cells;
	m_rows.clear();
	m_visible_rows.clear();

	// Get colors from skin
	gui::IGUISkin *skin = Environment->getSkin();
	m_color          = skin->getColor(gui::EGDC_BUTTON_TEXT);
	m_background     = skin->getColor(gui::EGDC_3D_HIGH_LIGHT);
	m_highlight      = skin->getColor(gui::EGDC_HIGH_LIGHT);
	m_highlight_text = skin->getColor(gui::EGDC_HIGH_LIGHT_TEXT);

	// Reset members
	m_is_textlist = false;
	m_has_tree_column = false;
	m_selected = -1;
	m_sel_column = 0;
	m_sel_doubleclick = false;
	m_keynav_time = 0;
	m_keynav_buffer = L"";
	m_border = true;
	m_strings.clear();
	m_images.clear();
	m_alloc_strings.clear();
	m_alloc_images.clear();
}

std::string GUITable::checkEvent()
{
	s32 sel = getSelected();
	assert(sel >= 0);

	if (sel == 0) {
		return "INV";
	}

	std::ostringstream os(std::ios::binary);
	if (m_sel_doubleclick) {
		os<<"DCL:";
		m_sel_doubleclick = false;
	}
	else {
		os<<"CHG:";
	}
	os<<sel;
	if (!m_is_textlist) {
		os<<":"<<m_sel_column;
	}
	return os.str();
}

s32 GUITable::getSelected() const
{
	if (m_selected < 0)
		return 0;

	assert(m_selected >= 0 && m_selected < (s32) m_visible_rows.size());
	return m_visible_rows[m_selected] + 1;
}

void GUITable::setSelected(s32 index)
{
	m_selected = -1;
	m_sel_column = 0;
	m_sel_doubleclick = false;

	--index;

	s32 rowcount = m_rows.size();

	if (index >= rowcount)
		index = rowcount - 1;
	while (index >= 0 && m_rows[index].visible_index < 0)
		--index;
	if (index >= 0) {
		m_selected = m_rows[index].visible_index;
		assert(m_selected >= 0 && m_selected < (s32) m_visible_rows.size());
	}

	autoScroll();
}

GUITable::DynamicData GUITable::getDynamicData() const
{
	DynamicData dyndata;
	dyndata.selected = getSelected();
	dyndata.scrollpos = m_scrollbar->getPos();
	dyndata.keynav_time = m_keynav_time;
	dyndata.keynav_buffer = m_keynav_buffer;
	if (m_has_tree_column)
		getOpenedTrees(dyndata.opened_trees);
	return dyndata;
}

void GUITable::setDynamicData(const DynamicData &dyndata)
{
	if (m_has_tree_column)
		setOpenedTrees(dyndata.opened_trees);

	m_keynav_time = dyndata.keynav_time;
	m_keynav_buffer = dyndata.keynav_buffer;

	m_scrollbar->setPos(dyndata.scrollpos);

	setSelected(dyndata.selected);
	m_sel_column = 0;
	m_sel_doubleclick = false;
}

const c8* GUITable::getTypeName() const
{
	return "GUITable";
}

void GUITable::updateAbsolutePosition()
{
	IGUIElement::updateAbsolutePosition();
	updateScrollBar();
}

void GUITable::draw()
{
	if (!IsVisible)
		return;

	gui::IGUISkin *skin = Environment->getSkin();

	// draw background

	bool draw_background = m_background.getAlpha() > 0;
	if (m_border)
		skin->draw3DSunkenPane(this, m_background,
				true, draw_background,
				AbsoluteRect, &AbsoluteClippingRect);
	else if (draw_background)
		skin->draw2DRectangle(this, m_background,
				AbsoluteRect, &AbsoluteClippingRect);

	// get clipping rect

	core::rect<s32> client_clip(AbsoluteRect);
	client_clip.UpperLeftCorner.Y += 1;
	client_clip.UpperLeftCorner.X += 1;
	client_clip.LowerRightCorner.Y -= 1;
	client_clip.LowerRightCorner.X -=
		m_scrollbar->isVisible() ?
		skin->getSize(gui::EGDS_SCROLLBAR_SIZE) :
		1;
	client_clip.clipAgainst(AbsoluteClippingRect);

	// draw visible rows

	s32 scrollpos = m_scrollbar->getPos();
	s32 row_min = scrollpos / m_rowheight;
	s32 row_max = (scrollpos + AbsoluteRect.getHeight() - 1)
			/ m_rowheight + 1;
	row_max = MYMIN(row_max, (s32) m_visible_rows.size());

	core::rect<s32> row_rect(AbsoluteRect);
	if (m_scrollbar->isVisible())
		row_rect.LowerRightCorner.X -=
			skin->getSize(gui::EGDS_SCROLLBAR_SIZE);
	row_rect.UpperLeftCorner.Y += row_min * m_rowheight - scrollpos;
	row_rect.LowerRightCorner.Y = row_rect.UpperLeftCorner.Y + m_rowheight;

	for (s32 i = row_min; i < row_max; ++i) {
		Row *row = &m_rows[m_visible_rows[i]];
		bool is_sel = i == m_selected;
		video::SColor color = m_color;

		if (is_sel) {
			skin->draw2DRectangle(this, m_highlight, row_rect, &client_clip);
			color = m_highlight_text;
		}

		for (s32 j = 0; j < row->cellcount; ++j)
			drawCell(&row->cells[j], color, row_rect, client_clip);

		row_rect.UpperLeftCorner.Y += m_rowheight;
		row_rect.LowerRightCorner.Y += m_rowheight;
	}

	// Draw children
	IGUIElement::draw();
}

void GUITable::drawCell(const Cell *cell, video::SColor color,
		const core::rect<s32> &row_rect,
		const core::rect<s32> &client_clip)
{
	if ((cell->content_type == COLUMN_TYPE_TEXT)
			|| (cell->content_type == COLUMN_TYPE_TREE)) {

		core::rect<s32> text_rect = row_rect;
		text_rect.UpperLeftCorner.X = row_rect.UpperLeftCorner.X
				+ cell->xpos;
		text_rect.LowerRightCorner.X = row_rect.UpperLeftCorner.X
				+ cell->xmax;

		if (cell->color_defined)
			color = cell->color;

		if (m_font) {
			if (cell->content_type == COLUMN_TYPE_TEXT)
				m_font->draw(m_strings[cell->content_index],
						text_rect, color,
						false, true, &client_clip);
			else // tree
				m_font->draw(cell->content_index ? L"+" : L"-",
						text_rect, color,
						false, true, &client_clip);
		}
	}
	else if (cell->content_type == COLUMN_TYPE_IMAGE) {

		if (cell->content_index < 0)
			return;

		video::IVideoDriver *driver = Environment->getVideoDriver();
		video::ITexture *image = m_images[cell->content_index];

		if (image) {
			core::position2d<s32> dest_pos =
					row_rect.UpperLeftCorner;
			dest_pos.X += cell->xpos;
			core::rect<s32> source_rect(
					core::position2d<s32>(0, 0),
					image->getOriginalSize());
			s32 imgh = source_rect.LowerRightCorner.Y;
			s32 rowh = row_rect.getHeight();
			if (imgh < rowh)
				dest_pos.Y += (rowh - imgh) / 2;
			else
				source_rect.LowerRightCorner.Y = rowh;

			video::SColor color(255, 255, 255, 255);

			driver->draw2DImage(image, dest_pos, source_rect,
					&client_clip, color, true);
		}
	}
}

bool GUITable::OnEvent(const SEvent &event)
{
	if (!isEnabled())
		return IGUIElement::OnEvent(event);

	if (event.EventType == EET_KEY_INPUT_EVENT) {
		if (event.KeyInput.PressedDown && (
				event.KeyInput.Key == KEY_DOWN ||
				event.KeyInput.Key == KEY_UP   ||
				event.KeyInput.Key == KEY_HOME ||
				event.KeyInput.Key == KEY_END  ||
				event.KeyInput.Key == KEY_NEXT ||
				event.KeyInput.Key == KEY_PRIOR)) {
			s32 offset = 0;
			switch (event.KeyInput.Key) {
				case KEY_DOWN:
					offset = 1;
					break;
				case KEY_UP:
					offset = -1;
					break;
				case KEY_HOME:
					offset = - (s32) m_visible_rows.size();
					break;
				case KEY_END:
					offset = m_visible_rows.size();
					break;
				case KEY_NEXT:
					offset = AbsoluteRect.getHeight() / m_rowheight;
					break;
				case KEY_PRIOR:
					offset = - (s32) (AbsoluteRect.getHeight() / m_rowheight);
					break;
				default:
					break;
			}
			s32 old_selected = m_selected;
			s32 rowcount = m_visible_rows.size();
			if (rowcount != 0) {
				m_selected = rangelim(m_selected + offset, 0, rowcount-1);
				autoScroll();
			}

			if (m_selected != old_selected)
				sendTableEvent(0, false);

			return true;
		}
		else if (event.KeyInput.PressedDown && (
				event.KeyInput.Key == KEY_LEFT ||
				event.KeyInput.Key == KEY_RIGHT)) {
			// Open/close subtree via keyboard
			if (m_selected >= 0) {
				int dir = event.KeyInput.Key == KEY_LEFT ? -1 : 1;
				toggleVisibleTree(m_selected, dir, true);
			}
			return true;
		}
		else if (!event.KeyInput.PressedDown && (
				event.KeyInput.Key == KEY_RETURN ||
				event.KeyInput.Key == KEY_SPACE)) {
			sendTableEvent(0, true);
			return true;
		}
		else if (event.KeyInput.Key == KEY_ESCAPE ||
				event.KeyInput.Key == KEY_SPACE) {
			// pass to parent
		}
		else if (event.KeyInput.PressedDown && event.KeyInput.Char) {
			// change selection based on text as it is typed
			s32 now = getTimeMs();
			if (now - m_keynav_time >= 500)
				m_keynav_buffer = L"";
			m_keynav_time = now;

			// add to key buffer if not a key repeat
			if (!(m_keynav_buffer.size() == 1 &&
					m_keynav_buffer[0] == event.KeyInput.Char)) {
				m_keynav_buffer.append(event.KeyInput.Char);
			}

			// find the selected item, starting at the current selection
			// don't change selection if the key buffer matches the current item
			s32 old_selected = m_selected;
			s32 start = MYMAX(m_selected, 0);
			s32 rowcount = m_visible_rows.size();
			for (s32 k = 1; k < rowcount; ++k) {
				s32 current = start + k;
				if (current >= rowcount)
					current -= rowcount;
				if (doesRowStartWith(getRow(current), m_keynav_buffer)) {
					m_selected = current;
					break;
				}
			}
			autoScroll();
			if (m_selected != old_selected)
				sendTableEvent(0, false);

			return true;
		}
	}
	if (event.EventType == EET_MOUSE_INPUT_EVENT) {
		core::position2d<s32> p(event.MouseInput.X, event.MouseInput.Y);

		if (event.MouseInput.Event == EMIE_MOUSE_WHEEL) {
			m_scrollbar->setPos(m_scrollbar->getPos() +
					(event.MouseInput.Wheel < 0 ? -3 : 3) *
					- (s32) m_rowheight / 2);
			return true;
		}

		// Find hovered row and cell
		bool really_hovering = false;
		s32 row_i = getRowAt(p.Y, really_hovering);
		const Cell *cell = NULL;
		if (really_hovering) {
			s32 cell_j = getCellAt(p.X, row_i);
			if (cell_j >= 0)
				cell = &(getRow(row_i)->cells[cell_j]);
		}

		// Update tooltip
		setToolTipText(cell ? m_strings[cell->tooltip_index].c_str() : L"");

		// Fix for #1567/#1806:
		// IGUIScrollBar passes double click events to its parent,
		// which we don't want. Detect this case and discard the event
		if (event.MouseInput.Event != EMIE_MOUSE_MOVED &&
				m_scrollbar->isVisible() &&
				m_scrollbar->isPointInside(p))
			return true;

		if (event.MouseInput.isLeftPressed() &&
				(isPointInside(p) ||
				 event.MouseInput.Event == EMIE_MOUSE_MOVED)) {
			s32 sel_column = 0;
			bool sel_doubleclick = (event.MouseInput.Event
					== EMIE_LMOUSE_DOUBLE_CLICK);
			bool plusminus_clicked = false;

			// For certain events (left click), report column
			// Also open/close subtrees when the +/- is clicked
			if (cell && (
					event.MouseInput.Event == EMIE_LMOUSE_PRESSED_DOWN ||
					event.MouseInput.Event == EMIE_LMOUSE_DOUBLE_CLICK ||
					event.MouseInput.Event == EMIE_LMOUSE_TRIPLE_CLICK)) {
				sel_column = cell->reported_column;
				if (cell->content_type == COLUMN_TYPE_TREE)
					plusminus_clicked = true;
			}

			if (plusminus_clicked) {
				if (event.MouseInput.Event == EMIE_LMOUSE_PRESSED_DOWN) {
					toggleVisibleTree(row_i, 0, false);
				}
			}
			else {
				// Normal selection
				s32 old_selected = m_selected;
				m_selected = row_i;
				autoScroll();

				if (m_selected != old_selected ||
						sel_column >= 1 ||
						sel_doubleclick) {
					sendTableEvent(sel_column, sel_doubleclick);
				}
			}
		}
		return true;
	}
	if (event.EventType == EET_GUI_EVENT &&
			event.GUIEvent.EventType == gui::EGET_SCROLL_BAR_CHANGED &&
			event.GUIEvent.Caller == m_scrollbar) {
		// Don't pass events from our scrollbar to the parent
		return true;
	}

	return IGUIElement::OnEvent(event);
}

/******************************************************************************/
/* GUITable helper functions                                                  */
/******************************************************************************/

s32 GUITable::allocString(const std::string &text)
{
	std::map<std::string, s32>::iterator it = m_alloc_strings.find(text);
	if (it == m_alloc_strings.end()) {
		s32 id = m_strings.size();
		std::wstring wtext = narrow_to_wide(text);
		m_strings.push_back(core::stringw(wtext.c_str()));
		m_alloc_strings.insert(std::make_pair(text, id));
		return id;
	}
	else {
		return it->second;
	}
}

s32 GUITable::allocImage(const std::string &imagename)
{
	std::map<std::string, s32>::iterator it = m_alloc_images.find(imagename);
	if (it == m_alloc_images.end()) {
		s32 id = m_images.size();
		m_images.push_back(m_tsrc->getTexture(imagename));
		m_alloc_images.insert(std::make_pair(imagename, id));
		return id;
	}
	else {
		return it->second;
	}
}

void GUITable::allocationComplete()
{
	// Called when done with creating rows and cells from table data,
	// i.e. when allocString and allocImage won't be called anymore
	m_alloc_strings.clear();
	m_alloc_images.clear();
}

const GUITable::Row* GUITable::getRow(s32 i) const
{
	if (i >= 0 && i < (s32) m_visible_rows.size())
		return &m_rows[m_visible_rows[i]];
	else
		return NULL;
}

bool GUITable::doesRowStartWith(const Row *row, const core::stringw &str) const
{
	if (row == NULL)
		return false;

	for (s32 j = 0; j < row->cellcount; ++j) {
		Cell *cell = &row->cells[j];
		if (cell->content_type == COLUMN_TYPE_TEXT) {
			const core::stringw &cellstr = m_strings[cell->content_index];
			if (cellstr.size() >= str.size() &&
					str.equals_ignore_case(cellstr.subString(0, str.size())))
				return true;
		}
	}
	return false;
}

s32 GUITable::getRowAt(s32 y, bool &really_hovering) const
{
	really_hovering = false;

	s32 rowcount = m_visible_rows.size();
	if (rowcount == 0)
		return -1;

	// Use arithmetic to find row
	s32 rel_y = y - AbsoluteRect.UpperLeftCorner.Y - 1;
	s32 i = (rel_y + m_scrollbar->getPos()) / m_rowheight;

	if (i >= 0 && i < rowcount) {
		really_hovering = true;
		return i;
	}
	else if (i < 0)
		return 0;
	else
		return rowcount - 1;

}

s32 GUITable::getCellAt(s32 x, s32 row_i) const
{
	const Row *row = getRow(row_i);
	if (row == NULL)
		return -1;

	// Use binary search to find cell in row
	s32 rel_x = x - AbsoluteRect.UpperLeftCorner.X - 1;
	s32 jmin = 0;
	s32 jmax = row->cellcount - 1;
	while (jmin < jmax) {
		s32 pivot = jmin + (jmax - jmin) / 2;
		assert(pivot >= 0 && pivot < row->cellcount);
		const Cell *cell = &row->cells[pivot];

		if (rel_x >= cell->xmin && rel_x <= cell->xmax)
			return pivot;
		else if (rel_x < cell->xmin)
			jmax = pivot - 1;
		else
			jmin = pivot + 1;
	}

	if (jmin >= 0 && jmin < row->cellcount &&
			rel_x >= row->cells[jmin].xmin &&
			rel_x <= row->cells[jmin].xmax)
		return jmin;
	else
		return -1;
}

void GUITable::autoScroll()
{
	if (m_selected >= 0) {
		s32 pos = m_scrollbar->getPos();
		s32 maxpos = m_selected * m_rowheight;
		s32 minpos = maxpos - (AbsoluteRect.getHeight() - m_rowheight);
		if (pos > maxpos)
			m_scrollbar->setPos(maxpos);
		else if (pos < minpos)
			m_scrollbar->setPos(minpos);
	}
}

void GUITable::updateScrollBar()
{
	s32 totalheight = m_rowheight * m_visible_rows.size();
	s32 scrollmax = MYMAX(0, totalheight - AbsoluteRect.getHeight());
	m_scrollbar->setVisible(scrollmax > 0);
	m_scrollbar->setMax(scrollmax);
	m_scrollbar->setSmallStep(m_rowheight);
	m_scrollbar->setLargeStep(2 * m_rowheight);
}

void GUITable::sendTableEvent(s32 column, bool doubleclick)
{
	m_sel_column = column;
	m_sel_doubleclick = doubleclick;
	if (Parent) {
		SEvent e;
		memset(&e, 0, sizeof e);
		e.EventType = EET_GUI_EVENT;
		e.GUIEvent.Caller = this;
		e.GUIEvent.Element = 0;
		e.GUIEvent.EventType = gui::EGET_TABLE_CHANGED;
		Parent->OnEvent(e);
	}
}

void GUITable::getOpenedTrees(std::set<s32> &opened_trees) const
{
	opened_trees.clear();
	s32 rowcount = m_rows.size();
	for (s32 i = 0; i < rowcount - 1; ++i) {
		if (m_rows[i].indent < m_rows[i+1].indent &&
				m_rows[i+1].visible_index != -2)
			opened_trees.insert(i);
	}
}

void GUITable::setOpenedTrees(const std::set<s32> &opened_trees)
{
	s32 old_selected = getSelected();

	std::vector<s32> parents;
	std::vector<s32> closed_parents;

	m_visible_rows.clear();

	for (size_t i = 0; i < m_rows.size(); ++i) {
		Row *row = &m_rows[i];

		// Update list of ancestors
		while (!parents.empty() && m_rows[parents.back()].indent >= row->indent)
			parents.pop_back();
		while (!closed_parents.empty() &&
				m_rows[closed_parents.back()].indent >= row->indent)
			closed_parents.pop_back();

		assert(closed_parents.size() <= parents.size());

		if (closed_parents.empty()) {
			// Visible row
			row->visible_index = m_visible_rows.size();
			m_visible_rows.push_back(i);
		}
		else if (parents.back() == closed_parents.back()) {
			// Invisible row, direct parent is closed
			row->visible_index = -2;
		}
		else {
			// Invisible row, direct parent is open, some ancestor is closed
			row->visible_index = -1;
		}

		// If not a leaf, add to parents list
		if (i < m_rows.size()-1 && row->indent < m_rows[i+1].indent) {
			parents.push_back(i);

			s32 content_index = 0; // "-", open
			if (opened_trees.count(i) == 0) {
				closed_parents.push_back(i);
				content_index = 1; // "+", closed
			}

			// Update all cells of type "tree"
			for (s32 j = 0; j < row->cellcount; ++j)
				if (row->cells[j].content_type == COLUMN_TYPE_TREE)
					row->cells[j].content_index = content_index;
		}
	}

	updateScrollBar();

	setSelected(old_selected);
}

void GUITable::openTree(s32 to_open)
{
	std::set<s32> opened_trees;
	getOpenedTrees(opened_trees);
	opened_trees.insert(to_open);
	setOpenedTrees(opened_trees);
}

void GUITable::closeTree(s32 to_close)
{
	std::set<s32> opened_trees;
	getOpenedTrees(opened_trees);
	opened_trees.erase(to_close);
	setOpenedTrees(opened_trees);
}

// The following function takes a visible row index (hidden rows skipped)
// dir: -1 = left (close), 0 = auto (toggle), 1 = right (open)
void GUITable::toggleVisibleTree(s32 row_i, int dir, bool move_selection)
{
	// Check if the chosen tree is currently open
	const Row *row = getRow(row_i);
	if (row == NULL)
		return;

	bool was_open = false;
	for (s32 j = 0; j < row->cellcount; ++j) {
		if (row->cells[j].content_type == COLUMN_TYPE_TREE) {
			was_open = row->cells[j].content_index == 0;
			break;
		}
	}

	// Check if the chosen tree should be opened
	bool do_open = !was_open;
	if (dir < 0)
		do_open = false;
	else if (dir > 0)
		do_open = true;

	// Close or open the tree; the heavy lifting is done by setOpenedTrees
	if (was_open && !do_open)
		closeTree(m_visible_rows[row_i]);
	else if (!was_open && do_open)
		openTree(m_visible_rows[row_i]);

	// Change selected row if requested by caller,
	// this is useful for keyboard navigation
	if (move_selection) {
		s32 sel = row_i;
		if (was_open && do_open) {
			// Move selection to first child
			const Row *maybe_child = getRow(sel + 1);
			if (maybe_child && maybe_child->indent > row->indent)
				sel++;
		}
		else if (!was_open && !do_open) {
			// Move selection to parent
			assert(getRow(sel) != NULL);
			while (sel > 0 && getRow(sel - 1)->indent >= row->indent)
				sel--;
			sel--;
			if (sel < 0)  // was root already selected?
				sel = row_i;
		}
		if (sel != m_selected) {
			m_selected = sel;
			autoScroll();
			sendTableEvent(0, false);
		}
	}
}

void GUITable::alignContent(Cell *cell, s32 xmax, s32 content_width, s32 align)
{
	// requires that cell.xmin, cell.xmax are properly set
	// align = 0: left aligned, 1: centered, 2: right aligned, 3: inline
	if (align == 0) {
		cell->xpos = cell->xmin;
		cell->xmax = xmax;
	}
	else if (align == 1) {
		cell->xpos = (cell->xmin + xmax - content_width) / 2;
		cell->xmax = xmax;
	}
	else if (align == 2) {
		cell->xpos = xmax - content_width;
		cell->xmax = xmax;
	}
	else {
		// inline alignment: the cells of the column don't have an aligned
		// right border, the right border of each cell depends on the content
		cell->xpos = cell->xmin;
		cell->xmax = cell->xmin + content_width;
	}
}
	Commit message (Collapse)	Author	Age
*	Use UTF-8 instead of narrow	est31	2015-07-08
\| \| \| \| \|	Use wide_to_utf8 and utf8_to_wide instead of wide_to_narrow and narrow_to_wide at almost all places. Only exceptions: test functions for narrow conversion, and chat, which is done in a separate commit.
*	More correct wrap_rows implementation	figec	2015-06-20
\|
*	Fix wrap_rows at inner byte of multibyte sequence	figec	2015-06-18
\| \| \| \|	Also fix UTF-8 inner byte bounds and make unittest for case this fixes.
*	Make wrap_rows not wrap inside utf-8 multibyte sequences	est31	2015-06-17
\| \| \| \| \| \|	Also count multibyte sequences as "one" character. Adds unittest for the bug reporter's case. Fixes #2796.
*	Add utf-8 conversion utilities and re-add intlGUIEditBox	est31	2015-06-13
\|
*	Split ObjDef/ObjDefManager out to objdef.cpp	kwolekr	2015-05-18
\|
*	Make early protocol auth mechanism generic, and add SRP	est31	2015-05-11
\| \| \| \| \| \| \|	Adds everything needed for SRP (and everything works too), but still deactivated, as protocol v25 init packets aren't final yet. Can be activated by changing the LATEST_PROTOCOL_VERSION header to 25 inside networkprotocol.h.
*	Fix fast leaves with texture_clean_transparent enabled.	Aaron Suen	2015-04-26
\|
*	Refactor around translatePassword	est31	2015-04-17
\| \| \| \| \| \| \|	Change types for passed password from wstring to string, which removes converting back and forth in most cases. Move the narrow_to_wide conversion, where its neccessary, closer to irrlicht. Remove trailing spaces in guiPasswordChange.cpp. Make parameters for translatePassword passed as const reference.
*	Fix Android text bug (no text displaying)	Craig Robbins	2015-03-07
\|
*	Reduce gettext wide/narrow and string/char* conversions	ShadowNinja	2015-02-05
\|
*	Make minor style change(unescape_string())	Craig Robbins	2015-01-16
\|
*	Fix unescape_string removing all backslashes	ShadowNinja	2015-01-15
\|
*	Deduplicate code and use stdlib in string functions	ShadowNinja	2015-01-03
\|
*	Fixes for Android build errors. Enable sensor landscape rotation.	KodexKy	2014-11-25
\| \| \| \| \| \| \| \| \| \| \|	Fix typo in Android Makefile ndk path. Fix touchscreen parts of game.cpp to work after Zeno's refactor. Fix isdigit and isspace overload conflict with Android Irrlicht in string.h Enable sensor landscape rotation in Android Manifiest. Add mapgen v5 to Android build. Fix Makefile not checking leveldb. Signed-off-by: Craig Robbins <kde.psych@gmail.com>
*	Cleanup and (mostly) document util/string.h and (very) minor refactoring	Craig Robbins	2014-11-02
\| \| \| \| \|	Updated: Incorporated feedback from 'kahrl' Updated: Moved MinetestApp::boolToCStr() from game.cpp into string.h renaming it bool_to_cstr()
*	Fix bug introduced by me (Zeno)	Craig Robbins	2014-10-29
\|
*	Added names colours and refactored parseColorString()	Craig Robbins	2014-10-29
\|
*	Add [colorize modifier	BlockMen	2014-10-05
\|
*	Standardize tooltip row detection	BlockMen	2014-09-28
\|
*	Use const references for Settings methods	ShadowNinja	2014-09-21
\| \| \| \|	Also check for (this == &other) before locking mutexes.
*	Fix msvc2012 build	sapier	2014-06-29
\|
*	Add formspec api versioning	sapier	2014-06-29
\|
*	Replace usage of long long with u64/s64	ShadowNinja	2014-03-12
\|
*	Add capability to read table flag fields from Lua API	kwolekr	2014-02-09
\|
*	Make flag strings clear specified flag with 'no' prefix	kwolekr	2014-02-08
\| \| \| \| \|	Remove flagmask field from set_mapgen_params table Add small bits of needed documentation
*	Revert "Fix settings to honor numeric conversion errors"	kwolekr	2014-02-05
\| \| \| \|	This reverts commit 3f376a092e1c16429fb52f24736e9da98aff4cd5.
*	Fix settings to honor numeric conversion errors	sapier	2014-02-04
\| \| \| \|	Rename try* non exceptioning functions to *NoEx
*	Implement urlencode and urldecode	Kahrl	2013-12-13
\|
*	Accept hexadecimal and string values for seeds	kwolekr	2013-11-04
\|
*	Change mainmenu texture handling + small misc changes	Kahrl	2013-09-11
\| \| \| \| \| \| \| \| \| \| \| \| \| \|	Texture names must now be escaped in formspec elements image[], background[], image_button[], image_button_exit[]. Instead of special-case handling of texture loading (and unloading which was missing) in guiFormSpecMenu.cpp, use the newly created ISimpleTextureSource interface which is a minimal subset of ITextureSource. There is an implementation of this interface used by GUIEngine (MenuTextureSource). Fix an off-by-one bug in unescape_string; it caused requests for a texture called "\0".
*	Add dummy and LevelDB database backends	Ilya Zhuravlev	2013-09-09
\|
*	Omnicleanup: header cleanup, add ModApiUtil shared between game and mainmenu	Kahrl	2013-08-14
\|
*	Settings: everything != 0 equals true; remove .asm shaders	PilzAdam	2013-07-08
\|
*	Allow any character in formspec strings with escape char	kwolekr	2013-03-05
\|
*	Update Copyright Years	Sfan5	2013-02-24
\|
*	Change Minetest-c55 to Minetest	PilzAdam	2013-02-24
\|
*	Add flag string settings, flat map option	kwolekr	2013-02-06
\|
*	Fix compile under MingW	kwolekr	2013-01-23
\|
*	Added ability to fetch media from remote server (using cURL library)	Ilya Zhuravlev	2012-12-16
\|
*	Enforce stricter world names using a blacklist	Matthew I	2012-09-05
\| \| \| \|	Blacklisted characters are: / \
*	Initially split utility.h to multiple files in util/	Perttu Ahola	2012-06-17