* @return Panel with company buttons.

 * @post \c *biggest_index contains the largest used index in the tree.

 */

static NWidgetBase *MakeNWidgetCompanyLines(int *biggest_index)

{

	NWidgetVertical *vert = new NWidgetVertical();

	uint line_height = max<uint>(GetSpriteSize(SPR_COMPANY_ICON).height, FONT_HEIGHT_NORMAL) + WD_FRAMERECT_TOP + WD_FRAMERECT_BOTTOM;

	for (int widnum = WID_GL_FIRST_COMPANY; widnum <= WID_GL_LAST_COMPANY; widnum++) {

		NWidgetBackground *panel = new NWidgetBackground(WWT_PANEL, COLOUR_GREY, widnum);

		panel->SetMinimalSize(246, line_height);

		panel->SetFill(1, 0);

		panel->SetDataTip(0x0, STR_GRAPH_KEY_COMPANY_SELECTION_TOOLTIP);

		vert->Add(panel);

	}

	*biggest_index = WID_GL_LAST_COMPANY;

	return vert;

}

static const NWidgetPart _nested_graph_legend_widgets[] = {

	NWidget(NWID_HORIZONTAL),

		NWidget(WWT_CLOSEBOX, COLOUR_GREY),

		NWidget(WWT_CAPTION, COLOUR_GREY), SetDataTip(STR_GRAPH_KEY_CAPTION, STR_TOOLTIP_WINDOW_TITLE_DRAG_THIS),

		NWidget(WWT_SHADEBOX, COLOUR_GREY),

		NWidget(WWT_STICKYBOX, COLOUR_GREY),

	EndContainer(),

	NWidget(WWT_PANEL, COLOUR_GREY, WID_GL_BACKGROUND),

		NWidget(NWID_SPACER), SetMinimalSize(0, 2),

		NWidget(NWID_HORIZONTAL),

			NWidget(NWID_SPACER), SetMinimalSize(2, 0),

			NWidgetFunction(MakeNWidgetCompanyLines),

			NWidget(NWID_SPACER), SetMinimalSize(2, 0),

		EndContainer(),

	EndContainer(),

};

static WindowDesc _graph_legend_desc(

	WDP_AUTO, "graph_legend", 0, 0,

	WC_GRAPH_LEGEND, WC_NONE,

	0,

	_nested_graph_legend_widgets, lengthof(_nested_graph_legend_widgets)

);

static void ShowGraphLegend()

{

	AllocateWindowDescFront<GraphLegendWindow>(&_graph_legend_desc, 0);

}

/** Contains the interval of a graph's data. */

struct ValuesInterval {

	OverflowSafeInt64 highest; ///< Highest value of this interval. Must be zero or greater.

	OverflowSafeInt64 lowest;  ///< Lowest value of this interval. Must be zero or less.

};

/******************/

/* BASE OF GRAPHS */

/*****************/

struct BaseGraphWindow : Window {

protected:

	static const int GRAPH_MAX_DATASETS     =  32;

	static const int GRAPH_AXIS_LINE_COLOUR = PC_BLACK;

	static const int GRAPH_NUM_MONTHS       =  24; ///< Number of months displayed in the graph.

	static const int MIN_GRAPH_NUM_LINES_Y  =   9; ///< Minimal number of horizontal lines to draw.

	static const int MIN_GRID_PIXEL_SIZE    =  20; ///< Minimum distance between graph lines.

	uint excluded_data; ///< bitmask of the datasets that shouldn't be displayed.

	byte num_dataset;

	byte num_on_x_axis;

	byte num_vert_lines;

	static const TextColour graph_axis_label_colour = TC_BLACK; ///< colour of the graph axis label.

	/* The starting month and year that values are plotted against. If month is

	 * 0xFF, use x_values_start and x_values_increment below instead. */

	byte month;

	Year year;

	/* These values are used if the graph is being plotted against values

	 * rather than the dates specified by month and year. */

	uint16 x_values_start;

	uint16 x_values_increment;

	int graph_widget;

	StringID format_str_y_axis;

	byte colours[GRAPH_MAX_DATASETS];

	OverflowSafeInt64 cost[GRAPH_MAX_DATASETS][GRAPH_NUM_MONTHS]; ///< Stored costs for the last #GRAPH_NUM_MONTHS months

	/**

	 * Get the interval that contains the graph's data. Excluded data is ignored to show smaller values in

	 * better detail when disabling higher ones.

	 * @param num_hori_lines Number of horizontal lines to be drawn.

	 * @return Highest and lowest values of the graph (ignoring disabled data).

	 */

	ValuesInterval GetValuesInterval(int num_hori_lines) const

	{

		ValuesInterval current_interval;

		current_interval.highest = INT64_MIN;

		current_interval.lowest  = INT64_MAX;

		for (int i = 0; i < this->num_dataset; i++) {

			if (HasBit(this->excluded_data, i)) continue;

			for (int j = 0; j < this->num_on_x_axis; j++) {

				OverflowSafeInt64 datapoint = this->cost[i][j];

				if (datapoint != INVALID_DATAPOINT) {

					current_interval.highest = max(current_interval.highest, datapoint);

					current_interval.lowest  = min(current_interval.lowest, datapoint);

				}

			}

		}

		/* Prevent showing values too close to the graph limits. */

		current_interval.highest = (11 * current_interval.highest) / 10;

		current_interval.lowest =  (11 * current_interval.lowest) / 10;

		/* Always include zero in the shown range. */

		double abs_lower  = (current_interval.lowest > 0) ? 0 : (double)abs(current_interval.lowest);

		double abs_higher = (current_interval.highest < 0) ? 0 : (double)current_interval.highest;

		int num_pos_grids;

		int64 grid_size;

		if (abs_lower != 0 || abs_higher != 0) {

			/* The number of grids to reserve for the positive part is: */

			num_pos_grids = (int)floor(0.5 + num_hori_lines * abs_higher / (abs_higher + abs_lower));

			/* If there are any positive or negative values, force that they have at least one grid. */

			if (num_pos_grids == 0 && abs_higher != 0) num_pos_grids++;

			if (num_pos_grids == num_hori_lines && abs_lower != 0) num_pos_grids--;

			/* Get the required grid size for each side and use the maximum one. */

			int64 grid_size_higher = (abs_higher > 0) ? ((int64)abs_higher + num_pos_grids - 1) / num_pos_grids : 0;

			int64 grid_size_lower = (abs_lower > 0) ? ((int64)abs_lower + num_hori_lines - num_pos_grids - 1) / (num_hori_lines - num_pos_grids) : 0;

			grid_size = max(grid_size_higher, grid_size_lower);

		} else {

			/* If both values are zero, show an empty graph. */

			num_pos_grids = num_hori_lines / 2;

			grid_size = 1;

		}

		current_interval.highest = num_pos_grids * grid_size;

		current_interval.lowest = -(num_hori_lines - num_pos_grids) * grid_size;

		return current_interval;

	}

	/**

	 * Get width for Y labels.

	 * @param current_interval Interval that contains all of the graph data.

	 * @param num_hori_lines Number of horizontal lines to be drawn.

	 */

	uint GetYLabelWidth(ValuesInterval current_interval, int num_hori_lines) const

	{

		/* draw text strings on the y axis */

		int64 y_label = current_interval.highest;

		int64 y_label_separation = (current_interval.highest - current_interval.lowest) / num_hori_lines;

		uint max_width = 0;

		for (int i = 0; i < (num_hori_lines + 1); i++) {

			SetDParam(0, this->format_str_y_axis);

			SetDParam(1, y_label);

			Dimension d = GetStringBoundingBox(STR_GRAPH_Y_LABEL);

			if (d.width > max_width) max_width = d.width;

			y_label -= y_label_separation;

		}

		return max_width;

	}

	/**

	 * Actually draw the graph.

	 * @param r the rectangle of the data field of the graph

	 */

	void DrawGraph(Rect r) const

	{

		uint x, y;               ///< Reused whenever x and y coordinates are needed.

		ValuesInterval interval; ///< Interval that contains all of the graph data.

		int x_axis_offset;       ///< Distance from the top of the graph to the x axis.

		/* the colours and cost array of GraphDrawer must accommodate

		 * both values for cargo and companies. So if any are higher, quit */

		assert_compile(GRAPH_MAX_DATASETS >= (int)NUM_CARGO && GRAPH_MAX_DATASETS >= (int)MAX_COMPANIES);

		assert(this->num_vert_lines > 0);

		byte grid_colour = _colour_gradient[COLOUR_GREY][4];

		/* Rect r will be adjusted to contain just the graph, with labels being

		 * placed outside the area. */

		r.top    += 5 + GetCharacterHeight(FS_SMALL) / 2;

		r.bottom -= (this->month == 0xFF ? 1 : 3) * GetCharacterHeight(FS_SMALL) + 4;