00001
00002
00003
00004
00005
00006
00007 #ifndef COH_TREE_MAP_HPP
00008 #define COH_TREE_MAP_HPP
00009
00010 #include "coherence/lang.ns"
00011
00012 #include "coherence/util/AbstractMap.hpp"
00013 #include "coherence/util/Comparator.hpp"
00014 #include "coherence/util/Map.hpp"
00015 #include "coherence/util/NavigableMap.hpp"
00016 #include "coherence/util/SortedMap.hpp"
00017
00018 COH_OPEN_NAMESPACE2(coherence,util)
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031 class COH_EXPORT TreeMap
00032 : public cloneable_spec<TreeMap,
00033 extends<AbstractMap>,
00034 implements<NavigableMap> >
00035 {
00036 friend class factory<TreeMap>;
00037
00038
00039
00040 protected:
00041
00042
00043
00044 TreeMap();
00045
00046
00047
00048
00049 TreeMap(Comparator::View vComparator);
00050
00051
00052
00053
00054 TreeMap(const TreeMap& that);
00055
00056
00057
00058
00059 virtual ~TreeMap();
00060
00061
00062
00063
00064 public:
00065
00066
00067
00068
00069 virtual size32_t size() const;
00070
00071
00072
00073
00074 virtual bool isEmpty() const;
00075
00076
00077
00078
00079 virtual bool containsKey(Object::View vKey) const;
00080
00081
00082
00083
00084 virtual Object::Holder get(Object::View vKey) const;
00085
00086
00087
00088
00089 using Map::get;
00090
00091
00092
00093
00094 virtual Object::Holder put(Object::View vKey, Object::Holder ohValue);
00095
00096
00097
00098
00099 virtual Object::Holder remove(Object::View vKey);
00100 using Map::remove;
00101
00102
00103
00104
00105 virtual void clear();
00106
00107
00108
00109
00110 virtual Set::View entrySet() const;
00111
00112
00113
00114
00115 virtual Set::Handle entrySet();
00116
00117
00118
00119
00120 public:
00121
00122
00123
00124 virtual Comparator::View comparator() const;
00125
00126
00127
00128
00129 virtual Object::View firstKey() const;
00130
00131
00132
00133
00134 virtual Object::View lastKey() const;
00135
00136
00137
00138
00139 virtual SortedMap::Handle headMap(Object::View vToKey);
00140
00141
00142
00143
00144 virtual SortedMap::View headMap(Object::View vToKey) const;
00145
00146
00147
00148
00149 virtual SortedMap::Handle subMap(Object::View vFromKey,
00150 Object::View vToKey);
00151
00152
00153
00154
00155 virtual SortedMap::View subMap(Object::View vFromKey,
00156 Object::View vToKey) const;
00157
00158
00159
00160
00161 virtual SortedMap::Handle tailMap(Object::View vFromKey);
00162
00163
00164
00165
00166 virtual SortedMap::View tailMap(Object::View vFromKey) const;
00167
00168
00169
00170
00171 public:
00172
00173
00174
00175 virtual Object::View ceilingKey(Object::View vKey) const;
00176
00177
00178
00179
00180 virtual Object::View floorKey(Object::View vKey) const;
00181
00182
00183
00184
00185 virtual Object::View higherKey(Object::View vKey) const;
00186
00187
00188
00189
00190 virtual Object::View lowerKey(Object::View vKey) const;
00191
00192
00193
00194
00195 virtual Map::Entry::Holder pollFirstEntry();
00196
00197
00198
00199
00200 virtual Map::Entry::Holder pollLastEntry();
00201
00202
00203
00204
00205 virtual NavigableMap::Handle headMap(Object::View vToKey, bool toInclusive);
00206
00207
00208
00209
00210 virtual NavigableMap::View headMap(Object::View vToKey, bool toInclusive) const;
00211
00212
00213
00214
00215 virtual NavigableMap::Handle subMap(Object::View vFromKey, bool fromInclusive,
00216 Object::View vToKey, bool toInclusive);
00217
00218
00219
00220
00221 virtual NavigableMap::View subMap(Object::View vFromKey, bool fromInclusive,
00222 Object::View vToKey, bool toInclusive) const;
00223
00224
00225
00226
00227 virtual NavigableMap::Handle tailMap(Object::View vFromKey, bool fromInclusive);
00228
00229
00230
00231
00232 virtual NavigableMap::View tailMap(Object::View vFromKey, bool fromInclusive) const;
00233
00234
00235
00236
00237 public:
00238
00239
00240
00241
00242 class COH_EXPORT Node
00243 : public cloneable_spec<Node,
00244 extends<Object>,
00245 implements<Map::Entry> >
00246 {
00247 friend class factory<Node>;
00248
00249
00250
00251 protected:
00252
00253
00254
00255 Node(Object::View ovKey);
00256
00257
00258
00259
00260 Node(const Node& that);
00261
00262
00263
00264 protected:
00265
00266
00267
00268
00269
00270
00271 virtual void adopt(Node::Handle hChild, bool fLeft);
00272
00273
00274
00275
00276
00277
00278 virtual Object::Holder getValue() const;
00279
00280
00281
00282
00283
00284
00285
00286
00287 virtual Object::Holder setValue(Object::Holder ohValue);
00288
00289
00290
00291
00292
00293
00294
00295 virtual bool isLeaf() const;
00296
00297
00298
00299
00300 virtual void dissolve();
00301
00302
00303
00304 public:
00305
00306
00307
00308
00309
00310 virtual Object::View getKey() const;
00311
00312
00313
00314
00315
00316
00317 virtual Object::Holder getValue();
00318
00319
00320
00321 public:
00322
00323
00324
00325 virtual TypedHandle<const String> toString() const;
00326
00327
00328
00329
00330 virtual void onInit();
00331
00332
00333
00334 public:
00335
00336
00337
00338
00339 FinalView<Object> f_vKey;
00340
00341
00342
00343
00344 MemberHolder<Object> m_ohValue;
00345
00346
00347
00348
00349 int32_t nBalance;
00350
00351
00352
00353
00354 MemberHandle<Node> m_hParent;
00355
00356
00357
00358
00359 MemberHandle<Node> m_hLeft;
00360
00361
00362
00363
00364 MemberHandle<Node> m_hRight;
00365
00366
00367
00368 friend class TreeMap;
00369 };
00370
00371
00372
00373
00374 public:
00375
00376
00377
00378
00379
00380
00381
00382 virtual void removeNode(Node::Handle hNode);
00383
00384
00385
00386
00387
00388
00389
00390
00391 virtual bool isHead(Node::View vNode) const;
00392
00393
00394
00395
00396
00397
00398 virtual Iterator::Handle iterator() const;
00399
00400
00401
00402
00403
00404
00405 virtual Muterator::Handle iterator();
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415
00416
00417
00418 virtual int32_t compare(Object::View v1, Object::View v2) const;
00419
00420
00421
00422
00423
00424
00425
00426
00427
00428 virtual Node::Handle find(Object::View vKey) const;
00429
00430
00431
00432
00433
00434
00435 virtual Node::Handle getHeadNode() const;
00436
00437 protected:
00438
00439
00440
00441
00442
00443
00444
00445
00446
00447 virtual Node::Handle replace(Node::Handle hNodeA,
00448 Node::Handle hNodeB);
00449 using Map::replace;
00450
00451
00452
00453
00454
00455
00456
00457
00458
00459 virtual Node::Handle rotate(Node::Handle hNode, bool fLeft);
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469 virtual Node::Handle doubleRotate(Node::Handle hNode,
00470 bool fLeft);
00471
00472
00473
00474
00475
00476
00477
00478
00479
00480 virtual void adjustDoubleBalance(Node::Handle hNode,
00481 Node::Handle hChild, int32_t nBal);
00482
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494
00495 virtual Node::Handle findInsertionPoint(Object::View ovKey) const;
00496
00497
00498
00499
00500
00501
00502
00503 virtual void balancedInsertion(Node::Handle hParent,
00504 Node::Handle hChild);
00505
00506
00507
00508
00509
00510
00511
00512 virtual void balancePostRemove(Node::Handle hPruned,
00513 bool fPrunedLeft);
00514
00515
00516
00517
00518
00519
00520
00521
00522
00523 virtual Node::Handle instantiateNode(Object::View vKey,
00524 Object::Holder ohValue);
00525
00526
00527
00528
00529 protected:
00530
00531
00532
00533
00534
00535
00536 size32_t m_nSize;
00537
00538
00539
00540
00541
00542 mutable MemberHandle<Node> m_hHead;
00543
00544
00545
00546
00547
00548 FinalView<Comparator> f_vComparator;
00549 };
00550
00551 COH_CLOSE_NAMESPACE2
00552
00553 #endif // COH_TREE_MAP_HPP