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.util.Collection;
  20 import java.util.Comparator;
  21 import java.util.Date;
  22 import java.util.HashMap;
  23 import java.util.Map;
  24
  25 public class TopologicalWalker extends Walker {
  26
  27                 @SuppressWarnings("unchecked")
  28                 Map<ObjectId, ObjectId> collected = new ObjectIdMap(new HashMap<ObjectId,ObjectId>());
  29                 Map<ObjectId, Date> commitTime = new ObjectIdMap(new HashMap<ObjectId,ObjectId>());
  30
  31                 TopologicalSorter<ObjectId> topoSorter;
  32                 final boolean returnAll;
  33
  34                 public boolean isReturnAll() {
  35                         return returnAll;
  36                 }
  37
  38                 protected TopologicalSorter<ObjectId>.Lane getLane(ObjectId id) {
  39                         return topoSorter.lane.get(id);
  40                 }
  41
  42                 protected TopologicalWalker(final Repository repostory, Commit[] starts,
  43                                 String[] relativeResourceName, boolean leafIsBlob,
  44                                 boolean followMainOnly, Boolean merges, ObjectId activeDiffLeafId, final boolean returnAll) {
  45                         super(repostory, starts, relativeResourceName, leafIsBlob,
  46                                         followMainOnly, merges, activeDiffLeafId);
  47                         this.returnAll = returnAll;
  48                         topoSorter = new TopologicalSorter<ObjectId>() {;
  49                                 @Override
  50                                 protected boolean filter(ObjectId element) {
  51                                         return returnAll ? true : collected.containsKey(element);
  52                                 }
  53
  54                                 @Override
  55                                 public int size() {
  56                                         return returnAll ? super.size() : collected.size();
  57                                 }
  58                         };
  59                         topoSorter.setComparator(new Comparator<ObjectId>() {
  60                                 public int compare(ObjectId i1, ObjectId i2) {
  61                                         if (i1 == i2)
  62                                                 return 0;
  63                                         if (i1 == null)
  64                                                 return -1;
  65                                         if (i2 == null)
  66                                                 return 1;
  67
  68                                         if (i1.equals(i2))
  69                                                 return 0;
  70
  71                                         Date when1 = commitTime.get(i1);
  72                                         if (when1 == null)
  73                                                 return i1.compareTo(i2);
  74
  75                                         Date when2 = commitTime.get(i2);
  76                                         if (when2 == null)
  77                                                 return i1.compareTo(i2);
  78
  79                                         int c = when2.compareTo(when1);
  80                                         if (c == 0)
  81                                                 return -1;
  82                                         return c;
  83                                 }
  84                         });
  85                 }
  86
  87                 @Override
  88                 protected void record(ObjectId pred, ObjectId succ) {
  89                         if (pred!=null) {
  90                                 if (succ != null)
  91                                         topoSorter.put(new TopologicalSorter.Edge<ObjectId>(pred, succ));
  92                                 // else topoSorter.put(pred);
  93                         } else
  94                                 topoSorter.put(succ);
  95                 }
  96
  97                 protected void collect(Commit commit, int count, int breadth) {
  98 //                      System.out.println("Got: "+count+" "+commit.getCommitId());
  99                         ObjectId commitId = commit.getCommitId();
 100                         if (commitId == null)
 101                                 commitId = ObjectId.zeroId();
 102                         collected.put(commitId, commitId);
 103                         if (commitId.equals(ObjectId.zeroId()) || commitId.equals(starts[0].getCommitId()))
 104                                 commitTime.put(commitId, new Date(Long.MAX_VALUE));
 105                         else
 106                                 commitTime.put(commitId, commit.getAuthor().getWhen());
 107                 }
 108
 109                 protected boolean isCancelled() {
 110                         return false;
 111                 }
 112
 113                 public Collection collectHistory() {
 114                         super.collectHistory();
 115                         return topoSorter.getEntries();
 116                 }
 117 }