I have known for long that in the constructors of a class in C++ and literally any major modern Object Oriented programming languages, the virtual methods of the class are not to work as one might expect - in fact only the method defined in the class that contains the constructor that is being executed is to be executed from within the constructor rather than the overriding one located in the class of which the object to be created is an instance, the reason simply being that the run-time information of the derived class on which the invocation of the overriding method(s) depends at this stage hasn't been created as the order of constructing is always from the base class to the derived. Note this is one of the questions I was given in a interview with google at Shanghai and I didn't get quite right. I have fully understood the significance of it since then as it's so fundamental and it will both enhance your code at a potentially architectural level and save you time debugging.
However, recently I found it was not the end. Despite the simplicity of that, it seems I didn't learn a proper lesson from it. This morning I encountered a similar issue, not with constructor but with destructor (which in C# dialect may also be known as 'finaliser'). I finally decided to extend a dialog class to deal with some importing and exporting stuff so that objects of a layer and of particular types recently implemented could be exchanged with files of GIS format as those of all the other layers were, and in the extended class I defined a exporter instance for polylines in addition to the existing one in the base class for polygons. I didn't forget to write the overriding methods for closing the files and doing other cleanup, nor did I forget to call the corresponding base methods from the overriding methods as appropriate or mark all the relevant methods 'virtual'. However the separate file for polylines never got exported correctly. As it had worked properly when done by simply adding logic to the base, so I was pretty sure the methods are logically correct. After quite a bit of debugging, comparisons and analysis, I found the problem was indeed to do with finalising which I had been suspecting most. Since the calling of finalising method was only made in the destructor of the base class, the overriding finalising method in the derived class never got called. The principle behind is the almost same as that behind the constructor, the only difference is the order is reversed - the destructor in the base class as is called last never has any knowledge of the derived class and is unable to call the overriding method.
The conclusion, to be simple, is that as you should avoid whatever attention you should pay with regards to virtual method calls from a constructor should equally be paid to those from a destructor.
An example of how this plays a part in a real programming paradigm,
The following is a typical and standard way of defining a class that implements IDisposable interface
class DisposableObject : IDisposable
{
protected bool disposed; // or any member that can indicate if the
// object has been finalised in any way
// however unlike what's suggested by most
// of the resources it should be made accessible
// from a derived class to make this inherited
// disposal implementation to work (unless a
// separate one is set up in the derived class)
~DisposableObject()
{
Dispose(false); // called from destructor
}
// As it's an implementation of IDisposable method, it has to be public
// And as it's normally called on the interface instance, it doesn't have
// to be declared virtual
public void Dispose()
{
Dispose(true); // called from diposing method
GC.SuppressFinalize(this);
}
// Dispose of managed resources, this is a safe and logic method
// that has already been widely practised,
// http://msdn.microsoft.com/en-us/library/system.idisposable.dispose.aspx
protected virtual void Dispose(bool disposing)
{
if (!disposed)
{
if (disposing)
{
// Dispose of managed resources
// ...
}
// cleanup unmanaged resources
// ...
disposed = true;
}
}
}
However the derived disposable class is rarely looked at. According to the above analysis of how destructors work, it should be like,
class DerivedDisposableObject : DisposableObject
{
~DisposableObject()
{
Dispose(false); // must not rely on the base class to dispose if an
// overriding method is defined; the base Dispose method
// will be called from the base destructor but its
// internal will not be unnecessarily executed as the
// flag of 'disposed' has already been flipped here
}
// void (IDispose.)Dispose() is not necessary (unless it's different to
// the base) since it's not at the finalising stage and the overriding method
// would be properly invoked from base class
protected virtual void Dispose(bool disposing)
{
if (!disposed)
{
if (disposing)
{
// Dispose of managed resources
// ...
}
// cleanup unmanaged resources
// ...
// DO NOT set 'disposed' to true as the base method needs it
base.Dispose(disposing);
}
}
}
Tuesday, July 31, 2012
Wednesday, July 4, 2012
Exercises of Chapter 3 (Part 1/5), Computational Geometry
Exercise 3.2 Show that the edges of the convex hull of a point set S will always be in every triangulation of S.
Proof. Because they are not crossing any of the edges other than themselves that have two points of S as its end points. □
Exercise 3.3 The definition of a triangulation of a point set does not even mention "triangles". Show that all the regions of subdivision inside the convex hull must indeed be triangles
Proof. The definition is repeated here again
A triangulation of a planar point set S is a subdivision of the plane determined by a maximal set of non-crossing edges whose vertex set is S.
As they are non-crossing each regions of subdivision must be a polygon. However if it's a polygon with more than 3 vertices, it can be further divided thus the set has yet to reach maximum.□
Exercise 3.4 Extend the triangle-splitting algorithm to work for points that may include three or more collinear points (but not all collinear)
Solution. Find the convex hull first leaving all the points on the edges of the hull between vertices out. Triangulate the hull ignoring again all the points on the edges. Performing the proceedings of the original algorithm for all points strictly interior to existing triangles with again points on edges ignored. Finally triangulate all the triangles just triangulated with points on edges.□
Exercise 3.5 Analyse the time complexity of the triangle-splitting algorithm.
Analysis. Only the original algorithm for non-collinear point set is considered. Hull finding takes O(n log n). Suppose there are m points on the hull, then there are m-2 triangles created by the initial triangulation, and m-n points inside. Each point to be added needs to be checked against all existing triangles and adds two triangles to the triangulation once added. The check determines if the point is inside the particular triangle, which take constant time. So this phase has (m+n-5)(n-m)/2 steps which is basically O(n2). Therefore the overall complexity is O(n2). □
Exercise 3.7 Prove or disprove: The triangle-splitting algorithm produces all possible triangulations of a point set.
Disprove (It's not true). As the triangulation produced by this algorithm has the restriction that it must contain diagonals of the hull, a counter-example can easily made by a triangulation of point set which doesn't contain any diagonals of the hull. □
Exercise 3.8 Analyse the complexity of the incremental algorithm.
Analysis. Sorting takes O(n log n); Visibility testing for about n nodes requires O(n2) time at minimum (by keeping track of the hull and performing the same process as for convex hull finding). So the overall complexity is O(n2). □
Exercise 3.9 Prove that the incremental algorithm produces a triangulation of a point set in general position.
Prove. Just discuss a special case where three points are collinear and the point behind is not considered as it's not visible to the current point, which is fine as it's the right way to do the triangulation. □
Exercise 3.10 Prove or disprove: The incremental algorithm produces all possible triangulations of a point set in general position.
Disprove (It's not true). Imagine a big triangle with quite a few points near all of its three edges exterior to the triangle, when properly set this point set can never be triangulated in such a way that the edges of big triangle remain. □
Exercise 3.11 Alter the Graham scan convex hull algorithm (Section 2.4) to compute triangulations.
Solution. Each time a new vertex is being processed, it should be combined with the latest edge scanned through to form a new triangle. For each reflex point (with right turn) encountered in the scanning process, simply add the triangle formed by the point and the edge introduced to eliminate the right turn. □
Exercise 3.14 Show that every triangulation has some vertex of degree at most five.
Proof. Use theorem 3.13 which declares that any triangulation of point set with n = k + h points where k is the the number of interior vertices and h that of those on the hull has 3k + 2h - 3 edges. Those edges are shared by those vertices. So the summed degree of the vertices is twice the edge number, which is 6k + 4h - 3, distributed to n vertices. According to pigeon hole principle at least one vertex has degree no more than ⌊( 6k + 4h - 3 ) / (k + h)⌋ = ⌊6 - ( 2h + 3 ) / (k + h)⌋ ≤ 5. □
Exercise 3.15 Construct a point set S with n+2 points such that the number of triangulations of S is greater than Catalan number Cn.
Example. See the example in Exercise 3.18 when n gets to 6. □
Exercise 3.17 Compare this value (30n, which is the upper bound of number of triangulations of an arbitrary point set) with Catalan number derived in Theorem 1.19.
Analysis. Number of triangulations of convex hull with n vertices is Cn-2, this number is generally smaller and growing (at a rate lower than 4) much slower than 30n. □
Exercise 3.18 Consider the point set S given in Figure 3.5. It is made of two "double chains" of points, where every pair of points from different chains is visible to each other. Show that the edges drawn in the figure appear in every triangulation of S. Moreover, if there are n points in each chain, find the number of triangulations of S.
Proof. If two points are not connected in a triangulation there must be an edge in the triangulation going across the edge that connects the two points. As every pair of points from different chains is visible to each other, it can be proved that there is no such edge for all the edges drawn in the figure.
Solution to the question. If we use T(m,n) to denote the number of triangulations between the chains of a point set which takes m points from the upper chain and n from the lower chain (it can be proved that this measurement is always applicable to this point set and any of its subsets). It is easy to see the following relationships
T(m,n) = T(n,m)
T(m,n) = T(m-1,n) + T(m,n-1)
T(m,1) = 1
The above relationships lead to T(m,n) = C(m+n-2, m-1) and T(n,n) = C(2n-2, n-1) where C is the combination function.
The polygon enclosed by either of the chain and the horizontal line attached to the chain is a convex polygon so it independently has Catalan(n-2) triangulations, therefore the total number of triangulations is Catalan(n-2)2 C(2n-2,n-1). □
Proof. Because they are not crossing any of the edges other than themselves that have two points of S as its end points. □
Exercise 3.3 The definition of a triangulation of a point set does not even mention "triangles". Show that all the regions of subdivision inside the convex hull must indeed be triangles
Proof. The definition is repeated here again
A triangulation of a planar point set S is a subdivision of the plane determined by a maximal set of non-crossing edges whose vertex set is S.
As they are non-crossing each regions of subdivision must be a polygon. However if it's a polygon with more than 3 vertices, it can be further divided thus the set has yet to reach maximum.□
Exercise 3.4 Extend the triangle-splitting algorithm to work for points that may include three or more collinear points (but not all collinear)
Solution. Find the convex hull first leaving all the points on the edges of the hull between vertices out. Triangulate the hull ignoring again all the points on the edges. Performing the proceedings of the original algorithm for all points strictly interior to existing triangles with again points on edges ignored. Finally triangulate all the triangles just triangulated with points on edges.□
Exercise 3.5 Analyse the time complexity of the triangle-splitting algorithm.
Analysis. Only the original algorithm for non-collinear point set is considered. Hull finding takes O(n log n). Suppose there are m points on the hull, then there are m-2 triangles created by the initial triangulation, and m-n points inside. Each point to be added needs to be checked against all existing triangles and adds two triangles to the triangulation once added. The check determines if the point is inside the particular triangle, which take constant time. So this phase has (m+n-5)(n-m)/2 steps which is basically O(n2). Therefore the overall complexity is O(n2). □
Exercise 3.7 Prove or disprove: The triangle-splitting algorithm produces all possible triangulations of a point set.
Disprove (It's not true). As the triangulation produced by this algorithm has the restriction that it must contain diagonals of the hull, a counter-example can easily made by a triangulation of point set which doesn't contain any diagonals of the hull. □
Exercise 3.8 Analyse the complexity of the incremental algorithm.
Analysis. Sorting takes O(n log n); Visibility testing for about n nodes requires O(n2) time at minimum (by keeping track of the hull and performing the same process as for convex hull finding). So the overall complexity is O(n2). □
Exercise 3.9 Prove that the incremental algorithm produces a triangulation of a point set in general position.
Prove. Just discuss a special case where three points are collinear and the point behind is not considered as it's not visible to the current point, which is fine as it's the right way to do the triangulation. □
Exercise 3.10 Prove or disprove: The incremental algorithm produces all possible triangulations of a point set in general position.
Disprove (It's not true). Imagine a big triangle with quite a few points near all of its three edges exterior to the triangle, when properly set this point set can never be triangulated in such a way that the edges of big triangle remain. □
Exercise 3.11 Alter the Graham scan convex hull algorithm (Section 2.4) to compute triangulations.
Solution. Each time a new vertex is being processed, it should be combined with the latest edge scanned through to form a new triangle. For each reflex point (with right turn) encountered in the scanning process, simply add the triangle formed by the point and the edge introduced to eliminate the right turn. □
Exercise 3.14 Show that every triangulation has some vertex of degree at most five.
Proof. Use theorem 3.13 which declares that any triangulation of point set with n = k + h points where k is the the number of interior vertices and h that of those on the hull has 3k + 2h - 3 edges. Those edges are shared by those vertices. So the summed degree of the vertices is twice the edge number, which is 6k + 4h - 3, distributed to n vertices. According to pigeon hole principle at least one vertex has degree no more than ⌊( 6k + 4h - 3 ) / (k + h)⌋ = ⌊6 - ( 2h + 3 ) / (k + h)⌋ ≤ 5. □
Exercise 3.15 Construct a point set S with n+2 points such that the number of triangulations of S is greater than Catalan number Cn.
Example. See the example in Exercise 3.18 when n gets to 6. □
Exercise 3.17 Compare this value (30n, which is the upper bound of number of triangulations of an arbitrary point set) with Catalan number derived in Theorem 1.19.
Analysis. Number of triangulations of convex hull with n vertices is Cn-2, this number is generally smaller and growing (at a rate lower than 4) much slower than 30n. □
Exercise 3.18 Consider the point set S given in Figure 3.5. It is made of two "double chains" of points, where every pair of points from different chains is visible to each other. Show that the edges drawn in the figure appear in every triangulation of S. Moreover, if there are n points in each chain, find the number of triangulations of S.
Proof. If two points are not connected in a triangulation there must be an edge in the triangulation going across the edge that connects the two points. As every pair of points from different chains is visible to each other, it can be proved that there is no such edge for all the edges drawn in the figure.
Solution to the question. If we use T(m,n) to denote the number of triangulations between the chains of a point set which takes m points from the upper chain and n from the lower chain (it can be proved that this measurement is always applicable to this point set and any of its subsets). It is easy to see the following relationships
T(m,n) = T(n,m)
T(m,n) = T(m-1,n) + T(m,n-1)
T(m,1) = 1
The above relationships lead to T(m,n) = C(m+n-2, m-1) and T(n,n) = C(2n-2, n-1) where C is the combination function.
The polygon enclosed by either of the chain and the horizontal line attached to the chain is a convex polygon so it independently has Catalan(n-2) triangulations, therefore the total number of triangulations is Catalan(n-2)2 C(2n-2,n-1). □
Subscribe to:
Comments (Atom)