Fast wordlist search using a Trie

[jalih]

Here is a sample code for the 8th programming language demonstrating the use of a Trie for fast wordlist search. Builds a Trie from the internal 8th help sqlite database.

Code: [Select]


needs nk/gui
needs utils/help

22 font:system font:new "font1" font:atlas! drop
22 1.5 n:* constant ROW-HEIGHT
22 1.2 n:* constant LIST-ROW-HEIGHT

var numwords
var trie

a:new constant list-data

: getcount \ -- n
  list-data a:len n:1- nip ;

: getitem \ n -- s
  list-data swap a:_@ ;

: all-words \ -- a
  help_db @
  "SELECT cls||\":\"||nm FROM words ORDER BY cls,nm" db:exec[] nip
  a:squash ;

: build-trie \ -- tree numwords
  null false tree:trie all-words a:len >r ' tree:add a:each! drop r> ;

: new-win
  {
    name: "main",
    title: "8th Word Search",           
    wide: 0.5,                     
    high: 0.5,                   
    bg: "white"
  }
  nk:win
  "list" nk:list-new nk:m! ;

: list-item  \ s --
  nk:TEXT_LEFT "black" nk:label-colored ;

: search
  list-data a:clear
  trie @ "word" nk:get numwords @ tree:search nip
  a:+ drop ;

: main-render
  {
    bg: "white",
    font: "f1",
    flags: [ @nk:WINDOW_NO_SCROLLBAR ],
    word: ""
  }

  nk:begin
    null  { rows: [@ROW-HEIGHT, -1], cols: 1, rgap: 4 } nk:layout-grid-begin
      0 1 0 1 nk:grid rect>local nk:grid-push
        "word" nk:get 31 nk:EDIT_FIELD nk:PLUGIN_FILTER_DEFAULT nk:edit-string if
          "word" swap nk:set
          search
        else
          drop
        then
      1 1 0 1 nk:grid nk:rect>local nk:grid-push
        "list" nk:TEXT_LEFT LIST-ROW-HEIGHT getcount "list" nk:m@ dup>r nk:list-begin if
          LIST-ROW-HEIGHT 1 nk:layout-row-dynamic
            (
              getitem list-item
            ) r@ nk:list-range drop loop
          r@ nk:list-end
        then rdrop
    nk:layout-grid-end
  nk:end ;

: app:main
  build-trie numwords ! trie !
  new-win ' main-render -1 nk:render-loop ;