Archive for Programming

O układaniu kontrolek

2008-05-19 20:57

Najprostszym sposobem na rozmieszczanie kontrolek w oknie programu jest oczywiście… podanie ich pozycji i rozmiarów dosłownie. Ta metoda sprawdza się dobrze jednak tylko w prostych przypadkach: gdy mamy stałą (i raczej niewielką) liczbę obiektów, gdy rozmiary okna są stałe, gdy nie dostosowujemy rozmiaru interfejsu do rozdzielczości ekranu, itd. W wielu przypadkach to jednak nie wystarcza i dlatego systemy GUI oferują też inne narzędzia pozycjonowania elementów interfejsu. Niektóre z nich są całkiem pomysłowe. Oto kilka przykładów:

  • Przykład dokowania kontrolek
    Przykład dokowania

    Dokowanie (docking), zwane też wyrównywaniem (align). Polega to na “przyklejeniu” kontrolki do którejś z krawędzi nadrzędnego pojemnika (np. okna) w jednym wymiarze oraz do obu krawędzi w wymiarze prostopadłym. Komponentowi pozostaje wówczas jeden stopień swobody. Przykładowo, kontrolka zadokowana po lewej stronie może się jedynie rozszerzać w prawo (lub zmniejszać w lewo), zaś jej górna i dolna krawędź pokrywają się zawsze z odpowiednimi krawędziami zawierającego ją pojemnika.
    Ten sposób pozycjonowania jest idealny chociażby dla pasków stanu (status bar), które zawsze umiejscowione są w dolnej krawędzi okna.

  • Ustawianie zakotwiczania
    Ustawianie zakotwiczania
    w Visual Studio

    Zakotwiczanie (anchoring) polega z kolei na ustawieniu stałej odległości pewnych krawędzi kontrolki od odpowiednich krawędzi kontrolki nadrzędnej. Domyślnie na przykład każdy komponent jest zakotwiczony z lewej i z góry. Gdy zmieniamy rozmiar zawierającego go okna, dystans między lewą krawędzią tegoż okna i lewą krawędzią kontrolki pozostaje stały; podobnie jest z górnymi brzegami. Zmieniając ustawienia zakotwiczania możemy uzyskać efekt kontrolki “wyrównanej” w podobny sposób jak tekst w edytorze, np. do prawej strony okna zamiast do lewej.
    Anchoring można uznać za nieco lepszą wersję dokowania, ale w istocie różni się on od niego dość znacznie (zwłaszcza jeśli dokujemy wiele kontrolek po jednej stronie). Jest on jednak przydatny wtedy, gdy kontrolka ma w określony sposób zmieniać rozmiar wraz z oknem.

  • Układ typu flow
    Układ typu flow

    Układy (layouts) kontrolek. Są to bardziej wyspecjalizowane narzędzia, których jedynym zadaniem jest układanie elementów interfejsu w określony sposób. Do najbardziej przydatnych należy układ typu flow oraz układ tabelkowy. Ten pierwszy polega na rozmieszczaniu kontrolek po kolei (w ustalonym porządku) tak, jak wypisuje się tekst w kolejnych wierszach. (Jak widać, analogie tekstowe w projektowaniu interfejsu pojawiają się całkiem często ;]). Z kolei układ tabelkowy, jak nazwa wskazuje, dzieli zadany obszar na wiersze i kolumny tak, że w każdej z powstałych w ten sposób komórek mieści się dokładnie jedna kontrolką i wypełnia ją całkowicie.
    Układy mają spore zastosowanie zwłaszcza wtedy, gdy rozmieszczane kontrolki są tworzone dynamicznie w trakcie działania programu. Potrafią wówczas zaoszczędzić dużo pracy z ręcznym przeliczaniem ich pozycji i/lub rozmiarów.

To stwierdzenie odnosi się zresztą do każdego z tych trzech sposobów na określanie wymiarów elementu interfejsu. Obecnie bardzo często okazuje się, że nawet stosunkowo zaawansowany układ kontrolek, który musi dostosowywać się do zmian rozmiaru okna, da się stworzyć bez obsługiwania zdarzeń typu OnResize i ręcznego rozmieszczania komponentów. A to może oszczędzić kilku kłopotów i pozwala łatwiej skoncentrować się na tych częściach programu, których wprawdzie nie widać, ale które są o wiele ważniejsze :)

Tags: , , ,
Author: Xion, posted under Programming » 1 comment

Przerywanie działania wątku

2008-05-12 21:17

Jednym z powodów używania wątków jest możliwość przerwania wykonywanych przezeń czynności właściwie w dowolnym momencie. Dzięki temu można na przykład wyposażyć aplikację okienkową w magiczny przycisk Anuluj obok paska postępu. Przez to zaś użytkownik ma wrażenie, że – nawet jeśli musi (dłuższą) chwilę zaczekać – nadal jest panem sytuacji :)
Jak można więc przerwać wątek, jeśli zachodzi taka potrzeba? Sposobów jest kilka:

  1. Najelegantszym jest sprawienie, aby zakończył się on “sam z siebie” i poczekanie na niego. Polega to na ustawieniu flagi sygnalizującej wątkowi konieczność zakończenia, którą oczywiście musi on regularnie sprawdzać. Stąd też główne pętle występujące w procedurach wątków są często w stylu while (!Terminating) { /* ... */ }. Dla porządku warto też (a w niektórych środowiskach trzeba), po ustawieniu rzeczonej flagi na wątek zaczekać. Czyni się to zwykle funkcją z join (‘złącz’) w nazwie: Thread.Join/join w .NET/Javie, pthread_join w POSIX-ie i… WaitForSingleObject w Windows API :)
  2. Jeśli wątek sporą część czasu poświęca na czekanie lub chociaż co jakiś czas przechodzi przynajmniej na krótko w stan uśpienia, wówczas można mu przerwać (interrupt). W .NET/Javie robi się to poprzez, niespodzianka, Thread.Interrupt/interrupt. Wówczas przy następnym wejściu do funkcji czekającej w rodzaju Thread.Sleep/sleep rzucany jest wyjątek (Thread)InterruptedException, który odwija stos wątku, kończąc w ten sposób jego działanie. W natywnych platformach nie może być oczywiście dokładnego odpowiednika podobnej operacji, lecz można ją symulować czekaniem na jakimś obiekcie synchronizacyjnym i sygnalizowaniem go, gdy chcemy to czekanie przerwać. W POSIX-ie funkcja pthread_cancel działa aczkolwiek w dość podobny sposób do Interrupt, pozwalając na posprzątanie zasobów w trakcie anulowania wątku.
  3. Najmniej eleganckim sposobem jest wreszcie brutalne przerwanie wątku, czyli próba jego natychmiastowego zakończenia w dowolnym momencie. Zarówno .NET, jak i Java rozwiązały to w podobny sposób: po wywoływaniu odpowiedniej metody (Thread.Abort/stop), w wątku rzucany jest bardzo specjalny wyjątek (ThreadAbortException lub ThreadDeath). Ma on tę cechę, że… przechodzi przez (prawie) wszystkie bloki catch – w .NET właściwie nie można go “zdusić”. To jednak sprawia, że taki wyjątek może wykonać po drodze wszystkie bloki finally, co pozwala zwolnić zawłaszczone zasoby i blokady oraz przywrócić obiekty synchronizujące do właściwego stanu. Występująca w Windows API funkcja TerminateThread takiej możliwości już nam nie daje, przez co jej użycie może prowadzić do różnych kłopotów.

Wnioski z tych trzech sposobów są mniej więcej takie, że pisząc kod wykonywany w osobnym wątku powinniśmy zawsze przewidzieć “czysty” sposób na jego zakończenie. Poleganie na przerywaniu lub brutalnym zakańczaniu wątków może się bowiem źle skończyć.

Tags: , ,
Author: Xion, posted under Programming » 2 comments

Potęga w 4 kilobajtach

2008-05-09 19:49
Screen z demka 4k autorstwa Charibo
Screen z demka 4k
autorstwa Charibo

Ostatnio na Warsztacie zapanował niecodzienny pęd do sceny – demosceny, rzecz jasna. Jego główną przyczyną, a może i skutkiem, jest oczywiście rozpoczynający się dzisiaj konkurs na najlepsze demo 4k. Pod tym tajemniczym skrótem kryje się maksymalny rozmiar takiego dema (co obejmuje plik wykonywalny i wszystkie wykorzystywane dane), który nie może przekroczyć granicy 4096 bajtów.
“A co można napisać na takim malutkim kawałeczku?”, pewnie chciałoby się spytać. Okazuje się, że całkiem sporo – pod warunkiem, że znamy kilka sztuczek oraz korzystamy z odpowiednich narzędzi. Jest to na przykład specjalny linker, który dokonuje wyjątkowo efektywnej kompresji wynikowego pliku. Oprócz należy też odpowiednio skonfigurować kompilator, włączając wszelkie optymalizacje rozmiaru generowanego kodu (kosztem jego szybkości) oraz pozbywając się niepotrzebnych dodatków.

Takich dodatkiem jest na przykład biblioteka czasu wykonania (runtime). Jej wykluczenie sprawia jednak, że tracimy kilka mechanizmów języka C++, jak chociażby część funkcji matematycznych. Do szczególnie dotkliwych może należeć na przykład brak operacji potęgowania w jakiejkolwiek formie – zarówno funkcji pow, jak i exp. Jeśli ich potrzebujemy, musimy sami je sobie zapewnić, co w przypadku niecałkowitego wykładnika może być kłopotliwe. Chyba że odwołamy się bezpośrednio do jednostki zmiennoprzecinkowej – na przykład tak:

  1. float pow(float a, float b)  // a^b
  2. {
  3.     __asm
  4.     {
  5.         fld1
  6.         fld a
  7.         fyl2x
  8.         fld b
  9.         fmulp ST(1), ST(0)    // na wierzchu b * log2(a)
  10.        
  11.         // obliczenie 2^(b * log2(a)), czyli a^b
  12.         fst ST(1)
  13.         frndint
  14.         fld1
  15.         fscale
  16.         fxch ST(1)
  17.         fsubr ST(0), ST(2)
  18.         f2xm1
  19.         fld1
  20.         faddp ST(1), ST(0)
  21.         fmulp ST(1), ST(0)
  22.         fstp ST(1)
  23.     }
  24. }

Samodzielnie wyprodukowanie tego kawałka nie było aczkolwiek takie proste (głównie ze względu na kłopotliwe wymagania co do argumentu instrukcji F2XM1, która dokonuje potęgowania). Dlatego prezentuję go tu dla potomności i pożytku wszystkich tworzących małe dema, licząc, że komuś może się przydać :)

Tags: , , , ,
Author: Xion, posted under Programming » 3 comments

Dynamicze tablice w C

2008-05-08 15:17

Czasem życie zmusza do pisania w sławetnym i na szczęście zanikającym już języku C. A tam nie ma chociażby takich luksusów jak STL z niezastąpionymi pojemnikami. O wszelkie struktury danych trzeba zatroszczyć się samemu, co obejmuje także tak podstawowe jak dynamiczne tablice.
Jak wiadomo, takie tablice należy samodzielnie alokować, zmieniać ich rozmiar (z kopiowaniem zawartości) oraz zwalniać, gdy nie są już potrzebne. Najwyraźniej więc wybitnie przydatne są tu funkcje malloc i free, prawda? Otóż nieprawda :)

O wiele wygodniej jest bowiem używać funkcji realloc:

  1. tab = (int*)realloc(tab, tab_size * sizeof(int));

Jej nazwa wskazuje, że jej głównym przeznaczeniem jest zmiana rozmiaru już zaalokowanego kawałka pamięci. Zazwyczaj sprowadza się to zresztą do przydzielenia nowego, skopiowania tam zawartości starej porcji i zwolnienia jej. Jednakże w dwóch szczególnych przypadkach realloc zachowuje się inaczej – zależy to od parametrów, jakie jej podamy:

  • jeżeli pierwszym parametrem będzie wskaźnik pusty (NULL), funkcja przydzieli pamięć w ilości bajtów wyrażonej drugim parametrem – czyli zachowa się jak malloc
  • jeśli zaś drugim parametrem będzie zero, to funkcja spróbuje zwolnić kawałek pamięci, na który pokazuje wskaźnik będący pierwszym parametrem – czyli zachowa się jak free

To sprawia, że możemy używać funkcji realloc w postaci wywołania podobnego jak powyżej zawsze wtedy, gdy musimy zmienić rozmiar tablicy. Można na przykład dodać do niej element w taki oto sposób:

  1. int* AddInt(int* tab, size_t* tab_size, int elem)
  2. {
  3.     int* new_tab = (int*)realloc(tab, (*tab_size + 1) *sizeof(int));
  4.     new_tab[(*tab_size)++] = elem;
  5.     return new_tab;
  6. }

Nie musimy się martwić, czy tablica została wcześniej zaalokowana czy nie. Analogicznie wygląda usuwanie elementów z końca lub początku tablicy – wówczas nie trzeba przejmować się tym, czy z tablicy coś zostanie. Tak naprawdę opakowywanie obu tych operacji w funkcje nie jest nawet specjalnie potrzebne.

Jedynym warunkiem, aby to wszystko działało, jest odpowiednie zainicjowanie wskaźnika na tablicę oraz zmiennej przechowującej jej rozmiar – co jest aczkolwiek dość oczywiste:

  1. int* tab = NULL;
  2. size_t tab_size = 0;

I to właściwie wszystko. W sumie więc nie jest to może std::vector, ale w C nie ma co wybrzydzać :)

Tags: ,
Author: Xion, posted under Programming » 2 comments

Jak nie należy używać operatorów

2008-04-30 22:23

W wielu API funkcje mają bardzo prosty sposób powiadamiania o tym, czy ich wykonanie zakończyło się sukcesem czy porażką. Albo więc wykorzystują typ bool bezpośrednio, albo wpasowują się w konwencję, iż niezerowa wartość liczbowa jest tożsama z prawdą, a zero z fałszem. To sprawia, że możliwe jest pisanie warunków podobnych do poniższego:

  1. if (!RegisterClassEx(&wc))    Error("Can't register window class.");

Ładne to i opisowe – wręcz samodokumentujące się. Ale czasami tak się zrobić nie da, bo wartości zwracane nie chcą współpracować z tym modelem.

Przykład? To większość biblioteki runtime języka C oraz API systemów uniksowych. O ile tylko rezultatem funkcji należącej do któregoś z tych dwóch zbiorów nie jest wskaźnik, konwencja informowania o powodzeniu lub niepowodzeniu jest zwykle dość osobliwa. Według niej zero oznacza sukces, natomiast porażka wykonania jest sygnalizowana przez wartość mniejszą od zera – zazwyczaj -1. Oczywiście nijak nie pasuje to sposobu interpretowania liczb jako wartości logicznych. Sprawia to, że sprawdzanie rezultatu takich funkcji może wyglądać cokolwiek enigmatycznie:

  1. if (close(fd) < 0)    perror("closing file");&#91;/cpp]
  2. Ale nie wszystko stracone :) W przypadku funkcji typu boolowskiego możemy posłużyć się operatorem logicznej negacji (<code>!</code>), dzięki czemu zawierające je <code>if</code>y są całkiem przejrzyste. Okazuje się, że z powodu pewnego zbiegu okoliczności także te wspomniane przed chwilą funkcje można potraktować tak samo... o ile dodamy jeszcze jeden operator. A dokładniej - jeśli oprócz negacji logicznej dodamy też bitową (<code>~</code>):
  3. [cpp]if (!~close(fd))    perror("closing file");

Powód, dla którego to działa, jest dość prosty. W standardowym sposobie zapisu liczb całkowitych, stosowanym na zdecydowanej większości typowych i nietypowych maszyn (zwanym uzupełnieniem do 2 – U2), wartość -1 to w zapisie binarnym same jedynki. Negując je bitowo, otrzymujemy same zera – czyli zero, a więc logiczny fałsz. A odwrotnością fałszu jest oczywiście prawda i wszystko działa poprawnie. Wygląda więc tak, jakby skromna tylda zdołała “naprawić” funkcję, by zachowywała się zgodnie z oczekiwaniami…

Tylko czy aby na pewno nowy zapis jest bardziej sugestywny? Mam nadzieję, że każdy potrafi poprawnie odpowiedzieć na to pytanie we własnym zakresie :) Na koniec jednak muszę – dla spokoju sumienia – ostrzec wszystkich: zdecydowanie nie róbcie tego w domu :D

Tags: , ,
Author: Xion, posted under Programming » 4 comments

Podział wielokątów na trójkąty

2008-04-27 21:39

Podział wypukłego wielokąta na trójkątyKolega rr- rzucił dzisiaj na kanale #warsztat ciekawy problem rysowania dowolnych wielokątów za pomocą samych trójkątów. Jak wiadomo, karty graficzne posługują się właśnie trójkątami, zatem w celu wyświetlenia wielokąta należy go odpowiednio podzielić. Matematycy dowodzą, że jest to zawsze możliwe, i podają prosty sposób dla wielokątów wypukłych: należy po prostu narysować wszystkie przekątne wychodzące z jednego wierzchołka. Nie jest trudno przełożyć ten przepis na kod.

Co jednak z dowolnymi wielokątami? Tu sprawa wydaje się bardziej skomplikowana, chociaż – jak się ukazuje – rysowanie przekątnych można na ten przypadek uogólnić. Wpadłem jednak na inny pomysł, polegający na odpowiednim “chodzeniu” po wierzchołkach naszego wielokąta i “odcinaniu” od niego kolejnych trójkątów brzegowych. Wygląda to mniej więcej tak:

  1. Startujemy od dowolnego wierzchołka wielokąta.
  2. Mając i-ty wierzchołek sprawdzamy, czy da się go połączyć z (i+2)-im (modulo liczba wierzchołków) tak, aby powstały przy tym odcinek mieścił się w wielokącie:
    • jeśli tak, to z wierzchołków: i-tego, (i+1)-ego i (i+2)-ego tworzymy nowy trójkąt, wierzchołek (i+1)-szy usuwamy z wielokąta i przechodzimy do (i+2)-ego
    • jeśli nie da się tak połączyć wierzchołków, przechodzimy do wierzchołka (i+1)-ego i próbujemy dalej
  3. Po wykonaniu pełnego cyklu kontynuujemy przechodzenie po wielokącie, usuwanie wierzchołków i tworzenie trójkątów – aż do momentu, gdy sam nasz wielokąt stanie się trójkątem. Będzie to oczywiście ostatni składający się na niego trójkąt.

Na tym rysunku można prześledzić, jak wyglądają kolejne cykle spaceru po krawędziach wielokąta – oznaczyłem je różnymi kolorami:

Podział dowolnego wielokąta na trójkąty

Z tym sposobem wiąże się oczywiście problem stwierdzenia, czy dany odcinek należy do wielokąta – co w ogólności nie musi być takie proste ani efektywne (może mieć złożoność liniową). Dodatkowo wielokąt może być “wredny” i niezbyt dobrze poddawać się operacji obcinania trójkątów. Na szczęście można udowodnić, że w każdym cyklu da się przynajmniej jeden taki trójkąt wyodrębnić. Te dwa fakty powodują, że cała operacja może mieć złożoność sięgającą nawet O(n3), chociaż pewnie da się ją zaimplementować lepiej.
Jest naturalnie bardzo możliwe, że algorytm ten jest znany od dawna, a ja po prostu nie przeczesałem Internetu dość dokładnie w poszukiwaniu już istniejącego opisu. Jednak biorąc pod uwagę to, co przed chwilą powiedziałem o jego możliwej “efektywności”, nie jest to znów takie pewne ;-) Istnieje aczkolwiek szansa, że może się on przydać komuś, kto implementuje bibliotekę graficzną 2D w oparciu o API w rodzaju DirectX czy OpenGL.

Czym jest NULL?

2008-04-24 21:42

Gdybym chciał byś złośliwy, to stwierdziłbym, że w C++ nawet ‘nic’ (czyli NULL) nie jest takie, jak być powinno. Ale ponieważ w rzeczywistości jestem wcieleniem łagodności (;]), napiszę raczej o tym, jak można zaradzić na niedogodności obecnej postaci wskaźnika pustego w C++.
Cały problem z NULL-em polega na tym, że nie jest on wartością odpowiedniego typu. Dwie klasyczne definicje tej stałej – jako 0 lub (void*)0 – mają zauważalne mankamenty. Pierwsza definiuje NULL jako liczbę, co sprawia, że dozwolone są bezsensowne podstawienia w rodzaju:

  1. int n = NULL;

Natomiast druga nie da się wprawdzie skonwertować na typ liczbowy, ale nie da się też niejawnie zmienić w wartość żadnego innego typu wskaźnikowego niż void*. A tego oczekiwalibyśmy po wskaźniku pustym. Dlatego z dwojga złego w standardzie przyjęto pierwszą definicję i NULL jest po prostu zerem.

To, czego naprawdę byśmy chcieli po NULL, to wartość 0, która:

  • może być podstawiona za dowolny typ wskaźnikowy
  • nie może być podstawiona za żaden inny typ, zwłaszcza liczbowy

To zaś da się osiągnąć, pisząc odpowiednią… klasę:

  1. #undef NULL
  2. const
  3.     class Null
  4.     {
  5.         public:
  6.             // konwersja na dowolny typ wskaźnikowy (także pointer-to-member)
  7.             template <typename T> operator T* () const { return 0; }
  8.             template <class C, typename T> operator T C::*() { return 0; }
  9.         private:
  10.             // zablokowanie pobierania adresu
  11.             void operator & () const;
  12.     }
  13. NULL;

Sztuczką są tu oczywiście szablony operatorów konwersji. Zapewniają one możliwość traktowania naszego NULL-a jako wartości dowolnego typu wskaźnikowego – łącznie ze wskaźnikami do składowych klas. A ze względu na brak innych konwersji, nie jest możliwe automatycznie przypisanie naszego pustego wskaźnika do zmiennej liczbowej.

Taki NULL jest na tyle dobry, że działa nawet z uchwytami Windows API, gdyż wewnętrznie są one zdefiniowane jako specyficzne wskaźniki. Dziwi więc, dlaczego nadal nie ma go chociażby w bibliotece standardowej C++. Najwyraźniej nawet jeśli chcemy mieć ‘nic’, trzeba się trochę napracować ;P

Tags: ,
Author: Xion, posted under Programming » 10 comments
 


© 2022 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.