alaroldai / gofingertree Goto Github PK

Implement Popr. Currently included as part of pull request #2. After this, the empty, single, and ftree structures should be usable as deques.

Rewrite the fold tests to use a non-associative operation rather than (+), as the current implementation doesn't test the direction of the fold.

@nshepperd - saw your comment in empty.Tailr() - do you think it would make sense for empty.Tailr() to return an empty node, rather than nil? That way we could chain operations together more easily, for example replacing the last element in a sequence could be done with n.Tailr().Pushr(newNode)

Implement sequence concatenation.
Six major scenarios:

• (empty) + (empty) => empty
• (empty) + (single) => return right
• (empty) + (ftree) => return right
• (single) + (empty) => return left
• (single) + (single) => reduces to Pushl or Pushr
• (single) + (ftree) => reduces to Pushl
• (ftree) + (empty) => return left
• (ftree) + (single) => reduces to Pushr
• (ftree) + (ftree) => Non-trivial.

I'm looking at this now.

At the moment, all of these structures are in fingerTree.go. This refactor will move each structure into it's own file, leaving only the FingerTree interface in fingerTree.go. This also makes room for a wrapper structure to be introduced later.

In addition, the Foldable and Iterable interfaces should be moved into fold.go and tier.go, respectively, and the tests should be split up accordingly.