Bidirectional cursors.

1 files changed, 53 insertions, 1 deletions

diff --git a/cursor.go b/cursor.go
index 410bb89..9a527af 100644
--- a/cursor.go
+++ b/cursor.go
@@ -19,11 +19,24 @@ func (c *Cursor) First() (key []byte, value []byte) {
 	if len(c.stack) > 0 {
 		c.stack = c.stack[:0]
 	}
-	c.stack = append(c.stack, pageElementRef{page: c.transaction.page(c.root), index: 0})
+	p := c.transaction.page(c.root)
+	c.stack = append(c.stack, pageElementRef{page: p, index: 0})
 	c.first()
 	return c.keyValue()
 }
 
+// Last moves the cursor to the last item in the bucket and returns its key and value.
+// If the bucket is empty then a nil key and value are returned.
+func (c *Cursor) Last() (key []byte, value []byte) {
+	if len(c.stack) > 0 {
+		c.stack = c.stack[:0]
+	}
+	p := c.transaction.page(c.root)
+	c.stack = append(c.stack, pageElementRef{page: p, index: p.count - 1})
+	c.last()
+	return c.keyValue()
+}
+
 // Next moves the cursor to the next item in the bucket and returns its key and value.
 // If the cursor is at the end of the bucket then a nil key and value are returned.
 func (c *Cursor) Next() (key []byte, value []byte) {
@@ -48,6 +61,30 @@ func (c *Cursor) Next() (key []byte, value []byte) {
 	return c.keyValue()
 }
 
+// Prev moves the cursor to the previous item in the bucket and returns its key and value.
+// If the cursor is at the beginning of the bucket then a nil key and value are returned.
+func (c *Cursor) Prev() (key []byte, value []byte) {
+	// Attempt to move back one element until we're successful.
+	// Move up the stack as we hit the beginning of each page in our stack.
+	for i := len(c.stack) - 1; i >= 0; i-- {
+		elem := &c.stack[i]
+		if elem.index > 0 {
+			elem.index--
+			break
+		}
+		c.stack = c.stack[:i]
+	}
+
+	// If we've hit the end then return nil.
+	if len(c.stack) == 0 {
+		return nil, nil
+	}
+
+	// Move down the stack to find the last element of the last leaf under this branch.
+	c.last()
+	return c.keyValue()
+}
+
 // Seek moves the cursor to a given key and returns it.
 // If the key does not exist then the next key is used. If no keys
 // follow, a nil value is returned.
@@ -80,6 +117,21 @@ func (c *Cursor) first() {
 	}
 }
 
+// last moves the cursor to the last leaf element under the last page in the stack.
+func (c *Cursor) last() {
+	p := c.stack[len(c.stack)-1].page
+	for {
+		// Exit when we hit a leaf page.
+		if (p.flags & leafPageFlag) != 0 {
+			break
+		}
+
+		// Keep adding pages pointing to the last element in the stack.
+		p = c.transaction.page(p.branchPageElement(c.stack[len(c.stack)-1].index).pgid)
+		c.stack = append(c.stack, pageElementRef{page: p, index: p.count - 1})
+	}
+}
+
 // search recursively performs a binary search against a given page until it finds a given key.
 func (c *Cursor) search(key []byte, p *page) {
 	_assert((p.flags&(branchPageFlag|leafPageFlag)) != 0, "invalid page type: "+p.typ())