Boost logo

Geometry :

Subject: [geometry] B-Tree Page API Example from Robert Sedgewick & Kevin Wayne
From: Henry Roeland (henry_at_[hidden])
Date: 2014-11-30 06:43:02

Dear all,

This morning I stumbled upon a B-Tree Page API Example from Robert Sedgewick & Kevin Wayne (Algorithms 4/e).

Its in Java but can easily be transformed into C++:

public class Page<Key>

                                Page(boolean bottom) // create and open a page

void close() // close a page

void add(Key key) // add key into the (external) page

void add(Page p) // open p and add an entry into this
                                                                                        // (internal) page that associates
                                                                                        // the smallest key in p with p

boolean isExternal() // Is this page external?

boolean contains(Key key) // is key in the page?

Page next(Key key) // the subtree that could contain the key

boolean isFull() // has the page overflowed?

Page split() // move the highest-ranking half of the
                                                                                        // keys in the page to a new page

Iterable<Key> keys() // iterator for the keys on the page


Is this useable as starting point for our Page API?
What should be different for an R*Tree?
Already answers some questions from my previous e-mail: Key(coordinates) should always be known.

For your information,

Kind regards,

Henry Roeland

Geometry list run by mateusz at