Структуры данных в Java — NavigableSet

в 21:03, , рубрики: java, новичкам

В данной статье я хотел бы рассмотреть очень узконаправленный и редко используемый, но достаточно полезный в некоторых случаях, интерфейс 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<Car> { 
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<Car> navigableSet = new TreeSet<Car>(); 
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(c);                                                               
           } 

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}

           NavigableSet navSet2 = navigableSet.subSet(car5, true, car3, true); 
           for (Object c : navSet2) { 
               System.out.println(c); 
           } 

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}

Автор: electro1709

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js