2016年10月

Guava的Strings.repeat

如果要自己实现一个repeat的话,最容易想到的可能会这样(示例不考虑int溢出的情况):

public static String repeat(String string, int count) {
    int length = string.length() * count;
    StringBuilder sb = new StringBuilder(length);
    for (int i = 0; i < count; i++) {
        sb.append(string);
    }
    return sb.toString();
}

用图画出来应该是这个样子的:

guava-strings-repeat (1).png

看到guava的实现,在位运算的时候还是小愣了一下,性能是比上面的实现好多了:

public static String repeat(String string, int count) {
  // 先去掉检测相关的判断,只看核心的实现
  final int len = string.length();
  final long longSize = (long) len * (long) count;
  final int size = (int) longSize;

  final char[] array = new char[size];
  string.getChars(0, len, array, 0);
  int n;
  for (n = len; n < size - n; n <<= 1) {
    System.arraycopy(array, 0, array, n, n);
  }
  System.arraycopy(array, 0, array, n, size - n);
  return new String(array);
}

用图画出来是这个样子的:

guava-strings-repeat.png

重点是这段代码:

  for (n = len; n < size - n; n <<= 1) {
    System.arraycopy(array, 0, array, n, n);
  }
  System.arraycopy(array, 0, array, n, size - n);

看下php的内核实现,其实原理一样,就是把现有的字串翻倍,当 [达到一半的长度, count为偶数] 或者 [刚超过一半的长度时, count为奇数] 做最后一次连接,只是写法不太一样:

// sed -n '5012,5058p' /usr/local/src/php-7.0.9/ext/standard/string.c
PHP_FUNCTION(str_repeat)
{
    zend_string        *input_str;        /* Input string */
    zend_long         mult;            /* Multiplier */
    zend_string    *result;        /* Resulting string */
    size_t        result_len;        /* Length of the resulting string */

    if (zend_parse_parameters(ZEND_NUM_ARGS(), "Sl", &input_str, &mult) == FAILURE) {
        return;
    }

    if (mult < 0) {
        php_error_docref(NULL, E_WARNING, "Second argument has to be greater than or equal to 0");
        return;
    }

    /* Don't waste our time if it's empty */
    /* ... or if the multiplier is zero */
    if (ZSTR_LEN(input_str) == 0 || mult == 0)
        RETURN_EMPTY_STRING();

    /* Initialize the result string */
    result = zend_string_safe_alloc(ZSTR_LEN(input_str), mult, 0, 0);
    result_len = ZSTR_LEN(input_str) * mult;

    /* Heavy optimization for situations where input string is 1 byte long */
    if (ZSTR_LEN(input_str) == 1) {
        memset(ZSTR_VAL(result), *ZSTR_VAL(input_str), mult);
    } else {
        char *s, *e, *ee;
        ptrdiff_t l=0;
        memcpy(ZSTR_VAL(result), ZSTR_VAL(input_str), ZSTR_LEN(input_str));
        s = ZSTR_VAL(result);
        e = ZSTR_VAL(result) + ZSTR_LEN(input_str);
        ee = ZSTR_VAL(result) + result_len;

        while (e<ee) {
            l = (e-s) < (ee-e) ? (e-s) : (ee-e);
            memmove(e, s, l);
            e += l;
        }
    }

    ZSTR_VAL(result)[result_len] = '\0';

    RETURN_NEW_STR(result);
}

https://github.com/jonschlinkert/repeat-string/blob/master/index.js

TOC的生成

TOC是什么

TOC 即 Table of Content,就是将文档中的 h1-h6 抽取出来,并结构化的展示;可以通过链接直接跳转到相应的内容 (这里我使用锚点)

这个本身是没什么好写的,但是涉及到树形的结构化处理,要考虑到怪异的层级问题。

方案

由于原始文档的格式(markdown,html,asciidoc)比较多,但是用于最后展示的还是 html,所以为了方便统一的处理,先将文档都选染成html

toc.png

  1. 使用 ParseDown 渲染markdown
  2. 使用 Crawler 解析html
  3. 提取 h{n},结构化 h{n},并设置html中的 id 属性
  4. 展示树形 TOC

预览

9FBAC831-0717-4728-A06F-CA5CCC4D62AF.png

实现

安装依赖包

composer require erusev/parsedown-extra
composer require symfony/dom-crawler
composer require symfony/css-selector

代码实现

public function getTocAttribute() {
    if ($this->headerNodes) {
        return $this->headerNodes;
    }
    $crawler = new Crawler();
    $crawler->addHtmlContent($this->html, 'utf-8');
    $this->headerNodes = $crawler->filter('h1,h2,h3,h4,h5,h6')->each(function (Crawler $node, $i) {
        $attrId = 'header_' . $i;
        $node->getNode(0)->setAttribute('id', $attrId);
        return [
            'target' => '#' . $attrId,
            'level' => intval(substr($node->nodeName(), 1)),
            'text' => $node->text(),
        ];
    });
    $this->tocedHtml = $crawler->html();
    return $this->headerNodes;
}

树形结构化

class MenuItem {
    public $level;
    public $text;
    public $target;
    public $children = [];
    public function __construct($target, $level, $text) {
        $this->target = $target;
        $this->level = $level;
        $this->text = $text;
    }
}
$rootMenu = new MenuItem(-1, 0, '__root__');
foreach ($wiki->toc as $hn) {
    $menuItem = new MenuItem($hn['target'], $hn['level'], $hn['text']);
    // 每个菜单都从根目录开始寻找
    $lastMenu = $rootMenu;
    while (true) {
        $nestMenu = end($lastMenu->children);
        // 如果比上个层级还大,就挂载到他后面
        if (!$nestMenu && $hn['level'] > $lastMenu->level) {
            $lastMenu->children[] = $menuItem;
            break;
        }
        // 如果循环下来发现没有匹配的层级,则放进根目录
        if ($hn['level'] < $nestMenu->level) {
            $rootMenu->children[] = $menuItem;
            break;
        }
        // 如果和上个层级一样,就赛到上层的children
        if ($nestMenu->level >= $hn['level']) {
            $lastMenu->children[] = $menuItem;
            break;
        }
        $lastMenu = $nestMenu;
    }
}

渲染输出

function tree($menu) {
    $html = '<ul>';
    $html .= '<li><a href="' . $menu->target . '">' . $menu->text . '</a>';
    if ($menu->children) {
        foreach ($menu->children as $subMenu) {
            $html .= tree($subMenu);
        }
    }
    $html .= '</li></ul>';
    return $html;
}
echo '<div class="wiki-index"><div class="wiki-index-header">文章目录</div><div class="wiki-index-body">';
foreach ($rootMenu->children as $menu) {
    echo tree($menu);
}
echo '</div></div>';

阿里云地图流量动画效果的实现分析

预览

阿里云的:
preview1.gif

实验品:
preview2.gif

原理

阿里云的流量动画是先画出一条线,然后改变每个关键颜色的offset,实现类似抛投的效果;渐变的结构如下:

7451DFEF-A99C-4777-B035-FB1F501F5093.png

实现

这里只画出一条简单的直线作为例子,如果需要画出曲线,d3的geo相关的函数可以很方便的作出。

C1B9DB0B-3364-404F-BCAE-682BB2FD942D.png

代码如下:

(function () {

    var svg = d3.select("#container")
                .append("svg")
                .attr("width", 500)
                .attr("height", 200);
    var gradient = svg.append("defs")
                      .append("linearGradient")
                        .attr("id", "gradient")
                        .attr("x1", "0%")
                        .attr("x2", "100%");
    var stops = [];
    var stop;
    stop = gradient.append("stop").attr("stop-opacity", 1).attr("offset", "0%")
        .attr("stop-color", "rgba(255, 255, 255, 0)");
    stops.push(stop);

    // start stop
    stop = gradient.append("stop").attr("stop-opacity", 1).attr("offset", "0%")
        .attr("stop-color", "rgba(255, 255, 255, 0)");
    stops.push(stop);

    // start color
    stop = gradient.append("stop").attr("stop-opacity", 1).attr("offset", "0%")
        .attr("stop-color", "rgba(255, 255, 255, 0)");
    stops.push(stop);

    // end color
    stop = gradient.append("stop").attr("stop-opacity", 1).attr("offset", "100%")
        .attr("stop-color", "#009a61");
    stops.push(stop);

    // end stop
    stop = gradient.append("stop").attr("stop-opacity", 1).attr("offset", "100%")
        .attr("stop-color", "rgba(255, 255, 255, 0)");
    stops.push(stop);

    stop = gradient.append("stop").attr("stop-opacity", 1).attr("offset", "100%")
        .attr("stop-color", "rgba(255, 255, 255, 0)");
    stops.push(stop);


    var route = svg.append("line")
                    .attr("x1", 0)
                    .attr("y1", 100)
                    .attr("x2", 500)
                    .attr("y2", 200)
                    .style("stroke", "url(#gradient)")
                    .style("stroke-width", 4)
                    .style("stroke-linecap", "round")
                    .style("fill", "none");

    var myoffset = 0;
    setInterval(function () {
        myoffset += 1;
        stops.slice(1, 3).forEach(function (stop, i) {
            stop.attr("offset", (myoffset - 20) + "%");
        });
        stops.slice(3, 5).forEach(function (stop, i) {
            stop.attr("offset", myoffset + "%");
        });
        if (myoffset >= 100) {
            myoffset = 0;
        }
    }, 100);
})();