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