Проблема сортировки компаратора Java с использованием значений карты

Question

У меня есть сценарий, в котором мне нужно взять ключи Map<String, Set<String>> и добавить их в новый Set<String>, который отсортирован.Порядок сортировки основан на значениях карты для каждого ключа.Значением для каждого ключа карты является Набор, содержащий другие ключи, связанные с этим ключом.

Мне нужно отсортировать ключи таким образом, чтобы связанный ключ был ДО другого ключа, который содержит его в связанном наборе.Чтобы использовать парадигму программирования, это похоже на требование объявления переменной в более ранней строке, прежде чем на нее можно будет ссылаться в другой строке.

Например, следующее представляет содержимое Map<String, Set<String>>:

abc=[def, ghi, jkl, mno]
def=[]
ghi=[def]
jkl=[ghi, stu]
mno=[]
pqr=[abc]
stu=[def]
vwx=[mno, ghi]
zy0=[jkl]

В этом примере ключ «jkl» имеет отношение к ключам, «ghi» и «stu», «def» не имеет отношения ни к одному из ключей.

ПРИМЕЧАНИЕ: Взаимоотношения будут только ОДНЫМИ.Так, например, если «ghi» относится к «def», «def» НИКОГДА не будет связано с «ghi».

Так, для приведенной выше карты порядок сортировки будет:

def=[]
mno=[]
ghi=[def]
stu=[def]
vwx=[mno, ghi]
jkl=[ghi, stu]
zy0=[jkl]
abc=[def, ghi, jkl, mno]
pqr=[abc]

Вот компаратор, который я написал.Он находится внутри исполняемого тестового класса, который использует приведенный выше пример:

import java.util.*;

public class RelationshipComparator_Test {
    public static void main(String[] args) {
        String[] testMap = "abc=[def,ghi,jkl,mno]|def=[]|ghi=[def]|jkl=[ghi,stu]|mno=[]|pqr=[abc]|stu=[def]|vwx=[mno,ghi]|zy0=[jkl]".split("[|]");
        Map<String, Set<String>> relationshipMap = new HashMap<>();
        for (String entry : testMap) {
            String[] keyValue = entry.split("[=]");
            String replacement = keyValue[1].replaceAll("[^a-z0-9,]", "");
            Set<String> valueSet = new HashSet<>();
            String[] values = (!replacement.equals("") ? replacement.split("[,]") : new String[0]);
            Collections.addAll(valueSet, values);
            relationshipMap.put(keyValue[0], valueSet);
        }
        Set<String> sortedKeys = new TreeSet<>(new RelationshipComparator(relationshipMap));
        sortedKeys.addAll(relationshipMap.keySet());
        for (String key : sortedKeys) {
            System.out.println(key + "=" + relationshipMap.get(key));
        }
    }

    static class RelationshipComparator implements Comparator<String> {
        private Map<String, Set<String>> relationshipMap;

        RelationshipComparator(Map<String, Set<String>> relationshipMap) {
            this.relationshipMap = relationshipMap;
        }

        @Override
        public int compare(String o1, String o2) {
            Set<String> o1Set = relationshipMap.get(o1);
            Set<String> o2Set = relationshipMap.get(o2);
            if (o1Set != null && o2Set != null) {
                if (o1Set.size() == 0 && o2Set.size() > 0) {
                    printCompare(o1, o2, "o1Set.size() == 0: -1");
                    return -1;
                }
                if (o2Set.size() == 0 && o1Set.size() > 0) {
                    printCompare(o1, o2, "o2Set.size() == 0: 1");
                    return 1;
                }
                if (o1Set.contains(o2)) {
                    printCompare(o1, o2, "o1Set.contains(o2): 1");
                    return 1;
                }
                if (o2Set.contains(o1)) {
                    printCompare(o1, o2, "o2Set.contains(o1): -1");
                    return -1;
                }
            }
            printCompare(o1, o2, "default: " + o1.compareTo(o2));
            return o1.compareTo(o2);
        }

        private void printCompare(String o1, String o2, String result) {
            System.out.println("**********");
            System.out.println("o1: " + o1 + "=" + relationshipMap.get(o1));
            System.out.println("o2: " + o2 + "=" + relationshipMap.get(o2));
            System.out.println("result: " + result);
            System.out.println("**********");
            System.out.println();
        }
    }
}

Если вы запустите код, вы увидите следующий вывод:

def=[]
mno=[]
ghi=[def]
jkl=[stu, ghi]
abc=[def, ghi, jkl, mno]
pqr=[abc]
stu=[def]
vwx=[ghi, mno]
zy0=[jkl]

Это неверно, потому что "jkl "ссылается на" stu ", но после" jkl "сортируется" stu ".

Любая помощь будет принята с благодарностью.

Answer 1

Вы говорите, что отношения являются односторонними, что исключает очевидные случаи, такие как:

a=[b]
b=[a]

, для которых невозможно решение.Однако нам также необходимо исключить циклические отношения, такие как:

a=[b]
b=[c]
c=[a]

Если это так, то я считаю, что вы можете добиться необходимого упорядочения, используя PriorityQueue для упорядочения ключей по размерунабор значений, связанных с ключом.Поскольку ключи удаляются из очереди, их также необходимо удалять из любого связанного набора значений, который их содержит.Какие наборы значений содержат данный ключ, могут быть восстановлены из обратного Map<String, Set<String>>, который содержит набор ключей, которые относятся к данному ключу значения.

Надеемся, что некоторый код прояснит ситуацию:

static List<String> orderByRef(Map<String, Set<String>> relationshipMap)
{
  final Map<String, Set<String>> relationshipMapCopy = new HashMap<>();
  for(String key : relationshipMap.keySet())
    relationshipMapCopy.put(key, new HashSet<>(relationshipMap.get(key)));

  final Map<String, Set<String>> referencedBy = new HashMap<>();
  for(String key : relationshipMap.keySet())
    referencedBy.put(key, new HashSet<>());

  for (Entry<String,Set<String>> e : relationshipMapCopy.entrySet())
    for(String v : e.getValue())
      referencedBy.get(v).add(e.getKey());

  PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>()
  {
    @Override
    public int compare(String k1, String k2)
    {
      return relationshipMapCopy.get(k1).size() - relationshipMapCopy.get(k2).size();
    }
  });
  pq.addAll(relationshipMap.keySet());

  List<String> orderedKeys = new ArrayList<>();
  while(!pq.isEmpty()) 
  {      
    String minKey = pq.poll();
    if(!relationshipMapCopy.get(minKey).isEmpty()) 
    {
      // cyclic relationship
      break;
    }
    orderedKeys.add(minKey);
    for(String refKey : referencedBy.get(minKey))
    {
      // remove minKey from value set of refKey 
      relationshipMapCopy.get(refKey).remove(minKey);
      // reorder refKey in pq
      pq.remove(refKey);
      pq.add(refKey);
    }
  }

  return orderedKeys;    
}

Обратите внимание, что, поскольку мы модифицируем relationshipMap, удаляя ключи из наборов значений, нам сначала нужно создать глубокую копию.Кроме того, мы можем обнаружить наличие циклических отношений, проверив, что набор значений клавиши min пуст.

Вывод:

def []
mno []
stu [def]
ghi [def]
vwx [ghi, mno]
jkl [stu, ghi]
zy0 [jkl]
abc [def, ghi, jkl, mno]
pqr [abc]

, который удовлетворяет условию, что ни на один ключ не ссылаютсяпрежде чем он появится в списке.

Для ввода, содержащего циклические отношения, например, (z=[y]|y=[]|a=[b]|b=[c]|c=[a]), мы получаем:

y []
z [y]