Program typu arkusz kalkulacyjny i szukanie cyklicznych odwołań do komórek

Witam!
Mam dosyć ogólne javowe pytanie. Otóż jestem w trakcie pisania aplikacji typu prosty arkusz kalkulacyjny. Program działa tak, że z pliku txt wczytywany jest owy arkusz w postaci (np.)

a1:10
a3:2
a4:2*a3
itp. Program jako wynik wypisuje do innego pliku obliczone wartości. Ale podobnie jak w normalnych programach (Excel i mu podobne) może wystąpić próba odwołania do tej samej komórki w innej komórce, przez co tworzy się "pętla", a to oczywiście jest bardzo niepożądane w przypadku arkuszy kalkulacyjnych ;)
I tutaj pojawia się mój problem. Jak wykorzystać dobrodziejstwa które udostępnia Java by móc w jakiś sposób poszukiwać tego typu cykliczne odwołania? Czy ktoś miałby jakiś pomysł?
Będę ogromnie wdzięczny za wskazówki.

Pozdrawiam!

Oznaczać w jakiś sposób już odwiedzone komórki. Np. tworzysz listę komórek, dodając do niej aktualnie obliczaną. Jeśli komórka była już na liście, to masz cykl.

Dzięki za odpowiedź!
Też zastanawiałem się nad takim rozwiązaniem ale chyba nie jest najdoskonalsze. Bo co w przypadku gdy inna komórka korzysta z danej komórki, a dodatkowo jeszcze inna z niej korzysta? Czyli przykładowo:

''a3:10
a5:5+a3
a1:a5+a3
''
Komórka a3 byłaby na liście dwa razy ale to nie oznaczałoby cyklu. Zastanawiałem się nad stworzeniem może czegoś w rodzaju grafu/drzewa ale jako (bardzo) poczatkujący użytkownik Javy nie mam pomysłu jak to zrealizować...

No tak, nie pomyślałem. W takim razie robisz dwie listy: komórki obliczone i komórki nieobliczone. Przy obliczaniu komórki najpierw wstawiasz ją w listę nieobliczonych, obliczasz rekurencyjnie dla wszystkich referencji, a potem wstawiasz w listę obliczonych i usuwasz z nieobliczonych. Jeśli komórka jest w obliczonych, to znaczy, że znowu się do niej odwołujemy, ale nie ma cyklu. Jeśli nie ma jej na żadnej liście, to obliczamy. Jeśli jest w nieobliczonych, to jest cykl.

Jest to taki sam problem co np. rozwiązywanie zależności (http://pl.wikipedia.org/wiki/Sortowanie_topologiczne).

Zamiast listy obliczonych możesz mieć od razu mapę komórka -> wartość, w której składowałbyś wyniki.
Wtedy: jeśli mamy już klucz, będący aktualną komórką, pobieramy wartość. Jeśli nie mamy, dodajemy do listy obliczanych i obliczamy, potem usuwamy z listy i dodajemy wartość do mapy. Jeśli już jest na liście, mamy cykl.

Hm, chyba nie jest to dla mnie do końca jasne. Odnośnie pierwszej części posta - co masz na myśli mówiąc "obliczasz rekurencyjnie dla wszystkich referencji"?
Bo rozumiem to tak, że napotykając jakąś komórkę przeszukuję gdzie jeszcze występuje i obliczam, tak? Ale w takim wypadku nie zawsze wiadomo czy dana komórka nie pojawi się w jakiejś innej komórce gdzie będzie zależna od innych. A popadając w rekurencję wykorzystującą rekurencję można źle skończyć :P Aczkolwiek nie wiem czy dobrze się rozumiemy w tym momencie.

Co do wspomnianej mapy, to właśnie wygooglowałem, że Java ma nawet jakieś specjalne struktury danych do tego typu rzeczy, więc chętnie bym z nich skorzystał bo wykorzystywanie wyłącznie list wydaje mi się w tym momencie dosyć topornym rozwiązaniem. Z tym, że widzę mapy to typy generyczne...jakoś ciężko mi się w nich odnaleźć :P
A mówisz dokładnie o TreeMap? Byłbym wdzięczny gdybyś mógł ubrać to we fragment kodu, mając jakąś podstawę byłoby to dla mnie bardzo pomocne :)

Pisząc "obliczasz rekurencyjnie dla wszystkich referencji" mam na myśli rekurencyjne (chociaż rzeczywiście rekurencyjne być nie musi, wszystko można zrobić w pętli) obliczenie wartości wszystkich innych komórek, do których dana komórka się odwołuje (a potem jej samej).

Typy generyczne to nic specjalnie trudnego, przeczytaj sobie choćby to: http://docs.oracle.com/javase/tutorial/java/generics/index.html
A tutaj o kolekcjach w Javie: http://docs.oracle.com/javase/tutorial/collections/index.html

Nie wiem tylko, w jaki sposób parsujesz i obliczasz wyrażenia w komórkach, więc kod będzie nieco abstrakcyjny:

public Wartość oblicz(Komorka komorka) {
    return oblicz(komorka, new LinkedList<Komorka>(), new HashMap<Komorka, Wartosc>());
}

private Wartosc oblicz(Komorka komorka, List<Komorka> obliczane, Map<Komorka, Wartosc> wartosciObliczone) {
    if (obliczane.contains(komorka) {
        throw new OdwolanieCykliczneException();
    }
    
    if (wartosciObliczone.containsKey(komorka)) {
        return wartosciObliczone.get(komorka);
    }
    
    obliczane.add(komorka);
    for (Komórka odwolanie : komorka.odwolania()) {
        oblicz(odwolanie, obliczane, wartosciObliczone);
    }
    obliczane.remove(komorka);

    Wartosc wartosc = komorka.wartoscDla(wartosciObliczone);
    wartosciObliczone.put(komorka, wartosc);
    
    return wartosc;
}

Wielkie dzięki Ci za pomoc! :)
Przyjrzę się temu dokładniej w wolnej chwili (bo teraz wolnych chwil zdecydowanie mi brakuje...) ale już widzę, że będzie to dla mnie bardzo pomocne.
W razie kolejnych pytań z pewnością jeszcze napiszę, aczkolwiek mam nadzieję, że udami się z tym uporać osobiście ;)
Pozdrawiam serdecznie!