具有型別安全的多型

    前言

    由於 Objective-C 有萬用物件型別 id,而且訊息也是在程式執行期才動態 binding,即使不用多型的手法,也可以自然地讓 Objective-C 程式具有多型的特性。

    但在預設情形下,Objective-C 程式的動態行為不具有型別安全性。本文會利用 Objective-C 的 protocol 建立具有型別安全的多型。如果想要在 Objective-C 中模擬泛型程式,同樣用本文的方式實作即可。

    基本上,Objective-C 的 protocol 類似於 Java 的 interface,使用時機也差不多。

    類別的公開界面

    在本文中,我們以有序串列為例,來實現 Objective-C 的多型。為了節省文章板面,我們不會實作有序串列所有的抽象資料結構 (ADT),只會實作少量訊息。

    有序串列在推入資料時,需要藉由資料的內部順序 (order) 來決定資料放入的位置。所以,我們希望傳入有序串列的物件能夠自行排序。

    在 Objective-C 的做法,是使用 protocol 來規範物件應該滿足的訊息。當 protocol 所宣告的訊息無法滿足時,編譯器會發出警告,提醒程式設計師該去實作 protocol 所宣告的訊息。藉由這個過程達成型別安全的多型。

    Objective-C 沒有規範用來比較物件大小的 protocol,所以我們就自己宣告一個 protocol 如下:

    /* compare.h */
    #pragma once
    
    @protocol Compare
    -(int) compareTo: (id) obj;
    @end
    

    訊息 compareTo 的作用相當於三元運算子,會根據兩物件的關係傳回大於零、等於零、小於零的整數。在 protocol 中沒有規定實際的回傳值,在實作訊息時自行決定即可。

    Protocol 本身是公開訊息的宣告,不處理實作。實作的部分由繼承 protocol 的類別來滿足。

    另外來看一下有序串列的公開界面:

    /* ordered_list.h */
    #pragma once
    
    #import <Foundation/Foundation.h>
    #include <stdbool.h>
    #import "compare.h"
    
    typedef struct list_data_t list_data_t;
    
    @interface OrderedList : NSObject {
        list_data_t *data;
    }
    
    -(OrderedList *) initByAscending;
    -(OrderedList *) initByDescending;
    -(void) release;
    -(bool) isEmpty;
    -(id) shift;
    -(bool) push: (id<Compare>) obj;
    @end
    

    我們有兩個建構子訊息:

    -(OrderedList *) initByAscending;
    -(OrderedList *) initByDescending;
    

    因為我們在初始化有序串列時,要決定該串列是遞增還是遞減排序,而且在決定後不應更動,以免打亂有序串列的內部順序。所以我們刻意用兩個訊息來區隔排序方式。

    和多型有關的行為在推入資料時發生:

    -(bool) push: (id<Compare>) obj;
    

    我們不限制 obj 的型別,但我們希望傳入的 obj 能滿足 Compare protocol,故我們用 id<Compare> 來標註型別資訊。藉此滿足多型和型別安全兩方面的需求。

    擴展 NSNumber 類別的訊息

    在本範例中,我們使用整數當成推入有序串列的資料,因為整數本身就具有順序。但整數是基礎型別,而非物件,不能直接推入範例程式的串列中。Objective-C 的解決方法是幫整數等基礎型別另外製作 box 類別,利用物件把這些基礎型別用物件包裝起來。在這一點上 Objective-C 和 Java 採用類似的解決方式。

    Objective-C 已經有內建的 box 類別了,使用 NSNumber 類別即可。由於 NSNumber 是內建類別,我們用 category 擴展 NSNumber 可應對的公開訊息。這算是轉個彎繼承 NSNumber 類別。參考以下的 category 程式碼:

    /* my_number.h */
    #pragma once
    
    #import <Foundation/Foundation.h>
    #import "compare.h"
    
    @interface NSNumber (Compare)
    -(int) compareTo: (id) obj;
    @end
    

    以及實作的部分:

    /* my_number.m */
    #import <Foundation/Foundation.h>
    #import "my_number.h"
    
    @implementation NSNumber (Compare)
    -(int) compareTo: (id) other {
        NSComparisonResult cmp = [self compare: other];
        
        if (NSOrderedAscending == cmp)
            return -1;
        else if (NSOrderedSame == cmp)
            return 0;
        else
            return 1;
    }
    @end
    

    其實 NSNumber 本身就可以用 compare 訊息來比較物件大小。然而,日後我們用其他物件推入我們的有序串列時,該物件不一定能回應 compare 訊息。所以,我們不在串列的實作中寫死 compare 訊息,而另外訂出新的 protocol,確保編譯器能幫我們檢查物件。

    類別內部的實作

    在本節中,我們來看有序串列的實作。

    串列內部會用到儲存物件的節點 (node),所以我們宣告結構體 node_t 及其建構函式:

    typedef struct node_t node_t;
    
    struct node_t {
        id data;
        node_t *prev;
        node_t *next;
    };
    
    node_t * node_new(id obj)
    {
        node_t *n = \
            (node_t *) malloc(sizeof(node_t));
        if (!n)
            return n;
        
        n->data = obj;
        n->prev = NULL;
        n->next = NULL;
        
        return n;
    }
    

    有序串列的 data 本身是 opaque pointer,藉此滿足封裝的特性。以下是 data 的結構體宣告:

    struct list_data_t {
        node_t *head;
        node_t *tail;
        bool isAscending;
    };
    

    我們在前文提過,範例程式初始化時會根據遞增或遞減有不同的建構子訊息:

    -(OrderedList *) initByAscending;
    -(OrderedList *) initByDescending;
    

    但兩者除了 isAscending 這個旗標的狀態相異外,兩者初始化的過程基本上是相同的。所以我們用 category 另外宣告私有的 init 訊息:

    @interface OrderedList ()
    -(OrderedList *) init;
    @end
    

    init 訊息的實作如下:

    -(OrderedList *) init
    {
        if (!self)
            return nil;
    
        data = \
            (list_data_t *) malloc(sizeof(list_data_t));
        if (!data) {
            [self release];
            self = nil;
            return self;
        }
    
        data->head = NULL;
        data->tail = NULL;
        
        return self;
    }
    

    有了共通的 init 訊息後,在建構子訊息中,只要處理旗標 isAscending 的部分即可。這裡以 initByAsending 為例:

    -(OrderedList *) initByAscending {
        if (!self)
            return nil;
    
        self = [self init];
    
        data->isAscending = true;
    
        return self;
    }
    

    我們在初始化時有用到純 C 的 malloc() 函式,在實作 release 訊息時就要撰寫相對應的 free() 函式:

    -(void) dealloc
    {
        if (!self)
            return;
    
        if (!data) {
            [super dealloc];
            return;
        }
    
        node_t *p = NULL;
        node_t *q = data->head;
    
        while (q) {
            p = q;
            q = q->next;
    
            [p->data release];
            free((void *)p);
        }
    
        [super dealloc];
    }
    

    有序串列的關鍵功能在於推入資料時會加上排序的動作,之後要取出資料時資料會自動按順序排好。推入資料的過程比較複雜,我們先講解過程,等等讀者可自行對照程式碼。

    推入資料時,串列可能有三種狀態:

    • 串列本身為空
    • 串列只有單一物件
    • 串列已有多個物件

    當串列為空時,可能的推入位置是唯一的,直接推入即可。

    當串列有單一物件時,要判斷該物件和推入物件的順序,以決定要推入串列的頭端或尾端。

    當串列有多個物件時,可能的情境再細分如下:

    • 推入串列頭端
    • 推入串列尾端
    • 推入串列其他的位置

    我們會用額外的兩個指標走訪串列內的節點,根據不同情境採用不同方式操作。至於操作的細節屬於資料結構的範圍,和 Objective-C 的特性無關,故請有興趣的讀者自行閱讀以下範例程式碼:

    /* ordered_list.m */
    #include <stdlib.h>
    #import "ordered_list.h"
    
    /* Private fields. */
    typedef struct node_t node_t;
    
    struct node_t {
        id data;
        node_t *prev;
        node_t *next;
    };
    
    node_t * node_new(id obj)
    {
        node_t *n = \
            (node_t *) malloc(sizeof(node_t));
        if (!n)
            return n;
    
        n->data = obj;
        n->prev = NULL;
        n->next = NULL;
    
        return n;
    }
    
    struct list_data_t {
        node_t *head;
        node_t *tail;
        bool isAscending;
    };
    
    /* Private messages. */
    @interface OrderedList ()
    -(OrderedList *) init;
    @end
    
    @implementation OrderedList
    -(OrderedList *) initByAscending
    {
        if (!self)
            return nil;
    
        self = [self init];
    
        data->isAscending = true;
    
        return self;
    }
    
    -(OrderedList *) initByDescending
    {
        if (!self)
            return nil;
    
        self = [self init];
    
        data->isAscending = false;
    
        return self;
    }
    
    -(OrderedList *) init
    {
        if (!self)
            return nil;
    
        data = \
            (list_data_t *) malloc(sizeof(list_data_t));
        if (!data) {
            [self release];
            self = nil;
            return self;
        }
    
        data->head = NULL;
        data->tail = NULL;
    
        return self;
    }
    
    -(void) dealloc
    {
        if (!self)
            return;
    
        if (!data) {
            [super dealloc];
            return;
        }
    
        node_t *p = NULL;
        node_t *q = data->head;
    
        while (q) {
            p = q;
            q = q->next;
    
            [p->data release];
            free((void *)p);
        }
    
        [super dealloc];
    }
    
    -(bool) isEmpty
    {
        return NULL == data->head;
    }
    
    -(id) shift
    {
        NSAssert(![self isEmpty], @"Empty list\n");
    
        id obj = data->head->data;
    
        if (data->head == data->tail) {
            free(data->head);
    
            data->head = NULL;
            data->tail = NULL;
        }
        else {
            node_t *p = data->head;
            data->head = p->next;
            free(p);
            data->head->prev = NULL;
        }
    
        return obj;
    }
    
    -(bool) push: (id<Compare>) obj
    {
        node_t *node = node_new(obj);
        if (!node)
            return false;
    
        if (!data) {
            free(node);
            return false;   
        }
    
        if (!(data->head)) {
            data->head = node;
            data->tail = node;
    
            return true;
        }
    
        if (data->head == data->tail) {
            if ((data->isAscending && ([obj compareTo: data->head->data] <= 0))
                || (!data->isAscending && ([obj compareTo: data->head->data] >= 0))) {
                node->next = data->head;
                data->head->prev = node;
                data->head = node;
            }
            else {
                data->tail->next = node;
                node->prev = data->tail;
                data->tail = node;
            }
    
            return true;
        }
    
        node_t *p = NULL;
        node_t *q = data->head;
        while (q && q->next) {
            if ((data->isAscending && ([obj compareTo: q->data] <= 0))
                || (!data->isAscending && ([obj compareTo: q->data] >= 0))) {
                if (!p) {
                    node->next = data->head;
                    data->head->prev = node;
                    data->head = node;
                }
                else {
                    p->next = node;
                    node->prev = p;
    
                    q->prev = node;
                    node->next = q;
                }
    
                break;
            }
    
            p = q;
            q = q->next;
        }
    
        if (q == data->tail) {
            if ((data->isAscending && ([obj compareTo: q->data] <= 0))
                || (!data->isAscending && ([obj compareTo: q->data] >= 0))) {
                p->next = node;
                node->prev = p;
    
                q->prev = node;
                node->next = q;
            }
            else {
                data->tail->next = node;
                node->prev = data->tail;
                data->tail = node;
            }
        }
    
        return true;
    }
    @end
    

    使用該類別的外部程式

    最後,我們用簡單的外部程式來看如何使用這個有序串列:

    /* main.m */
    #import <Foundation/Foundation.h>
    #include <stdio.h>
    #import "compare.h"
    #import "my_number.h"
    #import "ordered_list.h"
    
    int main(void)
    {
        NSAutoreleasePool* pool = [[NSAutoreleasePool alloc] init];
        if (!pool)
            return 1;
        
        OrderedList *lt = \
            [[[OrderedList alloc] initByAscending] autorelease];
        if (!lt) {
            perror("Failed to allocate list\n");
            goto ERROR;
        }
        
        NSArray *data = [NSArray arrayWithObjects:
            [NSNumber numberWithInt: 4],
            [NSNumber numberWithInt: 5],
            [NSNumber numberWithInt: 1],
            [NSNumber numberWithInt: 3],
            [NSNumber numberWithInt: 2],
            nil
        ];
        for (id n in data) {
            if (![lt push: n]) {
                perror("Failed to push data\n");
                goto ERROR;
            }
        }
        
        int a = [[lt shift] intValue];
        while (![lt isEmpty]) {
            int b = [[lt shift] intValue];
            
            if (!(a < b)) {
                fprintf(stderr, "Wrong order: %d %d\n", a, b);
                goto ERROR;
            }
            
            a = b;
        }
        
        [pool drain];
    
        return 0;
    
    ERROR:
        [pool drain];
        
        return 1;
    }
    

    一開始,建立串列物件 lt。接著,用陣列實字建立陣列 data。然後用 for 迴圈逐一推入串列 lt

    最後,我們逐一取出物件,在取出的過程中逐一檢查物件間的關係,確認物件總是保持遞增關係。

    編譯此範例程式

    當我們在 Mac 上用 Clang 編譯此程式時,由於 Cocoa 的路徑是已知的,所以指令比較簡短:

    $ clang -o list my_number.m ordered_list.m main.m -lobjc -framework Foundation
    

    相對來說,當我們在類 Unix 系統上用 GCC 編譯此程式時,由於 GNUstep 往往不在標準路徑上,所以要在參數中加上 GNUstep 相關的路徑:

    $ gcc -std=c11 -o list my_number.m ordered_list.m main.m -lobjc -lgnustep-base -I /usr/include/GNUstep -L /usr/lib/GNUstep -fconstant-string-class=NSConstantString
    

    同樣地,如果在類 Unix 系統上使用 Clang 編譯此程式時,也要加上 GNUstep 相關路徑。此外,還要加上 Objective-C 低階實作的路徑:

    $ clang -std=c11 -o listDemo my_number.m ordered_list.m main.m -lobjc -lgnustep-base -I /usr/include/GNUstep -I /usr/lib/gcc/x86_64-linux-gnu/7/include -L /usr/lib/GNUstep -fconstant-string-class=NSConstantString
    

    結語

    原本 Objective-C 就是動態語言,我們不需要在程式中刻意使用多型的手法。但我們仍然會適度地加上相關的 protocol,確保多型物件的行為合乎我們的期待,讓程式更加安全與強健。

    電子書籍

    如果你覺得這篇 Objective-C 的技術文章對你有幫助,可以看看這本 Objective-C 程式設計電子書:

    多平台 Objective-C 程式設計

    【分享本文】
    Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Yahoo
    【追蹤本站】
    Facebook Facebook Twitter Parler