Check if two integer iterators have the maximum distance of one

Given the interface IntIterator defined in the following, implement the method isDistanceZeroOrOne(IntIterator a, IntIterator b) to return if the distance between a and b is at most one, where the distance is defined as the minimum number of modifications to make them equal to each other. Modifications can be: 1) change an int in a. 2) insert an int to a. 3) remove an int from a. For example, the method should return true for 1, 2, 2 and 1, 3, 2, 2.

```
public class IteratorDistanceTest {
```
```
 
```
```
  interface IntIterator {
```
```
    boolean hasNext();
```
```
    int next();
```
```
  }
```
```
 
```

  static boolean isDistanceZeroOrOne(IntIterator a, IntIterator b) {

```
    boolean trying = false;
```
```
    boolean changable = false;
```
```
    boolean insertable = false;
```
```
    boolean removable = false;
```

    for(int aPrevious = 0, bPrevious = 0, aCurrent = 0, bCurrent = 0;

        ; aPrevious = aCurrent, bPrevious = bCurrent) {

```
      if(a.hasNext()) {
```
```
        aCurrent = a.next();
```

        if(b.hasNext()) { // a != null, b != null.

```
          bCurrent = b.next();
```
```
          if(trying) {
```
```
            if(changable) {
```

              if(aCurrent != bCurrent) {

```
                changable = false;
```
```
              }
```
```
            }
```
```
            if(insertable) {
```

              if(bCurrent != aPrevious) {

```
                insertable = false;
```
```
              }
```
```
            }
```
```
            if(removable) {
```

              if(aCurrent != bPrevious) {

```
                removable = false;
```
```
              }
```
```
            }
```

            if(!changable && !insertable && !removable) {

```
              return false;
```
```
            }
```

          } else if(aCurrent != bCurrent) {

            // start trying all the possibilities.

```
            trying = true;
```
```
            changable = true;
```
```
            insertable = true;
```
```
            removable = true;
```
```
          }
```

        } else { // a != null, b == null.

```
          if(trying) {
```

            if(removable && aCurrent == bPrevious) {

```
              return !a.hasNext();
```
```
            } else {
```
```
              return false;
```
```
            }
```
```
          } else { // remove a.
```
```
            return !a.hasNext();
```
```
          }
```
```
        }
```
```
      } else {
```

        if(b.hasNext()) { // a == null, b != null.

```
          bCurrent = b.next();
```
```
          if(trying) {
```

            if(insertable && bCurrent == aPrevious) {

```
              return !b.hasNext();
```
```
            } else {
```
```
              return false;
```
```
            }
```
```
          } else { // insert b.
```
```
            return !b.hasNext();
```
```
          }
```

        } else { // a == null, b == null.

          // can only fulfill changable if we are trying.

          return trying ? (changable ? true : false) : true;

```
        }
```
```
      }
```
```
    }
```
```
  }
```
```
 
```

  static IntIterator from(final int[] ints) {

```
    return new IntIterator() {
```
```
 
```
```
      int i = 0;
```
```
 
```
```
      @Override
```
```
      public boolean hasNext() {
```
```
        return i < ints.length;
```
```
      }
```
```
 
```
```
      @Override
```
```
      public int next() {
```
```
        return ints[i++];
```
```
      }
```
```
    };
```
```
  }
```
```
 
```
```
  @Test
```
```
  public void test() {
```

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {})
```
```
        , from(new int[] {})));
```

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1})
```
```
        , from(new int[] {})));
```

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {})
```
```
        , from(new int[] {1})));
```

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1, 2})
```
```
        , from(new int[] {1, 2})));
```

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1, 2, 3})
```
```
        , from(new int[] {1, 3, 3})));
```

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1, 2})
```
```
        , from(new int[] {1, 3})));
```

    Assert.assertFalse(isDistanceZeroOrOne(

```
        from(new int[] {1, 2})
```

        , from(new int[] {1, 3, 2, 2})));

    Assert.assertFalse(isDistanceZeroOrOne(

```
        from(new int[] {1, 3, 2, 2})
```
```
        , from(new int[] {1, 2})));
```

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1, 2, 2})
```

        , from(new int[] {1, 3, 2, 2})));

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1, 3, 2, 2})
```
```
        , from(new int[] {1, 2, 2})));
```

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1, 2, 2, 2})
```

        , from(new int[] {1, 3, 2, 2})));

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1, 3, 2, 2})
```

        , from(new int[] {1, 2, 2, 2})));

    Assert.assertFalse(isDistanceZeroOrOne(

```
        from(new int[] {1, 3, 2, 2, 4})
```

        , from(new int[] {1, 2, 2, 2, 5})));

    Assert.assertTrue(isDistanceZeroOrOne(

        from(new int[] {1, 3, 2, 3, 4, 5})

        , from(new int[] {1, 2, 3, 4, 5})));

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1, 2, 3, 4, 5})
```

        , from(new int[] {1, 3, 2, 3, 4, 5})));

    Assert.assertFalse(isDistanceZeroOrOne(

        from(new int[] {2, 2, 2, 2, 1, 1, 1, 1})

        , from(new int[] {1, 1, 1, 1, 2, 2, 2, 2})));

    Assert.assertTrue(isDistanceZeroOrOne(

        from(new int[] {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1})

        , from(new int[] {2, 1, 2, 1, 2, 1, 2, 1, 2, 1})));

    Assert.assertFalse(isDistanceZeroOrOne(

```
        from(new int[] {1, 1})
```

        , from(new int[] {2, 1, 1, 1})));

    Assert.assertFalse(isDistanceZeroOrOne(

```
        from(new int[] {2, 1, 1, 1})
```
```
        , from(new int[] {1, 1})));
```

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1, 2})
```
```
        , from(new int[] {1, 2, 3})));
```

    Assert.assertTrue(isDistanceZeroOrOne(

```
        from(new int[] {1, 2, 3})
```
```
        , from(new int[] {1, 2})));
```
```
  }
```
```
}
```

shanhe.me

Check if two integer iterators have the maximum distance of one

Check if two integer iterators have the maximum distance of one

Post new comment