kd_dump.cpp

Go to the documentation of this file.

//----------------------------------------------------------------------
// File:                        kd_dump.cc
// Programmer:          David Mount
// Description:         Dump and Load for kd- and bd-trees
// Last modified:       01/04/05 (Version 1.0)
//----------------------------------------------------------------------
// Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
// David Mount.  All Rights Reserved.
// 
// This software and related documentation is part of the Approximate
// Nearest Neighbor Library (ANN).  This software is provided under
// the provisions of the Lesser GNU Public License (LGPL).  See the
// file ../ReadMe.txt for further information.
// 
// The University of Maryland (U.M.) and the authors make no
// representations about the suitability or fitness of this software for
// any purpose.  It is provided "as is" without express or implied
// warranty.
//----------------------------------------------------------------------
// History:
//      Revision 0.1  03/04/98
//              Initial release
//      Revision 1.0  04/01/05
//              Moved dump out of kd_tree.cc into this file.
//              Added kd-tree load constructor.
//----------------------------------------------------------------------
// This file contains routines for dumping kd-trees and bd-trees and
// reloading them. (It is an abuse of policy to include both kd- and
// bd-tree routines in the same file, sorry.  There should be no problem
// in deleting the bd- versions of the routines if they are not
// desired.)
//----------------------------------------------------------------------

#include "kd_tree.h"                                    // kd-tree declarations
#include "bd_tree.h"                                    // bd-tree declarations

using namespace std;                                    // make std:: available

//----------------------------------------------------------------------
//              Constants
//----------------------------------------------------------------------

const int               STRING_LEN              = 500;  // maximum string length
const double    EPSILON                 = 1E-5; // small number for float comparison

enum ANNtreeType {KD_TREE, BD_TREE};    // tree types (used in loading)

//----------------------------------------------------------------------
//              Procedure declarations
//----------------------------------------------------------------------

static ANNkd_ptr annReadDump(                   // read dump file
        istream                         &in,                                    // input stream
        ANNtreeType                     tree_type,                              // type of tree expected
        ANNpointArray           &the_pts,                               // new points (if applic)
        ANNidxArray                     &the_pidx,                              // point indices (returned)
        int                                     &the_dim,                               // dimension (returned)
        int                                     &the_n_pts,                             // number of points (returned)
        int                                     &the_bkt_size,                  // bucket size (returned)
        ANNpoint                        &the_bnd_box_lo,                // low bounding point
        ANNpoint                        &the_bnd_box_hi);               // high bounding point

static ANNkd_ptr annReadTree(                   // read tree-part of dump file
        istream                         &in,                                    // input stream
        ANNtreeType                     tree_type,                              // type of tree expected
        ANNidxArray                     the_pidx,                               // point indices (modified)
        int                                     &next_idx);                             // next index (modified)

//----------------------------------------------------------------------
//      ANN kd- and bd-tree Dump Format
//              The dump file begins with a header containing the version of
//              ANN, an optional section containing the points, followed by
//              a description of the tree.      The tree is printed in preorder.
//
//              Format:
//              #ANN <version number> <comments> [END_OF_LINE]
//              points <dim> <n_pts>                    (point coordinates: this is optional)
//              0 <xxx> <xxx> ... <xxx>                 (point indices and coordinates)
//              1 <xxx> <xxx> ... <xxx>
//                ...
//              tree <dim> <n_pts> <bkt_size>
//              <xxx> <xxx> ... <xxx>                   (lower end of bounding box)
//              <xxx> <xxx> ... <xxx>                   (upper end of bounding box)
//                              If the tree is null, then a single line "null" is
//                              output.  Otherwise the nodes of the tree are printed
//                              one per line in preorder.  Leaves and splitting nodes 
//                              have the following formats:
//              Leaf node:
//                              leaf <n_pts> <bkt[0]> <bkt[1]> ... <bkt[n-1]>
//              Splitting nodes:
//                              split <cut_dim> <cut_val> <lo_bound> <hi_bound>
//
//              For bd-trees:
//
//              Shrinking nodes:
//                              shrink <n_bnds>
//                                              <cut_dim> <cut_val> <side>
//                                              <cut_dim> <cut_val> <side>
//                                              ... (repeated n_bnds times)
//----------------------------------------------------------------------

void ANNkd_tree::Dump(                                  // dump entire tree
                ANNbool with_pts,                               // print points as well?
                ostream &out)                                   // output stream
{
        out << "#ANN " << ANNversion << "\n";
        out.precision(ANNcoordPrec);            // use full precision in dumping
        if (with_pts) {                                         // print point coordinates
                out << "points " << dim << " " << n_pts << "\n";
                for (int i = 0; i < n_pts; i++) {
                        out << i << " ";
                        annPrintPt(pts[i], dim, out);
                        out << "\n";
                }
        }
        out << "tree "                                          // print tree elements
                << dim << " "
                << n_pts << " "
                << bkt_size << "\n";

        annPrintPt(bnd_box_lo, dim, out);       // print lower bound
        out << "\n";
        annPrintPt(bnd_box_hi, dim, out);       // print upper bound
        out << "\n";

        if (root == NULL)                                       // empty tree?
                out << "null\n";
        else {
                root->dump(out);                                // invoke printing at root
        }
        out.precision(0);                                       // restore default precision
}

void ANNkd_split::dump(                                 // dump a splitting node
                ostream &out)                                   // output stream
{
        out << "split " << cut_dim << " " << cut_val << " ";
        out << cd_bnds[ANN_LO] << " " << cd_bnds[ANN_HI] << "\n";

        child[ANN_LO]->dump(out);                       // print low child
        child[ANN_HI]->dump(out);                       // print high child
}

void ANNkd_leaf::dump(                                  // dump a leaf node
                ostream &out)                                   // output stream
{
        if (this == KD_TRIVIAL) {                       // canonical trivial leaf node
                out << "leaf 0\n";                              // leaf no points
        }
        else{
                out << "leaf " << n_pts;
                for (int j = 0; j < n_pts; j++) {
                        out << " " << bkt[j];
                }
                out << "\n";
        }
}

void ANNbd_shrink::dump(                                // dump a shrinking node
                ostream &out)                                   // output stream
{
        out << "shrink " << n_bnds << "\n";
        for (int j = 0; j < n_bnds; j++) {
                out << bnds[j].cd << " " << bnds[j].cv << " " << bnds[j].sd << "\n";
        }
        child[ANN_IN]->dump(out);                       // print in-child
        child[ANN_OUT]->dump(out);                      // print out-child
}

//----------------------------------------------------------------------
// Load kd-tree from dump file
//              This rebuilds a kd-tree which was dumped to a file.      The dump
//              file contains all the basic tree information according to a
//              preorder traversal.      We assume that the dump file also contains
//              point data.      (This is to guarantee the consistency of the tree.)
//              If not, then an error is generated.
//
//              Indirectly, this procedure allocates space for points, point
//              indices, all nodes in the tree, and the bounding box for the
//              tree.  When the tree is destroyed, all but the points are
//              deallocated.
//
//              This routine calls annReadDump to do all the work.
//----------------------------------------------------------------------

ANNkd_tree::ANNkd_tree(                                 // build from dump file
        istream                         &in)                                    // input stream for dump file
{
        int the_dim;                                                            // local dimension
        int the_n_pts;                                                          // local number of points
        int the_bkt_size;                                                       // local number of points
        ANNpoint the_bnd_box_lo;                                        // low bounding point
        ANNpoint the_bnd_box_hi;                                        // high bounding point
        ANNpointArray the_pts;                                          // point storage
        ANNidxArray the_pidx;                                           // point index storage
        ANNkd_ptr the_root;                                                     // root of the tree

        the_root = annReadDump(                                         // read the dump file
                in,                                                                             // input stream
                KD_TREE,                                                                // expecting a kd-tree
                the_pts,                                                                // point array (returned)
                the_pidx,                                                               // point indices (returned)
                the_dim, the_n_pts, the_bkt_size,               // basic tree info (returned)
                the_bnd_box_lo, the_bnd_box_hi);                // bounding box info (returned)

                                                                                                // create a skeletal tree
        SkeletonTree(the_n_pts, the_dim, the_bkt_size, the_pts, the_pidx);

        bnd_box_lo = the_bnd_box_lo;
        bnd_box_hi = the_bnd_box_hi;

        root = the_root;                                                        // set the root
}

ANNbd_tree::ANNbd_tree(                                 // build bd-tree from dump file
        istream                         &in) : ANNkd_tree()             // input stream for dump file
{
        int the_dim;                                                            // local dimension
        int the_n_pts;                                                          // local number of points
        int the_bkt_size;                                                       // local number of points
        ANNpoint the_bnd_box_lo;                                        // low bounding point
        ANNpoint the_bnd_box_hi;                                        // high bounding point
        ANNpointArray the_pts;                                          // point storage
        ANNidxArray the_pidx;                                           // point index storage
        ANNkd_ptr the_root;                                                     // root of the tree

        the_root = annReadDump(                                         // read the dump file
                in,                                                                             // input stream
                BD_TREE,                                                                // expecting a bd-tree
                the_pts,                                                                // point array (returned)
                the_pidx,                                                               // point indices (returned)
                the_dim, the_n_pts, the_bkt_size,               // basic tree info (returned)
                the_bnd_box_lo, the_bnd_box_hi);                // bounding box info (returned)

                                                                                                // create a skeletal tree
        SkeletonTree(the_n_pts, the_dim, the_bkt_size, the_pts, the_pidx);
        bnd_box_lo = the_bnd_box_lo;
        bnd_box_hi = the_bnd_box_hi;

        root = the_root;                                                        // set the root
}

//----------------------------------------------------------------------
//      annReadDump - read a dump file
//
//              This procedure reads a dump file, constructs a kd-tree
//              and returns all the essential information needed to actually
//              construct the tree.      Because this procedure is used for
//              constructing both kd-trees and bd-trees, the second argument
//              is used to indicate which type of tree we are expecting.
//----------------------------------------------------------------------

static ANNkd_ptr annReadDump(
        istream                         &in,                                    // input stream
        ANNtreeType                     tree_type,                              // type of tree expected
        ANNpointArray           &the_pts,                               // new points (returned)
        ANNidxArray                     &the_pidx,                              // point indices (returned)
        int                                     &the_dim,                               // dimension (returned)
        int                                     &the_n_pts,                             // number of points (returned)
        int                                     &the_bkt_size,                  // bucket size (returned)
        ANNpoint                        &the_bnd_box_lo,                // low bounding point (ret'd)
        ANNpoint                        &the_bnd_box_hi)                // high bounding point (ret'd)
{
        int j;
        char str[STRING_LEN];                                           // storage for string
        char version[STRING_LEN];                                       // ANN version number
        ANNkd_ptr the_root = NULL;

        //------------------------------------------------------------------
        //      Input file header
        //------------------------------------------------------------------
        in >> str;                                                                      // input header
        if (strcmp(str, "#ANN") != 0) {                         // incorrect header
                annError("Incorrect header for dump file", ANNabort);
        }
        in.getline(version, STRING_LEN);                        // get version (ignore)

        //------------------------------------------------------------------
        //      Input the points
        //                      An array the_pts is allocated and points are read from
        //                      the dump file.
        //------------------------------------------------------------------
        in >> str;                                                                      // get major heading
        if (strcmp(str, "points") == 0) {                       // points section
                in >> the_dim;                                                  // input dimension
                in >> the_n_pts;                                                // number of points
                                                                                                // allocate point storage
                the_pts = annAllocPts(the_n_pts, the_dim);
                for (int i = 0; i < the_n_pts; i++) {   // input point coordinates
                        ANNidx idx;                                                     // point index
                        in >> idx;                                                      // input point index
                        if (idx < 0 || idx >= the_n_pts) {
                                annError("Point index is out of range", ANNabort);
                        }
                        for (j = 0; j < the_dim; j++) {
                                in >> the_pts[idx][j];                  // read point coordinates
                        }
                }
                in >> str;                                                              // get next major heading
        }
        else {                                                                          // no points were input
                annError("Points must be supplied in the dump file", ANNabort);
        }

        //------------------------------------------------------------------
        //      Input the tree
        //                      After the basic header information, we invoke annReadTree
        //                      to do all the heavy work.  We create our own array of
        //                      point indices (so we can pass them to annReadTree())
        //                      but we do not deallocate them.  They will be deallocated
        //                      when the tree is destroyed.
        //------------------------------------------------------------------
        if (strcmp(str, "tree") == 0) {                         // tree section
                in >> the_dim;                                                  // read dimension
                in >> the_n_pts;                                                // number of points
                in >> the_bkt_size;                                             // bucket size
                the_bnd_box_lo = annAllocPt(the_dim);   // allocate bounding box pts
                the_bnd_box_hi = annAllocPt(the_dim);

                for (j = 0; j < the_dim; j++) {                 // read bounding box low
                        in >> the_bnd_box_lo[j];
                }
                for (j = 0; j < the_dim; j++) {                 // read bounding box low
                        in >> the_bnd_box_hi[j];
                }
                the_pidx = new ANNidx[the_n_pts];               // allocate point index array
                int next_idx = 0;                                               // number of indices filled
                                                                                                // read the tree and indices
                the_root = annReadTree(in, tree_type, the_pidx, next_idx);
                if (next_idx != the_n_pts) {                    // didn't see all the points?
                        annError("Didn't see as many points as expected", ANNwarn);
                }
        }
        else {
                annError("Illegal dump format.  Expecting section heading", ANNabort);
        }
        return the_root;
}

//----------------------------------------------------------------------
// annReadTree - input tree and return pointer
//
//              annReadTree reads in a node of the tree, makes any recursive
//              calls as needed to input the children of this node (if internal).
//              It returns a pointer to the node that was created.      An array
//              of point indices is given along with a pointer to the next
//              available location in the array.  As leaves are read, their
//              point indices are stored here, and the point buckets point
//              to the first entry in the array.
//
//              Recall that these are the formats.      The tree is given in
//              preorder.
//
//              Leaf node:
//                              leaf <n_pts> <bkt[0]> <bkt[1]> ... <bkt[n-1]>
//              Splitting nodes:
//                              split <cut_dim> <cut_val> <lo_bound> <hi_bound>
//
//              For bd-trees:
//
//              Shrinking nodes:
//                              shrink <n_bnds>
//                                              <cut_dim> <cut_val> <side>
//                                              <cut_dim> <cut_val> <side>
//                                              ... (repeated n_bnds times)
//----------------------------------------------------------------------

static ANNkd_ptr annReadTree(
        istream                         &in,                                    // input stream
        ANNtreeType                     tree_type,                              // type of tree expected
        ANNidxArray                     the_pidx,                               // point indices (modified)
        int                                     &next_idx)                              // next index (modified)
{
        char tag[STRING_LEN];                                           // tag (leaf, split, shrink)
        int n_pts;                                                                      // number of points in leaf
        int cd;                                                                         // cut dimension
        ANNcoord cv;                                                            // cut value
        ANNcoord lb;                                                            // low bound
        ANNcoord hb;                                                            // high bound
        int n_bnds;                                                                     // number of bounding sides
        int sd;                                                                         // which side

        in >> tag;                                                                      // input node tag

        if (strcmp(tag, "null") == 0) {                         // null tree
                return NULL;
        }
        //------------------------------------------------------------------
        //      Read a leaf
        //------------------------------------------------------------------
        if (strcmp(tag, "leaf") == 0) {                         // leaf node

                in >> n_pts;                                                    // input number of points
                int old_idx = next_idx;                                 // save next_idx
                if (n_pts == 0) {                                               // trivial leaf
                        return KD_TRIVIAL;
                }
                else {
                        for (int i = 0; i < n_pts; i++) {       // input point indices
                                in >> the_pidx[next_idx++];             // store in array of indices
                        }
                }
                return new ANNkd_leaf(n_pts, &the_pidx[old_idx]);
        }
        //------------------------------------------------------------------
        //      Read a splitting node
        //------------------------------------------------------------------
        else if (strcmp(tag, "split") == 0) {           // splitting node

                in >> cd >> cv >> lb >> hb;

                                                                                                // read low and high subtrees
                ANNkd_ptr lc = annReadTree(in, tree_type, the_pidx, next_idx);
                ANNkd_ptr hc = annReadTree(in, tree_type, the_pidx, next_idx);
                                                                                                // create new node and return
                return new ANNkd_split(cd, cv, lb, hb, lc, hc);
        }
        //------------------------------------------------------------------
        //      Read a shrinking node (bd-tree only)
        //------------------------------------------------------------------
        else if (strcmp(tag, "shrink") == 0) {          // shrinking node
                if (tree_type != BD_TREE) {
                        annError("Shrinking node not allowed in kd-tree", ANNabort);
                }

                in >> n_bnds;                                                   // number of bounding sides
                                                                                                // allocate bounds array
                ANNorthHSArray bds = new ANNorthHalfSpace[n_bnds];
                for (int i = 0; i < n_bnds; i++) {
                        in >> cd >> cv >> sd;                           // input bounding halfspace
                                                                                                // copy to array
                        bds[i] = ANNorthHalfSpace(cd, cv, sd);
                }
                                                                                                // read inner and outer subtrees
                ANNkd_ptr ic = annReadTree(in, tree_type, the_pidx, next_idx);
                ANNkd_ptr oc = annReadTree(in, tree_type, the_pidx, next_idx);
                                                                                                // create new node and return
                return new ANNbd_shrink(n_bnds, bds, ic, oc);
        }
        else {
                annError("Illegal node type in dump file", ANNabort);
                exit(0);                                                                // to keep the compiler happy
        }
}