HDFS-13252. Code refactoring: Remove Diff.ListType.
[hadoop.git] / hadoop-hdfs-project / hadoop-hdfs / src / main / java / org / apache / hadoop / hdfs / util / Diff.java
1 /**
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 */
18 package org.apache.hadoop.hdfs.util;
19
20 import java.util.ArrayList;
21 import java.util.Collections;
22 import java.util.Iterator;
23 import java.util.List;
24
25 import com.google.common.base.Preconditions;
26
27 /**
28 * The difference between the current state and a previous state of a list.
29 *
30 * Given a previous state of a set and a sequence of create, delete and modify
31 * operations such that the current state of the set can be obtained by applying
32 * the operations on the previous state, the following algorithm construct the
33 * difference between the current state and the previous state of the set.
34 *
35 * <pre>
36 * Two lists are maintained in the algorithm:
37 * - c-list for newly created elements
38 * - d-list for the deleted elements
39 *
40 * Denote the state of an element by the following
41 * (0, 0): neither in c-list nor d-list
42 * (c, 0): in c-list but not in d-list
43 * (0, d): in d-list but not in c-list
44 * (c, d): in both c-list and d-list
45 *
46 * For each case below, ( , ) at the end shows the result state of the element.
47 *
48 * Case 1. Suppose the element i is NOT in the previous state. (0, 0)
49 * 1.1. create i in current: add it to c-list (c, 0)
50 * 1.1.1. create i in current and then create: impossible
51 * 1.1.2. create i in current and then delete: remove it from c-list (0, 0)
52 * 1.1.3. create i in current and then modify: replace it in c-list (c', 0)
53 *
54 * 1.2. delete i from current: impossible
55 *
56 * 1.3. modify i in current: impossible
57 *
58 * Case 2. Suppose the element i is ALREADY in the previous state. (0, 0)
59 * 2.1. create i in current: impossible
60 *
61 * 2.2. delete i from current: add it to d-list (0, d)
62 * 2.2.1. delete i from current and then create: add it to c-list (c, d)
63 * 2.2.2. delete i from current and then delete: impossible
64 * 2.2.2. delete i from current and then modify: impossible
65 *
66 * 2.3. modify i in current: put it in both c-list and d-list (c, d)
67 * 2.3.1. modify i in current and then create: impossible
68 * 2.3.2. modify i in current and then delete: remove it from c-list (0, d)
69 * 2.3.3. modify i in current and then modify: replace it in c-list (c', d)
70 * </pre>
71 *
72 * @param <K> The key type.
73 * @param <E> The element type, which must implement {@link Element} interface.
74 */
75 public class Diff<K, E extends Diff.Element<K>> {
76 /** An interface for the elements in a {@link Diff}. */
77 public static interface Element<K> extends Comparable<K> {
78 /** @return the key of this object. */
79 public K getKey();
80 }
81
82 /** An interface for passing a method in order to process elements. */
83 public static interface Processor<E> {
84 /** Process the given element. */
85 public void process(E element);
86 }
87
88 /** Containing exactly one element. */
89 public static class Container<E> {
90 private final E element;
91
92 private Container(E element) {
93 this.element = element;
94 }
95
96 /** @return the element. */
97 public E getElement() {
98 return element;
99 }
100 }
101
102 /**
103 * Undo information for some operations such as delete(E)
104 * and {@link Diff#modify(Element, Element)}.
105 */
106 public static class UndoInfo<E> {
107 private final int createdInsertionPoint;
108 private final E trashed;
109 private final Integer deletedInsertionPoint;
110
111 private UndoInfo(final int createdInsertionPoint, final E trashed,
112 final Integer deletedInsertionPoint) {
113 this.createdInsertionPoint = createdInsertionPoint;
114 this.trashed = trashed;
115 this.deletedInsertionPoint = deletedInsertionPoint;
116 }
117
118 public E getTrashedElement() {
119 return trashed;
120 }
121 }
122
123 private static final int DEFAULT_ARRAY_INITIAL_CAPACITY = 4;
124
125 /**
126 * Search the element from the list.
127 * @return -1 if the list is null; otherwise, return the insertion point
128 * defined in {@link Collections#binarySearch(List, Object)}.
129 * Note that, when the list is null, -1 is the correct insertion point.
130 */
131 protected static <K, E extends Comparable<K>> int search(
132 final List<E> elements, final K name) {
133 return elements == null? -1: Collections.binarySearch(elements, name);
134 }
135
136 private static <E> void remove(final List<E> elements, final int i,
137 final E expected) {
138 final E removed = elements.remove(-i - 1);
139 Preconditions.checkState(removed == expected,
140 "removed != expected=%s, removed=%s.", expected, removed);
141 }
142
143 /** c-list: element(s) created in current. */
144 private List<E> created;
145 /** d-list: element(s) deleted from current. */
146 private List<E> deleted;
147
148 protected Diff() {}
149
150 protected Diff(final List<E> created, final List<E> deleted) {
151 this.created = created;
152 this.deleted = deleted;
153 }
154
155 public List<E> getCreatedUnmodifiable() {
156 return created != null? Collections.unmodifiableList(created)
157 : Collections.emptyList();
158 }
159
160 public E setCreated(int index, E element) {
161 final E old = created.set(index, element);
162 if (old.compareTo(element.getKey()) != 0) {
163 throw new AssertionError("Element mismatched: element=" + element
164 + " but old=" + old);
165 }
166 return old;
167 }
168
169 public void clearCreated() {
170 if (created != null) {
171 created.clear();
172 }
173 }
174
175 public List<E> getDeletedUnmodifiable() {
176 return deleted != null? Collections.unmodifiableList(deleted)
177 : Collections.emptyList();
178 }
179
180 public boolean containsDeleted(final K key) {
181 if (deleted != null) {
182 return search(deleted, key) >= 0;
183 }
184 return false;
185 }
186
187 public boolean containsDeleted(final E element) {
188 return getDeleted(element.getKey()) == element;
189 }
190
191 /**
192 * @return null if the element is not found;
193 * otherwise, return the element in the deleted list.
194 */
195 public E getDeleted(final K key) {
196 if (deleted != null) {
197 final int c = search(deleted, key);
198 if (c >= 0) {
199 return deleted.get(c);
200 }
201 }
202 return null;
203 }
204
205 public boolean removeDeleted(final E element) {
206 if (deleted != null) {
207 final int i = search(deleted, element.getKey());
208 if (i >= 0 && deleted.get(i) == element) {
209 deleted.remove(i);
210 return true;
211 }
212 }
213 return false;
214 }
215
216 public void clearDeleted() {
217 if (deleted != null) {
218 deleted.clear();
219 }
220 }
221
222 /** @return true if no changes contained in the diff */
223 public boolean isEmpty() {
224 return (created == null || created.isEmpty())
225 && (deleted == null || deleted.isEmpty());
226 }
227
228 /**
229 * Add the given element to the created list,
230 * provided the element does not exist, i.e. i < 0.
231 *
232 * @param i the insertion point defined
233 * in {@link Collections#binarySearch(List, Object)}
234 * @throws AssertionError if i >= 0.
235 */
236 private void addCreated(final E element, final int i) {
237 if (i >= 0) {
238 throw new AssertionError("Element already exists: element=" + element
239 + ", created=" + created);
240 }
241 if (created == null) {
242 created = new ArrayList<>(DEFAULT_ARRAY_INITIAL_CAPACITY);
243 }
244 created.add(-i - 1, element);
245 }
246
247 /** Similar to {@link #addCreated(Element, int)} but for the deleted list. */
248 private void addDeleted(final E element, final int i) {
249 if (i >= 0) {
250 throw new AssertionError("Element already exists: element=" + element
251 + ", deleted=" + deleted);
252 }
253 if (deleted == null) {
254 deleted = new ArrayList<>(DEFAULT_ARRAY_INITIAL_CAPACITY);
255 }
256 deleted.add(-i - 1, element);
257 }
258
259
260 /**
261 * Create an element in current state.
262 * @return the c-list insertion point for undo.
263 */
264 public int create(final E element) {
265 final int c = search(created, element.getKey());
266 addCreated(element, c);
267 return c;
268 }
269
270 /**
271 * Undo the previous create(E) operation. Note that the behavior is
272 * undefined if the previous operation is not create(E).
273 */
274 public void undoCreate(final E element, final int insertionPoint) {
275 remove(created, insertionPoint, element);
276 }
277
278 /**
279 * Delete an element from current state.
280 * @return the undo information.
281 */
282 public UndoInfo<E> delete(final E element) {
283 final int c = search(created, element.getKey());
284 E previous = null;
285 Integer d = null;
286 if (c >= 0) {
287 // remove a newly created element
288 previous = created.remove(c);
289 } else {
290 // not in c-list, it must be in previous
291 d = search(deleted, element.getKey());
292 addDeleted(element, d);
293 }
294 return new UndoInfo<E>(c, previous, d);
295 }
296
297 /**
298 * Undo the previous delete(E) operation. Note that the behavior is
299 * undefined if the previous operation is not delete(E).
300 */
301 public void undoDelete(final E element, final UndoInfo<E> undoInfo) {
302 final int c = undoInfo.createdInsertionPoint;
303 if (c >= 0) {
304 created.add(c, undoInfo.trashed);
305 } else {
306 remove(deleted, undoInfo.deletedInsertionPoint, element);
307 }
308 }
309
310 /**
311 * Modify an element in current state.
312 * @return the undo information.
313 */
314 public UndoInfo<E> modify(final E oldElement, final E newElement) {
315 Preconditions.checkArgument(oldElement != newElement,
316 "They are the same object: oldElement == newElement = %s", newElement);
317 Preconditions.checkArgument(oldElement.compareTo(newElement.getKey()) == 0,
318 "The names do not match: oldElement=%s, newElement=%s",
319 oldElement, newElement);
320 final int c = search(created, newElement.getKey());
321 E previous = null;
322 Integer d = null;
323 if (c >= 0) {
324 // Case 1.1.3 and 2.3.3: element is already in c-list,
325 previous = created.set(c, newElement);
326
327 // For previous != oldElement, set it to oldElement
328 previous = oldElement;
329 } else {
330 d = search(deleted, oldElement.getKey());
331 if (d < 0) {
332 // Case 2.3: neither in c-list nor d-list
333 addCreated(newElement, c);
334 addDeleted(oldElement, d);
335 }
336 }
337 return new UndoInfo<E>(c, previous, d);
338 }
339
340 /**
341 * Undo the previous modify(E, E) operation. Note that the behavior
342 * is undefined if the previous operation is not modify(E, E).
343 */
344 public void undoModify(final E oldElement, final E newElement,
345 final UndoInfo<E> undoInfo) {
346 final int c = undoInfo.createdInsertionPoint;
347 if (c >= 0) {
348 created.set(c, undoInfo.trashed);
349 } else {
350 final int d = undoInfo.deletedInsertionPoint;
351 if (d < 0) {
352 remove(created, c, newElement);
353 remove(deleted, d, oldElement);
354 }
355 }
356 }
357
358 /**
359 * Find an element in the previous state.
360 *
361 * @return null if the element cannot be determined in the previous state
362 * since no change is recorded and it should be determined in the
363 * current state; otherwise, return a {@link Container} containing the
364 * element in the previous state. Note that the element can possibly
365 * be null which means that the element is not found in the previous
366 * state.
367 */
368 public Container<E> accessPrevious(final K name) {
369 return accessPrevious(name, created, deleted);
370 }
371
372 private static <K, E extends Diff.Element<K>> Container<E> accessPrevious(
373 final K name, final List<E> clist, final List<E> dlist) {
374 final int d = search(dlist, name);
375 if (d >= 0) {
376 // the element was in previous and was once deleted in current.
377 return new Container<E>(dlist.get(d));
378 } else {
379 final int c = search(clist, name);
380 // When c >= 0, the element in current is a newly created element.
381 return c < 0? null: new Container<E>(null);
382 }
383 }
384
385 /**
386 * Find an element in the current state.
387 *
388 * @return null if the element cannot be determined in the current state since
389 * no change is recorded and it should be determined in the previous
390 * state; otherwise, return a {@link Container} containing the element in
391 * the current state. Note that the element can possibly be null which
392 * means that the element is not found in the current state.
393 */
394 public Container<E> accessCurrent(K name) {
395 return accessPrevious(name, deleted, created);
396 }
397
398 /**
399 * Apply this diff to previous state in order to obtain current state.
400 * @return the current state of the list.
401 */
402 public List<E> apply2Previous(final List<E> previous) {
403 return apply2Previous(previous,
404 getCreatedUnmodifiable(), getDeletedUnmodifiable());
405 }
406
407 private static <K, E extends Diff.Element<K>> List<E> apply2Previous(
408 final List<E> previous, final List<E> clist, final List<E> dlist) {
409 // Assumptions:
410 // (A1) All lists are sorted.
411 // (A2) All elements in dlist must be in previous.
412 // (A3) All elements in clist must be not in tmp = previous - dlist.
413 final List<E> tmp = new ArrayList<E>(previous.size() - dlist.size());
414 {
415 // tmp = previous - dlist
416 final Iterator<E> i = previous.iterator();
417 for(E deleted : dlist) {
418 E e = i.next(); //since dlist is non-empty, e must exist by (A2).
419 int cmp = 0;
420 for(; (cmp = e.compareTo(deleted.getKey())) < 0; e = i.next()) {
421 tmp.add(e);
422 }
423 Preconditions.checkState(cmp == 0); // check (A2)
424 }
425 for(; i.hasNext(); ) {
426 tmp.add(i.next());
427 }
428 }
429
430 final List<E> current = new ArrayList<E>(tmp.size() + clist.size());
431 {
432 // current = tmp + clist
433 final Iterator<E> tmpIterator = tmp.iterator();
434 final Iterator<E> cIterator = clist.iterator();
435
436 E t = tmpIterator.hasNext()? tmpIterator.next(): null;
437 E c = cIterator.hasNext()? cIterator.next(): null;
438 for(; t != null || c != null; ) {
439 final int cmp = c == null? 1
440 : t == null? -1
441 : c.compareTo(t.getKey());
442
443 if (cmp < 0) {
444 current.add(c);
445 c = cIterator.hasNext()? cIterator.next(): null;
446 } else if (cmp > 0) {
447 current.add(t);
448 t = tmpIterator.hasNext()? tmpIterator.next(): null;
449 } else {
450 throw new AssertionError("Violated assumption (A3).");
451 }
452 }
453 }
454 return current;
455 }
456
457 /**
458 * Apply the reverse of this diff to current state in order
459 * to obtain the previous state.
460 * @return the previous state of the list.
461 */
462 public List<E> apply2Current(final List<E> current) {
463 return apply2Previous(current,
464 getDeletedUnmodifiable(), getCreatedUnmodifiable());
465 }
466
467 /**
468 * Combine this diff with a posterior diff. We have the following cases:
469 *
470 * <pre>
471 * 1. For (c, 0) in the posterior diff, check the element in this diff:
472 * 1.1 (c', 0) in this diff: impossible
473 * 1.2 (0, d') in this diff: put in c-list --> (c, d')
474 * 1.3 (c', d') in this diff: impossible
475 * 1.4 (0, 0) in this diff: put in c-list --> (c, 0)
476 * This is the same logic as create(E).
477 *
478 * 2. For (0, d) in the posterior diff,
479 * 2.1 (c', 0) in this diff: remove from c-list --> (0, 0)
480 * 2.2 (0, d') in this diff: impossible
481 * 2.3 (c', d') in this diff: remove from c-list --> (0, d')
482 * 2.4 (0, 0) in this diff: put in d-list --> (0, d)
483 * This is the same logic as delete(E).
484 *
485 * 3. For (c, d) in the posterior diff,
486 * 3.1 (c', 0) in this diff: replace the element in c-list --> (c, 0)
487 * 3.2 (0, d') in this diff: impossible
488 * 3.3 (c', d') in this diff: replace the element in c-list --> (c, d')
489 * 3.4 (0, 0) in this diff: put in c-list and d-list --> (c, d)
490 * This is the same logic as modify(E, E).
491 * </pre>
492 *
493 * @param posterior The posterior diff to combine with.
494 * @param deletedProcesser
495 * process the deleted/overwritten elements in case 2.1, 2.3, 3.1 and 3.3.
496 */
497 public void combinePosterior(final Diff<K, E> posterior,
498 final Processor<E> deletedProcesser) {
499 final Iterator<E> createdIterator
500 = posterior.getCreatedUnmodifiable().iterator();
501 final Iterator<E> deletedIterator
502 = posterior.getDeletedUnmodifiable().iterator();
503
504 E c = createdIterator.hasNext()? createdIterator.next(): null;
505 E d = deletedIterator.hasNext()? deletedIterator.next(): null;
506
507 for(; c != null || d != null; ) {
508 final int cmp = c == null? 1
509 : d == null? -1
510 : c.compareTo(d.getKey());
511 if (cmp < 0) {
512 // case 1: only in c-list
513 create(c);
514 c = createdIterator.hasNext()? createdIterator.next(): null;
515 } else if (cmp > 0) {
516 // case 2: only in d-list
517 final UndoInfo<E> ui = delete(d);
518 if (deletedProcesser != null) {
519 deletedProcesser.process(ui.trashed);
520 }
521 d = deletedIterator.hasNext()? deletedIterator.next(): null;
522 } else {
523 // case 3: in both c-list and d-list
524 final UndoInfo<E> ui = modify(d, c);
525 if (deletedProcesser != null) {
526 deletedProcesser.process(ui.trashed);
527 }
528 c = createdIterator.hasNext()? createdIterator.next(): null;
529 d = deletedIterator.hasNext()? deletedIterator.next(): null;
530 }
531 }
532 }
533
534 @Override
535 public String toString() {
536 return getClass().getSimpleName()
537 + "{created=" + getCreatedUnmodifiable()
538 + ", deleted=" + getDeletedUnmodifiable() + "}";
539 }
540 }