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