Created
September 9, 2014 20:57
-
-
Save jnschaeffer/3f6708c83dba41c76c83 to your computer and use it in GitHub Desktop.
Zipper interface
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package zipper | |
| import "fmt" | |
| type Ord int | |
| const ( | |
| LeftLess Ord = iota | |
| Equal | |
| RightLess | |
| ) | |
| func (o Ord) String() string { | |
| switch o { | |
| case LeftLess: | |
| return "LeftLess" | |
| case Equal: | |
| return "Equal" | |
| case RightLess: | |
| return "RightLess" | |
| default: | |
| return "?" | |
| } | |
| } | |
| // A Zipper represents a pair of ordered collections that can be zipped | |
| // together. Elements of each collection are assumed to be sorted in | |
| // ascending order. | |
| type Zipper interface { | |
| // LenLeft returns the length of the left collection. | |
| LenLeft() int | |
| // LenRight returns the length of the right collection. | |
| LenRight() int | |
| // Compare compares the left and right collection elements at i and j | |
| // respectively. If the left element is less than the right, Compare | |
| // should return LeftLess. The same applies for Equal and RightLess. | |
| // Any other value will cause a panic during Zip. | |
| Compare(i, j int) Ord | |
| // AddLeft adds only the element from the left collection at i to the | |
| // zipped collection. | |
| AddLeft(i int) | |
| // AddRight adds only the element from the right collection at j to the | |
| // zipped collection. | |
| AddRight(j int) | |
| // AddBoth adds both the left and right elements at i and j to the zipped | |
| // collection. | |
| AddBoth(i, j int) | |
| } | |
| // Zip iterates through each element in the collection, comparing each leading | |
| // element in each collection exactly once. Any two elements that are equal | |
| // will be zipped together by AddBoth, otherwise the lesser element will be | |
| // added on its own. Assumes the left and right collections are in ascending | |
| // order when ordered by z.Compare. | |
| func Zip(z Zipper) { | |
| i, j := 0, 0 | |
| maxLeft, maxRight := z.LenLeft(), z.LenRight() | |
| for i < maxLeft || j < maxRight { | |
| switch { | |
| case i >= maxLeft: | |
| z.AddRight(j) | |
| j += 1 | |
| case j >= maxRight: | |
| z.AddLeft(i) | |
| i += 1 | |
| default: | |
| switch c := z.Compare(i, j); { | |
| case c == LeftLess: | |
| z.AddLeft(i) | |
| i += 1 | |
| case c == RightLess: | |
| z.AddRight(j) | |
| j += 1 | |
| case c == Equal: | |
| z.AddBoth(i, j) | |
| i += 1 | |
| j += 1 | |
| default: | |
| msg := fmt.Sprintf("Zip: compare returned %d: expected %s, "+ | |
| "%s, or %s", c, LeftLess, Equal, RightLess) | |
| panic(msg) | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment