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