fork download
copy 
  1. import java.util.*;
  2. import java.util.stream.*;
  3. import java.lang.*;
  4. import java.io.*;
  5. import static java.lang.Math.*;
  6.  
  7. class Util {
  8. 	public static IllegalArgumentException BadArgf(String fmt, Object... args) {
  9. 		return new IllegalArgumentException(String.format(fmt, args));
  10. 	};
  11.  
  12. 	public static String trace(Exception e) {
  13. 		StringWriter sw = new StringWriter();
  14. 		e.printStackTrace(new PrintWriter(sw));
  15. 		return sw.toString();
  16. 	}
  17.  
  18. 	public static int rangecheck(int x, int min, int max, String what) {
  19. 		if (x < min || x > max) throw BadArgf("Bad %s: %d, should be [%d; %d].", what, x, min, max);
  20. 		return x;
  21. 	}
  22. }
  23.  
  24. class Bitfield2D {
  25. 	int[] data;
  26. 	int w, h;
  27. 	static final int SANE_BITS_LIMIT = 1_000_000_000;
  28. 	static final int SANE_DIMENSION_LIMIT = 100_000_000;
  29. 	static final int BASE = Integer.SIZE; 
  30. 	// BASE expected to be power of 2, then
  31. 	// (bitno >> BASEP2) is faster version of (bitno / BASE), and
  32. 	// (bitno & BASEMASK) is faster version of (bitno % BASE).
  33. 	//
  34. 	// Compiler cannot optimize these operations as effectively as programmer can,
  35. 	// because they work differently for negative 'bitno' values, so it should check for negatives.
  36. 	// And it's only we who know that 'bitno' is never negative.
  37. 	//
  38. 	// Not sure if there is no danger of BASEP2 formula NOT resulting in compile-time constant,
  39. 	// but it appears to be OK.
  40. 	static final int BASEP2 = 32 - (Integer.numberOfLeadingZeros(BASE) + 1);
  41. 	static final int BASEMASK = BASE - 1;
  42.  
  43. 	public Bitfield2D(int w, int h) {
  44. 		validateSize(w, h);
  45. 		this.data = new int[(w*h + (BASE - 1)) >> BASEP2];
  46. 		this.w = w;
  47. 		this.h = h;
  48. 	}
  49.  
  50. 	static void validateSize(int w, int h) {
  51. 		if (w < 0 || h < 0 || w > SANE_DIMENSION_LIMIT || h > SANE_DIMENSION_LIMIT
  52. 			|| w > 0 && h > SANE_BITS_LIMIT / w)
  53. 			throw Util.BadArgf("Bad bitfield size: %d×%d.", w, h);
  54. 	}
  55.  
  56. 	public static boolean validCoord(int w, int h, int x, int y) {
  57. 		return x >= 0 && y >= 0 && x < w && y < h;
  58. 	}
  59.  
  60. 	public static void validateCoord(int w, int h, int x, int y) {
  61. 		if (!validCoord(w, h, x, y))
  62. 			throw Util.BadArgf("Bad coord of bitfield %d×%d: (%d, %d).", w, h, x, y);
  63. 	}
  64.  
  65. 	static void validateRect(int fullw, int fullh, int x, int y, int w, int h) {
  66. 		if (x < 0 || y < 0 || w < 0 || h < 0 || x + w > fullw || y + h > fullh)
  67. 			throw Util.BadArgf("Bad rect of bitfield %d×%d: (%d, %d) ~ (%d, %d).",
  68. 				fullw, fullh, x, y, x+w, y+h);
  69. 	}
  70.  
  71. 	boolean rawget(int index) { return (data[index >> BASEP2] & (1 << (index & BASEMASK))) != 0; }
  72. 	void rawset(int index) { data[index >> BASEP2] |= 1 << (index & BASEMASK); }
  73. 	void rawunset(int index) { data[index >> BASEP2] &= ~(1 << (index & BASEMASK)); }
  74. 	void rawset(int index, boolean value) { if (value) rawset(index); else rawunset(index); }
  75.  
  76. 	public boolean get(int x, int y) { validateCoord(w, h, x, y); return rawget(y*w+x); }
  77. 	public void set(int x, int y) { validateCoord(w, h, x, y); rawset(y*w+x); }
  78. 	public void unset(int x, int y) { validateCoord(w, h, x, y); rawunset(y*w+x); }
  79. 	public void set(int x, int y, boolean value) { validateCoord(w, h, x, y); rawset(y*w+x, value); }
  80. 	public int width() { return w; }
  81. 	public int height() { return h; }
  82.  
  83. 	// For functions like or() that apply one bitfield to another,
  84. 	// reduces potentially out-of-borders input to its valid part.
  85. 	static class CoordWarden {
  86. 		int srcX, srcY, w, h, destX, destY;
  87.  
  88. 		CoordWarden(int destFullW, int destFullH, int srcFullW, int srcFullH,
  89. 			int aSrcX, int aSrcY, int aW, int aH, int aDestX, int aDestY) {
  90.  
  91. 			validateRect(srcFullW, srcFullH, aSrcX, aSrcY, aW, aH);
  92. 			srcX = aSrcX; srcY = aSrcY; w = aW; h = aH; destX = aDestX; destY = aDestY;
  93. 			if (destX < 0) { srcX -= destX; w += destX; destX = 0; }
  94. 			if (destX + w > destFullW) { w = destFullW - destX; }
  95. 			if (destY < 0) { srcY -= destY; h += destY; destY = 0; }
  96. 			if (destY + h > destFullH) { h = destFullH - destY; }
  97. 		}
  98. 	}
  99.  
  100. 	public void or(Bitfield2D b, int thisX, int thisY) {
  101. 		or(b, 0, 0, b.w, b.h, thisX, thisY);
  102. 	}
  103.  
  104. 	public void or(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY) {
  105. 		var ward = new CoordWarden(this.w, this.h, b.w, b.h, bx, by, w, h, thisX, thisY);
  106. 		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
  107. 		for (int dy = 0; dy < ward.h; dy++, thisOfs += this.w - ward.w, bOfs += b.w - ward.w)
  108. 			for (int dx = 0; dx < ward.w; dx++, thisOfs++, bOfs++)
  109. 				if (b.rawget(bOfs)) this.rawset(thisOfs);
  110. 	}
  111.  
  112. 	public void orBATCH(Bitfield2D b, int thisX, int thisY) {
  113. 		orBATCH(b, 0, 0, b.w, b.h, thisX, thisY);
  114. 	}
  115.  
  116. 	public void orBATCH(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY) {
  117. 		apply(b, bx, by, w, h, thisX, thisY, (itemA, itemB) -> itemA | itemB);
  118. 	}
  119.  
  120. 	public void andNot(Bitfield2D b, int thisX, int thisY) {
  121. 		andNot(b, 0, 0, b.w, b.h, thisX, thisY);
  122. 	}
  123.  
  124. 	public void andNot(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY) {
  125. 		var ward = new CoordWarden(this.w, this.h, b.w, b.h, bx, by, w, h, thisX, thisY);
  126. 		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
  127. 		for (int dy = 0; dy < ward.h; dy++, thisOfs += this.w - ward.w, bOfs += b.w - ward.w)
  128. 			for (int dx = 0; dx < ward.w; dx++, thisOfs++, bOfs++)
  129. 				if (b.rawget(bOfs)) this.rawunset(thisOfs);
  130. 	}
  131.  
  132. 	public void andNotBATCH(Bitfield2D b, int thisX, int thisY) {
  133. 		andNotBATCH(b, 0, 0, b.w, b.h, thisX, thisY);
  134. 	}
  135.  
  136. 	public void andNotBATCH(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY) {
  137. 		apply(b, bx, by, w, h, thisX, thisY, (itemA, itemB) -> itemA & ~itemB);
  138. 	}
  139.  
  140. 	@FunctionalInterface
  141. 	interface Operation {
  142. 		abstract int apply(int a, int b);
  143. 	}
  144.  
  145. 	void apply(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY, Operation op) {
  146. 		var ward = new CoordWarden(this.w, this.h, b.w, b.h, bx, by, w, h, thisX, thisY);
  147. 		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
  148. 		for (int dy = 0; dy < ward.h; dy++, thisOfs += this.w, bOfs += b.w)
  149. 			applyOp(this.data, thisOfs, b.data, bOfs, ward.w, op);
  150. 	}
  151.  
  152. 	public Bitfield2D copyFrom(Bitfield2D b, int thisX, int thisY) {
  153. 		return copyFrom(b, 0, 0, b.w, b.h, thisX, thisY);
  154. 	}
  155.  
  156. 	public Bitfield2D copyFrom(Bitfield2D b, int bx, int by, int w, int h, int thisX, int thisY) {
  157. 		var ward = new CoordWarden(this.w, this.h, b.w, b.h, bx, by, w, h, thisX, thisY);
  158. 		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
  159. 		for (int dy = 0; dy < ward.h; dy++, thisOfs += this.w, bOfs += b.w)
  160. 			copyBits(b.data, bOfs, this.data, thisOfs, ward.w);
  161. 		return this;
  162. 	}
  163.  
  164. 	static int readBitsSmall(int[] src, int srcPos, int count) {
  165. 		assert count > 0 && count < BASE;
  166. 		//       0       1       2       3       4       5       6
  167. 		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  168. 		//            ^srcPos=5
  169. 		//                  ^srcPos+count=11
  170. 		int bits = src[srcPos >> BASEP2] >>> (srcPos & BASEMASK); // FGH
  171. 		if (count > BASE - (srcPos & BASEMASK))
  172. 			bits |= src[(srcPos >> BASEP2) + 1] << (BASE - (srcPos & BASEMASK)); // FGH | 000IJKLMNOP = FGHIJKLMNOP
  173. 		return bits & ((1 << count) - 1); // FGHIJK
  174. 	}
  175.  
  176. 	static void writeBits1(int bits, int[] dst, int dstPos, int count) {
  177. 		assert count > 0 && count < BASE - (dstPos & BASEMASK) && bits < 1 << count;
  178. 		// bits = qwer
  179. 		//       0       1       2       3       4       5       6
  180. 		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  181. 		//          ^dstPos=3
  182. 		//              ^dstPos+count=7
  183. 		dst[dstPos >> BASEP2] = dst[dstPos >> BASEP2] // ABCDEFGH
  184. 			& ~(((1 << count) - 1) << (dstPos & BASEMASK)) // ABC0000H
  185. 			| (bits << (dstPos & BASEMASK)); // ABCqwerH
  186. 	}
  187.  
  188. 	static void copyBits(int[] src, int srcPos, int[] dst, int dstPos, int count) {
  189. 		// Imagine BASE=8 (as if byte[] instead of int[]), srcPos = 3, dstPos = 2, count=25.
  190. 		//
  191. 		//       0       1       2       3       4       5       6
  192. 		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  193. 		//          ^srcPos=3                ^srcPos+count=28
  194. 		// dst = ...............................................
  195. 		//       0 ^dstPos=2     2       3       4       5
  196. 		//
  197. 		// First we align dstPos to the multiple of BASE by reading
  198. 		// first BASE - dstPos%BASE bits with readBitsSmall() and writing them
  199. 		// into the first cell of dst[] with writeBits1.
  200. 		//
  201. 		// We'll get:
  202. 		//       0       1       2       3       4       5       6
  203. 		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  204. 		//                ^srcPos=9          ^srcPos+count=28
  205. 		// dst = ..DEFGHI.......................................
  206. 		//       0       1       2       3       4       5
  207. 		//               ^dstPos=8
  208. 		if ((dstPos & BASEMASK) != 0) {
  209. 			int n = min(count, BASE - (dstPos & BASEMASK));
  210. 			if (n > 0) writeBits1(readBitsSmall(src, srcPos, n), dst, dstPos, n);
  211. 			srcPos += n;
  212. 			dstPos += n;
  213. 			count -= n;
  214. 		}
  215.  
  216. 		// Now we fill whole cells while possible.
  217. 		// We'll get:
  218. 		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  219. 		//                                ^srcPos=25
  220. 		//                                   ^srcPos+count=28
  221. 		// dst = ..DEFGHIJKLMNOPQRSTUVWXY.......................
  222. 		//       0       1       2       3       4       5
  223. 		//                               ^dstPos=24
  224. 		if (count >= BASE) {
  225. 			if ((srcPos & BASEMASK) == 0) {
  226. 				// Aligned case. This is not even an optimization, because 'int' shifts are restricted to 0..31.
  227. 				System.arraycopy(src, srcPos >> BASEP2, dst, dstPos >> BASEP2, count >> BASEP2);
  228. 			} else {
  229. 				// Unaligned case.
  230. 				// src: ...ABCDE FGH.....
  231. 				//         ^srcPos
  232. 				// dst: ........
  233. 				for (int iSrc = srcPos >> BASEP2, iDst = dstPos >> BASEP2, iDstEd = iDst + (count >> BASEP2); iDst < iDstEd; iDst++, iSrc++)
  234. 					dst[iDst] =
  235. 						(src[iSrc] >>> (srcPos & BASEMASK)) // ABCDE
  236. 						| (src[iSrc + 1] << (BASE - (srcPos & BASEMASK))); // ABCDE | 00000FGH = ABCDEFGH
  237. 			}
  238. 			srcPos += count - (count & BASEMASK);
  239. 			dstPos += count - (count & BASEMASK);
  240. 			count &= BASEMASK;
  241. 		}
  242.  
  243. 		// Append the tail.
  244. 		if (count > 0)
  245. 			writeBits1(readBitsSmall(src, srcPos, count), dst, dstPos, count);
  246. 	}
  247.  
  248. 	// Same as copyBits() but with custom operation instead of copying.
  249. 	// Argument order changed both to emphasize modifying 'dst' and
  250. 	// to match the order in op.apply: (dst, src) that matters for noncommutative operations.
  251. 	// Speaking of it, the only reason why copyBits() has (src, srcPos, dst,
  252. 	// dstPos, count) order is consistency with System.arraycopy.
  253. 	static void applyOp(int[] dst, int dstPos, int[] src, int srcPos, int count, Operation op) {
  254. 		if ((dstPos & BASEMASK) != 0) {
  255. 			int n = min(count, BASE - (dstPos & BASEMASK));
  256. 			if (n > 0) writeBits1(op.apply(readBitsSmall(dst, dstPos, n), readBitsSmall(src, srcPos, n)), dst, dstPos, n);
  257. 			srcPos += n; dstPos += n; count -= n;
  258. 		}
  259. 		if (count >= BASE) {
  260. 			for (int iSrc = srcPos >> BASEP2, iDst = dstPos >> BASEP2, iDstEd = iDst + (count >> BASEP2); iDst < iDstEd; iDst++, iSrc++)
  261. 				dst[iDst] = op.apply(dst[iDst], (srcPos & BASEMASK) == 0 ? src[iSrc] : (src[iSrc] >>> (srcPos & BASEMASK)) | (src[iSrc + 1] << (BASE - (srcPos & BASEMASK))));
  262. 			srcPos += count - (count & BASEMASK); dstPos += count - (count & BASEMASK); count &= BASEMASK;
  263. 		}
  264. 		if (count > 0)
  265. 			writeBits1(op.apply(readBitsSmall(dst, dstPos, count), readBitsSmall(src, srcPos, count)), dst, dstPos, count);
  266. 	}
  267.  
  268. 	@Override
  269. 	public String toString() {
  270. 		return toString("##", "..");
  271. 	}
  272.  
  273. 	public String toString(String one, String zero) {
  274. 		var sb = new StringBuilder();
  275. 		for (int ofs = 0, y = 0; y < h; y++) {
  276. 			if (y > 0) sb.append("\n");
  277. 			for (int x = 0; x < w; x++, ofs++)
  278. 				sb.append(rawget(ofs) ? one : zero);
  279. 		}
  280. 		return sb.toString();
  281. 	}
  282.  
  283. 	static Bitfield2D parse(String src) { return parse(src, "##"); }
  284.  
  285. 	static Bitfield2D parse(String src, String one) {
  286. 		if (one.isEmpty()) throw Util.BadArgf("'one' can't be empty.");
  287. 		if (one.indexOf('\n') >= 0) throw Util.BadArgf("Bad 'one': \"%s\". Shouldn't contain EOL.", one);
  288. 		// Prepass for size.
  289. 		int w = 0, h = 0;
  290. 		for (int pos = 0; pos < src.length(); ) {
  291. 			int eolp = src.indexOf("\n", pos);
  292. 			if (eolp < 0) eolp = src.length();
  293. 			if ((eolp - pos) % one.length() != 0)
  294. 				throw Util.BadArgf("Line %d:\n%s\ncontains %d character%s, which is not multiple of len(%s) = %d.",
  295. 					h, src.substring(pos, eolp), eolp - pos, eolp - pos != 1 ? "s" : "", one, one.length());
  296. 			w = max(w, (eolp - pos) / one.length());
  297. 			h++;
  298. 			pos = eolp + "\n".length();
  299. 		}
  300. 		var r = new Bitfield2D(w, h);
  301.  
  302. 		for (int y = 0, x = 0, ofs = 0, pos = 0; pos < src.length(); )
  303. 			if (src.charAt(pos) == '\n') {
  304. 				ofs += r.w - x;
  305. 				x = 0; y++;
  306. 				pos += "\n".length();
  307. 			} else {
  308. 				if (src.startsWith(one, pos)) r.rawset(ofs);
  309. 				pos += one.length();
  310. 				x++; ofs++;
  311. 			}
  312. 		return r;
  313. 	}
  314.  
  315. 	public boolean[][] toBool2D() { return toBool2D(0, 0, w, h); }
  316. 	public boolean[][] toBool2D(int atx, int aty, int w, int h) {
  317. 		validateRect(this.w, this.h, atx, aty, w, h);
  318. 		boolean[][] r = Bool2D.create(w, h);
  319. 		for (int y = 0, ofs = aty * this.w + atx; y < h; y++, ofs += this.w - w)
  320. 			for (int x = 0; x < w; x++, ofs++)
  321. 				r[y][x] = rawget(ofs);
  322. 		return r;
  323. 	}
  324. }
  325.  
  326. class Bool2D {
  327. 	public static boolean[][] create(int w, int h) {
  328. 		Bitfield2D.validateSize(w, h);
  329. 		if (h == 0) throw Util.BadArgf("boolean[][] can't have zero height.");
  330. 		return new boolean[h][w];
  331. 	}
  332.  
  333. 	public static void or(boolean[][] it, boolean[][] b, int itX, int itY) {
  334. 		or(it, b, 0, 0, b[0].length, b.length, itX, itY);
  335. 	}
  336.  
  337. 	public static void or(boolean[][] it, boolean[][] b, int bx, int by, int w, int h, int itX, int itY) {
  338. 		var ward = new Bitfield2D.CoordWarden(it[0].length, it.length, b[0].length, b.length, bx, by, w, h, itX, itY);
  339. 		for (int dy = 0, iItY = ward.destY, iBy = ward.srcY; dy < ward.h; dy++, iItY++, iBy++)
  340. 			for (int dx = 0, iItX = ward.destX, iBx = ward.srcX; dx < ward.w; dx++, iItX++, iBx++)
  341. 				it[iItY][iItX] |= b[iBy][iBx];
  342. 	}
  343.  
  344. 	public static void andNot(boolean[][] it, boolean[][] b, int itX, int itY) {
  345. 		andNot(it, b, 0, 0, b[0].length, b.length, itX, itY);
  346. 	}
  347.  
  348. 	public static void andNot(boolean[][] it, boolean[][] b, int bx, int by, int w, int h, int itX, int itY) {
  349. 		var ward = new Bitfield2D.CoordWarden(it[0].length, it.length, b[0].length, b.length, bx, by, w, h, itX, itY);
  350. 		for (int dy = 0, iItY = ward.destY, iBy = ward.srcY; dy < ward.h; dy++, iItY++, iBy++)
  351. 			for (int dx = 0, iItX = ward.destX, iBx = ward.srcX; dx < ward.w; dx++, iItX++, iBx++)
  352. 				it[iItY][iItX] &= !b[iBy][iBx];
  353. 	}
  354.  
  355. 	public static void copyFrom(boolean[][] it, boolean[][] b, int itX, int itY) {
  356. 		copyFrom(it, b, 0, 0, b[0].length, b.length, itX, itY);
  357. 	}
  358.  
  359. 	public static void copyFrom(boolean[][] it, boolean[][] b, int bx, int by, int w, int h, int itX, int itY) {
  360. 		var ward = new Bitfield2D.CoordWarden(it[0].length, it.length, b[0].length, b.length, bx, by, w, h, itX, itY);
  361. 		if (ward.w <= 0) return;
  362. 		for (int dy = 0, iItY = ward.destY, iBy = ward.srcY; dy < ward.h; dy++, iItY++, iBy++)
  363. 			System.arraycopy(b[iBy], ward.srcX, it[iItY], ward.destX, ward.w);
  364. 	}
  365.  
  366. 	public static String toString(boolean[][] it) {
  367. 		return toString(it, "##", "..");
  368. 	}
  369.  
  370. 	public static String toString(boolean[][] it, String one, String zero) {
  371. 		return toBitfield2D(it).toString(one, zero);
  372. 	}
  373.  
  374. 	public static boolean[][] parse(String src) { return parse(src, "##"); }
  375. 	public static boolean[][] parse(String src, String one) {
  376. 		return Bitfield2D.parse(src, one).toBool2D();
  377. 	}
  378.  
  379. 	public static Bitfield2D toBitfield2D(boolean[][] it) { return toBitfield2D(it, 0, 0, it[0].length, it.length); }
  380. 	public static Bitfield2D toBitfield2D(boolean[][] it, int atx, int aty, int w, int h) {
  381. 		Bitfield2D.validateRect(it[0].length, it.length, atx, aty, w, h);
  382. 		var r = new Bitfield2D(w, h);
  383. 		for (int y = 0, rOfs = 0; y < h; y++)
  384. 			for (int x = 0; x < w; x++, rOfs++)
  385. 				if (it[y][x]) r.rawset(rOfs);
  386. 		return r;
  387. 	}
  388. }
  389.  
  390. class Ideone
  391. {
  392. 	// Auto-growing bitfield for procedural generation when resulting size is impractical to predict.
  393. 	static class ProcBitfield2D {
  394. 		Bitfield2D b = new Bitfield2D(0, 0);
  395. 		int ax, ay, bx, by, boundAx, boundAy, boundBx, boundBy;
  396.  
  397. 		void set(int x, int y) {
  398. 			if (boundAx == boundBx) {
  399. 				ax = x; ay = y; bx = x; by = y;
  400. 				boundAx = x; boundAy = y; boundBx = x; boundBy = y;
  401. 			}
  402. 			if (x < ax || y < ay || x >= bx || y >= by)
  403. 				grow(
  404. 					x < ax ? growStgy(ax - x, bx - ax) : 0,
  405. 					y < ay ? growStgy(ay - y, by - ay) : 0,
  406. 					x >= bx ? growStgy(x - bx + 1, bx - ax) : 0,
  407. 					y >= by ? growStgy(y - by + 1, by - ay) : 0);
  408. 			if (x < boundAx) boundAx = x;
  409. 			if (x >= boundBx) boundBx = x + 1;
  410. 			if (y < boundAy) boundAy = y;
  411. 			if (y >= boundBy) boundBy = y + 1;
  412. 			b.set(x-ax, y-ay);
  413. 		}
  414.  
  415. 		void unset(int x, int y) {
  416. 			if (x >= boundAx && x < boundBx && x >= boundAy && x < boundBy)
  417. 				b.unset(x-ax, y-ay);
  418. 		}
  419.  
  420. 		void set(int x, int y, boolean value) { if (value) set(x, y); else unset(x, y); }
  421.  
  422. 		static int growStgy(int atLeast, int present) {
  423. 			return max(max(8, present / 2), atLeast);
  424. 		}
  425.  
  426. 		void grow(int Lx, int Ly, int Rx, int Ry) {
  427. 			this.b = new Bitfield2D((bx - ax) + Lx + Rx, (by - ay) + Ly + Ry).copyFrom(
  428. 				this.b, boundAx - ax, boundAy - ay, boundBx - boundAx, boundBy - boundAy, (boundAx - ax) + Lx, (boundAy - ay) + Ly);
  429. 			ax -= Lx; ay -= Ly; bx += Rx; by += Ry;
  430. 		}
  431.  
  432. 		Bitfield2D bake() {
  433. 			return new Bitfield2D(boundBx - boundAx, boundBy - boundAy).copyFrom(
  434. 				this.b, boundAx - ax, boundAy - ay, boundBx - boundAx, boundBy - boundAy, 0, 0);
  435. 		}
  436. 	}
  437.  
  438. 	static Bitfield2D makeSpruce(int size) {
  439. 		Util.rangecheck(size, 1, 20, "size");
  440. 		var r = new ProcBitfield2D();
  441. 		int nSegs = 3+size/4, trunkWidth = 1+size/3*2;
  442. 		int y = 0;
  443. 		for (int iSeg = 0; iSeg < nSegs; iSeg++) {
  444. 			int maxSegWidth = trunkWidth + 2 * (size + iSeg * size / 2);
  445. 			int segWidth = iSeg == 0 ? 1 : trunkWidth + (size + iSeg)/3*2;
  446. 			for (; segWidth < maxSegWidth; segWidth += 2) {
  447. 				for (int x = -segWidth/2; x < (segWidth+1)/2; x++)
  448. 					r.set(x, y);
  449. 				y += 1;
  450. 			}
  451. 		}
  452. 		for (int yTrunk = 0; yTrunk < size; yTrunk++) {
  453. 			for (int x = -trunkWidth/2; x < (trunkWidth + 1)/2; x++)
  454. 				r.set(x, y);
  455. 			y++;
  456. 		}
  457. 		return r.bake();
  458. 	}
  459.  
  460. 	static Bitfield2D moon = Bitfield2D.parse(
  461. 		"....######..........\n" +
  462. 		"..####..............\n" +
  463. 		"####................\n" +
  464. 		"####................\n" +
  465. 		"####................\n" +
  466. 		"####..............##\n" +
  467. 		"######..........####\n" +
  468. 		"..################..\n" +
  469. 		"....############", "##");
  470.  
  471. 	static Bitfield2D paintBitfield2D() {
  472. 		var r = new Bitfield2D(50, 40);
  473. 		r.or(moon, 11, 4);
  474. 		r.or(makeSpruce(4), -1, 15);
  475. 		r.or(makeSpruce(3), 29, 17);
  476. 		r.or(makeSpruce(2), 18, 18);
  477. 		r.or(makeSpruce(5), 32, 16);
  478. 		var rand = new Random(7);
  479. 		for (int iSnowflake = 0; iSnowflake < 25; iSnowflake++) {
  480. 			int x = rand.nextInt(r.width()),
  481. 				y = min(r.height() - 1, (int) (r.height() * pow(rand.nextFloat(), 2.0)));
  482. 			r.set(x, y, !r.get(x, y));
  483. 		}
  484. 		return r;
  485. 	}
  486.  
  487. 	static boolean[][] paintBool2D() {
  488. 		var r = Bool2D.create(50, 40);
  489. 		Bool2D.or(r, moon.toBool2D(), 11, 4);
  490. 		Bool2D.or(r, makeSpruce(4).toBool2D(), -1, 15);
  491. 		Bool2D.or(r, makeSpruce(3).toBool2D(), 29, 17);
  492. 		Bool2D.or(r, makeSpruce(2).toBool2D(), 18, 18);
  493. 		Bool2D.or(r, makeSpruce(5).toBool2D(), 32, 16);
  494. 		var rand = new Random(7);
  495. 		for (int iSnowflake = 0; iSnowflake < 25; iSnowflake++) {
  496. 			int x = rand.nextInt(r[0].length),
  497. 				y = min(r.length - 1, (int) (r.length * pow(rand.nextFloat(), 2.0)));
  498. 			r[y][x] = !r[y][x];
  499. 		}
  500. 		return r;
  501. 	}
  502.  
  503. 	static Bitfield2D makeRandomBitfield(int w, int h, Random rand) {
  504. 		var r = new Bitfield2D(w, h);
  505. 		for (int i = 0; i < w*h/5; i++) {
  506. 			r.set(rand.nextInt(w), rand.nextInt(h));
  507. 		}
  508. 		return r;
  509. 	}
  510.  
  511. 	static enum Op { OR, AND_NOT, COPY }
  512.  
  513. 	static class PlanItem {
  514. 		Op op;
  515. 		int rectIndex;
  516. 		int rectX, rectY, w, h, destX, destY;
  517.  
  518. 		static PlanItem random(Random rand, Bitfield2D canvas, Bitfield2D[] rects) {
  519. 			var r = new PlanItem();
  520. 			r.op = Op.values()[rand.nextInt(Op.values().length)];
  521.  
  522. 			r.rectIndex = rand.nextInt(rects.length);
  523. 			var rect = rects[r.rectIndex];
  524. 			if (rand.nextInt(2) == 0) {
  525. 				r.rectX = rand.nextInt(rect.width());
  526. 				r.rectY = rand.nextInt(rect.height());
  527. 				r.w = 1 + rand.nextInt(rect.width() - r.rectX);
  528. 				r.h = 1 + rand.nextInt(rect.height() - r.rectY);
  529. 				r.destX = -rect.width() + rand.nextInt(canvas.width() + rect.width() + 1);
  530. 				r.destY = -rect.height() + rand.nextInt(canvas.height() + rect.height() + 1);
  531. 			} else {
  532. 				r.rectX = 0;
  533. 				r.rectY = 0;
  534. 				r.w = rect.width();
  535. 				r.h = rect.height();
  536. 				r.destX = rand.nextInt(canvas.width() - rect.width());
  537. 				r.destY = rand.nextInt(canvas.height() - rect.height());
  538. 			}
  539. 			return r;
  540. 		}
  541. 	}
  542.  
  543. 	static void fusedBenchmarkTest() {
  544. 		Random rand = new Random(0);
  545. 		Bitfield2D bitCanvas = new Bitfield2D(1000, 1000);
  546. 		boolean[][] boolCanvas = Bool2D.create(bitCanvas.width(), bitCanvas.height());
  547. 		Bitfield2D bitCanvasBATCH = new Bitfield2D(bitCanvas.width(), bitCanvas.height());
  548.  
  549. 		Bitfield2D[] bitRects = new Bitfield2D[1000];
  550. 		boolean[] [][] boolRects = new boolean[bitRects.length][][];
  551. 		for (int i = 0; i < bitRects.length; i++) {
  552. 			bitRects[i] = makeRandomBitfield(1 + rand.nextInt(bitCanvas.width()/10), 1 + rand.nextInt(bitCanvas.height()/10), rand);
  553. 			boolRects[i] = bitRects[i].toBool2D();
  554. 		}
  555.  
  556. 		PlanItem[] plan = new PlanItem[600000];
  557. 		for (int i = 0; i < plan.length; i++)
  558. 			plan[i] = PlanItem.random(rand, bitCanvas, bitRects);
  559.  
  560. 		final int TRIALS = 3;
  561. 		for (int iTrial = 0; iTrial < TRIALS; iTrial++) {
  562. 			System.out.printf("%s--- TRIAL %d/%d ---\n", iTrial > 0 ? "\n" : "", 1 + iTrial, TRIALS);
  563. 			double refTime = benchmark("boolean[][]", () -> {
  564. 					for (int i = 0; i < plan.length; i++) {
  565. 						switch (plan[i].op) {
  566. 							case OR: Bool2D.or(boolCanvas, boolRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
  567. 							case AND_NOT: Bool2D.andNot(boolCanvas, boolRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
  568. 							case COPY: default: Bool2D.copyFrom(boolCanvas, boolRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
  569. 						}
  570. 					}
  571. 					return boolCanvas;
  572. 				});
  573.  
  574. 			benchmark("Bitfield2D (per-bit)", () -> {
  575. 				for (int i = 0; i < plan.length; i++) {
  576. 					switch (plan[i].op) {
  577. 						case OR: bitCanvas.or(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
  578. 						case AND_NOT: bitCanvas.andNot(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
  579. 						case COPY: default: bitCanvas.copyFrom(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
  580. 					}
  581. 				}
  582. 				return bitCanvas;
  583. 			}, refTime);
  584.  
  585. 			benchmark("Bitfield2D (bitsizeof(int) batches)", () -> {
  586. 				for (int i = 0; i < plan.length; i++) {
  587. 					switch (plan[i].op) {
  588. 						case OR: bitCanvasBATCH.orBATCH(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
  589. 						case AND_NOT: bitCanvasBATCH.andNotBATCH(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
  590. 						case COPY: default: bitCanvasBATCH.copyFrom(bitRects[plan[i].rectIndex], plan[i].rectX, plan[i].rectY, plan[i].w, plan[i].h, plan[i].destX, plan[i].destY); break;
  591. 					}
  592. 				}
  593. 				return bitCanvasBATCH;
  594. 			}, refTime);
  595.  
  596. 			if (iTrial == 0) {
  597. 				String ref = Bool2D.toString(boolCanvas);
  598. 				if (!bitCanvas.toString().equals(ref))
  599. 					throw new RuntimeException("Bitfield2D(per-bit) and boolean[][] do differ.");
  600. 				if (!bitCanvasBATCH.toString().equals(ref))
  601. 					throw new RuntimeException("Bitfield2D(bitsizeof(int) batches) and boolean[][] do differ.");
  602. 			}
  603. 		}
  604. 	}
  605.  
  606. 	@FunctionalInterface
  607. 	interface BenchmarkPayload {
  608. 		abstract Object run();
  609. 	}
  610.  
  611. 	static double benchmark(String title, BenchmarkPayload payload) {
  612. 		return benchmark(title, payload, -1);
  613. 	}
  614.  
  615. 	static double benchmark(String title, BenchmarkPayload payload, double refTime) {
  616. 		long start = System.nanoTime();
  617. 		Object keepAlive = payload.run();
  618. 		double time = (System.nanoTime() - start) * 1e-9;
  619. 		System.out.println(String.format(
  620. 			"%s: %.2f s%s",
  621. 			title, time, refTime >= 0 ? String.format(" (%s)", judgement(time, refTime)) : "", keepAlive));
  622. 		return time;
  623. 	}
  624.  
  625. 	static String judgement(double time, double refTime) {
  626. 		final double absThreshold = 0.3, relThreshold = .1;
  627.  
  628. 		return time <= absThreshold || refTime <= absThreshold ?
  629. 			String.format("can't judge, min. required time is %.1f s", absThreshold) :
  630. 			Math.max(time, refTime) > (1 + relThreshold) * Math.min(time, refTime) ?
  631. 			String.format("%.0f%% %s",
  632. 				Math.abs((time < refTime ? refTime / time : time / refTime) - 1) * 100,
  633. 				time < refTime ? "faster" : "slower") :
  634. 			String.format("no observable difference, min. %.0f%% required", relThreshold * 100);
  635. 	}
  636.  
  637. 	public static void main (String[] args) throws java.lang.Exception
  638. 	{
  639. 		try {
  640. 			var image = paintBitfield2D();
  641. 			var im2 = paintBool2D();
  642. 			if (!image.toString().equals(Bool2D.toString(im2))) {
  643. 				throw new RuntimeException(String.format("paintBool2D =\n%s\n\nyet paintBitfield2D =\n%s", im2, image));
  644. 			}
  645. 			fusedBenchmarkTest();
  646. 			System.out.printf("\n%s\n\n", image);
  647. 		} catch (Exception e) {
  648. 			System.out.println(Util.trace(e));
  649. 		}
  650. 	}
  651. }
Success #stdin #stdout 8.55s 146744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
--- TRIAL 1/3 ---
boolean[][]: 0.69 s
Bitfield2D (per-bit): 1.77 s (155% slower)
Bitfield2D (bitsizeof(int) batches): 0.43 s (60% faster)

--- TRIAL 2/3 ---
boolean[][]: 0.63 s
Bitfield2D (per-bit): 1.65 s (162% slower)
Bitfield2D (bitsizeof(int) batches): 0.41 s (53% faster)

--- TRIAL 3/3 ---
boolean[][]: 0.57 s
Bitfield2D (per-bit): 1.64 s (190% slower)
Bitfield2D (bitsizeof(int) batches): 0.33 s (71% faster)

..............##....................................##................##............##..............
....................................................................................................
................##..................................................................................
..............................................##....................................................
..........................######....................................................................
........................####........................................................................
......................####..........................................................................
......................####..........................................................................
......................####..........................................................................
......................####..............##..................##......................................
......................######..........####..........................................................
........................################............................................................
##........................############..............................................................
..............................................................................##....................
....................................................##............##................................
..................##..........................##..........##........................................
................######..................................................##..............##..........
..............##########..............................................##..............######........
............##########..##................##........................######..........########........
..........##################........##..######....................##########......########..####....
..............##########................######..................######..######..##################..
............##############............##########..................##########..######################
..........##################........##..######..................##..##########....##############....
........######################........##########..............####################################..
......##########################....##############................##########..######################
............##############................##....................####################################
..........##################..............##..................######################################
........######################..............................####################################....
......##########################....##....................########################################..
....##############################..................................######....######################
..##################################................................######..########################
............##############..........................................################################
..........##################............................................############################
........######################........................................##############################
......##################..######....................................################################
....##############################................................................##############....
####################################............................................##################..
######################################............##..........................######################
########################################....................................########################
................######....................................................##########################
https://ideone.com/FLigf3
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!