Интерфейс SortedSet предназначен для создания коллекций, который хранят элементы в отсортированном виде (сортировка по
возрастанию). SortedSet расширяет интерфейс Set, поэтому такая коллекция опять же хранит только уникальные значения.
SortedSet предоставляет следующие методы:
E first(): возвращает первый элемент набора
E last(): возвращает последний элемент набора
SortedSet<E> headSet(E end): возвращает объект SortedSet, который содержит все элементы первичного набора до элемента end
SortedSet<E> subSet(E start, E end): возвращает объект SortedSet, который содержит все элементы первичного набора между элементами start и end
SortedSet<E> tailSet(E start): возвращает объект SortedSet, который содержит все элементы первичного набора, начиная с элемента start
Интерфейс NavigableSet расширяет интерфейс SortedSet и позволяет извлекать элементы на основании их значений. NavigableSet определяет следующие методы:
E ceiling(E obj): ищет в наборе наименьший элемент e, который больше obj (e >=obj). Если такой элемент найден, то он возвращается в качестве результата. Иначе возвращается null.
E floor(E obj): ищет в наборе наибольший элемент e, который меньше элемента obj (e <=obj). Если такой элемент найден, то он возвращается в качестве результата. Иначе возвращается null.
E higher(E obj): ищет в наборе наименьший элемент e, который больше элемента obj (e >obj). Если такой элемент найден, то он возвращается в качестве результата. Иначе возвращается null.
E lower(E obj): ищет в наборе наибольший элемент e, который меньше элемента obj (e <obj). Если такой элемент найден, то он возвращается в качестве результата. Иначе возвращается null.
E pollFirst(): возвращает первый элемент и удаляет его из набора
E pollLast(): возвращает последний элемент и удаляет его из набора
NavigableSet<E> descendingSet(): возвращает объект NavigableSet, который содержит все элементы первичного набора NavigableSet в обратном порядке
NavigableSet<E> headSet(E upperBound, boolean incl): возвращает объект NavigableSet, который содержит все элементы первичного набора NavigableSet до upperBound. Параметр incl при значении true, позволяет включить в выходной набор элемент upperBound
NavigableSet<E> tailSet(E lowerBound, boolean incl): возвращает объект NavigableSet, который содержит все элементы первичного набора NavigableSet, начиная с lowerBound. Параметр incl при значении true, позволяет включить в выходной набор элемент lowerBound
NavigableSet<E> subSet(E lowerBound, boolean lowerIncl, E upperBound, boolean highIncl): возвращает объект NavigableSet, который содержит все элементы первичного набора NavigableSet от lowerBound до upperBound.
Обобщенный класс TreeSet<E> представляет структуру данных в виде дерева, в котором все объекты хранятся в отсортированном виде по возрастанию.
TreeSet является наследником класса AbstractSet и реализует интерфейс NavigableSet, а следовательно, и интерфейс SortedSet.
Добавление элемента в дерево происходит медленнее, чем добавление его в хеш-таблицу HashSet, но всt равно намного быстрее, чем проверка на наличие дубликатов в массиве или связном списке.
Если дерево содержит n элементов, то для поиска правильной позиции нового элемента требуется в среднем log2n сравнений. Например, если дерево уже содержит 1000 элементов, добавление нового элемента потребует около 10 сравнений.
И поскольку TreeSet при добавлении сравнивает объекты, они должны реализовывать интерфейс Comparable. Либо необходимо предоставить объект интерфейса Comparator
при создании дерева TreeSet.
В классе TreeSet определены следующие конструкторы:
TreeSet(): создает пустое дерево
TreeSet(Collection<? extends E> col): создает дерево, в которое добавляет все элементы коллекции col
TreeSet(SortedSet <E> set): создает дерево, в которое добавляет все элементы сортированного набора set
TreeSet(Comparator<? super E> comparator): создает пустое дерево, где все добавляемые элементы впоследствии будут
отсортированы компаратором.
TreeSet поддерживает все стандартные методы для вставки и удаления элементов и ряд других методов:
boolean add(E e): Добавляет указанный элемент в этот набор, если он ещё отсутствует
boolean addAll(Collection<? extends E> c): Добавляет все элементы указанной коллекции в этот набор
E ceiling(E e): Возвращает наименьший элемент в этом наборе, больший или равный заданному, или null, если такого элемента нет
void clear(): Удаляет все элементы из этого набора
Object clone(): Возвращает поверхностную копию данного экземпляра TreeSet
Comparator<? super E> comparator(): Возвращает компаратор, используемый для упорядочивания элементов в этом наборе, или null, если набор использует естественный порядок своих элементов
boolean contains(Object o): Возвращает true, если набор содержит указанный элемент
Iterator<E> descendingIterator(): Возвращает итератор по элементам набора в порядке убывания
NavigableSet<E> descendingSet(): Возвращает обратный порядок элементов набора
E first(): Возвращает первый (самый низкий) элемент в наборе
E floor(E e): Возвращает наибольший элемент набора, меньший или равный заданному, или null, если такого элемента нет
SortedSet<E> headSet(E toElement): Возвращает представление части набора, элементы которой строго меньше toElement
NavigableSet<E> headSet(E toElement, boolean inclusive): Возвращает представление части данного множества, элементы которой меньше (или равны, если inclusive равно true) toElement
E higher(E e): Возвращает наименьший элемент в данном множестве, строго больший заданного элемента, или null, если такого элемента нет
boolean isEmpty(): Возвращает true, если в данном множестве нет элементов
Iterator<E> iterator(): Возвращает итератор по элементам данного множества в порядке возрастания
E last(): Возвращает последний (наивысший) элемент в данном множестве в данный момент
E lower(E e): Возвращает наибольший элемент в данном множестве, строго меньший заданного элемента, или null, если такого элемента нет
E pollFirst(): Извлекает и удаляет первый (наименьший) элемент или возвращает null, если данное множество пусто (необязательная операция)
E pollLast(): Извлекает и удаляет последний (самый высокий) элемент или возвращает null, если набор пуст (необязательная операция)
boolean remove(Object o): Удаляет указанный элемент из набора, если он присутствует
int size(): Возвращает количество элементов в дереве
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive): Возвращает представление части набора, элементы которой находятся в диапазоне от fromElement до toElement
SortedSet<E> subSet(E fromElement, E toElement): Возвращает представление части набора, элементы которой находятся в диапазоне от fromElement (включительно) до toElement (исключительно)
SortedSet<E> tailSet(E fromElement): Возвращает представление части данного набора, элементы которой больше или равны fromElement
NavigableSet<E> tailSet(E fromElement, boolean inclusive): Возвращает представление части данного набора, элементы которой больше (или равны, если inclusive равно true) fromElement
import java.util.TreeSet;
public class Program{
public static void main(String[] args) {
TreeSet<String> langs = new TreeSet<String>();
// добавим в список ряд элементов
langs.add("Java");
langs.add("JavaScript");
langs.add("Python");
langs.add("C++");
System.out.printf("langs size: %d \n", langs.size());
System.out.println(langs); // [C++, Java, JavaScript, Python]
// удаление элемента
langs.remove("JavaScript");
System.out.println(langs); // [C++, Java, Python]
}
}
И поскольку при вставке объекты сразу же сортируются по возрастанию, то при выводе мы получим отсортированный набор:
langs size: 4 [C++, Java, JavaScript, Python] [C++, Java, Python]
Так как TreeSet реализует интерфейс NavigableSet, а через него и SortedSet, то мы можем применить к структуре дерева различные методы для получения элементов:
import java.util.TreeSet;
import java.util.SortedSet;
import java.util.NavigableSet;
public class Program{
public static void main(String[] args) {
TreeSet<String> langs = new TreeSet<String>();
// добавим в список ряд элементов
langs.add("Java");
langs.add("JavaScript");
langs.add("Python");
langs.add("C#");
langs.add("C++");
langs.add("Go");
// сначала выводим все
System.out.println(langs); // [C#, C++, Go, Java, JavaScript, Python]
// получим первый - самый меньший элемент
System.out.println(langs.first()); // C#
// получим последний - самый больший элемент
System.out.println(langs.last()); // Python
// получим поднабор от одного элемента до другого
SortedSet<String> set = langs.subSet("Go", "Python");
System.out.println(set); // [Go, Java, JavaScript]
// элемент из набора, который идет перед JavaScript ("больше" JavaScript)
String greater = langs.higher("JavaScript"); // Python
System.out.println(greater);
// элемент из набора, который идет перед Go ("меньше" Go)
String lower = langs.lower("Go");
System.out.println(lower); // C++
// возвращаем набор элементов, которые идут перед Go
SortedSet<String> goHead=langs.headSet("Go");
System.out.println(goHead); // [C#, C++]
// возвращаем набор элементов, которые идут начиная с JavaScript
SortedSet<String> jsTail =langs.tailSet("JavaScript");
System.out.println(jsTail); // [JavaScript, Python]
// возвращаем набор в обратном порядке
NavigableSet<String> reversedSet = langs.descendingSet();
System.out.println(reversedSet); // [Python, JavaScript, Java, Go, C++, C#]
}
}