* Binary Search Tree
- Search in BALANCED BST: O(logN)
- Insert and delete in BALANCED BST: O(logN)
- Obtain the parent node for a given node: O(logN)
- How to get maximal and minimal value in BST
- Output all the nodes SORTED in BST: O(N)
- Recursive algorithm associated
* Heap: Complete Binary Tree
- Implemented efficiently by an array due to its order and shape properties
- Insert, delete_min/max and delete: O(logN)
- Increase and decrease key: O(logN)
- Build heap: O(NlogN)
- Search in heap: O(N)
* Traversal
Preorder, DFS, postorder, in-order, and BFS
* Set
A set contains a sorted set of unique objects, which is usually implemented by BST.
* Examples
- Preorder traversal of BST without recursion
Stack is used to store the intermediate variables.
- Find the lowest ancestor of two nodes in one BST
The one with value between these two nodes would be the answer.
- Find the first K largest numbers or to find a subset of K numbers which sums up to at most T
Partial sort with one heap of K units.
- Find the K largest/smallest number in a heap of N elements with O(KlogK)/O(1). K is much less than N
- Construct a Huffman code and compute the sum of a large set of floating point number
Thursday, September 6, 2007
List
* Single Linked List
- One Head Pointer Must Be Associated
To change the head pointer in one sub-routine, the pointer itself instead of its copy must be changed. Therefore the pointer to head pointer must be passed in ANY sub-routines which changes the head/tail pointers.
- Lists End With NULL
This must be checked when the traverse happens.
- Insert And Delete
When deleting one element in the list, the element before this one must be obtained.
When inserting one element, it depends on whether it is inserted before or after a specific element.
- Free Every Element in The List
- Special Cases Processing: Head and Tail; Length of List == 0, 1, 2, ...
* Examples
- Implement stack data structure
We could implement stack with variable array or single linked list. Due to the heavy overhead of maintaining the memory of elements, variable array might be suitable for small data set.
- Insert and delete function in list with head and tail pointers
How to process special cases?
- Get the mth element in reverse order in one list
1) n = N - m; Two traverses to get N and n; O(N)
2) Two pointers with the distance of m
- How to check if the list contains loop?
Fast and slow pointers
- How to delete one element if only the pointer to this element is given, i.e. without traversing?
Copy the content of next element to this one and delete next element.
- How to reverse one list with/without recursion?
- One Head Pointer Must Be Associated
To change the head pointer in one sub-routine, the pointer itself instead of its copy must be changed. Therefore the pointer to head pointer must be passed in ANY sub-routines which changes the head/tail pointers.
- Lists End With NULL
This must be checked when the traverse happens.
- Insert And Delete
When deleting one element in the list, the element before this one must be obtained.
When inserting one element, it depends on whether it is inserted before or after a specific element.
- Free Every Element in The List
- Special Cases Processing: Head and Tail; Length of List == 0, 1, 2, ...
* Examples
- Implement stack data structure
We could implement stack with variable array or single linked list. Due to the heavy overhead of maintaining the memory of elements, variable array might be suitable for small data set.
- Insert and delete function in list with head and tail pointers
How to process special cases?
- Get the mth element in reverse order in one list
1) n = N - m; Two traverses to get N and n; O(N)
2) Two pointers with the distance of m
- How to check if the list contains loop?
Fast and slow pointers
- How to delete one element if only the pointer to this element is given, i.e. without traversing?
Copy the content of next element to this one and delete next element.
- How to reverse one list with/without recursion?
Wednesday, September 5, 2007
Sync in MPEG
* SCR/PCR, PTS and DTS
Sync in MPEG is handled at the packet layer (PES), with the SCR/PCR, PTS and DTS field serving as instruments. The timing base of them is 90KHz (27MHz/300). They are not necessarily encoded for each video frame or audio presentation unit, but are only required to occur with intervals not exceeding 0.7s/700ms for periodic updating of the decoders' clocks, i.e., the maximal length of pack in PS is 0.7s. For B frames of video and audio packet, the PTS is equal to its DTS. In the case of I and P pictures only, they are the same too. In general, I and P frames of video have a reordering delay (until next I/P frame comes) between DTS and PTS. The PTS actually could be interpolated based on the above information.
* Sync Using A Master Stream
All of the media streams being decoded and displayed must have exactly one independent master. Each of the individual media display units must slave the timing of their operation to the master stream. The master stream may be chosen depending on the application. Whichever media stream is the master, all the media streams bu the master must slave the timing of their respective displays to the PTSs extracted from the master media stream.
Audio is always chosen to be the master in MPEG decoding. The audio stream will be played back continuously with the clock being continually updated to equal the PTS value of the audio unit. In particular, the STD clock is typically initialized to be equal to the value encoded in the first SCR/PCR field when it enters the decoder's buffer. Thereafter the audio decoder controls the STD clock by updating this clock with the PTS value (coarse sync without PLL, in constrast, fine sync would PLL 27MHz with the PTSs).
The other decoders simply use the audio-controlled clock to determine the correct time to present their decoded data, at the times when their PTS are equal to the current value of the clock. Therefore, if the sync is missed, video picture would be skipped or repeated but audio unit never.
Sync in MPEG is handled at the packet layer (PES), with the SCR/PCR, PTS and DTS field serving as instruments. The timing base of them is 90KHz (27MHz/300). They are not necessarily encoded for each video frame or audio presentation unit, but are only required to occur with intervals not exceeding 0.7s/700ms for periodic updating of the decoders' clocks, i.e., the maximal length of pack in PS is 0.7s. For B frames of video and audio packet, the PTS is equal to its DTS. In the case of I and P pictures only, they are the same too. In general, I and P frames of video have a reordering delay (until next I/P frame comes) between DTS and PTS. The PTS actually could be interpolated based on the above information.
* Sync Using A Master Stream
All of the media streams being decoded and displayed must have exactly one independent master. Each of the individual media display units must slave the timing of their operation to the master stream. The master stream may be chosen depending on the application. Whichever media stream is the master, all the media streams bu the master must slave the timing of their respective displays to the PTSs extracted from the master media stream.
Audio is always chosen to be the master in MPEG decoding. The audio stream will be played back continuously with the clock being continually updated to equal the PTS value of the audio unit. In particular, the STD clock is typically initialized to be equal to the value encoded in the first SCR/PCR field when it enters the decoder's buffer. Thereafter the audio decoder controls the STD clock by updating this clock with the PTS value (coarse sync without PLL, in constrast, fine sync would PLL 27MHz with the PTSs).
The other decoders simply use the audio-controlled clock to determine the correct time to present their decoded data, at the times when their PTS are equal to the current value of the clock. Therefore, if the sync is missed, video picture would be skipped or repeated but audio unit never.
Monday, September 3, 2007
Extern "C"
Extern "C"
* It is used for C/C++ mix programming. Two aspects it has:
- All the variables and functions it is with are extern
- All of these are compiled and linked with C methods
* C and C++ Object Name
- Functions and variables in C are identified by their names
- Functions and variables in C++ are identified by their name, input arguments, return value and class name associated, etc. by combined, due to the overloading and other features in C++.
* Usage
It is only used in C++ header file and can not be included in C files.
- When C++ uses C header files, use the following in the C++ header file:
extern "C"
{
#include "xxx.h"
}
The C++ files must include this header file instead of using extern directly for C variables and functions.
- When C uses C++ header files, use extern instead of including the C++ header file:
cppfile.h:
extern "C"
{
void xxx(void);
}
cfile.c
extern void xxx(void);
* _cplusplus
In order to share this header file by C and C++, the macro _cplusplus is used to wrap the extern "C":
#ifdef _cplusplus
extern "C"{
#endif
... ... ...
#ifdef _cplusplus
}
#endif
* It is used for C/C++ mix programming. Two aspects it has:
- All the variables and functions it is with are extern
- All of these are compiled and linked with C methods
* C and C++ Object Name
- Functions and variables in C are identified by their names
- Functions and variables in C++ are identified by their name, input arguments, return value and class name associated, etc. by combined, due to the overloading and other features in C++.
* Usage
It is only used in C++ header file and can not be included in C files.
- When C++ uses C header files, use the following in the C++ header file:
extern "C"
{
#include "xxx.h"
}
The C++ files must include this header file instead of using extern directly for C variables and functions.
- When C uses C++ header files, use extern instead of including the C++ header file:
cppfile.h:
extern "C"
{
void xxx(void);
}
cfile.c
extern void xxx(void);
* _cplusplus
In order to share this header file by C and C++, the macro _cplusplus is used to wrap the extern "C":
#ifdef _cplusplus
extern "C"{
#endif
... ... ...
#ifdef _cplusplus
}
#endif
Sunday, September 2, 2007
Abstraction Relationship
* Three Relationships In General
- is-a
The public inheritance. Derived class is a special base class and could be used in any circumstances of base class. This is the key point of dynamic binding. On the contrary, base class is not derived class.
- has-a
The composite implementation with the handles to composite objects.
- use-a
Two classes interact at some time instant. No private inheritance implementation and use composite implementation with the handles to used objects.
* Has-a and Usa-a
It is difficult to distinguish these two relationships from the coding since it is generally using the handles to implement them. For has-a, the master class has the responsibility to create, maintain and delete its composite object. For use-a, the useful object might be shared with others. The setting of handles to comp might be these:
- Has-a
{ delete comp; comp = newcomp; }
{ delete comp; comp = newcomp->clone(); }
- Use-a
{ comp = newcomp; }
- is-a
The public inheritance. Derived class is a special base class and could be used in any circumstances of base class. This is the key point of dynamic binding. On the contrary, base class is not derived class.
- has-a
The composite implementation with the handles to composite objects.
- use-a
Two classes interact at some time instant. No private inheritance implementation and use composite implementation with the handles to used objects.
* Has-a and Usa-a
It is difficult to distinguish these two relationships from the coding since it is generally using the handles to implement them. For has-a, the master class has the responsibility to create, maintain and delete its composite object. For use-a, the useful object might be shared with others. The setting of handles to comp might be these:
- Has-a
{ delete comp; comp = newcomp; }
{ delete comp; comp = newcomp->clone(); }
- Use-a
{ comp = newcomp; }
C++ Dynamic Binding
* C++ Dynamic Binding
- Implemented by public inheritance and virtual functions
- Base and derived classes: general and special
- Base class must have one virtual function at least and it is the destructor. This affects the following two points.
- Virtual pointer to the virtual function table and its implementation in the derivation.
- Conversion/casting between base class object and derived class object.
- Public inheritance preferred. Use composite instead of private inheritance. No protected inheritance.
- Distinguish function overload, override, and hidden.
* Inheritance
- Base class consists of public interface (public accessibility) and private interface for derived classes (public and protected accessibility)
- Pure virtual function allows only interface without implementation for derived class.
- Virtual function allows interface with default implementation for derived class.
- Non-virtual function allows interface with mandatory implementation for derived class.
* Virtual Function
- Virtual function can not be static
- Redefine all the overloaded virtual functions
- No default arguments for virtual functions
- No virtual copy and assignment operator
- No virtual function calling in the constructor and destructor
* Abstract Class and Virtual Base Class
- Implemented by public inheritance and virtual functions
- Base and derived classes: general and special
- Base class must have one virtual function at least and it is the destructor. This affects the following two points.
- Virtual pointer to the virtual function table and its implementation in the derivation.
- Conversion/casting between base class object and derived class object.
- Public inheritance preferred. Use composite instead of private inheritance. No protected inheritance.
- Distinguish function overload, override, and hidden.
* Inheritance
- Base class consists of public interface (public accessibility) and private interface for derived classes (public and protected accessibility)
- Pure virtual function allows only interface without implementation for derived class.
- Virtual function allows interface with default implementation for derived class.
- Non-virtual function allows interface with mandatory implementation for derived class.
* Virtual Function
- Virtual function can not be static
- Redefine all the overloaded virtual functions
- No default arguments for virtual functions
- No virtual copy and assignment operator
- No virtual function calling in the constructor and destructor
* Abstract Class and Virtual Base Class
C++ Data Abstraction
* Abstract Data Type (class and object)
- Public interface
- Private implementation and private interface for derived classes
* Class
The following is very important for the abstract data type. They might be generated by compiler and could not be derived (not be virtual except destructor). (Note another one which can not be derived is the hidden data member or member function.)
- Constructor
1) Use initialization list in the constructor as much as possible to improve initialization efficiency. Const and reference must be put in the list while static and array member must not. Base class, const, reference and object members must be initialized.
2) Note the consistent order of member initialization.
3) Constructor with only one input or default inputs performs implicit casting.
4) Direct initialization instead of copy initialization, for example,
X a(10);
X a = X(10);
x a = 10;
- Destructor
1) If the class is designed for being derived, destructor must be virtual to allow the correct destructor to be called with dynamic binding and uniform data type mapping in memory. If not, do not declare it as virtual to save memory.
2) Even the destructor is pure virtual function, it still needs to be defined and it is allowed.
- Copy constructor
1) If some handle to object/memory outside the object is contained, the copy constructor must be redefined.
2) Each member must be copied explicitly in the copy constructor, esp. the base class.
3) The standard format for copy constructor
X(X const &x)
4) Put it in the private area without new definition to avoid use it illegally.
- Assignment operator
Note the difference of initialization and assignment.
1) If some handle to object/memory outside the object is contained, the assignment operator must be redefined. Delete the original memory allocation and reallocate and assign it.
2) The self assignment must be checked.
if (this != that) ...
3) Each member must be assigned explicitly in the assignment operator, esp. calling the assignment operator of base class.
B::operator =(that);
4) The standard format for assignment operator
X const &operator=(X const &x)
5) Put it in the private area without new definition to avoid use it illegally.
- Public interface
- Private implementation and private interface for derived classes
* Class
The following is very important for the abstract data type. They might be generated by compiler and could not be derived (not be virtual except destructor). (Note another one which can not be derived is the hidden data member or member function.)
- Constructor
1) Use initialization list in the constructor as much as possible to improve initialization efficiency. Const and reference must be put in the list while static and array member must not. Base class, const, reference and object members must be initialized.
2) Note the consistent order of member initialization.
3) Constructor with only one input or default inputs performs implicit casting.
4) Direct initialization instead of copy initialization, for example,
X a(10);
X a = X(10);
x a = 10;
- Destructor
1) If the class is designed for being derived, destructor must be virtual to allow the correct destructor to be called with dynamic binding and uniform data type mapping in memory. If not, do not declare it as virtual to save memory.
2) Even the destructor is pure virtual function, it still needs to be defined and it is allowed.
- Copy constructor
1) If some handle to object/memory outside the object is contained, the copy constructor must be redefined.
2) Each member must be copied explicitly in the copy constructor, esp. the base class.
3) The standard format for copy constructor
X(X const &x)
4) Put it in the private area without new definition to avoid use it illegally.
- Assignment operator
Note the difference of initialization and assignment.
1) If some handle to object/memory outside the object is contained, the assignment operator must be redefined. Delete the original memory allocation and reallocate and assign it.
2) The self assignment must be checked.
if (this != that) ...
3) Each member must be assigned explicitly in the assignment operator, esp. calling the assignment operator of base class.
B::operator =(that);
4) The standard format for assignment operator
X const &operator=(X const &x)
5) Put it in the private area without new definition to avoid use it illegally.
Subscribe to:
Posts (Atom)
