]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /* |
2 | Copyright 2010 Intel Corporation | |
3 | ||
4 | Use, modification and distribution are subject to the Boost Software License, | |
5 | Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
6 | http://www.boost.org/LICENSE_1_0.txt). | |
7 | */ | |
8 | //compare_schematics.hpp | |
9 | #ifndef BOOST_POLYGON_TUTORIAL_COMPARE_SCHEMATICS_HPP | |
10 | #define BOOST_POLYGON_TUTORIAL_COMPARE_SCHEMATICS_HPP | |
11 | #include <string> | |
12 | #include "schematic_database.hpp" | |
13 | ||
14 | bool compare_connectivity(std::string& ref_net, std::string& net, | |
15 | schematic_database& reference_schematic, | |
16 | schematic_database& schematic, | |
17 | std::vector<std::size_t>& reference_to_internal_device_map, | |
18 | std::size_t node_id) { | |
19 | std::set<std::size_t>& ref_nodes = reference_schematic.nets[ref_net]; | |
20 | std::set<std::size_t>& nodes = schematic.nets[net]; | |
21 | for(std::set<std::size_t>::iterator itr = ref_nodes.begin(); | |
22 | itr != ref_nodes.end() && *itr < node_id; ++itr) { | |
23 | if(nodes.find(reference_to_internal_device_map[*itr]) == nodes.end()) | |
24 | return false; | |
25 | } | |
26 | return true; | |
27 | } | |
28 | ||
29 | bool compare_schematics_recursive | |
30 | (schematic_database& reference_schematic, | |
31 | schematic_database& schematic, | |
32 | std::vector<std::size_t>& reference_to_internal_device_map, | |
33 | std::set<std::size_t>& assigned_devices, std::size_t node_id){ | |
34 | //do check of equivalence up to this node | |
35 | for(std::size_t i = 0; i < node_id; ++i) { | |
36 | for(std::size_t j = 0; j < reference_schematic.devices[i].terminals.size(); ++j) { | |
37 | device& rd = reference_schematic.devices[i]; | |
38 | device& xd = schematic.devices[reference_to_internal_device_map[i]]; | |
39 | if(rd.type == "PIN") { | |
40 | if(rd.terminals[j] != xd.terminals[j]) | |
41 | return false; | |
42 | } else { | |
43 | //connectivity must be the same | |
44 | if(j == 1) { | |
45 | //gate has to be the same net | |
46 | if(!compare_connectivity(rd.terminals[1], xd.terminals[1], reference_schematic, schematic, | |
47 | reference_to_internal_device_map, node_id)) | |
48 | return false; | |
49 | } else { | |
50 | //order of nets in source and drain is not important so check both ways and accept either | |
51 | if(!compare_connectivity(rd.terminals[j], xd.terminals[0], reference_schematic, schematic, | |
52 | reference_to_internal_device_map, node_id) && | |
53 | !compare_connectivity(rd.terminals[j], xd.terminals[2], reference_schematic, schematic, | |
54 | reference_to_internal_device_map, node_id)) | |
55 | return false; | |
56 | } | |
57 | } | |
58 | } | |
59 | } | |
60 | if(node_id >= reference_schematic.devices.size()) | |
61 | return true; //final success | |
62 | ||
63 | //recurse into subsequent nodes | |
64 | for(std::size_t i = 0; i < schematic.devices.size(); ++i) { | |
65 | if(reference_schematic.devices[node_id].type != | |
66 | schematic.devices[i].type) | |
67 | continue; //skip dissimilar devices | |
68 | //avoid multi-assignment of devices | |
69 | if(assigned_devices.find(i) == assigned_devices.end()) { | |
70 | reference_to_internal_device_map[node_id] = i; | |
71 | std::set<std::size_t>::iterator itr = assigned_devices.insert(assigned_devices.end(), i); | |
72 | if(compare_schematics_recursive(reference_schematic, schematic, | |
73 | reference_to_internal_device_map, | |
74 | assigned_devices, node_id + 1)) | |
75 | return true; | |
76 | assigned_devices.erase(itr); | |
77 | } | |
78 | } | |
79 | //could not find match between schematics | |
80 | return false; | |
81 | } | |
82 | ||
83 | //this is a trivial brute force comparison algorithm because comparing | |
84 | //schematics does not require the use of Boost.Polygon and doing it more | |
85 | //optimally does not add to the tutorial | |
86 | inline bool compare_schematics(schematic_database& reference_schematic, | |
87 | schematic_database& schematic) { | |
88 | std::vector<std::size_t> | |
89 | reference_to_internal_device_map(reference_schematic.devices.size(), 0); | |
90 | std::set<std::size_t> assigned_devices; | |
91 | return compare_schematics_recursive(reference_schematic, schematic, | |
92 | reference_to_internal_device_map, | |
93 | assigned_devices, 0); | |
94 | } | |
95 | ||
96 | #endif |