casacore
OrderedMap.h
Go to the documentation of this file.
1 //# OrderedMap.h: Templated associatve array (map) classes with ordered keys
2 //# Copyright (C) 1993,1994,1995,1996,1999,2000,2001
3 //# Associated Universities, Inc. Washington DC, USA.
4 //#
5 //# This library is free software; you can redistribute it and/or modify it
6 //# under the terms of the GNU Library General Public License as published by
7 //# the Free Software Foundation; either version 2 of the License, or (at your
8 //# option) any later version.
9 //#
10 //# This library is distributed in the hope that it will be useful, but WITHOUT
11 //# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 //# FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
13 //# License for more details.
14 //#
15 //# You should have received a copy of the GNU Library General Public License
16 //# along with this library; if not, write to the Free Software Foundation,
17 //# Inc., 675 Massachusetts Ave, Cambridge, MA 02139, USA.
18 //#
19 //# Correspondence concerning AIPS++ should be addressed as follows:
20 //# Internet email: aips2-request@nrao.edu.
21 //# Postal address: AIPS++ Project Office
22 //# National Radio Astronomy Observatory
23 //# 520 Edgemont Road
24 //# Charlottesville, VA 22903-2475 USA
25 //#
26 //# $Id$
27 
28 #ifndef CASA_ORDEREDMAP_H
29 #define CASA_ORDEREDMAP_H
30 
31 #ifndef AIPS_USE_DEPRECATED
32 #error "OrderedMap.h is deprecated; use -DBUILD_DEPRECATED=ON to use it"
33 #endif
34 
35 #include <casacore/casa/aips.h>
36 #include <casacore/casa/Exceptions/Error.h>
37 #include <casacore/casa/Containers/Block.h>
38 #include <casacore/casa/BasicSL/String.h>
39 #include <casacore/casa/Containers/Map.h>
40 #include <casacore/casa/Containers/OrderedPair.h>
41 #include <casacore/casa/Utilities/Register.h>
42 #include <casacore/casa/Utilities/Notice.h>
43 
44 namespace casacore { //#Begin casa namespace
45 
46 template<class t, class v> class OrderedMap;
47 template<class t, class v> class OrderedMapRep;
48 template<class t, class v> class OrderedMapIterRep;
49 
50 // <category lib=aips sect="Notice">
51 // <summary>Message used for OrderedMap notification</summary>
52 // <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="" demos="">
53 // </reviewed>
54 //
55 // This is the message that flows between the OrderedMap
56 // and the OrderedMap iterators. It allows OrderedMap
57 // iterators to react to changes as they occur to the
58 // OrderedMap.
59 //
60 template<class t,class v> class OrderedMapNotice : public Notice {
61 friend class OrderedMapRep<t,v>;
62 friend class OrderedMapIterRep<t,v>;
63 private:
66 
67  //*display 1
68  //
69  // This is used to construct a list notice. The parameters are:
70  // <list>
71  // <item> the change modification position
72  // <item> the change type
73  // </list>
74  //
75  OrderedMapNotice(uInt pos, NoticeType typ) : changeType(typ), modPos(pos) {}
76 
77 public:
78  //
79  // This function returns the "Notice" type, retrieved
80  // from the "type registry".
81  //
82  uInt type() const {return Register(this);}
83 
84  //
85  // This operator can be used to compare two
86  // "OrderedMapNotice"s.
87  //
88  int operator==(const Notice &op) const {
89  if (type() != op.type()) {
90  return 0;
91  } else {
92  const OrderedMapNotice<t,v> &opD = (const OrderedMapNotice<t,v> &) op;
93  return (modPos == opD.modPos && changeType == opD.changeType);
94  }
95  }
96 };
97 
98 // <summary> Representation class for an Ordered Map</summary>
99 // <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="" demos="">
100 // </reviewed>
101 
102 template<class key, class value> class OrderedMapRep : public NoticeSource, public MapRep<key,value> {
103 friend class OrderedMap<key,value>;
104 public:
105  //
106  // Creates a map with the specified default value, "value", and the
107  // internal block size.
108  //
109  OrderedMapRep (const value&, uInt size);
110 
111  //
112  // Creates a map with the specified default value, "value".
113  //
115 
116  //
117  // These functions check to see if a mapping is defined between
118  // the specified key and some value. If one is, a pointer to
119  // the value is returned, otherwise 0 is returned.
120  //
121  //+grp
122  value *isDefined(const key&);
123  const value *isDefined(const key&) const;
124  //-grp
125 
126  //
127  // Returns the number of user defined mappings
128  //
129  uInt ndefined() const;
130 
131  //
132  // Defines a mapping (ie. create a key value mapping)
133  //
134  value &define (const key&, const value&);
135 
136  //
137  // Undefines a mapping (ie. remove a key value mapping).
138  //
139  void remove (const key&);
140 
141  //
142  // Clear the entire map (ie. remove all mappings).
143  //
144  void clear ();
145 
147 
149 
150  //
151  // Get the number of mappings.
152  //
153  uInt nused() const { return nrused; }
154  uInt ntot() const { return nrtot; }
155 
156  //
157  // Get or set the Block allocation increment.
158  //
159  //+grp
160  uInt incr() const { return nrincr; }
161  uInt incr(uInt nri) { return (nrincr = nri); }
162  //-grp
163 
164  //
165  // Removes a map.
166  //
168 
170 
171 protected:
172  // The blocks to hold the keys and values
173  // and the total, used and increment size of these blocks.
178 
179  // The index of the last key used.
181 
182  // Binary search for the key.
183  Int findKey (const key&, Bool&) const;
184 };
185 
186 //
187 // <category lib=aips sect="Containers">
188 // <summary>Map with keys ordered</summary>
189 // <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="" demos="">
190 // </reviewed>
191 //
192 // OrderedMap<key,value> is a template class derived from Map.
193 // It is similar to ListMap, but the keys are kept in order and
194 // they have to be unique.
195 //
196 // It uses a Block to store an array of pointers to the keys and
197 // the associated values.
198 // The keys and values themselves are stored on the heap.
199 // The keys are kept in order to allow a binary search through
200 // the keys for rapid access.
201 //
202 // This is one (simple) implementation of an ordered map.
203 // It is not suitable for large arrays of keys, since the overhead
204 // of keeping the keys in order would get too big.
205 // For large arrays a red-black tree implementation would be better.
206 //
207 // Exceptions are raised when new[] is failing, when the next()
208 // getKey() or getValue() function is failing or when a duplicate key
209 // is defined.
210 //
211 // The AipsIO >> and << operators are defined in <aips/OrdMapIO.h>.
212 //
213 template<class key, class value> class OrderedMap : public Map<key,value> {
214 friend class OrderedMapIterRep<key,value>;
215 protected:
216 
217  void throwgetKey(uInt) const;
218  void throwgetValue(uInt) const;
219 
220  value &getVal(uInt inx) {
221  if (!this->Rep || inx >= nused())
222  throwgetValue(inx);
223  return (((OrderedMapRep<key,value> *)(this->Rep))->kvblk[inx]->y());
224  }
225 
226  const value &getVal(uInt inx) const {
227  if (!this->Rep || inx >= nused())
228  throwgetValue(inx);
229  return (((OrderedMapRep<key,value> *)(this->Rep))->kvblk[inx]->y());
230  }
231 
232  key &getKey (uInt inx) {
233  if (!this->Rep || inx >= nused())
234  throwgetKey(inx);
235  return (((OrderedMapRep<key,value> *)(this->Rep))->kvblk[inx]->x());
236  }
237 
238  const key &getKey (uInt inx) const {
239  if (!this->Rep || inx >= nused())
240  throwgetKey(inx);
241  return (((OrderedMapRep<key,value> *)(this->Rep))->kvblk[inx]->x());
242  }
243 
244 public:
245  //
246  // Creates a map with the specified default value, "value", and the
247  // internal block size.
248  //
249  OrderedMap (const value& dflt, uInt size) : Map<key,value>(new OrderedMapRep<key,value>(dflt,size)) { }
250 
251  //
252  // Creates a map with the specified default value, "value".
253  //
254  explicit OrderedMap (const value& dflt) : Map<key,value>(new OrderedMapRep<key,value>(dflt)) { }
255 
256  //
257  // Creates a map from another one; use copy semantics.
258  //
259  OrderedMap (const OrderedMap<key,value>& other) : Map<key,value>(other.Rep->Clone()) { }
260 
261  //
262  // Does nothing, the destruction is taken care of in the base class, i.e. the
263  // letter contains the guts.
264  //
266 
267  //
268  // Assigns this OrderedMap to another with copy semantics.
269  //
271  this->SetRep(other.Rep->Clone());
272  return *this;
273  }
274 
275  //
276  // Get the number of mappings.
277  //
278  uInt nused() const { return ((OrderedMapRep<key,value> *)(this->Rep))->nused(); }
279  uInt ntot() const { return ((OrderedMapRep<key,value> *)(this->Rep))->ntot(); }
280 
281  //
282  // Get or set the Block allocation increment.
283  //
284  //+grp
285  uInt incr() const { return ((OrderedMapRep<key,value> *)(this->Rep))->incr(); }
286  uInt incr(uInt nri) { return ((OrderedMapRep<key,value> *)(this->Rep))->incr(nri);}
287  //-grp
288 
289  enum {OrderedMapVersion = 1};
290 };
291 
292 
293 //
294 // <category lib=aips sect="Containers">
295 // <summary>OrderedMap iterator "letter"</summary>
296 // <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="" demos="">
297 // </reviewed>
298 //
299 // This is the "letter" which when paired (Const)MapIter "envelope"
300 // allows traversal of "OrderedMap"s.
301 //
302 template<class key, class value> class OrderedMapIterRep : virtual public MapIterRep<key,value>, public NoticeTarget {
303 protected:
304 
305  //*display 4
306  //
307  // Throw exceptions on behalf of inline functions.
308  //
309  //+grp
310  void thrownext() const;
311  void throwInvalidIter() const;
312  //-grp
313 
315 
317 
318 public:
319 
320  //
321  // Checks to see if the iterator is in a valid state.
322  //
323  Bool isValid() const;
324 
325  //
326  // Checks to see if the iterator is at one of the
327  // map extremes, "atEnd()" or "atStart()".
328  //
329  //+grp
330  Bool atEnd() const;
331  Bool atStart() const;
332  //-grp
333 
334  //
335  // Move the iterator to the beginning of the Map.
336  //
337  void toStart();
338 
339  //
340  // Advance the iterator to the next key.
341  //
342  //+grp
343  void operator++();
344  void operator++(int);
345  //-grp
346 
347  //
348  // Retrieve the key at the current iterator position.
349  //
350  //+grp
351  const key &getKey () const;
352  const key &getKey (uInt inx) const {
353  if (!container || !isValid())
355  return ((*container).getKey(inx));
356  }
357  //-grp
358 
359  //
360  // Retrieve the value at the given index in the internal block
361  // which stores the representation of the OrderedMap.
362  //
363  // <note> This should typically not be used.</note>
364  //
365  //+grp
366  value &getVal(uInt inx) {
367  if (!container || !isValid())
369  return ((*container).getVal(inx));
370  }
371  //-grp
372 
373  //
374  // Retrieve the value at the current iterator position.
375  //
376  //+grp
377  const value &getVal() const;
378  const value &getVal(uInt inx) const {
379  if (!container || !isValid())
381  return ((*container).getVal(inx));
382  }
383 
384  value &getVal() {return getVal(CurIndex);}
385  //-grp
386 
387 
390  return ret;
391  }
392 
393  //*display 4
394  //
395  // This function is the hook through which OrderedMap
396  // iterators are notified of changes to the OrderedMap
397  // which they observe, i.e. changes which may cause
398  // require iterator update.
399  //
400  void notify(const Notice &);
401 
402  //
403  // These constructors allow a ListMapIter to be constructed from a
404  // ListMap.
405  //
406  //+grp
408  : MapIterRep<key,value>(st),
409  NoticeTarget((NoticeSource *)((OrderedMapRep<key,value> *) st->Rep)),
410  container(st),
411  CurIndex(0)
412  {}
413 
415  : MapIterRep<key,value>(st),
416  NoticeTarget((NoticeSource *)((OrderedMapRep<key,value> *) st.Rep)),
417  container(&st),
418  CurIndex(0)
419  {}
420  //-grp
421 
423 
424 };
425 
426 } //#End casa namespace
427 #ifndef CASACORE_NO_AUTO_TEMPLATES
428 #include <casacore/casa/Containers/OrderedMap.tcc>
429 #endif //# CASACORE_NO_AUTO_TEMPLATES
430 #endif
Abstract base class for associative array iterators.
Definition: Map.h:277
Abstract base class for associative arrays.
Definition: Map.h:156
MapRep< key, value > * Rep
Definition: Map.h:246
void SetRep(MapRep< key, value > *st)
Used the set the representation.
Definition: Map.h:257
base class for notice originators
Definition: Notice.h:99
abstract base class for notice receptors
Definition: Notice.h:150
OrderedMap iterator "letter".
Definition: OrderedMap.h:302
const key & getKey(uInt inx) const
Definition: OrderedMap.h:352
OrderedMapIterRep(OrderedMap< key, value > &st)
Definition: OrderedMap.h:414
value & getVal()
Return the value at the current location of the map iterator.
Definition: OrderedMap.h:384
const value & getVal(uInt inx) const
Definition: OrderedMap.h:378
Bool atEnd() const
Checks to see if the iterator is at one of the map extremes, "atEnd()" or "atStart()".
void notify(const Notice &)
Hook through which NoticeTargets are notified (by NoticeSources).
OrderedMap< key, value > * container
Definition: OrderedMap.h:314
OrderedMapIterRep(OrderedMap< key, value > *st)
These constructors allow a ListMapIter to be constructed from a ListMap.
Definition: OrderedMap.h:407
value & getVal(uInt inx)
Retrieve the value at the given index in the internal block which stores the representation of the Or...
Definition: OrderedMap.h:366
void toStart()
Move the iterator to the beginning of the Map.
const value & getVal() const
Retrieve the value at the current iterator position.
const key & getKey() const
Retrieve the key at the current iterator position.
Bool isValid() const
Checks to see if the iterator is in a valid state.
MapIterRep< key, value > * Clone()
Duplicate a map iterator.
Definition: OrderedMap.h:388
void operator++()
Advance the iterator to the next key.
enum casacore::OrderedMapNotice::NoticeType changeType
uInt type() const
This function returns the "Notice" type, retrieved from the "type registry".
Definition: OrderedMap.h:82
int operator==(const Notice &op) const
This operator can be used to compare two "OrderedMapNotice"s.
Definition: OrderedMap.h:88
OrderedMapNotice(uInt pos, NoticeType typ)
Definition: OrderedMap.h:75
Representation class for an Ordered Map.
Definition: OrderedMap.h:102
value & define(const key &, const value &)
Defines a mapping (ie.
uInt nused() const
Get the number of mappings.
Definition: OrderedMap.h:153
uInt incr() const
Get or set the Block allocation increment.
Definition: OrderedMap.h:160
uInt lastRef
The index of the last key used.
Definition: OrderedMap.h:180
MapIterRep< key, value > * getRep(Map< key, value > *) const
const value * isDefined(const key &) const
Returns a non-zero value if a mapping is defined for the key parameter.
value * isDefined(const key &)
These functions check to see if a mapping is defined between the specified key and some value.
void clear()
Clear the entire map (ie.
uInt ndefined() const
Returns the number of user defined mappings.
Int findKey(const key &, Bool &) const
Binary search for the key.
OrderedMapRep(const value &, uInt size)
Creates a map with the specified default value, "value", and the internal block size.
OrderedMapRep(const value &)
Creates a map with the specified default value, "value".
MapRep< key, value > * Clone() const
~OrderedMapRep()
Removes a map.
void remove(const key &)
Undefines a mapping (ie.
PtrBlock< OrderedPair< key, value > * > kvblk
The blocks to hold the keys and values and the total, used and increment size of these blocks.
Definition: OrderedMap.h:174
uInt incr(uInt nri)
Definition: OrderedMap.h:161
Map with keys ordered.
Definition: OrderedMap.h:213
~OrderedMap()
Does nothing, the destruction is taken care of in the base class, i.e.
const value & getVal(uInt inx) const
Definition: OrderedMap.h:226
OrderedMap(const value &dflt, uInt size)
Creates a map with the specified default value, "value", and the internal block size.
Definition: OrderedMap.h:249
uInt incr() const
Get or set the Block allocation increment.
Definition: OrderedMap.h:285
uInt incr(uInt nri)
Definition: OrderedMap.h:286
key & getKey(uInt inx)
Definition: OrderedMap.h:232
value & getVal(uInt inx)
Definition: OrderedMap.h:220
OrderedMap< key, value > & operator=(const OrderedMap< key, value > &other)
Assigns this OrderedMap to another with copy semantics.
Definition: OrderedMap.h:270
uInt ntot() const
Definition: OrderedMap.h:279
OrderedMap(const OrderedMap< key, value > &other)
Creates a map from another one; use copy semantics.
Definition: OrderedMap.h:259
const key & getKey(uInt inx) const
Definition: OrderedMap.h:238
uInt nused() const
Get the number of mappings.
Definition: OrderedMap.h:278
void throwgetKey(uInt) const
OrderedMap(const value &dflt)
Creates a map with the specified default value, "value".
Definition: OrderedMap.h:254
void throwgetValue(uInt) const
A drop-in replacement for Block<T*>.
Definition: Block.h:814
this file contains all the compiler specific defines
Definition: mainpage.dox:28
unsigned int uInt
Definition: aipstype.h:51
int Int
Definition: aipstype.h:50
bool Bool
Define the standard types used by Casacore.
Definition: aipstype.h:42
LatticeExprNode value(const LatticeExprNode &expr)
This function returns the value of the expression without a mask.