From 1743275cba91ec6634722af32b7eae0e697bd277 Mon Sep 17 00:00:00 2001 From: Peter Odding Date: Wed, 31 Aug 2011 23:22:40 +0200 Subject: Binary insertion --- list.vim | 37 ++++++++++++++++++++++++++++++++++++- 1 file changed, 36 insertions(+), 1 deletion(-) diff --git a/list.vim b/list.vim index 8857af1..44d6b20 100644 --- a/list.vim +++ b/list.vim @@ -1,6 +1,6 @@ " Vim auto-load script " Author: Peter Odding -" Last Change: March 15, 2011 +" Last Change: August 31, 2011 " URL: http://peterodding.com/code/vim/misc/ " Remove duplicate values from {list} in-place (preserves order). @@ -20,4 +20,39 @@ function! xolox#misc#list#unique(list) return a:list endfunction +" Binary insertion (more efficient than calling sort() after each insertion). + +function! xolox#misc#list#binsert(list, value, ...) + let idx = s:binsert_r(a:list, 0, len(a:list), a:value, exists('a:1') && a:1) + return insert(a:list, a:value, idx) +endfunction + +function! s:binsert_r(list, low, high, value, ignorecase) + let mid = a:low + (a:high - a:low) / 2 + if a:low == a:high + return a:low + elseif a:ignorecase ? a:value >? a:list[mid] : a:value > a:list[mid] + return s:binsert_r(a:list, mid + 1, a:high, a:value, a:ignorecase) + elseif a:ignorecase ? a:value