Компаратор Java с относительным расстоянием

Question

Я пытаюсь создать упорядоченную карту, которая использует сравнительные сравнения расстояний. Однако способ ConcurrentSkipListMap (который я использую в данный момент) интерпретирует сравнения с компаратором, делает сравнение относительных расстояний невозможным. Существуют ли какие-либо структуры данных, которые позволяют использовать карты, такие как операции с ключом и относительный порядок?

Когда я говорю о сравнительных сравнениях, я имею в виду, что два значения нельзя сравнивать напрямую, но их нужно рассматривать с помощью контрольной точки. Подумайте, как эвклидово расстояние.

РЕДАКТИРОВАТЬ:

, например: при сравнении двоичных чисел 0011 и 1100 хочу сказать, один больше, чем другие на основе расстояния Хемминга (количество 1 битов в XOR двух чисел, эквивалентно, расстояние между двумя узлами в графе гиперкуба), очевидно, мне нужна контрольная точка для сравнения расстояния, поэтому я выбираю 0000 в качестве ссылки. Расстояние от 0011 до 0000 равно 2, а расстояние от 1100 до 0000 равно 2, однако 1100 не равно 0011. Я бы хотел сказать, что они имеют одинаковое относительное расстояние, но не равны. В конечном итоге будет отсортирован список этих чисел. Для справки 0000, в порядке возрастания, мы могли бы иметь 1000, 0100, 1100, 1001, 0011, 1110, 1101, 1111.

edit2, почему я не могу использовать компаратор:

Фактор для этого общего порядка: {(x, y) такой, что c.compare (x, y) == 0}.

Из сравнения следует, что отношение является отношением эквивалентности на S и что наложенный порядок является полным порядком на S. Когда мы говорим, что упорядочение, налагаемое с на S, согласуется с равенствами, мы имеем в виду, что фактором для упорядочения является отношение эквивалентности, определяемое методом (объектами) объектов: equals (Object): {(x, y) такое, что x.equals (y)}.

http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html

Answer 1

Вы всегда можете различать экземпляры, имеющие одинаковое расстояние до ссылочного номера, путем дальнейшего сравнения, когда расстояния одинаковы. Например, если вы представлять числа в Integer с:

public int compare(Integer i1, Integer i2) { 
     Integer r1 = hammingDistanceToReference(i1); 
     Integer r2 = hammingDistanceToReference(i2); 

     if (!r1.equals(r2)) 
      return r1.compareTo(r2); 

     return i1.compareTo(i2); 
    } 

Таким образом, цифры, которые имеют различное расстояние Хэмминга до ссылки будут упорядочены должным образом, и те, которые имеют такое же расстояние Хэмминга будет также полностью упорядочена.

Answer 2

Несколько Set реализаций позволяют компаратор, который не согласуется с равными. Если ConcurrentSkipListMap не делает, то ваши варианты должны использовать тот, который делает или использует неупорядоченную коллекцию, а затем сортирует ее вручную при вставке с использованием Collection.sort.

Вот пример создания Comparator (несовместимым с равными):

class Point { 
    int distanceTo(Point other) { 
     ... 
    } 

    Comparator<Point> distanceComparator() { 
     return (point1, point2) -> distanceTo(point1) - distanceTo(point2); 
    } 
} 

List<Point> points; 
Point fixedPoint; 
Collections.sort(points, fixedPoints.distanceComparator()); 

Это теперь будет сортировать points расстоянием до fixedPoint. В качестве альтернативы, по соображениям эффективности, вы можете использовать тот факт, что набор уже был отсортирован для правильной позиции при добавлении новых позиций:

Вы ссылаетесь на документацию для Comparator, в частности определение теории групп для группы связь. Ключевым условием является то, что если два элемента: equals, они должны возвращать 0 при сравнении. Однако, наоборот, это не так: если два элемента возвращают 0 при сравнении, это не обязательно означает, что они равны equals. Существует много случаев, когда порядок двух элементов не определен. Простым примером является порядок словаря, игнорирующий случай. В этой ситуации слова «Foobar», «foobar» и «FOOBAR» все «равны» относительно порядка.

Об этом говорится в документации как «несовместимая по отношению к равным».Например, в документации для SortedSet сказано: «Поведение сортированного набора хорошо определено, даже если его порядок не соответствует равным, он просто не выполняет общий контракт интерфейса Set». Это неверно для всех реализаций Set.