diff options
Diffstat (limited to 'vendor/github.com')
| -rw-r--r-- | vendor/github.com/jpillora/longestcommon/README.md | 45 | ||||
| -rw-r--r-- | vendor/github.com/jpillora/longestcommon/lc.go | 82 | ||||
| -rw-r--r-- | vendor/github.com/jpillora/longestcommon/lc_test.go | 111 |
3 files changed, 238 insertions, 0 deletions
diff --git a/vendor/github.com/jpillora/longestcommon/README.md b/vendor/github.com/jpillora/longestcommon/README.md new file mode 100644 index 0000000..f32d865 --- /dev/null +++ b/vendor/github.com/jpillora/longestcommon/README.md @@ -0,0 +1,45 @@ +# longestcommon + +Find the longest common prefix/suffix across of list of strings in Go (Golang). Runs in `O(n)`. + +[](https://godoc.org/github.com/jpillora/longestcommon) [](https://circleci.com/gh/jpillora/longestcommon) + +### Install + +``` +$ go get -v github.com/jpillora/longestcommon +``` + +### Usage + +``` go +longestcommon.Prefix([]string{"flower","flow","fleet"}) //"fl" +longestcommon.Suffix([]string{"flower","power","lower"}) //"ower" +``` + +### TODO + +* Include [Longest Common Subsequence](https://github.com/jpillora/lcs) with its TODOs completed + +#### MIT License + +Copyright © 2015 Jaime Pillora <dev@jpillora.com> + +Permission is hereby granted, free of charge, to any person obtaining +a copy of this software and associated documentation files (the +'Software'), to deal in the Software without restriction, including +without limitation the rights to use, copy, modify, merge, publish, +distribute, sublicense, and/or sell copies of the Software, and to +permit persons to whom the Software is furnished to do so, subject to +the following conditions: + +The above copyright notice and this permission notice shall be +included in all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND, +EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF +MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. +IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, +TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE +SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. diff --git a/vendor/github.com/jpillora/longestcommon/lc.go b/vendor/github.com/jpillora/longestcommon/lc.go new file mode 100644 index 0000000..788a7a6 --- /dev/null +++ b/vendor/github.com/jpillora/longestcommon/lc.go @@ -0,0 +1,82 @@ +package longestcommon + +import "strings" + +//TrimPrefix removes the longest common prefix from all provided strings +func TrimPrefix(strs []string) { + p := Prefix(strs) + if p == "" { + return + } + for i, s := range strs { + strs[i] = strings.TrimPrefix(s, p) + } +} + +//TrimSuffix removes the longest common suffix from all provided strings +func TrimSuffix(strs []string) { + p := Suffix(strs) + if p == "" { + return + } + for i, s := range strs { + strs[i] = strings.TrimSuffix(s, p) + } +} + +//Prefix returns the longest common prefix of the provided strings +func Prefix(strs []string) string { + return longestCommonXfix(strs, true) +} + +//Suffix returns the longest common suffix of the provided strings +func Suffix(strs []string) string { + return longestCommonXfix(strs, false) +} + +func longestCommonXfix(strs []string, pre bool) string { + //short-circuit empty list + if len(strs) == 0 { + return "" + } + xfix := strs[0] + //short-circuit single-element list + if len(strs) == 1 { + return xfix + } + //compare first to rest + for _, str := range strs[1:] { + xfixl := len(xfix) + strl := len(str) + //short-circuit empty strings + if xfixl == 0 || strl == 0 { + return "" + } + //maximum possible length + maxl := xfixl + if strl < maxl { + maxl = strl + } + //compare letters + if pre { + //prefix, iterate left to right + for i := 0; i < maxl; i++ { + if xfix[i] != str[i] { + xfix = xfix[:i] + break + } + } + } else { + //suffix, iternate right to left + for i := 0; i < maxl; i++ { + xi := xfixl - i - 1 + si := strl - i - 1 + if xfix[xi] != str[si] { + xfix = xfix[xi+1:] + break + } + } + } + } + return xfix +} diff --git a/vendor/github.com/jpillora/longestcommon/lc_test.go b/vendor/github.com/jpillora/longestcommon/lc_test.go new file mode 100644 index 0000000..136e3ff --- /dev/null +++ b/vendor/github.com/jpillora/longestcommon/lc_test.go @@ -0,0 +1,111 @@ +package longestcommon + +import ( + "strings" + "testing" +) + +func doTest(t *testing.T, lines, pre, suf string) { + strs := []string{} + if lines != "" { + strs = strings.Split(lines, "\n") + } + p := Prefix(strs) + if p != pre { + t.Fatalf("fail: expected prefix '%s', got '%s'", pre, p) + } + s := Suffix(strs) + if s != suf { + t.Fatalf("fail: expected suffix '%s', got '%s'", suf, s) + } +} + +func TestXFix1(t *testing.T) { + doTest(t, ``, "", "") +} + +func TestXFix2(t *testing.T) { + doTest(t, `single`, "single", "single") +} + +func TestXFix3(t *testing.T) { + doTest(t, "single\ndouble", "", "le") +} + +func TestXFix4(t *testing.T) { + doTest(t, "flower\nflow\nfleet", "fl", "") +} + +func TestXFix5(t *testing.T) { + doTest(t, `My Awesome Album - 01.mp3 +My Awesome Album - 11.mp3 +My Awesome Album - 03.mp3 +My Awesome Album - 04.mp3 +My Awesome Album - 05.mp3 +My Awesome Album - 06.mp3 +My Awesome Album - 07.mp3 +My Awesome Album - 08.mp3 +My Awesome Album - 09.mp3 +My Awesome Album - 10.mp3 +My Awesome Album - 11.mp3 +My Awesome Album - 12.mp3 +My Awesome Album - 13.mp3 +My Awesome Album - 14.mp3 +My Awesome Album - 15.mp3 +My Awesome Album - 16.mp3 +My Awesome Album - 17.mp3 +My Awesome Album - 18.mp3 +My Awesome Album - 19.mp3 +My Awesome Album - 20.mp3 +My Awesome Album - 21.mp3 +My Awesome Album - 22.mp3 +My Awesome Album - 23.mp3 +My Awesome Album - 24.mp3 +My Awesome Album - 25.mp3 +My Awesome Album - 26.mp3 +My Awesome Album - 27.mp3 +My Awesome Album - 28.mp3 +My Awesome Album - 29.mp3 +My Awesome Album - 30.mp3 +My Awesome Album - 31.mp3 +My Awesome Album - 32.mp3 +My Awesome Album - 33.mp3 +My Awesome Album - 34.mp3 +My Awesome Album - 35.mp3 +My Awesome Album - 36.mp3 +My Awesome Album - 37.mp3 +My Awesome Album - 38.mp3 +My Awesome Album - 39.mp3`, "My Awesome Album - ", ".mp3") +} + +func TestTrimPrefix1(t *testing.T) { + strs := []string{"flower", "flow", "fleet"} + TrimPrefix(strs) + if strs[0] != "ower" { + t.Fatalf("fail: expected result string to be 'ower', got '%s'", strs[0]) + } +} + +func TestTrimPrefix2(t *testing.T) { + strs := []string{"flower", "tree"} + TrimPrefix(strs) //no common prefix + if strs[0] != "flower" { + t.Fatalf("fail: expected result string to be 'flower', got '%s'", strs[0]) + } +} + +func TestTrimSuffix1(t *testing.T) { + strs := []string{"flower", "power"} + TrimSuffix(strs) + if strs[0] != "fl" { + t.Fatalf("fail: expected result string to be 'fl', got '%s'", strs[0]) + } +} + +func TestTrimSuffix2(t *testing.T) { + strs := []string{"flower", "tree"} + TrimSuffix(strs) //no common suffix + if strs[0] != "flower" { + t.Fatalf("fail: expected result string to be 'flower', got '%s'", strs[0]) + } +} |