Java Data Structures - NavigableSet
In this article, I would like to consider a very narrow-minded and rarely used, but quite useful in some cases, NavigableSet interface.
The interface is inherited from SortedSet and extends the navigation methods by finding the closest match by the given value. And akin to the parent interface in NavigableSet there can be no duplicates.
Consider the usefulness and convenience of applying its methods in practice.
Suppose a situation in which we have a certain array of fractional numbers (in my case, 6 numbers after the decimal point), in which we need to perform operations to search for the nearest values.
As you can see, even in such a small data array, where the numbers differ only in thousandths, when working manually, the complexity of working with existing data increases, which can lead to an error.
The
lower () method - returns the largest element in the set, but strictly less than what is specified if there is no such element, then null will be returned as a result.
floor () - returns the largest element in the set, but less than specified or equal to it, in the absence of such an element null will be returned.
ceiling () - returns the nearest element in the set, but which is greater than or equal to the specified one, in the absence of such an element, null will be returned.
higher ()- returns the nearest element in the set, but strictly more than specified, in the absence of such an element null will be returned.
So, we take the smallest number (n5 = 0.484554) in the set and look at the behavior of these methods in work.
As you can see, when calling the lower () method for the smallest number, the compiler returned null () due to the lack of suitable values. The floor () method returned the desired value due to the absence of elements, less than the given, but equivalent to the given number. The ceiling () and higher () methods worked according to the above descriptions.
To access all the elements of the set in turn, the built-in iterator is used in the NavigableSet; the output can be done in either ascending or descending order using the iterator () and descendingIterator () methods . For instance:
As a result, in the console we get the following result:
Create a Car class with the implementation of the Comparable interface and redefine the compareTo method, in this case, comparing the total mileage of the car to study the following methods.
In the main () method, create a NavigableSet and fill it with our cars:
PollFirst () method — Gets and removes the first smallest element () from the set, or returns null if the set is empty. Run this method and print the common set to the console.
As you can see, this is the car with the lowest mileage of 17000.0, and as indicated in the documentation for the method, it was removed from the total number of vehicles listed.
The pollLast () method acts exactly the opposite of the previous one. And in case of execution appears on the screen.
You can also make changes to the compareTo () method, or create a separate comparator that will compare by another parameter and sort according to the changes made.
headSet (), returns data that is less than the given or equal. For instance:
I want to note that the installed Car3 displays smaller elements, according to the settings of the compareTo () method, and the same rule applies to the methods described below.
tailSet () acts on the same principle, only returns data larger than the specified one.
subset () allows you to display data according to two given boundaries. Using SortedSet, the first specified value and all subsequent, but not the last, will be displayed. With NavigableSet, the output of the first and last is controlled by the true or false flags.
The interface is inherited from SortedSet and extends the navigation methods by finding the closest match by the given value. And akin to the parent interface in NavigableSet there can be no duplicates.
Consider the usefulness and convenience of applying its methods in practice.
Suppose a situation in which we have a certain array of fractional numbers (in my case, 6 numbers after the decimal point), in which we need to perform operations to search for the nearest values.
double n0 = 0.755544;
double n1 = 0.755444;
double n2 = 0.755543;
double n3 = 0.784554;
double n4 = 0.884554;
double n5 = 0.484554;
As you can see, even in such a small data array, where the numbers differ only in thousandths, when working manually, the complexity of working with existing data increases, which can lead to an error.
The
lower () method - returns the largest element in the set, but strictly less than what is specified if there is no such element, then null will be returned as a result.
floor () - returns the largest element in the set, but less than specified or equal to it, in the absence of such an element null will be returned.
ceiling () - returns the nearest element in the set, but which is greater than or equal to the specified one, in the absence of such an element, null will be returned.
higher ()- returns the nearest element in the set, but strictly more than specified, in the absence of such an element null will be returned.
So, we take the smallest number (n5 = 0.484554) in the set and look at the behavior of these methods in work.
The code
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
As you can see, when calling the lower () method for the smallest number, the compiler returned null () due to the lack of suitable values. The floor () method returned the desired value due to the absence of elements, less than the given, but equivalent to the given number. The ceiling () and higher () methods worked according to the above descriptions.
To access all the elements of the set in turn, the built-in iterator is used in the NavigableSet; the output can be done in either ascending or descending order using the iterator () and descendingIterator () methods . For instance:
Iterator iter = ns.descendingIterator();
while (iter.hasNext()) {
System.out.print(iter.next() + " ");
}
As a result, in the console we get the following result:
0.884554; 0.784554; 0.755544; 0.755543; 0.755444; 0.484554Create a Car class with the implementation of the Comparable interface and redefine the compareTo method, in this case, comparing the total mileage of the car to study the following methods.
The code
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 }
In the main () method, create a NavigableSet and fill it with our cars:
The code
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 () method — Gets and removes the first smallest element () from the set, or returns null if the set is empty. Run this method and print the common set to the console.
The code
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}
As you can see, this is the car with the lowest mileage of 17000.0, and as indicated in the documentation for the method, it was removed from the total number of vehicles listed.
The pollLast () method acts exactly the opposite of the previous one. And in case of execution appears on the screen.
Car{carBrand = 'Lada Kalina', displacemet = 1.7, mileage = 300000.0}You can also make changes to the compareTo () method, or create a separate comparator that will compare by another parameter and sort according to the changes made.
headSet (), returns data that is less than the given or equal. For instance:
The code
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}
The code
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}
I want to note that the installed Car3 displays smaller elements, according to the settings of the compareTo () method, and the same rule applies to the methods described below.
tailSet () acts on the same principle, only returns data larger than the specified one.
subset () allows you to display data according to two given boundaries. Using SortedSet, the first specified value and all subsequent, but not the last, will be displayed. With NavigableSet, the output of the first and last is controlled by the true or false flags.
Example
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}