File: DataStructure.tex

package info (click to toggle)
vite 1.2%2Bsvn%2Bgit4.c6c0ce7-8
  • links: PTS, VCS
  • area: main
  • in suites: bookworm
  • size: 21,544 kB
  • sloc: cpp: 32,343; makefile: 461; sh: 144; ansic: 67
file content (249 lines) | stat: -rw-r--r-- 9,711 bytes parent folder | download | duplicates (9)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
%%
%% This file is part of the ViTE project.
%%
%% This software is governed by the CeCILL-A license under French law
%% and abiding by the rules of distribution of free software. You can
%% use, modify and/or redistribute the software under the terms of the
%% CeCILL-A license as circulated by CEA, CNRS and INRIA at the following
%% URL: "http://www.cecill.info".
%% 
%% As a counterpart to the access to the source code and rights to copy,
%% modify and redistribute granted by the license, users are provided
%% only with a limited warranty and the software's author, the holder of
%% the economic rights, and the successive licensors have only limited
%% liability.
%% 
%% In this respect, the user's attention is drawn to the risks associated
%% with loading, using, modifying and/or developing or reproducing the
%% software by the user in light of its specific status of free software,
%% that may mean that it is complicated to manipulate, and that also
%% therefore means that it is reserved for developers and experienced
%% professionals having in-depth computer knowledge. Users are therefore
%% encouraged to load and test the software's suitability as regards
%% their requirements in conditions enabling the security of their
%% systems and/or data to be ensured and, more generally, to use and
%% operate it in the same conditions as regards security.
%% 
%% The fact that you are presently reading this means that you have had
%% knowledge of the CeCILL-A license and that you accept its terms.
%%
%%
%% ViTE developers are:
%%
%%        - COULOMB Kevin
%%        - FAVERGE Mathieu
%%        - JAZEIX Johnny
%%        - LAGRASSE Olivier
%%        - MARCOUEILLE Jule
%%        - NOISETTE Pascal
%%        - REDONDY Arthur
%%        - VUCHENER Clément 
%%

The data structure is composed by 2 main parts~:
\begin{itemize}
\item The first one where while parsing double chained list are built,
\item The second are trees that are built above the lists.
\end{itemize}

\section{The Main classes}
To represent the diversity of the Paj\'e trace format, we have created a wide variety of class that represent the various abstractions on objects~:
\begin{itemize}
\item Trace
\item Container
\item State
\item Event
\item Variable
\item Entity
\end{itemize}

Moreover, we had to create some other classes that help creating these objects such as their type. The definition of these types is necessary to use polymorphism in the optionnal fields that can be added (they all inherit from the Value class).

The basic types used in the data structure are defined in the \textit{values} directory. These types are :
\begin{itemize}
\item Color
\item Date
\item Double
\item Hex
\item Integer
\item Name
\item String
\item Value
\end{itemize}



The definitions for the tree and the interval are in the \textit{tree} directory.

\subsection{The class Trace}
The class \textit{Trace} represents the trace object generated by the user. It contains the elements~:
\begin{itemize}
\item List of type of container
\item List of container
\item List of states
\item List of events
\item List of links
\item List of variables
\end{itemize}
Moreover an attribute that contains the date when the latest action happens in the trace has been created. The methods only enable the construction of the trace, the possibility to get the values of the attributes, and to research some elements in the trace.

\subsection{The class container}
It represents an object of type container. In this class, there are~:
\begin{itemize}
\item A name
\item The date of the beginning and end of the container
\item Type of container
\item A father
\item A list of children
\item Set of states, events, links, and their cardinal
\end{itemize}

The methods are accessors.

\subsection{The class State}
It represents a state of a processor, a container. This class contains the only object of Paj\'e that is not directly presented. Because the use of trees of punctual events, we do not consider the states but the change of states as a relevant facts.
This class has~:
\begin{itemize}
\item Dates of beginning and end
\item Type of state
\item A descriptor of the value of the state, contains the optionnal fields.
\end{itemize}
The methods are accessors and a constructor attribute by attribute.

\subsection{The class event}
It represents an event that occurs in the trace. An event is made by~:
\begin{itemize}
\item A date when it occurs
\item A type of event
\item A descriptor of the value of the event, contains the optionnal fields.
\end{itemize}
Here, the only methods are accessors.

\subsection{The class Link}
It represents a communication between 2 containers in the trace. The attributes are~:
\begin{itemize}
\item Dates of beginning and end
\item A type of link
\item The containers source and destination of the communication
\item A descriptor with the value of the link(contains the optionnal fields).
Methods are accessors.
\end{itemize}

\section{The lists}

The lists are based on the std::list template. They are built in the logical order, each time an element is sent by the parser, it is added in last position in the right list (after making sure the data are rights).

The states are not seen as having a duration but punctual, as brief moments that represent either the beginning or the end of the action. So, to remain logical, a binary tree is not made with states, but with elements from the \textit{StateChange} class, because a state is not punctual whereas a change is, and represents the same information.

The lists may be :
\begin{itemize}
\item List of links, that are contained in the container that is related to the container where the communication starts and where it ends.
\item List of containers
\item List of States/Events, but they are transformed in binary trees after their construction
\end{itemize}

\section{The trees}

The trees do not concern the list of communications. The tree is binary and balanced.

Assuming there is a list, a class is used to build the tree reading only one time each element of the list.

The algorithm of construction is based on binary incrementation. To sum up the main idea, 1 element in the list on 2 is a leaf, as the lowest bit in binary, 1 element on 4 is a father of leaves, as the second lowest bit in binary, etc ...

Assuming we know the lenght of the list, we can calculate the height of the tree (because it is balanced) and then the number of leaves in the lowest level. While we have not reached this number of leaves, we build a binary tree linking the nodes depending on their position in the list (in binary). After this limit, a shift is necessary but the algorithm remain the same.

And so we have a binary tree, linked with an infix order kept : each node happen after all the nodes down in its left side, before all the nodes down in its right side, and these latter happen before the father date.

Then, there is a class that links the data structure and the interface, to be able to get all the events within an interval without being forced to visit each previous node.

%To understand the construction of the binary tree, here it's the diagram of class associated :


\section{Algorithms on the trees :}

\subsection{Browse tree}
\paragraph{The main idea} is a recursif browse of the tree. Going down we select the node that are in the interval, and going up we make sure the node is displayable, and prepare some data for the father to know if it can be displayed.

\paragraph{Algorithm :}

\begin{verbatim}
function browse_recursif ( root, interval, zoom)

if the node is in the interval
   If the interval is wide enought to display the node

      browse_recursif ( left child )
      browse_recursif ( right child )

      If there is a problem on the left side of the left child
          Copy the problematic data in the node
      end if

      If there is a problem on the right side of the left side and
      the left side of the right child
          Making sure we can display the node, or be added to an
          interval of conflict that is then displayed
      end if

     If there is a problem on the right of the right child
        Copy the problematic data in the node
     end if

     If the node has not been displayed yet
        Display the node
     end if

   else // Not wide enought to display 
      Current interval set as problematic in both problematic area
   end if

Else if node is after the interval
   browse_recursif ( left child )
   Copy the data of conflict on the left in the left child

Else // Node before the interval
   browse_recursif ( right child )
   Copy the data of conflict on the right in the right child

end if

end function


\end{verbatim}

\subsection{Getting informations on a clicked element}

\paragraph{Principe :}
First we browse for the links (because if we start by something else : state, counter or event, we would not be able to find the links because they are over the others elements and thin enought not to hide them). Because the use of a distance, sometimes to get the right information, it is important to zoom enought.

\paragraph{Algorithm :}
\begin{verbatim}
function get_information( positionX, positionY)

calculate the lowest container in the tree of container where
 the clic corresponds

for each container father of the container clicked
   look for a communication close enought
   if one is found
      return this communication
   end if
end for each

Search in the list of events of the lowest container
   if one corresponds
      return it
   end if
end search

Search in the list of states of the lowest container
   if one corresponds
      return it
   end if
end search

return no information found

end function
\end{verbatim}