# Hurricane VLSI Database

QuadTree.h
1 // ****************************************************************************************************
2 // File: ./hurricane/QuadTree.h
3 // Authors: R. Escassut
4 // Copyright (c) BULL S.A. 2000-2018, All Rights Reserved
5 //
6 // This file is part of Hurricane.
7 //
8 // Hurricane is free software: you can redistribute it and/or modify it under the terms of the GNU
9 // Lesser General Public License as published by the Free Software Foundation, either version 3 of the
10 // License, or (at your option) any later version.
11 //
12 // Hurricane is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even
13 // the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the Lesser GNU
14 // General Public License for more details.
15 //
16 // You should have received a copy of the Lesser GNU General Public License along with Hurricane. If
17 // not, see <http://www.gnu.org/licenses/>.
18 // ****************************************************************************************************
19
20 #ifndef HURRICANE_QUAD_TREE
21 #define HURRICANE_QUAD_TREE
22
23 #include "hurricane/Box.h"
24 #include "hurricane/Gos.h"
25 #include "hurricane/IntrusiveSet.h"
26
27 namespace Hurricane {
28
29
30
31 // ****************************************************************************************************
32 // QuadTree declaration
33 // ****************************************************************************************************
34
35 class QuadTree {
36 // Types
37 // *****
38
39 public: class GoSet : public IntrusiveSet<Go> {
40 // *******************************************
41
42 public: typedef IntrusiveSet<Go> Inherit;
43
44 public: GoSet();
45
46 public: virtual unsigned _getHashValue(Go* go) const;
47 public: virtual Go* _getNextElement(Go* go) const;
48 public: virtual void _setNextElement(Go* go, Go* nextGo) const;
49
50 };
51
52 // Attributes
53 // **********
54
55 private: QuadTree* _parent;
56 private: DbU::Unit _x;
57 private: DbU::Unit _y;
58 private: Box _boundingBox;
59 private: unsigned _size;
60 private: GoSet _goSet;
61 private: QuadTree* _ulChild; // Upper Left Child
62 private: QuadTree* _urChild; // Upper Right Child
63 private: QuadTree* _llChild; // Lower Left Child
64 private: QuadTree* _lrChild; // Lower Right Child
65
66 // Constructors
67 // ************
68
69 public: QuadTree();
70
71 private: QuadTree(QuadTree* parent);
72
73 private: QuadTree(const QuadTree& quadTree); // not implemented to forbid copy construction
74
75 // Destructor
76 // **********
77
78 public: ~QuadTree();
79
80 // Operators
81 // *********
82
83 private: QuadTree& operator=(const QuadTree& quadTree); // not implemented to forbid assignment
84
85 // Accessors
86 // *********
87
88 //public: static size_t getLocatorAllocateds ();
89 public: const Box& getBoundingBox() const;
90 public: Gos getGos() const;
91 public: Gos getGosUnder(const Box& area) const;
92
93 // Predicates
94 // **********
95
96 public: bool isEmpty() const {return (_size == 0);};
97
98 // Updators
99 // ********
100
101 public: void insert(Go* go);
102 public: void remove(Go* go);
103
104 // Others
105 // ******
106
107 public: string _getTypeName() const { return _TName("QuadTree"); };
108 public: string _getString() const;
109 public: Record* _getRecord() const;
110
111 public: GoSet& _getGoSet() {return _goSet;};
112 public: QuadTree* _getDeepestChild(const Box& box);
113 public: QuadTree* _getFirstQuadTree() const;
114 public: QuadTree* _getFirstQuadTree(const Box& area) const;
115 public: QuadTree* _getNextQuadTree();
116 public: QuadTree* _getNextQuadTree(const Box& area);
117
118 public: bool _hasBeenExploded() const {return (_ulChild != NULL);};
119
120 public: void _explode();
121 public: void _implode();
122
123 };
124
125
126 } // End of Hurricane namespace.
127
128
129 INSPECTOR_P_SUPPORT(Hurricane::QuadTree);
130 INSPECTOR_P_SUPPORT(Hurricane::QuadTree::GoSet);
131
132
133 #endif // HURRICANE_QUAD_TREE
134
135
136 // ****************************************************************************************************
137 // Copyright (c) BULL S.A. 2000-2018, All Rights Reserved
138 // ****************************************************************************************************
Hurricane::Go
Go description (API)
Definition: Go.h:36
Hurricane::DbU::Unit
std::int64_t Unit
Definition: DbU.h:70
Hurricane::QuadTree::isEmpty
bool isEmpty() const
Definition: QuadTree.h:96
Hurricane::QuadTree::getGosUnder
Gos getGosUnder(const Box &area) const
Hurricane::QuadTree::getGos
Gos getGos() const
Hurricane::GenericCollection
Generic Collection auto-pointer.
Definition: Collection.h:28
Hurricane::Box
Box description (API)
Definition: Box.h:31
Hurricane::QuadTree::insert
void insert(Go *go)
Hurricane::QuadTree::QuadTree
QuadTree()
Hurricane::QuadTree::getBoundingBox
const Box & getBoundingBox() const
Hurricane
The namespace dedicated to Hurricane.
Definition: Generalities.dox:5
Hurricane::QuadTree
QuadTree description (API)
Definition: QuadTree.h:35
Hurricane::QuadTree::~QuadTree
~QuadTree()

Generated by doxygen 1.8.14 on Sun Mar 8 2020 | Return to top of page

Hurricane VLSI Database | Copyright © 2000-2016 Bull S.A. All rights reserved