9 files changed, 1111 insertions, 1 deletions

diff --git a/src/BlockTypePalette.cpp b/src/BlockTypePalette.cpp
new file mode 100644
index 000000000..fabf5698e
--- /dev/null
+++ b/src/BlockTypePalette.cpp
@@ -0,0 +1,80 @@
+#include "Globals.h"
+#include "BlockTypePalette.h"
+
+
+
+
+BlockTypePalette::BlockTypePalette()
+{
+	// Nothing needed yet
+}
+
+
+
+
+
+UInt32 BlockTypePalette::index(const AString & aBlockTypeName, const BlockState & aBlockState)
+{
+	auto idx = maybeIndex(aBlockTypeName, aBlockState);
+	if (idx.second)
+	{
+		return idx.first;
+	}
+
+	// Not found, append:
+	mPalette.push_back(std::make_pair(aBlockTypeName, aBlockState));
+	return static_cast<UInt32>(mPalette.size() - 1);
+}
+
+
+
+
+
+std::pair<UInt32, bool> BlockTypePalette::maybeIndex(const AString & aBlockTypeName, const BlockState & aBlockState) const
+{
+	auto count = mPalette.size();
+	for (size_t idx = 0; idx < count; ++idx)
+	{
+		const auto & entry = mPalette[idx];
+		if ((entry.first == aBlockTypeName) && (entry.second == aBlockState))
+		{
+			return std::make_pair(static_cast<UInt32>(idx), true);
+		}
+	}
+	return std::make_pair(0, false);
+}
+
+
+
+
+
+UInt32 BlockTypePalette::count() const
+{
+	return static_cast<UInt32>(mPalette.size());
+}
+
+
+
+
+
+const std::pair<AString, BlockState> & BlockTypePalette::entry(UInt32 aIndex) const
+{
+	ASSERT(aIndex < mPalette.size());
+	return mPalette[aIndex];
+}
+
+
+
+
+
+std::map<UInt32, UInt32> BlockTypePalette::createTransformMap(const BlockTypePalette & aOther)
+{
+	std::map<UInt32, UInt32> res;
+	auto numIndices = aOther.count();
+	for (UInt32 idx = 0; idx < numIndices; ++idx)
+	{
+		const auto & e = aOther.mPalette[idx];
+		res[idx] = index(e.first, e.second);
+	}
+	return res;
+}
diff --git a/src/BlockTypePalette.h b/src/BlockTypePalette.h
new file mode 100644
index 000000000..47318f171
--- /dev/null
+++ b/src/BlockTypePalette.h
@@ -0,0 +1,44 @@
+#pragma once
+
+#include <utility>
+#include "BlockState.h"
+
+
+
+
+
+/** Holds a palette that maps block type + state into numbers.
+Used primarily by PalettedBlockArea to translate between numeric and stringular block representation.
+The object itself provides no thread safety, users of this class need to handle locking, if required. */
+class BlockTypePalette
+{
+public:
+
+	/** Create a new empty instance. */
+	BlockTypePalette();
+
+	/** Returns the index of the specified block type name and state.
+	If the combination is not found, it is added to the palette and the new index is returned. */
+	UInt32 index(const AString & aBlockTypeName, const BlockState & aBlockState);
+
+	/** Returns the <index, true> of the specified block type name and state, if it exists.
+	If the combination is not found, returns <undefined, false>. */
+	std::pair<UInt32, bool> maybeIndex(const AString & aBlockTypeName, const BlockState & aBlockState) const;
+
+	/** Returns the total number of entries in the palette. */
+	UInt32 count() const;
+
+	/** Returns the blockspec represented by the specified palette index.
+	The index must be valid (ASSERTed). */
+	const std::pair<AString, BlockState> & entry(UInt32 aIndex) const;
+
+	/** Adds missing entries from aOther to this, and returns an index-transform map from aOther to this.
+	Used when pasting two areas, to transform the src palette to dst palette. */
+	std::map<UInt32, UInt32> createTransformMap(const BlockTypePalette & aOther);
+
+
+protected:
+
+	/** The palette. Each item in the vector represents a single entry in the palette, the vector index is the palette index. */
+	std::vector<std::pair<AString, BlockState>> mPalette;
+};
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index dd92a969c..072eb6c97 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -18,6 +18,7 @@ SET (SRCS
 	BlockID.cpp
 	BlockInfo.cpp
 	BlockState.cpp
+	BlockTypePalette.cpp
 	BlockTypeRegistry.cpp
 	BrewingRecipes.cpp
 	Broadcaster.cpp
@@ -59,6 +60,7 @@ SET (SRCS
 	MonsterConfig.cpp
 	NetherPortalScanner.cpp
 	OverridesSettingsRepository.cpp
+	PalettedBlockArea.cpp
 	ProbabDistrib.cpp
 	RankManager.cpp
 	RCONServer.cpp
@@ -87,6 +89,7 @@ SET (HDRS
 	BlockInfo.h
 	BlockState.h
 	BlockTracer.h
+	BlockTypePalette.h
 	BlockTypeRegistry.h
 	BrewingRecipes.h
 	BoundingBox.h
@@ -140,6 +143,7 @@ SET (HDRS
 	NetherPortalScanner.h
 	OpaqueWorld.h
 	OverridesSettingsRepository.h
+	PalettedBlockArea.h
 	ProbabDistrib.h
 	RankManager.h
 	RCONServer.h
diff --git a/src/Cuboid.h b/src/Cuboid.h
index ed36a2298..4fefb8f57 100644
--- a/src/Cuboid.h
+++ b/src/Cuboid.h
@@ -117,6 +117,28 @@ public:
 	/** If needed, expands the cuboid so that it contains the specified point. Assumes sorted. Doesn't contract. */
 	void Engulf(Vector3i a_Point);
 
+	// tolua_end
+
+	/** Checks the two cuboids for equality. */
+	bool operator == (const cCuboid & aOther) const
+	{
+		return (
+			(p1.x == aOther.p1.x) &&
+			(p1.y == aOther.p1.y) &&
+			(p1.z == aOther.p1.z) &&
+			(p2.x == aOther.p2.x) &&
+			(p2.y == aOther.p2.y) &&
+			(p2.z == aOther.p2.z)
+		);
+	}
+
+	bool operator != (const cCuboid & aOther) const
+	{
+		return !operator ==(aOther);
+	}
+
+
+	// tolua_begin
 
 private:
 
diff --git a/src/PalettedBlockArea.cpp b/src/PalettedBlockArea.cpp
new file mode 100644
index 000000000..e703adec0
--- /dev/null
+++ b/src/PalettedBlockArea.cpp
@@ -0,0 +1,261 @@
+#include "Globals.h"
+#include "PalettedBlockArea.h"
+
+
+
+
+
+PalettedBlockArea::PalettedBlockArea()
+{
+	// Nothing needed yet
+}
+
+
+
+
+
+PalettedBlockArea PalettedBlockArea::createFilled(Vector3i aSize, const AString & aBlockTypeName, const BlockState & aBlockState)
+{
+	ASSERT(aSize.x > 0);
+	ASSERT(aSize.y > 0);
+	ASSERT(aSize.z > 0);
+
+	PalettedBlockArea res;
+	auto numBlocks = static_cast<UInt64>(aSize.x) * static_cast<UInt64>(aSize.y) * static_cast<UInt64>(aSize.z);
+	if (numBlocks >= std::numeric_limits<UInt32>::max())
+	{
+		// We use 32-bit indices in some functions (for ARM speed), so we need the entire area to fit into UInt32
+		throw std::runtime_error("Size is too large");
+	}
+	res.mSize = aSize;
+	res.mBlocks.resize(static_cast<size_t>(numBlocks));
+	res.fill(aBlockTypeName, aBlockState);
+	return res;
+}
+
+
+
+
+
+cCuboid PalettedBlockArea::whole() const
+{
+	return cCuboid(Vector3i(), mSize);
+}
+
+
+
+
+
+void PalettedBlockArea::setBlock(Vector3i aPos, const AString & aBlockTypeName, const BlockState & aBlockState)
+{
+	setBlock(aPos, paletteIndex(aBlockTypeName, aBlockState));
+}
+
+
+
+
+
+void PalettedBlockArea::setBlock(Vector3i aPos, UInt32 aPaletteIndex)
+{
+	ASSERT(isPositionValid(aPos));
+	ASSERT(aPaletteIndex < mPalette.count());
+
+	auto idx = positionToIndex(aPos);
+	mBlocks[idx] = aPaletteIndex;
+}
+
+
+
+
+
+UInt32 PalettedBlockArea::paletteIndex(const AString & aBlockTypeName, const BlockState & aBlockState)
+{
+	return mPalette.index(aBlockTypeName, aBlockState);
+}
+
+
+
+
+
+std::pair<UInt32, bool> PalettedBlockArea::maybePaletteIndex(const AString & aBlockTypeName, const BlockState & aBlockState) const
+{
+	return mPalette.maybeIndex(aBlockTypeName, aBlockState);
+}
+
+
+
+
+
+UInt32 PalettedBlockArea::blockPaletteIndex(Vector3i aPos) const
+{
+	auto idx = positionToIndex(aPos);
+	return mBlocks[idx];
+}
+
+
+
+
+
+const std::pair<AString, BlockState> & PalettedBlockArea::block(Vector3i aPos) const
+{
+	return paletteEntry(blockPaletteIndex(aPos));
+}
+
+
+
+
+
+const std::pair<AString, BlockState> & PalettedBlockArea::paletteEntry(UInt32 aPaletteIndex) const
+{
+	return mPalette.entry(aPaletteIndex);
+}
+
+
+
+
+
+bool PalettedBlockArea::isPositionValid(Vector3i aPos) const
+{
+	return (
+		(aPos.x >= 0) && (aPos.y >= 0) && (aPos.z >= 0) &&              // Non-negative coords
+		(aPos.x < mSize.x) && (aPos.y < mSize.y) && (aPos.z < mSize.z)  // Fit into size
+	);
+}
+
+
+
+
+
+void PalettedBlockArea::fill(const AString & aBlockTypeName, const BlockState & aBlockState)
+{
+	BlockTypePalette btp;
+	auto idx = btp.index(aBlockTypeName, aBlockState);
+	std::swap(mPalette, btp);
+	std::fill(mBlocks.begin(), mBlocks.end(), idx);
+}
+
+
+
+
+
+void PalettedBlockArea::paste(const PalettedBlockArea & aSrc, const cCuboid & aSrcCuboid, Vector3i aDstOrigin)
+{
+	// Clamp the src cuboid, first by src itself, then by this PBA's coord range:
+	cCuboid srcCuboid(aSrcCuboid);
+	srcCuboid.Sort();
+	srcCuboid.Clamp(aSrc.whole());
+	Vector3i maxSize = mSize - aDstOrigin;
+	srcCuboid.ClampSize(maxSize);
+	Vector3i dstOrigin(aDstOrigin);
+
+	// If any aDstOrigin coord is lower than 0, adjust the coord and src cuboid size:
+	if (dstOrigin.x < 0)
+	{
+		srcCuboid.p1.x -= dstOrigin.x;
+		if (srcCuboid.p1.x >= srcCuboid.p2.x)
+		{
+			return;
+		}
+		dstOrigin.x = 0;
+	}
+	if (dstOrigin.y < 0)
+	{
+		srcCuboid.p1.y -= dstOrigin.y;
+		if (srcCuboid.p1.y >= srcCuboid.p2.y)
+		{
+			return;
+		}
+		dstOrigin.y = 0;
+	}
+	if (dstOrigin.z < 0)
+	{
+		srcCuboid.p1.z -= dstOrigin.z;
+		if (srcCuboid.p1.z >= srcCuboid.p2.z)
+		{
+			return;
+		}
+		dstOrigin.z = 0;
+	}
+
+	// Create a transform map from aSrc's palette to our palette:
+	auto paletteTransform = mPalette.createTransformMap(aSrc.mPalette);
+
+	// Copy the data:
+	UInt32 srcStrideY = static_cast<UInt32>(aSrc.size().x * aSrc.size().z);
+	UInt32 srcStrideZ = static_cast<UInt32>(aSrc.size().x);
+	UInt32 dstStrideY = static_cast<UInt32>(mSize.x * mSize.z);
+	UInt32 dstStrideZ = static_cast<UInt32>(mSize.x);
+	UInt32 minX = static_cast<UInt32>(srcCuboid.p1.x);
+	UInt32 maxX = static_cast<UInt32>(srcCuboid.p2.x);
+	UInt32 minY = static_cast<UInt32>(srcCuboid.p1.y);
+	UInt32 maxY = static_cast<UInt32>(srcCuboid.p2.y);
+	UInt32 minZ = static_cast<UInt32>(srcCuboid.p1.z);
+	UInt32 maxZ = static_cast<UInt32>(srcCuboid.p2.z);
+	UInt32 dstX = static_cast<UInt32>(dstOrigin.x);
+	UInt32 dstY = static_cast<UInt32>(dstOrigin.y);
+	UInt32 dstZ = static_cast<UInt32>(dstOrigin.z);
+	for (UInt32 y = minY; y < maxY; ++y)
+	{
+		UInt32 srcOfsY = y * srcStrideY;
+		UInt32 dstOfsY = (y - minY + dstY) * dstStrideY;
+		for (UInt32 z = minZ; z < maxZ; ++z)
+		{
+			UInt32 srcOfs = srcOfsY + z * srcStrideZ + minX;
+			UInt32 dstOfs = dstOfsY + (z - minZ + dstZ) * dstStrideZ + dstX;
+			for (UInt32 x = minX; x < maxX; ++x)
+			{
+				mBlocks[dstOfs] = paletteTransform[aSrc.mBlocks[srcOfs]];
+				srcOfs += 1;
+				dstOfs += 1;
+			}
+		}
+	}
+}
+
+
+
+
+
+void PalettedBlockArea::crop(const cCuboid & aArea)
+{
+	cCuboid area(aArea);
+	area.Clamp(whole());
+
+	// Copy the data:
+	UInt32 srcStrideY = static_cast<UInt32>(size().x * size().z);
+	UInt32 srcStrideZ = static_cast<UInt32>(size().x);
+	UInt32 dstStrideY = static_cast<UInt32>(area.DifX() * area.DifZ());
+	UInt32 dstStrideZ = static_cast<UInt32>(area.DifZ());
+	UInt32 minX = static_cast<UInt32>(area.p1.x);
+	UInt32 maxX = static_cast<UInt32>(area.p2.x);
+	UInt32 minY = static_cast<UInt32>(area.p1.y);
+	UInt32 maxY = static_cast<UInt32>(area.p2.y);
+	UInt32 minZ = static_cast<UInt32>(area.p1.z);
+	UInt32 maxZ = static_cast<UInt32>(area.p2.z);
+	for (UInt32 y = minY; y < maxY; ++y)
+	{
+		UInt32 srcOfsY = (y - minY) * srcStrideY;
+		UInt32 dstOfsY = y * dstStrideY;
+		for (UInt32 z = minZ; z < maxZ; ++z)
+		{
+			UInt32 srcOfs = srcOfsY + (z - minZ) * srcStrideZ + minX;
+			UInt32 dstOfs = dstOfsY + z * dstStrideZ;
+			for (UInt32 x = minX; x < maxX; ++x)
+			{
+				mBlocks[dstOfs] = mBlocks[srcOfs];
+				srcOfs += 1;
+				dstOfs += 1;
+			}
+		}
+	}
+}
+
+
+
+
+
+UInt32 PalettedBlockArea::positionToIndex(Vector3i aPos) const
+{
+	ASSERT(isPositionValid(aPos));
+	return static_cast<UInt32>(aPos.x + aPos.z * mSize.x + aPos.y * mSize.x * mSize.z);
+}
diff --git a/src/PalettedBlockArea.h b/src/PalettedBlockArea.h
new file mode 100644
index 000000000..3866d405b
--- /dev/null
+++ b/src/PalettedBlockArea.h
@@ -0,0 +1,114 @@
+#pragma once
+
+
+
+
+
+#include <utility>
+
+#include "BlockTypePalette.h"
+#include "Cuboid.h"
+
+
+
+
+
+/** Represents an area of blocks that are represented using a palette.
+The object itself provides no thread safety, users of this class need to handle locking, if required.
+The PalettedBlockArea always contains Blocks and their associated BlockEntities, it may optionally contain Entities.
+There's no way to instantiate this class directly, you need to use either createFilled(), or read from cWorld. */
+class PalettedBlockArea
+{
+public:
+
+	/** Creates a new PBA of the specified size filled with the specified block.
+	Throws if there is an error (memory allocation etc.) */
+	static PalettedBlockArea createFilled(Vector3i aSize, const AString & aBlockTypeName, const BlockState & aBlockState);
+
+	/** Returns the actual size of the area in all 3 axes. */
+	const Vector3i & size() const { return mSize; }
+
+	/** Returns a cCuboid that encompasses the entire PBA.
+	Technically, {0, 0, 0} to mSize. */
+	cCuboid whole() const;
+
+	/** Sets a single block using its full blockspec.
+	The position must be valid (ASSERTed).
+	If the block is not already in palette, it is added. */
+	void setBlock(Vector3i aPos, const AString & aBlockTypeName, const BlockState & aBlockState);
+
+	/** Sets a single block using an index to the palette (retrieved earlier by paletteIndex()).
+	The position must be valid (ASSERTed).
+	The palette index must be valid (ASSERTed). */
+	void setBlock(Vector3i aPos, UInt32 aPaletteIndex);
+
+	/** Returns the index into the palette that is used by the specified full blockspec.
+	Adds the blockspec to palette if not already there. */
+	UInt32 paletteIndex(const AString & aBlockTypeName, const BlockState & aBlockState);
+
+	/** Returns the <index, true> into the palette that is used by the specified full blockspec.
+	Returns <undefined, false> if blockspec not in palette. */
+	std::pair<UInt32, bool> maybePaletteIndex(const AString & aBlockTypeName, const BlockState & aBlockState) const;
+
+	/** Returns the index into the palette for the block at the specified pos.
+	The position must be valid (ASSERTed). */
+	UInt32 blockPaletteIndex(Vector3i aPos) const;
+
+	/** Returns the full blockspec of the block at the specified position.
+	The position must be valid (ASSERTed). */
+	const std::pair<AString, BlockState> & block(Vector3i aPos) const;
+
+	/** Returns the blockspec represented by the specified palette index.
+	The index must be valid (ASSERTed). */
+	const std::pair<AString, BlockState> & paletteEntry(UInt32 aPaletteIndex) const;
+
+	/** Returns true if the specified position is within the size bounds of the area. */
+	bool isPositionValid(Vector3i aPos) const;
+
+	/** Fills the entire PBA with a single block of the specified type.
+	The palette is reset to one containing only the single block. */
+	void fill(const AString & aBlockTypeName, const BlockState & aBlockState);
+
+	/** Pastes (copies verbatim) a cCuboid out of the src PBA into this PBA.
+	aSrcCuboid is the coord range in aSrc that will be copied (min-coord is inclusive, max-coord is exclusive).
+	aDstOrigin is the coord relative to this PBA where the lowest coords of the copied area will be put.
+	aDstOrigin can be outside of this PBA's coord range (only part of the src is copied).
+	Automatically crops aSrcCuboid so that the copied part is entirely inside this PBA's coord range. */
+	void paste(const PalettedBlockArea & aSrc, const cCuboid & aSrcCuboid, Vector3i aDstOrigin = Vector3i());
+
+	/** Pastes (copies verbatim) the entire src PBA into this PBA.
+	aDstOrigin is the coord relative to this PBA where the lowest coords of the copied area will be put.
+	aDstOrigin can be outside of this PBA's coord range (only part of the src is copied).
+	Gracefully handles situations where the copied src PBA goes outside of this PBA's coord range. */
+	inline void paste(const PalettedBlockArea & aSrc, Vector3i aDstOrigin = Vector3i())
+	{
+		paste(aSrc, aSrc.whole(), aDstOrigin);
+	}
+
+	/** Crops this PBA by the specified coords.
+	aArea is first cropped to the size of this PBA (so it's only possible to shrink a PBA, not enlarge). */
+	void crop(const cCuboid & aArea);
+
+	/** Returns the (reqd-only) palette used internally by this object. */
+	const BlockTypePalette & palette() { return mPalette; }
+
+
+protected:
+
+	/** The palette used in the area. */
+	BlockTypePalette mPalette;
+
+	/** The blocks contained in the area, stored as indices into mPalette. */
+	std::vector<UInt32> mBlocks;
+
+	/** The size (dimensions) of the area. */
+	Vector3i mSize;
+
+
+	/** Creates a new uninitialized instance (all sizes zero). */
+	PalettedBlockArea();
+
+	/** Converts the position to index in mBlocks.
+	This may be removed later on when optimizing the RAM usage of this class by compressing low-palette-count PBAs. */
+	UInt32 positionToIndex(Vector3i aPos) const;
+};
diff --git a/tests/BlockTypeRegistry/BlockTypePaletteTest.cpp b/tests/BlockTypeRegistry/BlockTypePaletteTest.cpp
new file mode 100644
index 000000000..ef79d8927
--- /dev/null
+++ b/tests/BlockTypeRegistry/BlockTypePaletteTest.cpp
@@ -0,0 +1,122 @@
+#include "Globals.h"
+#include "../TestHelpers.h"
+#include "BlockTypePalette.h"
+
+
+
+
+
+/** Tests the BlockTypePalette's basic APIs - creation, addition, querying. */
+static void testBasic()
+{
+	LOGD("Testing the basic BlockTypePalette's APIs...");
+
+	// Check inserting different block type names:
+	BlockTypePalette pal;
+	TEST_EQUAL(pal.index("testblock", BlockState()), 0);  // Insert the first entry
+	TEST_EQUAL(pal.index("testblock", BlockState()), 0);  // Check that it's not inserted again
+	TEST_EQUAL(pal.maybeIndex("testblock", BlockState()), (std::make_pair<UInt32, bool>(0, true)));
+	TEST_EQUAL(pal.maybeIndex("nonexistent", BlockState()).second, false);
+
+	TEST_EQUAL(pal.index("another", BlockState()), 1);  // Insert the second entry
+	TEST_EQUAL(pal.index("another", BlockState()), 1);  // Check that it's not inserted twice
+	TEST_EQUAL(pal.maybeIndex("another", BlockState()), (std::make_pair<UInt32, bool>(1, true)));
+	TEST_EQUAL(pal.maybeIndex("testblock", BlockState()), (std::make_pair<UInt32, bool>(0, true)));  // The first one stayed
+
+	// Check same block type name, different BlockState:
+	BlockState bs1;
+	BlockState bs2("key1", "value1");
+	BlockState bs3({{"key1", "value1"}, {"key2", "value2"}});
+	BlockState bs2Copy(bs2);
+	TEST_EQUAL(pal.index("multistate", bs1), 2);
+	TEST_EQUAL(pal.index("multistate", bs2), 3);
+	TEST_EQUAL(pal.index("multistate", bs3), 4);
+	TEST_EQUAL(pal.index("multistate", bs2Copy), 3);  // Different BlockState instance, but same content
+	TEST_EQUAL(pal.count(), 5);
+
+	// Check the entry() API:
+	TEST_EQUAL(pal.entry(0), (std::make_pair<AString, BlockState>("testblock", BlockState())));
+	TEST_EQUAL(pal.entry(1), (std::make_pair<AString, BlockState>("another", BlockState())));
+	TEST_EQUAL(pal.entry(2), (std::make_pair<AString, BlockState>("multistate", BlockState(bs1))));  // make_pair requires a copy of the state
+	TEST_EQUAL(pal.entry(3), (std::make_pair<AString, BlockState>("multistate", BlockState(bs2))));
+	TEST_EQUAL(pal.entry(4), (std::make_pair<AString, BlockState>("multistate", BlockState(bs3))));
+}
+
+
+
+
+
+/** Tests creating the transform map between two palettes. */
+static void testTransform()
+{
+	LOGD("Testing the createTransformMap API...");
+
+	// Create two palettes with some overlap:
+	BlockTypePalette pal1, pal2;
+	pal1.index("block1", BlockState());
+	pal1.index("block2", BlockState());
+	pal1.index("block3", BlockState());
+	pal1.index("block4", BlockState());
+	pal1.index("block5", BlockState("key1", "value1"));
+	pal2.index("block0", BlockState());
+	pal2.index("block2", BlockState());  // overlap
+	pal2.index("block3", BlockState());  // overlap
+	pal2.index("block4", BlockState("key1", "value1"));
+	pal2.index("block5", BlockState("key1", "value1"));  // overlap
+	pal2.index("block6", BlockState("key1", "value1"));
+
+	// Check the transform map:
+	auto trans = pal1.createTransformMap(pal2);
+	TEST_EQUAL(pal1.maybeIndex("block1", BlockState()),                 (std::make_pair<UInt32, bool>(0, true)));
+	TEST_EQUAL(pal1.maybeIndex("block2", BlockState()),                 (std::make_pair<UInt32, bool>(1, true)));
+	TEST_EQUAL(pal1.maybeIndex("block3", BlockState()),                 (std::make_pair<UInt32, bool>(2, true)));
+	TEST_EQUAL(pal1.maybeIndex("block4", BlockState()),                 (std::make_pair<UInt32, bool>(3, true)));
+	TEST_EQUAL(pal1.maybeIndex("block5", BlockState("key1", "value1")), (std::make_pair<UInt32, bool>(4, true)));
+	TEST_EQUAL(pal1.maybeIndex("block0", BlockState()),                 (std::make_pair<UInt32, bool>(5, true)));
+	TEST_EQUAL(pal1.maybeIndex("block4", BlockState("key1", "value1")), (std::make_pair<UInt32, bool>(6, true)));
+	TEST_EQUAL(pal1.maybeIndex("block6", BlockState("key1", "value1")), (std::make_pair<UInt32, bool>(7, true)));
+	TEST_EQUAL(trans.size(), 6);
+	TEST_EQUAL(trans[0], 5);
+	TEST_EQUAL(trans[1], 1);
+	TEST_EQUAL(trans[2], 2);
+	TEST_EQUAL(trans[3], 6);
+	TEST_EQUAL(trans[4], 4);
+	TEST_EQUAL(trans[5], 7);
+}
+
+
+
+
+
+int main()
+{
+	LOGD("BlockTypePaletteTest started");
+
+	try
+	{
+		testBasic();
+		testTransform();
+	}
+	catch (const TestException & exc)
+	{
+		LOGERROR("BlockTypePaletteTest has failed, an exception was thrown: %s", exc.mMessage.c_str());
+		return 1;
+	}
+	catch (const std::exception & exc)
+	{
+		LOGERROR("BlockTypePaletteTest has failed, an exception was thrown: %s", exc.what());
+		return 1;
+	}
+	catch (...)
+	{
+		LOGERROR("BlockTypePaletteTest has failed, an unhandled exception was thrown.");
+		return 1;
+	}
+
+	LOGD("BlockTypePaletteTest finished");
+	return 0;
+}
+
+
+
+
diff --git a/tests/BlockTypeRegistry/CMakeLists.txt b/tests/BlockTypeRegistry/CMakeLists.txt
index c95c503dd..379158d5c 100644
--- a/tests/BlockTypeRegistry/CMakeLists.txt
+++ b/tests/BlockTypeRegistry/CMakeLists.txt
@@ -21,6 +21,16 @@ add_executable(BlockStateTest
 )
 target_link_libraries(BlockStateTest fmt::fmt)
 
+add_executable(BlockTypePaletteTest
+	BlockTypePaletteTest.cpp
+	../TestHelpers.h
+	${CMAKE_SOURCE_DIR}/src/BlockState.cpp
+	${CMAKE_SOURCE_DIR}/src/BlockTypePalette.cpp
+	${CMAKE_SOURCE_DIR}/src/StringUtils.cpp
+	${CMAKE_SOURCE_DIR}/src/OSSupport/CriticalSection.cpp
+)
+target_link_libraries(BlockTypePaletteTest fmt::fmt)
+
 # BlockTypeRegistryTest: Verify that the BlockTypeRegistry class works as intended:
 add_executable(BlockTypeRegistryTest
 	BlockTypeRegistryTest.cpp
@@ -31,6 +41,21 @@ add_executable(BlockTypeRegistryTest
 )
 target_link_libraries(BlockTypeRegistryTest fmt::fmt)
 
+# PalettedBlockAreaTest: Verify that the PalettedBlockArea class works as intended:
+add_executable(PalettedBlockAreaTest
+	PalettedBlockAreaTest.cpp
+	../TestHelpers.h
+	${CMAKE_SOURCE_DIR}/src/BlockState.cpp
+	${CMAKE_SOURCE_DIR}/src/BlockTypeRegistry.cpp
+	${CMAKE_SOURCE_DIR}/src/BlockTypePalette.cpp
+	${CMAKE_SOURCE_DIR}/src/Cuboid.cpp
+	${CMAKE_SOURCE_DIR}/src/PalettedBlockArea.cpp
+	${CMAKE_SOURCE_DIR}/src/StringUtils.cpp
+	${CMAKE_SOURCE_DIR}/src/OSSupport/CriticalSection.cpp
+)
+target_link_libraries(PalettedBlockAreaTest fmt::fmt)
+
+
 
 
 
@@ -38,8 +63,10 @@ target_link_libraries(BlockTypeRegistryTest fmt::fmt)
 
 # Define individual tests:
 
-add_test(NAME BlockStateTest COMMAND BlockStateTest)
+add_test(NAME BlockStateTest        COMMAND BlockStateTest)
 add_test(NAME BlockTypeRegistryTest COMMAND BlockTypeRegistryTest)
+add_test(NAME BlockTypePaletteTest  COMMAND BlockTypePaletteTest)
+add_test(NAME PalettedBlockAreaTest COMMAND PalettedBlockAreaTest)
 
 
 
@@ -49,5 +76,7 @@ add_test(NAME BlockTypeRegistryTest COMMAND BlockTypeRegistryTest)
 set_target_properties(
 	BlockStateTest
 	BlockTypeRegistryTest
+	BlockTypePaletteTest
+	PalettedBlockAreaTest
 	PROPERTIES FOLDER Tests/BlockTypeRegistry
 )
diff --git a/tests/BlockTypeRegistry/PalettedBlockAreaTest.cpp b/tests/BlockTypeRegistry/PalettedBlockAreaTest.cpp
new file mode 100644
index 000000000..0fc7c9452
--- /dev/null
+++ b/tests/BlockTypeRegistry/PalettedBlockAreaTest.cpp
@@ -0,0 +1,434 @@
+#include "Globals.h"
+#include <tuple>
+#include "PalettedBlockArea.h"
+#include "../TestHelpers.h"
+
+
+
+
+
+/** Tests creating a PBA. */
+static void testCreation()
+{
+	LOG("Testing PBA creation...");
+
+	// Check failures:
+	TEST_ASSERTS(PalettedBlockArea::createFilled({-2, 3, 4}, "block", BlockState()));  // Negative coords
+	TEST_THROWS(PalettedBlockArea::createFilled({4096, 4096, 4096}, "block", BlockState()), std::runtime_error);  // Size too large for UInt32
+
+	// Check that a created area really is filled:
+	auto pba = PalettedBlockArea::createFilled({2, 3, 4}, "block", BlockState());
+	TEST_EQUAL(pba.size(), Vector3i(2, 3, 4));
+	TEST_EQUAL(pba.whole(), cCuboid({0, 0, 0}, {2, 3, 4}));
+	TEST_EQUAL(pba.palette().count(), 1);
+	TEST_EQUAL(pba.maybePaletteIndex("block", BlockState()), (std::make_pair<UInt32, bool>(0, true)));
+	TEST_EQUAL(pba.maybePaletteIndex("nonexistentBlock", BlockState()).second, false);
+	for (int x = 0; x < 2; ++x)
+	{
+		for (int y = 0; y < 3; ++y)
+		{
+			for (int z = 0; z < 4; ++z)
+			{
+				TEST_EQUAL(pba.blockPaletteIndex({x, y, z}), 0);
+			}
+		}
+	}
+}
+
+
+
+
+
+/** Tests setting and getting blocks. */
+static void testSetting()
+{
+	LOG("Testing PBA's set and get APIs...");
+	auto pba = PalettedBlockArea::createFilled({2, 3, 4}, "block1", BlockState());
+	pba.setBlock({0, 0, 0}, "block2", BlockState());
+	pba.setBlock({1, 0, 0}, "block2", BlockState("key1", "value1"));
+	TEST_ASSERTS(pba.setBlock({2, 0, 0}, "block2", BlockState()));  // Invalid coords
+	pba.setBlock({0, 1, 0}, 1);
+	TEST_ASSERTS(pba.setBlock({1, 1, 0}, 100));  // Invalid palette index
+
+	// Check that the blocks have been set:
+	TEST_EQUAL(pba.palette().count(), 3);
+	TEST_EQUAL(pba.block({0, 0, 0}), (std::make_pair<AString, BlockState>("block2", BlockState())));
+	TEST_EQUAL(pba.block({1, 0, 0}), (std::make_pair<AString, BlockState>("block2", BlockState("key1", "value1"))));
+	TEST_ASSERTS(pba.block({2, 0, 0}));  // Invalid coords
+	TEST_EQUAL(pba.block({0, 1, 0}), (std::make_pair<AString, BlockState>("block2", BlockState())));
+	TEST_EQUAL(pba.block({1, 1, 0}), (std::make_pair<AString, BlockState>("block1", BlockState())));  // Didn't overwrite with invalid palette index
+	TEST_EQUAL(pba.blockPaletteIndex({0, 0, 0}), 1);
+	TEST_EQUAL(pba.blockPaletteIndex({1, 0, 0}), 2);
+	TEST_ASSERTS(pba.blockPaletteIndex({2, 0, 0}));  // Invalid coords
+	TEST_EQUAL(pba.blockPaletteIndex({0, 1, 0}), 1);
+	TEST_EQUAL(pba.blockPaletteIndex({1, 1, 0}), 0);  // Didn't overwrite with invalid palette index
+
+	// Test filling:
+	LOG("Testing PBA's fill API...");
+	pba.fill("block3", BlockState("key1", "value1"));
+	TEST_EQUAL(pba.palette().count(), 1);
+	TEST_EQUAL(pba.paletteEntry(0), (std::make_pair<AString, BlockState>("block3", BlockState("key1", "value1"))));
+	for (int x = 0; x < 2; ++x)
+	{
+		for (int y = 0; y < 2; ++y)
+		{
+			for (int z = 0; z < 2; ++z)
+			{
+				TEST_EQUAL(pba.blockPaletteIndex({x, y, z}), 0);
+			}
+		}
+	}
+}
+
+
+
+
+
+/** Creates pbaA and pbaB that are pre-filled with known content.
+The PBAs are then used for paste()-testing.
+Used to be a function, but clang-3.5 didn't like it ("error: debug information for auto is not yet supported"). */
+#define PREPARE_PASTING_PBAS \
+	auto pbaA = PalettedBlockArea::createFilled({5, 5, 5}, "blockA", BlockState()); \
+	for (int x = 0; x < 5; ++x) \
+	{ \
+		for (int y = 0; y < 5; ++y) \
+		{ \
+			for (int z = 0; z < 5; ++z) \
+			{ \
+				pbaA.setBlock({x, y, z}, Printf("A-%d-%d-%d", x, y, z), BlockState()); \
+			} \
+		} \
+	} \
+	auto pbaB = PalettedBlockArea::createFilled({6, 6, 6}, "blockB", BlockState()); \
+	for (int x = 0; x < 6; ++x) \
+	{ \
+		for (int y = 0; y < 6; ++y) \
+		{ \
+			for (int z = 0; z < 6; ++z) \
+			{ \
+				pbaB.setBlock({x, y, z}, Printf("B-%d-%d-%d", x, y, z), BlockState()); \
+			} \
+		} \
+	} \
+	do { } while (false)
+
+
+
+
+
+// This is the data for the original PBA, before the paste() operations.
+// It is included here so that when adding new paste() tests we can simply copy it
+// into the test function and modify for the test.
+/*
+static const AString expected[5][5][5] =
+{
+	{
+		{"A-0-0-0", "A-1-0-0", "A-2-0-0", "A-3-0-0", "A-4-0-0"},
+		{"A-0-1-0", "A-1-1-0", "A-2-1-0", "A-3-1-0", "A-4-1-0"},
+		{"A-0-2-0", "A-1-2-0", "A-2-2-0", "A-3-2-0", "A-4-2-0"},
+		{"A-0-3-0", "A-1-3-0", "A-2-3-0", "A-3-3-0", "A-4-3-0"},
+		{"A-0-4-0", "A-1-4-0", "A-2-4-0", "A-3-4-0", "A-4-4-0"},
+	},
+	{
+		{"A-0-0-1", "A-1-0-1", "A-2-0-1", "A-3-0-1", "A-4-0-1"},
+		{"A-0-1-1", "A-1-1-1", "A-2-1-1", "A-3-1-1", "A-4-1-1"},
+		{"A-0-2-1", "A-1-2-1", "A-2-2-1", "A-3-2-1", "A-4-2-1"},
+		{"A-0-3-1", "A-1-3-1", "A-2-3-1", "A-3-3-1", "A-4-3-1"},
+		{"A-0-4-1", "A-1-4-1", "A-2-4-1", "A-3-4-1", "A-4-4-1"},
+	},
+	{
+		{"A-0-0-2", "A-1-0-2", "A-2-0-2", "A-3-0-2", "A-4-0-2"},
+		{"A-0-1-2", "A-1-1-2", "A-2-1-2", "A-3-1-2", "A-4-1-2"},
+		{"A-0-2-2", "A-1-2-2", "A-2-2-2", "A-3-2-2", "A-4-2-2"},
+		{"A-0-3-2", "A-1-3-2", "A-2-3-2", "A-3-3-2", "A-4-3-2"},
+		{"A-0-4-2", "A-1-4-2", "A-2-4-2", "A-3-4-2", "A-4-4-2"},
+	},
+	{
+		{"A-0-0-3", "A-1-0-3", "A-2-0-3", "A-3-0-3", "A-4-0-3"},
+		{"A-0-1-3", "A-1-1-3", "A-2-1-3", "A-3-1-3", "A-4-1-3"},
+		{"A-0-2-3", "A-1-2-3", "A-2-2-3", "A-3-2-3", "A-4-2-3"},
+		{"A-0-3-3", "A-1-3-3", "A-2-3-3", "A-3-3-3", "A-4-3-3"},
+		{"A-0-4-3", "A-1-4-3", "A-2-4-3", "A-3-4-3", "A-4-4-3"},
+	},
+	{
+		{"A-0-0-4", "A-1-0-4", "A-2-0-4", "A-3-0-4", "A-4-0-4"},
+		{"A-0-1-4", "A-1-1-4", "A-2-1-4", "A-3-1-4", "A-4-1-4"},
+		{"A-0-2-4", "A-1-2-4", "A-2-2-4", "A-3-2-4", "A-4-2-4"},
+		{"A-0-3-4", "A-1-3-4", "A-2-3-4", "A-3-3-4", "A-4-3-4"},
+		{"A-0-4-4", "A-1-4-4", "A-2-4-4", "A-3-4-4", "A-4-4-4"},
+	},
+};
+*/
+
+
+
+
+
+/** Tests the "paste()" operation with the pasted region being completely inside the destination PBA. */
+static void testPastingCompletelyInside()
+{
+	LOG("Testing the paste() API with destination completely inside (with cropping)...");
+	PREPARE_PASTING_PBAS;
+	pbaA.paste(pbaB, cCuboid({1, 1, 1}, {4, 4, 4}), {1, 0, 0});  // Paste the 3x3x3 inside area from pbaB to pbaA, starting at {1, 0, 0}
+	static const AString expected[5][5][5] =
+	{
+		{
+			{"A-0-0-0", "B-1-1-1", "B-2-1-1", "B-3-1-1", "A-4-0-0"},
+			{"A-0-1-0", "B-1-2-1", "B-2-2-1", "B-3-2-1", "A-4-1-0"},
+			{"A-0-2-0", "B-1-3-1", "B-2-3-1", "B-3-3-1", "A-4-2-0"},
+			{"A-0-3-0", "A-1-3-0", "A-2-3-0", "A-3-3-0", "A-4-3-0"},
+			{"A-0-4-0", "A-1-4-0", "A-2-4-0", "A-3-4-0", "A-4-4-0"},
+		},
+		{
+			{"A-0-0-1", "B-1-1-2", "B-2-1-2", "B-3-1-2", "A-4-0-1"},
+			{"A-0-1-1", "B-1-2-2", "B-2-2-2", "B-3-2-2", "A-4-1-1"},
+			{"A-0-2-1", "B-1-3-2", "B-2-3-2", "B-3-3-2", "A-4-2-1"},
+			{"A-0-3-1", "A-1-3-1", "A-2-3-1", "A-3-3-1", "A-4-3-1"},
+			{"A-0-4-1", "A-1-4-1", "A-2-4-1", "A-3-4-1", "A-4-4-1"},
+		},
+		{
+			{"A-0-0-2", "B-1-1-3", "B-2-1-3", "B-3-1-3", "A-4-0-2"},
+			{"A-0-1-2", "B-1-2-3", "B-2-2-3", "B-3-2-3", "A-4-1-2"},
+			{"A-0-2-2", "B-1-3-3", "B-2-3-3", "B-3-3-3", "A-4-2-2"},
+			{"A-0-3-2", "A-1-3-2", "A-2-3-2", "A-3-3-2", "A-4-3-2"},
+			{"A-0-4-2", "A-1-4-2", "A-2-4-2", "A-3-4-2", "A-4-4-2"},
+		},
+		{
+			{"A-0-0-3", "A-1-0-3", "A-2-0-3", "A-3-0-3", "A-4-0-3"},
+			{"A-0-1-3", "A-1-1-3", "A-2-1-3", "A-3-1-3", "A-4-1-3"},
+			{"A-0-2-3", "A-1-2-3", "A-2-2-3", "A-3-2-3", "A-4-2-3"},
+			{"A-0-3-3", "A-1-3-3", "A-2-3-3", "A-3-3-3", "A-4-3-3"},
+			{"A-0-4-3", "A-1-4-3", "A-2-4-3", "A-3-4-3", "A-4-4-3"},
+		},
+		{
+			{"A-0-0-4", "A-1-0-4", "A-2-0-4", "A-3-0-4", "A-4-0-4"},
+			{"A-0-1-4", "A-1-1-4", "A-2-1-4", "A-3-1-4", "A-4-1-4"},
+			{"A-0-2-4", "A-1-2-4", "A-2-2-4", "A-3-2-4", "A-4-2-4"},
+			{"A-0-3-4", "A-1-3-4", "A-2-3-4", "A-3-3-4", "A-4-3-4"},
+			{"A-0-4-4", "A-1-4-4", "A-2-4-4", "A-3-4-4", "A-4-4-4"},
+		},
+	};
+	for (int x = 0; x < 5; ++x)
+	{
+		for (int y = 0; y < 5; ++y)
+		{
+			for (int z = 0; z < 5; ++z)
+			{
+				auto got = pbaA.block({x, y, z}).first;
+				TEST_EQUAL_MSG(
+					pbaA.block({x, y, z}).first,
+					expected[z][y][x],
+					Printf("{%d, %d, %d}, exp %s, got %s", x, y, z, expected[z][y][x].c_str(), pbaA.block({x, y, z}).first.c_str()).c_str()
+				);
+			}
+		}
+	}
+}
+
+
+
+
+
+/** Tests the "paste()" operation with the pasted region overflowing the destination PBA into the positive coords. */
+static void testPastingPositiveOverflow()
+{
+	LOG("Testing the paste() API with positive overflow...");
+	PREPARE_PASTING_PBAS;
+	pbaA.paste(pbaB, Vector3i{3, 2, 1});  // Paste the entire pbaB to pbaA, starting at {3, 2, 1}
+	static const AString expected[5][5][5] =
+	{
+		{
+			{"A-0-0-0", "A-1-0-0", "A-2-0-0", "A-3-0-0", "A-4-0-0"},
+			{"A-0-1-0", "A-1-1-0", "A-2-1-0", "A-3-1-0", "A-4-1-0"},
+			{"A-0-2-0", "A-1-2-0", "A-2-2-0", "A-3-2-0", "A-4-2-0"},
+			{"A-0-3-0", "A-1-3-0", "A-2-3-0", "A-3-3-0", "A-4-3-0"},
+			{"A-0-4-0", "A-1-4-0", "A-2-4-0", "A-3-4-0", "A-4-4-0"},
+		},
+		{
+			{"A-0-0-1", "A-1-0-1", "A-2-0-1", "A-3-0-1", "A-4-0-1"},
+			{"A-0-1-1", "A-1-1-1", "A-2-1-1", "A-3-1-1", "A-4-1-1"},
+			{"A-0-2-1", "A-1-2-1", "A-2-2-1", "B-0-0-0", "B-1-0-0"},
+			{"A-0-3-1", "A-1-3-1", "A-2-3-1", "B-0-1-0", "B-1-1-0"},
+			{"A-0-4-1", "A-1-4-1", "A-2-4-1", "B-0-2-0", "B-1-2-0"},
+		},
+		{
+			{"A-0-0-2", "A-1-0-2", "A-2-0-2", "A-3-0-2", "A-4-0-2"},
+			{"A-0-1-2", "A-1-1-2", "A-2-1-2", "A-3-1-2", "A-4-1-2"},
+			{"A-0-2-2", "A-1-2-2", "A-2-2-2", "B-0-0-1", "B-1-0-1"},
+			{"A-0-3-2", "A-1-3-2", "A-2-3-2", "B-0-1-1", "B-1-1-1"},
+			{"A-0-4-2", "A-1-4-2", "A-2-4-2", "B-0-2-1", "B-1-2-1"},
+		},
+		{
+			{"A-0-0-3", "A-1-0-3", "A-2-0-3", "A-3-0-3", "A-4-0-3"},
+			{"A-0-1-3", "A-1-1-3", "A-2-1-3", "A-3-1-3", "A-4-1-3"},
+			{"A-0-2-3", "A-1-2-3", "A-2-2-3", "B-0-0-2", "B-1-0-2"},
+			{"A-0-3-3", "A-1-3-3", "A-2-3-3", "B-0-1-2", "B-1-1-2"},
+			{"A-0-4-3", "A-1-4-3", "A-2-4-3", "B-0-2-2", "B-1-2-2"},
+		},
+		{
+			{"A-0-0-4", "A-1-0-4", "A-2-0-4", "A-3-0-4", "A-4-0-4"},
+			{"A-0-1-4", "A-1-1-4", "A-2-1-4", "A-3-1-4", "A-4-1-4"},
+			{"A-0-2-4", "A-1-2-4", "A-2-2-4", "B-0-0-3", "B-1-0-3"},
+			{"A-0-3-4", "A-1-3-4", "A-2-3-4", "B-0-1-3", "B-1-1-3"},
+			{"A-0-4-4", "A-1-4-4", "A-2-4-4", "B-0-2-3", "B-1-2-3"},
+		},
+	};
+	for (int x = 0; x < 5; ++x)
+	{
+		for (int y = 0; y < 5; ++y)
+		{
+			for (int z = 0; z < 5; ++z)
+			{
+				auto got = pbaA.block({x, y, z}).first;
+				TEST_EQUAL_MSG(
+					pbaA.block({x, y, z}).first,
+					expected[z][y][x],
+					Printf("{%d, %d, %d}, exp %s, got %s", x, y, z, expected[z][y][x].c_str(), pbaA.block({x, y, z}).first.c_str()).c_str()
+				);
+			}
+		}
+	}
+}
+
+
+
+
+
+/** Tests the "paste()" operation with the pasted region overflowing the destination PBA into the negative coords. */
+static void testPastingNegativeOverflow()
+{
+	LOG("Testing the paste() API with negative overflow...");
+	PREPARE_PASTING_PBAS;
+	pbaA.paste(pbaB, Vector3i{-4, -3, -2});  // Paste the entire pbaB to pbaA, starting at {-4, -3, -2}
+	static const AString expected[5][5][5] =
+	{
+		{
+			{"B-4-3-2", "B-5-3-2", "A-2-0-0", "A-3-0-0", "A-4-0-0"},
+			{"B-4-4-2", "B-5-4-2", "A-2-1-0", "A-3-1-0", "A-4-1-0"},
+			{"B-4-5-2", "B-5-5-2", "A-2-2-0", "A-3-2-0", "A-4-2-0"},
+			{"A-0-3-0", "A-1-3-0", "A-2-3-0", "A-3-3-0", "A-4-3-0"},
+			{"A-0-4-0", "A-1-4-0", "A-2-4-0", "A-3-4-0", "A-4-4-0"},
+		},
+		{
+			{"B-4-3-3", "B-5-3-3", "A-2-0-1", "A-3-0-1", "A-4-0-1"},
+			{"B-4-4-3", "B-5-4-3", "A-2-1-1", "A-3-1-1", "A-4-1-1"},
+			{"B-4-5-3", "B-5-5-3", "A-2-2-1", "A-3-2-1", "A-4-2-1"},
+			{"A-0-3-1", "A-1-3-1", "A-2-3-1", "A-3-3-1", "A-4-3-1"},
+			{"A-0-4-1", "A-1-4-1", "A-2-4-1", "A-3-4-1", "A-4-4-1"},
+		},
+		{
+			{"B-4-3-4", "B-5-3-4", "A-2-0-2", "A-3-0-2", "A-4-0-2"},
+			{"B-4-4-4", "B-5-4-4", "A-2-1-2", "A-3-1-2", "A-4-1-2"},
+			{"B-4-5-4", "B-5-5-4", "A-2-2-2", "A-3-2-2", "A-4-2-2"},
+			{"A-0-3-2", "A-1-3-2", "A-2-3-2", "A-3-3-2", "A-4-3-2"},
+			{"A-0-4-2", "A-1-4-2", "A-2-4-2", "A-3-4-2", "A-4-4-2"},
+		},
+		{
+			{"B-4-3-5", "B-5-3-5", "A-2-0-3", "A-3-0-3", "A-4-0-3"},
+			{"B-4-4-5", "B-5-4-5", "A-2-1-3", "A-3-1-3", "A-4-1-3"},
+			{"B-4-5-5", "B-5-5-5", "A-2-2-3", "A-3-2-3", "A-4-2-3"},
+			{"A-0-3-3", "A-1-3-3", "A-2-3-3", "A-3-3-3", "A-4-3-3"},
+			{"A-0-4-3", "A-1-4-3", "A-2-4-3", "A-3-4-3", "A-4-4-3"},
+		},
+		{
+			{"A-0-0-4", "A-1-0-4", "A-2-0-4", "A-3-0-4", "A-4-0-4"},
+			{"A-0-1-4", "A-1-1-4", "A-2-1-4", "A-3-1-4", "A-4-1-4"},
+			{"A-0-2-4", "A-1-2-4", "A-2-2-4", "A-3-2-4", "A-4-2-4"},
+			{"A-0-3-4", "A-1-3-4", "A-2-3-4", "A-3-3-4", "A-4-3-4"},
+			{"A-0-4-4", "A-1-4-4", "A-2-4-4", "A-3-4-4", "A-4-4-4"},
+		},
+	};
+	for (int x = 0; x < 5; ++x)
+	{
+		for (int y = 0; y < 5; ++y)
+		{
+			for (int z = 0; z < 5; ++z)
+			{
+				auto got = pbaA.block({x, y, z}).first;
+				TEST_EQUAL_MSG(
+					pbaA.block({x, y, z}).first,
+					expected[z][y][x],
+					Printf("{%d, %d, %d}, exp %s, got %s", x, y, z, expected[z][y][x].c_str(), pbaA.block({x, y, z}).first.c_str()).c_str()
+				);
+			}
+		}
+	}
+}
+
+
+
+
+
+/** Tests the "paste()" operation with the pasted region overflowing the destination PBA into mixed positive and negative coords. */
+static void testPastingMixedOverflow()
+{
+	LOG("Testing the paste() API with mixed positive and negative overflow...");
+	PREPARE_PASTING_PBAS;
+	pbaA.paste(pbaB, Vector3i{-4, -3, 2});  // Paste the entire pbaB to pbaA, starting at {-4, -3, 2}
+	static const AString expected[5][5][5] =
+	{
+		{
+			{"A-0-0-0", "A-1-0-0", "A-2-0-0", "A-3-0-0", "A-4-0-0"},
+			{"A-0-1-0", "A-1-1-0", "A-2-1-0", "A-3-1-0", "A-4-1-0"},
+			{"A-0-2-0", "A-1-2-0", "A-2-2-0", "A-3-2-0", "A-4-2-0"},
+			{"A-0-3-0", "A-1-3-0", "A-2-3-0", "A-3-3-0", "A-4-3-0"},
+			{"A-0-4-0", "A-1-4-0", "A-2-4-0", "A-3-4-0", "A-4-4-0"},
+		},
+		{
+			{"A-0-0-1", "A-1-0-1", "A-2-0-1", "A-3-0-1", "A-4-0-1"},
+			{"A-0-1-1", "A-1-1-1", "A-2-1-1", "A-3-1-1", "A-4-1-1"},
+			{"A-0-2-1", "A-1-2-1", "A-2-2-1", "A-3-2-1", "A-4-2-1"},
+			{"A-0-3-1", "A-1-3-1", "A-2-3-1", "A-3-3-1", "A-4-3-1"},
+			{"A-0-4-1", "A-1-4-1", "A-2-4-1", "A-3-4-1", "A-4-4-1"},
+		},
+		{
+			{"B-4-3-0", "B-5-3-0", "A-2-0-2", "A-3-0-2", "A-4-0-2"},
+			{"B-4-4-0", "B-5-4-0", "A-2-1-2", "A-3-1-2", "A-4-1-2"},
+			{"B-4-5-0", "B-5-5-0", "A-2-2-2", "A-3-2-2", "A-4-2-2"},
+			{"A-0-3-2", "A-1-3-2", "A-2-3-2", "A-3-3-2", "A-4-3-2"},
+			{"A-0-4-2", "A-1-4-2", "A-2-4-2", "A-3-4-2", "A-4-4-2"},
+		},
+		{
+			{"B-4-3-1", "B-5-3-1", "A-2-0-3", "A-3-0-3", "A-4-0-3"},
+			{"B-4-4-1", "B-5-4-1", "A-2-1-3", "A-3-1-3", "A-4-1-3"},
+			{"B-4-5-1", "B-5-5-1", "A-2-2-3", "A-3-2-3", "A-4-2-3"},
+			{"A-0-3-3", "A-1-3-3", "A-2-3-3", "A-3-3-3", "A-4-3-3"},
+			{"A-0-4-3", "A-1-4-3", "A-2-4-3", "A-3-4-3", "A-4-4-3"},
+		},
+		{
+			{"B-4-3-2", "B-5-3-2", "A-2-0-4", "A-3-0-4", "A-4-0-4"},
+			{"B-4-4-2", "B-5-4-2", "A-2-1-4", "A-3-1-4", "A-4-1-4"},
+			{"B-4-5-2", "B-5-5-2", "A-2-2-4", "A-3-2-4", "A-4-2-4"},
+			{"A-0-3-4", "A-1-3-4", "A-2-3-4", "A-3-3-4", "A-4-3-4"},
+			{"A-0-4-4", "A-1-4-4", "A-2-4-4", "A-3-4-4", "A-4-4-4"},
+		},
+	};
+	for (int x = 0; x < 5; ++x)
+	{
+		for (int y = 0; y < 5; ++y)
+		{
+			for (int z = 0; z < 5; ++z)
+			{
+				auto got = pbaA.block({x, y, z}).first;
+				TEST_EQUAL_MSG(
+					pbaA.block({x, y, z}).first,
+					expected[z][y][x],
+					Printf("{%d, %d, %d}, exp %s, got %s", x, y, z, expected[z][y][x].c_str(), pbaA.block({x, y, z}).first.c_str()).c_str()
+				);
+			}
+		}
+	}
+}
+
+
+
+
+
+IMPLEMENT_TEST_MAIN("PalettedBlockArea",
+	testCreation();
+	testSetting();
+	testPastingCompletelyInside();
+	testPastingPositiveOverflow();
+	testPastingNegativeOverflow();
+	testPastingMixedOverflow();
+)