Elm  2
ELM is a library providing generic data structures, OS-independent interface, plugins and XML.
SegmentBuilder.h
1 /*
2  * stree::MarkerBuilder class interface
3  *
4  * This file is part of OTAWA
5  * Copyright (c) 2013, IRIT UPS.
6  *
7  * OTAWA is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * OTAWA is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with OTAWA; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20  */
21 #ifndef ELM_STREE_SEGMENTBUILDER_H_
22 #define ELM_STREE_SEGMENTBUILDER_H_
23 
24 #include <elm/stree/Builder.h>
25 #include <elm/avl/Map.h>
26 
27 namespace elm { namespace stree {
28 
29 template <class K, class T, class C = Comparator<K> >
30 class SegmentBuilder: public Builder<K, T, C> {
31  typedef typename Builder<K, T, C>::node_t node_t;
32  typedef Pair<K, K> segment_t;
33  typedef struct {
34  static int compare(const segment_t& v1, const segment_t& v2) { return C::compare(v1.fst, v2.fst); }
35  } segment_comparator_t;
36  typedef avl::Map<Pair<K, K>, T, segment_comparator_t> map_t;
37  typedef typename map_t::PairIter iter_t;
38 
39 public:
40 
41  SegmentBuilder(const T& def): _def(def) { }
42 
43  void add(const K& low, const K& high, const T& val) {
44  segs.put(pair(low, high), val);
45  }
46 
47  void make(stree::Tree<K, T, C>& tree) {
48 
49  // count the nodes
50  int cnt = 0;
51  {
52  iter_t iter(segs);
53  if(!iter)
54  return;
55  cnt++;
56  K p = iter.item().fst.snd;
57  iter++;
58  while(iter()) {
59  if(C::compare(iter.item().fst.fst, p) != 0)
60  cnt++;
61  p = iter.item().fst.snd;
62  cnt++;
63  iter++;
64  }
65  }
66 
67  // allocate the memory
68  node_t *nodes = Builder<K, T, C>::allocate(cnt);
69 
70  // insert the bounds
71  int i = 0;
72  iter_t iter(segs);
73  nodes[i] = node_t(iter.item().fst.fst, iter.item().fst.snd);
74  nodes[i++].data = iter.item().snd;
75  K p = iter.item().fst.snd;
76  iter++;
77  while(iter()) {
78  if(C::compare(iter.item().fst.fst, p) != 0) {
79  nodes[i] = node_t(p, iter.item().fst.fst);
80  nodes[i++].data = _def;
81  }
82  nodes[i] = node_t(iter.item().fst.fst, iter.item().fst.snd);
83  nodes[i++].data = iter.item().snd;
84  p = iter.item().fst.snd;
85  iter++;
86  }
87 
88  // build the tree
89  int root = Builder<K, T, C>::make(nodes, i, 0, i - 1);
90 
91  // perform the transfer
92  tree.set(root, nodes);
93  }
94 
95 private:
96  map_t segs;
97  T _def;
98 };
99 
100 } } // elm::stree
101 
102 
103 #endif /* ELM_STREE_SEGMENTBUILDER_H_ */
elm::avl::Map
Definition: Map.h:33
elm::iter
Definition: util_WAHVector.cpp:157
elm::io::p
Printable< T, M > p(const T &data, const M &man)
Definition: Output.h:302
elm::stree::SegmentBuilder::make
void make(stree::Tree< K, T, C > &tree)
Definition: SegmentBuilder.h:47
elm::iter
void iter(const C &c, const F &f)
Definition: util.h:95
elm::pair
Pair< T1, T2 > pair(const T1 &v1, const T2 &v2)
Definition: Pair.h:63
elm::stree::Builder
Definition: Builder.h:29
elm::stree::Tree::set
void set(int _root, node_t *_nodes)
Definition: Tree.h:53
elm::Pair
Definition: Pair.h:33
elm::stree::Builder::allocate
node_t * allocate(t::uint32 n)
Definition: Builder.h:33
elm::avl::Map::put
void put(const K &key, const T &value)
Definition: Map.h:105
elm
Definition: adapter.h:26
elm::stree::Tree
Definition: Tree.h:31
elm::stree::SegmentBuilder
Definition: SegmentBuilder.h:30
elm::stree::Tree::node_t
Definition: Tree.h:35
elm::stree::SegmentBuilder::add
void add(const K &low, const K &high, const T &val)
Definition: SegmentBuilder.h:43
elm::stree::Builder::make
int make(node_t *nodes, int &s, int start, int end)
Definition: Builder.h:38
elm::stree::SegmentBuilder::SegmentBuilder
SegmentBuilder(const T &def)
Definition: SegmentBuilder.h:41
elm::stree::Tree::node_t::data
T data
Definition: Tree.h:48
elm::Pair::fst
T1 fst
Definition: Pair.h:35