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 BASE = Integer.SIZE;
  28. 	static final int SANE_BITS_LIMIT = 1_000_000_000;
  29. 	static final int SANE_DIMENSION_LIMIT = 100_000_000;
  30.  
  31. 	public Bitfield2D(int w, int h) { init(null, w, h); }
  32. 	Bitfield2D(int[] data, int w, int h) { init(data, w, h); }
  33.  
  34. 	private void init(int[] data, int w, int h) {
  35. 		validateSize(w, h);
  36. 		assert data == null || data.length >= (w*h + (BASE - 1)) / BASE;
  37. 		this.data = data != null ? data : new int[(w*h + (BASE - 1)) / BASE];
  38. 		this.w = w;
  39. 		this.h = h;
  40. 	}
  41.  
  42. 	static void validateSize(int w, int h) {
  43. 		if (w < 0 || h < 0 || w > SANE_DIMENSION_LIMIT || h > SANE_DIMENSION_LIMIT
  44. 			|| w > 0 && h > SANE_BITS_LIMIT / w)
  45. 			throw Util.BadArgf("Bad bitfield size: %d×%d.", w, h);
  46. 	}
  47.  
  48. 	public boolean validCoord(int x, int y) {
  49. 		return x >= 0 && y >= 0 && x < w && y < h;
  50. 	}
  51.  
  52. 	public void validateCoord(int x, int y) {
  53. 		if (!validCoord(x, y))
  54. 			throw Util.BadArgf("Bad coord of bitfield %d×%d: (%d, %d).", this.w, this.h, x, y);
  55. 	}
  56.  
  57. 	void validateRect(int x, int y, int w, int h) {
  58. 		if (x < 0 || y < 0 || w < 0 || h < 0 || x + w > this.w || y + h > this.h)
  59. 			throw Util.BadArgf("Bad rect of bitfield %d×%d: (%d, %d) ~ (%d, %d).",
  60. 				this.w, this.h, x, y, x+w, y+h);
  61. 	}
  62.  
  63. 	boolean rawget(int index) { return (data[index / BASE] & (1 << (index % BASE))) != 0; }
  64. 	void rawset(int index) { data[index / BASE] |= 1 << (index % BASE); }
  65. 	void rawunset(int index) { data[index / BASE] &= ~(1 << (index % BASE)); }
  66. 	void rawset(int index, boolean value) { if (value) rawset(index); else rawunset(index); }
  67.  
  68. 	public boolean get(int x, int y) { validateCoord(x, y); return rawget(y*w+x); }
  69. 	public void set(int x, int y) { validateCoord(x, y); rawset(y*w+x); }
  70. 	public void unset(int x, int y) { validateCoord(x, y); rawunset(y*w+x); }
  71. 	public void set(int x, int y, boolean value) { validateCoord(x, y); rawset(y*w+x, value); }
  72. 	public int width() { return w; }
  73. 	public int height() { return h; }
  74.  
  75. 	// For functions like or() that apply one bitfield to another,
  76. 	// reduces potentially out-of-borders input to its valid part.
  77. 	static class CoordWarden {
  78. 		int srcX, srcY, w, h, destX, destY;
  79. 		CoordWarden(Bitfield2D dest, Bitfield2D src, int aSrcX, int aSrcY, int aW, int aH, int aDestX, int aDestY) {
  80. 			src.validateRect(aSrcX, aSrcY, aW, aH);
  81. 			srcX = aSrcX; srcY = aSrcY; w = aW; h = aH; destX = aDestX; destY = aDestY;
  82. 			if (destX < 0) { srcX -= destX; w += destX; destX = 0; }
  83. 			if (destX + w > dest.w) { w = dest.w - destX; }
  84. 			if (destY < 0) { srcY -= destY; h += destY; destY = 0; }
  85. 			if (destY + h > dest.h) { h = dest.h - destY; }
  86. 		}
  87. 	}
  88.  
  89. 	public void or(Bitfield2D b, int destX, int destY) {
  90. 		or(b, 0, 0, b.w, b.h, destX, destY);
  91. 	}
  92.  
  93. 	public void or(Bitfield2D b, int bx, int by, int w, int h, int destX, int destY) {
  94. 		var ward = new CoordWarden(this, b, bx, by, w, h, destX, destY);
  95. 		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
  96. 		for (by = 0; by < ward.h; by++, thisOfs += this.w - ward.w, bOfs += b.w - ward.w) {
  97. 			for (bx = 0; bx < ward.w; bx++, thisOfs++, bOfs++)
  98. 				if (b.rawget(bOfs)) this.rawset(thisOfs);
  99. 		}
  100. 	}
  101.  
  102. 	public void andNot(Bitfield2D b, int destX, int destY) {
  103. 		andNot(b, 0, 0, b.w, b.h, destX, destY);
  104. 	}
  105.  
  106. 	public void andNot(Bitfield2D b, int bx, int by, int w, int h, int destX, int destY) {
  107. 		var ward = new CoordWarden(this, b, bx, by, w, h, destX, destY);
  108. 		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
  109. 		for (by = 0; by < ward.h; by++, thisOfs += this.w - ward.w, bOfs += b.w - ward.w) {
  110. 			for (bx = 0; bx < ward.w; bx++, thisOfs++, bOfs++)
  111. 				if (b.rawget(bOfs)) this.rawunset(thisOfs);
  112. 		}
  113. 	}
  114.  
  115. 	public Bitfield2D copyFrom(Bitfield2D b, int destX, int destY) {
  116. 		return copyFrom(b, 0, 0, b.w, b.h, destX, destY);
  117. 	}
  118.  
  119. 	public Bitfield2D copyFrom(Bitfield2D b, int bx, int by, int w, int h, int destX, int destY) {
  120. 		var ward = new CoordWarden(this, b, bx, by, w, h, destX, destY);
  121. 		int thisOfs = ward.destY*this.w + ward.destX, bOfs = ward.srcY*b.w + ward.srcX;
  122. 		for (by = 0; by < ward.h; by++, thisOfs += this.w, bOfs += b.w) {
  123. 			copyBits(b.data, bOfs, this.data, thisOfs, ward.w);
  124. 		}
  125. 		return this;
  126. 	}
  127.  
  128. 	static int readBitsSmall(int[] src, int srcPos, int count) {
  129. 		assert count > 0 && count < BASE;
  130. 		//       0       1       2       3       4       5       6
  131. 		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  132. 		//            ^srcPos=5
  133. 		//                  ^srcPos+count=11
  134. 		int bits = src[srcPos / BASE] >>> (srcPos % BASE); // FGH
  135. 		if (count > BASE - srcPos % BASE)
  136. 			bits |= src[srcPos / BASE + 1] << (BASE - srcPos % BASE); // FGH | 000IJKLMNOP = FGHIJKLMNOP
  137. 		return bits & ((1 << count) - 1); // FGHIJK
  138. 	}
  139.  
  140. 	static void writeBits1(int bits, int[] dst, int dstPos, int count) {
  141. 		assert count > 0 && count < BASE - dstPos % BASE && bits < 1 << count;
  142. 		// bits = qwer
  143. 		//       0       1       2       3       4       5       6
  144. 		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  145. 		//          ^dstPos=3
  146. 		//              ^dstPos+count=7
  147. 		dst[dstPos / BASE] = dst[dstPos / BASE] // ABCDEFGH
  148. 			& ~(((1 << count) - 1) << (dstPos % BASE)) // ABC0000H
  149. 			| (bits << (dstPos % BASE)); // ABCqwerH
  150. 	}
  151.  
  152. 	static void copyBits(int[] src, int srcPos, int[] dst, int dstPos, int count) {
  153. 		// Imagine BASE=8 (as if byte[] instead of int[]), srcPos = 3, dstPos = 2, count=25.
  154. 		//
  155. 		//       0       1       2       3       4       5       6
  156. 		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  157. 		//          ^srcPos=3                ^srcPos+count=28
  158. 		// dst = ...............................................
  159. 		//       0 ^dstPos=2     2       3       4       5
  160. 		//
  161. 		// First we align dstPos to the multiple of BASE by reading
  162. 		// first BASE - dstPos%BASE bits with readBitsSmall() and writing them
  163. 		// into the first cell of dst[] with writeBits1.
  164. 		//
  165. 		// We'll get:
  166. 		//       0       1       2       3       4       5       6
  167. 		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  168. 		//                ^srcPos=9          ^srcPos+count=28
  169. 		// dst = ..DEFGHI.......................................
  170. 		//       0       1       2       3       4       5
  171. 		//               ^dstPos=8
  172. 		if (dstPos % BASE != 0) {
  173. 			int n = min(count, BASE - dstPos % BASE);
  174. 			if (n > 0) writeBits1(readBitsSmall(src, srcPos, n), dst, dstPos, n);
  175. 			srcPos += n;
  176. 			dstPos += n;
  177. 			count -= n;
  178. 		}
  179.  
  180. 		// Now we fill whole cells while possible.
  181. 		// We'll get:
  182. 		// src = ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
  183. 		//                                ^srcPos=25
  184. 		//                                   ^srcPos+count=28
  185. 		// dst = ..DEFGHIJKLMNOPQRSTUVWXY.......................
  186. 		//       0       1       2       3       4       5
  187. 		//                               ^dstPos=24
  188. 		if (srcPos % BASE == 0) {
  189. 			// Aligned case. This is not even an optimization, because 'int' shifts are restricted to 0..31.
  190. 			System.arraycopy(src, srcPos / BASE, dst, dstPos / BASE, count / BASE);
  191. 		} else {
  192. 			// Unaligned case.
  193. 			// src: ...ABCDE FGH.....
  194. 			//         ^srcPos
  195. 			// dst: ........
  196. 			for (int iSrc = srcPos / BASE, iDst = dstPos / BASE, iDstEd = iDst + count / BASE; iDst < iDstEd; iDst++, iSrc++)
  197. 				dst[iDst] =
  198. 					(src[iSrc] >>> (srcPos % BASE)) // ABCDE
  199. 					| (src[iSrc + 1] << (BASE - srcPos % BASE)); // ABCDE | 00000FGH = ABCDEFGH
  200. 		}
  201. 		srcPos += count - count % BASE;
  202. 		dstPos += count - count % BASE;
  203. 		count %= BASE;
  204.  
  205. 		// Append the tail.
  206. 		if (count > 0)
  207. 			writeBits1(readBitsSmall(src, srcPos, count), dst, dstPos, count);
  208. 	}
  209.  
  210. 	@Override
  211. 	public String toString() {
  212. 		return toString("##", "..");
  213. 	}
  214.  
  215. 	public String toString(String one, String zero) {
  216. 		var sb = new StringBuilder();
  217. 		for (int ofs = 0, y = 0; y < h; y++) {
  218. 			if (y > 0) sb.append("\n");
  219. 			for (int x = 0; x < w; x++, ofs++)
  220. 				sb.append(rawget(ofs) ? one : zero);
  221. 		}
  222. 		return sb.toString();
  223. 	}
  224.  
  225. 	static Bitfield2D parse(String src) { return parse(src, "##"); }
  226.  
  227. 	static Bitfield2D parse(String src, String one) {
  228. 		if (one.isEmpty()) throw Util.BadArgf("'one' can't be empty.");
  229. 		if (one.indexOf('\n') >= 0) throw Util.BadArgf("Bad 'one': \"%s\". Shouldn't contain EOL.", one);
  230. 		// Prepass for size.
  231. 		int w = 0, h = 0;
  232. 		for (int pos = 0; pos < src.length(); ) {
  233. 			int eolp = src.indexOf("\n", pos);
  234. 			if (eolp < 0) eolp = src.length();
  235. 			if ((eolp - pos) % one.length() != 0)
  236. 				throw Util.BadArgf("Line %d:\n%s\ncontains %d character%s, which is not multiple of len(%s) = %d.",
  237. 					h, src.substring(pos, eolp), eolp - pos, eolp - pos != 1 ? "s" : "", one, one.length());
  238. 			w = max(w, (eolp - pos) / one.length());
  239. 			h++;
  240. 			pos = eolp + "\n".length();
  241. 		}
  242. 		var r = new Bitfield2D(w, h);
  243.  
  244. 		for (int y = 0, x = 0, ofs = 0, pos = 0; pos < src.length(); )
  245. 			if (src.charAt(pos) == '\n') {
  246. 				ofs += r.w - x;
  247. 				x = 0; y++;
  248. 				pos += "\n".length();
  249. 			} else {
  250. 				if (src.startsWith(one, pos)) r.rawset(ofs);
  251. 				pos += one.length();
  252. 				x++; ofs++;
  253. 			}
  254. 		return r;
  255. 	}
  256. }
  257.  
  258. class Ideone
  259. {
  260. 	// Auto-growing bitfield for procedural generation when resulting size is impractical to predict.
  261. 	static class ProcBitfield2D {
  262. 		Bitfield2D b = new Bitfield2D(0, 0);
  263. 		int ax, ay, bx, by, boundAx, boundAy, boundBx, boundBy;
  264.  
  265. 		void set(int x, int y) {
  266. 			if (boundAx == boundBx) {
  267. 				ax = x; ay = y; bx = x; by = y;
  268. 				boundAx = x; boundAy = y; boundBx = x; boundBy = y;
  269. 			}
  270. 			if (x < ax || y < ay || x >= bx || y >= by)
  271. 				grow(
  272. 					x < ax ? growStgy(ax - x, bx - ax) : 0,
  273. 					y < ay ? growStgy(ay - y, by - ay) : 0,
  274. 					x >= bx ? growStgy(x - bx + 1, bx - ax) : 0,
  275. 					y >= by ? growStgy(y - by + 1, by - ay) : 0);
  276. 			if (x < boundAx) boundAx = x;
  277. 			if (x >= boundBx) boundBx = x + 1;
  278. 			if (y < boundAy) boundAy = y;
  279. 			if (y >= boundBy) boundBy = y + 1;
  280. 			b.set(x-ax, y-ay);
  281. 		}
  282.  
  283. 		void unset(int x, int y) {
  284. 			if (x >= boundAx && x < boundBx && x >= boundAy && x < boundBy)
  285. 				b.unset(x-ax, y-ay);
  286. 		}
  287.  
  288. 		void set(int x, int y, boolean value) { if (value) set(x, y); else unset(x, y); }
  289.  
  290. 		static int growStgy(int atLeast, int present) {
  291. 			return max(max(8, present / 2), atLeast);
  292. 		}
  293.  
  294. 		void grow(int Lx, int Ly, int Rx, int Ry) {
  295. 			this.b = new Bitfield2D((bx - ax) + Lx + Rx, (by - ay) + Ly + Ry).copyFrom(
  296. 				this.b, boundAx - ax, boundAy - ay, boundBx - boundAx, boundBy - boundAy, (boundAx - ax) + Lx, (boundAy - ay) + Ly);
  297. 			ax -= Lx; ay -= Ly; bx += Rx; by += Ry;
  298. 		}
  299.  
  300. 		Bitfield2D bake() {
  301. 			return new Bitfield2D(boundBx - boundAx, boundBy - boundAy).copyFrom(
  302. 				this.b, boundAx - ax, boundAy - ay, boundBx - boundAx, boundBy - boundAy, 0, 0);
  303. 		}
  304. 	}
  305.  
  306. 	static Bitfield2D makeSpruce(int size) {
  307. 		Util.rangecheck(size, 1, 20, "size");
  308. 		var r = new ProcBitfield2D();
  309. 		int nSegs = 3+size/4, trunkWidth = 1+size/3*2;
  310. 		int y = 0;
  311. 		for (int iSeg = 0; iSeg < nSegs; iSeg++) {
  312. 			int maxSegWidth = trunkWidth + 2 * (size + iSeg * size / 2);
  313. 			int segWidth = iSeg == 0 ? 1 : trunkWidth + (size + iSeg)/3*2;
  314. 			for (; segWidth < maxSegWidth; segWidth += 2) {
  315. 				for (int x = -segWidth/2; x < (segWidth+1)/2; x++)
  316. 					r.set(x, y);
  317. 				y += 1;
  318. 			}
  319. 		}
  320. 		for (int yTrunk = 0; yTrunk < size; yTrunk++) {
  321. 			for (int x = -trunkWidth/2; x < (trunkWidth + 1)/2; x++)
  322. 				r.set(x, y);
  323. 			y++;
  324. 		}
  325. 		return r.bake();
  326. 	}
  327.  
  328. 	public static void main (String[] args) throws java.lang.Exception
  329. 	{
  330. 		try {
  331. 			var r = new Bitfield2D(50, 40);
  332. 			var moon = Bitfield2D.parse(
  333. 				"....######..........\n" +
  334. 				"..####..............\n" +
  335. 				"####................\n" +
  336. 				"####................\n" +
  337. 				"####................\n" +
  338. 				"####..............##\n" +
  339. 				"######..........####\n" +
  340. 				"..################..\n" +
  341. 				"....############", "##");
  342. 			r.or(moon, 11, 4);
  343. 			r.or(makeSpruce(4), -1, 15);
  344. 			r.or(makeSpruce(3), 29, 17);
  345. 			r.or(makeSpruce(2), 18, 18);
  346. 			r.or(makeSpruce(5), 32, 16);
  347. 			var rand = new Random(7);
  348. 			for (int iSnowflake = 0; iSnowflake < 25; iSnowflake++) {
  349. 				int x = rand.nextInt(r.width()),
  350. 					y = min(r.height() - 1, (int) (r.height() * pow(rand.nextFloat(), 2.0)));
  351. 				r.set(x, y, !r.get(x, y));
  352. 			}
  353. 			System.out.printf("%s\n\n", r);
  354. 		} catch (Exception e) {
  355. 			System.out.println(Util.trace(e));
  356. 		}
  357. 	}
  358. }
Success #stdin #stdout 0.12s 34300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
..............##....................................##................##............##..............
....................................................................................................
................##..................................................................................
..............................................##....................................................
..........................######....................................................................
........................####........................................................................
......................####..........................................................................
......................####..........................................................................
......................####..........................................................................
......................####..............##..................##......................................
......................######..........####..........................................................
........................################............................................................
##........................############..............................................................
..............................................................................##....................
....................................................##............##................................
..................##..........................##..........##........................................
................######..................................................##..............##..........
..............##########..............................................##..............######........
............##########..##................##........................######..........########........
..........##################........##..######....................##########......########..####....
..............##########................######..................######..######..##################..
............##############............##########..................##########..######################
..........##################........##..######..................##..##########....##############....
........######################........##########..............####################################..
......##########################....##############................##########..######################
............##############................##....................####################################
..........##################..............##..................######################################
........######################..............................####################################....
......##########################....##....................########################################..
....##############################..................................######....######################
..##################################................................######..########################
............##############..........................................################################
..........##################............................................############################
........######################........................................##############################
......##################..######....................................################################
....##############################................................................##############....
####################################............................................##################..
######################################............##..........................######################
########################################....................................########################
................######....................................................##########################
https://ideone.com/6SNrhV
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!