在看了NTU的AI课程之后，试着用C++来实现了A*搜索算法。它的思想就是Avoid expanding paths that are already expensive.。标准的A*搜索算法描述如下：

给出带权无向图，初始顶点，目标顶点，以及evaulation function。Evalutaion function包括

• g(n)：为到达顶点n，当前已有的花费（cost so far to reach n）
• h(n)：一个 从任意顶点 到 目标顶点 的估计花费（estimated cost to goal from n）
• f(n)：从 初始顶点 到 目标顶点 的估计花费（estimated total cost from the starting node to goal through n）

f(n) = h(n) + g(n)

例如有三个地点A, B, C，它们之间的图如下

A —— B —— C

A —— B权重为30，B —— C权重为40，

A —— C的直线距离为50，但是并没有A——C这条边（即不能直接从A开始，只经过一条边就到达C）

现在，给出初始顶点为A，目标顶点为C，h(n)如下

h(A) = 50

h(B) = 40

h(C) = 0

在一开始，我们将A放入名为froniter的优先队列中，froniter按照f(n)的值升序排序。

那么我们有f(A) = h(A) + g(A)。h(A)是由用户直接给出的，等于50。g(A)是我们为了到达C，已有的花费，在这个例子中，可以理解为已经走过的路程，因为我们是一开始就在A，还没有开始走，所以g(A)为0。于是f(A) = h(A) + g(A) = 50 + 0 = 50

froniter中的数据如下：

Continue reading Standard A* Search Algorithm in C++ →

node.js里面的EventEmitter非常好用，于是上次写完Functor之后，就顺理成章的写了这个EventEmitter，或者说，就是为了实现这个EventEmitter才写的Functor（后文会提到为什么要Functor，毕竟如果只看Functor本身的话，还不如直接用lamdba方便）。

在node.js中，使用EventEmitter非常简单，

const EventEmitter = require('events');

class MyEmitter extends EventEmitter {}

const myEmitter = new MyEmitter();
myEmitter.on('event', () => {
    console.log('an event occurred!');
});
myEmitter.emit('event');

——https://nodejs.org/api/events.html

那么现在这个C++版的EventEmitter也必须做到这样简单易用，事实上，它也的确和node.js的使用方式类似。

#include <iostream>
#include <sstream>
#include <thread>
#include <vector>
#include "EventEmitter.hpp"

using namespace std;

class emitter : public EventEmitter {
};

int main(int argc, const char * argv[]) {
    emitter emitter;
    emitter.on("event", [&emitter](int data) {
        ostringstream osstream;
        osstream << "data: " << data << '\n';
        std::cout << osstream.str();
    });

    vector<thread> threads;
    for (int i = 0; i < 10; i++) {
        threads.emplace_back([&emitter, i]() {
            emitter.emit("event", i);
        });
    }

    for (auto &t : threads) t.join();
}

Continue reading A simple EventEmitter in C++ →

最近写代码的时候，总能在不少STL的函数声明里看见可爱的std::enable_if，虽然自己偶尔用过，不过也只是直接用STL库里的std::is_arithmetic之类。

于是就去Google了std::enable_if，然后参考了如下几篇post，写了一个较为通用的Module Check。

• Introduction to Type Traits in the C++ standard library
• SFINAE and enable_if
• Tips and tricks » EnableIf<C++11>
• C++技巧： SFINAE
• C++ metafunction to determine whether a type is callable

所以还是先从一个小的问题开始讲起吧～

假设我们做了一个中间类作为接口，这个中间类有一个模版构造函数，它接受一个类实例和一个double类型的参数，并且总是调用一个固定的实例方法。

class Intermediate {
public:
    template <typename T>
    Intermediate(const T& object, double value) {
        object.method(value);
    }
};

现在我们有如下的类，

class A {
public:
    void method(double d) const {
        std::cout<<d<<'\n';
    }
};

class B {
public:
    void method(int i) const {
        std::cout<<i<<'\n';
    }
};

虽然如下代码可以编译运行，但是假如我们希望只有类A被这样调用才有效呢？

Intermediate inter_a_1(a, 2.33); // print 2.33
Intermediate inter_b_1(b, 2.33); // print 2

Continue reading Module Check——Usage of std::enable_if →

于是今天用C++11的模版实现了几个整数和浮点数的排序算法模版，分别是

• 冒泡排序
• 鸡尾酒排序
• 插入排序
• 选择排序
• 壳排序
• 快速排序

Continue reading 用C++11实现的几个排序算法模版 →

之前写了xterm256的wrapper，然后又看到了HTTPie，感觉Solarized的配色挺好看的，于是就有了这个带语法高亮输出的HTTP头捕获程序。

整个程序比较简单，用到了libpcap抓包，然后正则匹配、高亮输出，效果如下。

Continue reading 带语法高亮输出的HTTP头捕获 →

如果你的terminal支持xterm-256color模式的话，就可以在terminal中使用256种颜色。利用这256种色彩，可以做出很棒／很酷的效果。比如vim的语法高亮。

这里简单的实现了一个C++类，与cout的行为相同，仅在输出类xterm256::color的实例时做处理，将紧随其后的、截止下一个xterm256::color类实例前的文字输出为对应的颜色。

类xterm256::color使用3个unsigned short作为初始化参数，依次对应RGB。在输出时，由于仅有256种色彩，将自动转为与xterm-256color颜色表中欧氏距离最近的一种颜色。

简要的使用例子及截图如下

Continue reading A simple xterm256 wrapper in C++ →

之前写过一篇利用k-means算法来计算图像中主要颜色的文章，K-means聚类算法计算给定图像中主要颜色。于是今天顺便写了个较为通用的C++下的K-means算法模版。

有一个主要的模版，还有一个稍有变化的模版，仅体现在传入的第三个参数上。

主要的参数如下，

返回值都是包含k个该种类型的元素的std::vector

Continue reading C++下的通用K-means Algorithm模版 →

所以再过几个小时就要考《数据库系统概论》了，看书看到一半手痒了，就把书上的两个算法用C++实现了一遍，这两个算法是

• 求属性集X在U上的函数依赖集F的闭包
• 求给定函数依赖集F的最小覆盖

详细的算法都写在注释里了～

Continue reading 数据库系统概论——C++实现求解 属性集X关于函数依赖集F的闭包 & 给定函数依赖集F的最小覆盖 →

前几天wget出了一个洞，

On a server redirect from HTTP to a FTP resource, wget would trust the HTTP server and uses the name in the redirected URL as the destination filename.

——https://people.canonical.com/~ubuntu-security/cve/2016/CVE-2016-4971.html

即，当wget请求一个HTTP站点上的文件时，如果HTTP服务器将它重定向到一个FTP服务器的话，wget将使用HTTP服务器所给出的在FTP服务器上的文件的名字。

如果我们重定向到一个名为.bash_profile的文件，而且用户下载文件的目录下又正好是默认的登录目录，且没有这个.bash_profile的话， 我们的目的就达到了。我们可以在.bash_profile中写上恶意代码，下一次该用户登录上来时，这些恶意代码就会自动被执行，于是23333

Continue reading wget漏洞CVE-2016-4971 →