aapl/bstmap.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_BSTMAP_H
  23 #define _AAPL_BSTMAP_H
  24
  25 #include "compare.h"
  26 #include "vector.h"
  27
  28 #ifdef AAPL_NAMESPACE
  29 namespace Aapl {
  30 #endif
  31
  32 /**
  33  * \brief Element for BstMap.
  34  *
  35  * Stores the key and value pair.
  36  */
  37 template <class Key, class Value> struct BstMapEl
  38 {
  39         BstMapEl() {}
  40         BstMapEl(const Key &key) : key(key) {}
  41         BstMapEl(const Key &key, const Value &val) : key(key), value(val) {}
  42
  43         /** \brief The key */
  44         Key key;
  45
  46         /** \brief The value. */
  47         Value value;
  48 };
  49
  50 #ifdef AAPL_NAMESPACE
  51 }
  52 #endif
  53
  54 /**
  55  * \addtogroup bst
  56  * @{
  57  */
  58
  59 /**
  60  * \class BstMap
  61  * \brief Binary search table for key and value pairs.
  62  *
  63  * BstMap stores key and value pairs in each element. The key and value can be
  64  * any type. A compare class for the key must be supplied.
  65  */
  66
  67 /*@}*/
  68
  69 #define BST_TEMPL_DECLARE class Key, class Value, \
  70                 class Compare = CmpOrd<Key>, class Resize = ResizeExpn
  71 #define BST_TEMPL_DEF class Key, class Value, class Compare, class Resize
  72 #define BST_TEMPL_USE Key, Value, Compare, Resize
  73 #define GET_KEY(el) ((el).key)
  74 #define BstTable BstMap
  75 #define Element BstMapEl<Key, Value>
  76 #define BSTMAP
  77
  78 #include "bstcommon.h"
  79
  80 #undef BST_TEMPL_DECLARE
  81 #undef BST_TEMPL_DEF
  82 #undef BST_TEMPL_USE
  83 #undef GET_KEY
  84 #undef BstTable
  85 #undef Element
  86 #undef BSTMAP
  87
  88 /**
  89  * \fn BstMap::insert(const Key &key, BstMapEl<Key, Value> **lastFound)
  90  * \brief Insert the given key.
  91  *
  92  * If the given key does not already exist in the table then a new element
  93  * having key is inserted. They key copy constructor and value default
  94  * constructor are used to place the pair in the table. If lastFound is given,
  95  * it is set to the new entry created. If the insert fails then lastFound is
  96  * set to the existing pair of the same key.
  97  *
  98  * \returns The new element created upon success, null upon failure.
  99  */
 100
 101 /**
 102  * \fn BstMap::insertMulti(const Key &key)
 103  * \brief Insert the given key even if it exists already.
 104  *
 105  * If the key exists already then the new element having key is placed next
 106  * to some other pair of the same key. InsertMulti cannot fail. The key copy
 107  * constructor and the value default constructor are used to place the pair in
 108  * the table.
 109  *
 110  * \returns The new element created.
 111  */
 112
 113 #endif /* _AAPL_BSTMAP_H */