Реализация B-дерева в Java с использованием обобщений - PullRequest
Новая
       0

Реализация B-дерева в Java с использованием обобщений

1 голос
/ 31 июля 2011

Я написал свое собственное 2-3-4 дерево в Java. В настоящее время мой код выглядит так: 

public class tree234{  
    private class node{  
        Comparable data[]=new Comparable[3];  
        node next[]=new node[4];  
    }   
}

Вместо этого я хотел бы иметь что-то вроде этого: 

public class tree234<T extends Comparable<? super T>>{  
    private class node{  
        T[] data=new T[3];//error here!  
        node[] next=new node[4];  
    }  
}

Хотя я понимаю, что не могу создать массив (и вроде как понимаю, почему), я не могу придумать достаточно простой способ реализации класса узла с помощью обобщений. Есть предложения?

Ответы [ 4 ]

2 голосов
/ 31 июля 2011

Вы всегда можете выполнить явное приведение ...

Переменная T [] закончится как Comparable [] в скомпилированном классе, поскольку T расширяет Comparable.Поэтому тип массива должен быть Comparable[] - нельзя присвоить объект Object переменной Comparable.

Другой тип массива Tree234.Node[]. 

public class Tree234<T extends Comparable<? super T>>{  
    private class Node{  
        T[] data=(T[]) new Comparable[3];  // need to be a comparable, as the superclass is known.
        Node[] next = (Node[]) new Tree234.Node[4];  

    }  
}
1 голос
/ 31 июля 2011

Помимо очевидного «просто используйте массив объектов и приведите возвращенные значения», вы также можете использовать Array.newInstance(class, size) и привести возвращенное значение к T []. Вам по-прежнему приходится подавлять предупреждения, поскольку в текущей реализации обобщений нет способа избежать этого, но таким образом вы получаете проверку типов при вставке объектов в массив, а не при обращении к ним (а более ранняя ошибка лучше в imo).

Использует отражение на заднем плане, поэтому, наверное, не самая производительная вещь в мире.

1 голос
/ 31 июля 2011

Ах, Java-массивы и дженерики, как я тебя ненавижу. Хотя использование списков определенно решит ваши проблемы с печатью, иногда скорость массива действительно необходима.

Размышление, безусловно, является выходом (ищите здесь больше), но я считаю, что это слишком вонючий код для моих вкусов. Для более простых случаев вы можете использовать что-то вроде интерфейса ArrayConstructor, который у меня есть ниже. Если бы не тип Node, мы могли бы решить вашу проблему без каких-либо предупреждений за счет увеличения детализации кода и неплотной абстракции (пользователи вашего класса должны будут предоставить конструкторы массива Node и T). К сожалению, поскольку тип узла также принимает параметр типа, мы никак не можем обработать этот случай без предупреждений. 

interface ArrayConstructor<T> {
  T[] constructArray(int size);
}

class Node <T extends Comparable<? super T>>{  
    private T[] data;
    private Node[] next;

    Node(ArrayConstructor<T> dataConstructor,
         ArrayConstructor<Node<T>> nodeConstructor){
        this.data = dataConstructor.constructArray(3);
        this.next = nodeConstructor.constructArray(4);
    }
}
0 голосов
/ 01 августа 2011

Вы должны создать new Comparable[4]. Поскольку (я полагаю) этот массив является внутренним для вашей структуры, никому на самом деле не важно, каков реальный тип массива.

Затем вы можете либо: 1) присвоить ее переменной T[], если хотите (убедитесь, что к ней не обращен внешний код, или она потерпит крах), или 2) просто вручную привести элементы к T, когда вы вытащить их. В любом случае вы получите предупреждения.

...