overlapping_prefixes.rb

# given a list of numbers, print any prefixes that overlap.
#
# e.g. [1, 2, 34, 35] has no overlaps
# e.g. [1, 2, 34, 3, 5] overlaps (3 is more general than 34)
#
# This is useful in the TZip gem, since if our prefixes
# overlap, the more specific mapping will never be used - probably 
# not the intended behavior of anyone inputting a mapping.
#
# Note: this doesn't detect duplicate prefixes, since they've already
# been clobbered into the hash.
#
require 'pp'

def overlapping_prefixes(prefixes)
 
  overlapping = []
  prefix_tree_root = {}

  # Knowing that duplicates will be "more general" (shorter) 
  # simplifies redundant prefix detection, so we sort by length.
  prefixes.sort.reverse.select do |prefix|
    puts "inserting #{prefix}" if debug?
    branch = prefix_tree_root

    #split prefix into digits
    prefix.to_s.split('').each_with_index do |digit, index|
      # if this is the last digit of the prefix
      if index == (prefix.length - 1)
        # and the branch already exists, we've discovered 
        # a more general prefix than the pre-existing.
        puts "prefix overlaps: #{prefix}"
        overlapping << prefix if branch[digit]
      end

      #travel down the tree, building a new node if needed
      branch = branch[digit] ||= {}

      pp prefix_tree_root if debug?
      gets if debug?
    end
  end

    overlapping
end

# change to true to step through prefix tree building
def debug?
  false
end

require 'tzip'
overlapping_prefixes(TZip::MAPPING.keys)