Given a list of directories, filter out all folders that have sub dirs

Benchmark results.md

======= /etc Paths =======
                      user     system      total        real
Adam              0.210000   0.000000   0.210000 (  0.215259)
Andre             0.210000   0.000000   0.210000 (  0.207338)
David             0.090000   0.000000   0.090000 (  0.089603)
Pete              0.200000   0.000000   0.200000 (  0.201303)
Tim               0.010000   0.000000   0.010000 (  0.009618)
Tom               6.000000   0.000000   6.000000 (  5.998718)
Wes               0.000000   0.000000   0.000000 (  0.001508)
======= Random Paths =======
                      user     system      total        real
Adam              1.760000   0.000000   1.760000 (  1.756570)
Andre             1.750000   0.000000   1.750000 (  1.755080)
David             1.060000   0.000000   1.060000 (  1.059415)
Pete              1.700000   0.000000   1.700000 (  1.697262)
Tim               0.750000   0.000000   0.750000 (  0.747477)
Tom              48.720000   0.040000  48.760000 ( 48.719236)
Wes               0.060000   0.000000   0.060000 (  0.064951)
Skipped due to breakage
{}

% ruby -v
ruby 1.9.2p180 (2011-02-18 revision 30909) [x86_64-darwin10.7.1]

library.rb

module Library

  def self.leaf_paths_of(paths)
    leaves = []
    paths.sort.reduce do |l,r|
      leaves << l if should_keep(l, r)
      r
    end

    leaves << paths.last unless leaves.last == paths.last
    leaves
  end

  def self.should_keep(l, r)
    if r.start_with?(l)
      (l.count('/') == r.count('/')) && (l.length < r.length)
    else
      true
    end
  end
end

library_spec.rb

describe Library do
  
  describe "leaf paths of" do
    it "returns a path, if it doesn't have a sub dir in the list" do
      Library.leaf_paths_of(["a"]).should == ["a"]
    end

    it "keeps unrelated paths" do
      Library.leaf_paths_of(["a", "b"]).should == ["a", "b"]
    end

    it "removes the base path if we have a subdir for it" do
      Library.leaf_paths_of(["a", "a/aa"]).should == ["a/aa"]
    end

    it "keeps all sub dirs of the base path" do
      Library.leaf_paths_of(["a", "a/aa", "a/ab", "a/ac"]).should == ["a/aa", "a/ab", "a/ac"]
    end

    it "doesn't touch unrelated paths if a base dir is removed" do
      Library.leaf_paths_of(["a", "a/aa", "b"]).should == ["a/aa", "b"]
    end

    it "removes all base paths if they all have sub dirs" do
      Library.leaf_paths_of(["a", "a/aa", "b", "b/bb"]).should == ["a/aa", "b/bb"]
    end

    it "makes sure we only get leaves" do
      Library.leaf_paths_of(["a", "a/aa", "a/aa/aaa"]).should == ["a/aa/aaa"]
    end

    it "leaves similar named subdirs in another base path alone" do
      Library.leaf_paths_of(["a", "a/aa", "b", "b/a", "b/aa"]).should == ["a/aa", "b/a", "b/aa"]
    end

    it "keeps similar named subdirs in another base path if nested further" do
      Library.leaf_paths_of(["a", "a/aa", "a/aa/aaa", "b", "b/aa"]).should == ["a/aa/aaa", "b/aa"]
    end

    it "handles regular brackets in the path" do
      Library.leaf_paths_of(["a", "a/aa (123)"]).should == ["a/aa (123)"]
    end

    it "handles square brackets in the path" do
      Library.leaf_paths_of(["a", "a/aa [123]"]).should == ["a/aa [123]"]
    end

    it "handles square brackets with a dash in the path" do
      Library.leaf_paths_of(["a", "a/aa [mp3-123-456]"]).should == ["a/aa [mp3-123-456]"]
    end

    it "works" do
      paths = [
        'Music/Deadmau5',
        'Music/Deadmau5/At Play CD',
        'Music/Deadmau5/At Play CD/01 Deadmau5 - Vanishing Point.mp3',
        'Music/Deadmau5/At Play CD/02 Deadmau5 - Sex Lies Audiotape.mp3',
        'Music/Deadmau5/At Play CD/10 Melleefresh Vs Deadmau5 - Afterhours.mp3',
        'Music/Deadmau5/Mixmag Presents-Deadmau5 Tech_Trance_Electro Madness',
        'Music/Deadmau5/Mixmag Presents-Deadmau5 Tech_Trance_Electro Madness/01 Tech Trance Electro Madness.mp3',
        'Music/Deadmau5/Unknown Album',
        'Music/Deadmau5/Unknown Album/Live @ O2 Wireless Festival U',
      ]
      
      Library.leaf_paths_of(paths).should == [
        'Music/Deadmau5/At Play CD/01 Deadmau5 - Vanishing Point.mp3',
        'Music/Deadmau5/At Play CD/02 Deadmau5 - Sex Lies Audiotape.mp3',
        'Music/Deadmau5/At Play CD/10 Melleefresh Vs Deadmau5 - Afterhours.mp3',
        'Music/Deadmau5/Mixmag Presents-Deadmau5 Tech_Trance_Electro Madness/01 Tech Trance Electro Madness.mp3',
        'Music/Deadmau5/Unknown Album/Live @ O2 Wireless Festival U',
      ]
    end
  end
end