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