45

45


Одной из наиболее распространенных операций со множествами является проверка принадлежности методом contains(), но существуют и другие опера­ции, которые напомнят вам диаграммы Венна из школьного курса:



// holding/SetOperations java import java.util.*.



import static net.mindview.util.Print.*;



public class SetOperations {



public static void main(String[] args) {



Set<String> setl = new HashSet<String>(); Col 1ecti ons.addAl1(setl.



"ABCDEFGHIJK L".splitC ")). setl.addCM");



printCH " + setl containsCH"));



printCN " + setl containsCN"));



Set<String> set2 = new HashSet<String>();



Col 1 ecti ons. addAl l(set2. "H I J К L" splitC "));



print("set2 in setl- " + setl containsAll(set2));



setl.removeCH");



print("setl. " + setl);



print("set2 in setl- " + setl.containsAll(set2)); setl removeAll(set2); printCset2 removed from setl: " + setl). Collections.addAll (setl. "X Y Z".splitC ")). printC'X Y Г added to setl. " + setl);



}



} /* Output H. true N- false



set2 in setl: true



setl: [D. К. С. B. L. G. I. M. A. F. J. E] set2 in setl- false



set2 removed from setl- [D. С. B. G. M. A. F. E] 'X Y Г added to setl: [Z. D. С. B. G. M. A. F. Y. X. E] *///.-



Имена методов говорят за себя. Информацию о других методах Set можно найти в документации JDK.



Карта



Возможность отображения одних объектов на другие (ассоциация) чрезвычай­но полезна при решении широкого класса задач программирования. В качестве примера рассмотрим программу, анализирующую качество распределения класса Java Random. В идеале класс Random должен выдавать абсолютно равно­мерное распределение чисел, но чтобы убедиться в этом, необходимо сгенери­ровать большое количество случайных чисел и подсчитать их количество в раз­ных интервалах. Множества упрощают эту задачу: ключом в данном случае является число, сгенерированное при помощи Random, а значением — количест­во его вхождений:



// holding/Statistics java



// Простой пример использования HashMap



import java util *.



public class Statistics {



public static void main(String[] args) { Random rand = new Random(47). Map<Integer,Integer> m =



new HashMap<Integer.Integer>(), for(int i = 0, i < 10000. i++) {



// Получение случайного числа от 0 до 20. int г = rand nextInt(20). Integer freq = m get(r). m.put(r. freq == null ? 1 freq +1).



}



System out println(m);



}



} /* Output



{15=497. 4=481. 19=464. 8=468. 11=531, 16=533, 18=478, 3=508, 7=471, 12=521, 17=509, 2=489, 13=506, 9=549, 6=519, 1=502, 14=477, 10=513, 5=503, 0=481} *///•-



В main() механизм автоматической упаковки преобразует случайно сгенери- рованое целое число в ссылку на Integer, которая может использоваться с HashMap (контейнеры не могут использоваться для хранения примитивов). Метод get() возвращает null, если элемент отсутствует в контейнере (то есть если число было сгенерировано впервые. В противном случае метод get() воз­вращает значение Integer, связанное с ключом, и последнее увеличивается на 1 (автоматическая упаковка снова упрощает вычисления, но в действительности при этом выполняются преобразования к Integer и обратно).



Следующий пример демонстрирует поиск объектов Pet по строковому опи­санию String. Он также показывает, как проверить присутствие некоторого клю­ча или значения в Map методами containsKey() и containsValue():



// holding/PetMap java import typeinfo.pets.*, import java util *;



import static net mindview util Print *;



public class PetMap {



public static void main(String[] args) {






Map<String,Pet> petMap = new HashMap<String.Pet>(). petMap put ("My Cat", new CatCMolly")). petMap put("My Dog", new Dog("Ginger")). petMap put ("My Hamster", new HamsterCBosco")). print(petMap).



Pet dog = petMap get("My Dog"), print(dog).



print(petMap containsKeyC'My Dog")), pri nt(petMap.contai nsValue(dog)).



}



} /* Output-



{My Cat=Cat Molly. My Hamster=Hamster Bosco. My Dog=Dog Ginger}



Dog Ginger



true



true



*///•-



Map, по аналогии с массивами и Collection, легко расширяются до нескольких измерений; достаточно создать Map со значениями типа Map (причем значения­миэтихMap могут быть другие контейнеры, и даже другие Map). Контейнеры легко комбинируются друг с другом, что позволяет быстро создавать сложные структуры данных. Например, если нам потребуется сохранить информацию о владельцах сразу нескольких домашних животных, для этого будет достаточ­но создать контейнер Map<Person,List<Pet»:



//. holding/MapOfList.java package holding; import typeinfo pets.*, import java.util.*.



import static net.mindview util Print *;



public class MapOfList {



public static Map<Person. List<? extends Pet»



petPeople = new HashMap<Person. Li st<? extends Pet»();



static {



petPeople put(new PersonC'Dawn").



Arrays asList(new Cymric("Molly").new Mutt("Spot"))). petPeople put(new Person("Kate").



Arrays asList(new CatC'Shackleton"),



new Cat("Elsie May"), new DogCMargrett"))); petPeople put(new Person("Marilyn"). Arrays asList(



new Pug("Louie aka Louis Snorkel stein Dupree"). new Cat("Stanford aka Stinky el Negro"), new CatC'Pinkola"))). petPeople put(new Person("Luke").



Arrays asList(new Rat("Fuzzy"). new Rat("Fizzy"))). petPeople put(new Person("Isaac").



Arrays asList(new RatCFreckly"))).



}



public static void main(String[] args) {



print ("People- " + petPeople keySetO). printOPets: " + petPeople valuesO); for(Person person . petPeople.keySet()) { print(person + " has-"); for(Pet pet • petPeople get(person))



printC " + pet);продолжение &}



}



} /* Output



People [Person Luke, Person Marilyn. Person Isaac, Person Dawn. Person Kate] Pets [[Rat Fuzzy. Rat Fizzy], [Pug Louie aka Louis Snorkel stein Dupree. Cat Stanford aka Stinky el Negro, Cat Pinkola]. [Rat Freckly]. [Cymric Molly. Mutt Spot], [Cat Shackleton, Cat Elsie May, Dog Margrett]] Person Luke has Rat Fuzzy Rat Fizzy Person Marilyn has



Pug Louie aka Louis Snorkel stein Dupree Cat Stanford aka Stinky el Negro Cat Pinkola Person Isaac has Rat Freckly Person Dawn has. Cymric Molly Mutt Spot Person Kate has- Cat Shackleton Cat Elsie May Dog Margrett */// ~



Map может вернуть множество (Set) своих ключей, коллекцию (Collection) значений или множество (Set) всех пар «ключ-значение». Метод keySet() созда­ет множество всех ключей, которое затем используется в синтаксисе foreach для перебора Map.



ОчередьОчередьобычно представляет собой контейнер, работающий по принципу «пер­вым вошел, первым вышел»(FIFO).Иначе говоря, элементы заносятся в оче­редь с одного «конца» и извлекаются с другого в порядке их поступления. Оче­реди часто применяются для реализации надежной передачи объектов между разными областями программы.



Класс LinkedList содержит методы, поддерживающие поведение очереди, и реализует интерфейс Queue, поэтому LinkedList может использоваться в каче­стве реализации Queue. В следующем примере LinkedList повышается восходя­щим преобразованием до Queue:



//: hoiding/QueueDemo.java



// Восходящее преобразование LinkedList в Queue



import java.util.*;



public class QueueDemo {



public static void printQCQueue queue) { while(queue.peek() != null)



System out print(queue.remove() + " "), System out printin(),



}



public static void main(String[] args) {



Queue<Integer> queue = new LinkedList<Integer>();



Random rand = new Random(47); for(int i = 0; i < 10; i++)



queue.offer(rand.nextlnt(i + 10)); printQ(queue);



Queue<Character> qc = new LinkedList<Character>(); for(char с ; "Brontosaurus".toCharArrayO)



qc.offer(c); printQ(qc);



}



} /* Output;



8 1 1 1 5 14 3 1 0 1



Brontosaurus



*///;-



Метод offer(), один из методов Queue, вставляет элемент в конец очереди, а если вставка невозможна — возвращает false. Методы реек() и element() воз­вращают начальный элементбез его удаления из очереди, но реек() для пустой очереди возвращает null, a element() выдает исключение NoSuchElementException. Методы poll() и remove() удаляют и возвращают начальный элемент очереди, но poll() для пустой очереди возвращает null, a remove() выдает NoSuchElement­Exception.



Автоматическая упаковка преобразует результат int вызова nextlnt() в объект Integer, необходимый для queue, a char с — в объект Character, необхо­димый для qc. Интерфейс Queue сужает доступ к методам LinkedList так, что доступными остаются только соответствующие методы и у пользователя ос­тается меньше возможностей для вызова методов LinkedList (конечно, queue можно преобразовать обратно в LinkedList, но это создает дополнительные за­труднения).



PriorityQueue



Принцип FIFO описывает наиболее типичнуюорганизацию очереди. Именно организация очереди определяет, какой элемент будет следующим для заданно­го состояния очереди. Правило FIFO означает, что следующим элементом бу­дет тот, который дольше всего находится в очереди.



Вприоритетной очередиследующим элементом считается элемент, обладаю­щий наивысшим приоритетом. Например, в аэропорту пассажира, самолет кото­рого скоро улетит, могут пропустить без очереди. В системах обработки сообще­ний некоторые сообщения могут быть важнее других и должны обрабатываться как можно скорее, независимо от момента их поступления. Параметризованный класс PriorityQueue был добавлен в Java SE5 как механизм автоматической реали­зации этого поведения.



При помещении объекта в PriorityQueue вызовом offer() объект сортируется в очереди. По умолчанию используетсяестественный порядокпомещения объ­ектов в очередь, однако вы можете изменить его, предоставив собственную реа­лизацию Comparator. PriorityQueue гарантирует, что при вызове peek(), poll() или removeQ вы получите элемент с наивысшим приоритетом.



Создание приоритетной очереди для встроенных типов — Integer, String, Character и т. д. — является делом тривиальным. В следующем примере исполь­зуются те же значения, что и в предыдущем, но PriorityQueue выдает их в другом порядке:



//. hoiding/PriorityQueueDemo.java import java util *;



public class PriorityQueueDemo {



public static void main(String[] args) {



PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(); Random rand = new Random(47), for(int i = 0; i < 10; i++)



priorityQueue.offer(rand.nextInt(i + 10)); QueueDemo.pri ntQCpriori tyQueue);



List<Integer> ints = Arrays.asList(25, 22, 20.



18. 14. 9. 3. 1. 1, 2. 3. 9. 14, 18. 21. 23. 25); priorityQueue = new PriorityQueue<Integer>(ints); QueueDemo.pri ntQ(pri ori tyQueue); priorityQueue = new PriorityQueue<Integer>(



ints.sizeO. Collections reverseOrderO); pri ori tyQueue.addAl1(i nts). QueueDemo.pri ntQCpriori tyQueue);



String fact = "EDUCATION SHOULD ESCHEW 0BFUSCATI0N"; List<String> strings = Arrays.asList(fact.split("")); PriorityQueue<String> stringPQ =



new Pri ori tyQueue<Stri ng>(stri ngs); QueueDemo.printQ(stringPQ); stringPQ = new PriorityQueue<String>(



strings.sizeO. Col lections. reverseOrderO); stringPQ.addAl1(strings); QueueDemo.printQ(stringPQ);



Set<Character> charSet = new HashSet<Character>(); for(char с • fact toCharArray())



charSet.add(c); // Автоматическая упаковка PriorityQueue<Character> characterPQ =



new PriorityQueue<Character>(charSet); QueueDemo printQ(characterPQ).



}



} /* Output:



0   1 1 1 1 1 3 5 8 14



1   1 2 3 3 9 9 14 14 18 18 20 21 22 23 25 25 25 25 23 22 21 20 18 18 14 14 9 9 3 3 2 1 1



AABCCCDDEEEFHHIILNN0000SSSTTUUUW WUUUTTSSS0000NNLIIHHFEEEDDCCCBAA



ABCDEFH I LN0STUW *///:-



Мы видим, что дубликаты разрешены, а меньшие значения обладают более высокими приоритетами. Чтобы показать, как изменить порядок элементов по­средством передачи собственного объекта Comparator, при третьем вызове кон­структора PriorityQueue<Integer> и втором — PriorityQueue<String> используется






Comparator с обратной сортировкой, полученный вызовом Collections.reverse- Order() (одно из новшеств Java SE5).



В последней части добавляется HashSet для уничтожения дубликатов Charac­ter — просто для того, чтобы пример был чуть более интересным.



Integer, String и Character изначально работают с PriorityQueue, потому что они обладают «встроенным» естественным упорядочением. Если вы хотите исполь­зовать собственный класс с PriorityQueue, включите дополнительную реали­зацию естественного упорядочения или предоставьте собственный объект Comparator.



Collection и Iterator



Collection — корневой интерфейс, описывающий общую функциональность всех последовательных контейнеров. Его можно рассматривать как «вторичный ин­терфейс», появившийся вследствие сходства между другими интерфейсами. Кроме того, класс java.util. AbstractCollection предоставляет реализацию Collection по умолчанию, поэтому вы можете создать новый подтип AbstractCollection без избыточного дублирования кода.



Один из доводов в пользу интерфейсов заключается в том, что они позволя­ют создавать более универсальный код. Код, написанный для интерфейса, а не для его реализации, может быть применен к более широкому кругу объектов. Таким образом, если я пишу метод, которому при вызове передается Collection, этот ме­тод будет работать с любым типом, реализующим Collection, — следовательно, если новый класс реализует Collection, он будет совместим с моим методом. Од­нако интересно заметить, что стандартная библиотека С++ не имеет общего ба­зового класса для своих контейнеров — вся общность контейнеров обеспечива­ется итераторами. Казалось бы, в Java будет логично последовать примеру С++ и выражать сходство между контейнерами при помощи итераторов, а не Collection. Тем не менее эти два подхода взаимосвязаны, потому что реализация Collection также означает поддержку метода iterator():



//: hoiding/InterfaceVsIterator.java import typeinfo pets *, import java.util.*,



public class InterfaceVsIterator {



public static void display(Iterator<Pet> it) {. whileCit hasNextO) {



Pet p = it.nextO.



System out pri nt(p id() + " " + p + " ").



}



System.out.printi n();



}



public static void display(Collection<Pet> pets) { for(Pet p • pets)



System out print(p id() + " " + p + " "), System out printlnO.



}



public static void main(String[] args) {



List<Pet> petList = Pets arrayList(8).



Set<Pet> petSet = new HashSet<Pet>(petList). Map<String,Pet> petMap =



new LinkedHashMap<String.Pet>(). String[] names = ("Ralph. Eric, Robin. Lacey. " +



"Britney. Sam. Spot. Fluffy") splitC. "). for(int i = 0. i < names length. i++)



petMap.put(names[i]. petList get(i)). display(petList): display(petSet). display(petList iteratorO). displ ay (petSet iteratorO). System out println(petMap). System out. pri ntl n( petMap keySetO). displ ay (petMap valuesO). display(petMap.values О .iteratorO);



}



} /* Output-



0 Rat 1 Manx 2 Cymric 3.Mutt 4 Pug 5.Cymric 6 Pug 7 Manx 4:Pug 6 Pug 3 Mutt 1 Manx 5 Cymric 7 Manx 2:Cymric O-Rat O-Rat 1 Manx 2-Cymric 3-Mutt 4-Pug 5 Cymric 6 Pug 7 Manx 4-Pug 6 Pug 3 Mutt 1 Manx 5:Cymric 7.Manx 2 Cymric 0:Rat



{Ralph=Rat. Eric=Manx, Robin=Cymric. Lacey=Mutt. Britney=Pug. Sam=Cymric. Spot=Pug. Fluffy=Manx}



[Ralph. Eric. Robin. Lacey. Britney. Sam. Spot. Fluffy] 0:Rat l.Manx 2-Cymric 3-Mutt 4:Pug 5-Cymric 6:Pug 7 Manx 0:Rat 1 Manx 2-Cymric 3-Mutt 4.Pug 5:Cymric 6:Pug 7 Manx */// ~



Обе версии display() работают как с объектами Map, так и с подтипами Collection; при этом как Collection, так и Iterator изолируют методы display() от знания конкретной реализации используемого контейнера.



В данном случае два решения примерно равноценны. Использование Iterator становится предпочтительным при реализации постороннего класса, для которого реализация интерфейса Collection затруднена или нежелательна. Например, если мы создаем реализацию Collection наследованием от класса, со­держащего объекты Pet, нам придется реализовать все методы Collection, даже если они не будут использоваться в методе display(). Хотя проблема легко ре­шается наследованием от AbstractCollection, вам все равно придется реализо­вать iterator() вместе с size(), чтобы предоставить методы, не реализованные AbstractCollection, но используемые другими методами AbstractCollection: