# Hurricane Documentation

# 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 #pragma once
21 #include "hurricane/Box.h"
22 #include "hurricane/Gos.h"
23 #include "hurricane/IntrusiveSet.h"
24
25 namespace Hurricane {
26
27
28
29 // ****************************************************************************************************
30 // QuadTree declaration
31 // ****************************************************************************************************
32
33 class QuadTree {
34 // Types
35 // *****
36
37 public: class GoSet : public IntrusiveSet<Go> {
38 // *******************************************
39
40 public: typedef IntrusiveSet<Go> Inherit;
41
42 public: GoSet();
43
44 public: virtual unsigned _getHashValue(Go* go) const;
45 public: virtual Go* _getNextElement(Go* go) const;
46 public: virtual void _setNextElement(Go* go, Go* nextGo) const;
47
48 };
49
50 // Attributes
51 // **********
52
53 private: QuadTree* _parent;
54 private: DbU::Unit _x;
55 private: DbU::Unit _y;
56 private: Box _boundingBox;
57 private: unsigned _size;
58 private: GoSet _goSet;
59 private: QuadTree* _ulChild; // Upper Left Child
60 private: QuadTree* _urChild; // Upper Right Child
61 private: QuadTree* _llChild; // Lower Left Child
62 private: QuadTree* _lrChild; // Lower Right Child
63
64 // Constructors
65 // ************
66
67 public: QuadTree();
68
69 private: QuadTree(QuadTree* parent);
70
71 private: QuadTree(const QuadTree& quadTree); // not implemented to forbid copy construction
72
73 // Destructor
74 // **********
75
76 public: ~QuadTree();
77
78 // Operators
79 // *********
80
81 private: QuadTree& operator=(const QuadTree& quadTree); // not implemented to forbid assignment
82
83 // Accessors
84 // *********
85
86 //public: static size_t getLocatorAllocateds ();
87 public: const Box& getBoundingBox() const;
88 public: Gos getGos() const;
89 public: Gos getGosUnder(const Box& area, DbU::Unit threshold=0) const;
90
91 // Predicates
92 // **********
93
94 public: bool isEmpty() const {return (_size == 0);};
95
96 // Updators
97 // ********
98
99 public: void insert(Go* go);
100 public: void remove(Go* go);
101
102 // Others
103 // ******
104
105 public: string _getTypeName() const { return _TName("QuadTree"); };
106 public: string _getString() const;
107 public: Record* _getRecord() const;
108
109 public: GoSet& _getGoSet() {return _goSet;};
110 public: QuadTree* _getDeepestChild(const Box& box);
111 public: QuadTree* _getFirstQuadTree() const;
112 public: QuadTree* _getFirstQuadTree(const Box& area) const;
113 public: QuadTree* _getNextQuadTree();
114 public: QuadTree* _getNextQuadTree(const Box& area);
115
116 public: bool _hasBeenExploded() const {return (_ulChild != NULL);};
117
118 public: void _explode();
119 public: void _implode();
120
121 };
122
123
124 } // End of Hurricane namespace.
125
126
127 INSPECTOR_P_SUPPORT(Hurricane::QuadTree);
128 INSPECTOR_P_SUPPORT(Hurricane::QuadTree::GoSet);
129
130
131 // ****************************************************************************************************
132 // Copyright (c) BULL S.A. 2000-2018, All Rights Reserved
133 // ****************************************************************************************************
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:94
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::getGosUnder
Gos getGosUnder(const Box &area, DbU::Unit threshold=0) const
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:33
Hurricane::QuadTree::~QuadTree
~QuadTree()