Tesseract源代码阅读:单链表 ELIST

该类的定义为:

class DLLSYM ELIST_LINK
{
    friend class ELIST_ITERATOR;
    friend class ELIST;

    ELIST_LINK *next;

public:
    ELIST_LINK() {
        next = NULL;
    }

    //constructor
    ELIST_LINK(                 //copy constructor
        const ELIST_LINK &) {   //dont copy link
        next = NULL;
    }

    void operator= (            //dont copy links
        const ELIST_LINK &) {
        next = NULL;
    }
};

这个类实际被作为链表的 "节点"。

可以看到，这个类的定义异常简单，数据成员只有一个同类型的指针，也没有定义除构造方法外的其他方法。而且在拷贝构造函数和赋值运算符重载中，直接忽略了传入的参数，从注释里也能明白，作者是将 "拷贝" 这个行为直接禁止了 —— 如果不显式定义拷贝构造函数的话，编译器会生成一个默认的拷贝构造函数，里面还是会进行拷贝操作的，赋值运算符重载同理。

不过令人疑惑的是，为什么这个 "节点" 类型里没有保存节点数据的成员呢?这个待会再说，不妨先保留着疑问吧。

该类的定义如下(出于简洁考虑，这里没有列出它内部的一些方法):

class DLLSYM ELIST
{
    friend class ELIST_ITERATOR;

    ELIST_LINK *last;           // End of list
    //(points to head)
    ELIST_LINK *First() {       // return first
        return last ? last->next : NULL;
    }

public:
    ELIST() {
        last = NULL;
    }

    bool empty() const {
        return !last;
    }

    // ......
};

正如之前所说，ELIST 中记录了链表的头节点，同时还定义、实现了一些链表层面的操作方法。

令人比较在意的是，ELIST 中表示头节点的成员的名称为 "last" ，而且名为 "First" 的私有方法也是返回这个头节点的 下一个节点 ，脱离上下文来看的话，可能会觉得别扭。不过其实 ELIST 实现的是一个单向循环链表，这里的 "last" 确实是指向了最后一个节点，而这最后一个节点又指向了第一个节点。

顾名思义，该类是 ELIST 类的 "迭代器" ，可以用来对 ELIST 进行遍历操作。该类的定义为:

class DLLSYM ELIST_ITERATOR {
    friend void ELIST::assign_to_sublist(ELIST_ITERATOR *, ELIST_ITERATOR *);

    ELIST *list;
    ELIST_LINK *prev;
    ELIST_LINK *current;
    ELIST_LINK *next;

    // 其他成员

public:
    ELIST_ITERATOR() {
        list = NULL;
    }

    ELIST_ITERATOR(ELIST *list_to_iterate);

    void set_to_list(ELIST *list_to_iterate);

    void add_after_then_move(ELIST_LINK *new_link);

    void add_after_stay_put(ELIST_LINK *new_link);

    ELIST_LINK *forward();

    ELIST_LINK *extract();

    // 其他方法
}

刚才提到，在表示节点的类型 ELIST_LINK 中其实是没有表示节点数据的成员的，如果直接使用，肯定是没有意义的 —— 实际上 Tesseract 中确实也没有哪儿直接就使用 ELIST 了。Tesseract 中通过多重继承来解决了这个问题。

比如说我们希望我们的节点中保存一个点的坐标，那么我们可以先定义一个 Point 类:

class Point
{
public:
    Point(): _x(0), _y(0) {}
    Point(int x, int y): _x(x), _y(y) {}
    ~Point();

private:
    int _x;
    int _y;
};

然后定义节点类 POINT ，继承 Point 和 ELIST_LINK:

class POINT: public ELIST_LINK, public Point
{
public:
    POINT();
    ~POINT();
};

然后依次定义 POINT_LIST(继承 ELIST) 和 POINT_IT(继承 ELIST_ITERATOR)。

在 Tesseract 中提供了两个宏来直接产生 POINT_LIST 类和 POINT_IT 类的定义与实现，这两个宏分别是:

• ELISTIZEH
• ELISTIZE

第一个宏用来产生 POINT_LIST 和 POINT_IT 的定义，第二个宏用来产生实现，其用法是(仍以 POINT 为例):

• 在 point.h 中类 POINT 的定义之后，添加以下语句:

  ELISTIZEH(POINT)
  

• 在 point.cpp 中，添加以下语句:

  ELISTIZE(POINT)
  

这两个宏也是在 ccutil/elst.h 中定义的。这种用宏来展开类定义和实现的做法，在代码编写上确实很方便，但是阅读起来真的是好头疼，刚开始了解这个单链表的时候，我为了找 BLOCK_LIST (继承自 ELIST 的单链表类)的定义头疼地要死，代码里找不着，Google 也搜索不到答案，着实费了一番功夫。

由于 Tesseract 的这个设计把链表的操作与对节点数据的操作分离开来了，所以虽然没使用多态机制，这一套设计依然工作良好。

之前说过，Tesseract 中有不少不同类型的单链表都是从 ELIST 继承的，由于对 ELIST 的继承都是在宏展开后进行的，从代码里是找不到这些类的定义的，不过链表节点却是要手动去定义、实现的，所以查看那些继承了 ELIST_LINK 类的类就可以知道了。从 Tesseract 的 API Refrence 可以得知有 20 个类继承自 ELIST_LINK，它们是:

• ASSOC
• BLOB_CHOICE
• BLOCK_RES
• C_BLOB
• C_OUTLINE_FRAG
• CHAR_SAMPLE
• CHAR_SAMPLES
• FPSEGPT
• FRAGMENT
• ICOORDELT
• MENU_L
• OUTLINE_FRAG
• PBLOB
• PIXROW
• REGION_OCC
• ROW
• ROW_RES
• SORTED_FLOAT
• WERD
• WERD_RES