Lines Matching refs:KeyT
12 // KeyT objects are mapped to ValT objects. Intervals of keys that map to the
38 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
41 // typedef KeyT key_type;
51 // KeyT start() const;
52 // KeyT stop() const;
53 // ValT lookup(KeyT x, Value NotFound = Value()) const;
59 // const_iterator find(KeyT x) const;
60 // iterator find(KeyT x);
62 // void insert(KeyT a, KeyT b, ValT y);
66 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
74 // const KeyT &start() const;
75 // const KeyT &stop() const;
86 // void find(KeyT x);
87 // void advanceTo(KeyT x);
90 // template <typename KeyT, typename ValT, unsigned N, typename Traits>
93 // void insert(KeyT a, KeyT b, Value y);
191 // Leaves store ((KeyT, KeyT), ValT) pairs, branches use (NodeRef, KeyT).
430 template <typename KeyT, typename ValT>
439 static_cast<unsigned>(2*sizeof(KeyT)+sizeof(ValT)),
444 typedef NodeBase<std::pair<KeyT, KeyT>, ValT, LeafSize> LeafBase;
453 static_cast<unsigned>(sizeof(KeyT) + sizeof(void*))
559 template <typename KeyT, typename ValT, unsigned N, typename Traits>
560 class LeafNode : public NodeBase<std::pair<KeyT, KeyT>, ValT, N> {
562 const KeyT &start(unsigned i) const { return this->first[i].first; }
563 const KeyT &stop(unsigned i) const { return this->first[i].second; }
566 KeyT &start(unsigned i) { return this->first[i].first; }
567 KeyT &stop(unsigned i) { return this->first[i].second; }
576 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
591 unsigned safeFind(unsigned i, KeyT x) const {
605 ValT safeLookup(KeyT x, ValT NotFound) const {
610 unsigned insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y);
622 template <typename KeyT, typename ValT, unsigned N, typename Traits>
623 unsigned LeafNode<KeyT, ValT, N, Traits>::
624 insertFrom(unsigned &Pos, unsigned Size, KeyT a, KeyT b, ValT y) {
697 template <typename KeyT, typename ValT, unsigned N, typename Traits>
698 class BranchNode : public NodeBase<NodeRef, KeyT, N> {
700 const KeyT &stop(unsigned i) const { return this->second[i]; }
703 KeyT &stop(unsigned i) { return this->second[i]; }
712 unsigned findFrom(unsigned i, unsigned Size, KeyT x) const {
726 unsigned safeFind(unsigned i, KeyT x) const {
738 NodeRef safeLookup(KeyT x) const {
747 void insert(unsigned i, unsigned Size, NodeRef Node, KeyT Stop) {
929 template <typename KeyT, typename ValT,
930 unsigned N = IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
931 typename Traits = IntervalMapInfo<KeyT> >
933 typedef IntervalMapImpl::NodeSizer<KeyT, ValT> Sizer;
934 typedef IntervalMapImpl::LeafNode<KeyT, ValT, Sizer::LeafSize, Traits> Leaf;
935 typedef IntervalMapImpl::BranchNode<KeyT, ValT, Sizer::BranchSize, Traits>
937 typedef IntervalMapImpl::LeafNode<KeyT, ValT, N, Traits> RootLeaf;
943 DesiredRootBranchCap = (sizeof(RootLeaf) - sizeof(KeyT)) /
944 (sizeof(KeyT) + sizeof(IntervalMapImpl::NodeRef)),
948 typedef IntervalMapImpl::BranchNode<KeyT, ValT, RootBranchCap, Traits>
953 KeyT start;
959 typedef KeyT KeyType;
1008 KeyT rootBranchStart() const { return rootBranchData().start; }
1009 KeyT &rootBranchStart() { return rootBranchData().start; }
1037 ValT treeSafeLookup(KeyT x, ValT NotFound) const;
1060 KeyT start() const {
1066 KeyT stop() const {
1073 ValT lookup(KeyT x, ValT NotFound = ValT()) const {
1083 void insert(KeyT a, KeyT b, ValT y) {
1126 const_iterator find(KeyT x) const {
1132 iterator find(KeyT x) {
1141 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1142 ValT IntervalMap<KeyT, ValT, N, Traits>::
1143 treeSafeLookup(KeyT x, ValT NotFound) const {
1155 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1156 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1196 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1197 IntervalMapImpl::IdxPair IntervalMap<KeyT, ValT, N, Traits>::
1234 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1235 void IntervalMap<KeyT, ValT, N, Traits>::
1261 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1262 void IntervalMap<KeyT, ValT, N, Traits>::
1270 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1271 void IntervalMap<KeyT, ValT, N, Traits>::
1284 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1285 class IntervalMap<KeyT, ValT, N, Traits>::const_iterator :
1312 void pathFillFind(KeyT x);
1313 void treeFind(KeyT x);
1314 void treeAdvanceTo(KeyT x);
1317 KeyT &unsafeStart() const {
1324 KeyT &unsafeStop() const {
1352 const KeyT &start() const { return unsafeStart(); }
1355 const KeyT &stop() const { return unsafeStop(); }
1420 void find(KeyT x) {
1430 void advanceTo(KeyT x) {
1444 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1445 void IntervalMap<KeyT, ValT, N, Traits>::
1446 const_iterator::pathFillFind(KeyT x) {
1458 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1459 void IntervalMap<KeyT, ValT, N, Traits>::
1460 const_iterator::treeFind(KeyT x) {
1468 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1469 void IntervalMap<KeyT, ValT, N, Traits>::
1470 const_iterator::treeAdvanceTo(KeyT x) {
1508 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1509 class IntervalMap<KeyT, ValT, N, Traits>::iterator : public const_iterator {
1515 void setNodeStop(unsigned Level, KeyT Stop);
1516 bool insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop);
1518 void treeInsert(KeyT a, KeyT b, ValT y);
1521 bool canCoalesceLeft(KeyT Start, ValT x);
1522 bool canCoalesceRight(KeyT Stop, ValT x);
1531 void setStart(KeyT a);
1536 void setStop(KeyT b);
1547 void setStartUnchecked(KeyT a) { this->unsafeStart() = a; }
1553 void setStopUnchecked(KeyT b) {
1566 void insert(KeyT a, KeyT b, ValT y);
1600 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1601 bool IntervalMap<KeyT, ValT, N, Traits>::
1602 iterator::canCoalesceLeft(KeyT Start, ValT Value) {
1628 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1629 bool IntervalMap<KeyT, ValT, N, Traits>::
1630 iterator::canCoalesceRight(KeyT Stop, ValT Value) {
1652 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1653 void IntervalMap<KeyT, ValT, N, Traits>::
1654 iterator::setNodeStop(unsigned Level, KeyT Stop) {
1669 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1670 void IntervalMap<KeyT, ValT, N, Traits>::
1671 iterator::setStart(KeyT a) {
1673 KeyT &CurStart = this->unsafeStart();
1685 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1686 void IntervalMap<KeyT, ValT, N, Traits>::
1687 iterator::setStop(KeyT b) {
1695 KeyT a = this->start();
1700 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1701 void IntervalMap<KeyT, ValT, N, Traits>::
1705 KeyT a = this->start();
1711 KeyT a = this->start();
1723 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1724 bool IntervalMap<KeyT, ValT, N, Traits>::
1725 iterator::insertNode(unsigned Level, IntervalMapImpl::NodeRef Node, KeyT Stop) {
1768 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1769 void IntervalMap<KeyT, ValT, N, Traits>::
1770 iterator::insert(KeyT a, KeyT b, ValT y) {
1794 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1795 void IntervalMap<KeyT, ValT, N, Traits>::
1796 iterator::treeInsert(KeyT a, KeyT b, ValT y) {
1858 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1859 void IntervalMap<KeyT, ValT, N, Traits>::
1871 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1872 void IntervalMap<KeyT, ValT, N, Traits>::
1904 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1905 void IntervalMap<KeyT, ValT, N, Traits>::
1952 template <typename KeyT, typename ValT, unsigned N, typename Traits>
1954 bool IntervalMap<KeyT, ValT, N, Traits>::
2008 KeyT Stop = Node[Pos]->stop(NewSize[Pos]-1);
2036 /// IntervalMaps. The maps may be different, but the KeyT and Traits types