fork(1) 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. 	Node<T> headNode, tailNode;
  189. 	int iHead, iTail;
  190.  
  191. 	public UCLLDeque() {
  192. 		headNode = new Node<T>(4);
  193. 		tailNode = headNode;
  194. 		headNode.prev = tailNode;
  195. 		headNode.next = tailNode;
  196. 	}
  197.  
  198. 	public void addFront(T value) {
  199. 		if (iHead == 0) {
  200. 			headNode = headNode.prev != tailNode ? headNode.prev : insertNode(createNode(), true, headNode);
  201. 			iHead = headNode.values.length;
  202. 		}
  203. 		headNode.values[--iHead] = value;
  204. 	}
  205.  
  206. 	public void addBack(T value) {
  207. 		tailNode.values[iTail++] = value;
  208. 		if (iTail == tailNode.values.length) {
  209. 			tailNode = tailNode.next != headNode ? tailNode.next : insertNode(createNode(), false, tailNode);
  210. 			iTail = 0;
  211. 		}
  212. 	}
  213.  
  214. 	public T popFront() {
  215. 		if (headNode == tailNode && iHead == iTail) {
  216. 			throw Common.dequeEmpty();
  217. 		}
  218. 		T value = (T) headNode.values[iHead];
  219. 		headNode.values[iHead++] = null;
  220. 		if (iHead == headNode.values.length) {
  221. 			if (headNode.prev != tailNode && headNode.prev.prev != tailNode) {
  222. 				removeNode(headNode.prev.prev);
  223. 			}
  224. 			headNode = headNode.next;
  225. 			iHead = 0;
  226. 		}
  227. 		return value;
  228. 	}
  229.  
  230. 	public T popBack() {
  231. 		if (tailNode == headNode && iTail == iHead) {
  232. 			throw Common.dequeEmpty();
  233. 		}
  234. 		if (iTail == 0) {
  235. 			if (tailNode.next != headNode && tailNode.next.next != headNode) {
  236. 				removeNode(tailNode.next.next);
  237. 			}
  238. 			tailNode = tailNode.prev;
  239. 			iTail = tailNode.values.length;
  240. 		}
  241. 		T value = (T) tailNode.values[--iTail];
  242. 		tailNode.values[iTail] = null;
  243. 		return value;
  244. 	}
  245.  
  246. 	private int calcItemsCount() {
  247. 		int count = 0;
  248. 		for (Node<T> n = headNode, prevN = null; prevN != tailNode; prevN = n, n = n.next) {
  249. 			count += (n == tailNode ? iTail : n.values.length) - (n == headNode ? iHead : 0);
  250. 		}
  251. 		return count;
  252. 	}
  253.  
  254. 	private Node<T> createNode() {
  255. 		return new Node<T>(max(4, calcItemsCount() / 2));
  256. 	}
  257.  
  258. 	private Node<T> insertNode(Node node, boolean before, Node adjacent) {
  259. 		Node<T> prev = before ? adjacent.prev : adjacent;
  260. 		Node<T> next = before ? adjacent : adjacent.next;
  261. 		node.prev = prev;
  262. 		node.next = next;
  263. 		prev.next = node;
  264. 		next.prev = node;
  265. 		return node;
  266. 	}
  267.  
  268. 	private static <T> void removeNode(Node<T> node) {
  269. 		Node<T> n_prev = node.prev, n_next = node.next;
  270. 		n_prev.next = n_next;
  271. 		n_next.prev = n_prev;
  272. 	}
  273.  
  274. 	public String dump() {
  275. 		StringBuilder r = new StringBuilder(), desc = new StringBuilder();
  276. 		r.append("items=").append(calcItemsCount());
  277. 		boolean tailSeen = false;
  278. 		for (Node<T> n = headNode, stopN = null; n != stopN; stopN = headNode, n = n.next) {
  279. 			r.append("\n").append(Arrays.toString(n.values));
  280. 			desc.setLength(0);
  281. 			if (n == headNode) desc.append(desc.length() > 0 ? ", " : ": ").append("iHead=").append(iHead);
  282. 			if (n == tailNode) desc.append(desc.length() > 0 ? ", " : ": ").append("iTail=").append(iTail);
  283. 			if (tailSeen) desc.append(desc.length() > 0 ? ", " : ": ").append("dangling");
  284. 			r.append(desc);
  285. 			tailSeen |= n == tailNode;
  286. 		}
  287. 		return r.toString();
  288. 	}
  289.  
  290. 	public List<T> toList() {
  291. 		List<T> result = new ArrayList<T>();
  292. 		for (Node<T> n = headNode, prevN = null; prevN != tailNode; prevN = n, n = n.next) {
  293. 			result.addAll(((List<T>) Arrays.asList(n.values)).subList(
  294. 				n == headNode ? iHead : 0, n == tailNode ? iTail : n.values.length));
  295. 		}
  296. 		return result;
  297. 	}
  298. }
  299.  
  300. class UCLLDequeTracer<T> {
  301. 	private UCLLDeque<T> deque;
  302. 	private PrintStream out;
  303.  
  304. 	public UCLLDequeTracer(UCLLDeque<T> deque, PrintStream out) {
  305. 		this.deque = deque;
  306. 		this.out = out;
  307. 	}
  308.  
  309. 	public void addFront(T value) {
  310. 		deque.addFront(value);
  311. 		out.printf("addFront(%s): %s\n\n", value, deque.dump());
  312. 	}
  313.  
  314. 	public void addBack(T value) {
  315. 		deque.addBack(value);
  316. 		out.printf("addBack(%s): %s\n\n", value, deque.dump());
  317. 	}
  318.  
  319. 	public T popFront() {
  320. 		T value = deque.popFront();
  321. 		out.printf("popFront() -> %s: %s\n\n", value, deque.dump());
  322. 		return value;
  323. 	}
  324.  
  325. 	public T popBack() {
  326. 		T value = deque.popBack();
  327. 		out.printf("popBack() -> %s: %s\n\n", value, deque.dump());
  328. 		return value;
  329. 	}
  330. }
  331.  
  332. class Application {
  333. 	static final int OP_ADD_FRONT = 0;
  334. 	static final int OP_ADD_BACK = 1;
  335. 	static final int OP_POP_FRONT = 2;
  336. 	static final int OP_POP_BACK = 3;
  337. 	static final int DUMMIES = 10;
  338. 	static final int LEN_LIMIT = 100000;
  339. 	static final int OPS_COUNT = 4000000;
  340.  
  341. 	private static int[] generatePlan() {
  342. 		var ops = new ArrayList<Integer>();
  343. 		var rand = new Random(1);
  344. 		int len = 0, maxlen = 0;
  345. 		for (int i = 0; i < OPS_COUNT; i++) {
  346. 			if (len == 0 || len < LEN_LIMIT && len < rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1 + 6 * LEN_LIMIT)))) {
  347. 				int n = min(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(600)))), LEN_LIMIT - len);
  348. 				ops.add(rand.nextInt(2) == 0 ? OP_ADD_FRONT : OP_ADD_BACK);
  349. 				ops.add(n);
  350. 				ops.add(rand.nextInt(DUMMIES));
  351. 				len += n;
  352. 				maxlen = max(len, maxlen);
  353. 			} else {
  354. 				int n = min(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1 + rand.nextInt(1200)))), len);
  355. 				ops.add(rand.nextInt(2) == 0 ? OP_POP_FRONT : OP_POP_BACK);
  356. 				ops.add(n);
  357. 				len -= n;
  358. 			}
  359. 		}
  360. 		System.out.printf("len after ops=%d, max len during ops=%d\n", len, maxlen);
  361. 		return ops.stream().mapToInt(i -> i).toArray();
  362. 	}
  363.  
  364. 	static void fusedBenchmarkTest() {
  365. 		Integer[] dummies = IntStream.range(0, DUMMIES).map(i -> i*i).boxed().toArray(Integer[]::new);
  366. 		var ops = generatePlan();
  367.  
  368. 		final int TRIALS = 3;
  369. 		for (int iTrial = 0; iTrial < TRIALS; iTrial++) {
  370. 			System.out.printf("%s--- TRIAL %d/%d ---\n", iTrial > 0 ? "\n" : "", 1 + iTrial, TRIALS);
  371.  
  372. 			var q_a2 = new AryDeque<Integer>(false);
  373. 			double refTime = benchmark("Deque over array (grow to cap*2, shrink /4 -> /2)",
  374. 				() -> {
  375. 					for (int iOp = 0; iOp < ops.length; )
  376. 						switch (ops[iOp]) {
  377. 							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; }
  378. 							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; }
  379. 							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a2.popFront(); iOp += 2; break;
  380. 							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a2.popBack(); iOp += 2; break;
  381. 						}
  382. 					return q_a2;
  383. 				});
  384.  
  385. 			var q_a32 = new AryDeque<Integer>(true);
  386. 			benchmark("Deque over array (grow to cap*3/2, shrink /4 -> /2)",
  387. 				() -> {
  388. 					for (int iOp = 0; iOp < ops.length; )
  389. 						switch (ops[iOp]) {
  390. 							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; }
  391. 							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; }
  392. 							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a32.popFront(); iOp += 2; break;
  393. 							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_a32.popBack(); iOp += 2; break;
  394. 						}
  395. 					return q_a32;
  396. 				}, refTime);
  397.  
  398. 			var q_l = new LLDeque<Integer>();
  399. 			benchmark("Deque over linked list",
  400. 				() -> {
  401. 					for (int iOp = 0; iOp < ops.length; )
  402. 						switch (ops[iOp]) {
  403. 							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; }
  404. 							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; }
  405. 							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_l.popFront(); iOp += 2; break;
  406. 							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_l.popBack(); iOp += 2; break;
  407. 						}
  408. 					return q_l;
  409. 				}, refTime);
  410.  
  411. 			var q_ul = new UCLLDeque<Integer>();
  412. 			benchmark("Deque over unrolled circular linked list",
  413. 				() -> {
  414. 					for (int iOp = 0; iOp < ops.length; )
  415. 						switch (ops[iOp]) {
  416. 							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; }
  417. 							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; }
  418. 							case OP_POP_FRONT: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_ul.popFront(); iOp += 2; break;
  419. 							default: for (int i = 0, n = ops[iOp + 1]; i < n; i++) q_ul.popBack(); iOp += 2; break;
  420. 						}
  421. 					return q_ul;
  422. 				}, refTime);
  423.  
  424. 			if (iTrial == 0) {
  425. 				var ref = q_a32.toList();
  426. 				System.out.printf("\nfinal deque len=%d\n", ref.size());
  427. 				var test = q_l.toList();
  428. 				checkEqual("Linked list-based deque", test, ref, test.size());
  429. 				test = q_ul.toList();
  430. 				checkEqual("Unrolled circular linked list-based deque", test, ref, test.size());
  431. 			}
  432. 		}
  433. 	}
  434.  
  435. 	static void checkEqual(String what, Object test, Object ref, Object extra) {
  436. 		if (test.equals(ref))
  437. 			System.out.printf("%s implementation yielded the same result so is probably correct.\n", what);
  438. 		else
  439. 			throw new RuntimeException(String.format("%s yielded a different result (%d), one or another is incorrect.", what, extra));
  440. 	}
  441.  
  442. 	@FunctionalInterface
  443. 	interface BenchmarkPayload {
  444. 		abstract Object run();
  445. 	}
  446.  
  447. 	static double benchmark(String title, BenchmarkPayload payload) {
  448. 		return benchmark(title, payload, -1);
  449. 	}
  450.  
  451. 	static double benchmark(String title, BenchmarkPayload payload, double refTime) {
  452. 		long start = System.nanoTime();
  453. 		Object keepAlive = payload.run();
  454. 		double time = (System.nanoTime() - start) * 1e-9;
  455. 		System.out.println(String.format(
  456. 			"%s: %.2f s%s",
  457. 			title, time, refTime >= 0 ? String.format(" (%s)", judgement(time, refTime)) : "", keepAlive));
  458. 		return time;
  459. 	}
  460.  
  461. 	static String judgement(double time, double refTime) {
  462. 		final double absThreshold = 0.3, relThreshold = .1;
  463.  
  464. 		return time <= absThreshold || refTime <= absThreshold ?
  465. 			String.format("can't judge, min. required time is %.1f s", absThreshold) :
  466. 			Math.max(time, refTime) > (1 + relThreshold) * Math.min(time, refTime) ?
  467. 			String.format("%.0f%% %s", Math.abs(time / refTime - 1) * 100, time < refTime ? "faster" : "slower") :
  468. 			String.format("no observable difference, min. %.0f%% required", relThreshold * 100);
  469. 	}
  470.  
  471. 	public static void main(String[] args) {
  472. 		try {
  473. 			fusedBenchmarkTest();
  474.  
  475. 			System.out.println();
  476. 			/*var q = new UCLLDequeTracer(new UCLLDeque<Integer>(), System.out);
  477. 			for (int i = 0; i < 8; i++) {
  478. 				q.addFront(i);
  479. 			}
  480. 			for (int i = 0; i < 8; i++) {
  481. 				q.popFront();
  482. 			}
  483. 			q.addBack(10);
  484. 			q.popFront();
  485. 			q.addFront(9);*/
  486.  
  487. 			var deque = new UCLLDequeTracer(new UCLLDeque<Integer>(), System.out);
  488. 			for (int i = 3; i >= 0; i--) {
  489. 				deque.addFront(i);
  490. 			}
  491. 			for (int i = 4; i <= 7; i++) {
  492. 				deque.addBack(i);
  493. 			}
  494. 			for (int i = 0; i < 4; i++) {
  495. 				deque.popFront();
  496. 				deque.popBack();
  497. 			}
  498. 			deque.addBack(1);
  499. 			deque.addFront(0);
  500. 		} catch (Exception e) {
  501. 			StringWriter sw = new StringWriter();
  502. 			e.printStackTrace(new PrintWriter(sw));
  503. 			System.out.println(sw.toString());
  504. 		}
  505. 	}
  506. }
Success #stdin #stdout 9.72s 277356KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
len after ops=15979, max len during ops=28035
--- TRIAL 1/3 ---
Deque over array (grow to cap*2, shrink /4 -> /2): 0.64 s
Deque over array (grow to cap*3/2, shrink /4 -> /2): 0.67 s (no observable difference, min. 10% required)
Deque over linked list: 0.97 s (52% slower)
Deque over unrolled circular linked list: 0.65 s (no observable difference, min. 10% required)

final deque len=15979
Linked list-based deque implementation yielded the same result so is probably correct.
Unrolled circular linked list-based deque implementation yielded the same result so is probably correct.

--- TRIAL 2/3 ---
Deque over array (grow to cap*2, shrink /4 -> /2): 0.72 s
Deque over array (grow to cap*3/2, shrink /4 -> /2): 0.72 s (no observable difference, min. 10% required)
Deque over linked list: 0.79 s (10% slower)
Deque over unrolled circular linked list: 0.76 s (no observable difference, min. 10% required)

--- TRIAL 3/3 ---
Deque over array (grow to cap*2, shrink /4 -> /2): 0.67 s
Deque over array (grow to cap*3/2, shrink /4 -> /2): 0.67 s (no observable difference, min. 10% required)
Deque over linked list: 0.82 s (22% slower)
Deque over unrolled circular linked list: 0.65 s (no observable difference, min. 10% required)

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

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

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

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

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

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

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

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

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

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

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

popBack() -> 6: items=4
[null, null, 2, 3]: iHead=2
[4, 5, null, null]: iTail=2
[null, null, null, null]: dangling

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

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

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

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

addBack(1): items=1
[1, null, null, null]: iHead=0, iTail=1
[null, null, null, null]: dangling
[null, null, null, null]: dangling

addFront(0): items=2
[null, null, null, 0]: iHead=3
[1, null, null, null]: iTail=1
[null, null, null, null]: dangling
https://ideone.com/BVj9Bb
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!