Soyut veri tipleri (ADT) ve kapsülleme

Bir programın karmaşıklığıyla başa çıkmanın yolu soyutlama (abstraction): bir varlığın sadece o an önemli olan özelliklerini görmek, gerisini gizlemek. Alt programlar process abstraction’dır (sıralama algoritmasını bilmeden sort çağırırsın). Bu hafta ikincisi: data abstraction, yani abstract data type (ADT). Sınavda kavramsal sorular (ADT’nin iki koşulu, information hiding’in faydası, dil karşılaştırmaları) ve bir ADT’yi kullanan kodun çıktısı sorulur.

Altın kurallar:

1. ADT = gizli temsil + tek birimde tanımlanmış tip ve işlemler.
2. Kullanıcı sadece arayüzü görür. İçeriyi değiştirmek kullanıcı kodunu bozmaz.
3. Yığın LIFO, kuyruk FIFO. Çıktı sorularında içeriği her adımda yaz.
4. Parametreli ADT tip hatalarını derlemede yakalar.

Abstract data type

Kullanıcı tanımlı bir tip, iki koşulu sağlıyorsa ADT’dir:

1. Temsil gizli: tipin nesnelerinin iç yapısı, tipi kullanan birimlerden gizlidir. Kullanıcı nesnelere sadece tipin tanımladığı işlemlerle erişir.
2. Tek birim: tipin bildirimi ve üzerindeki işlemlerin protokolleri tek bir sözdizimsel birimde yer alır. Diğer birimler bu tipten değişken yaratabilir.

Aslında float da bir ADT gibi: bitlerin nasıl dizildiğini bilmeden + ve * kullanırsın. Kullanıcı tanımlı ADT’ler aynı rahatlığı programcının tiplerine getirir.

Information hiding’in faydaları:

• Reliability: kullanıcı nesnenin iç durumunu bozamaz (yığının top alanını rastgele bir değere çekemez).
• Değiştirilebilirlik: temsil değişirse (dizi yerine bağlı liste) kullanıcı kodu değişmez, çünkü sadece arayüze bağlı.
• Daha az isim çakışması ve daha küçük, yönetilebilir birimler.

Java’da ADT: sınıf

static class IntStack {
    private int[] items = new int[10];
    private int top = -1;
    public void push(int x) { items[++top] = x; }
    public int pop() { return items[top--]; }
    public int peek() { return items[top]; }
    public boolean isEmpty() { return top == -1; }
}

IntStack s = new IntStack();
s.push(3); s.push(7); s.pop(); s.push(2); s.push(9);
System.out.println(s.pop() + s.peek());

11

işlem      yığın (alt → üst)
push 3     [3]
push 7     [3, 7]
pop        [3]          (7 döndü)
push 2     [3, 2]
push 9     [3, 2, 9]
pop        [3, 2]       (9 döndü)
peek                    (2, silinmez)  → 9 + 2 = 11

Dışarıdan s.top = 5; ya da a.balance = 5000; yazmak derleme hatası verir:

error: balance has private access in Account

Java’da erişim düzeyleri: private (sadece sınıf), paket erişimi (belirtilmezse: aynı paket), protected (paket + alt sınıflar), public. Erişim sınıf düzeyindedir: bir Money nesnesi başka bir Money nesnesinin private alanını okuyabilir.

Immutable ADT

static final class Money {
    private final int cents;
    Money(int c) { cents = c; }
    Money add(Money o) { return new Money(cents + o.cents); }
    int cents() { return cents; }
}
Money m1 = new Money(150);
Money m2 = m1.add(new Money(75));
System.out.println(m1.cents() + " " + m2.cents());

150 225

Değişmeyen nesneler paylaşılabilir; aliasing sorunları (bir yerden değiştirilip başka yerden şaşırma) ortadan kalkar. Java’nın String’i de böyle.

Arayüz ile temsil ayrı

List<Integer> nums = new ArrayList<>(List.of(4, 1, 3));
List<Integer> view = Collections.unmodifiableList(nums);
try { view.add(5); } catch (UnsupportedOperationException e) { System.out.println("UnsupportedOperationException"); }
nums.add(5);
System.out.println(view.size());

UnsupportedOperationException
4

Diğer dillerde ADT

Ada’da specification package’ın private kısmı derleyicinin görmesi için oradadır (nesnenin boyutunu bilmesi gerekir) ama kullanıcı oradaki alanlara erişemez. Temsili tamamen gizlemek için tip bir pointer olarak bildirilir, gösterdiği yapı body’de tanımlanır.

C++‘ta destructor nesnenin ömrü bitince otomatik çağrılır ve heap’te ayırdığı belleği geri verir. Yaratılışın tersi sırasıyla çalışırlar. Java’da benzer bir sıra try-with-resources’ta görülür:

try (Res r1 = new Res("A"); Res r2 = new Res("B")) {
    System.out.print("body ");
}

open A open B body close B close A

Parametreli ADT’ler

Eleman tipi ne olursa olsun aynı işi yapan bir yığın yazmak istiyorsun. Parameterized ADT (generic class) tip parametresi alır:

List<Integer> xs = new ArrayList<>();
xs.add("five");

error: no suitable method found for add(String)

C++ template’leri her farklı tip için ayrı kod üretir (derlemede örnekleme). Java generics tek bir kod kullanır ve tip bilgisi derlemeden sonra silinir (type erasure); bu yüzden new T() yazılamaz.

Büyük programlar için kapsülleme

ADT tek bir tipi kapsüller. Binlerce sınıflı bir sistemde ilgili tipleri ve alt programları gruplamak, ayrı derlemek ve isim çakışmalarını önlemek gerekir.

• C: başlık dosyası (.h, arayüz) + uygulama dosyası (.c). Derleyici iki dosyanın tutarlılığını garanti etmez.
• C++, C#: namespace. std::cout gibi nitelikli isimler ya da using.
• Java: package. Paket hem isim alanı hem erişim birimidir: belirleyicisi olmayan üyeler paket içinde görünür.
• Ada: package’lar iç içe ve ayrı derlenebilir.
• Ruby: module.

Sık yapılan hatalar

IntStack s = new IntStack();   // push, pop, peek on an int array
s.push(3); s.push(7); s.pop(); s.push(2); s.push(9);
System.out.println(s.pop() + s.peek());

IntStack t = new IntStack();
for (int i = 1; i <= 4; i++) t.push(i * i);
int sum = 0;
while (!t.isEmpty()) { int v = t.pop(); if (v % 2 == 0) sum += v; }
System.out.println(sum);

Queue2<String> q = new Queue2<>();
q.enqueue("a"); q.enqueue("b"); q.dequeue(); q.enqueue("c");
System.out.println(q.dequeue() + q.size());

class Account {
    private int balance = 100;
    public int getBalance() { return balance; }
}
// in another class:
Account a = new Account();
a.balance = 5000;

// Res(String n) prints "open n", close() prints "close n"
try (Res r1 = new Res("A"); Res r2 = new Res("B")) {
    System.out.print("body ");
}

List<Integer> xs = new ArrayList<>();
xs.add("five");

static final class Money {
    private final int cents;
    Money(int c) { cents = c; }
    Money add(Money o) { return new Money(cents + o.cents); }
    int cents() { return cents; }
}
// in main:
Money m1 = new Money(150);
Money m2 = m1.add(new Money(75));
System.out.println(m1.cents() + " " + m2.cents());

List<Integer> nums = new ArrayList<>(List.of(4, 1, 3));
List<Integer> view = Collections.unmodifiableList(nums);
try { view.add(5); }
catch (UnsupportedOperationException e) { System.out.println("UnsupportedOperationException"); }
nums.add(5);
System.out.println(view.size());