# Abstract Data Types: Information Hiding

## Abstract Data Types

作者認為的良好的程式撰寫風格要盡量把物件的表示方式 (e.g., 資料型態組成方式) 隱藏 (封裝)，並且僅提供必要的操作介面 (抽象化)。

要做到這件事必然會提到 **abstract data type** (抽象化資料)，也就是將不是必須提供給使用者知道的資訊隱藏的物件 (資料型態)。

抽象化資料可以讓我們開發的程式具有彈性，因為僅提供必要資訊 (e.g., 各項操作的介面) 實際上代表著無論我們如何改變實作方式，只要程式執行結果與原先是相同的都不會影響到使用者。

* 不論未來要新增功能，或是改變實作方式以提升效能都不會影響到使用者，因為使用者使用的介面仍維持不變。

除了提供我們開發上的彈性以外，在只提供必要資訊的同時我們也把各項功能的實作獨立出來，也就是說我們把資料型態要提供的各個功能用類似 divide and conquer 的方式分開實作，

## An Example — Set

以下為一個使用資料抽象化概念實作的 set 例子:

/* Set.h */

#ifndef SET_H
#define SET_H
extern const void * Set;

void * add (void * set, const void * element);
void * find (const void * set, const void * element);
void * drop (void * set, const void * element);
int contains (const void * set, const void * element);
#endif

上方程式碼提供了我們正在使用的資料型態與相關操作介面

* 外部連結的 `Set` 變數: 透過變數名稱告訴使用者目前正在使用 set，實際上是帶有創建 set 物件所需的資訊。
* `void * add (void * set, const void * element)`: 將 element 加到 set 中，並回傳已經存在或是被加到 set 的 element。
* `void * find (const void * set, const void * element)`: 尋找 set 中是否有 element，有的話回傳，反之回傳 NULL。
* `void * drop (void * set, const void * element)`: 找到 set 中的 element 後將其移除。
* `int contains (const void * set, const void * element)`: 將 find() 的結果以 true/false 表示。

程式碼中大量使用 `void *`，這是因為它一方面可以去隱藏 set 實際實作的方式，另一方面它也讓我們幾乎可以傳遞任何東西到各個介面中，使我們的介面具有能應用在各種型態上的彈性。

* `void *` 會帶來一些安全上的問題，這部份的應對方式會在第八章做介紹。

### Memory Management

除了定義 set 的介面以外，我們還需要以下取得 set 物件的介面:

* `void * new (const void * type, ...)`: 接收描述型態資訊的描述符 (e.g., `Set`) 與用來初始化的不定數量參數，最後回傳指向資料表示方式與描述符相符的物件的指標。
* `void delete (void * item)`: 接收由 `new()` 產生的物件，並回收這個物件佔據的記憶體空間。

### Object

由於 set 裡面可能會包含各種我們有興趣的物件，因此提供以下資料型態與介面:

* `extern const void * Object`: 為了擴充性，因此用 `Object` 這個更大的集合 (不只是要放入 set 的 element，set 同樣也是一種物件)。
* `int differ (const void * a, const void * b)`: 用來比較物件是否相同。
* 這個函式可能會包含類似 `strcmp()` 的實作，也可能會透過回傳正負值來表示順序關係。

/* Object.h */

extern const void * Object; /* new(Object); */
int differ (const void * a, const void * b);

## An Application

下方為根據上面提供的介面撰寫的應用:

#include <stdio.h>

#include "new.h"
#include "Object.h"
#include "Set.h"

int main () { 
    void * s = new(Set);
    void * a = add(s, new(Object));
    void * b = add(s, new(Object));
    void * c = new(Object);
    
    if (contains(s, a) && contains(s, b))
        puts("ok");
    
    if (contains(s, c))
        puts("contains?");
        
    if (differ(a, add(s, a)))
        puts("differ?");
        
    if (contains(s, drop(s, a)))
        puts("drop?");
    
    delete(drop(s, b));
    delete(drop(s, c));
    
    return 0;
}

以下為應用程式執行流程:

1. 創建了一個 set，並且新增兩個物件給它。
2. 測試 contains() 的功能。
* 輸出 ok 代表正常。
* 物件 c 沒有被新增到 set 中，因此輸出 contains? 代表不正常。
3. 測試 differ() 功能，同時確保 add() 在新增重複物件時不會重複新增，並會回傳已存在的同物件。
4. 測試 drop() 功能，確保它有成功將回傳的物件從 set 移除。
5. 測試 delete() 功能，包括能正常釋放物件佔用空間以及能正確處理 null pointer。

## Implementation

實作的部分由於小弟我整理筆記的時候後面還有很多還沒看的章節，因此懶得重看這些比較瑣碎的部分。大家有興趣的話就麻煩自行去閱讀原作了🙏。

### An Implementation — Set
### Another Implementation — Bag

## Summary

為了程式在實作上具備更大的彈性，可以透過抽象化資料讓應用程式無法得知實作細節 (e.g., 資料型態的組成方式)。應用程式只可以透過存取包含用來提供資料型態資訊的 descriptor pointer 與使用並回傳 generic pointer (`void *`) 的相關操作介面。

* descriptor pointer 可以搭配 new() 來產生指向物件的指標，並且產生的物件可以透過 delete() 釋放。
* 通常 descriptor pointer 包含的資訊至少會有表示資料所需空間大小的資訊。