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 Common {
  8. 	static NoSuchElementException dequeEmpty() {
  9. 		return new NoSuchElementException("The deque is empty");
  10. 	}
  11. }
  12.  
  13. class AryDeque<T> {
  14. 	private Object[] data = new Object[2];
  15. 	private int lo = 0;
  16. 	private int hi = 0;
  17. 	private boolean grow32;
  18.  
  19. 	public AryDeque(boolean grow32) {
  20. 		this.grow32 = grow32;
  21. 	}
  22.  
  23. 	public void addFront(T value) {
  24. 		grow(1);
  25. 		lo = dec(lo);
  26. 		data[lo] = value;
  27. 	}
  28.  
  29. 	public void addBack(T value) {
  30. 		grow(1);
  31. 		data[hi] = value;
  32. 		hi = inc(hi);
  33. 	}
  34.  
  35. 	public T popFront() {
  36. 		if (lo == hi) throw Common.dequeEmpty();
  37. 		T value = (T) data[lo];
  38. 		data[lo] = null;
  39. 		lo = inc(lo);
  40. 		shrink();
  41. 		return value;
  42. 	}
  43.  
  44. 	public T popBack() {
  45. 		if (lo == hi) throw Common.dequeEmpty();
  46. 		hi = dec(hi);
  47. 		T value = (T) data[hi];
  48. 		data[hi] = null;
  49. 		shrink();
  50. 		return value;
  51. 	}
  52.  
  53. 	private int dec(int i) {
  54. 		return --i >= 0 ? i : i + data.length;
  55. 	}
  56.  
  57. 	private int inc(int i) {
  58. 		return ++i < data.length ? i : i - data.length;
  59. 	}
  60.  
  61. 	private int getItemsCount() {
  62. 		return lo == hi ? 0 : lo < hi ? hi - lo : data.length - lo + hi;
  63. 	}
  64.  
  65. 	private void grow(int by) {
  66. 		int itemsCount = getItemsCount();
  67. 		if (itemsCount + by + 1 > data.length) {
  68. 			reallocate(max(itemsCount + by + 1, grow32 ? data.length + max(4, data.length / 2) : 2 * data.length));
  69. 		}
  70. 	}
  71.  
  72. 	private void shrink() {
  73. 		int itemsCount = getItemsCount();
  74. 		if ((itemsCount == 0 || data.length > 8) && itemsCount <= data.length / 4) {
  75. 			reallocate(itemsCount == 0 ? 2 : grow32 ? itemsCount + max(4, itemsCount) : 2 * itemsCount);
  76. 		}
  77. 	}
  78.  
  79. 	private void reallocate(int newSize) {
  80. 		assert newSize >= 1 + getItemsCount();
  81.  
  82. 		Object[] newData = new Object[newSize];
  83. 		if (lo != hi) {
  84. 			System.arraycopy(data, lo, newData, 0, (lo < hi ? hi : data.length) - lo);
  85. 			if (lo > hi) System.arraycopy(data, 0, newData, data.length - lo, hi);
  86. 		}
  87. 		hi = getItemsCount();
  88. 		lo = 0;
  89. 		data = newData;
  90. 	}
  91.  
  92. 	public String dump() {
  93. 		return String.format("%s lo = %d hi = %d", Arrays.toString(data), lo, hi);
  94. 	}
  95.  
  96. 	public List<T> toList() {
  97. 		List<T> result = new ArrayList<T>();
  98. 		if (lo != hi) {
  99. 			result.addAll(Arrays.asList((T[]) data).subList(lo, lo < hi ? hi : data.length));
  100. 			if (lo > hi) result.addAll(Arrays.asList((T[]) data).subList(0, hi));
  101. 		}
  102. 		return result;
  103. 	}
  104. }
  105.  
  106. /**
  107.  * Deque built over linked list.
  108.  */
  109. class LLDeque<T> {
  110. 	static class Node<T> {
  111. 		T value;
  112. 		Node prev, next;
  113. 	}
  114.  
  115. 	Node<T> first, last;
  116.  
  117. 	public void addFront(T value) {
  118. 		Node<T> n = new Node<T>();
  119. 		n.value = value;
  120. 		n.next = first;
  121. 		if (first == null) last = n; else first.prev = n;
  122. 		first = n;
  123. 	}
  124.  
  125. 	public void addBack(T value) {
  126. 		Node<T> n = new Node<T>();
  127. 		n.value = value;
  128. 		n.prev = last;
  129. 		if (last == null) first = n; else last.next = n;
  130. 		last = n;
  131. 	}
  132.  
  133. 	public T popFront() {
  134. 		if (first == null) throw Common.dequeEmpty();
  135. 		T value = first.value;
  136. 		first = first.next;
  137. 		if (first == null) last = null; else first.prev = null;
  138. 		return value;
  139. 	}
  140.  
  141. 	public T popBack() {
  142. 		if (last == null) throw Common.dequeEmpty();
  143. 		T value = last.value;
  144. 		last = last.prev;
  145. 		if (last == null) first = null; else last.next = null;
  146. 		return value;
  147. 	}
  148.  
  149. 	public List<T> toList() {
  150. 		List<T> result = new ArrayList<T>();
  151. 		for (Node<T> n = first; n != null; n = n.next) {
  152. 			result.add(n.value);
  153. 		}
  154. 		return result;
  155. 	}
  156. }
  157.  
  158. /**
  159.  * Deque built over unrolled circular linked list with at most 2 "cached" empty nodes
  160.  * right after tail and before head.
  161.  * Thanks to these empty nodes, pushes and pops that happen to repeatedly over-
  162.  * and underflow head and tail won't provoke excessive amount of allocations.
  163.  *
  164.  * So the possible configurations are:
  165.  * head -> (head)
  166.  * — starting configuration, head == tail == head.next == head.prev.
  167.  *
  168.  * head -> ... ... ... -> tail -> (head)
  169.  * — no empty node after tail, tail.next == head,
  170.  * -or-
  171.  * head -> ... ... ... -> tail -> empty_node -> (head)
  172.  * — 1 empty node after tail, tail.next.next == head.
  173.  * Should an edge node become empty, it will be kept for reuse.
  174.  *
  175.  * head -> ... ... ... -> tail -> empty_node0 -> empty_node1 -> (head)
  176.  * — 2 empty nodes between tail and head.
  177.  * If another node becomes empty, one of these 3 finally gets disposed of.
  178.  */
  179. class UCLLDeque<T> {
  180. 	static class Node<T> {
  181. 		Object[] values;
  182. 		Node prev, next;
  183.  
  184. 		Node(int size) {
  185. 			values = new Object[size];
  186. 		}
  187. 	}
  188. 	static enum ImplementationVariant {
  189. 		LEGACY_INCORRECT,
  190. 		LEGACY,
  191. 		GOOD
  192. 	};
  193. 	public static ImplementationVariant LEGACY_INCORRECT = ImplementationVariant.LEGACY_INCORRECT;
  194. 	public static ImplementationVariant LEGACY = ImplementationVariant.LEGACY;
  195. 	public static ImplementationVariant GOOD = ImplementationVariant.GOOD;
  196.  
  197. 	Node<T> headNode, tailNode;
  198. 	int iHead, iTail;
  199. 	private final ImplementationVariant implv;
  200.  
  201. 	public UCLLDeque(ImplementationVariant implv) {
  202. 		headNode = new Node<T>(4);
  203. 		tailNode = headNode;
  204. 		headNode.prev = tailNode;
  205. 		headNode.next = tailNode;
  206. 		this.implv = implv;
  207. 	}
  208.  
  209. 	public void addFront(T value) {
  210. 		if (iHead == 0) {
  211. 			headNode = headNode.prev != tailNode ? headNode.prev : insertNode(createNode(), true, headNode);
  212. 			iHead = headNode.values.length;
  213.  
  214. 			if (implv == GOOD) {
  215. 				// do nothing
  216. 			} else if (iTail == 0) {
  217. 				tailNode = tailNode.prev;
  218. 				iTail = tailNode.values.length;
  219. 			}
  220. 		}
  221. 		headNode.values[--iHead] = value;
  222. 	}
  223.  
  224. 	public void addBack(T value) {
  225. 		if (implv == GOOD) {
  226. 			tailNode.values[iTail++] = value;
  227. 			if (iTail == tailNode.values.length) {
  228. 				tailNode = tailNode.next != headNode ? tailNode.next : insertNode(createNode(), false, tailNode);
  229. 				iTail = 0;
  230. 			}
  231. 		} else {
  232. 			if (iTail == tailNode.values.length) {
  233. 				tailNode = tailNode.next != headNode ? tailNode.next : insertNode(createNode(), false, tailNode);
  234. 				iTail = 0;
  235. 				if (implv == LEGACY_INCORRECT) {
  236. 					// don't check against headNode.values.length
  237. 				} else if (iHead == headNode.values.length) {
  238. 					headNode = headNode.next;
  239. 					iHead = 0;
  240. 				}
  241. 			}
  242. 			tailNode.values[iTail++] = value;
  243. 		}
  244. 	}
  245.  
  246. 	public T popFront() {
  247. 		if (headNode == tailNode && iHead == iTail) {
  248. 			throw Common.dequeEmpty();
  249. 		}
  250. 		T value = (T) headNode.values[iHead];
  251. 		headNode.values[iHead++] = null;
  252. 		if (iHead == headNode.values.length && (implv == GOOD || headNode != tailNode)) {
  253. 			if (headNode.prev != tailNode && headNode.prev.prev != tailNode) {
  254. 				removeNode(headNode.prev.prev);
  255. 			}
  256. 			headNode = headNode.next;
  257. 			iHead = 0;
  258. 		}
  259. 		return value;
  260. 	}
  261.  
  262. 	public T popBack() {
  263. 		if (tailNode == headNode && iTail == iHead) {
  264. 			throw Common.dequeEmpty();
  265. 		}
  266. 		if (implv == GOOD) {
  267. 			if (iTail == 0) {
  268. 				if (tailNode.next != headNode && tailNode.next.next != headNode) {
  269. 					removeNode(tailNode.next.next);
  270. 				}
  271. 				tailNode = tailNode.prev;
  272. 				iTail = tailNode.values.length;
  273. 			}
  274. 			T value = (T) tailNode.values[--iTail];
  275. 			tailNode.values[iTail] = null;
  276. 			return value;
  277. 		} else {
  278. 			T value = (T) tailNode.values[--iTail];
  279. 			tailNode.values[iTail] = null;
  280. 			if (iTail == 0 && tailNode != headNode) {
  281. 				if (tailNode.next != headNode && tailNode.next.next != headNode) {
  282. 					removeNode(tailNode.next.next);
  283. 				}
  284. 				tailNode = tailNode.prev;
  285. 				iTail = tailNode.values.length;
  286. 			}
  287. 			return value;
  288. 		}
  289. 	}
  290.  
  291. 	private int calcItemsCount() {
  292. 		int count = 0;
  293. 		for (Node<T> n = headNode, prevN = null; prevN != tailNode; prevN = n, n = n.next) {
  294. 			count += (n == tailNode ? iTail : n.values.length) - (n == headNode ? iHead : 0);
  295. 		}
  296. 		return count;
  297. 	}
  298.  
  299. 	private Node<T> createNode() {
  300. 		return new Node<T>(max(4, calcItemsCount() / 2));
  301. 	}
  302.  
  303. 	private Node<T> insertNode(Node node, boolean before, Node adjacent) {
  304. 		Node<T> prev = before ? adjacent.prev : adjacent;
  305. 		Node<T> next = before ? adjacent : adjacent.next;
  306. 		node.prev = prev;
  307. 		node.next = next;
  308. 		prev.next = node;
  309. 		next.prev = node;
  310. 		return node;
  311. 	}
  312.  
  313. 	private static <T> void removeNode(Node<T> node) {
  314. 		Node<T> n_prev = node.prev, n_next = node.next;
  315. 		n_prev.next = n_next;
  316. 		n_next.prev = n_prev;
  317. 	}
  318.  
  319. 	public String dump() {
  320. 		StringBuilder r = new StringBuilder(), desc = new StringBuilder();
  321. 		r.append("items=").append(calcItemsCount());
  322. 		boolean tailSeen = false;
  323. 		for (Node<T> n = headNode, stopN = null; n != stopN; stopN = headNode, n = n.next) {
  324. 			r.append("\n").append(Arrays.toString(n.values));
  325. 			desc.setLength(0);
  326. 			if (n == headNode) desc.append(desc.length() > 0 ? ", " : ": ").append("iHead=").append(iHead);
  327. 			if (n == tailNode) desc.append(desc.length() > 0 ? ", " : ": ").append("iTail=").append(iTail);
  328. 			if (tailSeen) desc.append(desc.length() > 0 ? ", " : ": ").append("dangling");
  329. 			r.append(desc);
  330. 			tailSeen |= n == tailNode;
  331. 		}
  332. 		return r.toString();
  333. 	}
  334.  
  335. 	public List<T> toList() {
  336. 		List<T> result = new ArrayList<T>();
  337. 		for (Node<T> n = headNode, prevN = null; prevN != tailNode; prevN = n, n = n.next) {
  338. 			result.addAll(((List<T>) Arrays.asList(n.values)).subList(
  339. 				n == headNode ? iHead : 0, n == tailNode ? iTail : n.values.length));
  340. 		}
  341. 		return result;
  342. 	}
  343. }
  344.  
  345. class UCLLDequeTracer<T> {
  346. 	private UCLLDeque<T> deque;
  347. 	private PrintStream out;
  348.  
  349. 	public UCLLDequeTracer(UCLLDeque<T> deque, PrintStream out) {
  350. 		this.deque = deque;
  351. 		this.out = out;
  352. 	}
  353.  
  354. 	public void addFront(T value) {
  355. 		deque.addFront(value);
  356. 		out.printf("addFront(%s): %s\n\n", value, deque.dump());
  357. 	}
  358.  
  359. 	public void addBack(T value) {
  360. 		deque.addBack(value);
  361. 		out.printf("addBack(%s): %s\n\n", value, deque.dump());
  362. 	}
  363.  
  364. 	public T popFront() {
  365. 		T value = deque.popFront();
  366. 		out.printf("popFront() -> %s: %s\n\n", value, deque.dump());
  367. 		return value;
  368. 	}
  369.  
  370. 	public T popBack() {
  371. 		T value = deque.popBack();
  372. 		out.printf("popBack() -> %s: %s\n\n", value, deque.dump());
  373. 		return value;
  374. 	}
  375. }
  376.  
  377. class Application {
  378. 	static final int OP_ADD_FRONT = 0;
  379. 	static final int OP_ADD_BACK = 1;
  380. 	static final int OP_POP_FRONT = 2;
  381. 	static final int OP_POP_BACK = 3;
  382. 	static final int DUMMIES = 10;
  383. 	static final int LEN_LIMIT = 100000;
  384. 	static final int OPS_COUNT = 4000000;
  385.  
  386. 	private static int[] generatePlan() {
  387. 		var ops = new ArrayList<Integer>();
  388. 		var rand = new Random(1);
  389. 		int len = 0, maxlen = 0;
  390. 		for (int i = 0; i < OPS_COUNT; i++) {
  391. 			if (len == 0 || len < LEN_LIMIT && len < rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1 + 6 * LEN_LIMIT)))) {
  392. 				int n = min(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(600)))), LEN_LIMIT - len);
  393. 				ops.add(rand.nextInt(2) == 0 ? OP_ADD_FRONT : OP_ADD_BACK);
  394. 				ops.add(n);
  395. 				ops.add(rand.nextInt(DUMMIES));
  396. 				len += n;
  397. 				maxlen = max(len, maxlen);
  398. 			} else {
  399. 				int n = min(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1200)))), len);
  400. 				ops.add(rand.nextInt(2) == 0 ? OP_POP_FRONT : OP_POP_BACK);
  401. 				ops.add(n);
  402. 				len -= n;
  403. 			}
  404. 		}
  405. 		System.out.printf("len after ops=%d, max len during ops=%d\n", len, maxlen);
  406. 		return ops.stream().mapToInt(i -> i).toArray();
  407. 	}
  408.  
  409. 	static void fusedBenchmarkTest() {
  410. 		Integer[] dummies = IntStream.range(0, DUMMIES).map(i -> i*i).boxed().toArray(Integer[]::new);
  411. 		var ops = generatePlan();
  412.  
  413. 		final int TRIALS = 3;
  414. 		for (int iTrial = 0; iTrial < TRIALS; iTrial++) {
  415. 			System.out.printf("%s--- TRIAL %d/%d ---\n", iTrial > 0 ? "\n" : "", 1 + iTrial, TRIALS);
  416.  
  417. 			var q_a2 = new AryDeque<Integer>(false);
  418. 			double refTime = benchmark("Deque over array (grow to cap*2, shrink /4 -> /2)",
  419. 				() -> {
  420. 					for (int iOp = 0; iOp < ops.length; )
  421. 						switch (ops[iOp]) {
  422. 							case OP_ADD_FRONT: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a2.addFront(dummy); iOp += 3; break; }
  423. 							case OP_ADD_BACK: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a2.addBack(dummy); iOp += 3; break; }
  424. 							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a2.popFront(); iOp += 2; break;
  425. 							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a2.popBack(); iOp += 2; break;
  426. 						}
  427. 					return q_a2;
  428. 				});
  429.  
  430. 			var q_a32 = new AryDeque<Integer>(true);
  431. 			benchmark("Deque over array (grow to cap*3/2, shrink /4 -> /2)",
  432. 				() -> {
  433. 					for (int iOp = 0; iOp < ops.length; )
  434. 						switch (ops[iOp]) {
  435. 							case OP_ADD_FRONT: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a32.addFront(dummy); iOp += 3; break; }
  436. 							case OP_ADD_BACK: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a32.addBack(dummy); iOp += 3; break; }
  437. 							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a32.popFront(); iOp += 2; break;
  438. 							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a32.popBack(); iOp += 2; break;
  439. 						}
  440. 					return q_a32;
  441. 				}, refTime);
  442.  
  443. 			var q_l = new LLDeque<Integer>();
  444. 			benchmark("Deque over linked list",
  445. 				() -> {
  446. 					for (int iOp = 0; iOp < ops.length; )
  447. 						switch (ops[iOp]) {
  448. 							case OP_ADD_FRONT: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_l.addFront(dummy); iOp += 3; break; }
  449. 							case OP_ADD_BACK: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_l.addBack(dummy); iOp += 3; break; }
  450. 							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_l.popFront(); iOp += 2; break;
  451. 							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_l.popBack(); iOp += 2; break;
  452. 						}
  453. 					return q_l;
  454. 				}, refTime);
  455.  
  456. 			var q_ul = new UCLLDeque<Integer>(UCLLDeque.LEGACY);
  457. 			benchmark("Deque over unrolled circular linked list",
  458. 				() -> {
  459. 					for (int iOp = 0; iOp < ops.length; )
  460. 						switch (ops[iOp]) {
  461. 							case OP_ADD_FRONT: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_ul.addFront(dummy); iOp += 3; break; }
  462. 							case OP_ADD_BACK: { Integer dummy = dummies[ops[iOp + 2]]; for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_ul.addBack(dummy); iOp += 3; break; }
  463. 							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_ul.popFront(); iOp += 2; break;
  464. 							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_ul.popBack(); iOp += 2; break;
  465. 						}
  466. 					return q_ul;
  467. 				}, refTime);
  468.  
  469. 			if (iTrial == 0) {
  470. 				var ref = q_a32.toList();
  471. 				System.out.printf("\nfinal deque len=%d\n", ref.size());
  472. 				var test = q_l.toList();
  473. 				checkEqual("Linked list-based deque", test, ref, test.size());
  474. 				test = q_ul.toList();
  475. 				checkEqual("Unrolled circular linked list-based deque", test, ref, test.size());
  476. 			}
  477. 		}
  478. 	}
  479.  
  480. 	static void checkEqual(String what, Object test, Object ref, Object extra) {
  481. 		if (test.equals(ref))
  482. 			System.out.printf("%s implementation yielded the same result so is probably correct.\n", what);
  483. 		else
  484. 			throw new RuntimeException(String.format("%s yielded a different result (%d), one or another is incorrect.", what, extra));
  485. 	}
  486.  
  487. 	@FunctionalInterface
  488. 	interface BenchmarkPayload {
  489. 		abstract Object run();
  490. 	}
  491.  
  492. 	static double benchmark(String title, BenchmarkPayload payload) {
  493. 		return benchmark(title, payload, -1);
  494. 	}
  495.  
  496. 	static double benchmark(String title, BenchmarkPayload payload, double refTime) {
  497. 		long start = System.nanoTime();
  498. 		Object keepAlive = payload.run();
  499. 		double time = (System.nanoTime() - start) * 1e-9;
  500. 		System.out.println(String.format(
  501. 			"%s: %.2f s%s",
  502. 			title, time, refTime >= 0 ? String.format(" (%s)", judgement(time, refTime)) : "", keepAlive));
  503. 		return time;
  504. 	}
  505.  
  506. 	static String judgement(double time, double refTime) {
  507. 		final double absThreshold = 0.3, relThreshold = .1;
  508.  
  509. 		return time <= absThreshold || refTime <= absThreshold ?
  510. 			String.format("can't judge, min. required time is %.1f s", absThreshold) :
  511. 			Math.max(time, refTime) > (1 + relThreshold) * Math.min(time, refTime) ?
  512. 			String.format("%.0f%% %s", Math.abs(time / refTime - 1) * 100, time < refTime ? "faster" : "slower") :
  513. 			String.format("no observable difference, min. %.0f%% required", relThreshold * 100);
  514. 	}
  515.  
  516. 	public static void main(String[] args) {
  517. 		try {
  518. 			// fusedBenchmarkTest();
  519.  
  520. 			// System.out.println();
  521. 			var q = new UCLLDequeTracer(new UCLLDeque<Integer>(UCLLDeque./*GOOD*/ LEGACY_INCORRECT), System.out);
  522. 			for (int i = 0; i < 8; i++) {
  523. 				q.addFront(i);
  524. 			}
  525. 			for (int i = 0; i < 8; i++) {
  526. 				q.popFront();
  527. 			}
  528. 			q.addBack(10);
  529. 			q.popFront();
  530. 			q.addFront(9);
  531.  
  532. 			/*var deque = new UCLLDequeTracer(new UCLLDeque<Integer>(UCLLDeque.LEGACY), System.out);
  533. 			for (int i = 3; i >= 0; i--) {
  534. 				deque.addFront(i);
  535. 			}
  536. 			for (int i = 4; i <= 7; i++) {
  537. 				deque.addBack(i);
  538. 			}
  539. 			for (int i = 0; i < 4; i++) {
  540. 				deque.popFront();
  541. 				deque.popBack();
  542. 			}
  543. 			deque.addBack(1);
  544. 			deque.addFront(0);*/
  545. 		} catch (Exception e) {
  546. 			StringWriter sw = new StringWriter();
  547. 			e.printStackTrace(new PrintWriter(sw));
  548. 			System.out.println(sw.toString());
  549. 		}
  550. 	}
  551. }
Success #stdin #stdout 0.09s 34252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
addFront(0): items=1
[null, null, null, 0]: iHead=3, iTail=4
[null, null, null, null]: dangling

addFront(1): items=2
[null, null, 1, 0]: iHead=2, iTail=4
[null, null, null, null]: dangling

addFront(2): items=3
[null, 2, 1, 0]: iHead=1, iTail=4
[null, null, null, null]: dangling

addFront(3): items=4
[3, 2, 1, 0]: iHead=0, iTail=4
[null, null, null, null]: dangling

addFront(4): items=5
[null, null, null, 4]: iHead=3
[3, 2, 1, 0]: iTail=4

addFront(5): items=6
[null, null, 5, 4]: iHead=2
[3, 2, 1, 0]: iTail=4

addFront(6): items=7
[null, 6, 5, 4]: iHead=1
[3, 2, 1, 0]: iTail=4

addFront(7): items=8
[7, 6, 5, 4]: iHead=0
[3, 2, 1, 0]: iTail=4

popFront() -> 7: items=7
[null, 6, 5, 4]: iHead=1
[3, 2, 1, 0]: iTail=4

popFront() -> 6: items=6
[null, null, 5, 4]: iHead=2
[3, 2, 1, 0]: iTail=4

popFront() -> 5: items=5
[null, null, null, 4]: iHead=3
[3, 2, 1, 0]: iTail=4

popFront() -> 4: items=4
[3, 2, 1, 0]: iHead=0, iTail=4
[null, null, null, null]: dangling

popFront() -> 3: items=3
[null, 2, 1, 0]: iHead=1, iTail=4
[null, null, null, null]: dangling

popFront() -> 2: items=2
[null, null, 1, 0]: iHead=2, iTail=4
[null, null, null, null]: dangling

popFront() -> 1: items=1
[null, null, null, 0]: iHead=3, iTail=4
[null, null, null, null]: dangling

popFront() -> 0: items=0
[null, null, null, null]: iHead=4, iTail=4
[null, null, null, null]: dangling

addBack(10): items=1
[null, null, null, null]: iHead=4
[10, null, null, null]: iTail=1

java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4
	at UCLLDeque.popFront(Main.java:250)
	at UCLLDequeTracer.popFront(Main.java:365)
	at Application.main(Main.java:529)
https://ideone.com/0r1ovb
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!