| | 644 | " Trie "{{{2 |
| | 645 | " |
| | 646 | " trie ::= {'root': node, |
| | 647 | " 'default_value': <any value>} |
| | 648 | " default-value ::= <any value> |
| | 649 | " node ::= {'value': <any value>, |
| | 650 | " 'children': {<a part of key (1 char)>: node, |
| | 651 | " ...}} |
| | 652 | |
| | 653 | let s:trie = {} |
| | 654 | let s:FALSE = 0 |
| | 655 | let s:TRUE = !s:FALSE |
| | 656 | |
| | 657 | |
| | 658 | function! s:trie.new(default_value) "{{{3 |
| | 659 | let new_instance = copy(s:trie) |
| | 660 | let new_instance.root = s:trie.node.new(a:default_value) |
| | 661 | let new_instance.default_value = a:default_value |
| | 662 | return new_instance |
| | 663 | endfunction |
| | 664 | |
| | 665 | |
| | 666 | function! s:trie.dump() "{{{3 |
| | 667 | echomsg 'Trie:' |
| | 668 | echomsg ' default_value:' string(self.default_value) |
| | 669 | call self.root.dump('root', 1) |
| | 670 | endfunction |
| | 671 | |
| | 672 | |
| | 673 | function! s:trie.put(sequence, value) "{{{3 |
| | 674 | let node = self.root |
| | 675 | let i = 0 |
| | 676 | while i < len(a:sequence) |
| | 677 | let item = a:sequence[i] |
| | 678 | if !has_key(node.children, item) |
| | 679 | let node.children[item] = s:trie.node.new(self.default_value) |
| | 680 | endif |
| | 681 | let node = node.children[item] |
| | 682 | let i = i + 1 |
| | 683 | endwhile |
| | 684 | let old_value = node.value |
| | 685 | let node.value = a:value |
| | 686 | return old_value |
| | 687 | endfunction |
| | 688 | |
| | 689 | |
| | 690 | function! s:trie.get(sequence, accept_halfway_matchp, ...) "{{{3 |
| | 691 | let default_value = a:0 ? a:1 : self.default_value |
| | 692 | let node = self.root |
| | 693 | let i = 0 |
| | 694 | while i < len(a:sequence) |
| | 695 | let item = a:sequence[i] |
| | 696 | if !has_key(node.children, item) |
| | 697 | return default_value |
| | 698 | endif |
| | 699 | let node = node.children[item] |
| | 700 | let i = i + 1 |
| | 701 | endwhile |
| | 702 | |
| | 703 | if node.leafp() || a:accept_halfway_matchp |
| | 704 | return node.value |
| | 705 | else |
| | 706 | return default_value |
| | 707 | endif |
| | 708 | endfunction |
| | 709 | |
| | 710 | |
| | 711 | function! s:trie.take(sequence) "{{{3 |
| | 712 | if len(a:sequence) == 0 |
| | 713 | throw 'empty sequence is not allowed' |
| | 714 | endif |
| | 715 | let parent = self.root |
| | 716 | let node = self.root |
| | 717 | let i = 0 |
| | 718 | while i < len(a:sequence) |
| | 719 | let item = a:sequence[i] |
| | 720 | if !has_key(node.children, item) |
| | 721 | throw 'value corresponding to the given sequence is not found' |
| | 722 | endif |
| | 723 | let parent = node |
| | 724 | let node = node.children[item] |
| | 725 | let i = i + 1 |
| | 726 | endwhile |
| | 727 | return remove(parent.children, item).value |
| | 728 | endfunction |
| | 729 | |
| | 730 | |
| | 731 | function! s:trie.get_incremental(accept_halfway_matchp, ...) "{{{3 |
| | 732 | let state = {} |
| | 733 | let state.accept_halfway_matchp = a:accept_halfway_matchp |
| | 734 | let state.default_value = a:0 ? a:1 : self.default_value |
| | 735 | let state.node = self.root |
| | 736 | let state.i = 0 |
| | 737 | |
| | 738 | function state.feed(item) |
| | 739 | if !has_key(self.node.children, a:item) |
| | 740 | return [s:trie.FAILED, self.default_value] |
| | 741 | endif |
| | 742 | let self.node = self.node.children[a:item] |
| | 743 | let self.i = self.i + 1 |
| | 744 | |
| | 745 | if self.node.leafp() || self.accept_halfway_matchp |
| | 746 | return [s:trie.MATCHED, self.node.value] |
| | 747 | else |
| | 748 | return [s:trie.CONTINUED, self.default_value] |
| | 749 | endif |
| | 750 | endfunction |
| | 751 | |
| | 752 | return state |
| | 753 | endfunction |
| | 754 | |
| | 755 | let s:trie.CONTINUED = ['CONTINUED'] |
| | 756 | let s:trie.FAILED = ['FAILED'] |
| | 757 | let s:trie.MATCHED = ['MATCHED'] |
| | 758 | |
| | 759 | |
| | 760 | let s:trie.node = {} "{{{3 |
| | 761 | |
| | 762 | function! s:trie.node.new(value) |
| | 763 | let new_instance = copy(s:trie.node) |
| | 764 | let new_instance.value = a:value |
| | 765 | let new_instance.children = {} |
| | 766 | return new_instance |
| | 767 | endfunction |
| | 768 | |
| | 769 | function! s:trie.node.leafp() |
| | 770 | return len(self.children) == 0 |
| | 771 | endfunction |
| | 772 | |
| | 773 | function! s:trie.node.dump(label, lv) |
| | 774 | echomsg s:indent(a:lv) string(a:label) ':' string(self.value) |
| | 775 | for key in sort(keys(self.children)) |
| | 776 | call self.children[key].dump(key, a:lv+1) |
| | 777 | endfor |
| | 778 | endfunction |
| | 779 | |
| | 780 | |
| | 781 | |
| | 782 | |
| | 783 | " User-defined surrounding objects "{{{2 |
| | 784 | |
| | 785 | function! s:user_obj_trie(type) |
| | 786 | if a:type ==# 'b' |
| | 787 | if !exists('b:surround_objects') |
| | 788 | let b:surround_objects = s:trie.new('') |
| | 789 | endif |
| | 790 | return b:surround_objects |
| | 791 | else " a:type ==# 'g' |
| | 792 | if !exists('g:surround_objects') |
| | 793 | let g:surround_objects = s:trie.new('') |
| | 794 | endif |
| | 795 | return g:surround_objects |
| | 796 | endif |
| | 797 | endfunction |
| | 798 | |
| | 799 | |
| | 800 | function! SurroundRegister(type, key, template) |
| | 801 | return s:user_obj_trie(a:type).put(a:key, a:template) |
| | 802 | endfunction |
| | 803 | |
| | 804 | function! SurroundUnregister(type, key) |
| | 805 | return s:user_obj_trie(a:type).take(a:key) |
| | 806 | endfunction |
| | 807 | |
| | 808 | |
| | 809 | function! s:user_obj_input() |
| | 810 | let [result, key] = s:user_obj_input_sub('b') |
| | 811 | if result is s:trie.FAILED |
| | 812 | call feedkeys(key, 't') |
| | 813 | let [result, key] = s:user_obj_input_sub('g') |
| | 814 | if result is s:trie.FAILED |
| | 815 | call feedkeys(key, 't') |
| | 816 | return '' |
| | 817 | endif |
| | 818 | endif |
| | 819 | |
| | 820 | return key |
| | 821 | endfunction |
| | 822 | |
| | 823 | function! s:user_obj_input_sub(type) |
| | 824 | let state = s:user_obj_trie(a:type).get_incremental(s:FALSE, 'not-used') |
| | 825 | let key = '' |
| | 826 | while 1 |
| | 827 | let c = s:getchar() |
| | 828 | let [result, _] = state.feed(c) |
| | 829 | let key = key . c |
| | 830 | if result is s:trie.MATCHED |
| | 831 | break |
| | 832 | elseif result is s:trie.FAILED |
| | 833 | break |
| | 834 | else " result is s:trie.CONTINUED |
| | 835 | " NOP |
| | 836 | endif |
| | 837 | endwhile |
| | 838 | return [result, key] |
| | 839 | endfunction |
| | 840 | |
| | 841 | |
| | 842 | function! s:user_obj_value(key) |
| | 843 | let Template = s:user_obj_trie('b').get(a:key, s:FALSE, '') |
| | 844 | if Template == '' |
| | 845 | let Template = s:user_obj_trie('g').get(a:key, s:FALSE, '') |
| | 846 | endif |
| | 847 | |
| | 848 | if type(Template) == type('string') |
| | 849 | return Template |
| | 850 | else " function? |
| | 851 | return Template() |
| | 852 | endif |
| | 853 | endfunction |
| | 854 | |
| | 855 | |
| | 856 | |
| | 857 | |