When I find something interesting and new, I post it here - that's mostly programming, of course, not everything.

Friday, June 02, 2006

Taming The Wildcard Generics

Have you ever tried to work with List<? extends Number>? You get this list from some smart program, and then try to do something with this collection. Only to find out that you cannot add anything to it. Why cannot you? You open books, you look up on Google, you go to java.sun.com, and finally you figure out that it is not a “generics bug”, but a regular, normal behavior. Here is the reason why:

Suppose some method produced an ArrayList<Integer>, and returns it disguised as List<? extends Number> - there is nothing wrong with it. But then the receiver, knowing only that it is a List of something extending Number, tries to add a Number to the list, namely, a Double – can it be legal? Of course not, because the original container expects only Integers, You cannot legally do it – some other method still expects this to be a List of Integers.

When the code is executed, all the generics information is erased, so that this kind of checking is done during compilation time. And during compilation time there seems to be no way, in the code that receives List<? extends Number>, to figure out what is the actual type of elements inside. We just do not know; all we know is that if you extract an element, you will get a superclass of Number. That’s why it is impossible to allow to add anything at all to such a list.

Interesting, right? One can easily remove elements from such a collection, but cannot add anything. You are not allowed, for List<? extends T> list to do list.add(T t) – but it is okay to remove elements from the list. The same is true for a Collection<T>, for a Map<K,V>.

I had a slightly different problem to solve: having a collection of collections, produce a virtual collection that lists all the component collections.

What does it mean that the collection is virtual? It means that no collection object exists – it may be a view into some other collection, or a class that behaves as if it contains elements, while actually it does not. Take a look at Collections.synchronizedList() – it returns a synchronized (thread-safe) list backed by the specified list. No significant amount of additional memory is allocated when you wrap a list using this method; and if the original list changes, the synchronized list will change accordingly – and vice versa.

Note that this kind of wrapper does not in any way influence the objects contained in the list – they are the same objects; the changes are in the methods that we use to access them.


The Problem



So, this is what I wanted to accomplish: having a Collection<? extends Collection<? extends T>>, produce a virtual Collection<T> - a collection that would change when components are changing, from which we could remove elements and to which we could add elements.

The desired collection should contain all the elements from the component collections; I want to be able to remove the elements (meaning, they are removed from components); I want to find a way to add elements to my resulting collection.

Note that this is not a flat collection produced from a tree represented as a collection of collections of collections, etc. Flattening happens on just one level: we had a collection of collections of type T, and produce a collection of type T.

One more natural requirement is that, when I list the elements of the resulting collection, they will be listed in a natural order: first, elements of the first component are listed, as if we were scanning the component itself, then the second one, etc., till the last element of the last component.

The functional difference between an Iterable<T> and a Collection<T> is essentially that with a Collection one can get its size and add elements. Of course, to calculate the size of a compound collection one has to add up the sizes of its components. Yes, the size can be changing while we count – but the same can happen to an ordinary collection as well, so we should not be too surprised.

A Collection<T> has actually two addition methods: add(T element) and addAll(Collection<? extends T>). Remember, the intention is to create a virtual, live collection, which means that we are not interested in making a copy of the collection passed to addAll() method. We want to use the collection itself.

But when we add an individual element, T element, we cannot add it to any original component.

It is easy to introduce a compound collection class that can shrink but cannot grow; let’s call it ShrinkingCompoundCollection. It works as described above, by scanning through individual components; deletion as I said above, is fine, but addition cannot be implemented..

The Solution



Let’s denote the original upper level collection of collections as A, and its components as Ai. Since we cannot touch neither any of Ai, nor the original collection A, we have to have two “overflow” collections. One, upper level, collection will receive all the collections that are being added using addAll() method. Let’s denote this upper level collection as B, and its components as Bk. When listing elements of the whole compound collection or calculating the size of the compound collection, we have to scan through all the Ai, and then through all the Bj.

The first component of B, Collection<T> B0, has to be added when B is created. This component will accept all individual elements added by calling add(T element).

So, we have the following structure: a collection C consisting of A and B; each one consists of “elementary” collections with elements of type either T or ? extends T. Now, have not you noticed that we have tree levels, instead of two. How do we handle this? By iteration. Let’s denote as F the operation of removing one layer of indirection, that is, the conversion of Collection<? extends Collection<? extends T>> to Collection<T>. Applying this operation to C, which is a Collection<Collection<? extends Collection<? extends T>>>, we get a Collection<Collection<? extends T>>; applying F to the resulting collection, we get the required Collection<T>.

How do we do it, if we are supposed to use a constructor? I never heard of recursive constructors yet. Well, actually we do not need much of recursion.

Watch my hands. Having a Collection<? extends Collection<? extends T>> A, and having created an “overflow” LinkedList<? extends Collection<? extends T>>, produce a collection out of these two, and pass it to a ShrinkingCollection constructor. The constructor returns a new Collection<? extends Collection<? extends T>>, the first element of which we know, it is our LinkedList.B. Add to it an “individual overflow list”, LinkedList<T> B0, and pass the resulting parameter again to super.constructor. We have built a Collection<T>, which is an instance of ShrinkingCompoundCollection<T>, and we know how to add to it collections and individual instances of T.

Q.E.D.

Две Черные Ласты

У нас в Архангельске вообще практически никто ни с кем не дрался. Я прожил там 15 лет, и не было случая, чтобы с кем-то там драться, чтобы кто-то напал. Ну разве с соседкой по парте Ниной Киселёвой, так и то – мы не друг друга мутузили, а она бросала на пол и топтала моё пальто, а я – её шапку. Чисто символически выражали свои чувства. Нет; один раз я присутствовал при драке – Лёнька Карельский с Серёгой Гермашевым поссорились из-за Сталина. Простак Лёнька сказал, что если бы Ленин был жив, то не дал бы Сталину устраивать репрессии; Серёга на это, цинично усмехнувшись, процедил, что Ленин и Сталин – едины; мы говорим Ленин – подразумеваем партия, говорим Сталин – подразумеваем тоже партия. Хоть у меня по русскому была вечная тройка, но меня слегонца бесило, когда Серёга нарочно вот так вот коверкал язык. Но не настолько меня бесило, чтобы из-за русского языка ещё драться – хватало мне дуры училки Валентины Александровны, которая даже не верила, что у Маяковского есть такое слово «земшар» - а я-то Маяковского уж всяко получше её знал. Да и ни из-за чего я не стал бы драться... ну разве если бы придурок Бармин вдруг обидел бы мою одноклассницу Валю К, так я бы вязл кирпич и убил бы его тут же, на это я был морально готов. А так драться – нет, не в моём вкусе.

А Лёнька с Серёгой как сцепились из-за Сталина, так и валялись, пыхтя и ругаясь, по школьному двору, пока совсем уж не стемнело. Я сидел на корточках и лениво уговаривал их: «кончайте вы, ребя», но кто ж в таких случаях прислушивается к голосу разума. Голос желудка – другое дело. Лёнька оголодал, вырвался из объятий Серёги, и полез через забор домой (Лёнька через забор от школы жил, так его дорога в школу и из школы в этом и состояла, в перелезании забора. А сразу за школьным забором стоял Лёнькин сарай, и в этом сарае, кстати, лежало полное собрание сочинений Сталина; мы эту гадость потом вместе с Лёнькой в школу на макулатуру стаскали – конечно, перекидывая тоже через забор.

Лёнька полез на забор, а мы с Серёгой двинулись в сторону наших домов, и Лёнька, сидя на заборе, обозвал меня предателем, потому что если я против Сталина, то не должен я с Серёгой ходить. Как будто Гермашев был за Сталина: ему просто смешна была наша глупость. Плюс, горячий астраханский характер. Серёга из Астрахани был, чердак называл «подловкой» и т.д. И своего младшего брата Вовку он иной раз бил так, что я уже был готов милицию вызывать. Не любил я Серёгу Гермашева за эти вот жестокость и цинизм; так и раздружились. В девятом классе, увидев его на остановке автобуса, я отвернулся – как и он от меня. А больше встретиться и не довелось – его застрелили через пару лет в Соломбале. Спасал кого-то от хулиганов, его и застрелили.

И кроме этой драки, ничего и не было. Мы во дворе жили себе своей жизнью, и никто никого пальцем не тронул. Люди были разного достатка – моряки, ходившие в загранку и привозившие диковинную одёжку для своих детей – а также чуингам, который, по словам наших учительниц, был вреден для организма и вызывал непрерывное слюноотделение. Жил шофёр Фёдоров с двумя глупыми дочками, погодками. Сёстры Фёдоровы любили верещать, когда их пугают, и в наши игры, «десять палочек» и «ваш чин», играть не любили. Были ещё у нас во дворе пенсионеры, один даже парализованный. Парализованный – но умный, научил нас всех делать воздушных змеев. Ну и наша вот семья тоже, не пришей не пристегни, не в квартире, как все остальные, а в отдельном домишке без газа и водопровода.

Нас соседи считали за очень бедных, и ко мне относились сочувственно. А я этой разныцы не ощущал; что с того, что у тебя телевизор дома, от этого умнее, что ли, станешь. Нет, я этого не ощущал; и городская библиотека была доступна всем, и еды тоже хватало в общем-то; хоть я, хоть Мишка Сорванов, хоть Колька Афонин - выходили иной раз на улицу с одинаковым бутербродом в виде посоленного куска свежего черного хлеба, и делились этой едой с налетавшими окружающими.

Вот этой дворовой кодлой иы и ходили летом на пляж, а иной раз и бегом бегали. В Архангельске в мои времена было три пляжа. Большой городской, тянулся километров на пять, от улицы Энгельса до яхтклуба, широкий, с хорошим песком; на нём в жаркую погоды толпился народ. Пляж с бонами, до которых в прилив было доплысть не сразу, а в отлив можно было пешком дойти. С бонов хорошо нырять. Если ловкий, то можно и на столб забраться, к которым эти боны привязаны на тросах, и со столба, с высоты метра полтора, нырять в Двину. В Двине вода летом тёплая, и течение не сильное в районе городского пляжа. Но вода мутная, видимость примерно метр; до дна надо донырнуть ещё, чтобы что-нибудь там увидеть. Особое развлечение – нырнуть с бонов и проплыть под водой до такого места, где стоять уже можно, где мелко. Кстати, срать в воду разрешалось только за бонами. Там – река унесёт. Вот ещё один повод сплавать до бонов.

Так как летом вода тёплая, то мы были избалованы, и в холодной воде купаться не тянуло. Раз только один, по инициативе шебутного Мишки Сорванова сходили в конце мая на городской пляж, искупаться среди плывущих льдин. Нет, не люблю. Кости ломит; яйца как доской прищемило. Кому нужно такое удовольствие?

Второй пляж был на месте строящегося речного вокзала, Речнухи. На Речнухе стояли горы привозного песка, настолько огромные, что зимой мы туда ходили кататься на лыжах, устраивали трамплины внизу... даже на уроках физкультуры нас туда гоняли, когда проходили катание с гор. Лыжи были главным предметом на физре, понятное дело.

На Речнухе, если честно признаться, пляжа-то никакого не было; был просто песок, была река, валялись вынесенные рекой брёвна, и выброшенные кем-то шины. То и то нам годилось – на бревне можно было прокатиться по реке, пытаясь удержаться на нём сидя; шины жгли на берегу, для жару, чтоб согреться, потому что на Речнуху ходили уже когда довольно холодно было. Дикий был пляж, эта Речнуха.

Ещё один пляж, оборудованный, но очень маленький, был у моста через Двину. Боны, выгороженная зона для плавания, вышка для ныряния. Здесь берег был очень крутой, и течение быстрое, так как место узкое. Самое узкое место Двины – восемьсот метров всего. Полмили.

Вот мы и пошли на этот пляж всей кодлой – Валерка Колодкин, Мишка Сорванов, Колька Афонин, Валерка Ожогин и его старший брат Сашка, а также Сашка Зуев. Такое количество Валерок я объяснить не в состоянии, а вот аномально высокая концентрация Сашек в первой волне бумеров объясняется просто – популярностью фильма «Александр Невский». Гордый профиль артиста Николая Черкасова, его арийская челюсть, плащ с кровавым подбоем, стальная будённовка вдохновляли вернувшихся с войны Отцов, мол, и их Сашка тоже вырастет таким. Победителем. Ожидания такого рода не всегда сбываются; некоторые из Сашек, выросши, вдруг стали Шуриками. Отцы не виноваты, виновата эпоха.

Валерка Ожогин, как и Мишка Сорванов, на год младше меня. Мне тогда нравилось это весёлое, незамороченное поколение – не то что Колька Афонин, на год старше; у Кольки в голове бродили очень странные для тех мест и того времени мысли... нынче бы – нормально, ну гомик и гомик, чё такого-то. Валерка Ожогин был мордаст и черноволос; у его брата Сашки тоже черные волосы, зачесаны гладко назад; Сашка худ, мускулист. Сашка был стилягой – только причёска не стиляжья. Иной раз, в субботу вечером, можно было его встретить в узких брючатах, с галстуком-верёвкой на пестрой «гавайской» рубахе. Про такой галстук моя тётя Лиза говорила, мол так бы и удавила этих стиляг на этих их галстуках. Не то чтобы тётя Лиза служила в обществе лимфоцитом, нет, она работала электриком на ТЭЦ – но она была передовик труда и искренне разделяла взгляды выписываемых ею журналов «Крокодил» и «Огонёк». Нет, до вступления в партию ей было далеко – во-первых, она была твёрдая христианка, во-вторых, родственники были слишком антисоветские - как соберутся два дедушки, отец и свёкор, да да как начнут «провергать коммунистов»... хоть и смеялись над дедушками, но всё ж уважали.

От Сашки Валерка Ожогин подхватывал модные иностранные песни, «рок, раунд зе клок», «твист энд шаут», и «абессамэ, абессамэ мучо» - на загадочном испанском, через много лет вдруг ставшем мне почти родным. Английский в наших местах хоть тоже был экзотикой, но встречался чаще; Лёнька Карельский ещё в третьем классе сообщил нам, что по-английски «кто отсутствует» будет «хуйзэпсэн» - и мы ждали, ухмыляясь, когда дорастём до пятого класса и услышим это своими ушами от Маргариты Иосифовны.

Да Сашку Ожогина, может быть, кто-то даже и побаивался, типа возьмёт да зарежет – такой стиляга-то! Колькина мать многое за ним подозревала. Она и за мной подозревала, что я губы крашу. Ничего семейка была. Подозревать двенадцатилетнего парня в сапогах и сером ватнике, что он губы красит!

Кодлой, конечно, весело купаться – по очереди с вышки ныряли; проплывали под водой (по течению) весь «бассейн»; ныряли по двое, под водой пугая друг друга всякими страшными жестами и рожами... У Сашки Ожогина были ласты, и он в них заныривал глубоко, до дна. У меня была маска, а ластов не было (да шутка ли, ласты стоили 7 рублей 10 копеек в магазине, чуть дешевле моего фотоаппарата, на который я два года копил, экономя на пирожках.

И вот, прыгнув с вышки в моей маске и в сашкиных ластах, я вынырнул в маске и одной ласте. Другой не было. Как бы это вам объяснить, в масштабе... Ну примерно как если у вас угнали незастрахованную машину, которую вы у приятеля взяли прокатиться.

Остаток дня я провёл, ныряя в своей маске в этот «бассейн». Не каждый раз удавалось донырнуть до дна - не хватало дыхания. Глубоко там всё-таки, метров пять; да и холодно на глубине. И темно. И эта мутная вода, которая тебя несёт над дном, пока ты по нему шаришь, пытаясь найти хоть какую-то неровность или что-нибудь тёмное... Наконец Сашка мне сказал «хватит», чтобы я перестал, что её всё равно уже не найдёшь.

Дома рассказал матери... мать дала денег, и я пошел к Ожогиным и пытался вручить им семь рублей. Зажиточная квартира, интеллигентные люди. Родителей Ожогиных я видел первый раз, и довольно-таки стеснялся. Они, конечно, никаких денег не взяли у меня – да и кто бы на их месте взял?

Это чувство, чувство отсутствущей ласты на правой ноге, чувство отчаяния, с которым ты шаришь руками по дну, в полумраке, а мутная вода сносит тебя вниз по течению, и ты пытаешься вернуться... эта густая холодая вода над серым дном, за которое я пытаюсь уцепиться, эта вода мне всё ещё снится – и я думаю, а куда же вот делась эта ласта? Куда?


Вторая ласта пропала 26 лет спустя. Моему сыну было столько, сколько мне тогда на пляже у моста.

Мы болтались по Вуоксе большой туснёй – Кротовы с детьми, Пихтины, Шура Холоимов. Наконец удалось нам добраться до моей заветной стояночки на Холмистом, на скале, где мы с Андрюшкой Кротовым даже выдолбили шлямбуром в скале канавку, чтобы вода не хастаивалась у камня, за которым мы пили чай и играли в ап-энд-даун, а стекала, и место чтобы оставалось сухим, только мох. Мы там вообще пообосновались; я даже примеривался сажать картошку и укроп на лугу на острове Фиалка, это напротив Холмистого.

В июле вода в Вуоксе теплющая; так что мы только и делали что купались. Дети ещё пытались ловить какую-то рыбу, чтоб кормить нашу знакомую чайку Чуку, но в жару рыба не особо спешит на крючок – а если попробовать рано утром, в пять часов – так это ж слишком холодно, и дураков нет вылезать из палатки мёрзнуть над неподвижной водой... так что пути наши и рыбьи не пересекались. У детей любимое место для рыбалки было – скала напротив, небольшая скала, высотой метра два – на ней можно сидеть рыбу ловить, анекдоты травить, а можно нырять, только надо знать куда, чтобы в ил не запилиться с головой: ил в нашей заводи знатный.

Дети вздумали гонять вплавь на время до скалы и обратно. К детям присоединились взрослые, начиная с Кротова. Я-то стоял на берегу и усмехался – никогда я не умел быстро плавать; я предпочитаю плыть не спеша, будь это хоть час, хоть два. А Шура – парень спортивный, и тут же присоединился к Кротову. Шура нас всех лет на десять этак моложе был. Худой, жилистый, небольшого роста, круглое лицо, весёлые карие глаза, глубокое понимание жизни и всех её поверхностных вещей; и с иронической улыбочкой ташит хоть какой тяжести рюкзак. Меня пробовал учить плавать кролем, да меня учить физкультуре – примерно как учителя физкультуры языку Лисп. Так что я стоял на бережку и засекал по часам время, рекорд 54 секунды в один конец.

Потом Шура решил ешё смерять, ну а сколько же будет если с ластами плыть; взял надел мои ласты и поплыл. И бац – свалилась с его маленькой ноги моя большая ласта, аккурат посредине между берегом и скалой. Взял я маску, стали мы с Шурой по очереди нырять. Да чего там нырять – хоть видимость и есть кое-какая, но на глубине два метра упираешься в слизистый жидкий ил, который при любом прикосновении вздымается облаком; и сколько там этого ила – неизвестно. Ну да и вода в Вуоксе только на поверхности тёплая, а там, ближе к дну – ледянющая. И ничего не нашли, конечно. Отметили только это место, мол, вот, здесь покоится чёрная ласта.

И в следующие заезды я своим гостям место показывал: так и так, мол, здесь Шура ласту утопил. А вот здесь чайка Чука жила. А здесь к нам однажды вышел беглый солдат с большим ножом и попросил перевезти на тот берег. А здесь Ник с Фаей лося как-то утром встретили. А у этого нашего камня снимались «Особенности». А здесь раньше был фарватер, теплоход ходил. А здесь когда-то избушка стояла, и в ней жил парень, и этот парень угощал нас чаем из чаги. А вот хутор Пёйлякаллио, и сосна, которую тихуанский колдун Ч назвал дубом, и намерял у этого дуба биополе - 8 метров в диаметре.

Через восемь лет Шура Холоимов умер от рака.

Ну это нам так легко говорить, мол, взял да умер. Это вот если ты, скажем, едешь по 85-й дороге в левом ряду, включил радио Пуро Мехико, да орёшь вместе с ними: Besame, besame mucho, como si fuera esta noche la ultima vez… oh shit! – и всё. Твои последние слова были «оу щит». Всё очень просто – для тебя. А с раком непросто. Сначала же надо вернуться от доктора, набраться сил, и твёрдым голосом, слегка, правда, задыхаясь, сказать: «мама, у меня рак.» Потом операция. Потом химия. Потом, после химии, облучение, рвота, облысение, тоска и бессилие. Если повезёт – без болей, а не повезёт – боли, с каждым днём всё неутолимей.

Потом койка.

Лежишь, глядишь в белый потолок.

Ждёшь.

Followers

Subscribe To My Podcast

whos.amung.us