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}
|