[Из песочницы] Структуры данных в Java — NavigableSet12.08.2014 01:18

В данной статье я хотел бы рассмотреть очень узконаправленный и редко используемый, но достаточно полезный в некоторых случаях, интерфейс NavigableSet.Интерфейс унаследован от SortedSet и расширяет методы навигации находя ближайшее совпадение по заданному значению. И сродни родительскому интерфейсу в NavigableSet не может быть дубликатов.Рассмотрим полезность и удобство применения его методов на практике.Предположим ситуацию, при которой мы имеем некий массив дробных чисел (в моем случае 6 чисел после запятой), в котором нужно производить операции поиска ближайших значений. double n0 = 0.755544; double n1 = 0.755444; double n2 = 0.755543; double n3 = 0.784554; double n4 = 0.884554; double n5 = 0.484554; Как вы можете заметить, даже в таком небольшом массиве данных, где числа отличаются лишь тысячными, при работе вручную увеличивается сложность работы с имеющимися данными, что может привести к ошибке.Методlower () — возвращает наибольший элемент в наборе, но строго меньше чём заданный если такого элемента нет, то в результате будет возвращено null.floor ()– возвращает наибольший элемент в наборе, но меньше чём заданный или равный ему, в случае отсутствия такого элемента будет возвращено null.ceiling () — возвращает ближайший элемент в наборе, но который больше или равняется заданному, в случае отсутствия такого элемента будет возвращено null.higher () — возвращает ближайший элемент в наборе, но строго больше чём заданный, в случае отсутствия такого элемента будет возвращено null.Итак, возьмем наименьшее число (n5 = 0.484554) в сете и посмотрим на поведение этих методов в работе.Код Object o = ns.lower (n5); System.out.println (o); Object o1 = ns.floor (n5); System.out.println (o1); Object o2 = ns.ceiling (n5); System.out.println (o2); Object o3 = ns.higher (n5); System.out.println (o3); В результате: null 0.484554 0.484554 0.755444

Как можно заметить что при вызове метода lower () для наименьшего числа компилятор выдал null () по причине отсутствия подходящих значений. Метод floor () вернул искомое значение в связи с отсутствием элементов, меньше чём заданный, но эквивалентное заданному числу. Методы ceiling () и higher () сработали по вышеуказанным описаниям.

Для доступа ко всем элементам набора поочередно в NavigableSet используется встроенный итератор, вывод может быть осуществлен как в порядке возрастания, так и спадания с помощью методов iterator () и descendingIterator (). Например:

Iterator iter = ns.descendingIterator ();

while (iter.hasNext ()) { System.out.print (iter.next () + » »); }

В результате в консоли получим такой результат:

0.884554; 0.784554; 0.755544; 0.755543; 0.755444; 0.484554

Создадим класс Car с имплементацией интерфейста Comparable, и переопределением метода compareTo, в данном случае сравнивающем по общему пробегу автомобиля для изучения последующих методов.

Код 4 public class Car implements Comparable { 5 private String carBrand; 6 private double displacemet; 7 private double mileage; 8 9 public Car (String carBrand, double displacemet, double mileage) { 10 this.carBrand = carBrand; 11 this.displacemet = displacemet; 12 this.mileage = mileage; 13 } 14 15 public String getCarBrand () { 16 return carBrand; 17 } 18 19 public void setCarBrand (String carBrand) { 20 this.carBrand = carBrand; 21 } 22 23 public double getDisplacemet () { 24 return displacemet; 25 } 26 27 public void setDisplacemet (double displacemet) { 28 this.displacemet = displacemet; 29 } 30 31 public double getMileage () { 32 return mileage; 33 } 34 35 public void setMileage (double mileage) { 36 this.mileage = mileage; 37 } 38 39 @Override 40 public String toString () { 41 final StringBuilder sb = new StringBuilder («Car{»); 42 sb.append («carBrand = '»).append (carBrand).append ('\''); 43 sb.append (», displacemet = »).append (displacemet); 44 sb.append (», mileage = »).append (mileage); 45 sb.append ('}'); 46 return sb.toString (); 47 } 48 49 @Override 50 public int compareTo (Car o) { 51 if (this.getMileage () < o.getMileage()) return -1; 52 if (this.getMileage() > o.getMileage ()) return 1; 53 return 0; 54 }

В методе main () создадим NavigableSet и наполним его нашими автомобилями:

Код 8 public static void main (String[] args) { 9 10 NavigableSet navigableSet = new TreeSet(); 11 12 Car car0 = new Car («Opel», 1.8, 52025); 13 Car car1 = new Car («Mersedes», 3.2, 90000); 14 Car car2 = new Car («Lada Kalina», 1.7, 300000); 15 Car car3 = new Car («Mitsubishi Lancer», 1.5, 64021); 16 Car car4 = new Car («Toyota Camry», 2.2, 51000); 17 Car car5 = new Car («Honda Accord», 2.0, 17000); 18 19 navigableSet.add (car0); 20 navigableSet.add (car1); 21 navigableSet.add (car2); 22 navigableSet.add (car3); 23 navigableSet.add (car4); 24 navigableSet.add (car5);

Метод pollFirst () –получает и удаляет из сета первый наименьший элемент (), или возвращает null в случае если сет пустой. Запустим этот метод и выведем общий набор в консоль.

Код 27 System.out.println (navigableSet.pollFirst ()); 28 29 System.out.println (»-------------------»); 30 31 Iterator iterator = navigableSet.iterator (); 32 while (iterator.hasNext ()){ 33 System.out.println (iterator.next ()); 34 }

Car{carBrand = 'Honda Accord', displacemet = 2.0, mileage = 17000.0} ------------------------------------------------------------------------------------------------ Car{carBrand = 'Toyota Camry', displacemet = 2.2, mileage = 51000.0} Car{carBrand = 'Opel', displacemet = 1.8, mileage = 52025.0} Car{carBrand = 'Mitsubishi Lancer', displacemet = 1.5, mileage = 64021.0} Car{carBrand = 'Mersedes', displacemet = 3.2, mileage = 90000.0} Car{carBrand = 'Lada Kalina', displacemet = 1.7, mileage = 300000.0}

Как видим, это автомобиль с наименьшим пробегом 17000.0, и как указано в документации к методу, он был удален из общего числа перечисленных транспортных средств.Метод pollLast () действует абсолютно противоположно предыдущему. И в случае выполнения на экране появится.Car{carBrand = 'Lada Kalina', displacemet = 1.7, mileage = 300000.0}

Вы также можете вносить изменения в метод compareTo (), или создать отдельный компаратор который будет сравнивать по другому параметру и сортировать согласно внесенным изменениям.

headSet (), возвращает данные которые меньше заданного либо равно. Например:

Код SortedSet navSet1 = navigableSet.headSet (car3); for (Object o: navSet1) { System.out.println (o); }

Car{carBrand = 'Honda Accord', displacemet = 2.0, mileage = 17000.0} Car{carBrand = 'Toyota Camry', displacemet = 2.2, mileage = 51000.0} Car{carBrand = 'Opel', displacemet = 1.8, mileage = 52025.0}

Код NavigableSet navSet2 = navigableSet.headSet (car3, true); //true указывает на то что указанный элемент должен быть включен for (Object c: navSet2) { System.out.println©; }

Car{carBrand = 'Honda Accord', displacemet = 2.0, mileage = 17000.0} Car{carBrand = 'Toyota Camry', displacemet = 2.2, mileage = 51000.0} Car{carBrand = 'Opel', displacemet = 1.8, mileage = 52025.0} Car{carBrand = 'Mitsubishi Lancer', displacemet = 1.5, mileage = 64021.0}

Хочу обратить внимание что установленная Car3 выводит меньшие элементы, согласно настройкам метода compareTo (), и это же правило действует в методах описанных ниже.tailSet () действует по такому же принципу, только возвращает данные больше заданного.subset () дает вывести вам данные согласно двум заданным границам. Используя SortedSet, будет выведено первое указанное значение и все последующие, но не последнее. С NavigableSet вывод первого и последнего регулируется флагами true or false.

Пример SortedSet navSet1 = navigableSet.subSet (car5, car3); for (Object o: navSet1) { System.out.println (o); }

Car{carBrand = 'Honda Accord', displacemet = 2.0, mileage = 17000.0} Car{carBrand = 'Toyota Camry', displacemet = 2.2, mileage = 51000.0} Car{carBrand = 'Opel', displacemet = 1.8, mileage = 52025.0}

Car{carBrand = 'Honda Accord', displacemet = 2.0, mileage = 17000.0} Car{carBrand = 'Toyota Camry', displacemet = 2.2, mileage = 51000.0} Car{carBrand = 'Opel', displacemet = 1.8, mileage = 52025.0} Car{carBrand = 'Mitsubishi Lancer', displacemet = 1.5, mileage = 64021.0}