Kodatnik

Wątki w Javie - podstawy

2011-06-07T00:59:00.000+02:00

Pisząc program dość często zachodzi konieczność wykonywania kilku czynności na raz (np. ściąganie plików, wyświetlanie obrazków, animacja, obsługa użytkownika). W Javie wszystkie te elementy mogą wykonywać się "jednocześnie" poprzez zastosowanie wątków.

Pierwszą czynnością przy tworzeniu wątków jest stworzenie obiektu klasy implementującej interfejs Runnable, interfejs ten ma tylko jedną metodę run(), w której zamieścimy kod naszego wątku.

public interface Runnable {
 void run();
}

Szkielet klasy implementującej interfejs Runnable:

class Watek implements Runnable {
 void run() {
  // kod, który ma zostać wywołany przez wątek
 }
}

Samo utworzenie w pełni sprawnego wątku to stworzenie obiektu klasy Thread z przekazaną do jej konstruktora referencją obiektu klasy implementującej interfejs Runnable.

Runnable obiekt = new Watek();
Thread pierwszyWatek = new Thread(obiekt);

Tak utworzony obiekt jest już pełnokrwistym wątkiem. Możemy go uruchomić za pomocą metody start() (wywołane zostanie ciało metody run()).

pierwszyWatek.start();

Spróbujmy wykorzystać naszą wiedzę do napisania prostej aplikacji, której zadaniem będzie wyświetlanie na ekranie za pomocą wątków różnych napisów. Każdy napis to osobny wątek. Ciało metody run() to pętla for, która co określoną liczbę milisekund wyświetli odpowiedni napis. Wartość opóźnienia w wyświetlaniu będzie losowana z zakresu od 0 do 2000 milisekund (pomiędzy 0 a 2 sekundami). Do losowania liczb wykorzystamy metodę rand() z klasy Math, a do zatrzymania wątku na określony czas metodę sleep() dostepną w klasie Thread. Pętla wykona się 10 razy po czym zakończy swoje zadanie, co za tym idzie wątek również zostanie zakończony (koniec metody run()).

/**
 * Wykorzystanie wątków
 * @author kodatnik.blogspot.com
 */

// klasa implementująca interfejs Runnable
class Napis implements Runnable {
 // pole napis przechowujące łańcuch tekstowy
 private String napis;

 // konstruktor klasy
 public Napis(String napis) {
  this.napis = napis;
 }

 // zaimplementowana metoda run
 public void run() {
  // pętla dziesięciokrotna
  for (int i = 0; i < 10; i++) {
   // wyświetlamy napis
   System.out.println(napis);
   try {
    // usypiamy wątek na losową liczbę milisekund (od 0 do 2000)
    Thread.sleep((int)(Math.random()*2000));
   } catch(InterruptedException e){}
   }
  }
}

// klasa tworząca i uruchamiająca wątki
public class Watki {
 public static void main(String [] args) {
  // rozpoczynamy działanie metody main()
  System.out.println("Tworzenie wątków w Javie.");
  
  // tworzymy trzy obiekty klasy napis z różnymi łańcuchami tekstowymi
  Napis napisPierwszy = new Napis("Kodatnik");
  Napis napisDrugi = new Napis("Java");
  Napis napisTrzeci = new Napis("Wątek");

  // tworzymy trzy wątki
  Thread watekPierwszy = new Thread(napisPierwszy);
  Thread watekDrugi = new Thread(napisDrugi);
  Thread watekTrzeci = new Thread(napisTrzeci);

  // uruchamiamy wątki
  watekPierwszy.start();
  watekDrugi.start();
  watekTrzeci.start();
  
  // kończymy działanie metody main() wyświetlając komunikat
  System.out.println("Metoda main(), główny wątek aplikacji, zakończyła swoje działanie.");
 }
}

Poniżej wynik działania aplikacji (za każdym razem będzie on inny). Zauważ, że metoda main() zakończyła swoje działanie od razu.

Tworzenie wątków w Javie.
Metoda main(), główny wątek aplikacji, zakończyła swoje działanie.
Kodatnik
Java
Wątek
Kodatnik
Wątek
Java
Wątek
Kodatnik
Java
Kodatnik
Java
Wątek
Kodatnik
Java
Wątek
Java
Kodatnik
Wątek
Java
Wątek
Kodatnik
Wątek
Java
Wątek
Java
Kodatnik
Kodatnik
Java
Wątek
Kodatnik
Java
Wątek
Wątek
Java
Kodatnik
Wątek
Kodatnik
Java
Kodatnik
Wątek
Java
Kodatnik
Kodatnik
Wątek
Wątek
Java
Kodatnik
Kodatnik
Kodatnik
Java
Wątek
Kodatnik
Wątek
Java
Kodatnik
Wątek
Java
Wątek
Java
Java

Możemy dodać nowe wątki z innymi napisami i sprawdzić działanie programu. Inny przykład wykorzystania wątków zaprezentowałem w poście Zegar w Swingu. W kolejnym postach zastanowimy się jak zatrzymywać wątki i jak je synchronizować.

Innym sposobem tworzenia wątków jest rozszerzenie możliwości klasy Thread. Przesłaniamy metodę run() i wątek gotowy. Ten sposób ma jednak kilka wad, jeśli nasza klasa będzie dziedziczyć z innej klasy to nie może już rozszerzać możliwości klasy Thread (dziedziczenie w Javie jest jednokrotne). Rozwiązanie z interfejsem nie narzuca nam takich ograniczeń.

Pisząc dowolny program w Javie korzystamy, nawet nie wiedząc o tym, z wątków. Każda aplikacja jest uruchamiana w Wirtualnej Maszynie Javy jako osobny wątek. Możliwe zatem jest jest wstrzymanie za pomocą metody Thread.sleep().

Java - darmowe książki i tutoriale

2011-06-06T02:24:00.001+02:00

W sieci dostępnych jest kilka darmowych pozycji książkowych dla chcących nauczyć się podstaw programowania w języku Java. Znajdziemy zarówno całe książki jak i przykładowe rozdziały (po polsku i po angielsku). Dobrze jest również znać strony z sensownymi tutorialami.

Zacznijmy od książek. Thinking in Java to to najbardziej znana i popularna książka dotycząca podstaw jak i zaawansowanych możliwości Javy. W wersji angielskiej jest ona dostępna za darmo na stronie autora: http://www.mindview.net/Books/TIJ/. Wersja polska niestety nie jest darmowa.

Kolejna pozycja w języku angielskim to dość spore opracowanie How to Think Like a Computer Scientist dostępne w formie PDF'a pod adresem: http://www.greenteapress.com/thinkapjava/thinkapjava.pdf. Książka zawiera wprowadzenie do Javy oraz kilka rozdziałów poświęconych algorytmom i strukturom danych. Bardzo ciekawą pozycją jest również Introduction to Programming in Java Roberta Sedgewicka i Kevina Wayne'a. Znajdziemy w niej interesujące przykłady jak i nieszablonowe podejście do wielu aspektów programowania (język angielski). Całość dostępna tutaj: http://introcs.cs.princeton.edu/java/home/. Inną polecaną książkę o tytule Introduction to Programming Using Java znajdziecie pod adresem: http://math.hws.edu/javanotes/. Poza wstępem do programowania autor opisuje zaawansowane struktury danych, strumienie wejścia/wyjścia jak i programowanie z wykorzystaniem graficznego interfejsu użytkownika. Pozostałe pozycje w języku angielskim to:

Data Structures and Algorithms with Object-Oriented Design Patterns in Java - http://www.brpreiss.com/books/opus5/html/book.html
Sams Teach Yourself Java 2 in 24 Hours - http://www.informit.com/library/library.aspx?b=STY_Java2_24hours
Tutorial ze strona Sun'a (teraz już Oracla) - http://download.oracle.com/javase/tutorial/
1000 Java Tips zbiór pytań i odpowiedzi - http://javaa.com/
A Guide to Modern Programming with Java - http://www.roxie.org/books/bleeding/tableofcontents.html
The Java Language Specification - http://java.sun.com/docs/books/jls/index.html
Objects and Java kilka rozdziałów - http://www.artima.com/objectsandjava/webuscript/index.html
Thinking in Patterns with Java - http://www.mindview.net/Books/TIPatterns/
Java: Classes in Java Applications - An Introduction to Java Programming - http://bookboon.com/pl/student/it/an-introduction-to-java-programming-2
Java: The Fundamentals of Objects and Classes - An Introduction to Java Programming - http://bookboon.com/pl/student/it/an-introduction-of-java-programming
Java: Graphical User Interfaces - An Introduction to Java Programming - http://bookboon.com/pl/student/it/an-introduction-to-java-programming-3
Object Oriented Programming using Java - http://bookboon.com/pl/student/it/object-oriented-programming-using-java
Introduction to Java tutorial - http://www.meshplex.org/wiki/Java/Introduction_to_Java

Po polsku wybór pozycji jest znacznie mniejszy. Większość to bardzo dobre tutoriale wprowadzajace do języka jak i również przybliżające trochę bardziej zaawansowane zagadnienia i tak:

Kurs programowania obiektowego - http://wazniak.mimuw.edu.pl/index.php?title=Programowanie_obiektowe
Zaawansowane programowanie obiektowe - http://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_projektowanie_obiektowe
Podstawy Javy - http://4programmers.net/Java/Podstawy_Javy
Java - nowy standard programowania w Internecie - http://arturt.republika.pl/java/
Kurs Javy, podstawy - http://javaprogramming.awardspace.com/index.php?pokaz=kurs

Możemy również poczytać rozdziały książek dostępnych w księgarniach internetowych np.:

Obsługa zdarzeń z książki Java - Podstawy - http://pdf.helion.pl/javpd3/javpd3-8.pdf
Aplety z książki Java - Podstawy - http://pdf.helion.pl/jv2pod/jv2pod-10.pdf
Strumienie i pliki z książki Java - Techniki zaawansowane - http://pdf.helion.pl/javtz8/javtz8-1.pdf
Wielowątkowość z ksiażki Java - Techniki zaawansowane - http://pdf.helion.pl/jv2te2/jv2te2-1.pdf
Wycieczka do Obiektowa z książki Java Rusz głową! - http://pdf.helion.pl/javrg2/javrg2-2.pdf
Wyjątki z książki Java - Efektywne programowanie - http://pdf.helion.pl/javep2/javep2-9.pdf
System wejścia-wyjścia z książki Praktyczny kurs Java - http://pdf.helion.pl/pkjav3/pkjav3.pdf
Aplikacje i aplety z książki Praktyczny kurs Java - http://pdf.helion.pl/pkjav2/pkjav2-8.pdf
Wzorzec fasada z książki Java - Wzorce projektowe - http://pdf.helion.pl/javawz/javawz-13.pdf
Typy danych zmienne i tablice z książki Java - Kompendium programisty - http://pdf.helion.pl/javakp/javakp-3.pdf
Wprowadzenie do Javy z książki Head First Java - http://pdf.helion.pl/hfjava/hfjava-1.pdf

...i jak zawsze zostaje Kodatnik ;)

Jesli znacie jakieś inne ciekawe kursy, darmowe podręczniki to dajcie znać o nich w komentarzach.

Zegar w Swingu

2011-06-05T02:29:00.000+02:00

Chcemy napisać aplikację wyświetlającą prosty zegar. Wykorzystamy do tego celu interfejs graficzny GUI czyli bibliotekę Swing oraz wątki. Całość ma być na tyle uniwersalna, aby możliwe było wykorzystanie zegara w dowolnej aplikacji.

Do naszych celów wykorzystamy klasę JLabel (standardowa etykieta tekstowa). Rozszerzymy jej możliwości wyposażając ją w obsługę wątków (zaimplementujemy interfejs Runnable). Nowa etykieta będzie co określoną liczbę milisekund zmieniała swoją treść, czyli będzie wyświetlała aktualny czas. Najprostsza wersja nowej klasy Zegar wygląda tak:

import java.awt.*;
import javax.swing.*;
import java.util.*;
import java.text.*;

/**
 * Prosty zegar w Swingu
 * @author kodatnik.blogspot.com
 */

// nowa klasa Zegar zbudowana w oparciu o klasę JLabel
class Zegar extends JLabel implements Runnable {
 // wątek
 private Thread watek;
 // liczba milisekund pauzy (1000 ms czyli 1 sekunda)
 private int pauza = 1000;

 // konstruktor klasy
 public Zegar() {
  // wyrównamy napisy do środka
  super("", SwingConstants.CENTER);
  // wybieramy font do wyświetlenia zagara (podajemy nazwę, styl oraz rozmiar)
  setFont (new Font ("Consolas", Font.BOLD, 28));
  // ustalamy kolor tła
  setBackground(Color.BLUE);
  // ustalamy kolor tekstu
  setForeground(Color.WHITE);
  // ustawiamy przeźroczystość
  setOpaque(true);
 }

 // metoda start tworzy i uruchamia wątek zegara
 public void start() {
  // jeśli nie ma działającego wątka, utwórz i uruchom nowy
  if (watek == null) {
   watek = new Thread(this);
   watek.start();
  }
 }

 // metoda wywołana po starcie wątku
 public void run() {
  // dopóki zmienna watek wskazuje na bieżący wątek
  while ( watek == Thread.currentThread()) {
   // nowy obiekt klasy Date
   Date time = new Date();
   // formatowanie
   DateFormat df = DateFormat.getTimeInstance(DateFormat.MEDIUM);
   // ustawiamy tekst
   setText(df.format(time));
   try {
    // wstrzymujemy działanie wątku na 1 sekundę
    watek.sleep(pauza);
   } catch (InterruptedException e) {}
  }
 }

 // metoda zatrzymująca zegar (wątek)
 public void stop() {
  // ustawiamy referencję watek na null
  watek = null;
 }
}

Gotowa klasa Zegar może zostać użyta w dowolnej aplikacji. Wystarczy tylko dodać ją do odpowiedniego kontenera. Sprawdźmy zatem jej działanie tworząc prostą aplikację w Swingu.

public class PrzykladowyZegar extends JFrame {

 // konstruktor
 public PrzykladowyZegar() {
  // tytuł okna
  super("Zegar w Swingu");
  // rozmiar okna
  setSize( 350, 100);
  // ustawienie domyślnej akcji przy zamykaniu okna
  setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  // ustawiamy widoczność okna
  setVisible(true);
  // nie pozwalamy zmieniać rozmiarów okna
  setResizable(false);

  // tworzymy nowy obiekt klasy Zegar
  Zegar zegar = new Zegar();
  // dodajmy go do naszego okna
  add(zegar);

  // startujemy nasz zegar
  zegar.start();
 }

 public static void main(String [] args) {
  // utworzenie obiektu i wywołanie konstruktora
  new PrzykladowyZegar();
 }
}

Całość prezentuje się w następujący sposób:

Klasa Zegar, aż prosi się o rozbudowę. Powinniśmy mieć możliwość określenia fontu, kolorów, formatu czy też strefy czasowej podczas tworzenia obiektu. Wystarczy dodać odpowiednie konstruktory i już można będzie wykorzystać kod do tworzenia stoperów czy zegarów wskazujących czas w różnych strefach czasowych.

Dodajemy przycisk +1 do Bloggera

2011-06-05T01:40:00.000+02:00

Odpowiedzią Google na Facebookowe "Lubię to" jest przycisk "+1". Możemy obdarzyć plusem strony, które nam się podobają i zwiększyć ich popularność w sieci. Oczywiście musimy być zalogowani na konto w dowolnej usłudze Google. Standardowo Blogger obsługuje nowy przycisk w domyślnych szablonach (wystarczy włączyć odpowiednią opcję). Sytuacja wygląda gorzej jeśli korzystamy z własnych szablonów.

Spróbujmy zatem zaimplementować nowość Google na naszych blogach. Potrzebujemy dwóch wpisów w szablonie bloga. Logujemy się do Bloggera, wybieramy Projekt/Edytuj kod HTML. Pierwszy wpis umieszczamy zaraz przez końcem sekcji head, szukamy (Ctrl+F) znacznika zamykającego </head> i powyżej dodajemy:

<script type="text/javascript" src="http://apis.google.com/js/plusone.js">
 {lang: 'pl'}
</script>

Parametr lang umożliwia obsługę danego języka (w naszym przypadku wybraliśmy język polski). Drugi wpis to już umieszczenie kodu samego przycisku w odpowiednim miejscu.

<g:plusone expr:href='data:post.url' size='medium'/>

Pytanie gdzie dodać ten kod. Możliwości jest kilka. Na moim blogu przycisk pojawia się zaraz przed treścią wpisu (tak samo jak przyciski facebooka i wykopu). Aby to osiągnąć znajdź w kodzie szablonu znajdź linię:

<div class='post-body entry-content'>

i wstaw powyżej tej linii kod przycisku. Jeśli nie chcesz wyświetlać przycisku na stronie głównej, a tylko przy wpisie zastosuj wyrażenie warunkowe:

<b:if cond='data:blog.pageType != "index"'>
 ...kod przycisku...
</b:if>

Efekt widoczny na moim blogu.

W kodzie przycisku możesz użyć różnych wartości parametru size: standard, small, medium i tall. Możesz również zmienić pozycjonowanie przycisku umieszczając go w divie (np. do prawej: <div style='float:right'></div>)

Gra w życie

2010-10-22T23:21:00.000+02:00

Gra w życie to przykład automatu komórkowego wymyślonego przez matematyka Johna Conwaya. Gra jest prowadzona w macierzy elementów, komórek. Każda z komórek może być żywa lub martwa. O stanie komórki w kolejnym etapie gry decyduje kilka zasad.

jeśli komórka jest martwa i ma dokładnie trzech sąsiadów żywych, staje się żywą
jeśli komórka jest żywa i ma dwóch lub trzech sąsiadów żywych, żyje dalej
jeśli komórka jest żywa i ma jednego lub mniej sąsiadów lub więcej niż trzech sąsiadów żywych, umiera (odpowiednio z samotności i przeludnienia).

Poniżej prosta implementacja Gry w życie. Podstawowym założeniem jest wykorzystanie macierzy przechowującej typ logiczny. Komórki żywe to elementy z wartościami true, a martwe z wartościami false. Po każdym etapie rozwoju wyświetlana jest plansza z aktualnym stanem naszej populacji komórek. Przejście do następnego etapu to naciśnięcie klawisza Enter, dowolny znak - koniec gry.

import java.util.Scanner;

/**
 * Prosta implementacja Gry w życie
 * @author kodatnik.blogspot.com
 */
public class GraWZycie {

 // stałe symbolizujące żywą i martwą komórkę
 private final char ZYWA = '#';
 private final char MARTWA = '.';
 // pola przechowujące rozmiar naszej planszy
 private int wiersze;
 private int kolumny;
 // deklaracja macierzy z planszą gry
 private boolean[][] plansza;

 // konstruktor, podajemy liczbę wierszy i kolumn planszy
 public GraWZycie(int wiersze, int kolumny) {
  // inicjalizujemy pola naszej klasy
  this.wiersze = wiersze;
  this.kolumny = kolumny;
  // tworzymy odpowiednią macierz, domyślnie wypełniona jest ona wartościami false
  plansza = new boolean[wiersze][kolumny];
 }

 // metoda pokazująca planszę na ekranie
 public void pokazPlansze(){
  // wyświetlamy każdy element planszy, w zależności od zawartości na ekranie pojawi się odpowiedni znak
  for(boolean wiersz[] : plansza){
   for(boolean element : wiersz)
    System.out.print((element) ? ZYWA : MARTWA);
   System.out.println();
  }
 }

 // przykładowa metoda uzupełniająca planszę populacją początkową
 public void utworzDaneTestowe() {
  // tworzymy populację początkową (standardowy Exploder)
  plansza[5][5] = true; plansza[5][7] = true; plansza[5][9] = true;
  plansza[6][5] = true; plansza[6][9] = true;
  plansza[7][5] = true; plansza[7][9] = true;
  plansza[8][5] = true; plansza[8][9] = true;
  plansza[9][5] = true; plansza[9][7] = true; plansza[9][9] = true;
 }

 // metoda zwraca liczbę żywych sąsiadów konkretnej komórki
 // w wywołaniu podajemy współrzędne komórki
 private int liczbaSasiadow(int x, int y) {

  // zmienna przechowująca liczbę sąsiadów
  int sasiedzi = 0;

  // sprawdzamy komórki na około naszej
  for(int i = x-1; i <= x+1; i++) {
   // jeżeli przekraczamy zakres planszy (wiersz) idziemy dalej
   if(i < 0 || i > wiersze-1) continue;
   for(int j = y-1; j <= y+1; j++) {
    // jeżeli przekraczamy zakres planszy (kolumna), lub jesteśmy w komórce(x,y) idziemy dalej
    if(j < 0 || j > kolumny-1 || (i == x && j == y)) continue;
    // jeśli sąsiad jest żywy to zwiększamy naszą zmienną
    if(plansza[i][j]) sasiedzi++;
   }
  }
  // zwracamy zmienną
  return sasiedzi;
 }

 // metoda sprawdza czy dana komórka będzie żywa czy też martwa w następnym etapie
 // w wywołaniu podajemy współrzędne komórki
 private boolean ewolucja(int x, int y) {

  // sprawdzamy liczbę żywych sąsiadów
  int sasiedzi = liczbaSasiadow(x, y);

  // jeżeli nasza komórka jest żywa
  if(plansza[x][y]) {
   // jeśli liczba sąsiadów jest mniejsza lub równa jeden lub większa od trzech to nasza komórka będzie martwa
   if(sasiedzi <= 1 || sasiedzi > 3) return false;
   // jeśli liczba sąsiadów jest równa trzy lub dwa to nasza komórka będzie żywa
   if(sasiedzi == 3 || sasiedzi == 2) return true;
  } else {
   // jeśli nasza komórka jest martwa i ma dokładnie trzech żywych sąsiadów to będzie żyła
   if(sasiedzi == 3) return true;
  }
  // w każdym innym przypadku zwracamy fałsz (komórka jest martwa)
  return false;
 }

 // metoda tworzy następną populację/pokolenie komórek
 public void nastepnePokolenie() {
  // tworzymy planszę tymczasową o takim samy rozmiarze jak nasza
  boolean[][] planszaTymczasowa = new boolean[wiersze][kolumny];

  // uzupełniamy nową planszę wartościami na podstawie ogólnych zasad
  for(int i = 0; i < wiersze; i++)
   for(int j = 0; j < kolumny; j++) 
    planszaTymczasowa[i][j] = ewolucja(i, j);

  // nasza główna plansza staje się planszą tymczasową
  plansza = planszaTymczasowa;
 }

 public static void main(String[] args) {

  // wyświetlamy napisy informacyjne
  System.out.println("Gra w życie - [Enter] generuje następne pokolenie, dowolny znak i [Enter] kończy grę.");

  // obsługujemy wejście
  Scanner sc = new Scanner(System.in);

  // tworzymy nowy obiekt przekazując do konstruktora rozmiar planszy
  GraWZycie gra = new GraWZycie(15, 15);
  // wypełniamy naszą planszę wartościami testowymi
  gra.utworzDaneTestowe();
  // wyświetlamy planszę na ekranie
  gra.pokazPlansze();

  // dopóki użytkownik będzie naciskał klawisz Enter
  while(sc.nextLine().equals("")) {
   // generujemy następne pokolenie
   gra.nastepnePokolenie();
   // wyświetlamy go na ekranie
   gra.pokazPlansze();
  }
 }
}

Pojawianie się następnych etapów naszej populacji może odbywać się automatycznie (bez konieczności naciskania klawisza Enter). Poniżej zmodyfikowana wersja pętli while z metody main. Mankamentem tego rozwiązania jest to, iż zakończenie programu odbywa się jedynie poprzez jego przerwanie np. za pomocą kombinacji Ctrl+C.

while(true) {
 gra.nastepnePokolenie();
 gra.pokazPlansze();
 try {
  Thread.sleep(300); // długość pauzy w milisekundach
 } catch (Exception e) {}
}

Uruchomiona aplikacja, początkowa populacja:

Gra w życie - [Enter] generuje następne pokolenie, dowolny znak i [Enter] kończy grę.
...............
...............
...............
...............
...............
.....#.#.#.....
.....#...#.....
.....#...#.....
.....#...#.....
.....#.#.#.....
...............
...............
...............
...............
...............

Populacja w następnych etapach:

...............
...............
...............
...............
...............
......#.#......
....##...##....
....###.###....
....##...##....
......#.#......
...............
...............
...............
...............
...............

...............
...............
...............
...............
...............
.....#...#.....
....#.....#....
...#..#.#..#...
....#.....#....
.....#...#.....
...............
...............
...............
...............
...............

Gra wygląda znacznie lepiej w środowisku graficznym ;)

Projekt Euler - Problem numer 1

2010-09-15T23:38:00.001+02:00

Projekt Euler (http://projecteuler.net) to strona internetowa zawierająca pokaźny zbiór (ponad 300) problemów obliczeniowych, do rozwiązania których potrzebny jest (w większości przypadków) komputer oraz dowolny język programowania. Rozwiązaniem każdego zadania jest wynik, który podajemy, aby sprawdzić czy nasz sposób obliczeń jest poprawny. Oczywiście sednem zabawy jest opracowanie odpowiedniego dla danego problemu algorytmu. Przyjrzyjmy się zatem pierwszemu zadaniu.

Weźmy wszystkie liczby naturalne mniejsze od 10, które są wielokrotnościami liczb 3 lub 5. Otrzymamy liczby: 3, 5, 6, 9. Ich suma wynosi 25. Znajdź sumę wielokrotności liczb 3 lub 5 mniejszych od 1000.

Najprostszy z możliwych algorytm powinien sprawdzić wszystkie liczby z podanego zakresu oraz zsumować tylko te, które są wielokrotnościami liczb 3 lub 5.

/**
 * Projekt Euler - Problem nr 1
 * @author kodatnik.blogspot.com
 */
public class PEProblem1 {
 public static void main(String args[]) {
  // zmienna przechowująca sumę
  int suma = 0;

  // pętla dla liczb naturalnych mniejszych od 1000 (zaczynamy od 3)
  for(int i = 3; i < 1000; i++)
   // jeśli liczba jest podzielna przez 3 lub 5 dodajemy ją do sumy
   if((i % 3 == 0) || (i % 5 == 0))
    suma += i;
        
  //wyświetlamy wynik
  System.out.println("Suma wynosi: " + suma);
 }
}

Otrzymany wynik to:

Suma wynosi: 233168

Pozostaje kwestia optymalizacji algorytmu. Czy można prościej, szybciej? Oczywiście. Pytanie tylko czy dla górnego zakresu (1000) jest to opłacalne?

Odległość Levenshteina - podobieństwo łańcuchów

2010-06-17T00:22:00.001+02:00

Do obliczania podobieństwa łańcuchów tekstowych wykorzystuje się algorytm Levenshteina (Vladimir Levenshtein - rosyjski uczony), znany również jako odległość edycyjna, albo odległość Levenshteina. Otrzymana w wyniku działania algorytmu liczba symbolizuje ile działań prostych musimy wykonać, aby dokonać konwersji/zamiany jednego łańcucha na drugi. Działania proste to wstawienie znaku, usunięcie znaku oraz zamiana znaku na inny. Dla łańcucha "kot" i "kod" odległość edycyjna wynosi 1. Musimy dokonać tylko jednej zamiany znaku. Im większa odległość tym bardziej różne są łańcuchy znaków.

Jak działa sam algorytm:

ustalamy długość łańcuchów znaków (dlugoscP - długość łańcucha pierwszego, dlugoscD - długość łańcucha drugiego),
tworzymy macierz o rozmiarze (dlugoscP+1) x (dlugoscD+1),
inicjalizujemy pierwszy wiersz wartościami od 0 do dlugoscP,
inicjalizujemy pierwszą kolumnę wartościami od 0 do dlugoscD,
sprawdzamy każdy znak z łańcucha pierwszego (indeks i od 1 do dlugoscP),
sprawdzamy każdy znak z łańcucha drugiego (indeksy j od 1 do dlugoscD),
jeżeli znak na pozycji i równa się znakowi na pozycji j to koszt jest równy zero,
jeżeli znak na pozycji i jest różny od znaku na pozycji j to koszt wynosi 1,
ustawiamy wartość komórki i,j jako minimum:

komórka powyżej + 1,
komórka z lewej + 1,
komórka po skosie (góra, lewo) + koszt.

algorytm powtarzamy dla wszystkich znaków, całkowity koszt otrzymamy w komórce o indeksie dlugoscP, dlugoscD

Sprawdźmy działanie algorytmu na przykładzie dwóch łańcuchów: "notatnik" i "kodatnik". Poniżej utworzona została macierz i obliczone zostały odpowiednie wartości komórek.

n o t a t n i k
0 1 2 3 4 5 6 7 8
k 1 1 2 3 4 5 6 7 7
o 2 2 1 2 3 4 5 6 7
d 3 3 2 2 3 4 5 6 7
a 4 4 3 3 2 3 4 5 6
t 5 5 4 3 3 2 3 4 5
n 6 5 5 4 4 3 2 3 4
i 7 6 6 5 5 4 3 2 3
k 8 7 7 6 6 5 4 3 2

Odczytana odległość edycyjna wynosi zatem 2 (wartość komórki o indeksie [8][8]). Dodatkowo możemy określić podobieństwo wyrazów stosując następujący wzór:

1 / (1 + OL)

gdzie OL to odległość Levenshteina dla dwóch łańcuchów obliczona zgodnie z powyższym algorytmem. Dla naszego przykładu podobieństwo wynosi: 1/3.

Poniżej prosty program liczący odległość Levenshteina oraz podobieństwo łańcuchów.

import java.util.Scanner;

/**
 * Obliczanie odległości Levenshteina (odległości edycyjnej)
 * Wyznaczanie podobieństwa łancuchów znaków
 * @author kodatnik.blogspot.com
 */
public class Levenshtein {

 public static int obliczOdleglosc(String p, String d) {
  // określamy długości łańcuchów znaków
  int dlugoscP = p.length();
  int dlugoscD = d.length();

  // tworzymy odpowiednią macierz
  int[][] macierz = new int[dlugoscP + 1][dlugoscD + 1];

  // uzupełniamy pierwszy wiersz i pierwszą kolumnę
  for(int i = 0; i <= dlugoscP; macierz[i][0] = i++);
  for(int j = 1; j <= dlugoscD; macierz[0][j] = j++);

  // sprawdzamy poszczególne znaki
  for(int i = 1; i <= dlugoscP; i++) {
   char znak = p.charAt(i - 1);
   for(int j = 1; j <= dlugoscD; j++) {
    // obliczamy koszt
    int koszt = macierz[i - 1][j - 1];
    if(d.charAt(j - 1) !=  znak ) koszt++;
    // wstawiamy minimum
    macierz[i][j] = Math.min( Math.min( macierz[i - 1][j] + 1, macierz[i][j - 1] + 1), koszt);
   }
  }
  // zwracamy całkowity koszt, odległość Levenshteina
  return macierz[dlugoscP][dlugoscD];
 }

 public static double obliczPodobienstwo(String lancuchPierwszy, String lancuchDrugi) {
  // obliczamy i zwracamy podobieństwo łańcuchów
  return (1.0/(1.0 + obliczOdleglosc(lancuchPierwszy, lancuchDrugi)));
 }

 public static void main(String[] args) {
  String lancuchPierwszy, lancuchDrugi;

  // pobieramy dane
  Scanner wejscie = new Scanner(System.in);
  System.out.print("Podaj pierwszy ciąg znaków: ");
  lancuchPierwszy = wejscie.nextLine();
  System.out.print("Podaj drugi ciąg znaków: ");
  lancuchDrugi = wejscie.nextLine();

  // wyświetlamy obliczone wyniki
  System.out.println("Odległość Levenshteina: " + obliczOdleglosc(lancuchPierwszy, lancuchDrugi));
  System.out.println("Podobieństwo ciągów znaków: " + obliczPodobienstwo(lancuchPierwszy, lancuchDrugi));
 }
}

Wynik działania programu dla przykładowych danych.

Podaj pierwszy ciąg znaków: notatnik
Podaj drugi ciąg znaków: kodatnik
Odległość Levenshteina: 2
Podobieństwo ciągów znaków: 0.3333333333333333

Praktyczne wykorzystanie algorytmu to między innymi sprawdzanie pisownii, rozpoznawanie mowy, analiza DNA, wykrywanie plagiatów itp.

Algorytm Luhna

2010-04-17T00:37:00.001+02:00

Algorytm Luhna (autor: Hans Peter Luhn - naukowiec z IBM) jest najczęściej wykorzystywanym sposobem sprawdzenia poprawności ciągu liczb. Jego zastosowanie to sprawdzanie numerów kart kredytowych i innych np. lojalnościowych, numerów IMEI, numerów ubezpieczeń itd. Algorytm działa na pojedynczych cyfrach od prawej do lewej strony sprawdzanej liczby. Sam schemat jest bardzo prosty i sprowadza się do kilku kroków:

sumujemy cyfry nieparzyste (pierwszą, trzecią, piąta itd.),
podwajamy cyfry parzyste (drugą, czwartą, szóstą itd.), jeśli podwojona wartość jest większa od 9, sumujemy cyfry (np. podwajamy 8, dostajemy 16, wartość większa od 9, sumujemy cyfry 1+6, dostajemy wynik 7),
sumujemy otrzymane cyfry z kroku drugiego,
dodajemy dwie sumy (dla cyfr parzystych i nieparzystych), jeśli wynik modulo 10 daje 0 to liczba jest poprawna, w przeciwnym przypadku niepoprawna.

Przeanalizujmy algorytm na prostym przykladzie. Mamy numer karty: 4853928344613904. Poruszamy się od prawej do lewej strony. Obliczamy sumę cyfr nieparzystych:

sumaNieparzystych = 4 + 9 + 1 + 4 + 3 + 2 + 3 + 8 = 34

Obliczamy sumę podwojonych cyfr parzystych (jeśli podwojona wartość jest większa od 9 dodajemy poszczególne cyfry):

sumaParzystych = 0 + 6 + (1+2) + 8 + (1+6) + (1+8) + (1+0) + 8 = 42

Dodajemy otrzymane wyniki:

sumaParzystych + sumaNieparzystych = 76

Reszta z dzielenia 76 przez 10 (76 modulo 10) nie jest zerem więc nasz numer nie jest poprawny.

Zapiszmy algorytm wykorzystując Javę. Metoda czyPoprawna() zwróci nam wartość logiczną świadczącą o poprawności bądź też nie sprawdzanego ciągu cyfr.

/**
 * Implementacja algorytmu Luhna
 * @author kodatnik.blogspot.com
 */
public class AlgorytmLuhna {

 public static boolean czyPoprawna(String liczba){
  // zmienne przechowujące odpowiednie sumy
  int sumaParzystych = 0, sumaNieparzystych = 0;

  // odwracamy liczbę dla uproszczenia obliczeń
  String odwroconaLiczba = new StringBuilder(liczba).reverse().toString();
        
  // pętla dla poszczególnych cyfr
  for(int i = 0 ;i < odwroconaLiczba.length(); i++){

   // zamieniamy znak cyfry na wartość liczbową
   int cyfra = Integer.parseInt(odwroconaLiczba.substring(i, i + 1));
            
   // cyfra na pozycji nieparzystej
   if(i % 2 == 0) { 
    // zwiększamy sumę 
    sumaNieparzystych += cyfra;
   } 
   // cyfra na pozycji parzystej
   else {  
    // podwajamy cyfrę
    cyfra = cyfra * 2;
                
    // jeśli wynik większy od 9 to sumujemy cyfry wyniku
    if (cyfra > 9) cyfra = (cyfra%10)+1;

    // zwiększamy sumę
    sumaParzystych += cyfra;
   }
  }
  // zwracamy prawdę lub fałsz w zależności od wyniku modulo 10
  return (sumaParzystych + sumaNieparzystych) % 10 == 0;
 }

 public static void main(String[] args) {
  System.out.println(czyPoprawna("4853928344613904"));
  System.out.println(czyPoprawna("4408041234567893"));
 }
}

Uruchomiona aplikacja:

false
true

Czyli pierwsza liczba jest niepoprawna, a druga poprawna (oczywiście według algorytmu Luhna).

Wyświetlanie drzewa na konsoli

2010-04-16T20:49:00.000+02:00

W poprzednich postach utworzyliśmy strukturę drzewa (Ogólna implementacja) oraz poznaliśmy metody umożliwiające przejście przez wszystkie jego węzły w określonej kolejności (Trawersowanie drzewa). Kolejnym krokiem będzie przedstawienie struktury drzewa w jakiejś czytelnej formie na ekranie komputera. Wykorzystamy do tego celu konsolę. Jest kilka sposobów prezentacji drzewa, najczęściej wykorzystuje się zapis, gdzie poszczególne elementy są w odpowiednich kolumnach lub zapis z nawiasami, które symbolizują dzieci danego elementu. Przyjrzyjmy się naszemu drzewu jeszcze raz w formie graficznej.

W postaci konsolowej możemy zapisać jego strukturę tak:

Adam
        Ewa
                Jurek
                Max
                Iza
        Jarek
                Iwona
        Marta
                Rafał
                Ola

lub tak:

Adam(Ewa(Jurek, Max, Iza), Jarek(Iwona), Marta(Rafał, Ola))

W obu przypadkach odczytujemy: Adam jest korzeniem i ma trójkę "dzieci" (Ewa, Jarek oraz Marta), Ewa ma trójkę "dzieci" (Jurek, Max oraz Iza), Jarek ma jedno "dziecko" (Iwona), Marta ma dwójkę "dzieci" (Rafał i Ola).

Jak utworzyć metody, które wyświetlą nam odpowiednią kolejność elementów oraz zapewnią formatowanie? Przyjrzyjmy się najpierw kolejności elementów....tak dokładnie to jest kolejność preorder. Wystarczy teraz tylko odpowiednio dokonać formatowania oraz wyświetlić zawartość elementów. Pierwszy sposób wymaga dopisania metody, która będzie dla danego elementu zwracać jego poziom (odległość od korzenia drzewa). Napiszemy w klasie Tree<T> prostą metodę rekurencyjną getLevel():

public int getLevel(Node<T> n) {
 if (n == root) return 0;
 else return 1 + getLevel(n.getParent());
}

Dodatkowo dodamy do naszej klasy pole output typu StringBuilder (taki dynamiczny String). W tej zmiennej będziemy przechowywać widok naszego drzewa. Metoda, która przygotuje nam ten widok działa bardzo podobnie jak metoda trawersująca typu preorder. Jedyne modyfikacje to pobieranie poziomu węzła i dodawanie odpowiedniej ilości znaków tabulacji (symulacja kolumn).

private void makeTreeStringOutline(Node<T> n) {
 for(int i=0; i < getLevel(n); i++) output.append("\t");
 output.append(n + "\n");
 Node<T> temp = n.getLeftMostChild();
 while (temp != null) {
  makeString(temp);
  temp = temp.getRightSibling();
 }
}

Drugi sposób prezentacji drzewa zostanie zrealizowany bardzo podobnie. Opieramy się na trawersowaniu preorder oraz wstawiamy w odpowiednie miejsca znaki nawiasów (otwierające i zamykające).

private void makeTreeStringBrackets(Node<T> n) {
 output.append(n);
 Node<T> temp = n.getLeftMostChild();
 if( temp != null) output.append("(");
 while (temp != null) {
  makeStringPar(temp);
  temp = temp.getRightSibling();
  if (temp != null) output.append(", ");
  else output.append(")");
 }
}

Wywołanie tych metod możemy umieścić w dowolnej metodzie. Najlepiej będzie wykorzystać do tego celu metodę toString(). Przesłonięta wersja tej metody poniżej (prezentacja drzewa możliwa jest na dwa sposoby, jeden jest ujęty w komentarz).

public String toString() {
 output = new StringBuilder();

 makeTreeStringOutline(root); // wersja "drzewiasta"
 //makeTreeStringBrackets(root); // wersja z nawiasami

 return output.toString();
}

Pozostaje tylko sprawdzenie czy nasz kod działa. Utwórzmy drzewo i wyświetlmy je na konsoli.

Node<String> korzen = new Node<String>(null, "Adam");
Node<String> n1 = korzen.addChild("Ewa");
Node<String> n2 = korzen.addChild("Jarek");
Node<String> n3 = korzen.addChild("Marta");

n1.addChild("Jurek");
n1.addChild("Max");
n1.addChild("Iza");

n2.addChild("Iwona");

n3.addChild("Rafał");
n3.addChild("Ola");

Tree<String> drzewo = new Tree<String>(korzen);

System.out.println (drzewo);

Efekt działania:

Adam
        Ewa
                Jurek
                Max
                Iza
        Jarek
                Iwona
        Marta
                Rafał
                Ola

Poniżej cały kod drzewa wraz ze wszystkimi klasami i metodami.

import java.util.*;

/**
 * Klasa Node<T> - węzeł drzewa
 * @author kodatnik.blogspot.com
 */
class Node<T> {
 private T data;
 private Node<T> parent;
 private LinkedList<Node<T>> children;

 public Node() {
  parent = null;
  children = new LinkedList<Node<T>>();
 }

 public Node(Node<T> parent) {
  this();
  this.parent = parent;
 }

 public Node(Node<T> parent, T data) {
  this(parent);
  this.data = data;
 }

 public Node<T> getParent(){
  return parent;
 }

 public void setParent(Node<T> parent) {
  this.parent = parent;
 }

 public T getData() {
  return data;
 }

 public void setData(T data) {
  this.data = data;
 }

 public int getDegree() {
  return children.size();
 }

 public boolean isLeaf(){
  return children.isEmpty();
 }

 public Node<T> addChild(Node<T> child) {
  child.setParent(this);
  children.add(child);
  return child;
 }

 public Node<T> addChild(T data) {
  Node<T> child = new Node<T>(this, data);
  children.add(child);
  return child;
 }

 public Node<T> getChild(int i){
  return children.get(i);
 }

 public Node<T> removeChild(int i) {
  return children.remove(i);
 }

 public void removeChildren() {
  children.clear();
 }

 public LinkedList<Node<T>> getChildren() {
  return children;
 }

 public Node<T> getLeftMostChild() {
  if (children.isEmpty()) return null;
  return children.get(0);
 }

 public Node<T> getRightSibling() {
  if (parent != null) {
   LinkedList<Node<T>> parentsChildren = parent.getChildren();
   int pos = parentsChildren.indexOf(this);
   if (pos < (parentsChildren.size()-1))
    return parentsChildren.get(pos+1);
  }
  return null;
 }

 public String toString() {
  return data.toString();
 }
}

/**
 * Klasa Tree<T> - drzewo
 * @author kodatnik.blogspot.com
 */
class Tree<T> {

 private Node<T> root;
 private StringBuilder output;

 public Tree() {
  root = null;
 }

 public Tree(Node<T> root) {
  this.root = root;
 }

 public Node<T> getRoot() {
  return root;
 }

 public void preOrder() {
  preOrder(root);
 }

 public void postOrder() {
  postOrder(root);
 }

 public void inOrder() {
  inOrder(root);
 }

// metoda wyświetla węzły w kolejności preorder
public void preOrder(Node<T> n) {
 //najpierw korzeń
 System.out.print(n + " ");
 // potem lewe skrajne poddrzewo, a później prawe
 Node<T> temp = n.getLeftMostChild();
 while (temp != null) {
  preOrder(temp);
  temp = temp.getRightSibling();
 }
}

// metoda wyświetla węzły w kolejności postorder
public void postOrder(Node<T> n) {
 // najpierw lewe skrajne poddrzewo, potem prawe
 Node<T> temp = n.getLeftMostChild();
 while (temp != null) {
  postOrder(temp);
  temp = temp.getRightSibling();
 }
 // na końcu korzeń
 System.out.print(n + " ");
}

// metoda wyświetla węzły w kolejności inorder
public void inOrder(Node<T> n) {
 if (n.isLeaf())
  System.out.print(n + " ");
 else {
  // najpierw lewe skrajne poddrzewo
  Node<T> temp = n.getLeftMostChild();
  inOrder(temp);
  // potem korzeń
  System.out.print(n + " ");
  // potem prawe
  temp = temp.getRightSibling();
  while (temp != null) {
   inOrder(temp);
   temp = temp.getRightSibling();
  }
 }
}

 // metoda zwraca poziom węzła
 public int getLevel(Node<T> n) {
  if (n == root) return 0;
  else return 1 + getLevel(n.getParent());
 }

 private void makeTreeStringOutline(Node<T> n) {
  for(int i=0; i < getLevel(n); i++) output.append("\t");
  output.append(n + "\n");
  Node<T> temp = n.getLeftMostChild();
  while (temp != null) {
   makeTreeStringOutline(temp);
   temp = temp.getRightSibling();
  }
 }

 private void makeTreeStringBrackets(Node<T> n) {
  output.append(n);
  Node<T> temp = n.getLeftMostChild();
  if( temp != null) output.append("(");
  while (temp != null) {
   makeTreeStringBrackets(temp);
   temp = temp.getRightSibling();
   if (temp != null) output.append(", ");
   else output.append(")");
  }
 }

 public String toString() {
  output = new StringBuilder();

  makeTreeStringOutline(root); // reprezentacja drzewiasta
  //makeTreeStringBrackets(root); // reprezentacja z nawiasami

  return output.toString();
 }
}

public class NaszeDrzewo {
 public static void main(String args[]) {

  // tworzymy węzeł będący korzeniem
  Node<String> korzen = new Node<String>(null, "Adam");

  // dodajemy do niego kolejne węzły
  Node<String> n1 = korzen.addChild("Ewa");
  Node<String> n2 = korzen.addChild("Jarek");
  Node<String> n3 = korzen.addChild("Marta");

  n1.addChild("Jurek");
  n1.addChild("Max");
  n1.addChild("Iza");

  n2.addChild("Iwona");

  n3.addChild("Rafał");
  n3.addChild("Ola");

  // tworzymy drzewo i wskazujemy, który węzeł jest korzeniem
  Tree<String> drzewo = new Tree<String>(korzen);

  System.out.println(drzewo);
 }
}

Klasa Arrays - przykłady zastosowań

2010-04-01T00:55:00.005+02:00

Dość często korzystamy z tablic jedno i wielowymiarowych. Klasa java.util.Arrays dostarcza wielu ciekawych metod ułatwiających pracę z tymi strukturami danych. Większość z nich jest przeciążona obsługując wiele typów danych (metoda przeciążona - metoda o takiej samej nazwie, ale różnej ilości lub rodzaju argumentów). Poniżej kilka przykładów wykorzystania tych metod (pamietaj o imporcie odpowiedniego pakietu - import java.util.*).

Wyświetlanie tablicy - metoda toString()

Metoda toString() zwraca tablicą jednowymiarową w formie tekstowej. Poszczególne elementy oddzielone są przecinkami. Jako parametr wywołania podajemy interesującą nas tablicę.

int[] tablica = {3, 8, 5, 6, 9, 2, 7, 4, 1};
System.out.println(Arrays.toString(tablica));

Wynik:

[3, 8, 5, 6, 9, 2, 7, 4, 1]

Jest to znaczące ułatwienie wyświetlania wszelkiego rodzaju tablic (nie musimy juz stosować pętli for). Dla tablic wielowymiarowych istnieje rekurencyjna wersja tej metody o nazwie deepToString().

int[][] macierz = { { 3, 8, 5},
                    { 5, 9, 2},
                    { 7, 4, 1} };
  
System.out.println(Arrays.deepToString(macierz));

Wynik:

[[3, 8, 5], [5, 9, 2], [7, 4, 1]]

Wypełnianie tablicy wartością - metoda fill()

Gdy chcemy wypełnić zawartość tablicy jakąś wartością możemy wykorzystać metodę fill(). Ma ona dwa parametry, pierwszy tablicę i drugi wartość jaką chcemy ją wypełnić.

int[] tablica = {3, 8, 5, 6, 9, 2, 7, 4, 1};
System.out.println(Arrays.toString(tablica));  
   
Arrays.fill(tablica, 14);
System.out.println(Arrays.toString(tablica));

Wynik:

[3, 8, 5, 6, 9, 2, 7, 4, 1]
[14, 14, 14, 14, 14, 14, 14, 14, 14]

Możemy również wykorzystać wypełnianie tylko części tablicy określoną wartością. Wykorzystamy do tego inną wersję metody fill() z czterema parametrami (dwa dodatkowe to indeks pierwszego i ostatniego elementu, który będziemy zmieniać, w przykładzie wartości 2 i 5).

int[] tablica = {3, 8, 5, 6, 9, 2, 7, 4, 1};
System.out.println(Arrays.toString(tablica));  
   
Arrays.fill(tablica, 2, 5, 14);
System.out.println(Arrays.toString(tablica));

Wynik:

[3, 8, 5, 6, 9, 2, 7, 4, 1]
[3, 8, 14, 14, 14, 2, 7, 4, 1]

Sortowanie tablicy - metoda sort()

Tablice możemy sortować za pomocą metody sort() (wykorzystywany jest algorytm sortowania szybkiego - quickSort).

int[] tablica = {3, 8, 5, 6, 9, 2, 7, 4, 1};
System.out.println(Arrays.toString(tablica));  

Arrays.sort(tablica);    
System.out.println(Arrays.toString(tablica));

Wynik:

[3, 8, 5, 6, 9, 2, 7, 4, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Przeciążona wersja metody sort() (z trzema parametrami) umożliwia sortowanie tylko części tablicy. Dodatowo podajemy indeks pierwszego i ostatniego elementu do sortowania. Jeżeli nasza tablica zawiera obiekty to muszą one implementować interfejs Comparable (pisałem o nim w poście Porównujemy obiekty - interfejs Comparable<T>).

Wyszukiwanie elementu - metoda binarySearch()

Znalezienie szukanej wartości w tablicy to zadanie dla metody binarySearch(). Ponieważ wykorzystuje ona wyszukiwanie binarne to tablica musi być już wstępnie posortowana. Metoda zwraca numer indeksu, na którym znajduje się poszukiwany element lub wartośc -1 jeśli taki element nie występuje w tablicy. Poniższy przykład sortuje tablicę oraz szuka w niej wartości 4.

int[] tablica = {3, 8, 5, 6, 9, 2, 7, 4, 1};
System.out.println(Arrays.toString(tablica));  
   
Arrays.sort(tablica);    
System.out.println(Arrays.toString(tablica));    
         
System.out.println(Arrays.binarySearch(tablica, 4));

Wynik (tablica nieposortowana, posortowana oraz indeks na którym znajduje się wartość 4):

[3, 8, 5, 6, 9, 2, 7, 4, 1]
[1, 2, 3, 4, 5, 6, 7, 8, 9]
3

Możemy również wykorzystać przeciążoną wersję metody binarySearch() wyszukującą tylko w określonej części posortowanej tablicy.

Porównywanie zawartości tablic - metoda equals()

Sprawdzenie czy dwie tablice są takie same (zawierają takie same elementy) realizowane jest za pomocą metody equals(). Zwraca ona prawdę (wartość true) jeśli tak i fałsz (wartość false) jeśli nie.

int[] tablicaA = {3, 8, 5, 6, 9, 2, 7, 0, 1};
int[] tablicaB = {3, 8, 5, 6, 9, 2, 7, 4, 1};         
   
if(Arrays.equals(tablicaA, tablicaB)) 
 System.out.println ("Tablice są takie same.");
else 
 System.out.println ("Tablice są różne.");

Wynik:

Tablice są różne.

Dla tablic wielowymiarowych odpowiednią metodą porównującą jest deepEquals().

Mieszanie zawartości tablicy...

Ostatnia przydatna rzecz to możliwość pomieszania elementów występujących w tablicy. Nie do końca ma to związek z klasą Arrays, ale... Załóżmy, że mamy taką tablicę:

String[] imiona = { "Adam", "Marek", "Iwona", "Patryk", "Dorota", "Ewa"};

W klasie obsługującej kolekcje (Collections) istnieje metoda, która miesza (ang. shuffle) elementy danej kolekcji (kolekcja to pojemnik przechowujący jakieś dane). Gdyby udało nam się zamienić naszą tablicę na kolekcję to moglibyśmy wykorzystać metodę mieszającą. Z pomocą przychodzi metoda toList() z klasy Arrays. Zamienia ona naszą tablicę w listę (obiekt klasy List), która jest już częścią kolekcji i daje nam możliwość wykorzystania metody shuffle().

Collections.shuffle(Arrays.asList(imiona));
System.out.println(Arrays.toString(imiona));

Przykładowa zawartość naszej tablicy po wymieszaniu elementów:

[Marek, Patryk, Ewa, Dorota, Adam, Iwona]

Elementami kolekcji mogą być tylko typy obiektowe. Gdybyśmy chcieli pomieszać typy prymitywne to wystarczy użyć klas opakowujących i tak na przykład dla tablicy z wartościami typu int możemy użyć poniższego kodu (konwersja między typem int, a Integer jest automatyczna).

Integer[] tablica = {3, 8, 5, 6, 9, 2, 7, 4, 1};
Collections.shuffle(Arrays.asList(tablica));
System.out.println(Arrays.toString(tablica));

Przykładowy wynik:

[1, 9, 6, 3, 7, 2, 5, 4, 8]

Trawersowanie drzewa - metody preorder, postoder i inorder

2010-03-31T00:35:00.002+02:00

W poprzednim poście (Drzewo ogólna implementacja) przedstawiłem podstawy tworzenia struktury drzewa. Dziś zajmiemy się sposobami trawersowanie drzewa czyli odwiedzenia wszystkich jego węzłów w ściśle określonej kolejności. Dla drzew ogólnych mamy dwie metody odwiedzania preorder oraz postorder, w przypadku drzew binarnych (gdzie węzeł może posiadać maksymalnie dwóch potomków) istnieje jeszcze metoda inorder.

Metoda preorder odwiedza węzły w następującej kolejności:

najpierw korzeń,
potem lewe skrajne poddrzewo,
potem prawe skrajne poddrzewo.

Trawersowanie za pomocą postorder:

najpierw lewe skrajne poddrzewo,
potem prawe skrajne poddrzewo,
i na końcu korzeń.

Metoda inorder:

najpierw lewe skrajne poddrzewo,
potem korzeń,
potem prawe skrajne poddrzewo.

Dla naszego przykładowego drzewa ogólnego metody preorder i postorder zwrócą następującą kolejność węzłów.

preorder: Adam Ewa Jurek Max Iza Jarek Iwona Marta Rafał Ola 
postorder: Jurek Max Iza Ewa Iwona Jarek Rafał Ola Marta Adam

Gdybyśmy utworzyli drzewo binarne z następującą strukturą (takie drzewo nazywane jest drzewem wyrażeń arytmetycznych):

Node<String> korzen = new Node<String>(null, "*");
Node<String> n1 = korzen.addChild("+");
Node<String> n2 = korzen.addChild("-");     
     
n1.addChild("7");
n1.addChild("3");     
      
n2.addChild("6");      
n2.addChild("2");            
     
Tree<String> drzewo = new Tree<String>(korzen);

to przejście przez wszystkie jego elementy wyglądałoby w następujący sposób:

preorder: * + 7 3 - 6 2 
postorder: 7 3 + 6 2 - * 
Inorder: 7 + 3 * 6 - 2

Jak łatwo zauważyć dla drzew zawierających wyrażenia arytmetyczne poszczególne metody odwiedzania węzłów odpowiadają odpowiedniej notacji. Preorder to notacja prefiksowa (notacja polska), postorder to notacja postfiksowa (odwrotna notacja polska), a inorder to zwykła notacja infiksowa.

Poniżej trzy metody rekurencyjne realizujące poszczególne sposoby trawersowania drzewa (umieszczamy je w ciele klasy Tree<T> z poprzedniego postu).

/**
 * Metody trawersowania drzewa
 * @author kodatnik.blogspot.com 
 */ 

// metoda wyświetla węzły w kolejności preorder
public void preOrder(Node<T> n) {
 //najpierw korzeń
 System.out.print(n + " ");        
 // potem lewe skrajne poddrzewo, a później prawe
 Node<T> temp = n.getLeftMostChild();
 while (temp != null) {
  preOrder(temp);
  temp = temp.getRightSibling();
 }
}  
  
// metoda wyświetla węzły w kolejności postorder
public void postOrder(Node<T> n) {
 // najpierw lewe skrajne poddrzewo, potem prawe
 Node<T> temp = n.getLeftMostChild();
 while (temp != null) {
  postOrder(temp);
  temp = temp.getRightSibling();
 }
 // na końcu korzeń
 System.out.print(n + " ");
}  

// metoda wyświetla węzły w kolejności inorder
public void inOrder(Node<T> n) {
 if (n.isLeaf())
  System.out.print(n + " ");
 else {
  // najpierw lewe skrajne poddrzewo
  Node<T> temp = n.getLeftMostChild();
  inOrder(temp);
  // potem korzeń
  System.out.print(n + " ");  
  // potem prawe
  temp = temp.getRightSibling();   
  while (temp != null) {
   inOrder(temp);
   temp = temp.getRightSibling();
  }
 } 
}

Mając już opanowane sposoby "chodzenia" po drzewie możemy zastanowić się nad prezentacją jego struktury na ekranie. To wszystko już w następnym poście.

Zamiana liczb rzymskich na arabskie i na odwrót

2010-03-17T02:37:00.000+01:00

Konwersja między różnymi formatami zapisu liczb zawsze jest dobrą wprawką programistyczną. Przyjrzyjmy się dwóm systemom zapisu. System arabski wykorzystuje cyfry od 0 do 9 i jest stosowany powszechnie na całym świecie. System rzymski opiera się na 7 znakach literowych (I - 1, V - 5, X - 10, L - 50, C - 100, D - 500, M - 1000). Poszczególne wartości są tworzone za pomocą odpowiednich zestawień znaków. Np. MCMXCIV odpowiada liczbie 1994. W jaki sposób prawidłowo odczytać wartość, znaki jednakowe są dodawane (np. XX - 10+10 = 20), znaki mniejsze stojące przed większymi są od nich odejmowane (np. IV - 5-1 = 4), znaki mniejsze stojące za większymi są do nich dodawane (np. VI - 5+1 = 6).

Dodatkowo jest kilka założeń, które powinny być przestrzegane:

nie można znaku stanowiącego jednostki (I), dziesiątki(X) lub setki(C) (nie dotyczy to znaku tysięcy - M) użyć więcej niż trzy razy, np. IIII jest niedozwolone,
znaki, które nie są symbolami jednostek (I), dziesiątek(X), setek (C), tysięcy (M) mogą występować tylko pojedynczo, np. LL jest niedozwolone,
znaki które można odejmować od znaków większych to tylko I, X, C, ale tylko jeśli znak większy nie jest więcej niż 10 razy większy, np. IC jest niedozwolone.

Zasady wyglądają strasznie ;) Poniżej algorytm, który dokona zamiany podanej przez użytkownika liczby w systemie rzymskim na system arabski i odwrotnie. W dwóch tablicach zapisane zostały podstawowe wartości w systemie rzymskim (7 podstawowych znaków plus dla uproszczenia algorytmu kilka wyjątków) oraz odpowiadające im wartości systemu arabskiego. Dodatkowo program sprawdza poprawność podawanych liczb. Dla systemu arabskiego jest sprawdzany zakres liczby (tylko liczby od 1 do 3999), a dla rzymskiego jej poprawność. Dla pominięcia wszelkich zawiłości związanych ze sprawdzeniem czy dana liczba rzymska została poprawnie podana przez użytkownika, metoda czyPoprawnaRzymska() dokonuje zamiany podanej liczby rzymskiej na arabską, a później dla uzyskanego wyniku z powrotem na rzymską. Jeśli wynik zgadza się z tym który podał użytkownik, program uznaje zapis za poprawny.

// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Zamiana liczb zapisanych w systemie rzymskim i arabskim
 * @author kodatnik.blogspot.com
 */
public class RzymskieArabskie {

 // tablica liczb rzymskich (podstawowe + dozwolone)
 private static String[] rzymskie = {"M", "CM", "D", "CD", "C","XC", "L", "XL", "X", "IX", "V", "IV", "I"};
 // tablica odpowiadających im liczb arabskich
 private static int[] arabskie   = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};

 // metoda sprawdza czy podana liczba rzymska jest poprawna
 public static boolean czyPoprawnaRzymska(String liczba) {
  
  // konwertujemy liczbę na duże znaki (takie mamy w tablicy)
  liczba = liczba.toUpperCase();  
  
  // jeśli liczba jest pusta zwracamy fałsz
  if (liczba.length() == 0) return false;
  // jeśli wartość tego co dostajemy od użytkownika z tym co 
  // sami obliczymy (zamiana na arabską i ponowna na rzymską) jest różna zwracamy fałsz 
  if (!liczba.equals(naRzymska(naArabska(liczba)))) return false;
  // w każdym innym przypadku zwracamy prawdę
  return true;
 }

 // metoda sprawdza czy podana liczba arabska jest poprawna
 public static boolean czyPoprawnaArabska(int liczba) {
  // sprawdzamy zakres
  if (liczba < 1 || liczba > 3999) return false;  
  // jeśli w porządku zwracamy prawdę
  else return true;
 }
 
 // metoda zamienia liczbę arabską na rzymską
 public static String naRzymska(int liczba) {
 
  // zmienna wyjście będzie zawierała liczbę rzymską
  String wyjscie = "";
  
  // sprawdzamy w pętli naszą liczbę z poszczególnymi
  // elementami tablicy liczb arabskich
  for (int i = 0; i < arabskie.length; i++) {
   // dopóki liczba jest większa
   while (liczba >= arabskie[i]) {
    // tworzymy liczbę rzymską dodając odpowiedną wartość z tablicy rzymskie
    wyjscie += rzymskie[i];
    // zmniejszamy liczbę arabską o odpowiednią wartość
    liczba -= arabskie[i];
   }
  }
  // zwracamy liczbę rzymską (łańcuch tekstowy)
  return wyjscie;
}
 
 // meoda zamienia liczbę rzymską na arabską
 public static int naArabska(String liczba) {
  
  // konwertujemy liczbę na duże znaki (takie mamy w tablicy)
  liczba = liczba.toUpperCase();
      
  // zmienna wyjście będzie zawierała liczbę arabską
  int wyjscie = 0;
 
  // zmienna index umożliwi nam przemieszczanie się po liczbie rzymskiej
  int index = 0;      
      
  // sprawdzamy w pętli naszą liczbę z poszczególnymi
  // elementami tablicy liczb rzymskich
  for (int i = 0; i < rzymskie.length; i++) {
   // dopóki liczba zaczyna się z odpowiednią liczbą rzymską
   while (liczba.startsWith(rzymskie[i], index)) {
    // tworzymy liczbę arabską dodając odpowiedną wartość z tablicy arabskie
    wyjscie += arabskie[i];
    // przechodzimy do następnej pozycji w liczbie rzymskiej
    index += rzymskie[i].length();
   }
  }  
  // zwracamy liczbę arabską 
  return wyjscie;
 } 
  
   
 public static void main (String[] args) {
     
  Scanner wejscie = new Scanner(System.in);
     
  System.out.print ("Podaj liczbę z zakresu (1-3999) w systemie rzymskim: ");
     
  // pobieramy od użytkownika łańcuch tekstowy (liczbę rzymską)
  String rzymska = wejscie.nextLine();
     
  // sprawdzamy poprawność i wyświetlamy wynik konwersji lub komunikat o błędzie
  if(czyPoprawnaRzymska(rzymska)) {
   System.out.println ("Liczba zapisana w systemie arabskim: " + naArabska(rzymska));
  } else {
   System.out.println ("Niepoprawna liczba.");      
  }
     
  System.out.print ("Podaj liczbę z zakresu (1-3999) w systemie arabskim: ");
  
  // pobieramy od użytkownika liczbę (liczbę arabska)     
  int arabska = wejscie.nextInt();
     
  // sprawdzamy poprawność i wyświetlamy wynik konwersji lub komunikat o błędzie     
  if(czyPoprawnaArabska(arabska)) {
   System.out.println ("Liczba zapisana w systemie rzymskim: " + naRzymska(arabska));
  } else {
   System.out.println ("Niepoprawna liczba.");
  }
 }
}

Przykłady uruchomień aplikacji:

Podaj liczbę z zakresu (1-3999) w systemie rzymskim: MCMXCIV
Liczba zapisana w systemie arabskim: 1994
Podaj liczbę z zakresu (1-3999) w systemie arabskim: 666
Liczba zapisana w systemie rzymskim: DCLXVI

Podaj liczbę z zakresu (1-3999) w systemie rzymskim: ICVI
Niepoprawna liczba.
Podaj liczbę z zakresu (1-3999) w systemie arabskim: 978
Liczba zapisana w systemie rzymskim: CMLXXVIII

Drzewo - ogólna implementacja

2010-02-24T21:09:00.004+01:00

Struktury drzewiaste są dość często wykorzystywane w informatyce. Java nie posiada żadnej gotowej klasy do obsługi drzew. Dzisiaj prosta implementacja dowolnego drzewa ogólnego (każdy element drzewa może posiadać nieograniczoną liczbę potomków). Samo drzewo to struktura elementów, węzłów (ang. node) pozostających w zależności hierarchicznej tak jak na poniższym diagramie.

Szczególnym elementem drzewa jest korzeń (ang. root) czyli element nie posiadający rodzica (elementu nadrzędnego). Dodatkowe pojęcia związane z drzewem to liść (element nie posiadający dzieci), stopień węzła (liczba potomków węzła), elementy siostrzane węzła (elementy mające tego samego rodzica co dany węzeł), wysokość węzła (długość najdłuższej ścieżki od danego węzła do liścia), poziom węzła (długość ścieżki od korzenia do danego węzła). Patrząc na powyższy diagram możemy ustalić, że każdy węzeł:

przechowuje jakieś dane,
posiada referencję do węzła będącego jego rodzicem (w przypadku korzenia będzie to wartość null),
ma listę swoich dzieci (czyli listę referencji do węzłów będących jego potomkami).

Wykorzystując typy generyczne (pisałem o nich wcześniej: Typy generyczne) oraz listę powiązaną (też wspominałem: LinkedList przykład wykorzystania) jesteśmy w stanie stosunkowo łatwo zbudować klasę odpowiadającą pojedynczemu węzłowi:

class Node<T> {
 // dane przechowywane w węźle
 private T data; 
 // referencja do rodzica
 private Node<T> parent; 
 // lista dzieci
 private LinkedList<Node<T>> children; 
}

Dodajemy potrzebne konstruktory, domyślny (węzeł bez rodzica i z pustą listą dzieci), jednoparametrowy (węzeł z ustawionym rodzicem) i dwuparametrowy (węzeł z rodzicem i danymi):

public Node() {
 // brak referencji do rodzica
 parent = null; 
 // tworzymy pustą listę dzieci
 children = new LinkedList<Node<T>>(); 
}

public Node(Node<T> parent) {
 // wywołujemy konstruktor domyślny
 this(); 
 // ustawiamy rodzica
 this.parent = parent; 
} 

public Node(Node<T> parent, T data) {
 // wywołujemy konstruktor jednoparametrowy
 this(parent); 
 // ustawiamy dane
 this.data = data; 
}

Dodajmy również do klasy podstawowe metody dostępowe i modyfikujące dla danych i rodzica:

public Node<T> getParent(){
 // zwracamy referencję do rodzica
 return parent; 
}

public void setParent(Node<T> parent) {
 // ustawiamy rodzica
 this.parent = parent; 
}

public T getData() {
 // zwracamy przechowywane dane
 return data; 
}

public void setData(T data) {
 // ustawiamy dane
 this.data = data; 
}

Stopień węzła, czyli liczbę jego potomków możemy łatwo określić zwracając rozmiar listy przechowującej referencję dzieci.

public int getDegree() {
 // zwracamy rozmiar listy przechowującej potomków węzła
 return children.size();
}

Tak samo sprawdzenie czy dany węzeł jest liściem (ang. leaf). Jeśli jego lista dzieci jest pusta, jest liściem.

public boolean isLeaf(){
 // jeśli lista dzieci jest pusta zwracamy true (węzeł jest liściem)
 return children.isEmpty();
}

Do węzła możemy dodawać dzieci. Jeden sposób to dodanie do listy potomków referencji węzła przekazanego jako parametr. Musimy pamiętać o ustawieniu w "dziecku" naszego "ojcostwa" (węzeł będący na liście naszych dzieci musi wiedzieć, że jesteśmy jego rodzicem).

public Node<T> addChild(Node<T> child) {
 // ustawiamy w dziecku rodzica (wskazujemy na nas)
 child.setParent(this);
 // dodajemy dziecko do listy naszych dzieci
 children.add(child);
 // zwracamy dziecko
 return child;
}

Drugi sposób wygodniejszy podczas tworzenia struktury drzewa to dodatnie do węzła dziecka z określonymi danymi. Nasza metoda utworzy na podstawie przekazanych danych nowy węzeł oraz doda go do listy jego dzieci.

public Node<T> addChild(T data) {
 //tworzymy nowy węzeł (ustawiamy od razu rodzica i dane)
 Node<T> child = new Node<T>(this, data); 
 // dopisujemy węzeł do listy naszych dzieci
 children.add(child);
 // zwracamy dziecko
 return child;
}

Dodatkowe operacje związane z dziećmi to pobranie i-tego dziecka z listy, usunięcia konkretnego dziecka, oraz usunięcie wszystkich dzieci węzła. Wykorzystamy metody dostępne w klasie LinkedList.

public Node<T> getChild(int i){
 // zwracamy referencję do i-tego dziecka (metoda get(int) z klasy LinkedList)
 return children.get(i);
}

public Node<T> removeChild(int i) {
 // usuwamy i-te dziecko (metoda remove(int) z klasy LinkedList)
 return children.remove(i);
}

public void removeChildren() {
 // usuwamy wszystkie nasze dzieci, czyścimy listę(metoda clear() z klasy LinkedList)
 children.clear();
}

Możemy również napisać metodę dostępową zwracającą listę dzieci węzła.

public LinkedList<Node<T>> getChildren() {
 // zwracamy referencję do listy naszych dzieci
 return children;
}

Pozostają nam jeszcze dwie metody, które przydadzą się do implementacji sposobów trawersowania drzewa. Pierwsza z nich zwróci nam najbardziej wysunięte w lewo dziecko węzła (czyli pierwszego potomka z listy o ile tylko taki istnieje).

public Node<T> getLeftMostChild() {
 // jeśli nie mamy dzieci zwrócimy null
 if (children.isEmpty()) return null;
 // w przciwnym wypadku pierwsze dziecko z listy naszych dzieci
 return children.get(0);
}

Druga zwraca prawy element siostrzany (o ile istnieje) węzła.

public Node<T> getRightSibling() {
 // jeśli nie jesteśmy korzeniem
 if (parent != null) {
  // pobieramy listę dzieci naszego rodzica
  LinkedList<Node<T>> parentsChildren = parent.getChildren();
  // szukamy się na tej liście
  int pos = parentsChildren.indexOf(this);
  // sprawdzamy czy są jeszcze jakieś dzieci za nami
  if (pos < (parentsChildren.size()-1))
   // jesli tak zwracamy kolejne dziecko
   return parentsChildren.get(pos+1);
 }
 // zwracamy null jak węzeł jest korzeniem, albo nie ma już elementu siostrzanego po prawej
 return null;
}

Ostatnią częścią naszej klasy będzie przesłonięcie metody toString(). Zwrócimy po prostu dane przechowywane w węźle.

public String toString() {
 // zwracamy dane w formie łańcucha tekstowego
 return data.toString();
}

Poniżej cała gotowa klasa Node<T> opisująca węzeł naszego drzewa (komentarze zostały pominięte).

/**
 * Klasa Node<T> - węzeł drzewa
 * @author kodatnik.blogspot.com
 */
class Node<T> {
 private T data;
 private Node<T> parent;
 private LinkedList<Node<T>> children;

 public Node() {
  parent = null;
  children = new LinkedList<Node<T>>();
 }

 public Node(Node<T> parent) {
  this();
  this.parent = parent;
 } 

 public Node(Node<T> parent, T data) {
  this(parent);
  this.data = data;
 } 

 public Node<T> getParent(){
  return parent;
 }

 public void setParent(Node<T> parent) {
  this.parent = parent;
 }

 public T getData() {
  return data;
 }

 public void setData(T data) {
  this.data = data;
 } 

 public int getDegree() {
  return children.size();
 }

 public boolean isLeaf(){
  return children.isEmpty();
 }

 public Node<T> addChild(Node<T> child) {
  child.setParent(this);
  children.add(child);
  return child;
 }

 public Node<T> addChild(T data) {
  Node<T> child = new Node<T>(this, data); 
  children.add(child);
  return child;
 }

 public Node<T> getChild(int i){
  return children.get(i);
 }

 public Node<T> removeChild(int i) {
  return children.remove(i);
 }

 public void removeChildren() {
  children.clear();
 }

 public LinkedList<Node<T>> getChildren() {
  return children;
 }

 public Node<T> getLeftMostChild() {
  if (children.isEmpty()) return null;
  return children.get(0);
 }

 public Node<T> getRightSibling() {
  if (parent != null) {
   LinkedList<Node<T>> parentsChildren = parent.getChildren();
   int pos = parentsChildren.indexOf(this);
   if (pos < (parentsChildren.size()-1))
    return parentsChildren.get(pos+1);
  }
  return null;
 }

 public String toString() {
  return data.toString();
 }
}

Ostatnią czynnością będzie zbudowanie konkretnego drzewa. Sam proces sprowadza się do utworzenia odpowiednich węzłów, połączenie ich w strukturę hierarchiczną oraz wskazania węzła będącego korzeniem. Nasza klasa będzie posiadała tylko jedno pole, referencję do węzła będącego korzeniem. Dwa konstruktory, domyślny puste drzewo i jednoparametrowy ustawiający referencję do korzenia.

/**
 * Klasa Tree<T> - drzewo
 * @author kodatnik.blogspot.com
 */
class Tree<T> {
 // referencja do węzła będącego korzeniem
 private Node<T> root;

 public Tree() {
  // brak korzenia
  root = null;
 }

 public Tree(Node<T> root) {
  // ustawiamy korzeń
  this.root = root;
 } 
}

Wykorzystajmy gotowe klasy Node<T> oraz Tree<T> do budowy drzewa z diagramu.

public class NaszeDrzewo {
 public static void main(String args[]) {

  // tworzymy węzeł będący korzeniem
  Node<String> korzen = new Node<String>(null, "Adam");

  // dodajemy do niego kolejne węzły
  Node<String> n1 = korzen.addChild("Ewa");
  Node<String> n2 = korzen.addChild("Jarek");     
  Node<String> n3 = korzen.addChild("Marta");      
  
  n1.addChild("Jurek");
  n1.addChild("Max");     
  n1.addChild("Iza");            

  n2.addChild("Iwona");      

  n3.addChild("Rafał");
  n3.addChild("Ola");      

  // tworzymy drzewo i wskazujemy, który węzeł jest korzeniem
  Tree<String> drzewo = new Tree<String>(korzen);
 }
}

Zbudowaliśmy strukturę drzewa. Pozostaje wyświetlenie naszego drzewa na ekranie oraz przedstawienie sposobów poruszania się po drzewie. To wszystko w następnej części...

Metody o zmiennej liczbie argumentów

2010-01-22T14:20:00.000+01:00

Po poprzednich wpisach dzisiaj coś lekkiego :) Poznamy metody, które mogą mieć zmienną liczbę argumentów (ang. varargs). Przed Javą 1.5 (inaczej zwaną 5.0) jedyną możliwością przesłania do metody zmiennej liczby argumentów było wykorzystanie tablic, w Javie 5.0 wprowadzono nowy sposób zapisu argumentu: Typ... Przykładowy nagłówek metody o zmiennej liczbie argumentów:

public static void metoda(String napis, String... napisy);

Argument o zmiennej liczbie danych musi występować zawsze jako ostatni na liście argumentów metody. Trzy kropki oznaczają, że argument może zostać przekazany jako tablica albo lista wartości oddzielonych przecinkami. Jeżeli wykorzystany wartości oddzielone od siebie przecinkami, to kompilator Javy automatycznie skonwertuje je do postaci tablicy i prześle do metody. Dostęp do poszczególnych argumentów jest możliwy za pomocą na przykład pętli iteracyjnej czy też zwykłego dostępu do elementów tablicy (np. rozmiar takiej tablicy - pole length). Poniżej przykładowa aplikacja zawierająca metodę wykorzystującą zmienną liczbę argumentów.

/**
 * Zmienna liczba argumentów w metodzie
 * @author kodatnik.blogspot.com
 */
public class ZmiennaLiczbaArgumentow {
 
 // ostatni argument metody może mieć zmienną liczbę danych
 public static void wyswietl(String napis, String... napisy) {
  
  // wyświetlamy pierwszy argument
  System.out.println (napis);

  // wyświetlamy liczbę argumentów przekazanych jako drugi parametr
  System.out.println ("Liczba zmiennych argumentów: " + napisy.length);

  // w pętli iteracyjnej wyświetlamy poszczególne elementy
  for (String lancuch : napisy) {
   System.out.println (lancuch);
  }
 }
 
 public static void main (String[] args) {
  // tworzymy tablicę łańcuchów znaków
  String[] lancuchy = {"Kasia", "Romek", "Andrzej", "Ola", "Tadeusz"};
  
  // wywołujemy metodę wyświetl z 4 argumentami
  wyswietl("Koleżanki", "Ania", "Ola", "Iwona");
  // wywołujemy metodę wyświetl z 2 argumentami
  wyswietl("Kolega", "Wiktor");
  // wywołujemy metodę wyświetl z 5 argumentami
  wyswietl("Znajomi", "Ania", "Ola", "Iwona", "Leszek");
  
  // wywołujemy metodę wyświetl z 2 argumentami
  // drugi argument jest tablicą z łańcuchami tekstowymi
  wyswietl("Pracownicy", lancuchy);
 }
}

Uruchomiona aplikacja:

Koleżanki
Liczba zmiennych argumentów: 3
Ania
Ola
Iwona
Kolega
Liczba zmiennych argumentów: 1
Wiktor
Znajomi
Liczba zmiennych argumentów: 4
Ania
Ola
Iwona
Leszek
Pracownicy
Liczba zmiennych argumentów: 5
Kasia
Romek
Andrzej
Ola
Tadeusz

Musimy pamiętać, że zamiana przez kompilator argumentów na tablicę pozbawia nas możliwości przeciążenia powyższej metody na taką:

public static void wyswietl(String napis, String[] napisy);

A co się stanie jeśli zdefiniujemy naszą metodę w ten sposób:

public static void wyswietl(String napis1, String napis2);

Która wersja metody zostanie wywołana dla takiego kodu?

wyswietl("Marek", "Wiktor");

Metoda wyswietl(String, String) jest bardziej wyspecjalizowana (inaczej mówiąc szczegółowa), więc ona zostanie wywołana domyślnie.

Przeglądamy kolekcję - interfejs Iterable<T>

2010-01-21T02:33:00.002+01:00

Od Javy 5.0 wprowadzono pętlę iteracyjną (znaną w innych językach programowania jako pętla foreach) umożliwiającą przeglądnięcie wszystkich elementów należących do danej kolekcji. Pętla ta może być stosowana z tablicami oraz wszystkim klasami, które implementują interfejs Iterable<T>.
Ogólny format pętli iteracyjnej:

for (T wartosc : kolekcja) {
 // dla każdego elementu z kolekcji dostępnego 
 // pod zmienną wartosc typu T
 // gdzie T jest typem generycznym
}

Powyższy zapis jest równoznaczny z uzyskaniem dla danej kolekcji iteratora (obiekt klasy Iterator<T>) oraz wykorzystania metod, które on udostępnia (np. hasNext(), next()).

Iterator<T> iterator = kolekcja.iterator();

while(iterator.hasNext()) {
 T wartosc = iterator.next();
 
 // dla każdego elementu z kolekcji dostępnego 
 // pod zmienną wartosc typu T
 // gdzie T jest typem generycznym
}

Jak utworzyć klasę, która będzie umożliwiała nam przejście przez wszystkie elementy za pomocą czy to pętli iteracyjnej for czy też while? Odpowiedź jest stosunkowo prosta. Musimy zaimplementować w naszej klasie interfejs Iterable<T> ("powiadamia" on o tym, że naszą klasę można przeglądać). Interfejs ten posiada tylko jedną metodę:

public Iterator<T> iterator();

zwracającą referencję do obiektu klasy implementującej interfejs Iterator<T>. Interfejs ten posiada trzy metody:

public boolean hasNext(); // sprawdza czy są jeszcze elementy w kolekcji
public T next();          // zwraca kolejny element
public void remove();     // usuwa kolejny element

Zazwyczaj implementuje się w pełni tylko dwie pierwsze metody. Trzecią zostawia się pustą (ma ona bezpośredni wpływ na zawartość kolekcji i nie ma sensu w ten sposób usuwać elementów, od tego powinny być metody dostępne w samej kolekcji). Zobaczmy prosty przykład wykorzystania interfejsu Iterable<T> na podstawie klasy Lista<T> odzwierciedlającej listę jednostronną jednokierunkową. Najpierw klasa pojedynczego węzła/elementu listy Wezel<T>.

/**
 * Węzeł - element listy 
 * @author kodatnik.blogspot.com
 */
class Wezel<T> {
 // pole przechowujące wartość znajdującą się w węźle
 private T obiekt;
 // referencja do następnego elementu listy
 private Wezel<T> nastepny;
 
 // konstruktor domyślny;
 public Wezel() {
  // wywołanie konstruktora dwuparametrowego)
  this(null, null);
 }
 
 // konstruktor dwuparametrowy
 // wartość oraz referencja do następnego węzła
 public Wezel(T obiekt, Wezel<T> nastepny) {
  this.obiekt = obiekt;
  this.nastepny = nastepny;
 }
  
 // metoda zwraca referencję do następnego węzła
 public Wezel<T> pobierzNastepny() {
  return nastepny;
 }
 
 // metoda zwraca przechowywaną w węźle wartość
 public T pobierzObiekt() {
  return obiekt;
 }
}

oraz klasa główna Lista<T>:

// wykorzystujemy klasę Iterator z pakietu java.util
import java.util.Iterator;

/**
 * Przykład wykorzystania iteratora
 * Lista jednostronna jednokierunkowa
 * @author kodatnik.blogspot.com
 */
class Lista implements Iterable<T> {

 // pole przechowujące referencję do początku listy
 private Wezel<T> poczatek;
 
 // konstruktor bezparametrowy
 public Lista () {
  // ustawiamy początek na null (lista pusta)
  poczatek = null;
 }
 
 // metoda wstawia dane na początek listy
 public void wstawNaPoczatek(T dane) {
  // tworzymy nowy węzeł oraz ustawiamy 
  // zmienną poczatek tak aby go wskazywała
  poczatek = new Wezel<T>(dane, poczatek);
 }
 
 // metoda usuwa element znajdujący się na początku listy
 // oraz zwraca referencję do niego
 public Wezel<T> usunZPoczatku() {
  // zapamiętujemy element z początku listy
  Wezel<T> temp = poczatek;
  // zmieniamy referencje początku listy
  // na następny element (pomijamy pierwszy)
  poczatek = poczatek.pobierzNastepny();
  // zwracamy zapamiętaną referencję
  return temp; 
 }
 
 // metoda zwraca referencję do obiektu klasy
 // implementującej interfejs Iterator<T>
 public Iterator<T> iterator() {
  // tworzymy nowy obiekt wewnętrznej klasy IteratorListy
  // i zwracamy jego referencję
  return new IteratorListy();
 }
 
 // prywatna klasa wewnętrzna implementująca interfejs Iterator<T>
 private class IteratorListy implements Iterator<T> {
  
  // pole przechowujące referencję do pierwszego elementu naszej listy
  private Wezel<T> temp = poczatek;
  
  // metoda zwraca wartość logiczną czy są jeszcze elementy w kolekcji
  public boolean hasNext() {
   return temp != null;
  }
  
  // metoda zwraca wartość elementu przechowywanego w kolejnym węźle
  public T next() {
   // pobieramy wartość (obiekt typu T)
   T obiekt = temp.pobierzObiekt();
   // przechodzimy na następny element listy
   temp = temp.pobierzNastepny();
   // zwracamy wartość
   return obiekt;
  }
  
  // metoda usuwająca element z kolekcji
  public void remove() {
   // ciało metody puste (patrz opis)
  }
 }
}

Zaimplementowaliśmy w klasie interfejs Iterable<T> (metoda iterator()) oraz utworzyliśmy wewnętrzną prywatną klasę IteratorListy implementującą interfejs Iterator<T>. Sprawdźmy działanie naszej klasy:

// wykorzystujemy klasę Iterator z pakietu java.util
import java.util.Iterator;

/**
 * Test listy
 * @author kodatnik.blogspot.com
 */
public class TestIteratora {
  
 public static void main (String[] args) {
 
  // tworzymy pierwszą listę (parametryzujemy typem String)
  Lista<String> listaPierwsza = new Lista<String>();
  
  // dodajemy elementy na początek listy
  listaPierwsza.wstawNaPoczatek("Adam");
  listaPierwsza.wstawNaPoczatek("Marek");
  listaPierwsza.wstawNaPoczatek("Kasia");
  
  // pobieramy iterator z listy
  Iterator<String> iterator = listaPierwsza.iterator();
  
  // dopóki są jeszcze elementy
  while(iterator.hasNext()) {
   // pobieramy je i wyświetlamy je na ekranie
   System.out.println (iterator.next());
  }
  
  // tworzymy drugą listę (parametryzujemy typem Integer)
  Lista<Integer> listaDruga = new Lista<Integer>();
  
  // dodajemy elementy do początek listy
  listaDruga.wstawNaPoczatek(10);
  listaDruga.wstawNaPoczatek(45);
  listaDruga.wstawNaPoczatek(83);
  
  // w pętli iteracyjnej wyświetlamy po kolei wszystkie elementy
  for (Integer wartosc: listaDruga) {
   System.out.println (wartosc);
  }
 }
}

Uruchomiona aplikacja:

Kasia
Marek
Adam
83
45
10

Kiedy korzystać z iteratora? Wtedy gdy nasza klasa przechowuje większą liczbę takich samych elementów, mówiąc inaczej jest kolekcją jakiś elementów. Implementacja interfejsu Iterable<T> znacznie uprości obsługę takiej klasy.

Porównujemy obiekty - interfejs Comparable<T>

2010-01-18T14:13:00.004+01:00

Często chcemy porównać ze sobą dwa obiekty jakiejś klasy. Oczywiście możemy porównać odpowiednie pola klasy i zwrócić wynik, ale.... rozwiązanie idealne polega na zaimplementowaniu w naszej klasie interfejsu Comparable<T>. Dzięki implementacji interfejsu, obiekty powstałe na bazie naszej klasy będą mogły być porównywane ze sobą. Taki sposób porównywania (mówiąc inaczej uporządkowania obiektów) jest wykorzystywany przez Javę np. w kolekcjach. Standardowe klasy np. klasa String również implementują ten interfejs. Dzięki temu porównując dwa łańcuchy tekstowe wiemy który jest "mniejszy", a który "większy" (w tym przypadku wykorzystywane jest uporządkowanie alfabetyczne). Wróćmy do interfejsu Comparable<T>, ma on tylko jedną metodę:

public int compareTo(T obiekt);

Metoda compareTo() może zwracać wartość ujemną, dodatnią albo zero odpowiednio dla obiektów mniejszych, większych lub równych obiektowi przekazanemu jako parametr jej wywołania. Wykorzystajmy interfejs Comparable<T> w przykładowej klasie Student. Nasza klasa będzie posiadać trzy pola: imię, nazwisko oraz numer albumu. Chcemy aby obiekty tworzone na jej podstawie można było porównywać ze sobą według nazwiska. Zastosowanie typów generycznych w interfejsie umożliwia nam swobodniejszy dostęp do obiektów, nie musimy wykonywać rzutowania (więcej o typach generycznych - Typy generyczne).

/**
* Klasa Student
* Przykład wykorzystania interfejsu Comparable<T>
* @author kodatnik.blogspot.com
*/

// klasa Student implementuje interfejs Comparable<T>
// czyli musi mieć wszystkie metody związane z tym interfejsem
class Student implements Comparable<Student> {
 // pola prywatne
 private String imie;
 private String nazwisko;
 private int nrAlbumu;

 // konstruktor klasy
 public Student(String imie, String nazwisko, int nrAlbumu) {
  this.imie = imie;
  this.nazwisko = nazwisko;
  this.nrAlbumu = nrAlbumu;
 }

 // metoda wymagana przez interfejs Comparable<T>
 public int compareTo(Student obiekt) {
  // zwracamy wynik porównania dwóch pól nazwisko
  // (korzystamy z porównania dostępnego w klasie String)
  return nazwisko.compareTo(obiekt.nazwisko);
 }

 // metoda przesłonięta, zwraca nam tekstową reprezentację obiektu
 public String toString() {
  return (nazwisko + " " + imie + " " + nrAlbumu);
 }
}

Poniżej przykład wykorzystania klasy Student. Tworzymy tablicę obiektów, sortujemy ją i wyświetlamy na ekranie.

/**
* Klasa TestPorownania
* Przykład wykorzystania klasy implementującej interfejs Comparable<T>
* @author kodatnik.blogspot.com
*/

// wykorzystujemy klasę Arrays (obsługa tablic)
import java.util.Arrays;

public class TestPorownania {
 public static void main(String[] args) {
  // tworzymy tablicę studentów o rozmiarze 6
  Student[] studenci = new Student[6];

  // wypełniamy poszczególne elementy tablicy obiektami typu Student
  studenci[0] = new Student("Marek", "Zielony", 4325);
  studenci[1] = new Student("Jacek", "Mruczek", 7453);
  studenci[2] = new Student("Iwona", "Lonkis", 2644);
  studenci[3] = new Student("Marta", "Annas", 1632);
  studenci[4] = new Student("Adam", "Mruczek", 3856);
  studenci[5] = new Student("Marek", "Zielony", 4287);

  // sortujemy tablicę za pomocą metody sort dostępnej w klasie Arrays
  // elementy tablicy zostaną posortowane według metody compareTo()
  Arrays.sort(studenci);

  // wyświetlamy zawartość posortowanej tablicy
  for (Student st: studenci){
   System.out.println(st);
  }
 }
}

Uruchomiona aplikacja:

Annas Marta 1632
Lonkis Iwona 2644
Mruczek Jacek 7453
Mruczek Adam 3856
Zielony Marek 4325
Zielony Marek 4287

Możemy poszerzyć zakres porównania dla studentów o takich samych nazwiskach. W ich przypadku będziemy porównywać również imiona, a gdy one również będą takie same numery albumu. Poprawiona metoda compareTo() przedstawia się następująco:

public int compareTo(Student obiekt) {
 // jeżeli nazwiska są takie same
 if (nazwisko.compareTo(obiekt.nazwisko) == 0)
  // sprawdzamy imiona
  if(imie.compareTo(obiekt.imie) == 0)
   // jeśli są takie same zwracamy różnicę z numerów albumu (dla takich samych będzie to zero)
   return nrAlbumu - obiekt.nrAlbumu;
  else
   // w przeciwnym wypadku zwracamy porównanie imion
   return imie.compareTo(obiekt.imie);
 else
  // w przeciwnym wypadku zwracamy porównanie nazwisk
  return nazwisko.compareTo(obiekt.nazwisko);
}

Wynik działania ze zmienioną metodą compareTo():

Annas Marta 1632
Lonkis Iwona 2644
Mruczek Adam 3856
Mruczek Jacek 7453
Zielony Marek 4287
Zielony Marek 4325

Odwrotna Notacja Polska - część 2

2009-12-12T23:28:00.003+01:00

W poprzedniej części (Odwrotna Notacja Polska - część 1) dokonaliśmy zamiany wyrażenia w formie infiksowej na postać postfiksową (czyli formę w Odwrotnej Notacji Polskiej). W tym wpisie spróbujemy dokonać sprawdzenia poprawności nawiasów występujących w wyrażeniu infiksowym oraz obliczymy wartość wyrażenia postfiksowego. Do sprawdzenia poprawności nawiasów w wyrażeniu infiksowym użyjemy stosu (więcej na ten temat - Sprawdzanie poprawności nawiasów). Jeśli wyrażenie nie będzie poprawne pod wartość wyrażenia postfiksowego podstawimy odpowiedni napis (klasa String - "Niepoprawne nawiasy w wyrażeniu infiksowym"). Nasza metoda sprawdzająca poprawność nawiasów będzie metodą prywatną:

// metoda sprawdza poprawność nawiasów w wyrażeniu infiksowym
private boolean czyPoprawneNawiasy() {
 // tworzymy stos
 Stack<String> stos = new Stack<String>();

 // dzielimy wyrażenie infiksowe na części na podstawie separatorów
 StringTokenizer st = new StringTokenizer(wyrazenieInfiksowe, "()", true);
        
 // dopóki są elementy w wyrażeniu wejściowym
 while(st.hasMoreTokens()) {
  // pobieramy element
  String s = st.nextToken();
            
  // jeżeli znak jest nawiasem otwierającym odkładamy go na stos
  if(s.equals("(")) stos.push(s);
  // jeżeli znak jest nawiasem zamykającym porównujemy go z wartością ze stosu            
  if(s.equals(")")) {
   if (stos.isEmpty()) return false;
   if (!stos.pop().equals("(")) return false;
  }
 }
 // zwracamy true albo false (stos pusty - wszystkie nawiasy są poprawne)
 return stos.isEmpty();         
}

Po sprawdzeniu poprawności nawiasów możemy już dokonać obliczenia wartości wyrażenia postfiksowego według następującego algorytmu:

Inicjalizujemy stos,
Analizujemy wyrażenie postfiksowe od lewej do prawej strony,
Jeżeli element jest argumentem to odkładamy go na stos,
Jeżeli element jest operatorem to ściągamy ze stosu dwie wartości, wykonujemy działanie, odkładamy na stos wynik,
Jeżeli dotarliśmy do końca wyrażenie postfiksowego, ściągamy wartość ze stosu (jest to obliczona wartość wyrażenia postfiksowego).

Przykład obliczenia wartości wyrażenia postfiksowego:

Wyrażenie infiksowe: (4*2)+(15/3)
Wyrażenie postfiksowe: 4 2 * 15 3 / + 

kolejny znak stos operacja
     4          4       odkładamy na stos
     2          4 2     odkładamy na stos
     *          8       ściągamy ze stosu dwie wartości i obliczamy
                        wartość wyrażenia(4*2), odkładamy ją na stos
     15         8 15    odkładamy na stos
     3          8 15 3  odkładamy na stos
     /          8 5     ściągamy ze stosu dwie wartości i obliczamy
                        wartość wyrażenia(15/3), odkładamy ją na stos
     +          13      ściągamy ze stosu dwie wartości i obliczamy
                        wartość wyrażenia(8+5), odkładamy ją na stos
                        ściągamy ze stosu wynik końcowy (13)

Obliczona wartość wyrażenia postfiksowego: 13

Poniżej metoda obliczająca wartość wyrażenia postfiksowego. Operujemy na wartościach typu double.

// metoda oblicza wartość wyrażenia postfiksowego
private double oblicz() {
  
 // tworzymy pusty stos
 Stack<Double> stos = new Stack<Double>();
        
 // dzielimy wyrażenie postfiksowe na elementy na podstawie spacji
 StringTokenizer st = new StringTokenizer(wyrazeniePostfiksowe, " ");
        
 // dopóki są elementy w wyrażeniu wejściowym
 while(st.hasMoreTokens()) {
  // pobieramy element
  String s = st.nextToken();
  
  // jeśli element nie jest operatorem (czyli jest wartością)
  if (!s.equals("+") && !s.equals("*") && !s.equals("-") && !s.equals("/")) {
   // zamieniamy łańcuch na liczbę
   double wartosc = Double.parseDouble(s);
   // odkładamy wartość na stos
   stos.push(wartosc);
  }
  else {
   //  jeśli element jest operatorem ściągamy dwie wartości ze stosu
   double wartosc1 = stos.pop();
   double wartosc2 = stos.pop();
   // w zależności od operatora obliczamy wynik i odkładamy go na stos
   switch(s.charAt(0)) {
    case '*': {stos.push(wartosc2 * wartosc1); break;}
    case '+': {stos.push(wartosc2 + wartosc1); break;}
    case '-': {stos.push(wartosc2 - wartosc1); break;}
    case '/': {stos.push(wartosc2 / wartosc1); break;}
   }
  }
 }
 // zwracamy końcowy wynik
 return stos.pop();
}

Cała klasa OdwrotnaNotacjaPolska:

// wykorzystujemy klasy Scanner, Stack<E> oraz StringTokenizer z pakietu java.util
import java.util.*;  
/**
 * Odwrotna Notacja Polska
 * Zamiana wyrażeń infiksowych na postfiksowe
 * @author kodatnik.blogspot.com
 */
public class OdwrotnaNotacjaPolska {
 // pola klasy
 private String wyrazenieInfiksowe;
 private String wyrazeniePostfiksowe; 
 private double wynik;   
 
 // konstruktor dokonuje przypisania polom wyrażeń
 public OdwrotnaNotacjaPolska(String wyrazenie) {
  this.wyrazenieInfiksowe = wyrazenie;
  wyrazeniePostfiksowe = "";
  wynik = 0.0;
  if(!czyPoprawneNawiasy())
   wyrazeniePostfiksowe = "Niepoprawne nawiasy w wyrażeniu infiksowym";
  else {
   // wywołujemy metodę dokonującą konwersji
   infiksNaPostfiks();
   wynik = oblicz();
  }   
 }

 // metoda zwraca wyrażenie w formie infiksowej
 public String pobierzWyrazenieInfiksowe() {
  return wyrazenieInfiksowe;
 }

 // metoda zwraca wyrażenie w formie postfiksowej
 public String pobierzWyrazeniePostfiksowe() {
  return wyrazeniePostfiksowe;
 }
 
 // metoda zwraca obliczoną wartość wyrażenia postfiksowego
 public double pobierzWynik() {
  return wynik;
 }
 
 // metoda sprawdza poprawność nawiasów w wyrażeniu infiksowym
 private boolean czyPoprawneNawiasy() {
  // tworzymy stos
  Stack<String> stos = new Stack<String>();

  // dzielimy wyrażenie infiksowe na części na podstawie separatorów
  StringTokenizer st = new StringTokenizer(wyrazenieInfiksowe, "()", true);
        
  // dopóki są elementy w wyrażeniu wejściowym
  while(st.hasMoreTokens()) {
   // pobieramy element
   String s = st.nextToken();
            
   // jeżeli znak jest nawiasem otwierającym odkładamy go na stos
   if(s.equals("(")) stos.push(s);
   // jeżeli znak jest nawiasem zamykającym porównujemy go z wartością ze stosu            
   if(s.equals(")")) {
    if (stos.isEmpty()) return false;
    if (!stos.pop().equals("(")) return false;
   }
  }
  // zwracamy true albo false (stos pusty - wszystkie nawiasy są poprawne)
  return stos.isEmpty();         
 }

 // metoda konwertuje wyrażenie w postaci infiksowej na postfiksową
 // wynik operacji jest zapisywany w polu wyrazeniePostfiksowe
 private void infiksNaPostfiks() {
        
  // tworzymy pusty stos
  Stack<String> stos = new Stack<String>();
        
  // dzielimy wyrażenie infiksowe na części na podstawie separatorów
  StringTokenizer st = new StringTokenizer(wyrazenieInfiksowe, "+-*/()", true);
        
  // dopóki są elementy w wyrażeniu wejściowym
  while(st.hasMoreTokens()) {
   // pobieramy element
   String s = st.nextToken();
         
   // jeżeli element jest operatorem
   if( s.equals("+") || s.equals("*") || s.equals("-") || s.equals("/")) {
    // sprawdzamy priorytety
    while(!stos.empty() && priorytet(stos.peek()) >= priorytet(s)) 
     wyrazeniePostfiksowe += stos.pop()  + " ";
    // odkładamy operator na stos
    stos.push(s);
   }
   // jeżeli element jest nawiasem otwierającym
   else if(s.equals("(")) stos.push(s);
   // jeżeli element jest nawiasem zamykającym
   else if(s.equals(")")) {
    // ściągamy operatory ze stosu, aż do nawiasu otwierajęcego
    while(!stos.peek().equals("(")) wyrazeniePostfiksowe += stos.pop() + " ";
    // ściągamy nawias otwierający
    stos.pop();
   }
   // jeżeli element nie jest operatorem ani nawiasem dodajemy go do wyrażenia postfiksowego
   else wyrazeniePostfiksowe += s  + " ";
  }
  // ściągamy ze stosu pozostałe operatory i dodajemy je do wyrażenia postfiksowego
  while(!stos.empty()) wyrazeniePostfiksowe += stos.pop()  + " ";
        
 } 
  
 // metoda zwraca priorytet operatora
 public static int priorytet(String operator) {
  // dla '+' i '-' zwracamy 1
  if(operator.equals("+") || operator.equals("-")) return 1;
  // dla '*' i '/' zwracamy 2
  else if(operator.equals("*") || operator.equals("/")) return 2;
  // dla pozostałych 0
  else return 0;
 }
 
 // metoda oblicza wartość wyrażenia postfiksowego
 private double oblicz() {
  
  // tworzymy pusty stos
  Stack<Double> stos = new Stack<Double>();
        
  // dzielimy wyrażenie postfiksowe na elementy na podstawie spacji
  StringTokenizer st = new StringTokenizer(wyrazeniePostfiksowe, " ");
        
  // dopóki są elementy w wyrażeniu wejściowym
  while(st.hasMoreTokens()) {

   // pobieramy element
   String s = st.nextToken();
  
   // jeśli element nie jest operatorem (czyli jest wartością)
   if (!s.equals("+") && !s.equals("*") && !s.equals("-") && !s.equals("/")) {
    // zamieniamy łańcuch na liczbę
    double wartosc = Double.parseDouble(s);
    // odkładamy wartość na stos
    stos.push(wartosc);
   }
   else {
    //  jeśli element jest operatorem ściągamy dwie wartości ze stosu
    double wartosc1 = stos.pop();
    double wartosc2 = stos.pop();
    // w zależności od operatora obliczamy wynik i odkładamy go na stos
    switch(s.charAt(0)) {
     case '*': {stos.push(wartosc2 * wartosc1); break;}
     case '+': {stos.push(wartosc2 + wartosc1); break;}
     case '-': {stos.push(wartosc2 - wartosc1); break;}
     case '/': {stos.push(wartosc2 / wartosc1); break;}
    }
   }
  }
  // zwracamy końcowy wynik
  return stos.pop();
 }
 
 // metoda zwraca nam łańcuch tekstowy z wyrażeniem 
 // w formie postfiksowej, oraz wynik
 public String toString() {
  return wyrazeniePostfiksowe + "\nWynik: " + wynik;
 }
}

Poniżej przykład wykorzystania klasy.

public class TestONP {
 public static void main(String args[]) {

  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj wyrażenie infiksowe: " );
  
  // pobieramy od użytkownika wyrażenie
  String wyrazenie = sc.nextLine();

  // tworzymy nowy obiekt klasy OdwrotnaNotacjaPolska 
  // i przekazujemy do konstruktora pobrane od użytkownika wyrażenie
  OdwrotnaNotacjaPolska onp = new OdwrotnaNotacjaPolska(wyrazenie);

  // wyświetlamy wyrażenie w postaci postfiksowej
  System.out.println ("Wyrażenie postfiksowe: " + onp);
 }
}

Wyniki działania aplikacji:

Podaj wyrażenie infiksowe: (4*2)+(15/3)
Wyrażenie postfiksowe: 4 2 * 15 3 / + 
Wynik: 13.0

Podaj wyrażenie infiksowe: (3+4)*2)
Wyrażenie postfiksowe: Niepoprawne nawiasy w wyrażeniu infiksowym

Podaj wyrażenie infiksowe: ((1+2)-2.5)*8/2
Wyrażenie postfiksowe: 1 2 + 2.5 - 8 * 2 / 
Wynik: 2.0

Nasza klasa nie obsługuje poprawnie sytuacji wyjątkowych oraz ma małą liczbę operatorów (można się pokusić o dodanie operacji potęgowania, pierwiastkowania czy też funkcji trygonometrycznych).

Piszemy gadżet do Bloggera - część 2

2009-12-06T14:49:00.014+01:00

W poprzedniej części (Piszemy gadżet do Bloggera - część 1) poznaliśmy podstawy pisania gadżetu oraz jego strukturę. Dzisiaj poznamy sposoby jego konfigurowania przez użytkownika. Pozwolimy użytkownikowi na podanie dodatkowych informacji podczas dodawania gadżetu do bloga. Dzięki temu użytkownik będzie mógł zdecydować np. o kolorach, napisach czy innych opcjach związanych z konkretnym gadżetem. Sekcją odpowiedzialną za preferencje jest <UserPref>. Opisuje ona pola, które będzie mógł modyfikować użytkownik podczas konfiguracji gadżetu. Pola mogą mieć następujące atrybuty:

name - nazwa którą będziemy się posługiwać w gadżecie,
display_name - nazwa wyświetlana użytkownikowi (jej brak powoduje wyświetlenie atrybutu name),
datatype - typ danych (string - łańcuch tekstowy, bool - wartość logiczna, enum - typ wyliczeniowy, hidden - pole ukyte, list - dynamiczna lista), domyślnym typem jest string,
required - atrybut logiczny określający czy dane pole jest wymagane,
default_value - domyślna wartość dla pola

Przykładowe pole preferencji pobierające od użytkownika łańcuch tekstowy (jego imię):

<UserPref name="imie" display_name="Podaj swoje imię:" />

W przypadku wybrania jako atrybutu pola preferencji typu enum, musimy określić dodatkowo opcje, z których może wybierać użytkownik. Opcje te podajemy za pomocą znacznika <EnumValue>. Posiada on dwa parametry:

value - wartość opcji,
display_value - nazwa wyświetlana użytkownikowi (jej brak powoduje wyświetlenie atrybutu value).

Przykładowe pole preferencji pobierające od użytkownika kierunek geograficzny (domyślnie południe):

<UserPref name="kierunek" display_name="Kierunek geogr." default_value="south" datatype="enum" >
 <EnumValue value="south" display_value="Południe" />
 <EnumValue value="north" display_value="Północ" />
 <EnumValue value="west" display_value="Zachód" />
 <EnumValue value="east" display_value="Wschód" />
</UserPref>

Dostęp do preferencji z poziomu kodu gadżetu odbywa się z wykorzystaniem JavaScript'u. Poniższy przykład pobierze podane przez użytkownika imię:

var preferencje = new gadgets.Prefs();
var imieUzytkownika = preferencje.getString("imie");

Wykorzystajmy naszą wiedzę do stworzenia prostego gadżetu umożliwiającego użytkownikowi podanie napisu, ustawienie koloru tła oraz określenie czy wyświetlać dzisiejszą datę czy też nie.

Wszystkie operacje związane z wyświetlaniem danych przeprowadzimy z wykorzystaniem JavaScript'u. Nasz przykładowy gadżet uruchamia się od funkcji init() (wywołanie gadgets.util.registerOnLoadHandler(init());) To co ma się pojawić w gadżecie zostało ujęte w sekcję HTML:

<div id="zawartosc"></div>

Korzystając z możliwości JavaScript'u jesteśmy w stanie zmienić kolor tła tego elementu (element.style.backgroundColor) jak i również wstawić do niego inne elementy czy to teksty czy też znaczniki HTML'a (element.innerHTML). Kod naszego gadżetu:

<?xml version="1.0" encoding="UTF-8" ?> 
<Module>
 <ModulePrefs 
  title="Przykładowy gadżet" 
  author="Devon"> 
  <Require feature="dynamic-height" />
 </ModulePrefs>
 <UserPref name="napis" display_name="Napis" default_value="Nasz drugi gadżet!" />
 <UserPref name="data" display_name="Pokazać datę?" default_value="true" datatype="bool" />
 <UserPref name="kolor" display_name="Kolor tła" default_value="green" datatype="enum" >
  <EnumValue value="red" display_value="Czerwony" />
  <EnumValue value="yellow" display_value="Żółty" />
  <EnumValue value="green" display_value="Zielony" />
 </UserPref>
 <Content type="html">
  <![CDATA[ 
   <div id="zawartosc"></div>

   <script type="text/javascript">
    // pobieramy preferencje
    var preferencje = new gadgets.Prefs();

    // funkcja startowa (nazwa może być dowolna)
    function init() {
     // bierzemy obiekt daty
     var data = new Date();
     // i wyciągamy z niego potrzebne informacje (dzień, miesiąc, rok)
     var dzisiaj = "< br />Dzisiaj jest: " + data.getDate() + "." + (data.getMonth()+1) + "." + data.getFullYear();
     // w tej zmiennej przechowujemy to co później dodamy do gadżetu
     var html = "";
    
     // pobieramy element zawartosc
     var element = document.getElementById('zawartosc');  
     // ustawiamy kolor tła elementu na taki jak podał użytkownik   
     element.style.backgroundColor = preferencje.getString("kolor"); 

     // dodajemy pobrany napis do zmiennej html
     html += preferencje.getString("napis");
   
     // jeżeli użytkownik chce wyświetlać datę
     if (preferencje.getBool("data") == true) {
      // to dodajemy ją do zmiennej html
      html += dzisiaj;
     }

     // wklejamy do "elementu" zawartość zmiennej html
     element.innerHTML = html;
    
     // zmieniamy wysokość gadżetu
     gadgets.window.adjustHeight(); 
    }

    // za pomocą tej metody podajemy funkcję, która
    // ma zostać uruchomiona podczas startu gadżetu (tutaj init())
    gadgets.util.registerOnLoadHandler(init()); 
   </script> 

  ]]>
 </Content> 
</Module>

Dodatkowo wykorzystaliśmy dynamiczną zmianę wysokości gadżetu (gadgets.window.adjustHeight()). Jest to możliwe po załadowaniu odpowiedniej biblioteki (<Require feature="dynamic-height" />) w sekcji <ModulePrefs>.
Po dodaniu gadżet prezentuje się następująco:

Gotowy gadżet jest dostępny do dodania do bloga pod adresem: http://sites.google.com/site/kodatnikfiles/xml/DrugiGadzet.xml

Odwrotna Notacja Polska - część 1

2009-12-05T00:05:00.003+01:00

Odwrotna Notacja Polska to sposób zapisu wyrażeń arytmetycznych za pomocą notacji postfiksowej. Standardowa notacja, z której korzystamy na codzień to notacja infiksowa, argument operator argument (np. 3 + 4). Notacja postfiksowa nie zmienia kolejności argumentów, natomiast zmienia położenie operatorów (występują one po argumentach, których dotyczą). Przykładowy zapis w notacji postfiksowej wyglada tak: 3 4 +. Taki sposób zapisu jest o wiele łatwiejszy do analizy poprawności wyrażenia jak i do jego obliczenia. Wykorzystując stos w prosty sposób możemy dokonać zamiany wyrażenia z postaci infiksowej na postać postfiksową. Algorytm zamiany jest następujący:

Inicjalizujemy stos,
Analizujemy wyrażenie infiksowe od lewej do prawej strony,
Jeżeli element jest argumentem to dodajemy go do wyrażenia postfiksowego,
Jeżeli element jest operatorem i stos jest pusty to odkładamy go na stos,
Jeżeli element jest operatorem i stos nie jest pusty to sprawdzamy co jest na wierzchołku stosu i porównujemy z odczytanym elementem. Jeśli operator ze stosu ma mniejszy lub równy priorytet z naszym znakiem to wstawiamy odczytany element na stos, jeśli nie to ściągamy operator ze stosu i dodajemy go do wyrażenia postfiksowego oraz odkładamy odczytany element na stos.
Jeśli nie ma więcej elementów w wyrażeniu infiksowym to ściągamy ze stosu (o ile nie jest pusty)znajdujące się tam operatory i dodajemy je do wyrażenia postfiksowego.

Przykład zamiany wyrażenia infiksowego na postfiksowe:

Wyrażenie infiksowe: 4 * 2 + 7 / 8

Kolejny znak       Stos      Wyrażenie postfiksowe
     4                                 4
     *             *                   4
     2             *                   4 2
     +             +                   4 2 *
     7             +                   4 2 * 7
     /             + /                 4 2 * 7
     8             + /                 4 2 * 7 8
                                       4 2 * 7 8 / +

Wyrażenie postfiksowe: 4 2 * 7 8 / +

Dla wyrażeń posiadających nawiasy postępujemy według następującego algorytmu:

Jeżeli odczytany znak jest nawiasem otwierającym to umieszczamy go na stosie,
Jeżeli odczytany znak jest nawiasem zamykającym to ściągamy ze stosu, aż do napotkania nawiasu otwierającego operatory i dodajemy do wyrażenia postfiksowego,
Ściągamy ze stosu nawias otwierający.

Przykład zamiany wyrażenia infiksowego z nawiasami na wyrażenie postfiksowe:

Wyrażenie infiksowe: ( 1 + 2 ) * 3

Kolejny znak       Stos      Wyrażenie postfiksowe 
     (             (
     1             (                   1
     +             ( +                 1
     2             ( +                 1 2
     )                                 1 2 +
     *             *                   1 2 +
     3             *                   1 2 + 3
                                       1 2 + 3 *

Wyrażenie postfiksowe: 1 2 + 3 *

Poniżej prosta klasa dokonująca konwersji wyrażeń z postaci infiksowej na postfiksową z wykorzystaniem powyższego algorytmu. Jako stos wykorzystałem klasę biblioteczną Stack. Podział danych wejściowych odbywa się za pomocą klasy StringTokenizer (więcej o tej klasie tu Podział łańcucha na części). Dodatkowo metoda priorytet(String) zwraca priorytet dla poszczególnych operatorów.

// wykorzystujemy klasy Scanner, Stack oraz StringTokenizer z pakietu java.util
import java.util.*;  
/**
 * Odwrotna Notacja Polska
 * Zamiana wyrażeń infiksowych na postfiksowe
 * @author kodatnik.blogspot.com
 */
public class OdwrotnaNotacjaPolska {
 // pola klasy
 private String wyrazenieInfiksowe;
 private String wyrazeniePostfiksowe; 
 
 // konstruktor dokonuje przypisania polom wyrażeń
 public OdwrotnaNotacjaPolska(String wyrazenie) {
  wyrazenieInfiksowe = wyrazenie;
  wyrazeniePostfiksowe = "";
  // wywołujemy metodę dokonującą konwersji
  infiksNaPostfiks();
 }

 // metoda konwertuje wyrażenie w postaci infiksowej na postfiksową
 // wynik operacji jest zapisywany w polu wyrazeniePostfiksowe
 private void infiksNaPostfiks() {
        
  // tworzymy pusty stos
  Stack<String> stos = new Stack<String>();
        
  // dzielimy wyrażenie infiksowe na części na podstawie separatorów
  StringTokenizer st = new StringTokenizer(wyrazenieInfiksowe, "+-*/()", true);
        
  // dopóki są elementy w wyrażeniu wejściowym
  while(st.hasMoreTokens()) {

   // pobieramy element
   String s = st.nextToken();
         
   // jeżeli element jest operatorem
   if( s.equals("+") || s.equals("*") || s.equals("-") || s.equals("/")) {
    // sprawdzemy priorytety
    while(!stos.empty() && priorytet(stos.peek()) >= priorytet(s)) 
     wyrazeniePostfiksowe += stos.pop()  + " ";
     // odkładamy operator na stos
    stos.push(s);
   }
   // jeżeli element jest nawiasem otwierającym
   else if(s.equals("(")) stos.push(s);
   // jeżeli element jest nawiasem zamykającym
   else if(s.equals(")")) {
    // ściągamy operatory ze stosu, aż do nawiasu otwierajęcego
    while(!stos.peek().equals("(")) wyrazeniePostfiksowe += stos.pop() + " ";
    // ściągamy nawias otwierający
    stos.pop();
   }
   // jeżeli element nie jest operatorem ani nawiasem dodajemy go do wyrażenia postfiksowego
   else wyrazeniePostfiksowe += s  + " ";
  }
  // ściągamy ze stosu pozostałe operatory i dodajemy je do wyrażenia postfiksowego
  while(!stos.empty()) wyrazeniePostfiksowe += stos.pop()  + " ";
 } 
  
 // metoda zwraca priorytet operatora
 public static int priorytet(String operator) {
  // dla + i - zwracamy 1
  if(operator.equals("+") || operator.equals("-")) return 1;
  // dla * i / zwracamy 2
  else if(operator.equals("*") || operator.equals("/")) return 2;
  // dla pozostałych 0
  else return 0;
 }
 
 // metoda zwraca nam łańcuch tekstowy z wyrażeniem w formie postfiksowej
 public String toString() {
  return wyrazeniePostfiksowe;
 }

 public static void main(String args[]) {

  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj wyrażenie infiksowe: " );
 
  // pobieramy od użytkownika wyrażenie
  String wyrazenie = sc.nextLine();

  // tworzymy nowy obiekt klasy OdwrotnaNotacjaPolska 
  // i przekazujemy do konstruktora pobrane od użytkownika wyrażenie
  OdwrotnaNotacjaPolska onp = new OdwrotnaNotacjaPolska(wyrazenie);

  // wyświetlamy wyrażenie w postaci postfiksowej
  System.out.println ("Wyrażenie postfiksowe: " + onp);
 }
}

Wynik działania aplikacji:

Podaj wyrażenie infiksowe: (4+2)*(3-1)
Wyrażenie postfiksowe: 4 2 + 3 1 - *

Dodatkowo możemy jeszcze sprawdzać poprawność nawiasów w podanym przez użytkownika wyrażeniu infiksowym (zobacz: Sprawdzanie poprawności nawiasów). W kolejnej części spróbujemy obliczyć wartość wyrażenia w postaci postfiksowej.

Klasa LinkedList - przykład zastosowania

2009-12-04T19:06:00.001+01:00

Klasa LinkedList jest jedną z klas bibliotecznych dostępnych w standardowej Javie. Jest to prosta implementacja listy powiązanej z wykorzystaniem typów generycznych (pisałem o nich tutaj Typy generyczne). Na jej bazie możemy napisać implementację w pełni dynamicznego stosu (inne sposoby tworzenia stosu to Stos - implementacja tablicowa oraz Lista powiązana - własna implementacja). Nasze rozwiązanie dzięki zastosowaniu typów generycznych umożliwi obsługę dowolnych obiektów.

// wykorzystujemy klasę LinkedList z pakietu java.util
import java.util.*;

/**
 * Stos - implementacja z wykorzystaniem klasy LinkedList
 * @author kodatnik.blogspot.com 
 */ 
public class Stos<E> {
 // lista przechowująca elementy stosu
 // wierzchołek stosu to ostatni element listy
 private LinkedList<E> lista;

 // konstruktor domyślny
 public Stos() {
  // tworzymy nowy obiekt klasy LinkedList
  lista = new LinkedList<E>();
 }
 
 // metoda odkładająca na stosie elementy
 public void push(E element) {
  // dodajemy element do listy
  lista.add(element);
 }

 // metoda ściąga ze stosu element
 public E pop() {
  // zwracamy element znajdujący się na końcu listy
  return lista.removeLast(); 
 }
 
 // metoda sprawdza czy stos jest pusty
 public boolean czyPusty() {
  // zwracamy prawdę lub fałsz
  return (lista.isEmpty());
 }
 
 // metoda "podgląda" co jest na wierzchołku stosu
 public E peek() {
  // zwracamy element z wierzchołka stosu (nie usuwamy go z listy)
  return lista.getLast();
 }
 
 // metoda wyświetla wszystkie elementy stanowiące stos
 public void wyswietl() {
  // wykorzystujemy metodę toString() z klasy LinkedList
  System.out.println(lista);
 }
 
 // metoda zwraca rozmiar stosu (liczbę jego elementów)
 public int rozmiar() {
  return lista.size(); 
 }
}

Poniżej przykładowe zastosowanie klasy Stos (przechowujemy na stosie łańcuchy tekstowe czyli obiekty klasy String).

public class TestujemyStos { 
 public static void main(String args[]) {
    
  // zakładamy nowy stos łańcuchów tekstowych
  Stos<String> s = new Stos<String>();
     
  // odkładamy kolejne elementy na stos
  s.push("Ala");
  s.push("Ola");
  s.push("Marcin");
     
  // wyświetlamy zawartość stosu
  s.wyswietl();

  // wyświetlamy element znajdujący się na szczycie (bez jego ściągania)
  System.out.println(s.peek());
     
  // ściągamy element ze stosu
  s.pop();     
      
  // wyświetlamy zawartość stosu
  s.wyswietl();    
      
  // wyświetlamy rozmiar stosu
  System.out.println (s.rozmiar());
 }
}

Uruchomiona aplikacja:

[Ala, Ola, Marcin]
Marcin
[Ala, Ola]
2

W oparciu o klasę LinkedList można utworzyć wiele innych struktur danych np. Kolejki czy też Drzewa.

Typy generyczne

2009-12-04T18:13:00.007+01:00

Java od wersji 1.5 obsługuje typy generyczne. Pozwalają one sparametryzować klasę, przez co nie ma konieczności dokonywania później kłopotliwego rzutowania. Sam zapis typu generycznego to duża litera/litery ujęta w nawiasy ostre. Utwórzmy prostą klasę Pudelko przechowującą elementy dowolnego typu.

/**
 * Wykorzystanie typów generycznych 
 * @author kodatnik.blogspot.com
 */
class Pudelko <T> {
 // referencja do obiektu typu T
 private T element; 

 // konstruktor klasy
 public Pudelko(T element) {
  this.element = element;
 } 

 // metoda zwraca referencję do przechowywanego elementu
 public T pobierzElement() {
  return element;
 }
}

Tworząc obiekt klasy Pudelko musimy określić jakiego typu dane będą w nim przechowywane. Przykładowe wykorzystanie klasy Pudelko.

public class TestPudelka {
 public static void main(String args[]) {
    
  // tworzymy trzy pudełka dla różnych typów danych (String, Integer oraz Double)
  Pudelko<String>  p1 = new Pudelko<String>("Ala ma kota");
  Pudelko<Integer> p2 = new Pudelko<Integer>(12);     
  Pudelko<Double>  p3 = new Pudelko<Double>(24.76);   
  
  // sprawdzamy zawartość każdego pudełka
  System.out.println (p1.pobierzElement());
  
  int wartosc = p2.pobierzElement() + 3;
  System.out.println (wartosc);
  
  System.out.println (p3.pobierzElement());    
 }
}

Wynik działania aplikacji (pudełko pierwsze przechowuje łańcuchy tekstowe, drugie liczby całkowite, a trzecie liczby rzeczywiste).

Ala ma kota
15
24.76

Większość klas dostarczanych z Javą wykorzystuje typy generyczne. Są to zazwyczaj klasy będące "pojemnikami" dla innych obiektów (tzw. kolekcje). Na przykład klasy LinkedList, Array, Stack, Vector, TreeMap itp.

Typy generyczne przeznaczone są tylko do typów obiektowych, nie można ich użyć do typów prymitywnych.

Piszemy gadżet do Bloggera - część 1

2009-11-26T16:38:00.003+01:00

Gadżety rozszerzają funkcjonalność naszych blogów. Dla platformy Blogger istnieje już kilkaset gotowych rozwiązań. Nic nie stoi na przeszkodzie, aby napisać samodzielnie taki gadżet. W kilku postach postaram się przybliżyć tematykę pisania gadżetów. Co będzie nam potrzebne:

edytor tekstu (z możliwością zapisu w formacie UTF-8, np. Windowsowy notatnik, Notepad++, czy PSPad),
serwer na którym zamieścimy nasz gadżet (np. Witryny Google, lub inny dowolny serwer z możliwością wgrywania plików),
podstawową znajomość HTML'a i JavaScriptu.

Struktura gadżetu

Gadżety do Bloggera tak samo jak pozostałe gadżety Googli składają się z plików XML (kod gadżetu, pliki językowe itd.). Podstawowa struktura gadżetu została przedstawiona poniżej.

<module>
 <moduleprefs title="Przykładowy gadżet"> 
  // pozostałe ustawienia
 <content type="html">
  <![CDATA[ 
   // zawartość HTML, JavaScript
  ]]>
 </content>
 </moduleprefs>
</module>

Pierwsza linia jest obowiązkowa i informuje o rozpoczęciu pliku w formacie XML. Pozostałe to tagi związane z gadżetami i tak:

tag <module> to oznaczenie, że plik będzie zawierał dane gadżetu,
tag <moduleprefs> zawiera dodatkowe informacje o gadżecie (autor, tytuł, lokalizacje, używane rozszerzenia itp.)
tag <content type="html"> informuje, że zawartością gadżetu będą polecenia HTML'a,
sekcja <![CDATA[ rozpoczyna właściwy kod HTML'a (czy JavaScript'u), który będzie wyświetlany przez gadżet,
]]> zamknięcie sekcji CDATA,
</content> - tag zamykający,
</module> - tag zamykający.

Utwórzmy prosty gadżet wyświetlający napis "Nasz pierwszy gadżet!". Dodatkowo w sekcji <moduleprefs> zamieścimy informacje o autorze. Po wpisaniu kodu do edytora zapiszmy go pod nazwą PierwszyGadzet.xml

<module>
 <moduleprefs author="Devon" title="Przykładowy gadżet"> 
 <content type="html">
  <![CDATA[ 
   Nasz pierwszy gadżet!
  ]]>
 </content>
 </moduleprefs>
</module>

Pozostaje opublikowanie go w sieci. Możemy wykorzystać do tego celu Witryny Googli (więcej informacji o zakładaniu witryny znajdziesz tutaj). Po opublikowaniu (adres mojego gadżetu to: http://sites.google.com/site/kodatnikfiles/xml/PierwszyGadzet.xml), możemy sprawdzić jego działanie. Logujemy się do Bloggera, przechodzimy na Układ/Elementy strony, klikamy Dodaj gadżet, wybieramy Dodaj swoje własne i wpisujemy adres URL naszego gadżetu.

Klikamy Dodaj wg adresów URL i jeśli wszystko przebiegło poprawnie powinniśmy otrzymać takie okienko:

Dajemy Zapisz i nasz gadżet pojawi się na blogu.

W następnych odcinkach pokaże jak skorzystać z dodatkowych opcji, zmienić kolory gadżetu (zgodnie z szablonem bloga), dostać się do danych bloga oraz utworzyć lokalizacje językowe.

Wszystkie gadżety, które utworzymy i dodamy do Bloggera są "cache'owane". Oznacza to, że zmiany które wprowadzimy w kodzie nie będą widoczne od razu w gadżecie (Google "trzyma" wersję zbuforowaną mniej więcej 2 godziny). Jeżeli chcemy sprawdzić od razu zmiany to możemy, albo wyłączyć buforowanie (trochę pracy - modyfikacja szablonu), albo zapisać gadżet pod inną nazwą na serwerze (np. DrugiGadzet.xml) i dodać go od nowa do naszego bloga.

Lista powiązana - własna implementacja

2009-11-26T01:02:00.001+01:00

Lista powiązana (ang. linked list) to struktura dynamiczna, której każdy element tak zwany węzeł (ang. node) posiada określoną wartość (lub wartości) oraz referencję do kolejnego węzła. Chcemy napisać prostą listę przechowującą wartości typu String (łańcuchy tekstowe). Pierwszą czynnością jest napisanie odpowiedniej klasy, na podstawie której będziemy tworzyć węzły.

/**
 * Węzeł - element listy 
 * @author kodatnik.blogspot.com
 */
class Wezel {
 // łańcuch tekstowy
 private String napis;
 // referencja do kolejnego elementu/węzła
 private Wezel nastepny;
 
 // konstruktor domyślny, "zerujemy" pola
 public Wezel() {
  this(null, null);
 }
 
 // konstruktor dwuparametrowy
 public Wezel(String napis, Wezel nastepny) {
  // przypisujemy polu napis wartość parametru
  this.napis = napis;
  // przypisujemy polu nastepny wartość parametru  
  this.nastepny = nastepny;
 }
 
 // metoda zwraca pole nastepny (dostępowa)
 public Wezel pobierzNastepny() {
  return nastepny;
 }
 
 // metoda ustawia pole nastepny (modyfikująca)
 public void ustawNastepny(Wezel nastepny) {
  this.nastepny = nastepny;
 }
 
 // metoda zwraca pole napis (dostępowa)
 public String pobierzNapis() {
  return napis;
 }

 // metoda ustawia pole napis (modyfikująca)
 public void ustawNapis(String napis) {
  this.napis = napis;
 } 
  
 // zwraca "węzeł" w formie łańucha tekstowego (pole napis)
 public String toString() {
  return napis;
 }
}

Mając gotową klasę dla węzłów, tworzymy klasę odpowiedzialną za prawidłowe funkcjonowanie listy. Nasza lista będzie listą jednostronną (dostęp możliwy tylko z jednego miejsca - początku listy).

/**
 * Lista powiązana 
 * Przykład listy jednostronnej, jednokierunkowej, 
 * przechowującej łańcuchy tekstowe 
 * @author kodatnik.blogspot.com
 */
public class ListaPowiazana {

 // początek listy
 private Wezel poczatek;
 // liczba elementów
 private int rozmiar;
 
 // konstruktor domyślny, "zerujemy" pola
 public ListaPowiazana () {
  poczatek = null;
  rozmiar = 0;
 }
 
 // metoda wstawia na początek listy nowy węzeł z wartością przekazaną jako parametr
 public void wstawNaPoczatek(String napis) {
  // tworzymy nowy węzeł oraz zmieniamy referencję początku listy
  poczatek = new Wezel(napis, poczatek);
  // zwiększamy rozmiar listy (liczbę elementów)
  rozmiar++;
 }
 
 // metoda usuwa i zwraca węzeł znajdujący się na początku listy
 public Wezel usunZPoczatku() {
  // jeśli lista jest pusta zwracamy null
  if(czyPusta()) return null;

  // zapamiętujemy referencję początku listy
  Wezel temp = poczatek;
  // zmieniamy referencję początku listy na następny węzeł
  poczatek = poczatek.pobierzNastepny();
  // zmniejszamy rozmiar listy
  rozmiar--;
  // zwracamy zapamiętany początek listy (usunięty węzeł)
  return temp; 
 }
 
 // metoda sprawdza czy lista jest pusta
 public boolean czyPusta() {
  // zwracamy prawdę lub fałsz
  return (poczatek == null);
 }
 
 // metoda czyści listę "zerując" pola
 public void wyczysc() {
  poczatek = null;
  rozmiar = 0;
 }
 
 // metoda zwraca rozmiar listy (liczbę jej elementów)
 public int pobierzRozmiar() {
  return rozmiar;
 }
 
 // metoda wyświetla zawartość listy
 public void wyswietl() {
  //zapamiętujemy początek listy
  Wezel temp = poczatek;
  // wyświetlamy komunikat
  System.out.print ("Początek -> ");
  // dopóki referencja jest różna od null
  while( temp != null ) {
   // wyświetlamy węzeł (zadziała metoda toString() z klasy Wezel)
   System.out.print (temp + " -> ");
   // przechodzimy do następnego węzła
   temp = temp.pobierzNastepny();
  }
  // wyświetlamy null (dla oznaczenia końca listy)
  System.out.println(temp);
 }
 
 // metoda zwraca listę w formie łańcucha tekstowego
 // inny sposób wyświetlenia listy
 public String toString() {
  // tworzymy zmienną przechowującą łańcuch wyjściowy
  String wyjscie = "";
  //zapamiętujemy początek listy
  Wezel temp = poczatek;
  // dopóki referencja jest różna od null  
  while( temp != null ) {
   // dodajemy zawartość węzła (zadziała metoda toString() z klasy Wezel) do zmiennej
   wyjscie +=  temp + " ";
   // przechodzimy do następnego węzła
   temp = temp.pobierzNastepny();
  }
  // zwracamy łańcuch tekstowy
  return wyjscie;
 }
}

Sprawdźmy działanie listy dodając do niej przykładowe elementy.

public class TestListyPowiazanej {
 public static void main(String args[]) {
    
  // tworzymy listę powiązaną
  ListaPowiazana lista = new ListaPowiazana();
 
  // dodajemy elementy do listy
  lista.wstawNaPoczatek("Kasia");
  lista.wstawNaPoczatek("Marek");  
  lista.wstawNaPoczatek("Dorota");   
  lista.wstawNaPoczatek("Olga");   
  // wyświetlamy listę
  lista.wyswietl();
  // wyświetlamy rozmiar listy
  System.out.println ("Liczba elementów listy: " + lista.pobierzRozmiar());
  // usuwamy jeden element
  System.out.println ("Usuwamy element: " + lista.usunZPoczatku());
  // wyświetlamy listę  
  lista.wyswietl();  
 }
}

Uruchomiona aplikacja:

Początek -> Olga -> Dorota -> Marek -> Kasia -> null
Liczba elementów listy: 4
Usuwamy element: Olga
Początek -> Dorota -> Marek -> Kasia -> null

Powyższą klasę możemy z powodzeniem wykorzystać do implementacji w pełni dynamicznego stosu. Rozwiązane z wykorzystaniem tablic przedstawiłem w poście: Stos - implementacja tablicowa.

Wieże Hanoi

2009-11-25T23:30:00.000+01:00

Wieże Hanoi to problem polegający na przełożeniu z jednego słupka, na drugi, dysków o różnej średnicy. Przy przekładaniu można posługiwać się dodatkowym słupkiem stanowiącym bufor. Nie można kłaść dysku o większej średnicy na dysk o mniejszej średnicy, ani przekładać więcej niż jednego dysku jednocześnie. Chcemy napisać aplikację, która zasymuluje nam kolejne kroki potrzebne do przełożenia dysków. Zastosujemy algorytm rekurencyjny.

// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Wieże Hanoi - rozwiązanie rekurencyjne
 * @author kodatnik.blogspot.com
 */
public class WiezeHanoi {
 
 // Rekurencyjna metoda przekładająca dyski o parametrach
 // dyski - liczba dysków
 // skad - oznaczenie słupka początkowego
 // dokad - oznaczenie słupka docelowego
 // bufor - oznaczenie słupka pomocniczego
 public static void hanoi(int dyski, char skad, char dokad, char bufor) {
  // jeśli są dyski
  if (dyski > 0 ) {
   // przenieś (rekurencyjnie) n-1 dysków ze słupka A na słupek B posługując się słupkiem C
   hanoi(dyski - 1, skad, bufor, dokad);
   // wyświetl przeniesienie dysku
   System.out.println(skad + " > " + dokad);
   // przenieś (rekurencyjnie) n-1 dysków ze słupka B na słupek C posługując się słupkiem A
   hanoi(dyski - 1, bufor, dokad, skad);
  }
 } 

 public static void main(String args[]) {
  
  Scanner sc = new Scanner(System.in);
  System.out.print ("Ile dysków chcesz przełożyć: " );

  // pobieramy od użytkownika liczbę dysków
  int n = sc.nextInt();     
     
  // wywołujemy metodę wyświetlającą kolejne przełożenia dysków
  // ze słupka A na słupek C korzystając ze słupka B
  hanoi(n , 'A', 'C', 'B');     
 }
}

Uruchomiona aplikacja:

Ile dysków chcesz przełożyć: 4
A > B
A > C
B > C
A > B
C > A
C > B
A > B
A > C
B > C
B > A
C > A
B > C
A > B
A > C
B > C

Problem Józefa Flawiusza

2009-11-20T23:13:00.004+01:00

Józef Flawiusz podczas wojny żydowsko-rzymskiej wraz 40 towarzyszami został otoczony przez Rzymian. Nie chcąc się poddać postanowili popełnić samobójstwo. Ustawili się w kręgu i co trzecia osoba odbierała sobie życie. Na końcu pozostał przy życiu przyjaciel Flawiusza oraz on sam. Oddali się w ręce wroga. Chcemy napisać aplikację, która zasymuluje nam, w jakiej kolejności ginęli żołnierze oraz, na której pozycji w kręgu ustawił się Flawiusz wraz ze swoim przyjacielem. Do rozwiązania tego problemu wykorzystamy przedstawioną wcześniej klasę Kolejka (Kolejka - implementacja tablicowa).

/**
 * Problem Józefa Flawiusza
 * @author kodatnik.blogspot.com
 */
public class JozefFlawiusz {
    
 public static void main(String[] args) {
  // zmienna przechowuje liczbę żołnierzy (Flawiusz + 40)
  int zolnierze = 41;
  // zmienna określa co który będzie ginął
  int coKtory = 3;

  // tworzymy kolejkę o rozmiarze równych liczbie żołnierzy
  Kolejka k = new Kolejka(zolnierze);
  
  // dodajemy żołnierzy do kolejki (od 1 do 41)
  for (int i = 1; i <= zolnierze; i++)
   k.dodaj(i);
            
  // w pętli dopóki kolejka nie jest pusta
  while ( !k.czyPusta() ) {
   // przestawiamy dwóch żołnierzy z początku na koniec kolejki
   for (int i = 0; i < coKtory - 1; i++)
    k.dodaj(k.usun());

   // eliminujemy trzeciego (usuwamy go z kolejki)
   // i wyświetlamy jego numer ekranie
   System.out.print(k.usun() + " ");
  } 
  System.out.println();
 }
}

Uruchomiona aplikacja:

3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41
7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31

Jak widać na wynikach generowanych przez program, Józef Flawiusz wraz z przyjacielem ustawili się na pozycji 16 i 31.