位元詩人 [Objective-C] 程式設計教學:具有型別安全的多型

Facebook Twitter LinkedIn LINE Skype EverNote GMail Yahoo Email

前言

由於 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,確保多型物件的行為合乎我們的期待,讓程式更加安全與強健。

關於作者

身為資訊領域碩士,位元詩人 (ByteBard) 認為開發應用程式的目的是為社會帶來價值。如果在這個過程中該軟體能成為永續經營的項目,那就是開發者和使用者雙贏的局面。

位元詩人喜歡用開源技術來解決各式各樣的問題,但必要時對專有技術也不排斥。閒暇之餘,位元詩人將所學寫成文章,放在這個網站上和大家分享。