fork download
copy 
  1. import java.lang.AutoCloseable;
  2. import java.util.Collection;
  3. import java.util.AbstractQueue;
  4. import java.util.Iterator;
  5. import java.util.TreeSet;
  6. import java.util.HashSet;
  7.  
  8. import java.util.NoSuchElementException;
  9. import java.util.ConcurrentModificationException;
  10.  
  11. import static java.lang.Math.max;
  12.  
  13. /**
  14.  * A maximum priority queue based on an unordered array.
  15.  * Supports fast constant-time insertions of the elements, but
  16.  * the retrieve-max-value methods work only in linear time.
  17.  */
  18. class MaxPQUnorderedArray<T extends Comparable<? super T>>
  19. 		extends AbstractQueue<T> {
  20.  
  21. 	private T[] data;
  22.  
  23. 	// Соответствует логическому количеству элементов, когда nOpenedIterators == 0,
  24. 	// иначе включает удалённые.
  25. 	private int nAll = 0;
  26.  
  27. 	// Множество индексов удалённых элементов. Создаётся по запросу.
  28. 	//
  29. 	// Удаление i-го индекса инвалидирует хотя бы один из индексов >= i,
  30. 	// поэтому finishPostponedRemoves должна иметь возможность обойти
  31. 	// удаляемые индексы от старшего к младшему. Так что HashSet не подходит.
  32. 	//
  33. 	// Вместо TreeSet можно использовать битовое поле из nAll бит,
  34. 	// в котором '1' соответствуют удалённым элементам.
  35. 	// Такое битовое поле будет эффективнее, когда количество удалённых элементов
  36. 	// сравнимо с количеством вообще всех элементов в очереди.
  37. 	//
  38. 	// Есть смысл сделать ОБА варианта и переключаться с TreeSet на битовое поле
  39. 	// в момент достижения чего-то типа removed >= max(24, 4% элементов).
  40. 	private TreeSet<Integer> postponedRemoves;
  41.  
  42. 	// Удаления откладываются при nOpenedIterators > 0.
  43. 	private int nOpenedIterators = 0;
  44.  
  45. 	public MaxPQUnorderedArray() { }
  46.  
  47. 	/**
  48. 	 * Creates a MaxPQ containing the elements from the
  49. 	 * specified collection.
  50. 	 */
  51. 	@SuppressWarnings("unchecked")
  52. 	public MaxPQUnorderedArray(Collection<T> elements) {
  53. 		addAll(elements);
  54. 	}
  55.  
  56. 	/**
  57. 	 * Create an empty queue with the specified initial capacity.
  58. 	 */
  59. 	@SuppressWarnings("unchecked")
  60. 	public MaxPQUnorderedArray(int initialCapacity) {
  61. 		if (initialCapacity < 0) {
  62. 			throw new IllegalStateException(String.format(
  63. 				"Expected: initialCapacity >= 0."
  64. 				+ " Got: initialCapacity = %d", initialCapacity
  65. 			));
  66. 		}
  67. 		reallocate(initialCapacity);
  68. 	}
  69.  
  70. 	/**
  71. 	 * Adds an element to the queue.
  72. 	 * @return true in case the queue is modified as a result of the call.
  73. 	 */
  74. 	@Override
  75. 	public boolean offer(T value) {
  76. 		grow(1);
  77. 		data[nAll++] = value;
  78. 		return true;
  79. 	}
  80.  
  81. 	/**
  82. 	 * Adds all of the elements from the specified collection.
  83. 	 * @return  true in case every element from the collection has been
  84. 	 *		  added to the queue.
  85. 	 */
  86. 	@Override
  87. 	public boolean addAll(Collection<? extends T> elements) {
  88. 		int i = nAll;
  89. 		grow(elements.size());
  90. 		for (T element : elements) {
  91. 			data[i++] = element;
  92. 		}
  93. 		nAll = i;
  94. 		return true;
  95. 	}
  96.  
  97. 	/**
  98. 	 * Retrieves, but does not remove, the max value stored in the queue
  99. 	 * or returns {@code null} in case the queue is empty.
  100. 	 * This method can be slightly improved by keeping the position
  101. 	 * of the max element, so that subsequential calls of {@code element}
  102. 	 * or {@code remove} would take constant time instead of linear.
  103. 	 */
  104. 	@Override
  105. 	public T peek() {
  106. 		int iMax = findMax();
  107. 		return iMax >= 0 ? data[iMax] : null;
  108. 	}
  109.  
  110. 	/**
  111. 	 * Retrieves and removes the maximum element of the queue or
  112. 	 * just retunrls {@code null} in case the queue is empty.
  113. 	 */
  114. 	@Override
  115. 	public T poll() {
  116. 		int iMax = findMax();
  117. 		if (iMax < 0) return null;
  118. 		T max = data[iMax];
  119. 		removeAt(iMax);
  120. 		return max;
  121. 	}
  122.  
  123. 	/**
  124. 	 * Removes all elements from the queue.
  125. 	 */
  126. 	@Override
  127. 	@SuppressWarnings("unchecked")
  128. 	public void clear() {
  129. 		if (nOpenedIterators == 0) {
  130. 			nAll = 0;
  131. 			shrink();
  132. 		} else {
  133. 			// Мне лень думать.
  134. 			for (int i = 0; i < nAll; i++)
  135. 				if (!flyblown(i)) postponeRemoveAt(i);
  136. 		}
  137. 	}
  138.  
  139. 	@Override
  140. 	public boolean isEmpty() {
  141. 		return nAll == flyblownCount();
  142. 	}
  143.  
  144. 	@Override
  145. 	public int size() {
  146. 		return nAll - flyblownCount();
  147. 	}
  148.  
  149. 	@Override
  150. 	public PQIterator iterator() {
  151. 		var result = new PQIterator(); // can throw, at least OOM!
  152. 		nOpenedIterators++; // so increment only now
  153. 		return result;
  154. 	}
  155.  
  156. 	int findMax() {
  157. 		int iMax = -1;
  158. 		for (int i = 0; i < nAll; i++)
  159. 			if (!flyblown(i) && (iMax < 0 || data[iMax].compareTo(data[i]) < 0))
  160. 				iMax = i;
  161. 		return iMax;
  162. 	}
  163.  
  164. 	void removeAt(int index) {
  165. 		if (nOpenedIterators == 0)
  166. 			removeRightAwayAt(index);
  167. 		else
  168. 			postponeRemoveAt(index);
  169. 	}
  170.  
  171. 	void removeRightAwayAt(int index) {
  172. 		data[index] = data[nAll - 1];
  173. 		nAll--;
  174. 		shrink();
  175. 	}
  176.  
  177. 	void postponeRemoveAt(int index) {
  178. 		assert postponedRemoves == null || !postponedRemoves.contains(index);
  179. 		if (postponedRemoves == null) postponedRemoves = new TreeSet<Integer>();
  180. 		postponedRemoves.add(index);
  181. 	}
  182.  
  183. 	void finishPostponedRemoves() {
  184. 		if (postponedRemoves == null) return;
  185. 		while (!postponedRemoves.isEmpty())
  186. 			removeRightAwayAt(postponedRemoves.pollLast());
  187. 	}
  188.  
  189. 	// flyblown == true означает, что элемент удалён и не должен быть виден снаружи.
  190. 	// Я хотел сделать нескучное название, но так и не вспомнил, как будет «зашкварен».
  191. 	//
  192. 	// Проверки nOpenedIterators экономят вызовы .contains и .size у заведомо
  193. 	// пустого множества, но портят отладочный вывод в PQIterator.close.
  194. 	boolean flyblown(int index) {
  195. 		return /* nOpenedIterators > 0 && */ postponedRemoves != null && postponedRemoves.contains(index);
  196. 	}
  197.  
  198. 	int flyblownCount() {
  199. 		return /*nOpenedIterators == 0 || */ postponedRemoves == null ? 0 : postponedRemoves.size();
  200. 	}
  201.  
  202. 	static final int MIN_GROW = 4;
  203. 	/**
  204. 	 * Reallocates the memory used to store the elements of the queue
  205. 	 * in a way to fit next `by` added elements. Grows the length of the
  206. 	 * array at least 1.5 times. We call this method beforehand the
  207. 	 * actual insertions of the elements, because it allows us to
  208. 	 * have fully filled array.
  209. 	 */
  210. 	private void grow(int by) {
  211. 		if (data == null ? by > 0 : nAll + by > data.length) {
  212. 			reallocate(nAll + max(by, max(MIN_GROW, data == null ? 0 : data.length / 2)));
  213. 		}
  214. 	}
  215.  
  216. 	/**
  217. 	 * Considers reducing the physical storage size, i. e. 'data'.
  218. 	 * Meant to be called after reducing element count.
  219. 	 */
  220. 	private void shrink() {
  221. 		if (data != null && nAll <= data.length / 4) {
  222. 			// make the array that would be 50% full
  223. 			int newLen = max(MIN_GROW, 2 * nAll);
  224.  
  225. 			// shrink only if this will remove strictly MORE than MIN_GROW cells,
  226. 			// so adding and removing a single item into an empty queue won't cause
  227. 			// repetitive reallocations.
  228. 			if (data.length - newLen > MIN_GROW) {
  229. 				reallocate(newLen);
  230. 			}
  231. 		}
  232. 	}
  233.  
  234. 	/**
  235. 	 * Changes the size of the array in which the elements are stored.
  236. 	 */
  237. 	@SuppressWarnings("unchecked")
  238. 	private void reallocate(int newSize) {
  239. 		assert newSize >= nAll;
  240.  
  241. 		Comparable<?>[] newData = new Comparable<?>[newSize];
  242. 		if (data != null) System.arraycopy(data, 0, newData, 0, nAll);
  243. 		data = (T[]) newData;
  244. 	}
  245.  
  246. 	// Итератор весьма медленный.
  247. 	//
  248. 	// Можно сделать так: если итератор прошёл уже >=10 элементов —
  249. 	// на этот раз не max(10, 4% элементов), а именно 10 или подобная очень маленькая константа —
  250. 	// то составить max-кучу из всех оставшихся живых элементов (и их индексов)
  251. 	// и в следующих next выдавать элементы из неё.
  252. 	//
  253. 	// Но это лечение гангрены подорожником. Нормальная реализация — см. в треде.
  254. 	private class PQIterator implements Iterator<T>, Iterable<T>, AutoCloseable {
  255. 		private HashSet<Integer> seen = new HashSet<Integer>();
  256. 		int nAll = MaxPQUnorderedArray.this.nAll;
  257. 		int last = -1;
  258. 		int cachedNext = -1; // speed up hasNext() + next() sequence.
  259.  
  260. 		public PQIterator() { }
  261.  
  262. 		public boolean hasNext() {
  263. 			return findNext(true) >= 0;
  264. 		}
  265.  
  266. 		public T next() {
  267. 			int iNext = findNext(false);
  268. 			if (iNext < 0) throw new NoSuchElementException("The queue is empty");
  269. 			last = iNext;
  270. 			seen.add(iNext);
  271. 			return data[iNext];
  272. 		}
  273.  
  274. 		public void remove() {
  275. 			if (last < 0) throw new IllegalStateException("Iterator doesn't point to an item.");
  276. 			postponeRemoveAt(last);
  277. 			last = -1;
  278. 		}
  279.  
  280. 		private int findNext(boolean isHasNextCheck) {
  281. 			int iMax = cachedNext;
  282. 			if (iMax < 0) {
  283. 				for (int i = 0; i < nAll; i++)
  284. 					if (!seen.contains(i) && !flyblown(i) && (iMax < 0 || data[iMax].compareTo(data[i]) < 0))
  285. 						iMax = i;
  286. 			}
  287. 			cachedNext = isHasNextCheck ? iMax : -1; // сохранить в hasNext(), сбросить в next().
  288. 			return iMax;
  289. 		}
  290.  
  291. 		@Override
  292. 		public void close() {
  293. 			if (seen == null) return; // я не знаю, предосторожность от двойного close().
  294. 			seen = null;
  295. 			if (--nOpenedIterators == 0) {
  296. 				System.out.printf("\nlast iterator closed, flyblownCount = %d\n", flyblownCount());
  297. 				finishPostponedRemoves();
  298. 			}
  299. 		}
  300.  
  301. 		@Override
  302. 		public PQIterator iterator() { return this; }
  303. 	}
  304.  
  305. 	public static void main(String[] args) {
  306. 		MaxPQUnorderedArray<Integer> pq = new MaxPQUnorderedArray<>();
  307. 		for (int i = 0; i < 10; i++) {
  308. 			pq.add(i);
  309. 		}
  310. 		try (var iterator = pq.iterator()) {
  311. 			while (iterator.hasNext()) {
  312. 				int next = iterator.next();
  313. 				System.out.printf("%d ", next);
  314. 				if (next == 5 || next == 2 || next == 3) {
  315. 					iterator.remove();
  316. 				}
  317. 			}
  318. 		}
  319.  
  320. 		System.out.println();
  321. 		try (var iterator = pq.iterator()) {
  322. 			for (int i : iterator) {
  323. 				System.out.printf("%d ", i);
  324. 			}
  325. 		}
  326. 	}
  327. }
Success #stdin #stdout 0.08s 34592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9 8 7 6 5 4 3 2 1 0 
last iterator closed, flyblownCount = 3

9 8 7 6 4 1 0 
last iterator closed, flyblownCount = 0
https://ideone.com/5m2iJu
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!