Skip to content

Commit 44c868c

Browse files
aothmsaothms
committed
#1531 Breadth-first search and maintain insertion order on remove_deep()
1 parent 83d2548 commit 44c868c

5 files changed

Lines changed: 93 additions & 15 deletions

File tree

‎src/ifcopenshell-python/ifcopenshell/file.py‎

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -359,19 +359,27 @@ def by_type(self, type, include_subtypes=True):
359359
return [entity_instance(e, self) for e in self.wrapped_data.by_type(type)]
360360
return [entity_instance(e, self) for e in self.wrapped_data.by_type_excl_subtypes(type)]
361361

362-
def traverse(self, inst, max_levels=None):
362+
def traverse(self, inst, max_levels=None, breadth_first=False):
363363
"""Get a list of all referenced instances for a particular instance including itself
364364
365365
:param inst: The entity instance to get all sub instances
366366
:type inst: ifcopenshell.entity_instance.entity_instance
367367
:param max_levels: How far deep to recursively fetch sub instances. None or -1 means infinite.
368368
:type max_levels: None|int
369+
:param breadth_first: Whether to use breadth-first search, the default is depth-first.
370+
:type max_levels: bool
369371
:returns: A list of ifcopenshell.entity_instance.entity_instance objects
370372
:rtype: list
371373
"""
372374
if max_levels is None:
373375
max_levels = -1
374-
return [entity_instance(e, self) for e in self.wrapped_data.traverse(inst.wrapped_data, max_levels)]
376+
377+
if breadth_first:
378+
fn = self.wrapped_data.traverse_breadth_first
379+
else:
380+
fn = self.wrapped_data.traverse
381+
382+
return [entity_instance(e, self) for e in fn(inst.wrapped_data, max_levels)]
375383

376384
def get_inverse(self, inst):
377385
"""Return a list of entities that reference this entity

‎src/ifcopenshell-python/ifcopenshell/util/element.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -104,7 +104,7 @@ def has_element_reference(value, element):
104104
def remove_deep(ifc_file, element):
105105
# @todo maybe some sort of try-finally mechanism.
106106
ifc_file.batch()
107-
subgraph = list(ifc_file.traverse(element))
107+
subgraph = list(ifc_file.traverse(element, breadth_first=True))
108108
subgraph_set = set(subgraph)
109109
for ref in subgraph[::-1]:
110110
if ref.id() and len(set(ifc_file.get_inverse(ref)) - subgraph_set) == 0:

‎src/ifcparse/IfcFile.h‎

Lines changed: 18 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,10 @@
2424
#include <set>
2525
#include <iterator>
2626
#include <boost/unordered_map.hpp>
27+
#include <boost/multi_index_container.hpp>
28+
#include <boost/multi_index/sequenced_index.hpp>
29+
#include <boost/multi_index/ordered_index.hpp>
30+
#include <boost/multi_index/random_access_index.hpp>
2731

2832
#include "ifc_parse_api.h"
2933

@@ -132,7 +136,16 @@ class IFC_PARSE_API IfcFile {
132136

133137
void build_inverses_(IfcUtil::IfcBaseClass*);
134138

135-
std::set<int> batch_deletion_ids_;
139+
typedef boost::multi_index_container<
140+
int,
141+
boost::multi_index::indexed_by<
142+
boost::multi_index::sequenced<>,
143+
boost::multi_index::ordered_unique<
144+
boost::multi_index::identity<int>
145+
>
146+
>
147+
> batch_deletion_ids_t;
148+
batch_deletion_ids_t batch_deletion_ids_;
136149
bool batch_mode_ = false;
137150
void process_deletion_();
138151

@@ -220,6 +233,10 @@ class IFC_PARSE_API IfcFile {
220233
/// in the first function argument.
221234
IfcEntityList::ptr traverse(IfcUtil::IfcBaseClass* instance, int max_level=-1);
222235

236+
/// Same as traverse() but maintains topological order by using a
237+
/// breadth-first search
238+
IfcEntityList::ptr traverse_breadth_first(IfcUtil::IfcBaseClass* instance, int max_level = -1);
239+
223240
IfcEntityList::ptr getInverse(int instance_id, const IfcParse::declaration* type, int attribute_index);
224241

225242
/// Marks entity as modified so that potential cache for it is invalidated.

‎src/ifcparse/IfcParse.cpp‎

Lines changed: 62 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1506,15 +1506,52 @@ void IfcFile::recalculate_id_counter() {
15061506
MaxId = (unsigned int)k;
15071507
}
15081508

1509+
class traversal_recorder {
1510+
IfcEntityList::ptr list_;
1511+
std::map<int, IfcEntityList::ptr> instances_by_level_;
1512+
int mode_;
1513+
1514+
public:
1515+
traversal_recorder(int mode) : mode_(mode) {
1516+
if (mode == 0) {
1517+
list_.reset(new IfcEntityList);
1518+
}
1519+
};
1520+
1521+
void push_back(int level, IfcUtil::IfcBaseClass* instance) {
1522+
if (mode_ == 0) {
1523+
list_->push(instance);
1524+
} else {
1525+
auto& l = instances_by_level_[level];
1526+
if (!l) {
1527+
l.reset(new IfcEntityList);
1528+
}
1529+
l->push(instance);
1530+
}
1531+
}
1532+
1533+
IfcEntityList::ptr get_list() const {
1534+
if (mode_ == 0) {
1535+
return list_;
1536+
} else {
1537+
IfcEntityList::ptr l(new IfcEntityList);
1538+
for (auto& p : instances_by_level_) {
1539+
l->push(p.second);
1540+
}
1541+
return l;
1542+
}
1543+
}
1544+
};
1545+
15091546
class traversal_visitor {
15101547
private:
15111548
std::set<IfcUtil::IfcBaseClass*>& visited_;
1512-
IfcEntityList::ptr& list_;
1549+
traversal_recorder& list_;
15131550
int level_;
15141551
int max_level_;
15151552

15161553
public:
1517-
traversal_visitor(std::set<IfcUtil::IfcBaseClass*>& visited, IfcEntityList::ptr& list, int level, int max_level)
1554+
traversal_visitor(std::set<IfcUtil::IfcBaseClass*>& visited, traversal_recorder& list, int level, int max_level)
15181555
: visited_(visited)
15191556
, list_(list)
15201557
, level_(level)
@@ -1524,12 +1561,12 @@ class traversal_visitor {
15241561
void operator()(IfcUtil::IfcBaseClass* inst);
15251562
};
15261563

1527-
void traverse_(IfcUtil::IfcBaseClass* instance, std::set<IfcUtil::IfcBaseClass*>& visited, IfcEntityList::ptr list, int level, int max_level) {
1564+
void traverse_(IfcUtil::IfcBaseClass* instance, std::set<IfcUtil::IfcBaseClass*>& visited, traversal_recorder& list, int level, int max_level) {
15281565
if (visited.find(instance) != visited.end()) {
15291566
return;
15301567
}
15311568
visited.insert(instance);
1532-
list->push(instance);
1569+
list.push_back(level, instance);
15331570

15341571
if (level >= max_level && max_level > 0) return;
15351572

@@ -1543,16 +1580,30 @@ void traversal_visitor::operator()(IfcUtil::IfcBaseClass* inst) {
15431580

15441581
IfcEntityList::ptr IfcParse::traverse(IfcUtil::IfcBaseClass* instance, int max_level) {
15451582
std::set<IfcUtil::IfcBaseClass*> visited;
1546-
IfcEntityList::ptr return_value(new IfcEntityList);
1547-
traverse_(instance, visited, return_value, 0, max_level);
1548-
return return_value;
1583+
traversal_recorder r(0);
1584+
traverse_(instance, visited, r, 0, max_level);
1585+
return r.get_list();
1586+
}
1587+
1588+
// I'm cheating this isn't breadth-first, but rather we record visited instances
1589+
// keeping track of their rank and return a list ordered by rank. Is this equivalent?
1590+
IfcEntityList::ptr IfcParse::traverse_breadth_first(IfcUtil::IfcBaseClass* instance, int max_level) {
1591+
std::set<IfcUtil::IfcBaseClass*> visited;
1592+
traversal_recorder r(1);
1593+
traverse_(instance, visited, r, 0, max_level);
1594+
return r.get_list();
15491595
}
15501596

15511597
/// @note: for backwards compatibility
15521598
IfcEntityList::ptr IfcFile::traverse(IfcUtil::IfcBaseClass* instance, int max_level) {
15531599
return IfcParse::traverse(instance, max_level);
15541600
}
15551601

1602+
/// @note: for backwards compatibility
1603+
IfcEntityList::ptr IfcFile::traverse_breadth_first(IfcUtil::IfcBaseClass* instance, int max_level) {
1604+
return IfcParse::traverse_breadth_first(instance, max_level);
1605+
}
1606+
15561607
void IfcFile::mark_entity_as_modified(int /*id*/)
15571608
{
15581609
by_ref_cached_.clear();
@@ -1825,7 +1876,7 @@ void IfcFile::removeEntity(IfcUtil::IfcBaseClass* entity) {
18251876
throw IfcParse::IfcException("Instance not part of this file");
18261877
}
18271878

1828-
batch_deletion_ids_.insert(id);
1879+
batch_deletion_ids_.push_back(id);
18291880

18301881
if (!batch_mode_) {
18311882
process_deletion_();
@@ -1834,7 +1885,7 @@ void IfcFile::removeEntity(IfcUtil::IfcBaseClass* entity) {
18341885

18351886
void IfcFile::process_deletion_() {
18361887

1837-
for (auto& id : batch_deletion_ids_) {
1888+
for (auto& id : batch_deletion_ids_.get<0>()) {
18381889
auto entity = instance_by_id(id);
18391890

18401891
IfcEntityList::ptr references = instances_by_reference(id);
@@ -1980,10 +2031,10 @@ void IfcFile::process_deletion_() {
19802031

19812032
if (batch_mode_) {
19822033
for (auto it = byref.begin(); it != byref.end();) {
1983-
bool do_delete = batch_deletion_ids_.find(it->first) != batch_deletion_ids_.end();
2034+
bool do_delete = batch_deletion_ids_.get<1>().find(it->first) != batch_deletion_ids_.get<1>().end();
19842035
if (!do_delete) {
19852036
it->second.erase(std::remove_if(it->second.begin(), it->second.end(), [this](int x) {
1986-
return batch_deletion_ids_.find(x) != batch_deletion_ids_.end();
2037+
return batch_deletion_ids_.get<1>().find(x) != batch_deletion_ids_.get<1>().end();
19872038
}), it->second.end());
19882039
do_delete = it->second.empty();
19892040
}

‎src/ifcparse/IfcParse.h‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -269,6 +269,8 @@ namespace IfcParse {
269269
IFC_PARSE_API IfcEntityInstanceData* read(unsigned int i, IfcFile* t, boost::optional<unsigned> offset = boost::none);
270270

271271
IFC_PARSE_API IfcEntityList::ptr traverse(IfcUtil::IfcBaseClass* instance, int max_level = -1);
272+
273+
IFC_PARSE_API IfcEntityList::ptr traverse_breadth_first(IfcUtil::IfcBaseClass* instance, int max_level = -1);
272274
}
273275

274276
IFC_PARSE_API std::ostream& operator<< (std::ostream& os, const IfcParse::IfcFile& f);

0 commit comments

Comments
 (0)