Warning, /education/kig/DESIGN is written in an unsupported language. File is not indexed.

0001 EXPLANATION OF THE KIG DESIGN
0002 =============================
0003 
0004 1. Object system
0005 ----------------
0006 
0007 The Kig Object System is a design I'm particularly proud of.  It
0008 started out pretty basic, but has undergone some major revisions, that
0009 have proven very succesful.  Currently, I have just made one more
0010 major change, and I think this will be the last majore change to it
0011 for quite some time to come.  That's also why I'm writing this
0012 explanation for other developers.
0013 
0014 
0015 
0016 1.1 ObjectImp's:  Basic objects.
0017 
0018 An ObjectImp represents the current state of an object in Kig.  It
0019 keeps information about what type of object it is ( e.g. a line, a
0020 point, a circle etc. ), and its exact data ( e.g. the center and
0021 radius of the circle ).  It is *not* in any way aware of how the
0022 object was calculated from its parents (e.g. is this a line that is
0023 constructed as the parallel of another line, or as the line going
0024 through two given points ? ) or how it is drawn on the window (
0025 e.g. the thickness of the line, its color etc. ).
0026 
0027 There is also the notion of BogusImp's in Kig.  These are special
0028 kinds of ObjectImp's that *only* hold data.  They do not represent any
0029 real object that can be drawn on a window.  Their use is *only* in
0030 holding data for other objects to use.  Examples are StringImp,
0031 IntImp, ConicImp etc.
0032 
0033 There are a lot of ObjectImp's in Kig, most of them are in files
0034 called *_imp.h and *_imp.cc or *_imp.cpp in the objects subdirectory.
0035 Examples are PointImp, LineImp, ConicImp, CircleImp, CubicImp,
0036 AngleImp etc.
0037 
0038 There is also the concept of ObjectImpType's.  These identify a kind
0039 of ObjectImp.  They carry information about the inheritance among the
0040 different ObjectImp types, and some strings identifying them.  You can
0041 get hold of the ObjectImpType of a certain ObjectImp by using its
0042 type() method, you can also get hold of them by name using
0043 ObjectImpFactory.
0044 
0045 
0046 1.2 ObjectCalcer's: calculating ObjectImp's from other ObjectImp's
0047 
0048 An ObjectCalcer is an object that represents an algorithm for
0049 calculating an ObjectImp from other ObjectImp's.  It is also a node in
0050 the dependency graph of a certain document. E.g. a LineImp can be
0051 calculated from the two PointImp's it has to go through; every time
0052 either of them moves, this calculation is redone.  In this case, there
0053 would be an ObjectCalcer that keeps a reference to its two parents (
0054 the ObjectCalcer's representing the points ), and that will calculate
0055 its ObjectImp value every time it is asked to do so ( i.e. every time
0056 one of its parents moves.. ).
0057 
0058 Because of the complex relations that ObjectCalcer's hold to other
0059 ObjectCalcer's and to other classes, they have been made
0060 reference-counted.  This means that they keep a count internally of
0061 how much times a pointer to them is held.  If this count reaches 0,
0062 this means that nobody needs them anymore, and they delete themselves.
0063 E.g. an ObjectCalcer always keeps a reference to its parents, to
0064 ensure that those aren't deleted before it is deleted.  
0065 
0066 In the inheritance graph of a document, the lowermost objects keep
0067 references to their parents and those keep reference to their parents,
0068 so that all of the top of the graph is kept alive.  Of course, someone
0069 needs to keep a reference to the bottommost objects in the graph,
0070 because otherwise, the entire graph would be deleted.  As we will see
0071 later, an external class ( ObjectHolder ) keeps a reference to the
0072 ObjectCalcer's that the user is aware of.  Thus, the reference
0073 counting system makes sure that all the objects that the user knows
0074 about, and all of their ancestors are kept alive, and the others die.
0075 At the end of the program, this reference is released, and all the
0076 objects are deleted.
0077 
0078 A special case of an ObjectCalcer is the ObjectConstCalcer.  This is
0079 an ObjectCalcer that has no parents, and only holds some data.  The
0080 data is held as an ObjectImp of some type, and it will remain
0081 constant, and no calculation needs to be done to get it, it is just
0082 returned every time it is needed.
0083 
0084 Other ObjectCalcer's are ObjectPropertyCalcer and ObjectTypeCalcer.
0085 ObjectTypeCalcer is a ObjectCalcer that calculates an object according
0086 to what a ObjectType object specifies.  It basically forwards all
0087 calculations to that object ( check below ).  An ObjectPropertyCalcer
0088 gets data from a property of a certain object.  In fact, ObjectImp's
0089 can specify property's ( e.g. properties of a circle are its radius,
0090 its circumference, its center etc. An angle has its bisector as a
0091 LineImp property ), and they are returned as ObjectImp's of an
0092 appropriate type.  The ObjectPropertyCalcer just gets one of the
0093 properties of a certain ObjectImp and stores it.
0094 
0095 
0096 1.3 ObjectType's: a specification of how to calculate an object.
0097 
0098 An ObjectType represents a certain algorithm to calculate an ObjectImp
0099 from other ObjectImp's.  Unlike an ObjectCalcer, it does not
0100 participate in the inheritance graph, and there is only one
0101 instantiation of each type of ObjectType.  An ObjectTypeCalcer is an
0102 ObjectCalcer that keeps a pointer to a certain ObjectType, and
0103 forwards all requests it gets to its ObjectType.  It's very normal
0104 that multiple ObjectTypeCalcer's share the same ObjectType.
0105 
0106 There are very much ObjectType's in Kig, check out all of the files
0107 that end in *_type.* or *_types.* in the objects subdirectory of the
0108 Kig source code.
0109 
0110 
0111 1.4 ObjectHolder's: a link from the document to the hierarchy
0112 
0113 An ObjectHolder represents an object as it is known to the document.
0114 It keeps a pointer to an ObjectCalcer, where it gets its data ( the
0115 ObjectImp that the ObjectCalcer holds ) from.  It also holds
0116 information about how to draw this ObjectImp on the window, by keeping
0117 a pointer to an ObjectDrawer ( see below ).  In its draw method, it
0118 gets the ObjectImp from the ObjectCalcer, and passes it to the
0119 ObjectDrawer, asking it to draw the ObjectImp on the window.
0120 
0121 The document ( check the KigDocument class ) holds a list of these
0122 ObjectHolder's.  This is its only link with the ObjectCalcer
0123 dependency graph.  An ObjectHolder keeps a reference to its ObjectCalcer.
0124 
0125 
0126 1.5 ObjectDrawer: An intelligent struct keeping some data about how to
0127     draw an ObjectImp on screen.
0128 
0129 An ObjectDrawer is used by an ObjectHolder to keep information about
0130 how to draw an ObjectImp on the window.  It is really nothing more
0131 than a struct with some convenience methods.  It does not have any
0132 virtual methods, or have any complex semantics.  It keeps information
0133 like the thickness of an object, its color, and whether or not it is
0134 hidden.
0135 
0136 
0137 2. Interesting Issues
0138 ---------------------
0139 
0140 Here, I explain some parts of the design that may at first look
0141 difficult to understand.  This part assumes you have read the above.
0142 
0143 
0144 2.1 Text labels 
0145 
0146 Text labels in Kig are designed in a pretty flexible
0147 way.  I will explain all the classes involved.
0148 
0149 2.1.1 TextImp
0150 
0151 First of all, there is the TextImp class.  It is an ObjectImp (
0152 cf. supra ), and thus represents a piece of text that can be drawn on
0153 the document.  It contains a QString ( the text to be shown ), a
0154 coordinate ( the location to draw it ), and a boolean saying whether a
0155 frame should be drawn around it.  As with all ObjectImp's, it does not
0156 contain any code for calculating it, or how it behaves on user input.
0157 Most of this is handled by the TextType class.
0158 
0159 2.1.2 TextType
0160 
0161 The TextType class is an implementation of an ObjectType.  It contains
0162 code specifying how to calculate a TextImp from its parents, and for
0163 how it behaves on user input.  A text object has at least three
0164 parents, and can handle any number of optional arguments.  The three
0165 mandatory arguments are an int, which is set to 1 or 0 depending on
0166 whether the label needs a surrounding box, a PointImp, containing the
0167 location of the text label, and a string containing the text of the
0168 label.  The text can contain tokens like '%1', '%2' etc.  Every
0169 additional argument is used to replace the lowest-numbered of those
0170 tokens, with its string representation.  The function
0171 ObjectImp::fillInNextEscape is used for this.
0172 
0173 For example, if a TextType has the following parents:
0174 a IntImp with value 0
0175 a PointImp with value (0,0)
0176 a String with value "This segment is %1 units long."
0177 a DoubleImp with value 3.9
0178 
0179 This would result in a string being drawn at the coordinate (0,0),
0180 with no surrounding box, and showing the text "This segment is 3.9
0181 units long.".
0182 
0183 All this gives labels in Kig a lot of flexibility.
0184 
0185 2.2 Locuses
0186 
0187 Locuses are a mathematical concept that has been modelled in Kig.
0188 Loosely defined, a locus is the mathematical shape defined by the set
0189 of points that a certain point moves through while another point is
0190 moved over its constraints.  This can be used to define mathematical
0191 objects like conics, and various other things.  It has been modelled
0192 in Kig in the most flexible way I can imagine, and I must say that I'm
0193 proud of this design.
0194 
0195 2.2.1 Constrained points
0196 
0197 In the implementation of this, we use the concept of constrained
0198 points.  This is a point that is attached to a certain curve.  It is
0199 implemented in Kig by the ConstrainedPointType, which takes a CurveImp
0200 and a DoubleImp as parents and calculates a Point from these by using
0201 the CurveImp::getPoint function.
0202 
0203 2.2.2 The Implementation
0204 
0205 When a Locus is constructed by the user, Kig receives two points, at
0206 least one of which is a Constrained point, and the other one somehow
0207 depends on the first.  This is checked before trying to construct a
0208 Locus, and the user is not allowed to try to construct locuses from
0209 other sorts of points.
0210 
0211 Next, Kig takes a look at the ObjectCalcer hierarchy.  We look at the
0212 smallest part of the hierarchy that contains all paths from the first
0213 point to the second point.  We then determine all objects that are not
0214 *on* one of those paths ( meaning that they are not calculated from
0215 the first point, or another object that is on one of those paths ),
0216 but that are parents of one or more objects that are on those paths.
0217 I call this set of objects the "side of the path" sometimes in the
0218 code.  The function that finds them is called sideOfTreePath.
0219 
0220 Next, an ObjectHierarchy object is constructed, which stores the way
0221 to calculate the second point from the first point and the objects
0222 from the previous paragraph.
0223 
0224 An object is then constructed that has as parent the curve parent that
0225 the first point is constrained to, the HierarchyImp containing the
0226 ObjectHierarchy from the previous paragraph, and all the objects from
0227 the "side of the tree".  This new object is an ObjectTypeCalcer with
0228 the LocusType as its type.  In its calc() function, it calculates a
0229 LocusImp by taking the objecthierarchy and substituting all the
0230 current values of the objects from the "side of the path", resulting
0231 in an ObjectHierarchy that takes one PointImp and calculates another
0232 PointImp from that.  The LocusImp then contains the new
0233 ObjectHierarchy and the current value of the curve that the first
0234 point is constrained to.  In the drawing function of this LocusImp,
0235 points on the curve are calculated, and then the hierarchy is used to
0236 calculated from those points the location of the second point.  A
0237 dynamic feedback algorithm, which has been written with a lot of help
0238 from the mathematician "Franco Pasquarelli" is used to determine which
0239 of the points on the curve should be used.
0240 
0241 2.2.3 The Rationale
0242 
0243 The above explanation may seem very complicated, but I am very much
0244 convinced that this *is* the proper way to handle locuses.  I will
0245 here try explain why I think it is superior to the much simpler
0246 implementation that is used by much other programs.
0247 
0248 The basic alternative implementation involves just keeping a pointer
0249 to the first and second point in the locus object, and when the locus
0250 is drawn, the first point is moved over all its possible locations,
0251 the second point is calculated, and a point is drawn at its new
0252 location.
0253 
0254 The reason I think that this is a bad implementation is that it is not
0255 possible to model the real dependency relations properly in this
0256 scheme.  For example, the locus object would then be made dependent on
0257 the constrained point.  This is wrong because when the constrained
0258 point moves within the limits of the curve constraining it, the locus
0259 does by definition not change.  Also, if the constrained point is
0260 redefined so that it is no longer constrained to any curve, this is a
0261 major problem, because it would invalidate the locus.  Another point
0262 is that in practice, the locus depends on more objects than its
0263 parents alone.  This is not a good thing, because it makes it
0264 impossible to optimise drawing of the objects, using the information
0265 about which objects depend on which others, because this information
0266 is invalid.
0267 
0268 The reason we need to calculate the "side of the path" above is that,
0269 together with the curve that the first point is constrained to, these
0270 are the objects that the locus is really dependent on.
0271 
0272 The current Kig system correctly models all dependency relations to
0273 the extent possible, while keeping a correct implementation.
0274 
0275