B-Tree Page API Example from Robert Sedgewick & Kevin Wayne

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

B-Tree Page API Example from Robert Sedgewick & Kevin Wayne

Henry Roeland
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 mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry