initial support for large objects

This has gone through a lot of iterations on my branch, and I'm quite
happy with the parts of the API that exist now. Test coverage can still
be better, and will get better in the following commits.

The API is not yet finished: I want to add Options arguments to
Object.Upload(), Object.Copy(), Object.Move() and Object.Delete() that
specify how each of these operations affect existing segments (and,
later, also existing symlinks). For Upload(), uploading in segments
shall become as easy as flipping a single switch.

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)`.
+
+[![GoDoc](https://godoc.org/github.com/jpillora/longestcommon?status.svg)](https://godoc.org/github.com/jpillora/longestcommon) [![Circle CI](https://circleci.com/gh/jpillora/longestcommon.svg?style=shield)](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])
+	}
+}