iLab Neuromorphic Robotics Toolkit  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
IdTable.H
Go to the documentation of this file.
1 /*! @file
2  @author Randolph Voorhies
3  @copyright GNU Public License (GPL v3)
4  @section License
5  @verbatim
6  // ////////////////////////////////////////////////////////////////////////
7  // The iLab Neuromorphic Robotics Toolkit (NRT) //
8  // Copyright 2010-2012 by the University of Southern California (USC) //
9  // and the iLab at USC. //
10  // //
11  // iLab - University of Southern California //
12  // Hedco Neurociences Building, Room HNB-10 //
13  // Los Angeles, Ca 90089-2520 - USA //
14  // //
15  // See http://ilab.usc.edu for information about this project. //
16  // ////////////////////////////////////////////////////////////////////////
17  // This file is part of The iLab Neuromorphic Robotics Toolkit. //
18  // //
19  // The iLab Neuromorphic Robotics Toolkit is free software: you can //
20  // redistribute it and/or modify it under the terms of the GNU General //
21  // Public License as published by the Free Software Foundation, either //
22  // version 3 of the License, or (at your option) any later version. //
23  // //
24  // The iLab Neuromorphic Robotics Toolkit is distributed in the hope //
25  // that it will be useful, but WITHOUT ANY WARRANTY; without even the //
26  // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR //
27  // PURPOSE. See the GNU General Public License for more details. //
28  // //
29  // You should have received a copy of the GNU General Public License //
30  // along with The iLab Neuromorphic Robotics Toolkit. If not, see //
31  // <http://www.gnu.org/licenses/>. //
32  // ////////////////////////////////////////////////////////////////////////
33  @endverbatim */
34 
35 
36 #ifndef INCLUDE_NRT_CORE_DESIGN_IDTABLE_H
37 #define INCLUDE_NRT_CORE_DESIGN_IDTABLE_H
38 
39 #include <unordered_map>
40 #include <queue>
41 #include <stddef.h> // for size_t
42 
43 namespace nrt
44 {
45  //! A table used to store linked value and id types supporting lookups on both.
46  /*! The IdTable class provides a way to associate a given value with an Id. Looking up a value by its id, or an id by
47  its value are both very fast operations because the IdTable keeps track of both forward and reverse lookup tables.
48 
49  IdTable keeps track of the number of "users" for each Id. Each time create() is called, a user count is
50  incremented, and each time remove() is called it is decremented. If the count becomes zero during a remove(), the
51  Id is destroyed.
52 
53  \note Care must be taken when using this structure in a multithreaded environment. If not locked properly, the
54  internal structures could get messed-up.
55 
56  \ingroup design */
57  template<class ValueType, class IdType = size_t>
58  class IdTable
59  {
60  public:
61  IdTable();
62 
63  //! Create a new entry by value (or just increment user count if entry exists), and return the Id
64  IdType create(ValueType const & value);
65 
66  //! Get a value by its id
67  /*! \throw IdNotFoundException Thrown if id does not exist in the table. */
68  ValueType get(IdType const & id) const;
69 
70  //! Get an id by value
71  /*! \throw ValueNotFoundException Thrown if value does not exist in the table. */
72  IdType get(ValueType const & value) const;
73 
74  //! Create a new entry by value if it does not already exist, and return the associated Id
75  /*! Note that this does not increment the user count if the Id already existed */
76  IdType getcreate(ValueType const & value);
77 
78  //! Get the user count for a given Id, or zero if it does not exist
79  size_t users(IdType const & id) const;
80 
81  //! Get the user count for a given value, or zero if it does not exist
82  size_t users(ValueType const & value) const;
83 
84  //! Decrement the user count and, if zero, delete the Id and associated value
85  /*! \return the new number of users after the decrement.
86  \throw IdNotFoundException Thrown if value does not exist in the table. */
87  size_t remove(IdType const & id);
88 
89  //! Decrement the user count and, if zero, delete the value and associated Id
90  /*! \return the new number of users after the decrement.
91  \throw ValueNotFoundException Thrown if value does not exist in the table. */
92  size_t remove(ValueType const & value);
93 
94  //! Clear the entire IdTable
95  void clear();
96 
97  //! An exception type which is thrown when users try to get() an unknown Id
98  class IdNotFoundException;
99 
100  //! An exception type which is thrown when users try to get() an unknown value
101  class ValueNotFoundException;
102 
103  private:
104  typedef std::pair<ValueType, size_t /* count */> ValueData;
105  std::unordered_map<IdType, ValueData> itsIdValueMap;
106  std::unordered_map<ValueType, IdType> itsValueIdMap;
107 
108  std::queue<IdType> itsRecycleBin;
109  IdType itsMaxId;
110 
111  IdType create_internal(ValueType const & value);
112  };
113 } // nrt
114 
116 
117 #endif // INCLUDE_NRT_CORE_DESIGN_IDTABLE_H