24 #ifndef SKELETON_BLOCKER_INTERNAL_TRIE_H_ 25 #define SKELETON_BLOCKER_INTERNAL_TRIE_H_ 34 namespace skeleton_blocker {
36 template<
typename SimplexHandle>
38 typedef SimplexHandle Simplex;
39 typedef typename SimplexHandle::Vertex_handle Vertex_handle;
42 std::vector<std::shared_ptr<Trie> > childs;
48 Trie() : parent_(0) { }
50 Trie(Vertex_handle v_) : v(v_), parent_(0) { }
52 Trie(Vertex_handle v_, Trie* parent) : v(v_), parent_(parent) { }
54 bool operator==(
const Trie& other)
const {
55 return (v == other.v);
58 void add_child(Trie* child) {
60 std::shared_ptr<Trie> ptr_to_add(child);
61 childs.push_back(ptr_to_add);
62 child->parent_ =
this;
66 typedef typename Simplex::Simplex_vertex_const_iterator Simplex_vertex_const_iterator;
68 Trie* make_trie(Simplex_vertex_const_iterator s_it, Simplex_vertex_const_iterator s_end) {
72 Trie* res =
new Trie(*s_it);
73 Trie* child = make_trie(++s_it, s_end);
74 res->add_child(child);
82 void add_simplex_helper(Simplex_vertex_const_iterator s_it, Simplex_vertex_const_iterator s_end) {
85 if (s_it == s_end)
return;
87 for (
auto child : childs) {
88 if (child->v == *s_it)
89 return child->add_simplex_helper(s_it, s_end);
94 Trie * son_with_what_remains_of_s(make_trie(s_it, s_end));
95 add_child(son_with_what_remains_of_s);
99 void maximal_faces_helper(std::vector<Simplex>& res)
const {
100 if (is_leaf()) res.push_back(simplex());
102 for (
auto child : childs)
103 child->maximal_faces_helper(res);
110 void add_simplex(
const Simplex& s) {
111 if (s.empty())
return;
112 assert(v == s.first_vertex());
113 add_simplex_helper(s.begin(), s.end());
116 std::vector<Simplex> maximal_faces()
const {
117 std::vector<Simplex> res;
118 maximal_faces_helper(res);
125 void add_vertices_up_to_the_root(Simplex& res)
const {
128 parent_->add_vertices_up_to_the_root(res);
131 Simplex simplex()
const {
133 add_vertices_up_to_the_root(res);
137 bool is_leaf()
const {
138 return childs.empty();
141 bool is_root()
const {
145 const Trie* parent() {
152 parent_->childs.erase(
this);
158 bool contains(
const Simplex& s)
const {
159 Trie
const* current =
this;
160 if (s.empty())
return true;
161 if (current->v != s.first_vertex())
return false;
162 auto s_pos = s.begin();
164 while (s_pos != s.end() && current != 0) {
166 for (
const auto child : current->childs) {
167 if (child->v == *s_pos) {
169 current = child.get();
174 if (!found)
return false;
179 Trie* go_bottom_left() {
183 return (*childs.begin())->go_bottom_left();
186 friend std::ostream& operator<<(std::ostream& stream,
const Trie& trie) {
187 stream <<
"T( " << trie.v <<
" ";
188 for (
auto t : trie.childs)
195 template<
typename SimplexHandle>
197 typedef typename SimplexHandle::Vertex_handle Vertex_handle;
198 typedef SimplexHandle Simplex;
200 typedef Trie<Simplex> STrie;
202 template<
typename SimpleHandleOutputIterator>
203 Tries(
unsigned num_vertices, SimpleHandleOutputIterator simplex_begin, SimpleHandleOutputIterator simplex_end) :
204 cofaces_(num_vertices, 0) {
205 for (
auto i = 0u; i < num_vertices; ++i)
206 cofaces_[i] =
new STrie(Vertex_handle(i));
207 for (
auto s_it = simplex_begin; s_it != simplex_end; ++s_it) {
208 if (s_it->dimension() >= 1)
209 cofaces_[s_it->first_vertex()]->add_simplex(*s_it);
214 for (STrie* t : cofaces_)
220 Simplex positive_neighbors(Vertex_handle v)
const {
222 for (
auto child : cofaces_[v]->childs)
223 res.add_vertex(child->v);
227 bool contains(
const Simplex& s)
const {
228 auto first_v = s.first_vertex();
229 return cofaces_[first_v]->contains(s);
232 friend std::ostream& operator<<(std::ostream& stream,
const Tries& tries) {
233 for (
auto trie : tries.cofaces_)
234 stream << *trie << std::endl;
240 std::vector<Simplex> next_dimension_simplices()
const {
241 std::vector<Simplex> res;
242 while (!(to_see_.empty()) && (to_see_.front()->simplex().dimension() == current_dimension_)) {
243 res.emplace_back(to_see_.front()->simplex());
244 for (
auto child : to_see_.front()->childs)
245 to_see_.push_back(child.get());
248 ++current_dimension_;
252 void init_next_dimension()
const {
253 for (
auto trie : cofaces_)
254 to_see_.push_back(trie);
258 mutable std::deque<STrie*> to_see_;
259 mutable int current_dimension_ = 0;
260 std::vector<STrie*> cofaces_;
265 namespace skbl = skeleton_blocker;
269 #endif // SKELETON_BLOCKER_INTERNAL_TRIE_H_ Definition: SimplicialComplexForAlpha.h:26