#include <stdarg.h>
#include <string.h>
#include "log.h"
#include "government.h"
#include "improvement.h"
#include "research.h"
#include "tech.h"
#include "client_main.h"
#include "options.h"
#include "tilespec.h"
#include "reqtree.h"
#include "colors_g.h"
#include "sprite_g.h"

Data Structures
struct	tree_node

struct	reqtree

struct	node_and_float

Enumerations
enum	reqtree_edge_type { REQTREE_EDGE = 0 , REQTREE_READY_EDGE , REQTREE_KNOWN_EDGE , REQTREE_ACTIVE_EDGE , REQTREE_GOAL_EDGE }

Functions
static void	add_requirement (struct tree_node node, struct tree_node req)

static struct tree_node *	new_tree_node (void)

static void	node_rectangle_minimum_size (struct tree_node node, int width, int *height)

static void	symmetrize (struct reqtree *tree)

static void	calculate_diagram_layout (struct reqtree *tree)

static struct reqtree *	create_dummy_reqtree (struct player *pplayer, bool show_all)

void	destroy_reqtree (struct reqtree *tree)

static int	longest_path (struct tree_node *node)

static void	longest_path_layering (struct reqtree *tree)

static int	max_provide_layer (struct tree_node *node)

static struct reqtree *	add_dummy_nodes (struct reqtree *tree)

static void	set_layers (struct reqtree *tree)

static int	cmp_func (const void _a, const void _b)

static void	barycentric_sort (struct reqtree *tree, int layer)

static int	count_crossings (struct reqtree *tree, int layer)

static void	swap (struct reqtree *tree, int layer, int order1, int order2)

static void	improve (struct reqtree *tree)

struct reqtree *	create_reqtree (struct player *pplayer, bool show_all)

void	get_reqtree_dimensions (struct reqtree reqtree, int width, int *height)

static enum color_std	node_color (struct tree_node *node)

static enum reqtree_edge_type	get_edge_type (struct tree_node node, struct tree_node dest_node)

static enum color_std	edge_color (struct tree_node node, struct tree_node dest_node)

void	draw_reqtree (struct reqtree tree, struct canvas pcanvas, int canvas_x, int canvas_y, int tt_x, int tt_y, int w, int h)

Tech_type_id	get_tech_on_reqtree (struct reqtree *tree, int x, int y)

bool	find_tech_on_reqtree (struct reqtree tree, Tech_type_id tech, int x, int y, int w, int *h)

Enumeration Type Documentation

◆ reqtree_edge_type

enum reqtree_edge_type

Enumerator
REQTREE_EDGE
REQTREE_READY_EDGE
REQTREE_KNOWN_EDGE
REQTREE_ACTIVE_EDGE
REQTREE_GOAL_EDGE

Definition at line 110 of file reqtree.c.

Function Documentation

◆ add_dummy_nodes()

static struct reqtree * add_dummy_nodes ( struct reqtree * tree )

static

Create new tree which has dummy nodes added. The source tree is completely copied, you can freely deallocate it.

Definition at line 547 of file reqtree.c.

Referenced by create_reqtree().

◆ add_requirement()

static void add_requirement	(	struct tree_node *	node,
		struct tree_node *	req
	)

static

Add requirement edge to node and provide edge to req

Definition at line 121 of file reqtree.c.

Referenced by add_dummy_nodes(), and create_dummy_reqtree().

◆ barycentric_sort()

static void barycentric_sort	(	struct reqtree *	tree,
		int	layer
	)

static

Simple heuristic: Sort nodes on the given layer by the average x-value of its parents.

Definition at line 705 of file reqtree.c.

Referenced by create_reqtree().

◆ calculate_diagram_layout()

static void calculate_diagram_layout ( struct reqtree * tree )

static

Calculate rectangles position and size from the tree. Logical order should already be calculated.

Definition at line 295 of file reqtree.c.

Referenced by create_reqtree().

◆ cmp_func()

static int cmp_func	(	const void *	_a,
		const void *	_b
	)

static

Comparison function used by barycentric_sort.

Definition at line 688 of file reqtree.c.

Referenced by barycentric_sort().

◆ count_crossings()

static int count_crossings	(	struct reqtree *	tree,
		int	layer
	)

static

Calculate number of edge crossings between layer and layer + 1

Definition at line 738 of file reqtree.c.

Referenced by improve().

◆ create_dummy_reqtree()

static struct reqtree * create_dummy_reqtree	(	struct player *	pplayer,
		bool	show_all
	)

static

Create a "dummy" tech tree from current ruleset. This tree is then fleshed out further (see create_reqtree() ). This tree doesn't include dummy edges. Layering and ordering isn't done also.

If pplayer is given, add only techs reachable by that player to tree.

Definition at line 393 of file reqtree.c.

Referenced by create_reqtree().

◆ create_reqtree()

struct reqtree * create_reqtree	(	struct player *	pplayer,
		bool	show_all
	)

Generate optimized tech_tree from current ruleset. You should free it by destroy_reqtree().

If pplayer is not NULL, techs unreachable to that player are not shown.

Definition at line 839 of file reqtree.c.

Referenced by research_diagram::reset(), and science_diagram_data().

◆ destroy_reqtree()

void destroy_reqtree ( struct reqtree * tree )

Free all memory used by tech_tree struct

Definition at line 473 of file reqtree.c.

Referenced by create_reqtree(), research_diagram::reset(), science_diagram_data(), and research_diagram::~research_diagram().

◆ draw_reqtree()

void draw_reqtree	(	struct reqtree *	tree,
		struct canvas *	pcanvas,
		int	canvas_x,
		int	canvas_y,
		int	tt_x,
		int	tt_y,
		int	w,
		int	h
	)

Draw the reqtree diagram!

This draws the given portion of the reqtree diagram (given by (tt_x,tt_y) and (w,h) onto the canvas at position (canvas_x, canvas_y).

Definition at line 1036 of file reqtree.c.

Referenced by science_diagram_update(), science_diagram_update(), and research_diagram::update_reqtree().

◆ edge_color()

static enum color_std edge_color	(	struct tree_node *	node,
		struct tree_node *	dest_node
	)

static

Return a stroke color for an edge between two nodes if node is a dummy, dest_node can be NULL

Definition at line 1010 of file reqtree.c.

Referenced by draw_reqtree().

◆ find_tech_on_reqtree()

bool find_tech_on_reqtree	(	struct reqtree *	tree,
		Tech_type_id	tech,
		int *	x,
		int *	y,
		int *	w,
		int *	h
	)

Return the position of the given tech on the reqtree. Return TRUE iff it was found.

Definition at line 1199 of file reqtree.c.

Referenced by science_diagram_center().

◆ get_edge_type()

static enum reqtree_edge_type get_edge_type	(	struct tree_node *	node,
		struct tree_node *	dest_node
	)

static

Return the type for an edge between two nodes if node is a dummy, dest_node can be NULL

Definition at line 940 of file reqtree.c.

Referenced by edge_color(), and get_edge_type().

◆ get_reqtree_dimensions()

void get_reqtree_dimensions	(	struct reqtree *	reqtree,
		int *	width,
		int *	height
	)

Give the dimensions of the reqtree.

Definition at line 870 of file reqtree.c.

Referenced by research_diagram::reset(), science_diagram_center(), science_diagram_data(), science_diagram_update(), and science_diagram_update().

◆ get_tech_on_reqtree()

Tech_type_id get_tech_on_reqtree	(	struct reqtree *	tree,
		int	x,
		int	y
	)

Return the tech ID at the given position of the reqtree (or A_NONE).

Definition at line 1176 of file reqtree.c.

Referenced by research_diagram::mousePressEvent(), science_diagram_button_release_callback(), science_diagram_left_button_up(), and science_diagram_right_button_up().

◆ improve()

static void improve ( struct reqtree * tree )

static

Try to reduce the number of crossings by swapping two nodes and checking if it improves the situation.

Definition at line 784 of file reqtree.c.

Referenced by create_reqtree().

◆ longest_path()

static int longest_path ( struct tree_node * node )

static

Compute the longest path from this tree_node to the node with no requirements. Store the result in node->layer.

Definition at line 498 of file reqtree.c.

Referenced by longest_path(), and longest_path_layering().

◆ longest_path_layering()

static void longest_path_layering ( struct reqtree * tree )

static

Compute longest_path for all nodes, thus prepare longest path layering

Definition at line 516 of file reqtree.c.

Referenced by create_reqtree().

◆ max_provide_layer()

static int max_provide_layer ( struct tree_node * node )

static

Find the largest value of layer amongst children of the given node

Definition at line 530 of file reqtree.c.

Referenced by add_dummy_nodes().

◆ new_tree_node()

static struct tree_node * new_tree_node ( void )

static

Allocate and initialize new tree node

Definition at line 142 of file reqtree.c.

Referenced by add_dummy_nodes(), and create_dummy_reqtree().

◆ node_color()

static enum color_std node_color ( struct tree_node * node )

static

Return a background color of node's rectangle

Definition at line 884 of file reqtree.c.

Referenced by draw_reqtree().

◆ node_rectangle_minimum_size()

static void node_rectangle_minimum_size	(	struct tree_node *	node,
		int *	width,
		int *	height
	)

static

Return minimum size of the rectangle in pixels on the diagram which corresponds to the given node

Definition at line 159 of file reqtree.c.

Referenced by calculate_diagram_layout().

◆ set_layers()

static void set_layers ( struct reqtree * tree )

static

Calculate layers[] and layer_size[] fields of tree. There should be layer value calculated for each node. Nodes will be put into layers in no particular order.

Definition at line 640 of file reqtree.c.

Referenced by create_reqtree().

◆ swap()

static void swap	(	struct reqtree *	tree,
		int	layer,
		int	order1,
		int	order2
	)

static

Swap positions of two nodes on the same layer

Definition at line 769 of file reqtree.c.

Referenced by improve().

◆ symmetrize()

static void symmetrize ( struct reqtree * tree )

static

Move nodes up and down without changing order but making it more symmetrical. Gravitate towards parents average position.

Definition at line 238 of file reqtree.c.

Referenced by calculate_diagram_layout().

Data Structures

Enumerations

Functions

Enumeration Type Documentation

◆ reqtree_edge_type

Function Documentation

◆ add_dummy_nodes()

◆ add_requirement()

◆ barycentric_sort()

◆ calculate_diagram_layout()

◆ cmp_func()

◆ count_crossings()

◆ create_dummy_reqtree()

◆ create_reqtree()

◆ destroy_reqtree()

◆ draw_reqtree()

◆ edge_color()

◆ find_tech_on_reqtree()

◆ get_edge_type()

◆ get_reqtree_dimensions()

◆ get_tech_on_reqtree()

◆ improve()

◆ longest_path()

◆ longest_path_layering()

◆ max_provide_layer()

◆ new_tree_node()

◆ node_color()

◆ node_rectangle_minimum_size()

◆ set_layers()

◆ swap()

◆ symmetrize()