Попытка реализовать приоритетную очередь для поиска ближайшего соседа

Итак, немного предыстории:

  • Я пытаюсь реализовать дерево kd с поиском ближайшего соседа.
  • Для реализации поиска NN мне нужно было создать приоритетную очередь.
  • Приоритетная очередь должна иметь координаты точки и расстояние.
  • Поэтому я решил сгруппировать эти два элемента в Tuple.

Оказывается, C# немного отличается от других языков, к которым я привык.

Вот сообщение об ошибке, которое я получаю, когда делаю это:

PriorityQueue<Tuple<Point, double>> pq = new PriorityQueue<Tuple<Point, double>>();

ошибка CS0311: тип System.Tuple<Tree.Point,double>' cannot be used as type parameterT' в универсальном типе или методе PriorityQueue.PriorityQueue<T>'. There is no implicit reference conversion fromSystem.Tuple' для 'System.IComparable>'

Я исследовал это в течение довольно долгого времени, и, поскольку я новичок в С#, я не совсем понимаю, почему это происходит. Я думаю, что программирование на Python очень упрощает жизнь.


Мой класс приоритетной очереди выглядит так:

public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> dataHeap;

    public PriorityQueue()
    {
        this.dataHeap = new List<T>();
    }

    public void Enqueue(T value)
    {
        this.dataHeap.Add(value);
        BubbleUp();
    }

    public T Dequeue()
    {
        if (this.dataHeap.Count <= 0)
        {
            throw new InvalidOperationException("Cannot Dequeue from empty queue!");
        }

        T result = dataHeap[0];
        int count = this.dataHeap.Count - 1;
        dataHeap[0] = dataHeap[count];
        dataHeap.RemoveAt(count);
        ShiftDown();

        return result;
    }

    private void BubbleUp()
    {
        int childIndex = dataHeap.Count - 1;

        while (childIndex > 0)
        {
            int parentIndex = (childIndex - 1) / 2;

            if (dataHeap[childIndex].CompareTo(dataHeap[parentIndex]) >= 0)
            {
                break;
            }

            SwapAt(childIndex, parentIndex);
            childIndex = parentIndex;
        }
    }

    private void ShiftDown()
    {
        int count = this.dataHeap.Count - 1;
        int parentIndex = 0;

        while (true)
        {
            int childIndex = parentIndex * 2 + 1;
            if (childIndex > count)
            {
                break;
            }

            int rightChild = childIndex + 1;
            if (rightChild <= count && dataHeap[rightChild].CompareTo(dataHeap[childIndex]) < 0)
            {
                childIndex = rightChild;
            }
            if (dataHeap[parentIndex].CompareTo(dataHeap[childIndex]) <= 0)
            {
                break;
            }

            SwapAt(parentIndex, childIndex);
            parentIndex = childIndex;
        }
    }

    public T Peek()
    {
        if (this.dataHeap.Count == 0)
        {
            throw new InvalidOperationException("Queue is empty.");
        }

        T frontItem = dataHeap[0];
        return frontItem;
    }

    public int Count()
    {
        return dataHeap.Count;
    }

    /// <summary>Removes all elements from the queue.</summary>
    public void Clear()
    {
        this.dataHeap.Clear();
    }

    public void CopyToArray(T[] array, int index)
    {
        if (array == null)
        {
            throw new ArgumentNullException("Array");
        }

        int length = array.Length;
        if (index < 0 || index >= length)
        {
            throw new IndexOutOfRangeException("Index must be between zero and array length.");
        }
        if (length - index < this.dataHeap.Count-1)
        {
            throw new ArgumentException("Queue is bigger than array");
        }

        T[] data = this.dataHeap.ToArray();
        Array.Copy(data, 0, array, index, data.Length);
    }

    public bool IsConsistent()
    {
        if (dataHeap.Count == 0)
        {
            return true;
        }

        int lastIndex = dataHeap.Count - 1; 
        for (int parentIndex = 0; parentIndex < dataHeap.Count; ++parentIndex) 
        {
            int leftChildIndex = 2 * parentIndex + 1; 
            int rightChildIndex = 2 * parentIndex + 2;

            if (leftChildIndex <= lastIndex && dataHeap[parentIndex].CompareTo(dataHeap[leftChildIndex]) > 0)
            {
                return false;
            }
            if (rightChildIndex <= lastIndex && dataHeap[parentIndex].CompareTo(dataHeap[rightChildIndex]) > 0)
            {
                return false;
            }
        }

        return true;
    }

    private void SwapAt(int first,int second)
    {
        T value = dataHeap[first];
        dataHeap[first] = dataHeap[second];
        dataHeap[second] = value;
    }

    public override string ToString()
    {
        string queueString = string.Join(" ", dataHeap.ToArray());
        return queueString;
    }
}

Мой класс Point:

class Point : IComparable
{
    private double x;
    private double y;

    public Point(double xCoord, double yCoord)
    {
        SetPoint(xCoord, yCoord);
    }

    ~Point() {}

    public int CompareTo(object obj) 
    {
        if (obj == null) return 1;

        Point p = obj as Point;
        if (p != null) 
            return (this.x.CompareTo(p.x) & this.y.CompareTo(p.y));
        else 
           throw new ArgumentException("Object is not a Point");
    }

    public static bool operator ==(Point a, Point b)
    {
        if (ReferenceEquals(a, null) || ReferenceEquals(b, null)) return true;
        if (a[0] == b[0] && a[1] == b[1]) return true;
        else return false;
    }

    public static bool operator !=(Point a, Point b)
    {
        if (ReferenceEquals(a, null) || ReferenceEquals(b, null)) return true;
        if (a[0] != b[0] || a[1] != b[1]) return true;
        else return false;
    }

    public double this[int index]
    {
        get
        {
            if (index == 0) return x;
            else if (index == 1) return y;
            else throw new System.IndexOutOfRangeException("index " + index + " is out of range");
        }
        set
        {
            if (index == 0) x = value;
            else if (index == 1) y = value;
            else throw new System.IndexOutOfRangeException("index " + index + " is out of range");
        }

    }

    public void SetPoint(double xCoord, double yCoord)
    {
        x = xCoord;
        y = yCoord;
    }

    public override string ToString()
    {
        return "(" + x + ", " + y + ")";
    }
}

person ctzdev    schedule 28.05.2015    source источник
comment
Сообщение об ошибке кажется довольно понятным. Как насчет этого вы не понимаете? Вы потребовали, чтобы тип был сравнимым, а он не определил себя как сравнимый. Либо используйте сопоставимый тип, либо измените структуру данных, чтобы не требовать сравнения типов.   -  person Servy    schedule 28.05.2015
comment
Ваш класс Point не нуждается в финализаторе и, вероятно, должен реализовать IComparable<Point> вместо неуниверсальной версии. Вы также должны подумать о том, чтобы сделать его структурой и сделать ее неизменной.   -  person Lee    schedule 28.05.2015
comment
@Servy Чего я не понимаю, так это того, что Tuple сопоставим, и я реализую IComparable для своей приоритетной очереди, поэтому я не вижу, как появляется это сообщение об ошибке. Извините за невежество, я изучаю C# всего пару дней.   -  person ctzdev    schedule 28.05.2015
comment
@ChrisTarazi Что заставляет вас думать, что Tuple можно сравнить? Вам дали довольно четкое указание на то, что на самом деле это несопоставимо, а это не так.   -  person Servy    schedule 28.05.2015
comment
@Servy Итак, что же подразумевает под этим MSDN? msdn.microsoft.com/en-us/ библиотека/dd990083%28v=vs.110%29.aspx)   -  person ctzdev    schedule 28.05.2015
comment
Он реализует IComparable, а не IComparable<T>, что является ограничением, которое вы применили в своем контейнере.   -  person Servy    schedule 28.05.2015
comment
@Servy Значит, невозможно создать действительно универсальную очередь с приоритетами, которая может обрабатывать все типы?   -  person ctzdev    schedule 28.05.2015
comment
@ChrisTarazi Нет. Вы не можете требовать, чтобы тип реализовывал IComparable<T>, если вы хотите создать контейнер для типов, которые его не реализуют. Вместо этого вам, вероятно, следует просто принять IComparer.   -  person Servy    schedule 28.05.2015


Ответы (1)


Я предлагаю вам удалить ограничение на T, а затем использовать явное IComparer<T> в конструкторе для PriorityQueue. Ваш существующий конструктор может предоставить Comparer<T>.Default в качестве компаратора, если он не указан.

Затем вам нужно изменить obj.CompareTo(other) на comp.Compare(obj, other) на протяжении PriorityQueue.

public class PriorityQueue<T>
{
    private List<T> dataHeap;
    private readonly IComparer<T> comp;

    public PriorityQueue() : this(Comparer<T>.Default) {}

    public PriorityQueue(IComparer<T> comp)
    {
        this.dataHeap = new List<T>();
        this.comp = comp;
    }
    ...
    private void BubbleUp() {
        if (this.comp.Compare(dataHeap[childIndex], dataHeap[parentIndex]) >= 0)
   }
}
person Lee    schedule 28.05.2015