接口、实现、多态

转载须注明出处：https://www.jianshu.com/u/5e6f798c903a

参考：《数据结构（Python 语言描述）》 - 第5章 接口、实现和多态

目录.jpg

在 C# 等静态语言中，我们会将"接口类型"简称为接口。但本文中提及的"接口"并非特指接口类型，而是以软件资源用户的视角，将软件资源为用户提供的各种操作视为接口。由于用户只关心如何使用方法，但并不关心其具体实现(这是类编写者的工作)，所以接口仅含方法名、参数以及文档注释。就 Python 而言，接口可理解为"类为用户提供的一组方法签名及其文档注释"。

使用 help 函数获取模块、数据类型、类、方法或函数的相关信息时，便会访问与该软件资源的接口相关的文档。比如通过 help() 获取 data types (或 classes) 的帮助文档时，可以看到一个 "Methods defined" 列表，其中包含了相关的接口。

class Cls:
    """测试类"""

    def func_1(self, argm: object) -> object:
        """方法 1"""
        return True

    def func_2(self, argm):
        """方法 2"""
        pass


help(Cls)

输出：

class Cls(builtins.object)
 |  测试类
 |  
 |  Methods defined here:
 |  
 |  func_1(self, argm:object) -> object
 |      方法 1
 |  
 |  func_2(self, argm)
 |      方法 2
 |  
 |  ----------------------------------------------------------------------
 |  Data descriptors defined here:
 |  
 |  __dict__
 |      dictionary for instance variables (if defined)
 |  
 |  __weakref__
 |      list of weak references to the object (if defined)

一个设计良好的软件资源，其特征之一便是可以清晰的区分接口和实现。当用户使用一个软件资源时，只需要关心其接口。理想情况下，这些软件资源如何实现的细节，也就是底层的算法代码和数据结构，都隐藏或封装在一个抽象的边界中。这个边界将接口和实现隔开，从而：

• 允许用户即插即用的方式，快速地将软件资源整合起来；
• 让用户有机会在相同软件资源的不同实现中做出选；
• 并允许具体实现者对软件资源的实现做出修改，而不影响其用户的代码。

多态(polymorphism)是指一个软件资源的多种实现，但这些实现都遵从相同的接口或方法。比如在两个不同的实现中都使用了相同的运算符符号或方法名，这便是多态。多态方法的示例是 str 和 len ；多态运算符的示例是 + 和 == 。

1. 接口类型

一些编程语言会提供接口(interface)类型，例如 C#。在接口类型中，我们会指定一组函数成员，但不会实现它们。因此，接口本身不会执行任何操作，它作用是为实现接口的类提供一套有关函数成员的蓝图。在创建类的过程中，必须依照接口提供的蓝图，逐一实现接口中的函数成员。

Tips：本小结中提及的"接口"表示接口类型，如 IIfc1 接口。

# 本例展示了在C#中声明和使用接口的过程
interface IIfc1{  // 声明接口
    void PrintOut(string s); // 不必实现函数体
}

class MyClass : IIfc1{ // 声明类，该类需要实现IIfc1接口
    public void PrintOut(string s){ // 实现接口
        Console.WriteLine("Calling through: {0}", s);
    }
}
class Program{
    static void Main(){
        MyClass mc = new MyClass(); // 创建类实例
        mc.PrintOut("object"); // 调用方法
    }
}

2. 伪接口类

Python 中并没有接口类型，如果我们需要事先为类提供一个蓝图，以说明类中所包含的操作，可创建一个伪接口类。伪接口类不会出现在继承链中，作用仅在于为类提供蓝图，用于说明类中所包含的操作，并确保操作和实现之间的一致性。

伪接口类通常以 "Interface" 为后缀，其中包含一组未实现的方法，所有方法都以 pass 或 return 结尾并包含文档字符串。pass 语句用于没有返回值的修改器方法；return 语句用于访问器方法，并返回一个简单的默认值，如 False 、0 或 None 。最后，还需要为所有方法添加文档字符串，以说明该方法所做的事情。

由于在之后的内容中，我们会为一种为名"包(bag)"的无需集合(collection)类型开发接口。所以，此处以包集合为例，创建一个伪接口类：

"""
File: baginterface.py
Author: Ken Lambert
"""

class BagInterface(object):
    """Interface for all bag types."""

    # Constructor 构造器
    def __init__(self, sourceCollection = None):
        """Sets the initial state of self, which includes the
        contents of sourceCollection, if it's present."""
        pass

    # Accessor methods 访问器方法
    def isEmpty(self):
        """Returns True if len(self) == 0, or False otherwise."""
        return True
    
    def __len__(self):
        """Returns the number of items in self."""
        return 0

    def __str__(self):
        """Returns the string representation of self."""
        return ""

    def __iter__(self):
        """Supports iteration over a view of self."""
        return None

    def __add__(self, other):
        """Returns a new bag containing the contents
        of self and other."""
        return None

    def __eq__(self, other):
        """Returns True if self equals other,
        or False otherwise."""
        return False

    # Mutator methods
    def clear(self):
        """Makes self become empty."""
        pass

    def add(self, item):
        """Adds item to self."""
        pass

    def remove(self, item):
        """Precondition: item is in self.
        Raises: KeyError if item in not in self.
        Postcondition: item is removed from self."""
        pass

在设计一个软件资源的伪接口类时，首先考虑要完成哪些操作，并依次给出文档字符串；然后，依据文档字符串的描述来给出恰当的函数签名。

3. 开发基于 BagInterface 的实现

下面来为包集合开发两种基于 BagInterface 的实现。

在集合类的设计者获知了集合的伪接口类之后，类自身的设计和实现包含两个步骤：

1. 选择一个恰当的数据结构来包含集合中的项，并确定用于表示集合状态的其它数据，将这些数据赋给 __init__ 方法中的实例变量(也有可能使用类变量)。
2. 完成接口中指定方法的代码

注意：伪接口类的作用仅是为实现提供蓝图，不必也不需要继承伪接口类。

3.1 基于数组的实现

本节将基于 BagInterface 开发一个基于数组的实现，这里使用名为 Array 的数组类，代码如下：

"""
File: arrays.py

An Array is a restricted list whose clients can use
only [], len, iter, and str.

To instantiate, use

<variable> = array(<capacity>, <optional fill value>)

The fill value is None by default.
"""

class Array(object):
    """Represents an array."""

    def __init__(self, capacity, fillValue = None):
        """Capacity is the static size of the array.
        fillValue is placed at each position."""
        self._items = list()
        for count in range(capacity):
            self._items.append(fillValue)

    def __len__(self):
        """-> The capacity of the array."""
        return len(self._items)

    def __str__(self):
        """-> The string representation of the array."""
        return str(self._items)

    def __iter__(self):
        """Supports iteration over a view of an array."""
        return iter(self._items)

    def __getitem__(self, index):
        """Subscript operator for access at index."""
        return self._items[index]

    def __setitem__(self, index, newItem):
        """Subscript operator for replacement at index."""
        self._items[index] = newItem

a. 构造器方法

from arrays import Array

class ArrayBag(object):# 不必继承BagInterface
    """An array-based bag implementation."""

    # Class variable
    DEFAULT_CAPACITY = 10

    # Constructor
    def __init__(self, sourceCollection = None):
        """Sets the initial state of self, which includes the
        contents of sourceCollection, if it's present."""
        self._items = Array(ArrayBag.DEFAULT_CAPACITY)
        self._size = 0 # _size表示逻辑尺寸，len(Array)表示物理尺寸
        if sourceCollection:
            for item in sourceCollection:
                self.add(item)
    # --snip--

b. 无需使用数组变量的方法

当需要访问(或修改)实例变量时，应尽可能通过相应的方法来完成操作，将对变量的引用保持最小化。比如当我们需要查看包实例的逻辑尺寸时，应该运行 len()，而不是直接使用实例变量 _size。

这样做的优点是，例如某个方法没有使用数组变量，那么即使将数组变为其它数据结构，也无需对该方法做出修改，可继续使用。

class ArrayBag(object):
    # --snip--
    # Accessor methods
    def isEmpty(self):
        """Returns True if len(self) == 0, or False otherwise."""
        return len(self) == 0
    
    def __len__(self):
        """Returns the number of items in self."""
        return self._size

    def __str__(self):
        """Returns the string representation of self."""
        return "{" + ", ".join(map(str, self)) + "}"

    def __eq__(self, other):
        """Returns True if self equals other,
        or False otherwise."""
        if self is other: return True
        if type(self) != type(other) or \
           len(self) != len(other):
            return False
        for item in self:
            if not item in other:
                return False
        return True
    # --snip--

c. 需要使用数组变量的方法

如果将数组变为其它数据结构，则会影响到使用数组变量的方法。因为，数据结构的改变可能会导致操作方式的变化。

class ArrayBag(object):
    # --snip--
    # Accessor methods
    def __iter__(self):
        """Supports iteration over a view of self."""
        cursor = 0
        while cursor < len(self):
            yield self._items[cursor] # 使用数组变量
            cursor += 1

    def __add__(self, other):
        """Returns a new bag containing the contents
        of self and other."""
        result = ArrayBag(self) # 使用数组变量，不一定是类变量
        for item in other:
            result.add(item)
        return result
    
    # Mutator methods
    def clear(self):
        """Makes self become empty."""
        self._items = Array(ArrayBag.DEFAULT_CAPACITY) # 使用数组变量
        self._size = 0 

    def add(self, item):
        """Adds item to self."""
        # Check array memory here and increase it if necessary
        # 附加练习：如果数组已满，需要编写额外的代码以调整数组大小
        self._items[len(self)] = item # 使用数组变量
        self._size += 1

    def remove(self, item):
        """Precondition: item is in self.
        Raises: KeyError if item in not in self.
        Postcondition: item is removed from self."""
        # Check precondition and raise if necessary
        if not item in self:
            raise KeyError(str(item) + " not in bag")
        # Search for the index of the target item
        targetIndex = 0
        for targetItem in self:
            if targetItem == item:
                break
            targetIndex += 1
        # Shift items to the left of target up by one position
        for i in range(targetIndex, len(self) - 1):
            self._items[i] = self._items[i + 1] # 使用数组变量
        # Decrement logical size
        self._size -= 1
        # Check array memory here and decrease it if necessary
        # 附加练习：如果删除了多个项，可能会造成内存的浪费。
        # 编写代码，当数组的装载因子达到某个阈值时，自动调整数组的大小

3.2 基于链表的实现

本节将基于 BagInterface 开发一个基于链表的实现，这里使用名为 Node 的链表类，代码如下：

"""
File: node.py
Author: Ken Lambert
"""

class Node(object):
    """Represents a singly linked node."""

    def __init__(self, data, next = None):
        self.data = data
        self.next = next

a. 构造器方法

"""
File: linkedbag.py
Author: Ken Lambert
"""

from node import Node

class LinkedBag(object):
    """A link-based bag implementation."""

    # Constructor
    def __init__(self, sourceCollection = None):
        """Sets the initial state of self, which includes the
        contents of sourceCollection, if it's present."""
        self._items = None # 外部头链接，初始值None表明链表为空
        self._size = 0 # 逻辑尺寸
        if sourceCollection:
            for item in sourceCollection:
                self.add(item)
    # --snip--

b. 可拷贝的方法

如果某个方法没有访问数组变量，它也就不必访问链表变量。所以那些 ArrayBag 类中没有访问数组变量的方法，可直接拷贝到 LinkedBag 中。这是之前的策略——当需要访问(或修改)实例变量时，应尽可能通过相应的方法来完成操作，将对变量的引用保持最小化——带来的回报。也是编写方法的重要一环：尽可能尝试着将数据结构隐藏到对象的方法调用之中，以使得通过调用相应的方法便可完成对数据结构的操作(always try to hide the implementing data structures behind a wall of method calls on the object being implemented.)。

以下方法没有访问数组变量，可直接拷贝到 LinkedBag 中：

class LinkedBag(object):
    # --snip--
    # Accessor methods
    def isEmpty(self):
        """Returns True if len(self) == 0, or False otherwise."""
        return len(self) == 0
    
    def __len__(self):
        """Returns the number of items in self."""
        return self._size

    def __str__(self):
        """Returns the string representation of self."""
        return "{" + ", ".join(map(str, self)) + "}"

    def __eq__(self, other):
        """Returns True if self equals other,
        or False otherwise."""
        if self is other: return True
        if type(self) != type(other) or \
           len(self) != len(other):
            return False
        for item in self:
            if not item in other:
                return False
        return True
    # --snip--

c. 需要使用链表变量的方法

class LinkedBag(object):
    # --snip--
    # Accessor methods
    def __iter__(self):
        """Supports iteration over a view of self."""
        cursor = self._items
        while not cursor is None:
            yield cursor.data
            cursor = cursor.next
            
    def __add__(self, other):
        """Returns a new bag containing the contents
        of self and other."""
        result = LinkedBag(self) # 改动
        for item in other:
            result.add(item)
        return result
    
    # Mutator methods
    def clear(self):
        """Makes self become empty."""
        # Exercise
        self._items = None  # 外部头链接，初始值None表明链表为空
        self._size = 0  # 逻辑尺寸

    def add(self, item):
        """Adds item to self's head."""
        # 在列表头部添加新项，从而利用了常数访问时间的优点
        self._items = Node(item, self._items)
        self._size += 1

    def remove(self, item):
        """Precondition: item is in self.
        Raises: KeyError if item in not in self.
        Postcondition: item is removed from self."""
        # Check precondition and raise if necessary
        if not item in self:
            raise KeyError(str(item) + " not in bag")
        # Search for the node containing the target item
        # probe will point to the target node, and trailer
        # will point to the one before it, if it exists
        probe = self._items
        trailer = None
        for targetItem in self:
            if targetItem == item:
                break
            trailer = probe
            probe = probe.next
        # Unhook the node to be deleted, either the first one or one
        # thereafter
        if probe == self._items:
            self._items = self._items.next
        else:
            trailer.next = probe.next
        # Decrement logical size
        self._size -= 1
    # --snip--