org.spearce.jgit/src/org/spearce/jgit/lib/TopologicalWalker.java

   1 /*
   2  *  Copyright (C) 2007  Robin Rosenberg
   3 *
   4 *  This library is free software; you can redistribute it and/or
   5 *  modify it under the terms of the GNU General Public
   6 *  License, version 2, as published by the Free Software Foundation.
   7 *
   8 *  This library is distributed in the hope that it will be useful,
   9 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 *  General Public License for more details.
  12 *
  13 *  You should have received a copy of the GNU General Public
  14 *  License along with this library; if not, write to the Free Software
  15 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301
  16 */
  17 package org.spearce.jgit.lib;
  18
  19 import java.io.IOException;
  20 import java.util.Collection;
  21 import java.util.Comparator;
  22 import java.util.Date;
  23 import java.util.HashMap;
  24 import java.util.Map;
  25
  26 /**
  27  * The topological walker traverses the commit graph and
  28  * returns it in topological order. Topological order is
  29  * useful for displaying graphs of more than one branch.
  30  */
  31 public class TopologicalWalker extends Walker {
  32
  33                 @SuppressWarnings("unchecked")
  34                 Map<ObjectId, ObjectId> collected = new ObjectIdMap(new HashMap<ObjectId,ObjectId>());
  35                 Map<ObjectId, Date> commitTime = new ObjectIdMap(new HashMap<ObjectId,ObjectId>());
  36
  37                 TopologicalSorter<ObjectId> topoSorter;
  38                 final boolean returnAll;
  39
  40                 /**
  41                  * @return true if all commit should be returned rather than being filtered.
  42                  */
  43                 public boolean isReturnAll() {
  44                         return returnAll;
  45                 }
  46
  47                 protected TopologicalSorter<ObjectId>.Lane getLane(ObjectId id) {
  48                         return topoSorter.lane.get(id);
  49                 }
  50
  51                 protected TopologicalWalker(final Repository repostory, Commit[] starts,
  52                                 String[] relativeResourceName, boolean leafIsBlob,
  53                                 boolean followMainOnly, Boolean merges, ObjectId activeDiffLeafId, final boolean returnAll) {
  54                         super(repostory, starts, relativeResourceName, leafIsBlob,
  55                                         followMainOnly, merges, activeDiffLeafId);
  56                         this.returnAll = returnAll;
  57                         topoSorter = new TopologicalSorter<ObjectId>() {
  58                                 @Override
  59                                 protected boolean filter(ObjectId element) {
  60                                         return returnAll ? true : collected.containsKey(element);
  61                                 }
  62
  63                                 @Override
  64                                 public int size() {
  65                                         return returnAll ? super.size() : collected.size();
  66                                 }
  67                         };
  68                         topoSorter.setComparator(new Comparator<ObjectId>() {
  69                                 public int compare(ObjectId i1, ObjectId i2) {
  70                                         if (i1 == i2)
  71                                                 return 0;
  72                                         if (i1 == null)
  73                                                 return -1;
  74                                         if (i2 == null)
  75                                                 return 1;
  76
  77                                         if (i1.equals(i2))
  78                                                 return 0;
  79
  80                                         Date when1 = commitTime.get(i1);
  81                                         Date when2 = commitTime.get(i2);
  82                                         if (when1 == null) {
  83                                                 if (when2 == null)
  84                                                         return i1.compareTo(i2);
  85                                                 return 1;
  86                                         }
  87                                         if (when2 == null)
  88                                                 return -1;
  89                                         int c = when2.compareTo(when1);
  90                                         if (c == 0)
  91                                                 return i1.compareTo(i2);
  92                                         return c;
  93                                 }
  94                         });
  95                 }
  96
  97                 @Override
  98                 protected void record(ObjectId pred, ObjectId succ) {
  99                         if (pred!=null) {
 100                                 if (succ != null)
 101                                         topoSorter.put(new TopologicalSorter.Edge<ObjectId>(pred, succ));
 102                                 // else topoSorter.put(pred);
 103                         } else {
 104                                 topoSorter.put(succ);
 105                                 try {
 106                                         collectSortOrder(succ, repository.mapCommit(succ));
 107                                 } catch (IOException e) {
 108                                         // TODO Auto-generated catch block
 109                                         e.printStackTrace();
 110                                 }
 111                         }
 112                         if (pred != null)
 113                                 collectSortOrder(pred, null);
 114                         if (succ != null)
 115                                 collectSortOrder(succ, null);
 116                 }
 117
 118                 protected void collect(Commit commit, int count, int breadth) {
 119 //                      System.out.println("Got: "+count+" "+commit.getCommitId());
 120                         ObjectId commitId = commit.getCommitId();
 121                         if (commitId == null)
 122                                 commitId = ObjectId.zeroId();
 123                         collected.put(commitId, commitId);
 124                         collectSortOrder(commitId, commit);
 125                 }
 126
 127                 private void collectSortOrder(ObjectId commitId, Commit commit) {
 128                         if (commitId.equals(ObjectId.zeroId()))
 129                                 commitTime.put(commitId, new Date(Long.MAX_VALUE));
 130                         else
 131                                 if (commitId.equals(starts[0].getCommitId()))
 132                                         commitTime.put(commitId, new Date(Long.MAX_VALUE-1));
 133                                 else
 134                                         if (commit != null)
 135                                                 commitTime.put(commitId, commit.getAuthor().getWhen());
 136                 }
 137
 138                 protected boolean isCancelled() {
 139                         return false;
 140                 }
 141
 142                 public Collection collectHistory() {
 143                         super.collectHistory();
 144                         return topoSorter.getEntries();
 145                 }
 146 }