plugins/git4idea/src/git4idea/history/wholeTree/TreeNavigationImpl.java - platform/tools/idea - Git at Google

 /*
  * 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 com.intellij.util.Consumer;
 import com.intellij.util.containers.Convertor;
 import com.intellij.util.containers.ReadonlyList;

 import java.util.*;

 /**
  * @author irengrig
  */
 public class TreeNavigationImpl implements TreeNavigation, WireEventsListener {
   public static final int[] MARKER = new int[]{-1};
   private final TreeMap<Integer, WireEvent> myWireEvents;
   // created for some of wire events; idx of _commit_
   private final TreeMap<Integer, RingIndex> myRingIndex;
   // maximum number of commits, after which index entry should be written
   private final int myCommitIndexInterval;
   // maximum number of wire events, after which index entry should be written
   private final int myNumWiresInGroup;

   public TreeNavigationImpl(final int commitIndexInterval, final int numWiresInGroup) {
     myCommitIndexInterval = commitIndexInterval;
     myNumWiresInGroup = numWiresInGroup;
     myWireEvents = new TreeMap<Integer, WireEvent>();
     myRingIndex = new TreeMap<Integer, RingIndex>();
   }

   public Set<Integer> getRingIndexPoints() {
     return myRingIndex.keySet();
   }

   public void recalcIndex(final ReadonlyList<CommitI> commits, final Convertor<Integer, List<Integer>> future) {
     if (myWireEvents.isEmpty()) return;
     Integer lastIndexKey = myRingIndex.isEmpty() ? null : myRingIndex.lastKey();
     final SortedMap<Integer, WireEvent> tail;
     final Ring<Integer> ring;
     if (lastIndexKey != null) {
       tail = myWireEvents.tailMap(lastIndexKey, true);
       final int size = tail.size();
       if (size == 1) return;
       final Integer lastKey = myWireEvents.lastKey();
       if (lastKey - lastIndexKey < myCommitIndexInterval || size < myNumWiresInGroup) {
         return;
       }
       ring = myRingIndex.lastEntry().getValue().getUsedInRing();
     } else {
       lastIndexKey = myWireEvents.firstKey();
       ring = new Ring.IntegerRing();
       final List<Integer> used = ring.getUsed();
       myRingIndex.put(lastIndexKey, new RingIndex(used.toArray(new Integer[used.size()])));
       WireEventI firstEvent = myWireEvents.firstEntry().getValue();
       performOnRing(ring, firstEvent, commits, future.convert(firstEvent.getCommitIdx()));
       tail = myWireEvents.tailMap(lastIndexKey, false);
     }

     int cnt = 0;
     int recordCommitIdx = myCommitIndexInterval + myWireEvents.floorKey(lastIndexKey);
     for (Integer integer : tail.keySet()) {
       ++ cnt;
       if ((cnt >= myNumWiresInGroup) || (integer >= recordCommitIdx)) {
         final List<Integer> used = ring.getUsed();
         myRingIndex.put(integer, new RingIndex(used.toArray(new Integer[used.size()])));
         cnt = 0;
         recordCommitIdx += myCommitIndexInterval;
       }
       WireEventI event = tail.get(integer);
       performOnRing(ring, event, commits, future.convert(event.getCommitIdx()));
     }
   }

   private void performOnRing(final Ring<Integer> ring, final WireEventI event, final ReadonlyList<CommitI> convertor,
                              List<Integer> futureWireStarts) {
     final int[] wireEnds = event.getWireEnds();
     if (wireEnds != null) {
       for (int wireEnd : wireEnds) {
         int wireNumber = convertor.get(wireEnd).getWireNumber();
         ring.back(wireNumber);
       }
     }
     if (event.isStart()) {
       final int commitWire = convertor.get(event.getCommitIdx()).getWireNumber();
       //System.out.println("use(start): " + commitWire);
       ring.minus(commitWire);
     }
     if (event.isEnd()) {
       final int commitWire = convertor.get(event.getCommitIdx()).getWireNumber();
       //System.out.println("back(2): " + commitWire + " from: " + event.getCommitIdx());
       ring.back(commitWire);
     } else {
       final int[] commitsStarts = event.getCommitsStarts();
       for (int commitStart : commitsStarts) {
         final int commitWire = convertor.get(commitStart).getWireNumber();
         //System.out.println("use(merge commit): " + commitWire);
         ring.minus(commitWire);
       }
     }
     final int[] futureWireStarts1 = event.getFutureWireStarts();
     if (futureWireStarts1 != null && futureWireStarts1.length > 0) {
       for (int i : futureWireStarts1) {
         ring.minus(i);
       }
     }
     for (Integer wireStart : futureWireStarts) {
       ring.minus(wireStart);
     }
   }

   public Collection<WireEvent> getTail(int rowInclusive) {
     return myWireEvents.tailMap(rowInclusive).values();
   }

   public WireEventI getEventForRow(int row) {
     return myWireEvents.get(row);
   }

   @Override
   public Iterator<WireEvent> createWireEventsIterator(int rowInclusive) {
     return myWireEvents.tailMap(rowInclusive).values().iterator();
   }

   private Iterator<WireEvent> createWireEventsBackIterator(int rowExclusive) {
     return myWireEvents.headMap(rowExclusive, false).descendingMap().values().iterator();
   }

   @Override
   public Ring<Integer> getUsedWires(int row, ReadonlyList<CommitI> commits, final Convertor<Integer, List<Integer>> future) {
     final Map.Entry<Integer, RingIndex> entry = myRingIndex.floorEntry(row);
       if (entry == null) return new Ring.IntegerRing();
     final Ring<Integer> ring = entry.getValue().getUsedInRing();
       if (entry.getKey() == row) {
         return ring;
       }
     //System.out.println("-----------------> row = " + row);
       final Iterator<WireEvent> iterator = createWireEventsIterator(entry.getKey());
       while (iterator.hasNext()) {
         final WireEventI event = iterator.next();
         if (event.getCommitIdx() >= row) {
           return ring;
         }
 //        System.out.println("event: " + event.toString());
 //        System.out.println("ring before: " + ring.toString());
         //if (event.getCommitIdx() == entry.getKey()) continue;
         performOnRing(ring, event, commits, future.convert(event.getCommitIdx()));
       }
     return ring;
   }

   @Override
   public void addStartToEvent(int row, final int parentRow, final int wireNumber) {
     modify(row, new Consumer<WireEvent>() {
       @Override
       public void consume(WireEvent wireEvent) {
         wireEvent.addStart(parentRow, wireNumber);
       }
     });
   }

   @Override
   public void setWireStartsNumber(int row, final Integer[] number) {
     modify(row, new Consumer<WireEvent>() {
       @Override
       public void consume(WireEvent wireEvent) {
         wireEvent.setWaitStartsNumber(number);
       }
     });
   }

   @Override
   public void wireStarts(int row) {
     modify(row, new Consumer<WireEvent>() {
       @Override
       public void consume(WireEvent wireEvent) {
         /*if (wireEvent.getCommitsEnds() == null) {
           wireEvent.setCommitEnds(MARKER);
         }*/
       }
     });
     //myWireEvents.put(row, new WireEvent(row, MARKER));
   }

   @Override
   public void wireEnds(int row) {
     modify(row, new Consumer<WireEvent>() {
       @Override
       public void consume(WireEvent wireEvent) {
         wireEvent.addStart(-1, -1);
       }
     });
   }

   @Override
   public void setEnds(int row, final int[] commitEnds) {
     modify(row, new Consumer<WireEvent>() {
       @Override
       public void consume(WireEvent wireEvent) {
         wireEvent.setCommitEnds(commitEnds);
       }
     });
   }

   /*@Override
   public void addWireEvent(int row, int[] branched) {
     final WireEvent wireEvent = new WireEvent(row, branched);
     myWireEvents.put(row, wireEvent);
   }*/

   @Override
   public void parentWireEnds(int row, final int parentRow) {
     modify(row, new Consumer<WireEvent>() {
       @Override
       public void consume(WireEvent wireEvent) {
         wireEvent.addWireEnd(parentRow);
       }
     });
   }

   private void modify(final int row, final Consumer<WireEvent> consumer) {
     WireEvent event = (WireEvent)myWireEvents.get(row);
     if (event == null) {
       event = new WireEvent(row, null);
       myWireEvents.put(row, event);
     }
     consumer.consume(event);
   }

   public void printSelf() {
     System.out.println("============== EVENTS =================");
     for (WireEventI event : myWireEvents.values()) {
       System.out.println(event.toString());
     }
     System.out.println("==============********=================");
   }

   private static class RingIndex {
     private final Integer[] myWireNumbers;

     private RingIndex(Integer[] wireNumbers) {
       myWireNumbers = wireNumbers;
     }

     public Ring<Integer> getUsedInRing() {
       return new Ring.IntegerRing(Arrays.<Integer>asList(myWireNumbers));
     }
   }

   /*public void recountWires(final int fromIdx, final ReadonlyList<CommitI> commits) {
     final Map<Integer, Integer> recalculateMap = new HashMap<Integer, Integer>();

     //final Iterator<WireEvent> backIterator = createWireEventsBackIterator(fromIdx);
     //int runningCommitNumber = backIterator.hasNext() ? backIterator.next().getCommitIdx() : 0;  // next after previous event
     // t_odo: group two iterators to optimize!

     Ring<Integer> usedWires = getUsedWires(fromIdx, commits);
     final Ring.IntegerRing ring = new Ring.IntegerRing(usedWires.getUsed());

     int runningCommitNumber = 0;
     final Iterator<WireEvent> iterator = createWireEventsIterator(fromIdx);
     for (; iterator.hasNext(); ) {
       final WireEvent we = iterator.next();
       recountFragmentZwichem(commits, recalculateMap, runningCommitNumber, we.getCommitIdx());
       runningCommitNumber = we.getCommitIdx() + 1;

       final int[] wireEnds = we.getWireEnds();
       if (wireEnds != null) {
         for (int wireEnd : wireEnds) {
           ring.back(wireEnd);
         }
       }
       if (we.isStart()) {
         final CommitI thisCommit = commits.get(we.getCommitIdx());
         final int thisWireNum = thisCommit.getWireNumber();
         final Integer newNum = ring.getFree();
         if (newNum != thisWireNum) {
           recalculateMap.put(thisWireNum, newNum);
           // if self is start, recalculate self here
           thisCommit.setWireNumber(newNum);
         }
       }
       if (we.isEnd()) {
         ring.back(commits.get(we.getCommitIdx()).getWireNumber());
       }
       final int[] commitsStarts = we.getCommitsStarts();
       if (commitsStarts.length > 0 && (! we.isEnd())) {
         for (int commitStart : commitsStarts) {
           // wire number
           Integer corrected = recalculateMap.get(commitStart);
           int wasWireNumber = commits.get(commitStart).getWireNumber();
           corrected = (corrected == null) ? wasWireNumber : corrected;
           if (! ring.isNumUsed(corrected)) {
             final Integer newNum = ring.getFree();
             recalculateMap.put(wasWireNumber, newNum);
           }
         }
       }
     }
     recountFragmentZwichem(commits, recalculateMap, runningCommitNumber, commits.getSize() - 1);
     // todo is not called any more
     myMaximumWires = Math.max(myMaximumWires, ring.getMaxNumber());
   }*/

   private void recountFragmentZwichem(ReadonlyList<CommitI> commits,
                                       Map<Integer, Integer> recalculateMap,
                                       int runningCommitNumber,
                                       int inclusive) {
     if (! recalculateMap.isEmpty()) {
       for (int i = runningCommitNumber; i <= inclusive; i++) {
         final CommitI commit = commits.get(i);
         final Integer newWire = recalculateMap.get(commit.getWireNumber());
         if (newWire != null) {
           commit.setWireNumber(newWire);
         }
       }
     }
   }
 }
	/*
	* 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 com.intellij.util.Consumer;
	import com.intellij.util.containers.Convertor;
	import com.intellij.util.containers.ReadonlyList;

	import java.util.*;

	/**
	* @author irengrig
	*/
	public class TreeNavigationImpl implements TreeNavigation, WireEventsListener {
	public static final int[] MARKER = new int[]{-1};
	private final TreeMap<Integer, WireEvent> myWireEvents;
	// created for some of wire events; idx of _commit_
	private final TreeMap<Integer, RingIndex> myRingIndex;
	// maximum number of commits, after which index entry should be written
	private final int myCommitIndexInterval;
	// maximum number of wire events, after which index entry should be written
	private final int myNumWiresInGroup;

	public TreeNavigationImpl(final int commitIndexInterval, final int numWiresInGroup) {
	myCommitIndexInterval = commitIndexInterval;
	myNumWiresInGroup = numWiresInGroup;
	myWireEvents = new TreeMap<Integer, WireEvent>();
	myRingIndex = new TreeMap<Integer, RingIndex>();
	}

	public Set<Integer> getRingIndexPoints() {
	return myRingIndex.keySet();
	}

	public void recalcIndex(final ReadonlyList<CommitI> commits, final Convertor<Integer, List<Integer>> future) {
	if (myWireEvents.isEmpty()) return;
	Integer lastIndexKey = myRingIndex.isEmpty() ? null : myRingIndex.lastKey();
	final SortedMap<Integer, WireEvent> tail;
	final Ring<Integer> ring;
	if (lastIndexKey != null) {
	tail = myWireEvents.tailMap(lastIndexKey, true);
	final int size = tail.size();
	if (size == 1) return;
	final Integer lastKey = myWireEvents.lastKey();
	if (lastKey - lastIndexKey < myCommitIndexInterval \|\| size < myNumWiresInGroup) {
	return;
	}
	ring = myRingIndex.lastEntry().getValue().getUsedInRing();
	} else {
	lastIndexKey = myWireEvents.firstKey();
	ring = new Ring.IntegerRing();
	final List<Integer> used = ring.getUsed();
	myRingIndex.put(lastIndexKey, new RingIndex(used.toArray(new Integer[used.size()])));
	WireEventI firstEvent = myWireEvents.firstEntry().getValue();
	performOnRing(ring, firstEvent, commits, future.convert(firstEvent.getCommitIdx()));
	tail = myWireEvents.tailMap(lastIndexKey, false);
	}

	int cnt = 0;
	int recordCommitIdx = myCommitIndexInterval + myWireEvents.floorKey(lastIndexKey);
	for (Integer integer : tail.keySet()) {
	++ cnt;
	if ((cnt >= myNumWiresInGroup) \|\| (integer >= recordCommitIdx)) {
	final List<Integer> used = ring.getUsed();
	myRingIndex.put(integer, new RingIndex(used.toArray(new Integer[used.size()])));
	cnt = 0;
	recordCommitIdx += myCommitIndexInterval;
	}
	WireEventI event = tail.get(integer);
	performOnRing(ring, event, commits, future.convert(event.getCommitIdx()));
	}
	}

	private void performOnRing(final Ring<Integer> ring, final WireEventI event, final ReadonlyList<CommitI> convertor,
	List<Integer> futureWireStarts) {
	final int[] wireEnds = event.getWireEnds();
	if (wireEnds != null) {
	for (int wireEnd : wireEnds) {
	int wireNumber = convertor.get(wireEnd).getWireNumber();
	ring.back(wireNumber);
	}
	}
	if (event.isStart()) {
	final int commitWire = convertor.get(event.getCommitIdx()).getWireNumber();
	//System.out.println("use(start): " + commitWire);
	ring.minus(commitWire);
	}
	if (event.isEnd()) {
	final int commitWire = convertor.get(event.getCommitIdx()).getWireNumber();
	//System.out.println("back(2): " + commitWire + " from: " + event.getCommitIdx());
	ring.back(commitWire);
	} else {
	final int[] commitsStarts = event.getCommitsStarts();
	for (int commitStart : commitsStarts) {
	final int commitWire = convertor.get(commitStart).getWireNumber();
	//System.out.println("use(merge commit): " + commitWire);
	ring.minus(commitWire);
	}
	}
	final int[] futureWireStarts1 = event.getFutureWireStarts();
	if (futureWireStarts1 != null && futureWireStarts1.length > 0) {
	for (int i : futureWireStarts1) {
	ring.minus(i);
	}
	}
	for (Integer wireStart : futureWireStarts) {
	ring.minus(wireStart);
	}
	}

	public Collection<WireEvent> getTail(int rowInclusive) {
	return myWireEvents.tailMap(rowInclusive).values();
	}

	public WireEventI getEventForRow(int row) {
	return myWireEvents.get(row);
	}

	@Override
	public Iterator<WireEvent> createWireEventsIterator(int rowInclusive) {
	return myWireEvents.tailMap(rowInclusive).values().iterator();
	}

	private Iterator<WireEvent> createWireEventsBackIterator(int rowExclusive) {
	return myWireEvents.headMap(rowExclusive, false).descendingMap().values().iterator();
	}

	@Override
	public Ring<Integer> getUsedWires(int row, ReadonlyList<CommitI> commits, final Convertor<Integer, List<Integer>> future) {
	final Map.Entry<Integer, RingIndex> entry = myRingIndex.floorEntry(row);
	if (entry == null) return new Ring.IntegerRing();
	final Ring<Integer> ring = entry.getValue().getUsedInRing();
	if (entry.getKey() == row) {
	return ring;
	}
	//System.out.println("-----------------> row = " + row);
	final Iterator<WireEvent> iterator = createWireEventsIterator(entry.getKey());
	while (iterator.hasNext()) {
	final WireEventI event = iterator.next();
	if (event.getCommitIdx() >= row) {
	return ring;
	}
	// System.out.println("event: " + event.toString());
	// System.out.println("ring before: " + ring.toString());
	//if (event.getCommitIdx() == entry.getKey()) continue;
	performOnRing(ring, event, commits, future.convert(event.getCommitIdx()));
	}
	return ring;
	}

	@Override
	public void addStartToEvent(int row, final int parentRow, final int wireNumber) {
	modify(row, new Consumer<WireEvent>() {
	@Override
	public void consume(WireEvent wireEvent) {
	wireEvent.addStart(parentRow, wireNumber);
	}
	});
	}

	@Override
	public void setWireStartsNumber(int row, final Integer[] number) {
	modify(row, new Consumer<WireEvent>() {
	@Override
	public void consume(WireEvent wireEvent) {
	wireEvent.setWaitStartsNumber(number);
	}
	});
	}

	@Override
	public void wireStarts(int row) {
	modify(row, new Consumer<WireEvent>() {
	@Override
	public void consume(WireEvent wireEvent) {
	/*if (wireEvent.getCommitsEnds() == null) {
	wireEvent.setCommitEnds(MARKER);
	}*/
	}
	});
	//myWireEvents.put(row, new WireEvent(row, MARKER));
	}

	@Override
	public void wireEnds(int row) {
	modify(row, new Consumer<WireEvent>() {
	@Override
	public void consume(WireEvent wireEvent) {
	wireEvent.addStart(-1, -1);
	}
	});
	}

	@Override
	public void setEnds(int row, final int[] commitEnds) {
	modify(row, new Consumer<WireEvent>() {
	@Override
	public void consume(WireEvent wireEvent) {
	wireEvent.setCommitEnds(commitEnds);
	}
	});
	}

	/*@Override
	public void addWireEvent(int row, int[] branched) {
	final WireEvent wireEvent = new WireEvent(row, branched);
	myWireEvents.put(row, wireEvent);
	}*/

	@Override
	public void parentWireEnds(int row, final int parentRow) {
	modify(row, new Consumer<WireEvent>() {
	@Override
	public void consume(WireEvent wireEvent) {
	wireEvent.addWireEnd(parentRow);
	}
	});
	}

	private void modify(final int row, final Consumer<WireEvent> consumer) {
	WireEvent event = (WireEvent)myWireEvents.get(row);
	if (event == null) {
	event = new WireEvent(row, null);
	myWireEvents.put(row, event);
	}
	consumer.consume(event);
	}

	public void printSelf() {
	System.out.println("============== EVENTS =================");
	for (WireEventI event : myWireEvents.values()) {
	System.out.println(event.toString());
	}
	System.out.println("==============********=================");
	}

	private static class RingIndex {
	private final Integer[] myWireNumbers;

	private RingIndex(Integer[] wireNumbers) {
	myWireNumbers = wireNumbers;
	}

	public Ring<Integer> getUsedInRing() {
	return new Ring.IntegerRing(Arrays.<Integer>asList(myWireNumbers));
	}
	}

	/*public void recountWires(final int fromIdx, final ReadonlyList<CommitI> commits) {
	final Map<Integer, Integer> recalculateMap = new HashMap<Integer, Integer>();

	//final Iterator<WireEvent> backIterator = createWireEventsBackIterator(fromIdx);
	//int runningCommitNumber = backIterator.hasNext() ? backIterator.next().getCommitIdx() : 0; // next after previous event
	// t_odo: group two iterators to optimize!

	Ring<Integer> usedWires = getUsedWires(fromIdx, commits);
	final Ring.IntegerRing ring = new Ring.IntegerRing(usedWires.getUsed());

	int runningCommitNumber = 0;
	final Iterator<WireEvent> iterator = createWireEventsIterator(fromIdx);
	for (; iterator.hasNext(); ) {
	final WireEvent we = iterator.next();
	recountFragmentZwichem(commits, recalculateMap, runningCommitNumber, we.getCommitIdx());
	runningCommitNumber = we.getCommitIdx() + 1;

	final int[] wireEnds = we.getWireEnds();
	if (wireEnds != null) {
	for (int wireEnd : wireEnds) {
	ring.back(wireEnd);
	}
	}
	if (we.isStart()) {
	final CommitI thisCommit = commits.get(we.getCommitIdx());
	final int thisWireNum = thisCommit.getWireNumber();
	final Integer newNum = ring.getFree();
	if (newNum != thisWireNum) {
	recalculateMap.put(thisWireNum, newNum);
	// if self is start, recalculate self here
	thisCommit.setWireNumber(newNum);
	}
	}
	if (we.isEnd()) {
	ring.back(commits.get(we.getCommitIdx()).getWireNumber());
	}
	final int[] commitsStarts = we.getCommitsStarts();
	if (commitsStarts.length > 0 && (! we.isEnd())) {
	for (int commitStart : commitsStarts) {
	// wire number
	Integer corrected = recalculateMap.get(commitStart);
	int wasWireNumber = commits.get(commitStart).getWireNumber();
	corrected = (corrected == null) ? wasWireNumber : corrected;
	if (! ring.isNumUsed(corrected)) {
	final Integer newNum = ring.getFree();
	recalculateMap.put(wasWireNumber, newNum);
	}
	}
	}
	}
	recountFragmentZwichem(commits, recalculateMap, runningCommitNumber, commits.getSize() - 1);
	// todo is not called any more
	myMaximumWires = Math.max(myMaximumWires, ring.getMaxNumber());
	}*/

	private void recountFragmentZwichem(ReadonlyList<CommitI> commits,
	Map<Integer, Integer> recalculateMap,
	int runningCommitNumber,
	int inclusive) {
	if (! recalculateMap.isEmpty()) {
	for (int i = runningCommitNumber; i <= inclusive; i++) {
	final CommitI commit = commits.get(i);
	final Integer newWire = recalculateMap.get(commit.getWireNumber());
	if (newWire != null) {
	commit.setWireNumber(newWire);
	}
	}
	}
	}
	}