Traktat o wyższości klawiatury

Używanie edytora vim zawsze uważałem za rodzaj białej magii. Sam program to przykład bodaj najbardziej oszczędnego interfejsu użytkownika, jaki można sobie wyobrazić – zaledwie jedna linijka tekstu na polecenia. I mimo tego, że prawie nic tam nie widać, można w edytorze zrobić prawie wszystko.
W nieco bardziej współrzędnych aplikacjach mamy na szczęście nieco bardziej rozwinięte sposoby sterowania. Paski menu, paski narzędzi (a ostatnio wzorowane na Office 2007 jakieś dziwne hybrydy tychże), dokowalne okienka opcji, gesty myszy, i tak dalej. Wszystkie opcje są więc widoczne i “doskonale dostępne”, jak zwykle twierdzą twórcy.

Mimo tych wszystkich wynalazków cały czas każdy dobrze skonstruowany program można obsługiwać najszybciej przy pomocy klawiatury. Wprawdzie polecenia tekstowe wyszły już z mody (i zbytnio mi to nie przeszkadza), ale inne narzędzia ciągle istnieją i mają się świetnie. Mówię tu o często niedocenianych przez nowicjuszy skrótach klawiaturowych.
Przyznam szczerze, że dopiero niedawno zbliżyłem się do punktu, który można nazwać w miarę sensownym wykorzystaniem potencjału tych udogodnień. Nie mówię tu rzecz jasna o takich oczywistościach jak Alt+F4 :) Chodzi mi raczej o bardziej przydatne skróty czy nawet same klawisze – jak choćby:

• Win+D, Win+R – w samym systemie operacyjnym
• Home, End, Page Up, Page Down – do poruszania się w tekście
• Shift + ew. Ctrl + strzałki – do zaznaczania
• Ctrl+(+), Ctrl +(-) – do przeskakiwania między miejscami w kodzie w Visual Studio
• F7, Ctrl+F7, F5, Ctrl+F5 – do kompilacji i uruchamiania programów w VS
• F9, F10, F11 – do debugowania w VS

Korzystanie z nich – a także z wielu innych użytecznych kombinacji – jest naprawdę bardzo wygodne. Kto wie, może jeśli sterowanie głosem stanie się doskonalsze, to przy jego wykorzystaniu w połączeniu ze skrótami (szybkość!) będziemy mogli ostatecznie pozbyć się gryzoni :) No, pomijając oczywiście gry!

Trzy rozwiązania dla relacji zawierania

Chcę dzisiaj zająć się pewną sprawą natury projektowej. Mam tu mianowicie na myśli sytuację, gdy mamy do czynienia ze zbiorem różnych elementów, wywodzących się z tej samej klasy bazowej. Najlepiej widać to będzie na odpowiednim diagramie:

Jest tu klasa kontenera (Container), która posiada m.in. zestaw różnych Elementów. Ich dokładne typy nie są i nie muszą być znane – ważne, że wywodzą się od klasy bazowej Element. W szczególności klasy Container i Element mogą być jednym i tym samym – wtedy będziemy mieli do czynienia ze strukturą hierarchiczną, reprezentującą np. drzewo węzłów dokumentu XML czy kontrolki systemu GUI. Zauważmy jeszcze, że każdy element wie o swoim właścicielu (pole Owner), czyli o pojemniku, który go zawiera (albo o elemencie nadrzędnym w przypadku drzewa).
Z obsługą już dodanych elementów nie ma zbytniego problemu, jako że wyjątkowo naturalne jest tu wykorzystanie metod wirtualnych i polimorfizmu. Kłopot polega właśnie na tworzeniu i dodawaniu nowych elementów – a ściślej na interfejsie (funkcjach i parametrach), które mają do tego służyć. I tutaj właśnie pojawiają się te trzy rozwiązania.

Rozwiązanie pierwsze polega na wyposażeniu klasy Container w garnitur metod zajmujących się tworzeniem każdego typu elementów i dodawaniem ich do zbioru. W naszym przypadku byłyby to więc funkcje AddElementA, AddElementB i AddElementC:

Jak widać w tym przypadku dobrze jest wyposażyć konstruktory klasy Element i pochodnych w parametr, przez który będziemy podawali wskaźnik do nadrzędnego kontenera lub elementu.

Drugie rozwiązanie zakłada, że pojemnik dysponuje tylko jedną ogólną metodą AddElement. Przekazujemy jej już utworzone obiekty, a jej zadaniem jest tylko dodać je do już posiadanych:

Zauważmy, że tutaj konstruktory elementów już nie przyjmują wskaźników na swoich właścicieli. Dzięki temu możemy uchronić się przed omyłkowym dodaniem elementu do innego pojemnika niż ten, który podaliśmy podczas jego tworzenia.
Skąd jednak element wie, do kogo należy?… Za to odpowiada już metoda dodająca, która modyfikuje pole określające właściciela:

Oczywiście w tym celu klasa Container musi być zaprzyjaźniona z klasą bazową Element, co na szczęście w C++ nie stanowi problemu :) (W innych językach, jak np. C# czy Java, można osiągnąć bardzo podobny efekt przy pomocy pakietów.)

W końcu trzecie wyjście przenosi cały ciężar pracy na same elementy. W tej koncepcji to elementy same się dodają do podanego pojemnika:

Żeby miało to sens, muszą być one aczkolwiek tworzone dynamicznie poprzez operator new.

Czas na nieodparcie nasuwające się pytanie, czyli… które rozwiązanie jest najlepsze? No cóż, sprawa nie jest taka prosta (inaczej bym o niej nie pisał ;D), więc może przyjrzyjmy się kilku argumentom:

• Rozwiązanie nr 1 jest dość powszechnie stosowane zwłaszcza tam, gdy elementy mają ustalone i raczej niezmienne typy. Przykładem jest wspomniane drzewko węzłów XML: tam wachlarz typów ogranicza się do tekstu, elementów XML, atrybutów, sekcji CDATA, instrukcji przetwarzania i jeszcze paru innych. Napisanie dla każdego z nich odpowiedniej metody Add* nie jest specjalnie czasochłonne.
• Trzecie rozwiązanie jest najwygodniejsze i daje najmniejsze pole manewru, jeżeli chodzi o popełnienie błędów – np. stworzenie obiektu i niedodanie go do pojemnika. Z drugiej strony może ono produkować nieintuicyjny kod. Jeżeli bowiem chcemy tylko dodać jakiś element i nie jest on nam za chwilę potrzebny, to użyjemy poniższego kodu:
  1. new ElementA(pContainer, parametry);

  Jest więc new, którego rezultat ignorujemy i tylko po dłuższym przyjrzeniu się można zauważyć, że to jednak nie jest wyciek pamięci.

• Zarówno trzecie, jak i (zwłaszcza) drugie rozwiązanie dopuszcza tworzenie elementów “wolnych”, nieprzypisanych do żadnego pojemnika. Wbrew temu co napisałem przed chwilą, taka czynność nie musi być wcale błędem. W takim przypadku odwołanie do właściciela w elemencie ustawiamy po prostu na NULL.

Cóż więc wybrać? Ostatnio skłaniam się ku drugiemu rozwiązaniu. Według mnie jest ono z tych trzech najbardziej przejrzyste – tworzenie obiektu to jedno (operator new), a jego dodawanie drugie (metoda Add). Ponadto dzieli ono pracę w miarę równo między element, jak i pojemnik – w przeciwieństwie do pozostałych modeli. I w końcu, nic w tym rozwiązaniu nie jest robione za plecami programisty, co oczywiście może być zaletą, ale i wadą oznaczającą, że przecież wszystko musimy zrobić samemu.

A zatem… kwadratura koła? W takich sytuacjach warto chyba iść na kompromis, czyli poprzeć prostokąt z zaokrąglonymi rogami ;)

Obiekty są pamiętliwe

Czasami mylne wyobrażenie o pewnych elementach języka programowania potrafi ściągnąć na nas nie lada kłopoty. Właśnie ostatnio mogłem o się o tym przekonać, a sprawa dotyczy niezbyt często wykorzystywanego elementu C++, a mianowicie placement new.

Cóż to takiego? Jest to sposób na podanie operatorowi new adresu miejsca w pamięci, który ma wykorzystać. Może to brzmieć niedorzecznie, bo przecież new ma za zadanie właśnie alokację pamięci. To jednak tylko część prawdy, bowiem ten operator wywołuje też konstruktor tworzonego obiektu. W przypadku wersji placement będzie to więc jedyna czynność, jaką wykona.
Składnia placement new wygląda mniej więcej tak:

Na czym jednak polega problem? Otóż tego specjalnego wariantu operatora new nie można wywoływać bezkarnie. W szczególności nie jest to sposób na “przezroczyste” wywołanie konstruktora dla jakiegoś obiektu.

Pytanie oczywiście brzmi: do czego było mi potrzebne użycie tego rzadkiego mechanizmu języka? No cóż, teraz już wiem, że do niczego, jednak wcześniej myślałem, że będzie to niezły sposób na wczytywanie zasobów.
W skrócie: w mojej bibliotece zasoby takie jak np. tekstury czy bufory tworzą dość prostą hierarchię dziedziczenia. Parametry niektórych z nich – jak np. tekstur – można wczytywać z pliku tekstowego – w tym przypadku chodzi chociażby o nazwę pliku graficznego z obrazkiem tekstury.
Sęk w tym, że zasób tekstury (reprezentowany przez klasę CTexture) jest też zasobem DirectX (dziedziczy po IDxResource). A z tym związane są kolejne parametry, jak np. pula pamięci czy sposób użycia zasobu (to akurat nie jest mój wymysł, tylko DirectXa ;P). One również mogą być zapisane w pliku i trzeba je uwzględnić przy wczytywaniu tekstury.

W moim “genialnym” rozwiązaniu wymyśliłem więc, że podczas tworzenia obiektu CTexture zostanie najpierw stworzony obiekt IDxResource (dzięki czemu zostanie załatwiona kwestia “DX-owych” parametrów). Następnie w tym samym miejscu pamięci – placement new! -skonstruujemy obiekt CTexture, który zajmie się załadowaniem pozostałych danych.
I to rzeczywiście działało, dopóki się nie zorientowałem, że zapomniałem dopisać do menedżera zasobów kodu, który zwalniałby wszystko przy kończeniu programu. Wtedy to w ruch poszły destruktory, a wtedy pojawiły się… przerwania systemowe informujące o uszkodzeniu sterty.

Powodem jest fakt, że obiekty (a ściślej mechanizm ich alokacji) pamiętają sposób, w jaki zostały stworzone. Jeżeli było to zwykłe new, to zniszczenie obiektu pociąga za sobą zwolnienie pamięci. Lecz jeżeli było to placement new, to operator delete zakłada, że nic nie wie o obszarze pamięci, w którym obiekt rezyduje – więc go nie zwalnia. W istocie FAQ C++ wyraźnie pisze, by przy używaniu placement new samemu wywoływać destruktor, a potem samodzielnie zwalniać pamięć.
placement new nie jest po prostu sposobem na wywołanie konstruktora – z jego użyciem wiążą się określone konsekwencje. Jak widać czasami można przekonać się o nich w mało przyjemny sposób :)

Ewolucja serwisu

Zdaje się, że ostatnio polubiłem webmajstrowanie. Podejrzewam jednak, że to stan wysoce przejściowy i dlatego lepiej by było jak najwięcej zrobić przy tej stronce, zanim przejdzie mi na to ochota ;P

Tak więc dzisiaj dodałem mnóstwo różnych gadżetów, które sprawiają, że blog coraz bardziej przypomina normalną stronę domową. Wśród nich jest chociażby to menu na górze, dające dostęp do najważniejszych działów.
Jednym z ciekawszych jest Galeria, gdzie docelowo znajdzie się miejsce na różne ładne obrazki, które jako programista gier powinienem przecież masowo produkować ;) Póki co znalazło się tam miejsce za niewielkiej kolekcji wykonanych przeze mnie screenów z gry World of Warcraft. Nie jest ich zbyt wiele, jako że generalnie jestem dość oszczędny w korzystaniu z klawisza Print Screen :) Z tych, które znalazły swoje miejsce w Galerii, chyba najbardziej reprezentatywne są te trzy:

czyli: coś śmiesznego, ładny widoczek i równie uroczy trup pewnego bossa ;]

Oprócz galerii mamy też dość standardowe działy Download i Linki. W sumie jest już chyba wszystko co na prawdziwą stronę domową przystało…

Walidacja wszerz

Dzisiaj będzie trochę algorytmicznie :) Zajmowanie się programowaniem grafiki i konstruowaniem silnika jest oczywiście satysfakcjonujące, ale programowanie to przecież nie tylko tworzenie, lecz także rozwiązywanie problemów. Dlatego czasami dobrze jest sobie jakiś problem wynaleźć i go rozwiązać :D

Dzisiejszy wprawdzie nie wziął się znikąd, jako że wynalazłem go już jakiś czas temu przeglądając część mojej biblioteki zajmującą się operacjami na łańcuchach. Zagadnienie dotyczy zaś sprawy dość przydatnej i nie tak znowu trywialnej.
Chodzi tu tzw. filtry wildcards. Jest to bardzo znany (zwłaszcza w Windows) sposób zapisywania szablonów nazw plików, przydatny zwłaszcza przy wyszukiwaniu. Jego reguły są bardzo proste: w filtrze mogą występować w dowolnej ilości dwa znaki specjalne:

• gwiazdka (*), która symbolizuje dowolny ciąg znaków (także pusty)
• znak zapytania (?), który symbolizuje dokładnie jeden dowolny znak

Oprócz tego szablon może też zawierać dowolne inne znaki, które muszą być dopasowane dosłownie. Typowe “plikowe” przykłady takich szablonów to:

• *.exe – pasuje do wszystkich nazw plików wykonywalnych (z rozszerzeniem EXE)
• file????.tmp – pasuje do file0000.tmp, file0001.tmp, ale też fileqwer.tmp, itd.
• *.? – pasuje do wszystkich nazw plików z jednoliterowym rozszerzeniem

Wildcards (swoją drogą, ciekawa nazwa – ktoś zna jej pochodzenie?) stały się na tyle popularne, że rozpoznaje je także większość wyszukiwarek internetowych. Są bowiem całkiem elastyczne, a o wiele prostsze od wyrażeń regularnych.

Jaki więc problem jest z nimi związany? Chodzi po prostu o sprawdzenie, czy podany ciąg znaków pasuje do podanego wzorca wildcards. Na pierwszy rzut oka może wydawać się to proste – niby wystarczy szukać kolejnych “części stałych” i sprawdzać, czy odstępy między nimi są odpowiednio duże. Ten algorytm jest jednak niepoprawny, bowiem czasami znaki sprawdzanego tekstu musimy traktować na różne sposoby. Przykładowo dla szablonu “a*ba” ciąg “ababa” będzie uznany za niepoprawny, gdyż algorytm dopasuje pierwsze “ba” z tekstu do “ba” zapisanego na sztywno we wzorcu zamiast potraktować je jako dowolny ciąg pasujący do gwiazdki.
Poprawne rozwiązanie musi sprawdzać wszystkie możliwe dopasowania – w tym przypadku oba wystąpienia ciągów “ba”. W swoim algorytmie dla poprawienia efektywności zastosowałem jeszcze wstępne przetwarzanie, dzielące wzorzec na fragmenty – czyli części stałe – oraz zakresy – sekwencje znaków * i ?. Samo sprawdzanie polega natomiast na znajdowaniu wszystkich wystąpień fragmentów, które są w odpowiedniej odległości od siebie (wyznaczanej przez zakresy) i dodawaniu ich do kolejki. Potem są one pobieranie i używane do znalezienia dopasowań następnego fragmentu.
Zasadniczo jest to bardzo podobne do przeszukiwania wszerz wyimaginowanego “grafu dopasowań”. Swoją drogą to ciekawe, że szkielet tego algorytmu grafowego może być użyty do tak wielu rzeczy (jak np. wyszukiwanie najkrótszej drogi między dwoma miastami (algorytm Djikstry) czy szukanie węzłów XML pasujących do wyrażenia XPath). Tak jest oczywiście dlatego, że w tych problemach zawsze wchodzi w grę jakiś mniej lub bardziej intuicyjny graf, tyle że w większości wypadków zastanawianie się nad tym, jak on wygląda, nie ma zbytniego sensu. A tak przy okazji, to w moim algorytmie wildcards można by zmienić kolejkę na stos i wszystko byłoby OK – wtedy mielibyśmy po prostu coś w stylu przeszukiwania wgłąb.

Hmm… wyszedł z tego trochę przydługi miniwykładzik ;) Pozwolę sobie jednak nie kończyć go nieodzowną kwestią “Czy są jakieś pytania” – załóżmy po prostu optymistycznie, że pytań nie stwierdzono ;)

Pora migracji

Rozpoczynając prowadzenie tego bloga w serwisie Blogger, stwierdziłem, że jest on bardzo dobrym rozwiązaniem ze względu na swoją prostotę. Ważne było to, że wszystko można tam zrobić bez grzebania w HTMLu czy jeszcze mniej przyjemnej mieszance HTML i PHP.

W końcu jednak potrzebuje się czegoś więcej. Braki Bloggera odczułem pierwszy raz wtedy, gdy zachciało mi się dołączyć do bloga krótkie opisy niektórych spośród moich produkcji. Niestety, serwis nie oferuje póki co możliwości tworzenia dodatkowych podstron, niebędących notkami.
Dlatego też (między innymi) mamy tę “drobną” rewolucję :) Obecnie blog oparty jest na WordPress – znanym i bardzo rozbudowanym mini-CMSie przeznaczonym właśnie dla tego rodzaju stron. Wygoda korzystania z niego jest właściwie taka sama jak z Bloggera – włączając to rzecz jasna niezbędny edytor działający w trybie WYSIWYG :)

Przesiadka wymagała oczywiście nieco pracy, łącznie ze sporą ilością dłubaniny w jakże ‘pięknym’ kodzie PHP+HTML. Na szczęście w ogromnej większości mam już ją za sobą, zatem teraz czeka nas już tylko świetlana przyszłość ;)

Tam, gdzie kończy się C++

Pod jednym z ostatnich postów, dotyczącym kwestii rysowania dwuwymiarowych sprite’ów, rozpętała się całkiem ciekawa dyskusja. Jej głównym tematem było to, czy i jak implementowany system 2D będzie przydatny w renderowaniu elementu niezbędnego każdej grze – choćby była do bólu trójwymiarowa. Chodzi naturalnie o graficzny interfejs użytkownika, czyli GUI.

Wyświetlanie elementów takiego interfejsu (na który składać się będą różnego rodzaju kontrolki, jak przyciski, pola tekstowe czy listy rozwijalne) to dość złożone zagadnienie. Można je rozwiązać łatwo acz nieefektywnie lub trochę trudniej, ale prawie optymalnie :) Oprócz tego GUI prezentuje sobą też bardzo poważne wyzwanie projektowe, które wymaga dokładnego zaplanowania występujących w nim klas i ich składowych.
Niestety w C++ dochodzi do tego jeszcze jeden problem, który w dodatku jest nieco krępujący. Nie lubimy się nim chwalić w towarzystwie i w sumie chcielibyśmy o nim zapomnieć, zakopać jak najgłębiej, by tylko usunąć go z pola widzenia. Ale rzeczywistość skreczy i uciekanie od kłopotu go nie rozwiąże… Trzeba wypowiedzieć go na głos. Otóż – w C++ nie ma delegatów i w związku z tym obsługa zdarzeń generowanych przez kontrolki GUI zaczyna być problemem.

‘Delegat’ to taka trochę myląca dla prostego i wręcz niezbędnego w obiektowym języku programowania mechanizmu. Delegatem nazywamy bowiem pewien rodzaj wskaźnika, który pokazuje na konkretną metodę w konkretnym obiekcie. Taki wskaźnik jest konieczny do wygodnego realizowania mechanizmu callback, czyli powiadamiania (poprzez wywołanie owej metody), że coś się zdarzyło.
W programowaniu strukturalnym nie ma z tym problemu, jako że istnieją wskaźniki na zwykłe funkcje. Najbardziej znanym jest chyba wskaźnik na procedurę zdarzeniową okna w Windows API:

Mimo pokrętnej składni, wskaźniki do funkcji dobrze spełniają swoje zadanie. Problem polega na tym, że w programowaniu obiektowym nie życzymy sobie obecności “luźnych” funkcji, skoro wszystko zamykamy w klasy. Ten rodzaj wskaźników jest więc kompletnie nieprzydatny.

C++ ma też inny rodzaj wskaźników na kod. Są to w gruncie rzeczy bardzo dziwne twory, dla których samodzielnego zastosowania póki co nie udało mi się znaleźć (co oczywiście nie znaczy, że ono nie istnieje). Te wskaźniki służą do pokazywania na metodę o danej sygnaturze, lecz nie w obiekcie, tylko w klasie. Jak już mówiłem, są to bardzo wyjątkowo nietypowe twory (C++ jest chyba jedynym językiem posiadającym coś podobnego), a towarzysząca im składnia jest zdecydowanie odpychająca.
Ten egzotyczny mechanizm można jednak użyć do implementacji własnego systemu delegatów w C++. Kiedyś nawet popełniłem artykuł wyjaśniający, jak można to zrobić. Przedstawiony tam sposób jest jednak mało elegancki i dlatego jest raczej wątpliwe, bym bo użył.

Skłaniam się raczej do zastosowania zewnętrznej biblioteki, co jest według mnie dość przykrą koniecznością. Ciężko bowiem pogodzić się z tym, że używany język programowania zmusza do uciekania się do zewnętrznych i nieustandaryzowanych rozwiązań tylko po to, by w jakiś w miarę sensowny sposób symulować to, czego mu ewidentnie brakuje. W dodatku kłóci się to z moją filozofią konstrukcji kodu “bibliotecznego” (do którego należy silnik graficzny lub silnik gry), która każe eliminować zewnętrzne powiązania. Czasem jednak stajemy pod ścianą.
Opcje są właściwie dwie. Pierwsza to użycie bibliotek Function i Bind wchodzących w skład Boosta. Mimo że Boost jest rzecz jasna świetnie opracowanym zestawem bibliotek rozszerzających C++, chciałbym jednak jej uniknąć ze względów wydajnościowych. Dokładniej chodzi o obciążenie kompilatora (z którego właściwie każda część Boosta wyciska ostatnie soki) oraz na znacznie ważniejszą kwestię wywołań delegatów w czasie wykonania programu. Dlatego skłaniam się raczej ku innej bibliotece o nazwie FastDelegate, która pod tym względem nie ma sobie równych. Być może kiedyś uda mi się napisać coś równie dobrego i będę mógł z niej zrezygnować, ale chyba bardziej prawdopodobne jest, że do tego czasu C++ będzie miał już wbudowany mechanizm delegatów :)

Mógłbym jeszcze wspomnieć o innym rozwiązaniu polegającym na użyciu polimorfizmu i funkcji wirtualnych i o tym, dlaczego w C++ – ze względu na brak niestatycznych klas wewnętrznych – byłoby ono skrajnie niewygodne. Myślę jednak, że na dzisiaj moglibyśmy już sobie tego oszczędzić :D