1#!/usr/bin/env ruby
2#--
3# Copyright (c) 2001,2003 Akinori MUSHA <knu@iDaemons.org>
4#
5# All rights reserved.  You can redistribute and/or modify it under
6# the same terms as Ruby.
7#
8# $Idaemons: /home/cvs/rb/abbrev.rb,v 1.2 2001/05/30 09:37:45 knu Exp $
9# $RoughId: abbrev.rb,v 1.4 2003/10/14 19:45:42 knu Exp $
10# $Id: abbrev.rb 39458 2013-02-24 05:06:42Z zzak $
11#++
12
13##
14# Calculates the set of unique abbreviations for a given set of strings.
15#
16#   require 'abbrev'
17#   require 'pp'
18#
19#   pp Abbrev.abbrev(['ruby', 'rules'])
20#
21# Generates:
22#
23#   { "rub"   =>  "ruby",
24#     "ruby"  =>  "ruby",
25#     "rul"   =>  "rules",
26#     "rule"  =>  "rules",
27#     "rules" =>  "rules" }
28#
29# It also provides an array core extension, Array#abbrev.
30#
31#   pp %w{summer winter}.abbrev
32#   #=> {"summe"=>"summer",
33#        "summ"=>"summer",
34#        "sum"=>"summer",
35#        "su"=>"summer",
36#        "s"=>"summer",
37#        "winte"=>"winter",
38#        "wint"=>"winter",
39#        "win"=>"winter",
40#        "wi"=>"winter",
41#        "w"=>"winter",
42#        "summer"=>"summer",
43#        "winter"=>"winter"}
44
45module Abbrev
46
47  # Given a set of strings, calculate the set of unambiguous
48  # abbreviations for those strings, and return a hash where the keys
49  # are all the possible abbreviations and the values are the full
50  # strings.
51  #
52  # Thus, given +words+ is "car" and "cone", the keys pointing to "car" would
53  # be "ca" and "car", while those pointing to "cone" would be "co", "con", and
54  # "cone".
55  #
56  #   require 'abbrev'
57  #
58  #   Abbrev.abbrev(['car', 'cone'])
59  #   #=> {"ca"=>"car", "con"=>"cone", "co"=>"cone", "car"=>"car", "cone"=>"cone"}
60  #
61  # The optional +pattern+ parameter is a pattern or a string. Only
62  # input strings that match the pattern or start with the string
63  # are included in the output hash.
64  #
65  #   Abbrev.abbrev(%w{car box cone}, /b/)
66  #   #=> {"bo"=>"box", "b"=>"box", "box"=>"box"}
67  def abbrev(words, pattern = nil)
68    table = {}
69    seen = Hash.new(0)
70
71    if pattern.is_a?(String)
72      pattern = /\A#{Regexp.quote(pattern)}/  # regard as a prefix
73    end
74
75    words.each do |word|
76      next if word.empty?
77      word.size.downto(1) { |len|
78        abbrev = word[0...len]
79
80        next if pattern && pattern !~ abbrev
81
82        case seen[abbrev] += 1
83        when 1
84          table[abbrev] = word
85        when 2
86          table.delete(abbrev)
87        else
88          break
89        end
90      }
91    end
92
93    words.each do |word|
94      next if pattern && pattern !~ word
95
96      table[word] = word
97    end
98
99    table
100  end
101
102  module_function :abbrev
103end
104
105class Array
106  # Calculates the set of unambiguous abbreviations for the strings in
107  # +self+.
108  #
109  #   require 'abbrev'
110  #   %w{ car cone }.abbrev
111  #   #=> {"ca" => "car", "con"=>"cone", "co" => "cone",
112  #        "car"=>"car", "cone" => "cone"}
113  #
114  # The optional +pattern+ parameter is a pattern or a string. Only
115  # input strings that match the pattern or start with the string
116  # are included in the output hash.
117  #
118  #   %w{ fast boat day }.abbrev(/^.a/)
119  #   #=> {"fas"=>"fast", "fa"=>"fast", "da"=>"day",
120  #        "fast"=>"fast", "day"=>"day"}
121  #
122  # See also Abbrev.abbrev
123  def abbrev(pattern = nil)
124    Abbrev::abbrev(self, pattern)
125  end
126end
127
128if $0 == __FILE__
129  while line = gets
130    hash = line.split.abbrev
131
132    hash.sort.each do |k, v|
133      puts "#{k} => #{v}"
134    end
135  end
136end
137