/*
Minetest
Copyright (C) 2010-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 "voxelalgorithms.h"
#include "nodedef.h"
#include "mapblock.h"
#include "map.h"

namespace voxalgo
{

/*!
 * A direction.
 * 0=X+
 * 1=Y+
 * 2=Z+
 * 3=Z-
 * 4=Y-
 * 5=X-
 * 6=no direction
 * Two directions are opposite only if their sum is 5.
 */
typedef u8 direction;
/*!
 * Relative node position.
 * This represents a node's position in its map block.
 * All coordinates must be between 0 and 15.
 */
typedef v3s16 relative_v3;
/*!
 * Position of a map block (block coordinates).
 * One block_pos unit is as long as 16 node position units.
 */
typedef v3s16 mapblock_v3;

//! Contains information about a node whose light is about to change.
struct ChangingLight {
	//! Relative position of the node in its map block.
	relative_v3 rel_position;
	//! Position of the node's block.
	mapblock_v3 block_position;
	//! Pointer to the node's block.
	MapBlock *block = NULL;
	/*!
	 * Direction from the node that caused this node's changing
	 * to this node.
	 */
	direction source_direction = 6;

	ChangingLight() = default;

	ChangingLight(const relative_v3 &rel_pos, const mapblock_v3 &block_pos,
		MapBlock *b, direction source_dir) :
		rel_position(rel_pos),
		block_position(block_pos),
		block(b),
		source_direction(source_dir)
	{}
};

/*!
 * A fast, priority queue-like container to contain ChangingLights.
 * The ChangingLights are ordered by the given light levels.
 * The brightest ChangingLight is returned first.
 */
struct LightQueue {
	//! For each light level there is a vector.
	std::vector<ChangingLight> lights[LIGHT_SUN + 1];
	//! Light of the brightest ChangingLight in the queue.
	u8 max_light;

	/*!
	 * Creates a LightQueue.
	 * \param reserve for each light level that many slots are reserved.
	 */
	LightQueue(size_t reserve)
	{
		max_light = LIGHT_SUN;
		for (u8 i = 0; i <= LIGHT_SUN; i++) {
			lights[i].reserve(reserve);
		}
	}

	/*!
	 * Returns the next brightest ChangingLight and
	 * removes it from the queue.
	 * If there were no elements in the queue, the given parameters
	 * remain unmodified.
	 * \param light light level of the popped ChangingLight
	 * \param data the ChangingLight that was popped
	 * \returns true if there was a ChangingLight in the queue.
	 */
	bool next(u8 &light, ChangingLight &data)
	{
		while (lights[max_light].empty()) {
			if (max_light == 0) {
				return false;
			}
			max_light--;
		}
		light = max_light;
		data = lights[max_light].back();
		lights[max_light].pop_back();
		return true;
	}

	/*!
	 * Adds an element to the queue.
	 * The parameters are the same as in ChangingLight's constructor.
	 * \param light light level of the ChangingLight
	 */
	inline void push(u8 light, const relative_v3 &rel_pos,
		const mapblock_v3 &block_pos, MapBlock *block,
		direction source_dir)
	{
		assert(light <= LIGHT_SUN);
		lights[light].emplace_back(rel_pos, block_pos, block, source_dir);
	}
};

/*!
 * This type of light queue is for unlighting.
 * A node can be pushed in it only if its raw light is zero.
 * This prevents pushing nodes twice into this queue.
 * The light of the pushed ChangingLight must be the
 * light of the node before unlighting it.
 */
typedef LightQueue UnlightQueue;
/*!
 * This type of light queue is for spreading lights.
 * While spreading lights, all the nodes in it must
 * have the same light as the light level the ChangingLights
 * were pushed into this queue with. This prevents unnecessary
 * re-pushing of the nodes into the queue.
 * If a node doesn't let light trough but emits light, it can be added
 * too.
 */
typedef LightQueue ReLightQueue;

/*!
 * neighbor_dirs[i] points towards
 * the direction i.
 * See the definition of the type "direction"
 */
const static v3s16 neighbor_dirs[6] = {
	v3s16(1, 0, 0), // right
	v3s16(0, 1, 0), // top
	v3s16(0, 0, 1), // back
	v3s16(0, 0, -1), // front
	v3s16(0, -1, 0), // bottom
	v3s16(-1, 0, 0), // left
};

/*!
 * Transforms the given map block offset by one node towards
 * the specified direction.
 * \param dir the direction of the transformation
 * \param rel_pos the node's relative position in its map block
 * \param block_pos position of the node's block
 */
bool step_rel_block_pos(direction dir, relative_v3 &rel_pos,
	mapblock_v3 &block_pos)
{
	switch (dir) {
	case 0:
		if (rel_pos.X < MAP_BLOCKSIZE - 1) {
			rel_pos.X++;
		} else {
			rel_pos.X = 0;
			block_pos.X++;
			return true;
		}
		break;
	case 1:
		if (rel_pos.Y < MAP_BLOCKSIZE - 1) {
			rel_pos.Y++;
		} else {
			rel_pos.Y = 0;
			block_pos.Y++;
			return true;
		}
		break;
	case 2:
		if (rel_pos.Z < MAP_BLOCKSIZE - 1) {
			rel_pos.Z++;
		} else {
			rel_pos.Z = 0;
			block_pos.Z++;
			return true;
		}
		break;
	case 3:
		if (rel_pos.Z > 0) {
			rel_pos.Z--;
		} else {
			rel_pos.Z = MAP_BLOCKSIZE - 1;
			block_pos.Z--;
			return true;
		}
		break;
	case 4:
		if (rel_pos.Y > 0) {
			rel_pos.Y--;
		} else {
			rel_pos.Y = MAP_BLOCKSIZE - 1;
			block_pos.Y--;
			return true;
		}
		break;
	case 5:
		if (rel_pos.X > 0) {
			rel_pos.X--;
		} else {
			rel_pos.X = MAP_BLOCKSIZE - 1;
			block_pos.X--;
			return true;
		}
		break;
	}
	return false;
}

/*
 * Removes all light that is potentially emitted by the specified
 * light sources. These nodes will have zero light.
 * Returns all nodes whose light became zero but should be re-lighted.
 *
 * \param bank the light bank in which the procedure operates
 * \param from_nodes nodes whose light is removed
 * \param light_sources nodes that should be re-lighted
 * \param modified_blocks output, all modified map blocks are added to this
 */
void unspread_light(Map *map, const NodeDefManager *nodemgr, LightBank bank,
	UnlightQueue &from_nodes, ReLightQueue &light_sources,
	std::map<v3s16, MapBlock*> &modified_blocks)
{
	// Stores data popped from from_nodes
	u8 current_light;
	ChangingLight current;
	// Data of the current neighbor
	mapblock_v3 neighbor_block_pos;
	relative_v3 neighbor_rel_pos;
	// A dummy boolean
	bool is_valid_position;
	// Direction of the brightest neighbor of the node
	direction source_dir;
	while (from_nodes.next(current_light, current)) {
		// For all nodes that need unlighting

		// There is no brightest neighbor
		source_dir = 6;
		// The current node
		const MapNode &node = current.block->getNodeNoCheck(
			current.rel_position, &is_valid_position);
		const ContentFeatures &f = nodemgr->get(node);
		// If the node emits light, it behaves like it had a
		// brighter neighbor.
		u8 brightest_neighbor_light = f.light_source + 1;
		for (direction i = 0; i < 6; i++) {
			//For each neighbor

			// The node that changed this node has already zero light
			// and it can't give light to this node
			if (current.source_direction + i == 5) {
				continue;
			}
			// Get the neighbor's position and block
			neighbor_rel_pos = current.rel_position;
			neig 
<span class="hl com">/* start css.sty */</span>
<span class="hl kwc">.ecsx-1728</span><span class="hl opt">{</span><span class="hl kwa">font-size</span><span class="hl opt">:</span><span class="hl num">170</span><span class="hl opt">%;</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1728</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1728</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1728</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1728</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1728</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecst-1440</span><span class="hl opt">{</span><span class="hl kwa">font-size</span><span class="hl opt">:</span><span class="hl num">140</span><span class="hl opt">%;}</span>
<span class="hl kwc">.ecsx-1200</span><span class="hl opt">{</span><span class="hl kwa">font-size</span><span class="hl opt">:</span><span class="hl num">120</span><span class="hl opt">%;</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1200</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1200</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1200</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1200</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1200</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecsx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecbx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecbx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecbx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecbx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecbx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
<span class="hl kwc">.ecbx-1000</span><span class="hl opt">{</span> <span class="hl kwa">font-weight</span><span class="hl opt">:</span> bold<span class="hl opt">;}</span>
p<span class="hl opt">.</span>noindent <span class="hl opt">{</span> <span class="hl kwa">text-indent</span><span class="hl opt">:</span> <span class="hl num">0em</span> <span class="hl opt">}</span>
td p<span class="hl opt">.</span>noindent <span class="hl opt">{</span> <span class="hl kwa">text-indent</span><span class="hl opt">:</span> <span class="hl num">0em</span><span class="hl opt">;</span> <span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">0em</span><span class="hl opt">; }</span>
p<span class="hl opt">.</span>nopar <span class="hl opt">{</span> <span class="hl kwa">text-indent</span><span class="hl opt">:</span> <span class="hl num">0em</span><span class="hl opt">; }</span>
p<span class="hl opt">.</span>indent<span class="hl opt">{</span> <span class="hl kwa">text-indent</span><span class="hl opt">:</span> <span class="hl num">1.5em</span> <span class="hl opt">}</span>
<span class="hl kwb">&#64;media</span> print <span class="hl opt">{</span>div<span class="hl opt">.</span>crosslinks <span class="hl opt">{</span><span class="hl kwa">visibility</span><span class="hl opt">:</span>hidden<span class="hl opt">;}}</span>
a img <span class="hl opt">{</span> <span class="hl kwa">border-top</span><span class="hl opt">:</span> <span class="hl num">0</span><span class="hl opt">;</span> <span class="hl kwa">border-left</span><span class="hl opt">:</span> <span class="hl num">0</span><span class="hl opt">;</span> <span class="hl kwa">border-right</span><span class="hl opt">:</span> <span class="hl num">0</span><span class="hl opt">; }</span>
center <span class="hl opt">{</span> <span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">1em</span><span class="hl opt">;</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span><span class="hl num">1em</span><span class="hl opt">; }</span>
td center <span class="hl opt">{</span> <span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">0em</span><span class="hl opt">;</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span><span class="hl num">0em</span><span class="hl opt">; }</span>
<span class="hl kwc">.Canvas</span> <span class="hl opt">{</span> <span class="hl kwa">position</span><span class="hl opt">:</span>relative<span class="hl opt">; }</span>
img<span class="hl opt">.</span>math<span class="hl opt">{</span><span class="hl kwa">vertical-align</span><span class="hl opt">:</span>middle<span class="hl opt">;}</span>
li p<span class="hl opt">.</span>indent <span class="hl opt">{</span> <span class="hl kwa">text-indent</span><span class="hl opt">:</span> <span class="hl num">0em</span> <span class="hl opt">}</span>
li <span class="hl kwa">p</span><span class="hl opt">:</span>first-child<span class="hl opt">{</span> <span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">0em</span><span class="hl opt">; }</span>
li <span class="hl kwa">p</span><span class="hl opt">:</span>last-child<span class="hl opt">,</span> li <span class="hl kwa">div</span><span class="hl opt">:</span>last-child <span class="hl opt">{</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span><span class="hl num">0.5em</span><span class="hl opt">; }</span>
li p<span class="hl opt">~</span><span class="hl kwa">ul</span><span class="hl opt">:</span>last-child<span class="hl opt">,</span> li p<span class="hl opt">~</span><span class="hl kwa">ol</span><span class="hl opt">:</span>last-child<span class="hl opt">{</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span><span class="hl num">0.5em</span><span class="hl opt">; }</span>
<span class="hl kwc">.enumerate1</span> <span class="hl opt">{</span><span class="hl kwa">list-style-type</span><span class="hl opt">:</span>decimal<span class="hl opt">;}</span>
<span class="hl kwc">.enumerate2</span> <span class="hl opt">{</span><span class="hl kwa">list-style-type</span><span class="hl opt">:</span>lower-alpha<span class="hl opt">;}</span>
<span class="hl kwc">.enumerate3</span> <span class="hl opt">{</span><span class="hl kwa">list-style-type</span><span class="hl opt">:</span>lower-roman<span class="hl opt">;}</span>
<span class="hl kwc">.enumerate4</span> <span class="hl opt">{</span><span class="hl kwa">list-style-type</span><span class="hl opt">:</span>upper-alpha<span class="hl opt">;}</span>
div<span class="hl opt">.</span>newtheorem <span class="hl opt">{</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span> <span class="hl num">2em</span><span class="hl opt">;</span> <span class="hl kwa">margin-top</span><span class="hl opt">:</span> <span class="hl num">2em</span><span class="hl opt">;}</span>
<span class="hl kwc">.obeylines-h,.obeylines-v</span> <span class="hl opt">{</span><span class="hl kwa">white-space</span><span class="hl opt">:</span> nowrap<span class="hl opt">; }</span>
div<span class="hl opt">.</span>obeylines-v p <span class="hl opt">{</span> <span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">0</span><span class="hl opt">;</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span><span class="hl num">0</span><span class="hl opt">; }</span>
<span class="hl kwc">.overline</span><span class="hl opt">{</span> <span class="hl kwa">text-decoration</span><span class="hl opt">:</span>overline<span class="hl opt">; }</span>
<span class="hl kwc">.overline img</span><span class="hl opt">{</span> <span class="hl kwa">border-top</span><span class="hl opt">:</span> <span class="hl num">1px</span> solid black<span class="hl opt">; }</span>
td<span class="hl opt">.</span>displaylines <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">;</span> <span class="hl kwa">white-space</span><span class="hl opt">:</span>nowrap<span class="hl opt">;}</span>
<span class="hl kwc">.centerline</span> <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">;}</span>
<span class="hl kwc">.rightline</span> <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>right<span class="hl opt">;}</span>
div<span class="hl opt">.</span>verbatim <span class="hl opt">{</span><span class="hl kwa">font-family</span><span class="hl opt">:</span> monospace<span class="hl opt">;</span> <span class="hl kwa">white-space</span><span class="hl opt">:</span> nowrap<span class="hl opt">;</span> <span class="hl kwa">text-align</span><span class="hl opt">:</span>left<span class="hl opt">;</span> <span class="hl kwa">clear</span><span class="hl opt">:</span>both<span class="hl opt">; }</span>
<span class="hl kwc">.fbox</span> <span class="hl opt">{</span><span class="hl kwa">padding-left</span><span class="hl opt">:</span><span class="hl num">3.0pt</span><span class="hl opt">;</span> <span class="hl kwa">padding-right</span><span class="hl opt">:</span><span class="hl num">3.0pt</span><span class="hl opt">;</span> <span class="hl kwa">text-indent</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">;</span> <span class="hl kwa">border</span><span class="hl opt">:</span>solid black <span class="hl num">0.4pt</span><span class="hl opt">; }</span>
div<span class="hl opt">.</span>fbox <span class="hl opt">{</span><span class="hl kwa">display</span><span class="hl opt">:</span>table<span class="hl opt">}</span>
div<span class="hl opt">.</span>center div<span class="hl opt">.</span>fbox <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">;</span> <span class="hl kwa">clear</span><span class="hl opt">:</span>both<span class="hl opt">;</span> <span class="hl kwa">padding-left</span><span class="hl opt">:</span><span class="hl num">3.0pt</span><span class="hl opt">;</span> <span class="hl kwa">padding-right</span><span class="hl opt">:</span><span class="hl num">3.0pt</span><span class="hl opt">;</span> <span class="hl kwa">text-indent</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">;</span> <span class="hl kwa">border</span><span class="hl opt">:</span>solid black <span class="hl num">0.4pt</span><span class="hl opt">; }</span>
div<span class="hl opt">.</span>minipage<span class="hl opt">{</span><span class="hl kwa">width</span><span class="hl opt">:</span><span class="hl num">100</span><span class="hl opt">%;}</span>
div<span class="hl opt">.</span>center<span class="hl opt">,</span> div<span class="hl opt">.</span>center div<span class="hl opt">.</span>center <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span> center<span class="hl opt">;</span> <span class="hl kwa">margin-left</span><span class="hl opt">:</span><span class="hl num">1em</span><span class="hl opt">;</span> <span class="hl kwa">margin-right</span><span class="hl opt">:</span><span class="hl num">1em</span><span class="hl opt">;}</span>
div<span class="hl opt">.</span>center div <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span> left<span class="hl opt">;}</span>
div<span class="hl opt">.</span>flushright<span class="hl opt">,</span> div<span class="hl opt">.</span>flushright div<span class="hl opt">.</span>flushright <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span> right<span class="hl opt">;}</span>
div<span class="hl opt">.</span>flushright div <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span> left<span class="hl opt">;}</span>
div<span class="hl opt">.</span>flushleft <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span> left<span class="hl opt">;}</span>
<span class="hl kwc">.underline</span><span class="hl opt">{</span> <span class="hl kwa">text-decoration</span><span class="hl opt">:</span>underline<span class="hl opt">; }</span>
<span class="hl kwc">.underline img</span><span class="hl opt">{</span> <span class="hl kwa">border-bottom</span><span class="hl opt">:</span> <span class="hl num">1px</span> solid black<span class="hl opt">;</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span><span class="hl num">1pt</span><span class="hl opt">; }</span>
<span class="hl kwc">.framebox-c, .framebox-l, .framebox-r</span> <span class="hl opt">{</span> <span class="hl kwa">padding-left</span><span class="hl opt">:</span><span class="hl num">3.0pt</span><span class="hl opt">;</span> <span class="hl kwa">padding-right</span><span class="hl opt">:</span><span class="hl num">3.0pt</span><span class="hl opt">;</span> <span class="hl kwa">text-indent</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">;</span> <span class="hl kwa">border</span><span class="hl opt">:</span>solid black <span class="hl num">0.4pt</span><span class="hl opt">; }</span>
<span class="hl kwc">.framebox-c</span> <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">;}</span>
<span class="hl kwc">.framebox-l</span> <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>left<span class="hl opt">;}</span>
<span class="hl kwc">.framebox-r</span> <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>right<span class="hl opt">;}</span>
span<span class="hl opt">.</span>thank-mark<span class="hl opt">{</span> <span class="hl kwa">vertical-align</span><span class="hl opt">:</span> super <span class="hl opt">}</span>
span<span class="hl opt">.</span>footnote-mark sup<span class="hl opt">.</span>textsuperscript<span class="hl opt">,</span> span<span class="hl opt">.</span>footnote-mark a sup<span class="hl opt">.</span>textsuperscript<span class="hl opt">{</span> <span class="hl kwa">font-size</span><span class="hl opt">:</span><span class="hl num">80</span><span class="hl opt">%; }</span>
div<span class="hl opt">.</span>tabular<span class="hl opt">,</span> div<span class="hl opt">.</span>center div<span class="hl opt">.</span>tabular <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span> center<span class="hl opt">;</span> <span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">0.5em</span><span class="hl opt">;</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span><span class="hl num">0.5em</span><span class="hl opt">; }</span>
table<span class="hl opt">.</span>tabular td p<span class="hl opt">{</span><span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">0em</span><span class="hl opt">;}</span>
table<span class="hl opt">.</span>tabular <span class="hl opt">{</span><span class="hl kwa">margin-left</span><span class="hl opt">:</span> auto<span class="hl opt">;</span> <span class="hl kwa">margin-right</span><span class="hl opt">:</span> auto<span class="hl opt">;}</span>
td <span class="hl kwa">p</span><span class="hl opt">:</span>first-child<span class="hl opt">{</span> <span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">0em</span><span class="hl opt">; }</span>
td <span class="hl kwa">p</span><span class="hl opt">:</span>last-child<span class="hl opt">{</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span><span class="hl num">0em</span><span class="hl opt">; }</span>
div<span class="hl opt">.</span>td00<span class="hl opt">{</span> <span class="hl kwa">margin-left</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">;</span> <span class="hl kwa">margin-right</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">; }</span>
div<span class="hl opt">.</span>td01<span class="hl opt">{</span> <span class="hl kwa">margin-left</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">;</span> <span class="hl kwa">margin-right</span><span class="hl opt">:</span><span class="hl num">5pt</span><span class="hl opt">; }</span>
div<span class="hl opt">.</span>td10<span class="hl opt">{</span> <span class="hl kwa">margin-left</span><span class="hl opt">:</span><span class="hl num">5pt</span><span class="hl opt">;</span> <span class="hl kwa">margin-right</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">; }</span>
div<span class="hl opt">.</span>td11<span class="hl opt">{</span> <span class="hl kwa">margin-left</span><span class="hl opt">:</span><span class="hl num">5pt</span><span class="hl opt">;</span> <span class="hl kwa">margin-right</span><span class="hl opt">:</span><span class="hl num">5pt</span><span class="hl opt">; }</span>
table<span class="hl opt">[</span>rules<span class="hl opt">] {</span><span class="hl kwa">border-left</span><span class="hl opt">:</span>solid black <span class="hl num">0.4pt</span><span class="hl opt">;</span> <span class="hl kwa">border-right</span><span class="hl opt">:</span>solid black <span class="hl num">0.4pt</span><span class="hl opt">; }</span>
td<span class="hl opt">.</span>td00<span class="hl opt">{</span> <span class="hl kwa">padding-left</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">;</span> <span class="hl kwa">padding-right</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">; }</span>
td<span class="hl opt">.</span>td01<span class="hl opt">{</span> <span class="hl kwa">padding-left</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">;</span> <span class="hl kwa">padding-right</span><span class="hl opt">:</span><span class="hl num">5pt</span><span class="hl opt">; }</span>
td<span class="hl opt">.</span>td10<span class="hl opt">{</span> <span class="hl kwa">padding-left</span><span class="hl opt">:</span><span class="hl num">5pt</span><span class="hl opt">;</span> <span class="hl kwa">padding-right</span><span class="hl opt">:</span><span class="hl num">0pt</span><span class="hl opt">; }</span>
td<span class="hl opt">.</span>td11<span class="hl opt">{</span> <span class="hl kwa">padding-left</span><span class="hl opt">:</span><span class="hl num">5pt</span><span class="hl opt">;</span> <span class="hl kwa">padding-right</span><span class="hl opt">:</span><span class="hl num">5pt</span><span class="hl opt">; }</span>
table<span class="hl opt">[</span>rules<span class="hl opt">] {</span><span class="hl kwa">border-left</span><span class="hl opt">:</span>solid black <span class="hl num">0.4pt</span><span class="hl opt">;</span> <span class="hl kwa">border-right</span><span class="hl opt">:</span>solid black <span class="hl num">0.4pt</span><span class="hl opt">; }</span>
<span class="hl kwc">.hline hr, .cline hr</span><span class="hl opt">{</span> <span class="hl kwa">height</span> <span class="hl opt">:</span> <span class="hl num">1px</span><span class="hl opt">;</span> <span class="hl kwa">margin</span><span class="hl opt">:</span><span class="hl num">0px</span><span class="hl opt">; }</span>
<span class="hl kwc">.tabbing-right</span> <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>right<span class="hl opt">;}</span>
span<span class="hl opt">.</span>TEX <span class="hl opt">{</span><span class="hl kwa">letter-spacing</span><span class="hl opt">: -</span><span class="hl num">0.125em</span><span class="hl opt">; }</span>
span<span class="hl opt">.</span>TEX span<span class="hl opt">.</span>E<span class="hl opt">{</span> <span class="hl kwa">position</span><span class="hl opt">:</span>relative<span class="hl opt">;</span><span class="hl kwa">top</span><span class="hl opt">:</span><span class="hl num">0.5ex</span><span class="hl opt">;</span><span class="hl kwa">left</span><span class="hl opt">:-</span><span class="hl num">0.0417em</span><span class="hl opt">;}</span>
a span<span class="hl opt">.</span>TEX span<span class="hl opt">.</span>E <span class="hl opt">{</span><span class="hl kwa">text-decoration</span><span class="hl opt">:</span> none<span class="hl opt">; }</span>
span<span class="hl opt">.</span>LATEX span<span class="hl opt">.</span>A<span class="hl opt">{</span> <span class="hl kwa">position</span><span class="hl opt">:</span>relative<span class="hl opt">;</span> <span class="hl kwa">top</span><span class="hl opt">:-</span><span class="hl num">0.5ex</span><span class="hl opt">;</span> <span class="hl kwa">left</span><span class="hl opt">:-</span><span class="hl num">0.4em</span><span class="hl opt">;</span> <span class="hl kwa">font-size</span><span class="hl opt">:</span><span class="hl num">85</span><span class="hl opt">%;}</span>
span<span class="hl opt">.</span>LATEX span<span class="hl opt">.</span>TEX<span class="hl opt">{</span> <span class="hl kwa">position</span><span class="hl opt">:</span>relative<span class="hl opt">;</span> <span class="hl kwa">left</span><span class="hl opt">: -</span><span class="hl num">0.4em</span><span class="hl opt">; }</span>
div<span class="hl opt">.</span>float<span class="hl opt">,</span> div<span class="hl opt">.</span>figure <span class="hl opt">{</span><span class="hl kwa">margin-left</span><span class="hl opt">:</span> auto<span class="hl opt">;</span> <span class="hl kwa">margin-right</span><span class="hl opt">:</span> auto<span class="hl opt">;}</span>
div<span class="hl opt">.</span>float img <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">;}</span>
div<span class="hl opt">.</span>figure img <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">;}</span>
<span class="hl kwc">.marginpar</span> <span class="hl opt">{</span><span class="hl kwa">width</span><span class="hl opt">:</span><span class="hl num">20</span><span class="hl opt">%;</span> <span class="hl kwa">float</span><span class="hl opt">:</span>right<span class="hl opt">;</span> <span class="hl kwa">text-align</span><span class="hl opt">:</span>left<span class="hl opt">;</span> <span class="hl kwa">margin-left</span><span class="hl opt">:</span>auto<span class="hl opt">;</span> <span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">0.5em</span><span class="hl opt">;</span> <span class="hl kwa">font-size</span><span class="hl opt">:</span><span class="hl num">85</span><span class="hl opt">%;</span> <span class="hl kwa">text-decoration</span><span class="hl opt">:</span>underline<span class="hl opt">;}</span>
<span class="hl kwc">.marginpar p</span><span class="hl opt">{</span><span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">0.4em</span><span class="hl opt">;</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span><span class="hl num">0.4em</span><span class="hl opt">;}</span>
table<span class="hl opt">.</span>equation <span class="hl opt">{</span><span class="hl kwa">width</span><span class="hl opt">:</span><span class="hl num">100</span><span class="hl opt">%;}</span>
<span class="hl kwc">.equation td</span><span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">; }</span>
td<span class="hl opt">.</span>equation <span class="hl opt">{</span> <span class="hl kwa">margin-top</span><span class="hl opt">:</span><span class="hl num">1em</span><span class="hl opt">;</span> <span class="hl kwa">margin-bottom</span><span class="hl opt">:</span><span class="hl num">1em</span><span class="hl opt">; }</span> 
td<span class="hl opt">.</span>equation-label <span class="hl opt">{</span> <span class="hl kwa">width</span><span class="hl opt">:</span><span class="hl num">5</span><span class="hl opt">%;</span> <span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">; }</span>
td<span class="hl opt">.</span>eqnarray4 <span class="hl opt">{</span> <span class="hl kwa">width</span><span class="hl opt">:</span><span class="hl num">5</span><span class="hl opt">%;</span> <span class="hl kwa">white-space</span><span class="hl opt">:</span> normal<span class="hl opt">; }</span>
td<span class="hl opt">.</span>eqnarray2 <span class="hl opt">{</span> <span class="hl kwa">width</span><span class="hl opt">:</span><span class="hl num">5</span><span class="hl opt">%; }</span>
table<span class="hl opt">.</span>eqnarray-star<span class="hl opt">,</span> table<span class="hl opt">.</span>eqnarray <span class="hl opt">{</span><span class="hl kwa">width</span><span class="hl opt">:</span><span class="hl num">100</span><span class="hl opt">%;}</span>
div<span class="hl opt">.</span>eqnarray<span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">;}</span>
div<span class="hl opt">.</span>array <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">;}</span>
div<span class="hl opt">.</span>pmatrix <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">;}</span>
table<span class="hl opt">.</span>pmatrix <span class="hl opt">{</span><span class="hl kwa">width</span><span class="hl opt">:</span><span class="hl num">100</span><span class="hl opt">%;}</span>
span<span class="hl opt">.</span>pmatrix img<span class="hl opt">{</span><span class="hl kwa">vertical-align</span><span class="hl opt">:</span>middle<span class="hl opt">;}</span>
div<span class="hl opt">.</span>pmatrix <span class="hl opt">{</span><span class="hl kwa">text-align</span><span class="hl opt">:</span>center<span class="hl opt">;}</span>
table<span class="hl opt">.</span>pmatrix <span class="hl opt">{</span><span class="hl kwa">width</span><span class="hl opt">:</span><span class="hl num">100</span><span class="hl opt">%;}</span>
span<span class="hl opt">.</span>bar-css <span class="hl opt">{</span><span class="hl kwa">text-decoration</span><span class="hl opt">:</span>overline<span class="hl opt">;}</span>
img<span class="hl opt">.</span>cdots<span class="hl opt">{</span><span class="hl kwa">vertical-align</span><span class="hl opt">:</span>middle<span class="hl opt">;}</span>
<span class="hl kwc">.figure img.graphics</span> <span class="hl opt">{</span><span class="hl kwa">margin-left</span><span class="hl opt">:</span><span class="hl num">10</span><span class="hl opt">%;}</span>
<span class="hl com">/* end css.sty */</span>

</code></pre></td></tr></table>
</div> <!-- class=content -->
<div class='footer'>generated by <a href='https://git.zx2c4.com/cgit/about/'>cgit v1.2.3</a> (<a href='https://git-scm.com/'>git 2.39.1</a>) at 2024-11-08 13:39:40 +0000</div>
</div> <!-- id=cgit -->
</body>
</html>
= MAP_BLOCKSIZE - 1; y >= 0; y--) {
			MapNode n = block->getNodeNoCheck(x, y, z, &is_valid);
			// Ignore IGNORE nodes, these are not generated yet.
			if (n.getContent() == CONTENT_IGNORE)
				continue;
			const ContentFeatures &f = ndef->get(n.getContent());
			if (lig && !f.sunlight_propagates) {
				// Sunlight is stopped.
				lig = false;
			}
			// Reset light
			n.setLight(LIGHTBANK_DAY, lig ? 15 : 0, f);
			n.setLight(LIGHTBANK_NIGHT, 0, f);
			block->setNodeNoCheck(x, y, z, n);
		}
		// Output outgoing light.
		light[z][x] = lig;
	}
}

void repair_block_light(ServerMap *map, MapBlock *block,
	std::map<v3s16, MapBlock*> *modified_blocks)
{
	if (!block || block->isDummy())
		return;
	const NodeDefManager *ndef = map->getNodeDefManager();
	// First queue is for day light, second is for night light.
	UnlightQueue unlight[] = { UnlightQueue(256), UnlightQueue(256) };
	ReLightQueue relight[] = { ReLightQueue(256), ReLightQueue(256) };
	// Will hold sunlight data.
	bool lights[MAP_BLOCKSIZE][MAP_BLOCKSIZE];
	SunlightPropagationData data;
	// Dummy boolean.
	bool is_valid;

	// --- STEP 1: reset everything to sunlight

	mapblock_v3 blockpos = block->getPos();
	(*modified_blocks)[blockpos] = block;
	// For each map block:
	// Extract sunlight above.
	is_sunlight_above_block(map, blockpos, ndef, lights);
	// Reset the voxel manipulator.
	fill_with_sunlight(block, ndef, lights);
	// Copy sunlight data
	data.target_block = v3s16(blockpos.X, blockpos.Y - 1, blockpos.Z);
	for (s16 z = 0; z < MAP_BLOCKSIZE; z++)
	for (s16 x = 0; x < MAP_BLOCKSIZE; x++) {
		data.data.emplace_back(v2s16(x, z), lights[z][x]);
	}
	// Propagate sunlight and shadow below the voxel manipulator.
	while (!data.data.empty()) {
		if (propagate_block_sunlight(map, ndef, &data, &unlight[0],
				&relight[0]))
			(*modified_blocks)[data.target_block] =
				map->getBlockNoCreateNoEx(data.target_block);
		// Step downwards.
		data.target_block.Y--;
	}

	// --- STEP 2: Get nodes from borders to unlight

	// For each border of the block:
	for (const VoxelArea &a : block_pad) {
		v3s16 relpos;
		// For each node of the border:
		for (relpos.X = a.MinEdge.X; relpos.X <= a.MaxEdge.X; relpos.X++)
		for (relpos.Z = a.MinEdge.Z; relpos.Z <= a.MaxEdge.Z; relpos.Z++)
		for (relpos.Y = a.MinEdge.Y; relpos.Y <= a.MaxEdge.Y; relpos.Y++) {

			// Get node
			MapNode node = block->getNodeNoCheck(relpos, &is_valid);
			const ContentFeatures &f = ndef->get(node);
			// For each light bank
			for (size_t b = 0; b < 2; b++) {
				LightBank bank = banks[b];
				u8 light = f.param_type == CPT_LIGHT ?
					node.getLightNoChecks(bank, &f):
					f.light_source;
				// If the new node is dimmer than sunlight, unlight.
				// (if it has maximal light, it is pointless to remove
				// surrounding light, as it can only become brighter)
				if (LIGHT_SUN > light) {
					unlight[b].push(
						LIGHT_SUN, relpos, blockpos, block, 6);
				}
			} // end of banks
		} // end of nodes
	} // end of borders

	// STEP 3: Remove and spread light

	finish_bulk_light_update(map, blockpos, blockpos, unlight, relight,
		modified_blocks);
}

VoxelLineIterator::VoxelLineIterator(const v3f &start_position, const v3f &line_vector) :
	m_start_position(start_position),
	m_line_vector(line_vector)
{
	m_current_node_pos = floatToInt(m_start_position, 1);
	m_start_node_pos = m_current_node_pos;
	m_last_index = getIndex(floatToInt(start_position + line_vector, 1));

	if (m_line_vector.X > 0) {
		m_next_intersection_multi.X = (floorf(m_start_position.X - 0.5) + 1.5
			- m_start_position.X) / m_line_vector.X;
		m_intersection_multi_inc.X = 1 / m_line_vector.X;
	} else if (m_line_vector.X < 0) {
		m_next_intersection_multi.X = (floorf(m_start_position.X - 0.5)
			- m_start_position.X + 0.5) / m_line_vector.X;
		m_intersection_multi_inc.X = -1 / m_line_vector.X;
		m_step_directions.X = -1;
	}

	if (m_line_vector.Y > 0) {
		m_next_intersection_multi.Y = (floorf(m_start_position.Y - 0.5) + 1.5
			- m_start_position.Y) / m_line_vector.Y;
		m_intersection_multi_inc.Y = 1 / m_line_vector.Y;
	} else if (m_line_vector.Y < 0) {
		m_next_intersection_multi.Y = (floorf(m_start_position.Y - 0.5)
			- m_start_position.Y + 0.5) / m_line_vector.Y;
		m_intersection_multi_inc.Y = -1 / m_line_vector.Y;
		m_step_directions.Y = -1;
	}

	if (m_line_vector.Z > 0) {
		m_next_intersection_multi.Z = (floorf(m_start_position.Z - 0.5) + 1.5
			- m_start_position.Z) / m_line_vector.Z;
		m_intersection_multi_inc.Z = 1 / m_line_vector.Z;
	} else if (m_line_vector.Z < 0) {
		m_next_intersection_multi.Z = (floorf(m_start_position.Z - 0.5)
			- m_start_position.Z + 0.5) / m_line_vector.Z;
		m_intersection_multi_inc.Z = -1 / m_line_vector.Z;
		m_step_directions.Z = -1;
	}
}

void VoxelLineIterator::next()
{
	m_current_index++;
	if ((m_next_intersection_multi.X < m_next_intersection_multi.Y)
			&& (m_next_intersection_multi.X < m_next_intersection_multi.Z)) {
		m_next_intersection_multi.X += m_intersection_multi_inc.X;
		m_current_node_pos.X += m_step_directions.X;
	} else if ((m_next_intersection_multi.Y < m_next_intersection_multi.Z)) {
		m_next_intersection_multi.Y += m_intersection_multi_inc.Y;
		m_current_node_pos.Y += m_step_directions.Y;
	} else {
		m_next_intersection_multi.Z += m_intersection_multi_inc.Z;
		m_current_node_pos.Z += m_step_directions.Z;
	}
}

s16 VoxelLineIterator::getIndex(v3s16 voxel){
	return
		abs(voxel.X - m_start_node_pos.X) +
		abs(voxel.Y - m_start_node_pos.Y) +
		abs(voxel.Z - m_start_node_pos.Z);
}

} // namespace voxalgo