git log, first *working* version with virtual table. loads and merges data, filters...
authorirengrig <Irina.Chernushina@jetbrains.com>
Fri, 10 Sep 2010 11:42:09 +0000 (15:42 +0400)
committerKirill Likhodedov <kirill.likhodedov@jetbrains.com>
Wed, 15 Sep 2010 11:53:04 +0000 (15:53 +0400)
27 files changed:
platform/util/src/com/intellij/util/BufferedListConsumer.java
platform/vcs-api/src/com/intellij/openapi/vcs/ReadonlyListsMerger.java
platform/vcs-api/src/com/intellij/openapi/vcs/Ring.java
platform/vcs-impl/src/com/intellij/openapi/vcs/BigArray.java [new file with mode: 0644]
platform/vcs-impl/src/com/intellij/openapi/vcs/StaticReadonlyList.java [new file with mode: 0644]
plugins/git4idea/src/META-INF/plugin.xml
plugins/git4idea/src/git4idea/history/GitHistoryUtils.java
plugins/git4idea/src/git4idea/history/browser/GitCommit.java
plugins/git4idea/src/git4idea/history/browser/LowLevelAccess.java
plugins/git4idea/src/git4idea/history/browser/LowLevelAccessImpl.java
plugins/git4idea/src/git4idea/history/browser/Portion.java
plugins/git4idea/src/git4idea/history/wholeTree/BigTableTableModel.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/FictiveAction.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/GitLogLongPanel.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/Join.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/LinesCache.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/LinesProxy.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/Loader.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/LoaderImpl.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/SkeletonBuilder.java
plugins/git4idea/src/git4idea/history/wholeTree/TreeComposite.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/TreeNavigation.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/TreeSkeleton.java
plugins/git4idea/src/git4idea/history/wholeTree/TreeSkeletonImpl.java
plugins/git4idea/src/git4idea/history/wholeTree/VisibleLine.java [new file with mode: 0644]
plugins/git4idea/src/git4idea/history/wholeTree/WiresIndex.java [new file with mode: 0644]
plugins/git4idea/tests/git4idea/tests/SkeletonBuilderTest.java

index 2cb12a45a5f24c8ca589d065d715cacbcf057ea0..2a3b990d20c87ae1d7b31e6036bb33cd39e5ece9 100644 (file)
@@ -25,6 +25,8 @@ public class BufferedListConsumer<T> implements Consumer<List<T>> {
   private final int mySize;
   private final List<T> myBuffer;
   private final Consumer<List<T>> myConsumer;
+  private int myCnt;
+  private Runnable myFlushListener;
 
   public BufferedListConsumer(int size, Consumer<List<T>> consumer, int interval) {
     mySize = size;
@@ -32,6 +34,7 @@ public class BufferedListConsumer<T> implements Consumer<List<T>> {
     myConsumer = consumer;
     myInterval = interval;
     myTs = System.currentTimeMillis();
+    myCnt = 0;
   }
 
   public void consumeOne(final T t) {
@@ -39,6 +42,8 @@ public class BufferedListConsumer<T> implements Consumer<List<T>> {
   }
 
   public void consume(List<T> list) {
+    myCnt += list.size();
+
     myBuffer.addAll(list);
     final long ts = System.currentTimeMillis();
     if ((mySize <= myBuffer.size()) || (myInterval > 0) && ((ts - myInterval) > myTs)) {
@@ -53,5 +58,25 @@ public class BufferedListConsumer<T> implements Consumer<List<T>> {
       myConsumer.consume(new ArrayList<T>(myBuffer));
       myBuffer.clear();
     }
+    if (myFlushListener != null) {
+      myFlushListener.run();
+    }
+  }
+
+  public void setFlushListener(Runnable flushListener) {
+    myFlushListener = flushListener;
+  }
+
+  public int getCnt() {
+    return myCnt;
+  }
+
+  public Consumer<T> asConsumer() {
+    return new Consumer<T>() {
+      @Override
+      public void consume(T t) {
+        consumeOne(t);
+      }
+    };
   }
 }
index 0dd7ca76be01824b6f4e0e543cc32be92c6b393c..94d2c97ff8237ab1ef563a00d919a7fffc57b582 100644 (file)
  */
 package com.intellij.openapi.vcs;
 
+import com.intellij.openapi.util.Pair;
 import com.intellij.util.Consumer;
 import com.intellij.util.containers.ReadonlyList;
 
+import java.util.Comparator;
 import java.util.List;
 
 /**
  * @author irengrig
  */
-public class ReadonlyListsMerger<T extends Comparable<T>> {
+public class ReadonlyListsMerger<T> {
   private final List<ReadonlyList<T>> myLists;
   private final Consumer<CompoundNumber> myConsumer;
+  private final Comparator<Pair<CompoundNumber, T>> myComparator;
 
-  public ReadonlyListsMerger(final List<ReadonlyList<T>> lists, final Consumer<CompoundNumber> consumer) {
+  private ReadonlyListsMerger(final List<ReadonlyList<T>> lists, final Consumer<CompoundNumber> consumer, final Comparator<Pair<CompoundNumber, T>> comparator) {
     myLists = lists;
     myConsumer = consumer;
+    myComparator = comparator;
+  }
+
+  public static<T extends Comparable<T>> void merge(final List<ReadonlyList<T>> lists, final Consumer<CompoundNumber> consumer) {
+    new ReadonlyListsMerger<T>(lists, consumer, new ComparableComparator<T>()).execute();
+  }
+
+  public static<T> void merge(final List<ReadonlyList<T>> lists, final Consumer<CompoundNumber> consumer, final Comparator<Pair<CompoundNumber, T>> comparator) {
+    new ReadonlyListsMerger<T>(lists, consumer, comparator).execute();
   }
 
   public void execute() {
@@ -40,19 +52,26 @@ public class ReadonlyListsMerger<T extends Comparable<T>> {
     }
 
     while (true) {
-      T minValue = null;
-      int minValueIdx = -1;
+      CompoundNumber minIdxs = null;
       for (int i = 0; i < idxs.length; i++) {
         if (idxs[i] == -1) continue;  // at end
         final ReadonlyList<T> list = myLists.get(i);
-        if ((minValue == null) || (list.get(idxs[i]).compareTo(minValue) <= 0)) {
-          minValue = list.get(idxs[i]);
-          minValueIdx = i;
+        if ((minIdxs == null) || (myComparator.compare(new Pair<CompoundNumber,T>(new CompoundNumber(i, idxs[i]), list.get(idxs[i])),
+                new Pair<CompoundNumber,T>(minIdxs, myLists.get(minIdxs.getMemberNumber()).get(minIdxs.getIdx()))) <= 0)) {
+          minIdxs = new CompoundNumber(i, idxs[i]);
         }
       }
-      if (minValueIdx == -1) return;
-      myConsumer.consume(new CompoundNumber(minValueIdx, idxs[minValueIdx]));
-      idxs[minValueIdx] = (myLists.get(minValueIdx).getSize() == (idxs[minValueIdx] + 1) ? -1 : idxs[minValueIdx] + 1);
+      if (minIdxs == null) return;
+      myConsumer.consume(minIdxs);
+      final int memberIdx = minIdxs.getMemberNumber();
+      idxs[memberIdx] = (myLists.get(memberIdx).getSize() == (idxs[memberIdx] + 1) ? -1 : idxs[memberIdx] + 1);
+    }
+  }
+
+  private static class ComparableComparator<T extends Comparable<T>> implements Comparator<Pair<CompoundNumber, T>> {
+    @Override
+    public int compare(Pair<CompoundNumber, T> o1, Pair<CompoundNumber, T> o2) {
+      return o1.getSecond().compareTo(o2.getSecond());
     }
   }
 }
index 578a10552dabb7ae13ee5fe9c03c5a5302bbecd2..95109bc03a9d087c625e94b07a62bd8901bf07af 100644 (file)
@@ -34,6 +34,18 @@ public abstract class Ring<T extends Comparable<T>> {
     myFirst = first;
   }
 
+  public Ring(final T first, final List<T> used) {
+    this(first);
+    for (T t : used) {
+      minus(t);
+    }
+  }
+
+  public void reset() {
+    myFreeNumbers.clear();
+    myNextAvailable = myFirst;
+  }
+
   public void back(final T number) {
     final int idx = Collections.binarySearch(myFreeNumbers, number);
     assert idx < 0;
@@ -41,6 +53,10 @@ public abstract class Ring<T extends Comparable<T>> {
   }
 
   public boolean minus(final T t) {
+    while (myNextAvailable.compareTo(t) <= 0) {
+      myFreeNumbers.add(myNextAvailable);
+      myNextAvailable = getNext(myNextAvailable);
+    }
     return myFreeNumbers.remove(t);
   }
 
@@ -66,6 +82,10 @@ public abstract class Ring<T extends Comparable<T>> {
     return result;
   }
 
+  public T getMaxNumber() {
+    return myNextAvailable;
+  }
+
   protected abstract T getNext(final T t);
 
   public T getFree() {
@@ -82,6 +102,10 @@ public abstract class Ring<T extends Comparable<T>> {
       super(0);
     }
 
+    public IntegerRing(final List<Integer> used) {
+      super(0, used);
+    }
+
     @Override
     protected Integer getNext(Integer integer) {
       return integer + 1;
diff --git a/platform/vcs-impl/src/com/intellij/openapi/vcs/BigArray.java b/platform/vcs-impl/src/com/intellij/openapi/vcs/BigArray.java
new file mode 100644 (file)
index 0000000..0eb30ac
--- /dev/null
@@ -0,0 +1,83 @@
+/*
+ * Copyright 2000-2010 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;
+
+import com.intellij.util.containers.ReadonlyList;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * @author irengrig
+ */
+public class BigArray<T> implements ReadonlyList<T> {
+  private final int mySize2Power;
+  private final List<List<T>> myList;
+  private int myPack;
+
+  // pack size = 2^size2Power
+  public BigArray(final int size2Power) {
+    assert (size2Power > 1) && (size2Power < 16);
+    mySize2Power = size2Power;
+    myList = new ArrayList<List<T>>();
+    myPack = (int) Math.pow(2, size2Power);
+  }
+
+  public T get(final int idx) {
+    final int itemNumber = idx >> mySize2Power;
+    return myList.get(itemNumber).get(idx ^ (itemNumber << mySize2Power));
+  }
+
+  public void add(final T t) {
+    final List<T> commits;
+    if (myList.isEmpty() || (myList.get(myList.size() - 1).size() == myPack)) {
+      commits = new ArrayList<T>();
+      myList.add(commits);
+    } else {
+      commits = myList.get(myList.size() - 1);
+    }
+    commits.add(t);
+  }
+
+  public void put(final int idx, final T t) {
+    final int itemNumber = idx >> mySize2Power;
+
+    final List<T> commits;
+    if (itemNumber >= myList.size()) {
+      commits = new ArrayList<T>();
+      myList.add(itemNumber, commits);
+    } else {
+      if (! myList.isEmpty()) {
+        ((ArrayList) myList.get(myList.size() - 1)).trimToSize();
+      }
+      commits = myList.get(itemNumber);
+    }
+    commits.add(idx ^ (itemNumber << mySize2Power), t);
+  }
+
+  public void addingFinished() {
+    ((ArrayList) myList.get(myList.size() - 1)).trimToSize();
+  }
+
+  public int getSize() {
+    if (myList.isEmpty()) return 0;
+    return ((myList.size() - 1) * myPack + myList.get(myList.size() - 1).size());
+  }
+
+  public void clear() {
+    myList.clear();
+  }
+}
diff --git a/platform/vcs-impl/src/com/intellij/openapi/vcs/StaticReadonlyList.java b/platform/vcs-impl/src/com/intellij/openapi/vcs/StaticReadonlyList.java
new file mode 100644 (file)
index 0000000..fba3633
--- /dev/null
@@ -0,0 +1,45 @@
+/*
+ * Copyright 2000-2010 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;
+
+import com.intellij.util.Consumer;
+import com.intellij.util.containers.ReadonlyList;
+
+/**
+ * @author irengrig
+ */
+public class StaticReadonlyList<T> implements ReadonlyList<T>, Consumer<T> {
+  private final BigArray<T> myList;
+
+  public StaticReadonlyList(final int size2power) {
+    myList = new BigArray<T>(size2power);
+  }
+
+  @Override
+  public T get(int idx) {
+    return myList.get(idx);
+  }
+
+  @Override
+  public int getSize() {
+    return myList.getSize();
+  }
+
+  @Override
+  public void consume(T t) {
+    myList.add(t);
+  }
+}
index 364275f8224c753d2e6f8449dd40f12dc21e318e..015fb1579f1b5cb0d3569ca230be1c3c84765a6e 100644 (file)
@@ -33,6 +33,7 @@
       <reference id="Vcs.ShowHistoryForBlock"/>
       <!-- <reference id="ChangesView.Browse"/> -->
       <separator/>
+      <!-- <action id="Test" class="git4idea.history.wholeTree.FictiveAction" text="Test git log"/> -->
 
       <action id="Git.CurrentBranch" class="git4idea.actions.GitCurrentBranch" text="Current Branch..."/>
       <action id="Git.Checkout" class="git4idea.actions.GitCheckout" text="Checkout Branch..."/>
index 2dbf86224aa6252db31e082c1aa144ae815ca949..59898c1cde009c7d80023b832745b001a6405aa2 100644 (file)
@@ -29,6 +29,7 @@ import com.intellij.openapi.vcs.history.VcsFileRevision;
 import com.intellij.openapi.vcs.history.VcsRevisionNumber;
 import com.intellij.openapi.vfs.VirtualFile;
 import com.intellij.util.ArrayUtil;
+import com.intellij.util.CollectConsumer;
 import com.intellij.util.Consumer;
 import com.intellij.util.concurrency.Semaphore;
 import com.intellij.util.text.StringTokenizer;
@@ -335,7 +336,7 @@ public class GitHistoryUtils {
     /*h.addParameters("-M", "--follow", "--name-only",
                     "--pretty=format:%x03%H%x00%ct%x00%an%x00%ae%x00%cn%x00%ce%x00[%P]%x00[%d]%x00%s%n%n%b%x00", "--encoding=UTF-8");*/
     h.addParameters("--name-only",
-                    "--pretty=format:%x03%H%x00%ct%x00%an%x00%ae%x00%cn%x00%ce%x00[%P]%x00[%d]%x00%s%n%n%b%x00", "--encoding=UTF-8");
+                    "--pretty=format:%x03%h%x00%H%x00%ct%x00%an%x00%ae%x00%cn%x00%ce%x00[%p]%x00[%d]%x00%s%n%n%b%x00", "--encoding=UTF-8");
 
     h.endOptions();
     h.addRelativePaths(path);
@@ -348,6 +349,7 @@ public class GitHistoryUtils {
       final String line = tk.nextToken();
       final StringTokenizer tk2 = new StringTokenizer(line, "\u0000\n", false);
       //while (tk2.hasMoreTokens()) {
+      final String shortHash = tk2.nextToken("\u0000");
       final String hash = tk2.nextToken("\u0000\n");
       final String dateString = tk2.nextToken("\u0000");
       final Date date = GitUtil.parseTimestamp(dateString);
@@ -357,12 +359,12 @@ public class GitHistoryUtils {
       final String committerEmail = tk2.nextToken("\u0000");
       // parent hashes
       final String parents = removeSquareBraces(tk2.nextToken("\u0000"));
-      final Set<SHAHash> parentsHashes;
+      final Set<String> parentsHashes;
       if (!StringUtil.isEmptyOrSpaces(parents)) {
         final String[] parentsSplit = parents.split(" "); // todo if parent = 000000
-        parentsHashes = new HashSet<SHAHash>();
+        parentsHashes = new HashSet<String>();
         for (String s : parentsSplit) {
-          parentsHashes.add(new SHAHash(s));
+          parentsHashes.add(s);
         }
       }
       else {
@@ -400,7 +402,7 @@ public class GitHistoryUtils {
         }
       }
       // todo parse revisions... patches?
-      rc.add(new GitCommit(new SHAHash(hash), authorName, committerName, date, message, parentsHashes, pathsList, authorEmail,
+      rc.add(new GitCommit(shortHash, new SHAHash(hash), authorName, committerName, date, message, parentsHashes, pathsList, authorEmail,
                            committerEmail, tags, branches));
       //}
     }
@@ -408,6 +410,12 @@ public class GitHistoryUtils {
   }
 
   public static List<CommitHashPlusParents> hashesWithParents(Project project, FilePath path, final String... parameters) throws VcsException {
+    final CollectConsumer<CommitHashPlusParents> consumer = new CollectConsumer<CommitHashPlusParents>();
+    hashesWithParents(project, path, consumer, parameters);
+    return (List<CommitHashPlusParents>) consumer.getResult();
+  }
+
+  public static void hashesWithParents(Project project, FilePath path, final Consumer<CommitHashPlusParents> consumer, final String... parameters) throws VcsException {
     // adjust path using change manager
     path = getLastCommitName(project, path);
     final VirtualFile root = GitUtil.getGitRoot(path);
@@ -415,30 +423,35 @@ public class GitHistoryUtils {
     h.setNoSSH(true);
     h.setStdoutSuppressed(true);
     h.addParameters(parameters);
-    h.addParameters("--name-only", "--pretty=format:%h%x00%ct%x00%p", "--encoding=UTF-8");
+    h.addParameters("--name-only", "--pretty=format:%x01%h%x00%ct%x00%p", "--encoding=UTF-8");
 
     h.endOptions();
     h.addRelativePaths(path);
     String output = h.run();
     final List<CommitHashPlusParents> rc = new ArrayList<CommitHashPlusParents>();
-    StringTokenizer tk = new StringTokenizer(output, "\n", false);
+    StringTokenizer tk = new StringTokenizer(output, "\u0001", false);
 
     while (tk.hasMoreTokens()) {
       final String line = tk.nextToken();
-      final StringTokenizer tk2 = new StringTokenizer(line, "\u0000", false);
+      final String[] subLines = line.split("\n");
+      final StringTokenizer tk2 = new StringTokenizer(subLines[0], "\u0000", false);
 
       final String hash = tk2.nextToken();
-      final String dateString = tk2.nextToken();
-      final long time = Long.parseLong(dateString.trim());
+      final long time;
+      if (tk2.hasMoreTokens()) {
+        final String dateString = tk2.nextToken();
+        time = Long.parseLong(dateString.trim());
+      } else {
+        time = 0;
+      }
       final String[] parents;
       if (tk2.hasMoreTokens()) {
         parents = tk2.nextToken().split(" ");
       } else {
         parents = ArrayUtil.EMPTY_STRING_ARRAY;
       }
-      rc.add(new CommitHashPlusParents(hash, parents, time));
+      consumer.consume(new CommitHashPlusParents(hash, parents, time));
     }
-    return rc;
   }
 
   @Nullable
index ececa1da646156abd71cae0b4f6a22852e6b7d00..927f4c0ef946919a78a9b5921121a399f822b69f 100644 (file)
@@ -21,6 +21,8 @@ import org.jetbrains.annotations.NotNull;
 import java.util.*;
 
 public class GitCommit {
+  @NotNull
+  private final String myShortHash;
   @NotNull
   private final SHAHash myHash;
   private final String myAuthor;
@@ -34,14 +36,24 @@ public class GitCommit {
   private final List<String> myTags;
   private final List<String> myBranches;
 
-  private final Set<SHAHash> myParentsHashes;
+  private final Set<String> myParentsHashes;
   private final Set<GitCommit> myParentsLinks;
 
   private final List<FilePath> myPathsList;
 
-  public GitCommit(@NotNull final SHAHash hash, final String author, final String committer, final Date date, final String description,
-                   final Set<SHAHash> parentsHashes, final List<FilePath> pathsList,
-                   final String authorEmail, final String comitterEmail, List<String> tags, List<String> branches) {
+  public GitCommit(@NotNull final String shortHash,
+                   @NotNull final SHAHash hash,
+                   final String author,
+                   final String committer,
+                   final Date date,
+                   final String description,
+                   final Set<String> parentsHashes,
+                   final List<FilePath> pathsList,
+                   final String authorEmail,
+                   final String comitterEmail,
+                   List<String> tags,
+                   List<String> branches) {
+    myShortHash = shortHash;
     myAuthor = author;
     myCommitter = committer;
     myDate = date;
@@ -82,7 +94,7 @@ public class GitCommit {
   }
 
   // todo think of interface
-  public Set<SHAHash> getParentsHashes() {
+  public Set<String> getParentsHashes() {
     return myParentsHashes;
   }
 
@@ -140,4 +152,9 @@ public class GitCommit {
   public String toString() {
     return myHash.getValue();
   }
+
+  @NotNull
+  public String getShortHash() {
+    return myShortHash;
+  }
 }
index be78c416eba6a200a7f78d85ca99965b7fc9bb15..7427f9878b3c7dbb5641a5ac66de5146bee3cbfa 100644 (file)
@@ -18,6 +18,7 @@ package git4idea.history.browser;
 import com.intellij.openapi.util.Pair;
 import com.intellij.openapi.vcs.VcsException;
 import com.intellij.util.Consumer;
+import git4idea.history.wholeTree.CommitHashPlusParents;
 import org.jetbrains.annotations.NotNull;
 
 import java.util.Collection;
@@ -46,4 +47,6 @@ public interface LowLevelAccess {
   void loadAllTags(final List<String> sink) throws VcsException;
 
   void cherryPick(SHAHash hash) throws VcsException;
+  void loadHashesWithParents(final @NotNull Collection<String> startingPoints, @NotNull final Collection<ChangesFilter.Filter> filters,
+                                    final Consumer<CommitHashPlusParents> consumer) throws VcsException;
 }
index a1ffda080010359ed4ed1cba02ce0cc337b1b830..8af3b358b2008c5e6418ddbda6e2adb2e8b5fc8a 100644 (file)
@@ -74,6 +74,24 @@ public class LowLevelAccessImpl implements LowLevelAccess {
     return GitHistoryUtils.onlyHashesHistory(myProject, new FilePathImpl(myRoot), parameters.toArray(new String[parameters.size()]));
   }
 
+  public void loadHashesWithParents(final @NotNull Collection<String> startingPoints, @NotNull final Collection<ChangesFilter.Filter> filters,
+                                    final Consumer<CommitHashPlusParents> consumer) throws VcsException {
+    final List<String> parameters = new LinkedList<String>();
+    for (ChangesFilter.Filter filter : filters) {
+      filter.getCommandParametersFilter().applyToCommandLine(parameters);
+    }
+
+    if (! startingPoints.isEmpty()) {
+      for (String startingPoint : startingPoints) {
+        parameters.add(startingPoint);
+      }
+    } else {
+      parameters.add("--all");
+    }
+
+    GitHistoryUtils.hashesWithParents(myProject, new FilePathImpl(myRoot), consumer, parameters.toArray(new String[parameters.size()]));
+  }
+
   public void loadCommits(final Collection<String> startingPoints, final Date beforePoint, final Date afterPoint,
                              final Collection<ChangesFilter.Filter> filtersIn, final Consumer<GitCommit> consumer,
                              int maxCnt, List<String> branches) throws VcsException {
index f105c93c97edf3bf86bb72acd88937b7e31455b9..fc9968f5c7642dc343cf9b933cffabd4e6ceb653 100644 (file)
@@ -25,7 +25,7 @@ import java.util.*;
 // todo introduce synchronization here?
 public class Portion implements AsynchConsumer<GitCommit> {
   private final Map<String, SHAHash> myNameToHash;
-  private final Map<SHAHash, Integer> myHolder;
+  private final Map<String, Integer> myHolder;
   private boolean myStartFound;
 
   // ordered
@@ -33,7 +33,7 @@ public class Portion implements AsynchConsumer<GitCommit> {
 
   private final boolean myChildrenWasSet;
 
-  private final MultiMap<SHAHash, GitCommit> myOrphanMap;
+  private final MultiMap<String, GitCommit> myOrphanMap;
 
   private final Set<String> myUsers;
 
@@ -48,13 +48,13 @@ public class Portion implements AsynchConsumer<GitCommit> {
     myChildrenWasSet = startingPoints == null || startingPoints.isEmpty();
     
     myNameToHash = new HashMap<String, SHAHash>();
-    myHolder = new HashMap<SHAHash, Integer>();
+    myHolder = new HashMap<String, Integer>();
     myOrdered = new LinkedList<GitCommit>();
     
     myRoots = new LinkedList<GitCommit>();
     myLeafs = new LinkedList<GitCommit>();
 
-    myOrphanMap = new MultiMap<SHAHash, GitCommit>();
+    myOrphanMap = new MultiMap<String, GitCommit>();
     myUsers = new HashSet<String>();
   }
 
@@ -71,8 +71,8 @@ public class Portion implements AsynchConsumer<GitCommit> {
     myUsers.add(commit.getCommitter());
 
     myOrdered.add(commit);
-    myHolder.put(commit.getHash(), myOrdered.size() - 1);
-    final Collection<GitCommit> orphans = myOrphanMap.get(commit.getHash());
+    myHolder.put(commit.getShortHash(), myOrdered.size() - 1);
+    final Collection<GitCommit> orphans = myOrphanMap.get(commit.getShortHash());
     for (GitCommit orphan : orphans) {
       orphan.addParentLink(commit);
     }
@@ -92,11 +92,11 @@ public class Portion implements AsynchConsumer<GitCommit> {
       }
     }
 
-    final Set<SHAHash> parentHashes = commit.getParentsHashes();
+    final Set<String> parentHashes = commit.getParentsHashes();
     if (parentHashes.isEmpty()) {
       myStartFound = true;
     } else {
-      for (SHAHash parentHash : parentHashes) {
+      for (String parentHash : parentHashes) {
         final Integer idx = myHolder.get(parentHash);
         if (idx != null) {
           final GitCommit parent = myOrdered.get(idx);
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/BigTableTableModel.java b/plugins/git4idea/src/git4idea/history/wholeTree/BigTableTableModel.java
new file mode 100644 (file)
index 0000000..4e383c3
--- /dev/null
@@ -0,0 +1,58 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import com.intellij.util.containers.ReadonlyList;
+import com.intellij.util.ui.ColumnInfo;
+
+import javax.swing.table.AbstractTableModel;
+import java.util.List;
+
+/**
+ * @author irengrig
+ */
+public class BigTableTableModel<T> extends AbstractTableModel {
+  private final List<ColumnInfo> myColumns;
+  private final ReadonlyList<T> myLines;
+
+  public BigTableTableModel(final List<ColumnInfo> columns, final ReadonlyList<T> lines) {
+    myColumns = columns;
+    myLines = lines;
+  }
+
+  @Override
+  public String getColumnName(int column) {
+    return myColumns.get(column).getName();
+  }
+
+  @Override
+  public int getColumnCount() {
+    return myColumns.size();
+  }
+
+  @Override
+  public int getRowCount() {
+    return myLines.getSize();
+  }
+
+  // todo 7-8 - what about decoration?
+  @Override
+  public Object getValueAt(int rowIndex, int columnIndex) {
+    final T item = myLines.get(rowIndex);
+    final ColumnInfo column = myColumns.get(columnIndex);
+    return item == null ? column.getPreferredStringValue() : column.valueOf(item);
+  }
+}
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/FictiveAction.java b/plugins/git4idea/src/git4idea/history/wholeTree/FictiveAction.java
new file mode 100644 (file)
index 0000000..a2e0b28
--- /dev/null
@@ -0,0 +1,56 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import com.intellij.openapi.actionSystem.AnAction;
+import com.intellij.openapi.actionSystem.AnActionEvent;
+import com.intellij.openapi.actionSystem.PlatformDataKeys;
+import com.intellij.openapi.vcs.BigArray;
+
+/**
+ * @author irengrig
+ */
+public class FictiveAction extends AnAction {
+  public FictiveAction() {
+    super("New Git Log");
+  }
+
+  @Override
+  public void actionPerformed(AnActionEvent e) {
+    final BigArray<VisibleLine> ba = new BigArray<VisibleLine>(4);
+    for (int i = 0; i < 100; i++) {
+      ba.add(new MyLine("Test" + i));
+    }
+    GitLogLongPanel.showDialog(PlatformDataKeys.PROJECT.getData(e.getDataContext()));
+  }
+
+  private static class MyLine implements VisibleLine {
+    private final String myLine;
+
+    public MyLine(String line) {
+      myLine = line;
+    }
+
+    @Override
+    public Object getData() {
+      return myLine;
+    }
+    @Override
+    public boolean isDecoration() {
+      return false;
+    }
+  }
+}
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/GitLogLongPanel.java b/plugins/git4idea/src/git4idea/history/wholeTree/GitLogLongPanel.java
new file mode 100644 (file)
index 0000000..46f9489
--- /dev/null
@@ -0,0 +1,271 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import com.intellij.openapi.application.ModalityState;
+import com.intellij.openapi.project.Project;
+import com.intellij.openapi.ui.DialogWrapper;
+import com.intellij.openapi.util.Comparing;
+import com.intellij.openapi.util.text.StringUtil;
+import com.intellij.openapi.vcs.CalledInAwt;
+import com.intellij.openapi.vcs.CompoundNumber;
+import com.intellij.openapi.vcs.ProjectLevelVcsManager;
+import com.intellij.openapi.vfs.VirtualFile;
+import com.intellij.ui.ColoredTableCellRenderer;
+import com.intellij.ui.ScrollPaneFactory;
+import com.intellij.ui.SimpleTextAttributes;
+import com.intellij.ui.table.JBTable;
+import com.intellij.util.ui.ColumnInfo;
+import com.intellij.util.ui.UIUtil;
+import git4idea.GitVcs;
+import git4idea.history.browser.ChangesFilter;
+import git4idea.history.browser.GitCommit;
+
+import javax.swing.*;
+import javax.swing.event.ChangeEvent;
+import javax.swing.event.ChangeListener;
+import java.awt.*;
+import java.awt.event.FocusAdapter;
+import java.awt.event.FocusEvent;
+import java.awt.event.KeyAdapter;
+import java.awt.event.KeyEvent;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+
+/**
+ * @author irengrig
+ */
+public class GitLogLongPanel {
+  private final static String LOADING_CARD = "LOADING_CARD";
+  private final static String READY_CARD = "READY_CARD";
+
+  private final JPanel myPanel;
+
+  private CardLayout myLayout;
+  private final Loader myLoader;
+  private final LinesProxy myLinesProxy;
+  private UIRefresh myUIRefresh;
+  private BigTableTableModel myTableModel;
+  private JTextField myFilterField;
+  private String myPreviousFilter;
+  private JLabel myLoading;
+
+  // todo for the case when hierarchy is also drawn?
+  public GitLogLongPanel(final Project project, final Collection<VirtualFile> roots) {
+    final LoaderImpl loaderImpl = new LoaderImpl(project, roots);
+    myLoader = loaderImpl;
+    myLinesProxy = loaderImpl.getLinesProxy();
+    myLayout = new CardLayout();
+    myPanel = new JPanel(myLayout);
+    //LoaderImpl
+    myUIRefresh = new UIRefresh() {
+      @Override
+      public void fireDataReady(int idxFrom, int idxTo) {
+        myTableModel.fireTableRowsInserted(idxFrom, idxTo);
+        myPanel.revalidate();
+        myPanel.repaint();
+      }
+      @Override
+      public void setLoadingShowNoDataState() {
+        myLayout.show(myPanel, LOADING_CARD);
+        myPanel.revalidate();
+        myPanel.repaint();
+      }
+      @Override
+      public void setSomeDataReadyState() {
+        myLoading.setVisible(true);
+        myLayout.show(myPanel, READY_CARD);
+        myTableModel.fireTableDataChanged();
+        myPanel.revalidate();
+        myPanel.repaint();
+      }
+
+      @Override
+      public void skeletonLoadComplete() {
+        myLoading.setVisible(false);
+        myPanel.revalidate();
+        myPanel.repaint();
+      }
+
+      @Override
+      public void acceptException(Exception e) {
+        // TODO
+        e.printStackTrace();
+      }
+    };
+    loaderImpl.setUIRefresh(myUIRefresh);
+
+    initPanel();
+  }
+
+  private void initPanel() {
+    final JPanel container = new JPanel(new BorderLayout());
+    final JPanel menu = new JPanel();
+    final BoxLayout layout = new BoxLayout(menu, BoxLayout.X_AXIS);
+    menu.setLayout(layout);
+
+    myLoading = new JLabel("Loading");
+    menu.add(myLoading);
+    myFilterField = new JTextField(100);
+    menu.add(myFilterField);
+    createFilterFieldListener();
+
+    myTableModel = new BigTableTableModel(Arrays.<ColumnInfo>asList(COMMENT, AUTHOR, DATE), myLinesProxy);
+    final JBTable table = new JBTable(myTableModel);
+    table.setModel(myTableModel);
+    final JScrollPane scrollPane = ScrollPaneFactory.createScrollPane(table);
+    scrollPane.getViewport().addChangeListener(new MyChangeListener());
+
+    container.add(menu, BorderLayout.NORTH);
+    container.add(scrollPane, BorderLayout.CENTER);
+
+    myPanel.add(LOADING_CARD, new JLabel("Loading"));
+    myPanel.add(READY_CARD, container);
+
+    table.setDefaultRenderer(Object.class, new ColoredTableCellRenderer() {
+      @Override
+      protected void customizeCellRenderer(JTable table, Object value, boolean selected, boolean hasFocus, int row, int column) {
+        final CompoundNumber memberData = ((LoaderImpl) myLoader).getTreeComposite().getMemberData(row);
+        append(value.toString(), new SimpleTextAttributes(memberData.getMemberNumber() < colors.length ? colors[memberData.getMemberNumber()] :
+                                                          UIUtil.getTableBackground(),
+                                                          selected ? UIUtil.getTableSelectionForeground() : UIUtil.getTableForeground(),
+                                                          null, SimpleTextAttributes.STYLE_PLAIN));
+      }
+    });
+  }
+
+  private final static Color[] colors = {Color.gray.brighter(), Color.green.brighter(), Color.orange.brighter()};
+
+  private void createFilterFieldListener() {
+    myFilterField.addKeyListener(new KeyAdapter() {
+      @Override
+      public void keyReleased(KeyEvent e) {
+        if (e.getKeyCode() == KeyEvent.VK_ENTER) {
+          checkIfFilterChanged();
+        }
+      }
+    });
+    myFilterField.addFocusListener(new FocusAdapter() {
+      @Override
+      public void focusLost(FocusEvent e) {
+        checkIfFilterChanged();
+      }
+    });
+  }
+
+  private void checkIfFilterChanged() {
+    final String newValue = myFilterField.getText().trim();
+    if (! Comparing.equal(myPreviousFilter, newValue)) {
+      myPreviousFilter = newValue;
+      getUIRefresh().setLoadingShowNoDataState();
+
+      if (StringUtil.isEmptyOrSpaces(myPreviousFilter)) {
+        // todo hierarchy presence can be determined here
+        myLoader.loadSkeleton(Collections.<String>emptyList(), Collections.<ChangesFilter.Filter>emptyList());
+      } else {
+        // todo add starting points when ready
+        // todo filters are also temporal
+        myLoader.loadSkeleton(Collections.<String>emptyList(), Collections.<ChangesFilter.Filter>singletonList(new ChangesFilter.Author(myPreviousFilter)));
+      }
+    }
+  }
+
+  public static void showDialog(final Project project) {
+    final VirtualFile[] roots = ProjectLevelVcsManager.getInstance(project).getRootsUnderVcs(GitVcs.getInstance(project));
+    final GitLogLongPanel gitLogLongPanel = new GitLogLongPanel(project, Arrays.asList(roots));
+    new MyDialog(project, gitLogLongPanel).show();
+  }
+
+  public UIRefresh getUIRefresh() {
+    return myUIRefresh;
+  }
+
+  private final static ColumnInfo<Object, String> COMMENT = new ColumnInfo<Object, String>("Comment") {
+    @Override
+    public String valueOf(Object o) {
+      if (o instanceof GitCommit) {
+        return ((GitCommit) o).getDescription();
+      }
+      return o == null ? "" : o.toString();
+    }
+  };
+  private final static ColumnInfo<Object, String> AUTHOR = new ColumnInfo<Object, String>("Committer") {
+    @Override
+    public String valueOf(Object o) {
+      if (o instanceof GitCommit) {
+        return ((GitCommit) o).getCommitter();
+      }
+      return o == null ? "" : o.toString();
+    }
+  };
+  private final static ColumnInfo<Object, String> DATE = new ColumnInfo<Object, String>("Date") {
+    @Override
+    public String valueOf(Object o) {
+      if (o instanceof GitCommit) {
+        return ((GitCommit) o).getDate().toString();
+      }
+      return o == null ? "" : o.toString();
+    }
+  };
+
+  // UIRefresh and Loader both share the same LinesProxy, and [result] data are actually passed through it
+
+  public interface UIRefresh {
+    @CalledInAwt
+    void setLoadingShowNoDataState();
+    @CalledInAwt
+    void setSomeDataReadyState();
+    @CalledInAwt
+    void skeletonLoadComplete();
+    @CalledInAwt
+    void fireDataReady(final int idxFrom, final int idxTo);
+    void acceptException(final Exception e);
+  }
+
+  private static class MyDialog extends DialogWrapper {
+    private final GitLogLongPanel myGitLogLongPanel;
+
+    private MyDialog(Project project, final GitLogLongPanel gitLogLongPanel) {
+      super(project, true);
+      myGitLogLongPanel = gitLogLongPanel;
+      init();
+    }
+
+    @Override
+    protected JComponent createCenterPanel() {
+      return myGitLogLongPanel.myPanel;
+    }
+
+    @Override
+    public JComponent getPreferredFocusedComponent() {
+      myGitLogLongPanel.setModalityState(ModalityState.current());
+      return super.getPreferredFocusedComponent();
+    }
+  }
+
+  private void setModalityState(ModalityState current) {
+    ((LoaderImpl) myLoader).setModalityState(current);
+    checkIfFilterChanged();
+  }
+
+  private static class MyChangeListener implements ChangeListener {
+    @Override
+    public void stateChanged(ChangeEvent e) {
+      System.out.println(e.toString());
+    }
+  }
+}
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/Join.java b/plugins/git4idea/src/git4idea/history/wholeTree/Join.java
new file mode 100644 (file)
index 0000000..bce3209
--- /dev/null
@@ -0,0 +1,38 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import java.util.concurrent.atomic.AtomicInteger;
+
+/**
+ * @author irengrig
+ */
+public class Join {
+  private final Runnable myOnFinish;
+  private AtomicInteger myCnt;
+
+  public Join(int cnt, Runnable onFinish) {
+    myCnt = new AtomicInteger(cnt);
+    myOnFinish = onFinish;
+  }
+
+  public void complete() {
+    final int result = myCnt.decrementAndGet();
+    if (result == 0) {
+      myOnFinish.run();
+    }
+  }
+}
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/LinesCache.java b/plugins/git4idea/src/git4idea/history/wholeTree/LinesCache.java
new file mode 100644 (file)
index 0000000..03a788d
--- /dev/null
@@ -0,0 +1,35 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import com.intellij.util.containers.SLRUMap;
+import git4idea.history.browser.GitCommit;
+
+/**
+ * @author irengrig
+ */
+public class LinesCache {
+  private final static int ourSize = 400; // todo ?
+  private final SLRUMap<String, GitCommit> myCache;
+
+  public LinesCache() {
+    myCache = new SLRUMap<String, GitCommit>(ourSize, 50);
+  }
+
+  public GitCommit get(final String hash) {
+    return myCache.get(hash);
+  }
+}
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/LinesProxy.java b/plugins/git4idea/src/git4idea/history/wholeTree/LinesProxy.java
new file mode 100644 (file)
index 0000000..025cc75
--- /dev/null
@@ -0,0 +1,106 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import com.intellij.util.Consumer;
+import com.intellij.util.containers.ReadonlyList;
+import com.intellij.util.containers.SLRUMap;
+import git4idea.history.browser.GitCommit;
+
+/**
+ * @author irengrig
+ * todo can we specify some type?
+ */
+public class LinesProxy implements ReadonlyList<Object>, Consumer<GitCommit> {
+  private final static int ourSize = 400; // todo ?
+  private final ReadonlyList<VisibleLine> myTreeComposite;
+  private final SLRUMap<String, GitCommit> myCache;
+
+  public LinesProxy(final ReadonlyList<VisibleLine> treeComposite) {
+    myTreeComposite = treeComposite;
+    myCache = new SLRUMap<String, GitCommit>(ourSize, 50);
+  }
+
+  @Override
+  public Object get(int idx) {
+    final VisibleLine visibleLine = myTreeComposite.get(idx);
+    if (visibleLine.isDecoration()) {
+      return visibleLine.getData();
+    }
+    final String hash = new String(((TreeSkeletonImpl.Commit) visibleLine.getData()).getHash());
+    // todo check that gets are made periodically while cell is visible; otherwise, ping
+    // todo (check misses)
+    final GitCommit gitCommit = myCache.get(hash);
+    return (gitCommit == null) ? hash : gitCommit;
+  }
+
+  @Override
+  public void consume(GitCommit gitCommit) {
+    myCache.put(gitCommit.getShortHash(), gitCommit);
+  }
+
+  @Override
+  public int getSize() {
+    return myTreeComposite.getSize();
+  }
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/Loader.java b/plugins/git4idea/src/git4idea/history/wholeTree/Loader.java
new file mode 100644 (file)
index 0000000..ade4e10
--- /dev/null
@@ -0,0 +1,27 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import git4idea.history.browser.ChangesFilter;
+
+import java.util.Collection;
+
+/**
+* @author irengrig
+*/
+public interface Loader {
+  void loadSkeleton(final Collection<String> startingPoints, final Collection<ChangesFilter.Filter> filters);
+}
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/LoaderImpl.java b/plugins/git4idea/src/git4idea/history/wholeTree/LoaderImpl.java
new file mode 100644 (file)
index 0000000..c8824e4
--- /dev/null
@@ -0,0 +1,378 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import com.intellij.openapi.application.Application;
+import com.intellij.openapi.application.ApplicationManager;
+import com.intellij.openapi.application.ModalityState;
+import com.intellij.openapi.diff.impl.patch.formove.FilePathComparator;
+import com.intellij.openapi.project.Project;
+import com.intellij.openapi.util.Comparing;
+import com.intellij.openapi.util.Condition;
+import com.intellij.openapi.util.Pair;
+import com.intellij.openapi.vcs.CalledInAwt;
+import com.intellij.openapi.vcs.CompoundNumber;
+import com.intellij.openapi.vcs.StaticReadonlyList;
+import com.intellij.openapi.vcs.VcsException;
+import com.intellij.openapi.vfs.VirtualFile;
+import com.intellij.util.BufferedListConsumer;
+import com.intellij.util.Consumer;
+import com.intellij.util.containers.Convertor;
+import git4idea.history.browser.ChangesFilter;
+import git4idea.history.browser.GitCommit;
+import git4idea.history.browser.LowLevelAccess;
+import git4idea.history.browser.LowLevelAccessImpl;
+
+import java.util.*;
+
+/**
+ * @author irengrig
+ */
+public class LoaderImpl implements Loader {
+  private static final long ourTestTimeThreshold = 500;
+  private final static int ourBigArraysSize = 10;
+  private final static int ourTestCount = 5;
+  // todo Object +-
+  private final TreeComposite<VisibleLine> myTreeComposite;
+  private final Map<VirtualFile, LowLevelAccess> myAccesses;
+  private final LinesProxy myLinesCache;
+  
+  private int myLoadId;
+  private boolean mySomeDataShown;
+  private final Object myLock;
+  
+  private GitLogLongPanel.UIRefresh myUIRefresh;
+  private final Project myProject;
+  private ModalityState myModalityState;
+
+  public LoaderImpl(final Project project,
+                    final Collection<VirtualFile> allGitRoots) {
+    myProject = project;
+    myTreeComposite = new TreeComposite<VisibleLine>(ourBigArraysSize, WithoutDecorationComparator.getInstance());
+    myLinesCache = new LinesProxy(myTreeComposite);
+    myAccesses = new HashMap<VirtualFile, LowLevelAccess>();
+    for (VirtualFile gitRoot : allGitRoots) {
+      myAccesses.put(gitRoot, new LowLevelAccessImpl(project, gitRoot));
+    }
+    myLock = new Object();
+    myLoadId = 0;
+  }
+
+  public LinesProxy getLinesProxy() {
+    return myLinesCache;
+  }
+
+  public void setModalityState(ModalityState modalityState) {
+    myModalityState = modalityState;
+  }
+
+  public void setUIRefresh(GitLogLongPanel.UIRefresh UIRefresh) {
+    myUIRefresh = UIRefresh;
+  }
+
+  private class MyJoin implements Runnable {
+    private final int myId;
+
+    public MyJoin(final int id) {
+      myId = id;
+    }
+
+    @Override
+    public void run() {
+      ApplicationManager.getApplication().invokeLater(new Runnable() {
+        @Override
+        public void run() {
+          synchronized (myLock) {
+            if (myId == myLoadId) {
+              myUIRefresh.skeletonLoadComplete();
+            }
+          }
+        }
+      }, myModalityState, new Condition() {
+        @Override
+        public boolean value(Object o) {
+          return (! (! myProject.isDisposed()) && (myId == myLoadId));
+        }
+      });
+    }
+  }
+
+  public TreeComposite<VisibleLine> getTreeComposite() {
+    return myTreeComposite;
+  }
+
+  @CalledInAwt
+  @Override
+  public void loadSkeleton(final Collection<String> startingPoints, final Collection<ChangesFilter.Filter> filters) {
+    // load first portion, limited, measure time, decide whether to load only ids or load commits...
+    final Application application = ApplicationManager.getApplication();
+    application.assertIsDispatchThread();
+
+    final int current;
+    synchronized (myLock) {
+      current = ++ myLoadId;
+      mySomeDataShown = false;
+    }
+    final boolean drawHierarchy = filters.isEmpty();
+
+    application.executeOnPooledThread(new Runnable() {
+      @Override
+      public void run() {
+        try {
+          final Join join = new Join(myAccesses.size(), new MyJoin(current));
+          final Runnable joinCaller = new Runnable() {
+            @Override
+            public void run() {
+              join.complete();
+            }
+          };
+
+          myTreeComposite.clearMembers();
+
+          final List<VirtualFile> list = new ArrayList<VirtualFile>(myAccesses.keySet());
+          Collections.sort(list, FilePathComparator.getInstance());
+
+          for (VirtualFile vf : list) {
+            final LowLevelAccess access = myAccesses.get(vf);
+            final Consumer<CommitHashPlusParents> consumer = createCommitsHolderConsumer(drawHierarchy);
+            final Consumer<List<CommitHashPlusParents>> listConsumer = new RefreshingCommitsPackConsumer(current, consumer);
+
+            final BufferedListConsumer<CommitHashPlusParents> bufferedListConsumer =
+              new BufferedListConsumer<CommitHashPlusParents>(15, listConsumer, 1000);
+            bufferedListConsumer.setFlushListener(joinCaller);
+
+            final long start = System.currentTimeMillis();
+            final boolean allDataAlreadyLoaded =
+              FullDataLoader.load(myLinesCache, access, startingPoints, filters, bufferedListConsumer.asConsumer(), ourTestCount);
+            final long end = System.currentTimeMillis();
+
+            if (allDataAlreadyLoaded) {
+              bufferedListConsumer.flush();
+            } else {
+              final boolean loadFull = (end - start) > ourTestTimeThreshold;
+              final LoaderBase loaderBase = new LoaderBase(access, bufferedListConsumer, filters, ourTestCount, loadFull, startingPoints, myLinesCache);
+              loaderBase.execute();
+            }
+          }
+        } catch (VcsException e) {
+          myUIRefresh.acceptException(e);
+        } finally {
+          //myUIRefresh.skeletonLoadComplete();
+        }
+      }
+    });
+  }
+
+  private Consumer<CommitHashPlusParents> createCommitsHolderConsumer(boolean drawHierarchy) {
+    Consumer<CommitHashPlusParents> consumer;
+    if (drawHierarchy) {
+      final SkeletonBuilder skeletonBuilder = new SkeletonBuilder(ourBigArraysSize, ourBigArraysSize - 1);
+      consumer = skeletonBuilder;
+      myTreeComposite.addMember(skeletonBuilder.getResult());
+    } else {
+      final StaticReadonlyList<VisibleLine> readonlyList = new StaticReadonlyList<VisibleLine>(ourBigArraysSize);
+      consumer = new Consumer<CommitHashPlusParents>() {
+        @Override
+        public void consume(CommitHashPlusParents commitHashPlusParents) {
+          readonlyList.consume(new TreeSkeletonImpl.Commit(commitHashPlusParents.getHash().getBytes(), 0, commitHashPlusParents.getTime()));
+        }
+      };
+      myTreeComposite.addMember(readonlyList);
+    }
+    return consumer;
+  }
+
+  private static class MyStopListenToOutputException extends RuntimeException {}
+
+  private class RefreshingCommitsPackConsumer implements Consumer<List<CommitHashPlusParents>> {
+    private final int myId;
+    private final Consumer<CommitHashPlusParents> myConsumer;
+    private Application myApplication;
+    private final Runnable myRefreshRunnable;
+    private final Condition myRefreshCondition;
+
+    public RefreshingCommitsPackConsumer(int id, Consumer<CommitHashPlusParents> consumer) {
+      myId = id;
+      myConsumer = consumer;
+      myApplication = ApplicationManager.getApplication();
+      myRefreshRunnable = new Runnable() {
+        @Override
+        public void run() {
+          myTreeComposite.repack();
+          if (! mySomeDataShown) {
+            // todo remove
+            myUIRefresh.setSomeDataReadyState();
+          }
+          myUIRefresh.fireDataReady(0, myTreeComposite.getSize());
+          mySomeDataShown = true;
+        }
+      };
+      myRefreshCondition = new Condition() {
+        @Override
+        public boolean value(Object o) {
+          return (! (! myProject.isDisposed()) && myId == myLoadId);
+        }
+      };
+    }
+
+    @Override
+    public void consume(List<CommitHashPlusParents> commitHashPlusParentses) {
+      synchronized (myLock) {
+        if (myId != myLoadId) throw new MyStopListenToOutputException();
+      }
+      for (CommitHashPlusParents item : commitHashPlusParentses) {
+        myConsumer.consume(item);
+      }
+      synchronized (myLock) {
+        if (myId != myLoadId) throw new MyStopListenToOutputException();
+        myApplication.invokeLater(myRefreshRunnable, myModalityState, myRefreshCondition);
+        //myApplication.invokeLater(myRefreshRunnable, myModalityState);
+      }
+    }
+  }
+
+  private static class LoaderBase {
+    private final boolean myLoadFullData;
+    private final BufferedListConsumer<CommitHashPlusParents> myConsumer;
+    private final LowLevelAccess myAccess;
+    private final Collection<String> myStartingPoints;
+    private final Consumer<GitCommit> myLinesCache;
+    private final Collection<ChangesFilter.Filter> myFilters;
+    private final int myIgnoreFirst;
+
+    public LoaderBase(LowLevelAccess access,
+                       BufferedListConsumer<CommitHashPlusParents> consumer,
+                       Collection<ChangesFilter.Filter> filters,
+                       int ignoreFirst, boolean loadFullData, Collection<String> startingPoints, final Consumer<GitCommit> linesCache) {
+      myAccess = access;
+      myConsumer = consumer;
+      myFilters = filters;
+      myIgnoreFirst = ignoreFirst;
+      myLoadFullData = loadFullData;
+      myStartingPoints = startingPoints;
+      myLinesCache = linesCache;
+    }
+
+    public void execute() throws VcsException {
+      final MyConsumer consumer = new MyConsumer(myConsumer, myIgnoreFirst);
+
+      if (myLoadFullData) {
+        FullDataLoader.load(myLinesCache, myAccess, myStartingPoints, myFilters, myConsumer.asConsumer(), -1);
+      } else {
+        myAccess.loadHashesWithParents(myStartingPoints, myFilters, consumer);
+      }
+      myConsumer.flush();
+    }
+
+    private static class MyConsumer implements Consumer<CommitHashPlusParents> {
+      private final int myIgnoreFirst;
+      private final BufferedListConsumer<CommitHashPlusParents> myConsumer;
+      private int myCnt;
+
+      private MyConsumer(BufferedListConsumer<CommitHashPlusParents> consumer, int ignoreFirst) {
+        myConsumer = consumer;
+        myIgnoreFirst = ignoreFirst;
+        myCnt = 0;
+      }
+
+      @Override
+      public void consume(CommitHashPlusParents commitHashPlusParents) {
+        if (myCnt >= myIgnoreFirst) {
+          myConsumer.consumeOne(commitHashPlusParents);
+        }
+        ++ myCnt;
+      }
+    }
+  }
+
+  // true if there are no more rows
+  private static class FullDataLoader {
+    private boolean myLoadIsComplete;
+    private int myCnt;
+
+    private FullDataLoader() {
+      myLoadIsComplete = false;
+      myCnt = 0;
+    }
+
+    public static boolean load(final Consumer<GitCommit> linesCache, final LowLevelAccess access, final Collection<String> startingPoints,
+                               final Collection<ChangesFilter.Filter> filters, final Consumer<CommitHashPlusParents> consumer,
+                               final int maxCnt) throws VcsException {
+      return new FullDataLoader().loadFullData(linesCache, access, startingPoints, filters, consumer, maxCnt);
+    }
+
+    private boolean loadFullData(final Consumer<GitCommit> linesCache, final LowLevelAccess access, final Collection<String> startingPoints,
+                               final Collection<ChangesFilter.Filter> filters, final Consumer<CommitHashPlusParents> consumer,
+                               final int maxCnt) throws VcsException {
+    access.loadCommits(startingPoints, null, null, filters, new Consumer<GitCommit>() {
+      @Override
+      public void consume(GitCommit gitCommit) {
+        linesCache.consume(gitCommit);
+        consumer.consume(GitCommitToCommitConvertor.getInstance().convert(gitCommit));
+        if (gitCommit.getParentsHashes().isEmpty()) {
+          myLoadIsComplete = true;
+        }
+        ++ myCnt;
+      }
+    }, maxCnt, Collections.<String>emptyList());
+    return myLoadIsComplete || (maxCnt > 0) && (myCnt < maxCnt);
+  }
+  }
+
+  private static class GitCommitToCommitConvertor implements Convertor<GitCommit, CommitHashPlusParents> {
+    private final static GitCommitToCommitConvertor ourInstance = new GitCommitToCommitConvertor();
+
+    public static GitCommitToCommitConvertor getInstance() {
+      return ourInstance;
+    }
+
+    @Override
+    public CommitHashPlusParents convert(GitCommit o) {
+      final Set<String> parentsHashes = o.getParentsHashes();
+      return new CommitHashPlusParents(o.getShortHash(), parentsHashes.toArray(new String[parentsHashes.size()]), o.getDate().getTime());
+    }
+  }
+
+  private static class WithoutDecorationComparator implements Comparator<Pair<CompoundNumber, VisibleLine>> {
+    private final static WithoutDecorationComparator ourInstance = new WithoutDecorationComparator();
+
+    public static WithoutDecorationComparator getInstance() {
+      return ourInstance;
+    }
+
+    @Override
+    public int compare(Pair<CompoundNumber, VisibleLine> o1, Pair<CompoundNumber, VisibleLine> o2) {
+      if (o1 == null || o2 == null) {
+        return o1 == null ? -1 : 1;
+      }
+      final Object obj1 = o1.getSecond();
+      final Object obj2 = o2.getSecond();
+
+      if (obj1 instanceof TreeSkeletonImpl.Commit && obj2 instanceof TreeSkeletonImpl.Commit) {
+        final long diff;
+        if (o1.getFirst().getMemberNumber() == o2.getFirst().getMemberNumber()) {
+          // natural order
+          diff = o1.getFirst().getIdx() - o2.getFirst().getIdx();
+        } else {
+          // lets take time here
+          diff = - (((TreeSkeletonImpl.Commit)obj1).getTime() - ((TreeSkeletonImpl.Commit)obj2).getTime());
+        }
+        return diff == 0 ? 0 : (diff < 0 ? -1 : 1);
+      }
+      return Comparing.compare(obj1.toString(), obj2.toString());
+    }
+  }
+}
index 5b753db2cdbc6014b2938e2f99834c78c087a0f9..4673cd2007269d7c91fb3c5f74e19b6175b4f41a 100644 (file)
@@ -16,6 +16,7 @@
 package git4idea.history.wholeTree;
 
 import com.intellij.openapi.vcs.Ring;
+import com.intellij.util.AsynchConsumer;
 import com.intellij.util.containers.MultiMap;
 
 import java.util.*;
@@ -23,7 +24,7 @@ import java.util.*;
 /**
  * @author irengrig
  */
-public class SkeletonBuilder {
+public class SkeletonBuilder implements AsynchConsumer<CommitHashPlusParents> {
   private final TreeSkeletonImpl mySkeleton;
   private final MultiMap<String, WaitingCommit> myAwaitingParents;
   // next available idx
@@ -43,7 +44,8 @@ public class SkeletonBuilder {
     mySeizedWires = new HashMap<Integer, Integer>();
   }
 
-  public void accept(final CommitHashPlusParents obj) {
+  @Override
+  public void consume(final CommitHashPlusParents obj) {
     int wireNumber = -1;
 
     final Collection<WaitingCommit> awaiting = myAwaitingParents.remove(obj.getHash());
@@ -68,7 +70,7 @@ public class SkeletonBuilder {
       }
 
       for (final WaitingCommit commit : awaitingList) {
-        final TreeSkeletonImpl.Commit correspCommit = mySkeleton.getCommitAt(commit.myIdx);
+        final TreeSkeletonImpl.Commit correspCommit = mySkeleton.get(commit.myIdx);
         commit.parentFound();
 
         if (commit.isMerge()) {
@@ -120,12 +122,13 @@ public class SkeletonBuilder {
   }
 
   public void finished() {
-
+    mySkeleton.refreshIndex();
     // recount of wires
     recountWires();
   }
 
   private void recountWires() {
+    // todo with reset
     final Ring.IntegerRing ring = new Ring.IntegerRing();
     
     final Map<Integer, Integer> recalculateMap = new HashMap<Integer, Integer>();
@@ -135,7 +138,7 @@ public class SkeletonBuilder {
     for (; iterator.hasNext(); ) {
       final TreeSkeletonImpl.WireEvent we = iterator.next();
       for (int i = runningCommitNumber; i <= we.getCommitIdx(); i++) {
-        final TreeSkeletonImpl.Commit commit = mySkeleton.getCommitAt(i);
+        final TreeSkeletonImpl.Commit commit = mySkeleton.get(i);
         final Integer newWire = recalculateMap.get(commit.getWireNumber());
         if (newWire != null) {
           commit.setWireNumber(newWire);
@@ -150,7 +153,7 @@ public class SkeletonBuilder {
         }
       }
       if (we.isStart()) {
-        final TreeSkeletonImpl.Commit thisCommit = mySkeleton.getCommitAt(we.getCommitIdx());
+        final TreeSkeletonImpl.Commit thisCommit = mySkeleton.get(we.getCommitIdx());
         final int thisWireNum = thisCommit.getWireNumber();
         final Integer newNum = ring.getFree();
         if (newNum != thisWireNum) {
@@ -160,7 +163,7 @@ public class SkeletonBuilder {
         }
       }
       if (we.isEnd()) {
-        ring.back(mySkeleton.getCommitAt(we.getCommitIdx()).getWireNumber());
+        ring.back(mySkeleton.get(we.getCommitIdx()).getWireNumber());
       }
       final int[] commitsStarts = we.getCommitsStarts();
       if (commitsStarts.length > 0 && (! we.isEnd())) {
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/TreeComposite.java b/plugins/git4idea/src/git4idea/history/wholeTree/TreeComposite.java
new file mode 100644 (file)
index 0000000..c953b6e
--- /dev/null
@@ -0,0 +1,102 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import com.intellij.openapi.util.Pair;
+import com.intellij.openapi.vcs.BigArray;
+import com.intellij.openapi.vcs.CompoundNumber;
+import com.intellij.openapi.vcs.ReadonlyListsMerger;
+import com.intellij.util.Consumer;
+import com.intellij.util.SmartList;
+import com.intellij.util.containers.ReadonlyList;
+
+import java.util.Comparator;
+import java.util.List;
+
+/**
+ * @author irengrig
+ */
+public class TreeComposite<T> implements ReadonlyList<T> {
+  private final List<ReadonlyList<T>> myMembers;
+
+  private final Object myLock;
+  private BigArray<CompoundNumber> myCombinedList;
+  private List<BigArray<Integer>> myBackIndex;
+  private final int myPackSize2Power;
+  private final Comparator<Pair<CompoundNumber, T>> myComparator;
+
+  public TreeComposite(final int packSize2Power, final Comparator<Pair<CompoundNumber, T>> comparator) {
+    myPackSize2Power = packSize2Power;
+    myLock = new Object();
+    myComparator = comparator;
+    myMembers = new SmartList<ReadonlyList<T>>();
+    myCombinedList = new BigArray<CompoundNumber>(packSize2Power);
+    myBackIndex = new SmartList<BigArray<Integer>>();
+  }
+
+  public void addMember(final ReadonlyList<T> convertor) {
+    synchronized (myLock) {
+      myMembers.add(convertor);
+    }
+  }
+
+  public void clearMembers() {
+    synchronized (myLock) {
+      myMembers.clear();
+    }
+  }
+
+  // when members are updated
+  public void repack() {
+    final BigArray<CompoundNumber> combinedList = new BigArray<CompoundNumber>(myPackSize2Power);
+    final SmartList<BigArray<Integer>> backIndex = new SmartList<BigArray<Integer>>();
+    for (int i = 0; i < myMembers.size(); i++) {
+      backIndex.add(new BigArray<Integer>(myPackSize2Power));
+    }
+
+    // todo at the moment I think we don't need synch on members, further we can just put fictive list size there
+    ReadonlyListsMerger.merge(myMembers, new Consumer<CompoundNumber>() {
+      @Override
+      public void consume(final CompoundNumber compoundNumber) {
+        combinedList.add(compoundNumber);
+        // it can be only next - for each list
+        backIndex.get(compoundNumber.getMemberNumber()).add(compoundNumber.getIdx());
+      }
+    }, myComparator);
+
+    synchronized (myLock) {
+      myCombinedList = combinedList;
+      myBackIndex = backIndex;
+    }
+  }
+
+  @Override
+  public T get(int idx) {
+    synchronized (myLock) {
+      final CompoundNumber compNumber = myCombinedList.get(idx);
+      return myMembers.get(compNumber.getMemberNumber()).get(compNumber.getIdx());
+    }
+  }
+
+  public CompoundNumber getMemberData(final int idx) {
+    return myCombinedList.get(idx);
+  }
+
+  @Override
+  public int getSize() {
+    return myCombinedList.getSize();
+  }
+}
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/TreeNavigation.java b/plugins/git4idea/src/git4idea/history/wholeTree/TreeNavigation.java
new file mode 100644 (file)
index 0000000..79ae509
--- /dev/null
@@ -0,0 +1,30 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import com.intellij.openapi.vcs.Ring;
+import org.jetbrains.annotations.Nullable;
+
+import java.util.Iterator;
+
+/**
+ * @author irengrig
+ */
+public interface TreeNavigation {
+  @Nullable
+  Ring<Integer> getUsedWires(int row);
+  Iterator<TreeSkeletonImpl.WireEvent> createWireEventsIterator(int rowInclusive);
+}
index 8435953c3172c1af948b87d90e2af4a34dfc77f2..ba0c43b138a18ceb31b61d6b14fd6a73545a2474 100644 (file)
  */
 package git4idea.history.wholeTree;
 
-import java.util.Iterator;
+import com.intellij.util.containers.ReadonlyList;
 
 /**
  * @author irengrig
  */
-public interface TreeSkeleton {
-  short getNumberOfWiresOnEnter(int row);
-  Iterator<TreeSkeletonImpl.WireEvent> createWireEventsIterator(int rowInclusive);
-  TreeSkeletonImpl.Commit getCommitAt(final int row);
+public interface TreeSkeleton extends ReadonlyList<VisibleLine>, TreeNavigation {
 }
index 0eb6be386b66c4b8e709d5640fa905e6202a9e29..16875d4a7cabf80a002058f23c8d5d2474c4b4fe 100644 (file)
 package git4idea.history.wholeTree;
 
 import com.intellij.openapi.util.Pair;
+import com.intellij.openapi.vcs.BigArray;
+import com.intellij.openapi.vcs.Ring;
 import com.intellij.util.ArrayUtil;
 import com.intellij.util.Consumer;
 import com.intellij.util.containers.EmptyIterator;
+import com.intellij.util.containers.ReadonlyList;
 import org.jetbrains.annotations.Nullable;
 
 import java.util.*;
@@ -27,35 +30,33 @@ import java.util.*;
  * @author irengrig
  */
 public class TreeSkeletonImpl implements TreeSkeleton {
-  private final int myPack;
-  private final int myWireEventsPack;
-
-  private final int mySize2Power;
-  private final int myWireEventsIdxSize2Power;
-
   // just commit hashes
-  private final List<Commit[]> myList;
+  private final BigArray<Commit> myList;
 
   // hierarchy structure events
   private final List<WireEvent> myWireEvents;
 
-  // Pair<WireEvent, WireEvent> -> before event, after event todo build afterwards!!
-  private final List<Pair<Integer, Integer>> myEventsIdx;
-  private int mySize;
+  private final WiresIndex myWiresIndex;
+  private final ReadonlyList<Commit> myAsCommitList;
 
   public TreeSkeletonImpl(final int size2Power, final int wireEventsIdxSize2Power) {
-    mySize2Power = size2Power;
-    myWireEventsIdxSize2Power = wireEventsIdxSize2Power;
-
     // some defense. small values for tests
     assert (size2Power < 16) && (wireEventsIdxSize2Power < 16) && (size2Power > 1) && (wireEventsIdxSize2Power > 1);
 
-    myPack = (int) Math.pow(2, size2Power);
-    myWireEventsPack = (int) Math.pow(2, wireEventsIdxSize2Power);
-
-    myList = new LinkedList<Commit[]>();
+    myList = new BigArray<Commit>(size2Power);
     myWireEvents = new LinkedList<WireEvent>(); // todo can use another structure, a list of arrays?
-    myEventsIdx = new LinkedList<Pair<Integer, Integer>>();
+    myWiresIndex = new WiresIndex(wireEventsIdxSize2Power);
+    myAsCommitList = new ReadonlyList<Commit>() {
+      @Override
+      public Commit get(int idx) {
+        return TreeSkeletonImpl.this.get(idx);
+      }
+
+      @Override
+      public int getSize() {
+        return TreeSkeletonImpl.this.getSize();
+      }
+    };
   }
 
   public void wireStarts(final int row) {
@@ -72,21 +73,17 @@ public class TreeSkeletonImpl implements TreeSkeleton {
     });
   }
 
+  public void refreshIndex() {
+    myWiresIndex.reset();
+    for (int i = 0; i < myWireEvents.size(); i++) {
+      final WireEvent event = myWireEvents.get(i);
+      myWiresIndex.accept(i, event, myAsCommitList);
+    }
+  }
+
   public void addWireEvent(final int row, final int[] branched) {
     final WireEvent wireEvent = new WireEvent(row, branched);
     myWireEvents.add(wireEvent);
-
-    // todo create idx afterwards
-    /*final int idx = wireEvent.getCommitIdx() >> myWireEventsIdxSize2Power;
-    if (idx < myEventsIdx.size()) return;
-
-    // when idx of index is event index, put same objects as previous and next
-    final int currentIdx = myWireEvents.size() - 1;
-    final int previous = (wireEvent.getCommitIdx() ^ (idx << myWireEventsIdxSize2Power)) == 0 ? currentIdx : (currentIdx - 1);
-    final Pair<Integer, Integer> indexEntry = new Pair<Integer, Integer>(previous, currentIdx);
-    while (idx >= myEventsIdx.size()) {
-      myEventsIdx.add(indexEntry);
-    }*/
   }
 
   public void addStartToEvent(final int row, final int parentRow) {
@@ -115,12 +112,13 @@ public class TreeSkeletonImpl implements TreeSkeleton {
       event = myWireEvents.get(foundIdx);
     } else {
       event = new WireEvent(row, null);
-      myWireEvents.add(- foundIdx - 1, event);
+      final int index = - foundIdx - 1;
+      myWireEvents.add(index, event);
     }
     wireEventConsumer.consume(event);
   }
 
-  public void markBreaks(final Collection<Integer> breaks) {
+  /*public void markBreaks(final Collection<Integer> breaks) {
     for (Integer aBreak : breaks) {
       modifyWireEvent(aBreak, new Consumer<WireEvent>() {
         @Override
@@ -129,43 +127,34 @@ public class TreeSkeletonImpl implements TreeSkeleton {
         }
       });
     }
-  }
+  }*/
   
   // todo not very well
   public void commitsAdded(final int rowThatWasLast) {
-    mySize = rowThatWasLast + 1;
-    final int itemNumber = rowThatWasLast >> mySize2Power;
-    final int size = (rowThatWasLast ^ (itemNumber << 10)) + 1;
-    final Commit[] newArr = new Commit[size];
-    System.arraycopy(myList.get(itemNumber), 0, newArr, 0, size);
-    myList.set(itemNumber, newArr);
+    myList.addingFinished();
   }
 
   public void addCommit(final int row, final String hash, final int wireNumber, final long time) {
-    final int itemNumber = row >> mySize2Power;
-
-    final Commit[] commits;
-    if (itemNumber >= myList.size()) {
-      commits = new Commit[myPack];
-      myList.add(itemNumber, commits);
-    } else {
-      commits = myList.get(itemNumber);
-    }
-    commits[row ^ (itemNumber << mySize2Power)] = new Commit(hash.getBytes(), wireNumber, time);
+    myList.put(row, new Commit(hash.getBytes(), wireNumber, time));
   }
 
+  @Nullable
   @Override
-  public short getNumberOfWiresOnEnter(final int row) {
-    if (myWireEvents.isEmpty()) return -1;  // todo think of
-
-    final Pair<Integer, Boolean> eventFor = getEventFor(row);
-    // TODO
-    // TODO
-    // TODO
-    // TODO
-    /*return eventFor.getSecond() ? myWireEvents.get(eventFor.getFirst()).getTotalLinesNumberBefore() :
-           myWireEvents.get(eventFor.getFirst()).getTotalLinesNumberAfter();*/
-    return -1;
+  public Ring<Integer> getUsedWires(final int row) {
+    if (myWireEvents.isEmpty()) return null;  // todo think of
+
+    final WiresIndex.IndexPoint point = myWiresIndex.getPoint(row);
+    final int pointIdx = point.getLessOrEqualWireEvent();
+    final Ring<Integer> ring = point.getUsedInRing();
+
+    for (int i = pointIdx; i < myWireEvents.size(); i++) {
+      final WireEvent event = myWireEvents.get(i);
+      if (event.getCommitIdx() >= row) {
+        return ring;
+      }
+      WiresIndex.performOnRing(ring, event, myAsCommitList);
+    }
+    return ring;
   }
 
   private static class SearchWireEventsComparator implements Comparator<WireEvent> {
@@ -185,19 +174,16 @@ public class TreeSkeletonImpl implements TreeSkeleton {
   private Pair<Integer, Boolean> getEventFor(final int row) {
     assert ! myWireEvents.isEmpty();
 
-    final int idx = row >> myWireEventsIdxSize2Power;
-    int eventsIdx = 0;
-    if (! myEventsIdx.isEmpty()) {
-      final Pair<Integer, Integer> pair = myEventsIdx.get(idx);
-      eventsIdx = pair.getFirst();
-    }
+    final WiresIndex.IndexPoint point = myWiresIndex.getPoint(row);
 
-    final int foundIdx = Collections.binarySearch(myWireEvents, new WireEvent(row, null), SearchWireEventsComparator.getInstance());
+    final int sizeDiff = point.getLessOrEqualWireEvent();
+    final int foundIdx = Collections.binarySearch(myWireEvents.subList(point.getLessOrEqualWireEvent(), myWireEvents.size()),
+                                                  new WireEvent(row, null), SearchWireEventsComparator.getInstance());
     // exact coinsidence
-    if (foundIdx >= 0) return new Pair<Integer, Boolean>(foundIdx, true);
+    if (foundIdx >= 0) return new Pair<Integer, Boolean>(sizeDiff + foundIdx, true);
 
     // todo check
-    final int beforeInsertionIdx = - foundIdx - 2;
+    final int beforeInsertionIdx = (- foundIdx - 1) + sizeDiff;
     // the very first then
     if (beforeInsertionIdx < 0) return new Pair<Integer, Boolean>(0, true);
     return (beforeInsertionIdx == myWireEvents.size()) ? new Pair<Integer, Boolean>(myWireEvents.size() - 1, false) :
@@ -213,14 +199,17 @@ public class TreeSkeletonImpl implements TreeSkeleton {
     return myWireEvents.subList(eventFor.getFirst(), myWireEvents.size()).iterator();
   }
 
-  // todo test
   @Override
-  public Commit getCommitAt(final int row) {
-    final int itemNumber = row >> mySize2Power;
-    return myList.get(itemNumber)[row ^ (itemNumber << mySize2Power)];
+  public Commit get(int idx) {
+    return myList.get(idx);
+  }
+
+  @Override
+  public int getSize() {
+    return myList.getSize();
   }
 
-  public static class Commit {
+  public static class Commit implements Comparable<Commit>, VisibleLine {
     private final byte[] myHash;
     private int myWireNumber;
     private final long myTime;
@@ -231,6 +220,16 @@ public class TreeSkeletonImpl implements TreeSkeleton {
       myTime = time;
     }
 
+    @Override
+    public Object getData() {
+      return this;
+    }
+
+    @Override
+    public boolean isDecoration() {
+      return false;
+    }
+
     public byte[] getHash() {
       return myHash;
     }
@@ -246,12 +245,17 @@ public class TreeSkeletonImpl implements TreeSkeleton {
     public void setWireNumber(int wireNumber) {
       myWireNumber = wireNumber;
     }
+
+    @Override
+    public int compareTo(Commit o) {
+      final long result = myTime - o.getTime();
+      return result == 0 ? 0 : (result < 0) ? -1 : 1;
+    }
   }
 
   // commits with 1 start and end just belongs to its wire
   public static class WireEvent {
     private final int myCommitIdx;
-    private int myNumWiresBefore;
     // wire # can be taken from commit
     @Nullable
     private final int[] myCommitsEnds;      // branch point   |/.       -1 here -> start of a wire
@@ -282,19 +286,6 @@ public class TreeSkeletonImpl implements TreeSkeleton {
       }
     }
 
-    /*public short getTotalLinesNumberAfter() {
-      return (short) (myTotalLinesNumberBefore + (myWiresStarts == null ? 0 : myWiresStarts.length)
-                   - (myWiresEnds == null ? 0 : myWiresEnds.length));
-    }*/
-
-    public int getNumWiresBefore() {
-      return myNumWiresBefore;
-    }
-
-    public void setNumWiresBefore(int numWiresBefore) {
-      myNumWiresBefore = numWiresBefore;
-    }
-
     @Nullable
     public int[] getWireEnds() {
       return myWireEnds;
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/VisibleLine.java b/plugins/git4idea/src/git4idea/history/wholeTree/VisibleLine.java
new file mode 100644 (file)
index 0000000..389730b
--- /dev/null
@@ -0,0 +1,24 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+/**
+ * @author irengrig
+ */
+public interface VisibleLine {
+  boolean isDecoration();
+  Object getData();
+}
diff --git a/plugins/git4idea/src/git4idea/history/wholeTree/WiresIndex.java b/plugins/git4idea/src/git4idea/history/wholeTree/WiresIndex.java
new file mode 100644 (file)
index 0000000..0483285
--- /dev/null
@@ -0,0 +1,135 @@
+/*
+ * Copyright 2000-2010 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 git4idea.history.wholeTree;
+
+import com.intellij.openapi.vcs.BigArray;
+import com.intellij.openapi.vcs.Ring;
+import com.intellij.util.containers.ReadonlyList;
+
+import java.util.Arrays;
+import java.util.List;
+
+/**
+ * @author irengrig
+ *
+ * T - used to count wires
+ * index of events -> united index (for the case when several repositories are united)
+ */
+public class WiresIndex {
+  private final int myFrequency2Power;
+  private final Ring<Integer> myRing;
+  // <=
+  private final BigArray<IndexPoint> myPoints;
+
+  private int myPrevious;
+  private int myPreviousAdded;
+
+  public WiresIndex(final int frequency2Power) {
+    myFrequency2Power = frequency2Power;
+    myPoints = new BigArray<IndexPoint>(frequency2Power);
+
+    myRing = new Ring.IntegerRing();
+    myPrevious = -1;       // latest event idx
+    myPreviousAdded = -1;  // latest filled index of index array
+  }
+
+  public void reset() {
+    myRing.reset();
+    myPoints.clear();
+    myPreviousAdded = -1;
+    myPrevious = -1;
+  }
+
+  public void accept(final int eventIdx,
+                     final TreeSkeletonImpl.WireEvent event,
+                     final ReadonlyList<TreeSkeletonImpl.Commit> convertor) {
+    final int commitIdx = event.getCommitIdx();
+    final int idx = commitIdx >> myFrequency2Power; // latest where it should be
+
+    if ((myPreviousAdded == -1) || (idx >= (myPreviousAdded + 1))) {
+      final List<Integer> used = myRing.getUsed();
+
+      final int eventIdxToRegister = ((myPreviousAdded == -1) || (idx == (myPreviousAdded + 1))) ? eventIdx : myPrevious;
+      for (int i = (myPreviousAdded + 1); i <= idx; i++) {
+        myPoints.put(i, new IndexPoint(eventIdxToRegister, used.toArray(new Integer[used.size()])));
+      }
+      myPreviousAdded = idx;
+    }
+    myPrevious = eventIdx;
+
+    performOnRing(myRing, event, convertor);
+  }
+
+  public static void performOnRing(final Ring<Integer> ring, final TreeSkeletonImpl.WireEvent event, final ReadonlyList<TreeSkeletonImpl.Commit> convertor) {
+    final int[] wireEnds = event.getWireEnds();
+    if (wireEnds != null) {
+      for (int wireEnd : wireEnds) {
+        ring.back(convertor.get(wireEnd).getWireNumber());
+      }
+    }
+    if (event.isStart()) {
+      final int commitWire = convertor.get(event.getCommitIdx()).getWireNumber();
+      ring.minus(commitWire);
+    }
+    if (event.isEnd()) {
+      final int commitWire = convertor.get(event.getCommitIdx()).getWireNumber();
+      ring.back(commitWire);
+    } else {
+      final int[] commitsStarts = event.getCommitsStarts();
+      for (int commitStart : commitsStarts) {
+        final int commitWire = convertor.get(commitStart).getWireNumber();
+        ring.minus(commitWire);
+      }
+    }
+  }
+
+  public void finish(final int lastIdx) {
+    myPoints.addingFinished();
+  }
+
+  public IndexPoint getPoint(final int row) {
+    final int idx = row >> myFrequency2Power;
+    return myPoints.get(idx);
+  }
+
+  public int getMaxWires() {
+    return myRing.getMaxNumber();
+  }
+
+  public static class IndexPoint {
+    // wire index
+    private final int myLessOrEqualWireEvent;
+    // T[]
+    private final Integer[] myWireNumbers;
+
+    public IndexPoint(final int lessOrEqualWireEvent, final Integer[] wireNumbers) {
+      myLessOrEqualWireEvent = lessOrEqualWireEvent;
+      myWireNumbers = wireNumbers;
+    }
+
+    public int getLessOrEqualWireEvent() {
+      return myLessOrEqualWireEvent;
+    }
+
+    public Ring<Integer> getUsedInRing() {
+      return new Ring.IntegerRing(Arrays.<Integer>asList(myWireNumbers));
+    }
+
+    public Integer[] getWireNumbers() {
+      return myWireNumbers;
+    }
+  }
+}
index f1a66701eff15ec1957e31406f213312b29ec9e9..f590af6b5dcf84fd283a49d24626b65b09824498 100644 (file)
@@ -37,12 +37,12 @@ public class SkeletonBuilderTest extends TestCase {
     // 4, 4
     final SkeletonBuilder builder = new SkeletonBuilder(2, 2);
     for (CommitHashPlusParents commitHashPlusParents : list) {
-      builder.accept(commitHashPlusParents);
+      builder.consume(commitHashPlusParents);
     }
     builder.finished();
     final TreeSkeleton result = builder.getResult();
     for (int i = 0; i < 5; i++) {
-      final TreeSkeletonImpl.Commit commit = result.getCommitAt(i);
+      final TreeSkeletonImpl.Commit commit = (TreeSkeletonImpl.Commit)result.get(i);
       // just because of the test data order
       Assert.assertEquals("" + (i + 1), new String(commit.getHash()));
       Assert.assertEquals(0, commit.getWireNumber());
@@ -55,6 +55,28 @@ public class SkeletonBuilderTest extends TestCase {
       Assert.assertEquals(true, we.isStart());
       Assert.assertEquals(i, we.getCommitIdx());
     }
+
+    assertWires(result.getUsedWires(0).getUsed());
+    assertWires(result.getUsedWires(1).getUsed());
+    assertWires(result.getUsedWires(2).getUsed());
+    assertWires(result.getUsedWires(3).getUsed());
+    assertWires(result.getUsedWires(4).getUsed());
+
+    final Iterator<TreeSkeletonImpl.WireEvent> iterator2 = result.createWireEventsIterator(4);
+    for (int i = 4; i < 5; i++) {
+      final TreeSkeletonImpl.WireEvent we = iterator2.next();
+      Assert.assertEquals(true, we.isEnd());
+      Assert.assertEquals(true, we.isStart());
+      Assert.assertEquals(i, we.getCommitIdx());
+    }
+
+    final Iterator<TreeSkeletonImpl.WireEvent> iterator3 = result.createWireEventsIterator(2);
+    for (int i = 2; i < 5; i++) {
+      final TreeSkeletonImpl.WireEvent we = iterator3.next();
+      Assert.assertEquals(true, we.isEnd());
+      Assert.assertEquals(true, we.isStart());
+      Assert.assertEquals(i, we.getCommitIdx());
+    }
   }
 
   public void testOneLine() throws Exception {
@@ -62,13 +84,13 @@ public class SkeletonBuilderTest extends TestCase {
     // 4, 4
     final SkeletonBuilder builder = new SkeletonBuilder(2, 2);
     for (CommitHashPlusParents commitHashPlusParents : list) {
-      builder.accept(commitHashPlusParents);
+      builder.consume(commitHashPlusParents);
     }
     builder.finished();
 
     final TreeSkeleton result = builder.getResult();
     for (int i = 0; i < 5; i++) {
-      final TreeSkeletonImpl.Commit commit = result.getCommitAt(i);
+      final TreeSkeletonImpl.Commit commit = (TreeSkeletonImpl.Commit)result.get(i);
       // just because of the test data order
       Assert.assertEquals("" + (i + 1), new String(commit.getHash()));
       Assert.assertEquals(0, commit.getWireNumber());
@@ -82,6 +104,17 @@ public class SkeletonBuilderTest extends TestCase {
     we = iterator.next();
     Assert.assertEquals(true, we.isEnd());
     Assert.assertEquals(4, we.getCommitIdx());
+
+    assertWires(result.getUsedWires(0).getUsed());
+    assertWires(result.getUsedWires(1).getUsed(), 0);
+    assertWires(result.getUsedWires(2).getUsed(), 0);
+    assertWires(result.getUsedWires(3).getUsed(), 0);
+    assertWires(result.getUsedWires(4).getUsed(), 0);
+
+    final Iterator<TreeSkeletonImpl.WireEvent> iterator1 = result.createWireEventsIterator(4);
+    TreeSkeletonImpl.WireEvent we1 = iterator1.next();
+    Assert.assertEquals(true, we1.isEnd());
+    Assert.assertEquals(4, we1.getCommitIdx());
   }
 
   public void testBranchAndMerge() throws Exception {
@@ -89,13 +122,13 @@ public class SkeletonBuilderTest extends TestCase {
     // 4, 4
     final SkeletonBuilder builder = new SkeletonBuilder(2, 2);
     for (CommitHashPlusParents commitHashPlusParents : list) {
-      builder.accept(commitHashPlusParents);
+      builder.consume(commitHashPlusParents);
     }
     builder.finished();
     final TreeSkeleton result = builder.getResult();
     final int[] expectedWireNumbers = {0, 0, 0, 1, 0, 1, 0, 1, 1};
     for (int i = 0; i < 5; i++) {
-      final TreeSkeletonImpl.Commit commit = result.getCommitAt(i);
+      final TreeSkeletonImpl.Commit commit = (TreeSkeletonImpl.Commit)result.get(i);
       // just because of the test data order
       Assert.assertEquals("" + (i + 1), new String(commit.getHash()));
       Assert.assertEquals(expectedWireNumbers[i], commit.getWireNumber());
@@ -125,6 +158,30 @@ public class SkeletonBuilderTest extends TestCase {
     we = iterator.next();
     Assert.assertEquals(true, we.isEnd());
     Assert.assertEquals(8, we.getCommitIdx());
+
+    assertWires(result.getUsedWires(0).getUsed());
+    assertWires(result.getUsedWires(1).getUsed(), 0);
+    assertWires(result.getUsedWires(2).getUsed(), 0, 1);
+    assertWires(result.getUsedWires(3).getUsed(), 0, 1);
+    assertWires(result.getUsedWires(4).getUsed(), 0, 1);
+    assertWires(result.getUsedWires(5).getUsed(), 0, 1);
+    assertWires(result.getUsedWires(6).getUsed(), 0, 1);
+    assertWires(result.getUsedWires(7).getUsed(), 0, 1);  // before wires!
+    assertWires(result.getUsedWires(8).getUsed(), 1);
+
+    final Iterator<TreeSkeletonImpl.WireEvent> iterator1 = result.createWireEventsIterator(5);
+    TreeSkeletonImpl.WireEvent we1 = iterator1.next();
+
+    Assert.assertEquals(6, we1.getWireEnds()[0]);
+    Assert.assertEquals(7, we1.getCommitIdx());
+    final int[] commitsEnds1 = we1.getCommitsEnds();
+    Assert.assertEquals(2, commitsEnds1.length);
+    Assert.assertEquals(5, commitsEnds1[0]);
+    Assert.assertEquals(6, commitsEnds1[1]);
+
+    we1 = iterator1.next();
+    Assert.assertEquals(true, we1.isEnd());
+    Assert.assertEquals(8, we1.getCommitIdx());
   }
 
   public void testBranchIsMerged() throws Exception {
@@ -132,13 +189,13 @@ public class SkeletonBuilderTest extends TestCase {
     // 4, 4
     final SkeletonBuilder builder = new SkeletonBuilder(2, 2);
     for (CommitHashPlusParents commitHashPlusParents : list) {
-      builder.accept(commitHashPlusParents);
+      builder.consume(commitHashPlusParents);
     }
     builder.finished();
     final TreeSkeleton result = builder.getResult();
     final int[] expectedWireNumbers = {0, 0, 0, 1, 1, 2, 1, 0, 2, 1, 1};
     for (int i = 0; i < 5; i++) {
-      final TreeSkeletonImpl.Commit commit = result.getCommitAt(i);
+      final TreeSkeletonImpl.Commit commit = (TreeSkeletonImpl.Commit)result.get(i);
       // just because of the test data order
       Assert.assertEquals("" + (i + 1), new String(commit.getHash()));
       Assert.assertEquals(expectedWireNumbers[i], commit.getWireNumber());
@@ -187,6 +244,37 @@ public class SkeletonBuilderTest extends TestCase {
     Assert.assertEquals(6, commitsEnds[0]);
     Assert.assertEquals(7, commitsEnds[1]);
     Assert.assertEquals(8, commitsEnds[2]);
+
+    assertWires(result.getUsedWires(0).getUsed());
+    assertWires(result.getUsedWires(1).getUsed(), 0, 1);
+    assertWires(result.getUsedWires(2).getUsed(), 0, 1, 2);
+    assertWires(result.getUsedWires(3).getUsed(), 0, 1, 2);
+    assertWires(result.getUsedWires(4).getUsed(), 0, 1, 2);
+    assertWires(result.getUsedWires(5).getUsed(), 0, 1, 2);
+    assertWires(result.getUsedWires(6).getUsed(), 0, 1, 2);
+    assertWires(result.getUsedWires(7).getUsed(), 0, 1, 2);
+    assertWires(result.getUsedWires(8).getUsed(), 0, 1, 2);
+    assertWires(result.getUsedWires(9).getUsed(), 0, 1, 2);
+
+    final Iterator<TreeSkeletonImpl.WireEvent> iterator1 = result.createWireEventsIterator(5);
+    TreeSkeletonImpl.WireEvent we1 = iterator1.next();
+    Assert.assertNull(we1.getWireEnds());
+    Assert.assertEquals(5, we1.getCommitIdx());
+    int[] commitsEnds1 = we1.getCommitsEnds();
+    Assert.assertEquals(2, commitsEnds1.length);
+    Assert.assertEquals(1, commitsEnds1[0]);
+    Assert.assertEquals(3, commitsEnds1[1]);
+
+    we1 = iterator1.next();
+    Assert.assertEquals(7, we1.getWireEnds()[0]);
+    Assert.assertEquals(8, we1.getWireEnds()[1]);
+    Assert.assertEquals(9, we1.getCommitIdx());
+    Assert.assertEquals(true, we1.isEnd());
+    commitsEnds1 = we1.getCommitsEnds();
+    Assert.assertEquals(3, commitsEnds1.length);
+    Assert.assertEquals(6, commitsEnds1[0]);
+    Assert.assertEquals(7, commitsEnds1[1]);
+    Assert.assertEquals(8, commitsEnds1[2]);
   }
 
   private List<CommitHashPlusParents> read(final String data) {
@@ -205,4 +293,12 @@ public class SkeletonBuilderTest extends TestCase {
     }
     return result;
   }
+
+  private void assertWires(final List<Integer> returned, final Integer... expected) {
+    Assert.assertEquals(expected.length, returned.size());
+    for (int i = 0; i < returned.size(); i++) {
+      final Integer integer = returned.get(i);
+      Assert.assertEquals(expected[i], integer);
+    }
+  }
 }