aapl/bstset.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_BSTSET_H
  23 #define _AAPL_BSTSET_H
  24
  25 /**
  26  * \addtogroup bst
  27  * @{
  28  */
  29
  30 /**
  31  * \class BstSet
  32  * \brief Binary search table for types that are the key.
  33  *
  34  * BstSet is suitable for types that comprise the entire key. Rather than look
  35  * into the element to retrieve the key, the element is the key. A class that
  36  * contains a comparison routine for the key must be given.
  37  */
  38
  39 /*@}*/
  40
  41 #include "compare.h"
  42 #include "vector.h"
  43
  44 #define BST_TEMPL_DECLARE class Key, class Compare = CmpOrd<Key>, \
  45                 class Resize = ResizeExpn
  46 #define BST_TEMPL_DEF class Key, class Compare, class Resize
  47 #define BST_TEMPL_USE Key, Compare, Resize
  48 #define GET_KEY(el) (el)
  49 #define BstTable BstSet
  50 #define Element Key
  51 #define BSTSET
  52
  53 #include "bstcommon.h"
  54
  55 #undef BST_TEMPL_DECLARE
  56 #undef BST_TEMPL_DEF
  57 #undef BST_TEMPL_USE
  58 #undef GET_KEY
  59 #undef BstTable
  60 #undef Element
  61 #undef BSTSET
  62
  63 /**
  64  * \fn BstSet::insert(const Key &key, Key **lastFound)
  65  * \brief Insert the given key.
  66  *
  67  * If the given key does not already exist in the table then it is inserted.
  68  * The key's copy constructor is used to place the item in the table. If
  69  * lastFound is given, it is set to the new entry created. If the insert fails
  70  * then lastFound is set to the existing key of the same value.
  71  *
  72  * \returns The new element created upon success, null upon failure.
  73  */
  74
  75 /**
  76  * \fn BstSet::insertMulti(const Key &key)
  77  * \brief Insert the given key even if it exists already.
  78  *
  79  * If the key exists already then it is placed next to some other key of the
  80  * same value. InsertMulti cannot fail. The key's copy constructor is used to
  81  * place the item in the table.
  82  *
  83  * \returns The new element created.
  84  */
  85
  86 #endif /* _AAPL_BSTSET_H */