aapl/sbstset.h

   1 /*
   2  *  Copyright 2002 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Aapl.
   6  *
   7  *  Aapl is free software; you can redistribute it and/or modify it under the
   8  *  terms of the GNU Lesser General Public License as published by the Free
   9  *  Software Foundation; either version 2.1 of the License, or (at your option)
  10  *  any later version.
  11  *
  12  *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
  13  *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14  *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
  15  *  more details.
  16  *
  17  *  You should have received a copy of the GNU Lesser General Public License
  18  *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
  19  *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20  */
  21
  22 #ifndef _AAPL_SBSTSET_H
  23 #define _AAPL_SBSTSET_H
  24
  25 /**
  26  * \addtogroup bst
  27  * @{
  28  */
  29
  30 /**
  31  * \class SBstSet
  32  * \brief Copy-on-write binary search table for types that are the key.
  33  *
  34  * This is a set style binary search table that employs the copy-on-write
  35  * mechanism for storing table data. BstSet is suitable for types that
  36  * comprise the entire key. Rather than look into the element to retrieve the
  37  * key, the element is the key.  A class that contains a comparison routine
  38  * for the key must be given.
  39  */
  40
  41 /*@}*/
  42
  43 #include "compare.h"
  44 #include "svector.h"
  45
  46 #define BST_TEMPL_DECLARE class Key, class Compare = CmpOrd<Key>, \
  47                 class Resize = ResizeExpn
  48 #define BST_TEMPL_DEF class Key, class Compare, class Resize
  49 #define BST_TEMPL_USE Key, Compare, Resize
  50 #define GET_KEY(el) (el)
  51 #define BstTable SBstSet
  52 #define Vector SVector
  53 #define Table STable
  54 #define Element Key
  55 #define BSTSET
  56 #define SHARED_BST
  57
  58 #include "bstcommon.h"
  59
  60 #undef BST_TEMPL_DECLARE
  61 #undef BST_TEMPL_DEF
  62 #undef BST_TEMPL_USE
  63 #undef GET_KEY
  64 #undef BstTable
  65 #undef Vector
  66 #undef Table
  67 #undef Element
  68 #undef BSTSET
  69 #undef SHARED_BST
  70
  71 /**
  72  * \fn SBstSet::insert(const Key &key, Key **lastFound)
  73  * \brief Insert the given key.
  74  *
  75  * If the given key does not already exist in the table then it is inserted.
  76  * The key's copy constructor is used to place the item in the table. If
  77  * lastFound is given, it is set to the new entry created. If the insert fails
  78  * then lastFound is set to the existing key of the same value.
  79  *
  80  * \returns The new element created upon success, null upon failure.
  81  */
  82
  83 /**
  84  * \fn SBstSet::insertMulti(const Key &key)
  85  * \brief Insert the given key even if it exists already.
  86  *
  87  * If the key exists already then it is placed next to some other key of the
  88  * same value. InsertMulti cannot fail. The key's copy constructor is used to
  89  * place the item in the table.
  90  *
  91  * \returns The new element created.
  92  */
  93
  94 #endif /* _AAPL_SBSTSET_H */