Package org.apache.hadoop.hdfs.util

Class Diff<K,E extends Diff.Element<K>>

java.lang.Object
org.apache.hadoop.hdfs.util.Diff<K,E>
Type Parameters:
K - The key type.
E - The element type, which must implement Diff.Element interface.
public class Diff<K,E extends Diff.Element<K>> extends Object
The difference between the current state and a previous state of a list. Given a previous state of a set and a sequence of create, delete and modify operations such that the current state of the set can be obtained by applying the operations on the previous state, the following algorithm construct the difference between the current state and the previous state of the set. 
 Two lists are maintained in the algorithm:
 - c-list for newly created elements
 - d-list for the deleted elements

 Denote the state of an element by the following
   (0, 0): neither in c-list nor d-list
   (c, 0): in c-list but not in d-list
   (0, d): in d-list but not in c-list
   (c, d): in both c-list and d-list

 For each case below, ( , ) at the end shows the result state of the element.

 Case 1. Suppose the element i is NOT in the previous state.           (0, 0)
   1.1. create i in current: add it to c-list                          (c, 0)
   1.1.1. create i in current and then create: impossible
   1.1.2. create i in current and then delete: remove it from c-list   (0, 0)
   1.1.3. create i in current and then modify: replace it in c-list    (c', 0)

   1.2. delete i from current: impossible

   1.3. modify i in current: impossible

 Case 2. Suppose the element i is ALREADY in the previous state.       (0, 0)
   2.1. create i in current: impossible

   2.2. delete i from current: add it to d-list                        (0, d)
   2.2.1. delete i from current and then create: add it to c-list      (c, d)
   2.2.2. delete i from current and then delete: impossible
   2.2.2. delete i from current and then modify: impossible

   2.3. modify i in current: put it in both c-list and d-list          (c, d)
   2.3.1. modify i in current and then create: impossible
   2.3.2. modify i in current and then delete: remove it from c-list   (0, d)
   2.3.3. modify i in current and then modify: replace it in c-list    (c', d)

  • Constructor Details

    • Diff

      protected Diff()

    • Diff

      protected Diff(List<E> created, List<E> deleted)

  • Method Details

    • search

      protected static <K, E extends Comparable<K>> int search(List<E> elements, K name)
      Search the element from the list.
      Returns:
      -1 if the list is null; otherwise, return the insertion point defined in Collections.binarySearch(List, Object). Note that, when the list is null, -1 is the correct insertion point.

    • getCreatedUnmodifiable

      public List<E> getCreatedUnmodifiable()

    • setCreated

      public E setCreated(int index, E element)

    • removeCreated

      public boolean removeCreated(E element)

    • clearCreated

      public void clearCreated()

    • getDeletedUnmodifiable

      public List<E> getDeletedUnmodifiable()

    • containsDeleted

      public boolean containsDeleted(K key)

    • containsDeleted

      public boolean containsDeleted(E element)

    • getDeleted

      public E getDeleted(K key)
      Returns:
      null if the element is not found; otherwise, return the element in the deleted list.

    • removeDeleted

      public boolean removeDeleted(E element)

    • clearDeleted

      public void clearDeleted()

    • isEmpty

      public boolean isEmpty()
      Returns:
      true if no changes contained in the diff

    • create

      public int create(E element)
      Create an element in current state.
      Returns:
      the c-list insertion point for undo.

    • undoCreate

      public void undoCreate(E element, int insertionPoint)
      Undo the previous create(E) operation. Note that the behavior is undefined if the previous operation is not create(E).

    • delete

      public Diff.UndoInfo<E> delete(E element)
      Delete an element from current state.
      Returns:
      the undo information.

    • undoDelete

      public void undoDelete(E element, Diff.UndoInfo<E> undoInfo)
      Undo the previous delete(E) operation. Note that the behavior is undefined if the previous operation is not delete(E).

    • modify

      public Diff.UndoInfo<E> modify(E oldElement, E newElement)
      Modify an element in current state.
      Returns:
      the undo information.

    • undoModify

      public void undoModify(E oldElement, E newElement, Diff.UndoInfo<E> undoInfo)
      Undo the previous modify(E, E) operation. Note that the behavior is undefined if the previous operation is not modify(E, E).

    • accessPrevious

      public Diff.Container<E> accessPrevious(K name)
      Find an element in the previous state.
      Returns:
      null if the element cannot be determined in the previous state since no change is recorded and it should be determined in the current state; otherwise, return a Diff.Container containing the element in the previous state. Note that the element can possibly be null which means that the element is not found in the previous state.

    • accessCurrent

      public Diff.Container<E> accessCurrent(K name)
      Find an element in the current state.
      Returns:
      null if the element cannot be determined in the current state since no change is recorded and it should be determined in the previous state; otherwise, return a Diff.Container containing the element in the current state. Note that the element can possibly be null which means that the element is not found in the current state.

    • apply2Previous

      public List<E> apply2Previous(List<E> previous)
      Apply this diff to previous state in order to obtain current state.
      Returns:
      the current state of the list.

    • apply2Current

      public List<E> apply2Current(List<E> current)
      Apply the reverse of this diff to current state in order to obtain the previous state.
      Returns:
      the previous state of the list.

    • combinePosterior

      public void combinePosterior(Diff<K,E> posterior, Diff.Processor<E> deletedProcesser)
      Combine this diff with a posterior diff. We have the following cases: 
       1. For (c, 0) in the posterior diff, check the element in this diff:
 1.1 (c', 0)  in this diff: impossible
 1.2 (0, d')  in this diff: put in c-list --> (c, d')
 1.3 (c', d') in this diff: impossible
 1.4 (0, 0)   in this diff: put in c-list --> (c, 0)
 This is the same logic as create(E).
 
 2. For (0, d) in the posterior diff,
 2.1 (c', 0)  in this diff: remove from c-list --> (0, 0)
 2.2 (0, d')  in this diff: impossible
 2.3 (c', d') in this diff: remove from c-list --> (0, d')
 2.4 (0, 0)   in this diff: put in d-list --> (0, d)
 This is the same logic as delete(E).
 
 3. For (c, d) in the posterior diff,
 3.1 (c', 0)  in this diff: replace the element in c-list --> (c, 0)
 3.2 (0, d')  in this diff: impossible
 3.3 (c', d') in this diff: replace the element in c-list --> (c, d')
 3.4 (0, 0)   in this diff: put in c-list and d-list --> (c, d)
 This is the same logic as modify(E, E).
      Parameters:
      posterior - The posterior diff to combine with.
      deletedProcesser - process the deleted/overwritten elements in case 2.1, 2.3, 3.1 and 3.3.

    • toString

      public String toString()
      Overrides:
      toString in class Object