SuffixArray

git-svn-id: http://svn.coderepos.org/share/lang/javascript/vimperator-plugins/trunk@30853 d0d07461-0603-4401-acd4-de1884942a52

1 files changed, 237 insertions, 94 deletions

diff --git a/hatena-bookmark-search.js b/hatena-bookmark-search.js
index 1a8ef3c..a0647dd 100644
--- a/hatena-bookmark-search.js
+++ b/hatena-bookmark-search.js
@@ -8,7 +8,7 @@ var PLUGIN_INFO =
 <updateURL>http://svn.coderepos.org/share/lang/javascript/vimperator-plugins/trunk/hatena-bookmark-search.js</updateURL>

 <author mail="hotchpotch@gmail.com" homepage="http://d.hatena.ne.jp/secondlife/">Yuichi Tateno</author>

 <license>MPL 1.1/GPL 2.0/LGPL 2.1</license>

-<version>0.1.2</version>

+<version>1.0.0</version>

 <detail><![CDATA[

 >||

 :bs[earch][!] word

@@ -51,20 +51,29 @@ liberator.globalVariables.hatena_bookmark_no_migemo = true;
 

 liberator.plugins.HatenaBookmark = (function(){

 

-var p = function(arg) {

-    Application.console.log(arg);

+let p = function(arg) {

+    Application.console.log(''+arg);

     // liberator.log(arg);

 }

 

+p.b = function(func, name) {

+    let now = (new Date() * 1);

+    func();

+    let t = (new Date() * 1) - now;

+    // p('sary: ' + name + ': ' + t);

+}

+

 const HatenaBookmark = {};

-HatenaBookmark.Data = new Struct('url', 'title', 'comment', 'icon');

-HatenaBookmark.Data.defaultValue('icon', function() bookmarks.getFavicon(this.url));

-HatenaBookmark.Data.prototype.__defineGetter__('stext', function() {

-    if (typeof this._stext == 'undefined') {

-         this._stext = this.comment + "\0" + this.title + "\0" + this.url;

-    }

-    return this._stext;

-});

+HatenaBookmark.Data = new Struct('data');

+/*

+ * title

+ * comment

+ * url 

+ */

+HatenaBookmark.Data.prototype.__defineGetter__('title', function() this.data.split("\n")[0]);

+HatenaBookmark.Data.prototype.__defineGetter__('comment', function() this.data.split("\n")[1]);

+HatenaBookmark.Data.prototype.__defineGetter__('url', function() this.data.split("\n")[2]);

+HatenaBookmark.Data.prototype.__defineGetter__('icon', function() bookmarks.getFavicon(this.url));

 HatenaBookmark.Data.prototype.__defineGetter__("extra", function () [

     ["comment", this.comment, "Comment"],

 ].filter(function (item) item[1]));

@@ -79,7 +88,15 @@ try {
 } catch (e if e instanceof TypeError) {

 }

 

+HatenaBookmark.useSuffixArray = !!(liberator.globalVariables.hatena_bookmark_suffix_array);

 HatenaBookmark.useMigemo = !!(!liberator.globalVariables.hatena_bookmark_no_migemo && XMigemoCore);

+HatenaBookmark.reload = function() {

+    if (HatenaBookmark.useSuffixArray) {

+        HatenaBookmark.SuffixArray.reload();

+    } else {

+        HatenaBookmark.UserData.reload();

+    }

+}

 

 HatenaBookmark.Command = {

    templateDescription: function (item, text) {

@@ -115,7 +132,7 @@ HatenaBookmark.Command = {
                 this.migemo = HatenaBookmark.Command.compileRegexp(this.filter);

             }

             var migemo = this.migemo;

-            return migemo.test(item.stext);

+            return migemo.test(item.data);

         } else {

             return this.match(item.url) || this.match(item.comment) || this.match(item.title);

         }

@@ -129,7 +146,7 @@ HatenaBookmark.Command = {
     },

     execute: function(args) {

         if (args['-reload']) {

-            HatenaBookmark.UserData.reload();

+            HatenaBookmark.reload();

             liberator.echo('HatenaBookmark data reloaded.');

             return;

         }

@@ -168,9 +185,14 @@ HatenaBookmark.Command = {
                 ],

             }

             context.ignoreCase = true;

-            if (context.migemo) delete context.migemo;

-            context.filters = [HatenaBookmark.Command.filter];

-            context.completions = HatenaBookmark.UserData.bookmarks;

+            if (HatenaBookmark.useSuffixArray) {

+                context.filters = [];

+                context.completions = HatenaBookmark.SuffixArray.search(context.filter);

+            } else {

+                if (context.migemo) delete context.migemo;

+                context.filters = [HatenaBookmark.Command.filter];

+                context.completions = HatenaBookmark.UserData.bookmarks;

+            }

         }

     }

 }

@@ -203,91 +225,131 @@ commands.addUserCommand(
 

 completion.addUrlCompleter("H", "Hatena Bookmarks", HatenaBookmark.Command.createCompleter(["Hatena Bookmarks"]));

 

+HatenaBookmark.Cache = {

+    get store() {

+        if (!this._store) {

+            let key = 'plugins-hatena-bookmark-search-data';

+            this._store = storage.newMap(key, true);

+        }

+        return this._store;

+    },

+    get now() {

+        return (new Date * 1);

+    },

+    clear : function () {

+        let store = this.store;

+        store.remove('expire');

+        store.remove('data');

+        store.remove('saryindexes');

+    },

+    get data () {

+        let store = this.store;

+        let expire = store.get('expire');

+        if (expire && expire > this.now) {

+            return store.get('data');

+        } else {

+            return this.loadByRemote();

+        }

+    },

+    get expire() {

+        // 24 hours;

+        return this.now + (liberator.globalVariables.hatena_bookmark_cache_expire || 1000 * 60 * 24); 

+    },

+    loadByRemote: function() {

+        let r = util.httpGet('http://b.hatena.ne.jp/my.name');

+        let check = eval('(' + r.responseText + ')');

+        if (!check.login) {

+            liberator.echo('please login hatena bookmark && :bsearch -reload ');

+            this.store.set('expire', this.expire);

+            this.store.set('data', '');

+            return '';

+        } else {

+            let url = 'http://b.hatena.ne.jp/my/search.data';

+            let res = util.httpGet(url);

+            this.store.set('expire', this.expire);

+            this.store.set('data', res.responseText);

+            return res.responseText;

+        }

+    },

+    get sary() {

+        let data = this.data;

+        if (data[0] != "\0") {

+            data = data.substr(0, data.length * 3/4).split("\n").map(function(s, i) 

+                (i % 3 == 0) ? ("\0" + s) : s

+            ).join("\n");

+            this.store.set('expire', this.expire);

+            this.store.set('data', data);

+        }

+        let sary = new SuffixArray(data);

+        let saryindexes = this.store.get('saryindexes');

+        if (saryindexes) {

+            sary.sary = saryindexes.split(',');

+        } else {

+            sary.make();

+            this.store.set('saryindexes', sary.sary.join(','));

+        }

+        return sary;

+    },

+}

+

+HatenaBookmark.SuffixArray = {

+    get cache() HatenaBookmark.Cache,

+    reload: function() {

+        this.cache.clear();

+        this.sary = null;

+    },

+    search: function(word) {

+        if (word.length < 2) return [];

+        if (!this.sary) {

+            this.sary = this.cache.sary;

+        }

+        let sary = this.sary;

+        let indexes;

+        p.b(function() {

+            indexes = sary.search(word);

+        }, 'search/' + word);

+        /*

+         * title

+         * comment

+         * url 

+         */

+        var str = this.sary.string;

+        let tmp = [];

+        let res = [];

+        for (let i = 0, len = indexes.length; i < len; i++) {

+            let sIndex = str.lastIndexOf("\0", indexes[i]);

+            if (tmp.indexOf(sIndex) == -1) {

+                tmp.push(sIndex);

+                let eIndex = str.indexOf("\0", indexes[i]);

+                if (sIndex != -1 && eIndex != -1) {

+                    res.push(new HatenaBookmark.Data(str.substring(sIndex, eIndex-1)));

+                }

+            }

+        }

+        return res;

+    },

+}

+

 HatenaBookmark.UserData = {

     get bookmarks() {

         this.init();

         return this._bookmarks;

     },

+    get cache() HatenaBookmark.Cache,

     reload: function() {

         this._inited = false;

+        this.cache.clear();

         this.init();

     },

     init: function() {

         if (!this._inited) {

+            let cache = HatenaBookmark.Cache.data;

             if (this._bookmarks)

                delete this._bookmarks;

             this._inited = true;

-            this.preloadLimit = 500;

-            this.preload();

+            this.createDataStructure(cache);

         }

     },

-    preload: function() {

-        this.load({

-            offset: 0,

-            limit: this.preloadLimit

-        });

-    },

-    load: function(query) {

-        var url = 'http://b.hatena.ne.jp/my/search.data';

-        var xhr = new XMLHttpRequest();

-        var self = this;

-        if (query.async) {

-           xhr.onreadystatechange = function() {

-               if (xhr.readyState == 4) {

-                   if (xhr.status == 200) {

-                       self.completeHandler(xhr)

-                   } else {

-                       liberator.echoerr('XHR Error: ' + xhr.statusText);

-                       // throw new Error(xhr.statusText);

-                   }

-               }

-           }

-        }

-        xhr.open('POST', url, query.async);

-        xhr.setRequestHeader('Content-Type', 'application/x-www-form-urlencoded');

-        xhr.send(this.makeQuery(query));

-        if (!query.async) {

-            if (xhr.status == 200) {

-              this.completeHandler(xhr);

-            } else {

-              liberator.echoerr('XHR Error: ' + xhr.statusText);

-              // throw new Error(xhr.statusText);

-            }

-        }

-    },

-    makeQuery: function(data) {

-        var pairs = [];

-        var regexp = /%20/g;

-        for (var k in data) {

-            if (typeof data[k] == 'undefined') continue;

-            var v = data[k].toString();

-            var pair = encodeURIComponent(k).replace(regexp,'+') + '=' +

-                encodeURIComponent(v).replace(regexp,'+');

-            pairs.push(pair);

-        }

-        return pairs.join('&');

-    },

-    completeHandler: function(res) {

-        if (this._loaded) return;

-

-        if (!this._bookmarks) {

-            this.createDataStructure(res.responseText || '');

-            if (this._bookmarks.length == this.preloadLimit) {

-                this.load({

-                    offset: this.preloadLimit,

-                    async: true

-                });

-            } else {

-                this._loaded = 1;

-            }

-        } else {

-            this.updateDataStructure(res.responseText || '');

-            this._loaded = 1;

-        }

-    },

-    updateDataStructure: function(data) {

-        this.pushData(this._bookmarks, data);

-    },

     createDataStructure: function(data) {

         this._bookmarks = [];

         this.pushData(this._bookmarks, data);

@@ -297,18 +359,99 @@ HatenaBookmark.UserData = {
         var tmp = infos.splice(0, infos.length * 3/4);

         var len = tmp.length;

         for (var i = 0; i < len; i+=3) {

-            ary.push(new HatenaBookmark.Data(tmp[i+2]/* url */, tmp[i]/* title */, tmp[i+1]/* comment */));

+            /*

+             * title

+             * comment

+             * URL

+             */

+            ary.push(new HatenaBookmark.Data(tmp[i] + "\n" + tmp[i+1] + "\n" + tmp[i+2]));

         }

-    },

-    mapFunc: function(item) {

-        item = item.split("\n");

-        return {

-            url: item[2],

-            comment: item[1],

-            title: item[0],

+    }

+};

+

+let SuffixArray = function (string) {

+    this.string = string;

+    this.lowerString = string.toLowerCase();

+    this.defaultLength = 255;

+}

+

+SuffixArray.prototype = {

+    make: function SuffixArray_createSuffixArray() {

+        let string = this.lowerString;

+        let sary = [];

+        let saryIndex = 0;

+        let str;

+        let index;

+        let dLen = this.defaultLength;

+        p.b(function() {

+        for (let i = 0, len = string.length; i < len; i++) {

+            str = string.substr(i, dLen);

+            index = str.indexOf("\n");

+            if (index != 0) {

+                if (index != -1)

+                    str = str.substr(0, index);

+                sary[saryIndex++] = [str, i];

+            }

         }

+        }, 'create');

+        p.b(function() {

+        sary.sort(function(a, b) {

+            if (a[0] > b[0]) {

+                return 1;

+            } else if (a[0] < b[0]) {

+                return -1;

+            }

+            return 0;

+        });

+        }, 'sort');

+        this.sary = sary.map(function([_,i]) i);

     },

-};

+    set sary (sary) { this._sary = sary; this._len = sary.length },

+    get sary () this._sary,

+    get length () this._len,

+    search: function SuffixArray_search(word) {

+        let wLen = word.length;

+        if (wLen == 0) return [];

+        if (!this.sary) this.make();

+

+        word = word.toLowerCase();

+        let string = this.lowerString;

+        let sary = this.sary;

+        let len = this.length;

+        let lastIndex = -1;

+        let index = parseInt(len / 2);

+

+        let floor = Math.floor;

+        let ceil = Math.ceil;

+

+        let str;

+        let range = index;

+

+        while (lastIndex != index) {

+            lastIndex = index;

+            str = string.substr(sary[index], wLen);

+            if (word < str) {

+                range = floor(range / 2);

+                index = index - range;

+            } else if (word > str) {

+                range = ceil(range / 2);

+                index = index + range;

+            } else {

+                let res = [sary[index]];

+                let start = index;

+                while (string.substr(sary[--start], wLen) == word)

+                    res.unshift(sary[start]);

+                let end = index;

+                while (string.substr(sary[++end], wLen) == word)

+                    res.push(sary[end]);

+                res.sort(function(a, b) a - b);

+                return res;

+            }

+        }

+

+        return [];

+    }

+}

 

 return HatenaBookmark;

 })();