coding►设计模式

设计模式（一）

开始

找出应用中可能需要变化之处，把它们独立出来，不要和那些不需要变化的代码混在一起。针对接口编程，而不是针对实现编程。少用继承，多用组合。 良好的OO设计必须具备 可复用、可扩充、可维护 三个特性，模式可以让我们构建出具有良好OO设计质量的系统。

策略模式 定义了算法族，分别封装起来，让它们之间可以互相替换，此模式让算法的变化独立于使用算法的客户。

计算机科学►编译原理

flex & bison 实现语法解析

简述

flex/lex 和 bison/yacc 是 linux 下用来生成词法分析器和语法分析器的工具。flex和lex、bison和yacc 数据同质的程序，相对于flex和lex，bison和yacc之间兼容性更好。

工具介绍

bison

Bison是一个通用解析器生成器，可以将带注释的上下文无关语法，转换为使用LALR解析表的确定性 LR 或广义LR（GLR）解析器。可熟练运用bison后，可以用它开发各种语言解析器。

Bison向上兼容Yacc，所有正确编写的Yacc语法都可与Bison一起工作，无需修改。

yacc

Yacc（Yet Another Compiler Compiler）是一个用来生成编译器的编译器。yacc 生成的编译器主要是用C语言写成的语法解析器（parser），需要与词法解析器（lex）一起使用，再把两部分产生出来的C程序一并编译。

Yacc的输入是巴克斯范式（BNF）表达的语法规则，以及语法规约的处理代码，输出的是基于表驱动的编译器，包含输入的语法规约的处理代码部分。

Yacc是开发编译器的工具，采用LALR语法分析方法。

lex

在计算机科学里面，lex是一个产生词法分析器的程序。Lex常与 yacc 语法分析器产生程序（parser generator）一起使用。

flex

flex 是一个词法分析器，用于生成扫描器，识别文本中词汇模式。

编译器

一个语言编译器或解释器，通常分解为两个部分：

  • 读取源文件并发现其中的结构
  • 处理他的结构等，生成目标程序

Lex 和 Yacc 可以生成代码片段，解决第一个任务。发现源文件结构的任务可以分解为子任务：

  • 分解词法源文件为 tokens（Lex）
  • 找到程序的层次结构（Yacc）

语法

lex 词法分析器

lex通过扫描词法源文件，从中提取token，可看做关键词。lex工具会生成一个 yylex 函数，语法解析器通过调用这个函数获取信息。lex的输入文件一般会被命名为 *.l 文件，通过 [f]lex XX.l 得到文件 lex.yy.c。

语法格式

Lex程序主要由一系列带有指令的正则表达式组成，这些指令确定了正则表达式匹配后相应的动作（action）。由flex生成的词法分析器可以读取输入，匹配输入与所有的正则表达式，并执行每次匹配后适当的关联动作。

Flex程序包含是哪个部分，通过 %% 分隔。第一部分包含声明和选项设置，第二部分是一系列的模式和动作，第三部分是会被拷贝到生成的词法分析器里面的C代码，通常是与动作代码相关的程序。

1
2
3
4
5
Definition section
%%
Rules section
%%
C code section

第一部分

在声明部分，%{ 和 %} 之间的代码会被原样照抄到生成的 C 文件的开头部分。

第二部分

每个模式处在一行的开头处，接着是模式匹配时所需要执行的 C 代码，这里的 C 代码是使用 {} 括住的一行或者多行语句。模式必须在行首出现，flex会把空白开始的行当做代码复制到生成C程序中。

文本统计示例

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
%{
int chars = 0;
int words = 0;
int lines = 0;
%}

%%
[a-zA-Z]+   { words++; chars += strlen(yytext) }
\n          { chars++; lines++; }
.           { chars++; }
%%

int main(int argc, char **argv) {
  yylex();
  printf("%8d%8d%8d\n", lines, words, chars);
  return 0;
}

在这个示例中，末尾的C代码为主程序，负责调用flex提供的词法分析程序yylex()，并输出结果。

编译

1
2
3
$ flex flex-wc.l					# 运行命令后会生成文件 lex.yy.c
$ cc -lfl -o wc lex.yy.c 	# 编译词法解析
$ ./wc

注：对于使用命令将 flex 安装到系统，可以直接执行上述命令。如若将 flex 编译至特定目录，并使用的话，需要制定库环境变量，以使程序可正确运行。

1
2
3
4
5
6
7
8
9
10
11
12
$ export FLEX_BIN_PATH="/.../bin"    # flex 程序路径
$ export FLEX_LIB_PATH="/.../lib"    # flex 库文件路径
$ export LD_LIBRARY_PATH=${FLEX_LIB_PATH}    # 用于 linux 系统
$ export DYLD_LIBRARY_PATH=${FLEX_LIB_PATH}	 # 用于 mac os 系统
$ export PATH="$FLEX_BIN_PATH:$PATH"
# 编译执行
$ flex flex-wc.l
$ cc -L"${LIB_PATH}" -lfl -o wc lex.yy.c		
$ ./wc
hello world
^D
       1       2      12

示例说明

该实例程序，仅使用 flex 实现。首先，按照 flex 的语法，定义了词法文件 wc.l，其中包含 3 个模式 [a-zA-Z]+、\n 、. ，分别用于匹配单词、换行、任意字符。这里需要注意，模式匹配具有排他性，输入被一个模式匹配，则不会重复被其他模式匹配，因此在匹配到单词后，需要使用 chars += strlen(yytext) 来修正字符统计值。然后，使用 flex 程序解析 wc.l ，生成 lex.yy.c 文件。最后，编译生成的文件，并执行。

yacc / bison 语法分析器

语法分析器，借助 lex 生成的 token，将关键字组合成语法。语法分析器会生成一个 yyparse 函数，这个函数会不断调用词法分析器生成的 yylex 函数来得到 token 信息。词法分析器输入的源文件一般命名为 *.y ，通过命令 yacc -d XX.y 得到文件 y.tab.h 和 y.tab.c ，前者包含了 lex 需要的 token 类型定义，需要被 include 进 *.l 文件中。

flex & bison

单纯的 flex 程序，可以解决简单的解析问题，但对于复杂的场景，需要语法分析器的支持。flex 仅解析输入中的模式，并执行相应的动作，对于复杂的语法需要语法分析器的支持。

计算器示例

接下来，用一个计算器程序示例，展示 flex 和 bison 是如何一起工作。简单些，我们首先实现一个 flex 程序，可以复述（无需解析运算符优先级及计算）简单的表达式。

1
2
3
4
5
6
7
8
9
10
11
%%
"+" { printf("PLUS\n"); }
"-" { printf("MINUS\n"); }
"*" { printf("TIMES\n"); }
"/" { printf("DIVIDE\n"); }
"|" { printf("ABS\n"); }
[0-9]+ { printf("NUMBER %s\n", yytext); }
\n  { printf("NEW LINE\n"); }
[ \t] { }
.   { printf("Mystery character %s\n", yytext); }
%%

编译运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$ flex cal.l
$ cc -o cal lex.yy.c
$ ./cal
12+34
NUMBER 12
PLUS
NUMBER 34
NEW LINE
5 6 / 7q
NUMBER 5
NUMBER 6
DIVIDE
NUMBER 7
Mystery character q
NEW LINE

上述程序，只是简单识别了我们的意图，并执行了打印操作。为了让我们的示例更像一个计算器，我们需要支持类似于真正的计算，并支持运算符的优先级等特性。对于这种高阶解析，需要借助 bison 来完成。

flex 作为词法分析器，可以生成一个 token 流，方便语法分析器处理。当程序需要一个 token 时，通过调用 yylex() 来读取一小部分输入，然后返回相应的记号，通过再次调用 yylex() 获取更多 token。

token 编号和 token 值

flex 返回 token 时，实际包含两部分，token 编号和 token 值。这里的编号是一个较小的随意整数，如果返回 0 则意味着文件的结束。当 bison 创建一个语法分析器时， bison 自动地从 258 起指派每个记号编号，并且创建一个包含这些编号定义的 .h 文件。在这里，我们在 flex 程序中，为每个 token 分配一个固定的编号。重写上面计算器的 flex 源文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
%{
enum yytokentype {
    NUMBER = 258,
    ADD = 259,
    SUB = 260,
    MUL = 261,
    DIV = 262,
    ABS = 263,
    EOL = 264,
    POW = 265
};
int yylval;
%}

%%

"+" { return ADD; }
"-" { return SUB; }
"*" { return MUL; }
"/" { return DIV; }
"|" { return ABS; }
"^" { return POW; }
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
\n  { return EOL; }
[ \t] { }
.   { printf("Mystery character %c\n", *yytext); }

%%

/*int main(int argc, char **argv)
{
    int tok;
    while (tok = yylex()) {
        printf("%d", tok);
        if (tok == NUMBER) printf(" = %d\n", yylval);
        else printf("\n");
    }
}*/

继续编译运行。

1
2
3
4
5
6
7
8
9
10
11
$ $ flex cal.l
$ cc -o cal lex.yy.c
$ ./cal
a / 34 + |45
Mystery character a
262
258 = 34
259
263
258 = 45
264

至此，我们有了一个可以返回特定 token 编号及 token 值的词法解析器，接下来关注其如何与语法分析器一起工作。

语法分析器

语法分析器的作用是，找出输入记号之间的关系，一种常见的关系表达式就是语法分析树。

BNF文法

为了编写一个语法分析器，需要一定的方法描述语法分析器所使用的把一系列记号转化为语法分析书的规则。在计算机最常用的语言就是上下文无关文法（Content-Free Grammar，CFG），书写上下文无关文法的标准格式就是 BackusNaur范式（BackusNaur Form，BNF）。

幸运的是，BNF相当简单。对于表达式 1 * 2 + 3 * 4 + 5 ，下面的 BNF 语法足以处理。

1
2
3
4
<exp> ::= <factor>
	| <exp> + <factor>
<factor> ::= NUMBER
	| <factor> * NUMBER

每一行就是一条规则，用来说明如何创建语法分析树的分支。::= 被解读为 是 或 变成；| 为 或者，创建同类分支的另一种方式。规则左边的名称是语法符号。大致来说，所有的记号都被认为是语法符号，但是有一些语法符号并不是记号。

有效的BNF总是带有递归性的，规则会直接或者间接地指向自身。这些简单的规则被递归地使用以匹配任何极端复杂的加法和乘法序列。

bison 规则描述语言

bison 规则基本符合 BNF 文法，下面是计算器程序的 bison 代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
%{
#include <stdio.h>
#include <math.h>
int yylex();
void yyerror(char *s);
%}

/* 声明 Tokens; 在这里的声明要和 cal.l 声明的 yytokentype 顺序一致 */
%token NUMBER
%token ADD SUB MUL DIV ABS EOL
%token POW

%%

calclist: /* 空规则 */
	| calclist exp EOL { printf("= %d\n", $2); }
	;

exp: factor
	| exp ADD factor { $$ = $1 + $3; }
	| exp SUB factor { $$ = $1 - $3; }
	;

factor: term
    | factor MUL term { $$ = $1 * $3; }
    | factor DIV term { $$ = $1 / $3; }
    | term POW term   { $$ = pow($1, $3); }
    ;

term: NUMBER
    | SUB NUMBER   { $$ = -$2 }
    | ABS term ABS { $$ = $2 >= 0 ? $2 : -$2; }
    ;

%%

int main(int argc, char **argv)
{
    yyparse();
    return 0;
}

void yyerror(char *s)
{
    fprintf(stderr, "error: %s\n", s);
}

bison 程序包含了与flex程序相同的三部分结构：声明部分、规则部分和C代码部分。

声明部分， %{ 和 %} 之间内容同样会被拷贝进代码，%token 用于声明标记，以便让 bison 语法分析程序知晓符号。没有声明为记号的语法符号，应该出现在至少一条规则的左边。

规则部分，包含了BNF定义的规则，使用分号分隔不同规则。每条规则中的每个语法符号都有一个语义值，目标符号（冒号左边符号）的值使用 $$ 代替，右边语法符号的语义值分别用 $1、$2 ... 代替。

联合 bison & flex 编译

1
2
3
4
5
6
7
8
9
10
11
12
$ bison -d cal.y
$ flex cal.l
$ gcc -Wno-parentheses -o calc cal.tab.c lex.yy.c -lfl
$ ./calc   # 执行
1 + 2
= 3
3 - -2
= 5
1 + -2
= -1
1 + |-1|
= 2

高级语法

flex

正则表达式

表达式 说明 实例
[] 字符类，匹配方括号内任意一个字符 [a-z]、[\^a-c]
[a-z]{-}[jv] 去除字符类中某些字符 -
^ 匹配行首 -
$ 匹配行尾 -
{} {5} {1,5}
\ 转义
* 匹配0个或多个前面的表达式
+ 匹配1个或多个前面的表达式
? 匹配0个或1个前面的表达式
| 选择操作符，匹配前或后的表达式 foo|bar
“…” 引号内解释为字面常量
() 把一系列正则表达式组成一个新的正则表达式
/ 尾部上下文，匹配斜线前的表达式，但是要求其后紧跟着斜线后的表达式

解析文件

词法分析器总是从 yyin 读取输入，可以通过重新设定 yyin 实现从文件读取。也可以使用 yyrestart 指定输入源，此外，yyrestart 可以重置解析，并通过调用 yylex 重新开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
%option noyywrap

%{
int chars = 0;
int words = 0;
int lines = 0;
%}

%%

[a-zA-Z]+   { ++words; chars += strlen(yytext); }
\n          { ++chars; ++lines; }
.           { ++chars; }

%%

int main(int argc, char **argv) {
    yyin = fopen("wc.in", "r");
    // yyrestart(fopen("wc.in", "r"));  // 也可以使用 yyrestart 指定输入源
    yylex();
    printf("%8d%8d%8d\n", lines, words, chars);
}

输入

flex 词法分析器支持从文件或标准输入读取数据，flex 提供将数据预读取到缓冲区的机制，提高效率，行为大致如下。

1
2
3
4
5
6
YY_BUFFER_STATE bp;
extern FILE* yyin;
... // 第一次调用语法分析器之前所需要做的事情
if (!yyin) yyin = stdin;
bp = yy_create_buffer(yyin, YY_BUF_SIZE); // YY_BUF_SIZE 由 flex 定义，通常 16k
yy_switch_to_buffer(bp);

通过如下宏定义，可重新定义用于输入到缓冲区的宏。

1
#define YY_INPUT(buf, result, max_size) ...

每当词法分析器的输入缓冲区为空时，就会调用 YY_INPUT，buf 是缓冲区，max_size 是缓冲区大小，result 则用来放置实际读取的长度。

输出

默认没有匹配的输入，都会被拷贝到 yyout 中，通过默认添加如下规则实现。

1
2
. ECHO
#define ECHO fwrite(yytext, yyleng, 1, yyout)

上面代码，定义一个规则 . 用于匹配所有未被识别的输入，并执行默认的行为 fwrite(yytext, yyleng, 1, yyout)。

option

flex 在文件头部通过 %option 定义选项。

1
%option noyywrap nodefault yylineno case-insensitive
选项 说明
noyywrap
nodefault 屏蔽默认行为
yylineno 定义变量 yylineno，保存当前行号
case-insensitive 生成大小写无关的词法分析器
yyclass 指定 scanner 的类名
c++ 生成c++代码
debug

bison

flex 可以识别正则表达式，bison 可以识别语法。flex 把输入流分解为若干个片段，而bison则分析这些记号并给予逻辑进行组合。

%token

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 规则
%token <type> name "string-literal"
  
// 示例
%token NUM 300    // 为 token 指定数字编码
%token XNUM 0x12d // a GNU extension
%union {              /* define stack type */
  double val;
  symrec *tptr;
}
%token <val> NUM      /* define token NUM and its type */
  
// 为 token 指定字符常量
%token ARROW "=>"     /* yylex 可通过 token 名称和 字符常量来获取 toKen 类型编码 */

%union

%union 用于指定语义值的类型集合，定义语法和 c 中的 union 类似。

1
2
3
4
%union {
  double val;
  symrec *tptr;
}

上述声明，声明有两个可选类型 double 和 symrec *，并给定名字 val 和 tptr ，这些名字用在 %token 、 %nterm 和 %type 声明中，为终结符和非终结符指定类型。

1
%token <val> expr stmt   // 声明 expr、stmt 类型名称为 val，即 double

%type

每个语义值（即 $$）都有其类型，默认为 int，可以通过如下方式借助 bison api 修改默认语义值类型。

1
2
%define api.value.type {double}
%define api.value.type {struct semantic_type}

也可通过定义宏 YYSTYPE 借助编译器修改，值得注意的是，Bison并不知道 YYSTYPE 的值，甚至不知道其是否定义，因此无法提供部分支持。

1
%define YYSTYPE double

当使用 %union 指定多值类型时，必须为每个要指定值的非终结符声明值类型。这是通过 %type 声明完成的，类似于如下。

1
%type <type> nonterminal...

这里的 nonterminal 是非终结符的名字，type 是 %union 中声明的可选类型名称。

%code

在指定位置插入代码。

1
2
3
%code [place] {
  ... code ...
}

[place] 用于指定位置，可选项有 top、provides 、requires ，对应的位置分别为文件的顶部、在YYSTYPE与YYLTYPE定义之前和之后。

%defines

生成解析器头文件，包含语法中定义的标记种类名称的定义及其它一些声明。如果解析器实现文件名为 name.c ，则解析器头文件名称为 name.h ，可通过 %define api.header.include 重新设定文件名。

%define

1
2
3
4
$define variable
$define variable value
$define variable {value}
$define variable "value"

variable

variable 说明 默认 示例
api.filename.type 文件名称在 location 和 position 中的类型 const std::string
api.namespace 为 parser 类指定 namespace
api.parser.class 为 parser 类指定类名
api.value.type 语义值类型

api.value.type

取值 适用语言 说明
union-directive c，c++ 使用 %union 直接定义，无需指定 api.value.type
union c，c++ 这种方式通过在定义token是指定，比如%token <int> INT "integer" ，大多数c++对象不能保存在union中，使用 variant 代替
variant c++ 类似于 union，但是适用于允许任意类型的 c++ 对象
{type} - 自定义类型 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
%code requires
{
  struct my_value
  {
    enum
    {
      is_int, is_str
    } kind;
    union
    {
      int ival;
      char *sval;
    } u;
  };
}
%define api.value.type {struct my_value}   // 使用自定义类型
%token <u.ival> INT "integer"
%token <u.sval> STR "string"

默认类型：

  • 如果定义 %union ，则是 union-directive
  • 如果使用类型标签（%token <type> ...），则是指定类型
  • 否则为 undefined

%parse-param

定义解析器参数，比如。

1
%parse-param {int *nastiness} {int *randomness}

那么像如下方式，调用解析器。

1
2
3
4
5
6
{
  int nastiness, randomness;
  …  /* Store proper data in nastiness and randomness. */
  value = yyparse (&nastiness, &randomness);
  …
}

在语法的action中，像如下使用变量。

1
exp: …    { …; *randomness += 1; … }

下面的定义。

1
%parse-param {int *randomness}

会生成如下签名。

1
2
void yyerror (int *randomness, const char *msg);
int  yyparse (int *randomness);

如果 %define api.pure full 和 %locations 被使用，那么签名会如下所示。

1
2
void yyerror (YYLTYPE *llocp, int *randomness, const char *msg);
int  yyparse (int *randomness);

%locations

使用 %locations 时，c++解析器支持位置追踪，具体参照这里。

参考

linux►程序

awk

说明

  • 默认按空白符分隔（\s+），多个连续空白符不切分

  • 列数从 1 开始

打印

1
2
# 打印
ls -l | awk '{print $5}'   # 打印第 5 列

统计

1
2
# 统计大小
ls -l | awk '{sum+=$5}END{print sum/1024/1024"MB"}'
play►os x

黑苹果安装

说明

不定期更新装黑苹果的流程和问题处理，提供两个具体的基于 OpenCore 的 config.plist。

流程

该流程基于 OpenCore，使用 Mac OS，config.plist 主要参考 这里，具体流程如下。

下载镜像

  • 百度搜索 黑果小兵，找下最新的系统镜像

制作启动盘

  • 如果无需制作多启动优盘，使用 etcher 写入即可
  • 如果需要制作多启动优盘，需要使用命令，参考 这里 制作

配置 OpenCore

异常

whatevergreen: failed to route IsTypeCOnlySystem

whatevergreen 报 failed to route IsTypeCOnlySystem 异常，如果是使用集显，需要调整 device-properties。

DSDT_HPET.aml

Dell Optiplex 7050 使用 OpenCore 0.6.5 安装 Big Sur (11.1) 后，板载声卡无法识别，Lilu.kext + AppleALC.kext 换各种 layout-id 无解。后参考这篇帖子，需要 fix Comment-IRQ，如果使用 Clover 的话，在 ACPI 勾选 FixHPET、FixIPIC 、 FixRTC 、FixTMR 即可，使用 OpenCore 的话，略微麻烦。

首先，获取机器的 DSDT.aml ，参考这篇文章 ，我使用 UEFI Shell 方式，需要下载 acpidump.efi ，和 OpenShell.efi（在下载的 OpenCore 中） 一并放入 /EFI/OC/Tools 下面，并在 config.plist 的 Misc -> Tools 下面启用，具体参考文章。重启，在引导界面进入 Open Shell，输入如下命令。

1
2
3
4
5
6
shell> fs0: // 替换为实际分区，进入OpenShell后会有分区提示
fs0:\> dir  // 查看分区文件，确认选的分区是否正确
   Directory of fs0:\
   01/01/01 3:30p EFI
fs0:\> cd EFI\OC\Tools   
fs0:\EFI\OC\Tools> acpidump.efi -b -n DSDT -z

运行完上面命令后，会在EFI分区生成多个 *.dat 文件，我们把 dsdt.dat 拿出来，重命名为 DSDT.aml。

然后，使用工具生成 SSDT-HPET.aml 文件。下载工具 SSDTTime，双击 SSDTTime.command 运行，选择 FixHPET - Patch Out IRQ Conflicts ，把生成好的 DSDT.aml 拖入终端，按照提示操作，最后会生成四个文件。

1
2
3
4
patches_Clover.plist
patches_OC.plist
SSDT-HPET.aml
SSDT-HPET.dsl

接下来，需要做的是拷贝文件和Patch，把 SSDT-HPET.aml 拷贝至 EFI/OC/ACPI 文件夹下，并用 OpenCore Configurator 打开 patches_OC.plist，把 ACPI 项内的数据复制至我们自己的 config.plist 中。

至此，大功告成。可解决 ALC255/ALC3243 声卡无法识别问题。

coding►设计模式

设计模式（一）之策略模式

目录

  • 引言
  • 观察者模式

引言

设计模式系列，主要参考 《Head First 设计模式》 一书。

模拟鸭子

有这样一个需求，需要设计模拟鸭子游戏，游戏中有多种鸭子，鸭子都会叫和游泳，但是有不同的外观。简单的，我们采用 继承 来实现。首先，定义抽象类 Duck。

1
2
3
4
5
6
7
8
9
10
11
public abstract class Duck {
    public void quack() {
        System.out.println("quack quack!");
    }

    public void swim() {
        System.out.println("I am swimming!");
    }

    abstract void display();
}

基于基类Duck，我们创造绿头鸭和红头鸭。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 绿头鸭
public class MallardDuck extends Duck {
    @Override
    void display() {
        System.out.println("green head");
    }
}

// 红头鸭
public class RedHeadDuck extends Duck {
    @Override
    void display() {
        System.out.println("red head");
    }
}

会飞的鸭子

基于上面的鸭子，我们还需要添加会飞的技能。借助继承，我们在基类中添加飞行方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public abstract class Duck {
    public void quack() {
        System.out.println("quack quack!");
    }

    public void swim() {
        System.out.println("I am swimming!");
    }

    public void fly() {
        System.out.println("I am flying!");
    }

    abstract void display();
}

但是，可怕的事情发生了。在添加橡皮鸭的时候，竟然会飞！因为疏于设计，导致局部的修改，影响到了所有的鸭子对象。该怎么办呢？试下 覆盖 吧，在橡皮鸭中，实现飞行方法，覆盖父类行为，但是什么都不做。

1
2
3
4
5
6
7
8
9
10
11
12
public class RubberDuck extends Duck {

    @Override
    public void fly() {
        // do nothing
    }

    @Override
    void display() {
        System.out.println("I am rubber duck");
    }
}

似乎，解决了问题。是不是可以使用接口呢，只有会飞的鸭子才实现此接口。

但是如此，重复代码会增加，因为对同样的行为需要重复实现，比如需要对所有呱呱叫的鸭子，需要在 quack 方法中实现呱呱叫的行为。

问题归零，来重新设计。继承不能很好地解决问题，因为鸭子的行为在不断的改变，并且让鸭子实现具有所有行为是不合理的。接口 不具有具体实现，所以继承接口无法实现代码复用。

找出应用中可能需要变化之处，把它们独立出来，不要和那些不需要变化的代码混在一起。 把会变化的部分取出并封装，好让其他部分不受影响。依据此原则，把鸭子的行为从 Duck 类中抽取出来。把 Duck 类中的 fly 和 quack 会随鸭子不同而变化的行为，从 Duck 类中分开。

我们希望设计具有弹性，可以指定行为到鸭子实例。可以把鸭子的行为放在分开的类中，专门提供某行为接口的实现。**针对接口编程，而不是针对实现编程。**利用接口代表每个行为，比如 FlyBehavior 和 QuackBehavior ，行为的每个实现都将实现其中的一个接口。这次，鸭子类不负责实现 Flying 和 Quacking 接口，由我们制造一组其他类专门实现 FlyBehavior 和 QuackBehavior，这称为行为类。

针对接口编程真正的意思是针对超类型 (supertype)编程。利用多态，程序可以针对超类型编程，执行时会根据 实际状况执行到真正的行为。

1
2
3
4
5
6
7
8
9
10
11
// 针对实现编程
Dog d = new Dog( ); 
d.bark( );

// 针对接口/超类型编程
Animal animal = new Dog( ); 
animal.makeSound( ); 

// 行时指定具体实现
Animal a = getAnimal( );
a.makeSound( );

最终的实现如下。

至此。

少用继承，多用组合。

策略模式 定义了算法族，分别封装起来，让它们之间可以互相替换，此模式让算法的变化独立于使用算法的客户。

要点 良好的OO设计必须具备 可复用、可扩充、可维护 三个特性，模式可以让我们构建出具有良好OO设计质量的系统。

数据结构►树

树

定义

生成

遍历

前序遍历

中序遍历

后续遍历

深度优先遍历（DFS）

广度优先遍历（BFS）

应用

红黑树

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)，红黑树有如下特性。

  • 每个节点或者是黑色，或者是红色。
  • 根节点是黑色。
  • 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
  • 如果一个节点是红色的，则它的子节点必须是黑色的。
  • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中非常高效。

应用

  • Java 中的 TreeSet、TreeMap
  • C++ STL 中的 set、map
  • Linux 虚拟内存的管理

搜索二叉树（BST）

二叉查找树实际上是数据域有序的二叉树，即对树上的每个结点，都满足其左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。

平衡二叉树（AVL）

平衡二叉树是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出，因此一般也称作AVL树，AVL树本质还是一棵二叉查找树，只是在其基础上增加了“平衡”的要求。所谓平衡是指，对AVL树的任意结点来说，其左子树与右子树的高度之差的绝对值不超过1，其中左子树与右子树的高度因子之差称为平衡因子。

B/B+/B* 树

B树

B 树是一种多路搜索树（非二叉树），其具有如下特点。

  • 定义任意非叶子结点最多只有M个儿子；且M>2；

  • 根结点的儿子数为[2, M]；

  • 除根结点以外的非叶子结点的儿子数为[M/2, M]；

  • 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

  • 非叶子结点的关键字个数=指向儿子的指针个数-1；

  • 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

  • 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的

    子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

  • 所有叶子结点位于同一层；

问题

B树和B+树的区别

  • B 树每个节点都保存key和data，B+ 树的data存储在叶子节点上
    • 非叶子节点不存储数据，这样一个节点可存储更多key，使树更矮，减少查找 / IO次数
  • 树的所有叶节点构成一个有序链表，可以按照key的排序次序遍历全部数据
    • 由于数据顺序排列且相连，便于区间查找和搜索

索引为什么使用B+树，而不是哈希表或B树

对应磁盘中的数据读取，应尽量优化磁盘访问次序。磁盘读取是按块读取的，充分利用这个原理，可减少磁盘访问次数。

索引使用B+树，相对于B树来说，非叶子结点保存数据更多，一次读取磁盘，可便利的key范围更广，所以理论上度写磁盘次数更少。

B+树，相对于哈希表来说，哈希索引也不支持多列联合索引的最左匹配规则，且无法按key的范围查找。

计算机科学►软件工程

类图

关系

继承（Inheritance / Extension）

关系 连线
继承，子类特化父类所有特征和行为 带箭头实线，箭头指向父类

示例

接口（Interfaces）

关系 连线
类实现接口 带三角箭头的虚线，箭头指向接口

虚线

关联（Associations）

可双向关联，也可单向关联，或自身关联。

关系 连线 代码
拥有关系，使一个类可以知道其他类的属性和方法 实心线，单向关联使用普通箭头，指向被拥有者；双向关联无箭头 成员属性

示例

聚合（Aggregation）

关系 连线 代码
部分和整体的关系，部分可离开整体独立存在 空心菱形实心线，菱形指向整体 成员属性

示例

组合（Composition）

关系 连线 代码
部分和整体的关系，部分不可离开整体独立存在 实心菱形实心线，菱形指向整体 成员属性

依赖（Dependency）

关系 连线 代码
使用关系 带箭头的虚线，指向被使用者 局部变量、方法的参数或者对静态方法的调用

示例

示例

Example UML Class Diagram

参考

计算机科学►软件工程

领域驱动设计（Domain-Driven Design）

领域驱动设计（DDD，Domain-Driven Design）是帮助开发大型系统的原则和模式的集合。DDD 更像一种方法论，指导我们开发大型的系统。

软件系统设计理念经历了 POP（面向过程编程）、OOP（面向对象编程）、DDD（领域驱动设计） 的转变。POP 设计，通过构建函数、分层，划分模块等方式，分解软件系统的复杂度。OOP 把软件的设计从功能维度提升到实体维度，进一步分解软件系统的复杂度，并以一种更易于理解的方式来组织软件系统。

随着软件系统规模的不断扩大，面临着实体爆炸的问题，在一个单一的逻辑范畴内，处理所有的实体，到了极其复杂的程度。DDD 通过把系统从需求维度划分为不同的领域，每个领域进行单独的设计，域之间通过暴露接口来进行协作。

核心概念

contexts

构成要素

  • 实体（Entity）
  • 值对象（Value Objects）
  • 领域服务（Domain Service）
  • 聚合根（Aggregate Root）
  • 工厂（Factories）
  • 仓储（Repository）

Bounded Context

contexts

参考

tools►plantuml

plantuml 类图

声明元素

1
2
3
4
5
6
7
8
9
10
11
12
13
@startuml
abstract        abstract
abstract class  "abstract class"
annotation      annotation
circle          circle
()              circle_short_form
class           class
diamond         diamond
<>              diamond_short_form
entity          entity
enum            enum
interface       interface
@enduml

定义关系

关系 符号
扩展（Extension） <|–
组合（Conposition） *–
聚合（Aggregation） o–

示例

1
2
3
4
5
6
7
8
9
10
11
@startuml
class Dummy {
  String data
  void methods()
}

class Flight {
   flightNumber : Integer
   departureTime : Date
}
@enduml