platform/vcs-impl/src/com/intellij/openapi/vcs/changes/committed/SimiliarListsZipper.java

/*
 * Copyright 2000-2009 JetBrains s.r.o.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.intellij.openapi.vcs.changes.committed;

import com.intellij.openapi.vcs.versionBrowser.CommittedChangeList;

import java.util.*;

public class SimiliarListsZipper {
  private final LinkedList<SubSequence<CommittedChangeList>> myLists;
  private final List<CommittedChangeList> myResult;
  private final VcsCommittedListsZipper myZipper;
  private final RepositoryLocationGroup myGroup;

  /**
   * 
   * @param lists - MUST be internally ordered in ??? ascending order
   * @param zipper
   */
  public SimiliarListsZipper(final Collection<List<CommittedChangeList>> lists,
                             final VcsCommittedListsZipper zipper, final RepositoryLocationGroup group) {
    myZipper = zipper;
    myGroup = group;
    myLists = new LinkedList<SubSequence<CommittedChangeList>>();
    myResult = new ArrayList<CommittedChangeList>();
    
    for (List<CommittedChangeList> list : lists) {
      if (! list.isEmpty()) {
        myLists.add(new SubSequence<CommittedChangeList>(list));
      }
    }
  }

  public void zip() {
    Collections.sort(myLists);
    
    while (! myLists.isEmpty()) {
      // check for equality of first n things
      if (tryZipFirstN()) {
        continue;
      }
      if (! usualStep()) {
        break;
      }
    }
  }

  private boolean usualStep() {
    while (! myLists.isEmpty()) {
      final SubSequence<CommittedChangeList> sequence = myLists.removeFirst();
      myResult.add(sequence.getCurrentList());

      if (sequence.hasNext()) {
        sequence.next();
        insert(sequence);
        return true;
      }
    }
    return false;
  }
  
  private boolean tryZipFirstN() {
    final SubSequence<CommittedChangeList> firstSequence = myLists.getFirst();
    List<SubSequence<CommittedChangeList>> removed = null;
    List<CommittedChangeList> toBeZipped = null;
    
    for (ListIterator<SubSequence<CommittedChangeList>> iterator = myLists.listIterator(1); iterator.hasNext();) {
      final SubSequence<CommittedChangeList> sequence = iterator.next();
      if (sequence.compareTo(firstSequence) != 0) {
        break;
      }
      if (removed == null) {
        removed = new ArrayList<SubSequence<CommittedChangeList>>();
        toBeZipped = new ArrayList<CommittedChangeList>();
      }
      iterator.remove();
      removed.add(sequence);
      toBeZipped.add(sequence.getCurrentList());
    }
    if (removed != null) {
      // also remove first
      myLists.removeFirst();
      // and add to equal collection
      removed.add(firstSequence);
      toBeZipped.add(firstSequence.getCurrentList());

      final CommittedChangeList zippedList = myZipper.zip(myGroup, toBeZipped);
      myResult.add(zippedList);

      for (SubSequence<CommittedChangeList> sequence : removed) {
        if (sequence.hasNext()) {
          sequence.next();
          insert(sequence);
        }
      }
      return true;
    }
    return false;
  }

  private void insert(final SubSequence<CommittedChangeList> firstSequence) {
    for (ListIterator<SubSequence<CommittedChangeList>> iterator = myLists.listIterator(); iterator.hasNext();) {
      final SubSequence<CommittedChangeList> currentSequence = iterator.next();
      if (currentSequence.compareTo(firstSequence) > 0) {
        iterator.previous();
        iterator.add(firstSequence);
        return;
      }
    }
    myLists.addLast(firstSequence);
  }

  public List<CommittedChangeList> getResult() {
    return myResult;
  }

  private class SubSequence<T extends CommittedChangeList> implements Comparable<SubSequence<T>> {
    private int myIdx;
    private long myCachedNumber;
    private final List<T> myList;

    private SubSequence(final List<T> list) {
      myList = list;
      myIdx = 0;
      myCachedNumber = myZipper.getNumber(myList.get(0));
    }

    boolean hasNext() {
      return myIdx < (myList.size() - 1);
    }

    public int compareTo(final SubSequence<T> other) {
      final long sign = myCachedNumber - other.myCachedNumber;
      return sign == 0 ? 0 : ((sign < 0) ? -1 : 1);
    }

    void next() {
      if (hasNext()) {
        ++ myIdx;
        myCachedNumber = myZipper.getNumber(myList.get(myIdx));
      }
    }

    T getCurrentList() {
      return myList.get(myIdx);
    }
  }
}