Siena Fast Forwarding Documentation

00001 // -*- C++ -*-
00002 //
00003 //  This file is part of Siena, a wide-area event notification system.
00004 //  See http://www.cs.colorado.edu/serl/siena/
00005 //
00006 //  Authors: Antonio Carzaniga <[email protected]>
00007 //  See the file AUTHORS for full details. 
00008 //
00009 //  Copyright (C) 2002 University of Colorado
00010 //
00011 //  This program is free software; you can redistribute it and/or
00012 //  modify it under the terms of the GNU General Public License
00013 //  as published by the Free Software Foundation; either version 2
00014 //  of the License, or (at your option) any later version.
00015 //
00016 //  This program is distributed in the hope that it will be useful,
00017 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00018 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019 //  GNU General Public License for more details.
00020 //
00021 //  You should have received a copy of the GNU General Public License
00022 //  along with this program; if not, write to the Free Software
00023 //  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
00024 //  USA, or send email to [email protected].
00025 //
00026 //
00027 // $Id: tst.h,v 1.15 2002/09/30 04:51:49 carzanig Exp $
00028 //
00029 #ifndef TST_H
00030 #define TST_H
00031 
00032 #include "ft_allocator.h"
00033 //
00034 // the basic TST algorithms are taken more or less directly from
00035 // R. Sedgewick's "Algorithms in C" 3rd Ed. pp 638--639.  All the rest
00036 // (next, prev, partial insert and match, etc.) is mine.
00037 //
00038 class TST;
00039 class PTST;
00040 class TSTNode;
00041 
00043 class TSTNode {
00044 public:
00045     void *              data;
00046 
00047                         TSTNode(char c, TSTNode * u);
00048 
00049     TSTNode *           next() const;
00050     TSTNode *           prev() const;
00051 
00052     TSTNode *           upper_bound(char s) const;
00053     TSTNode *           lower_bound(char s) const;
00054 
00055     void                print(int level = 0) const;
00056     bool                is_eos()                                        const;
00057 
00058 private:
00059     char                c;
00060     TSTNode *           up;
00061     TSTNode *           left;
00062     TSTNode *           middle;
00063     TSTNode *           right;
00064 
00065     TSTNode *           backtrack_prev() const;
00066     TSTNode *           backtrack_next() const;
00067 
00068     friend class TST;
00069     friend class PTST;
00070 };
00071 
00077 class TST {
00078 public:
00079                         TST();
00080 
00081     TSTNode *           insert(const char * s, FTAllocator & a);
00082     const TSTNode *     find(const char * s)                            const;
00083 
00084     TSTNode *           first()                                         const;
00085     TSTNode *           last()                                          const;
00086     void                print()                                         const;
00087     void                clear();
00088 
00089 protected:
00090     TSTNode *           root;
00091 };
00092 
00093 enum PartialResult {
00094     Found_Partial,
00095     Found_Complete,
00096     Not_Found
00097 };
00098 
00102 class PTST : public TST {
00103 public:
00104     PartialResult       find_partial(const TSTNode ** pp, 
00105                                      const char ** s) const;
00106     TSTNode *           insert_partial(const char * s, FTAllocator & a);
00107 };
00108 
00109 #ifdef HAVE_INLINE
00110 #include "tst.icc"
00111 #endif
00112 
00113 #endif