package com.intellij.openapi.vcs;
import com.intellij.util.PairProcessor;
-import org.jetbrains.annotations.NotNull;
-import org.jetbrains.annotations.Nullable;
-import java.util.*;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Map;
-/**
- * @author irengrig
- */
-public class AreaMap<Key, Val> {
- protected final List<Key> myKeys;
- protected final Map<Key, Val> myMap;
- // [admittedly] parent, [-"-] child
- protected final PairProcessor<Key, Key> myKeysResemblance;
- private final Comparator<Key> myComparator;
-
- public static<Key extends Comparable<Key>, Val> AreaMap<Key, Val> create(final PairProcessor<Key, Key> keysResemblance) {
- return new AreaMap<>(keysResemblance, new ComparableComparator<>());
- }
-
- public static<Key, Val> AreaMap<Key, Val> create(final PairProcessor<Key, Key> keysResemblance, final Comparator<Key> comparator) {
- return new AreaMap<>(keysResemblance, comparator);
- }
-
- protected AreaMap(final PairProcessor<Key, Key> keysResemblance, final Comparator<Key> comparator) {
- myKeysResemblance = keysResemblance;
- myComparator = comparator;
- myKeys = new LinkedList<>();
- myMap = new HashMap<>();
- }
+import static com.intellij.util.containers.ContainerUtil.newHashMap;
+import static com.intellij.util.containers.ContainerUtil.newLinkedList;
+import static java.util.Collections.binarySearch;
- public void putAll(final AreaMap<Key, Val> other) {
- myKeys.addAll(other.myKeys);
- myMap.putAll(other.myMap);
- }
+public class AreaMap<Key extends Comparable<Key>, Val> {
+ private final List<Key> myKeys = newLinkedList();
+ private final Map<Key, Val> myMap = newHashMap();
public void put(final Key key, final Val val) {
- putImpl(key, val);
- }
-
- protected int putIfNoParent(final Key key, final Val val) {
- if(myMap.put(key, val) != null) {
- return -1;
- }
-
- if (myKeys.isEmpty()) {
- myKeys.add(key);
- return 0;
- }
-
- final int idx = Collections.binarySearch(myKeys, key, myComparator);
- if (idx < 0) {
- // insertion, no copy exist
- final int insertionIdx = - idx - 1;
- // check parent
- for (final ListIterator<Key> listIterator = myKeys.listIterator(insertionIdx); listIterator.hasPrevious();) {
- final Key previous = listIterator.previous();
- if (myKeysResemblance.process(previous, key)) {
- myMap.remove(key);
- return -1;
- }
- }
- // insertionIdx not necessarily exist
- myKeys.add(insertionIdx, key);
- return insertionIdx;
- }
- assert true;
- myMap.remove(key);
- return -1;
- }
-
- protected int putImpl(final Key key, final Val val) {
myMap.put(key, val);
if (myKeys.isEmpty()) {
myKeys.add(key);
- return 0;
}
-
- final int idx = Collections.binarySearch(myKeys, key, myComparator);
- if (idx < 0) {
- // insertion, no copy exist
- final int insertionIdx = - idx - 1;
- // insertionIdx not necessarily exist
- myKeys.add(insertionIdx, key);
- return insertionIdx;
- }
- return idx;
- }
-
- public Collection<Val> values() {
- return Collections.unmodifiableCollection(myMap.values());
- }
-
- public Collection<Key> keySet() {
- return Collections.unmodifiableCollection(myKeys);
- }
-
- @Nullable
- public Val getExact(final Key key) {
- return myMap.get(key);
- }
-
- public void removeByValue(@NotNull final Val val) {
- for (Iterator<Key> iterator = myKeys.iterator(); iterator.hasNext();) {
- final Key key = iterator.next();
- final Val current = myMap.get(key);
- if (val.equals(current)) {
- iterator.remove();
- myMap.remove(key);
- return;
+ else {
+ int idx = binarySearch(myKeys, key);
+ if (idx < 0) {
+ int insertionIdx = -idx - 1;
+ myKeys.add(insertionIdx, key);
}
}
}
- public void remove(final Key key) {
- myKeys.remove(key);
- myMap.remove(key);
- }
-
- public boolean contains(final Key key) {
- return myKeys.contains(key);
- }
-
- public void getSimiliar(final Key key, final PairProcessor<Key, Val> consumer) {
- final int idx = Collections.binarySearch(myKeys, key, myComparator);
+ public void getSimiliar(Key key, PairProcessor<Key, Key> keysResemblance, PairProcessor<Key, Val> consumer) {
+ int idx = binarySearch(myKeys, key);
if (idx < 0) {
- final int insertionIdx = - idx - 1;
- // take item before
- final int itemBeforeIdx = insertionIdx - 1;
- if (itemBeforeIdx >= 0) {
- for (ListIterator<Key> iterator = myKeys.listIterator(itemBeforeIdx + 1); iterator.hasPrevious(); ) {
- final Key candidate = iterator.previous();
- if (! myKeysResemblance.process(candidate, key)) continue;
+ int insertionIdx = -idx - 1;
+ if (insertionIdx - 1 >= 0) {
+ for (ListIterator<Key> iterator = myKeys.listIterator(insertionIdx); iterator.hasPrevious(); ) {
+ Key candidate = iterator.previous();
+ if (!keysResemblance.process(candidate, key)) continue;
if (consumer.process(candidate, myMap.get(candidate))) break; // if need only a part of keys
}
}
consumer.process(key, myMap.get(key));
}
}
-
- public boolean isEmpty() {
- return myKeys.isEmpty();
- }
-
- public void clear() {
- myKeys.clear();
- myMap.clear();
- }
-
- @Override
- public boolean equals(Object o) {
- if (this == o) return true;
- if (o == null || getClass() != o.getClass()) return false;
-
- AreaMap areaMap = (AreaMap)o;
-
- if (!myKeys.equals(areaMap.myKeys)) return false;
- if (!myMap.equals(areaMap.myMap)) return false;
-
- return true;
- }
-
- @Override
- public int hashCode() {
- int result = myKeys.hashCode();
- result = 31 * result + myMap.hashCode();
- return result;
- }
}