1 \section{Dynamic Structures}
7 \cvclass{CvMemStorage}\label{CvMemStorage}
8 Growing memory storage.
11 typedef struct CvMemStorage
13 struct CvMemBlock* bottom;/* first allocated block */
14 struct CvMemBlock* top; /* the current memory block - top of the stack */
15 struct CvMemStorage* parent; /* borrows new blocks from */
16 int block\_size; /* block size */
17 int free\_space; /* free space in the \texttt{top} block (in bytes) */
21 Memory storage is a low-level structure used to store dynamicly growing
22 data structures such as sequences, contours, graphs, subdivisions, etc. It
23 is organized as a list of memory blocks of equal size - \texttt{bottom}
24 field is the beginning of the list of blocks and \texttt{top} is the
25 currently used block, but not necessarily the last block of the list. All
26 blocks between \texttt{bottom} and \texttt{top}, not including the
27 latter, are considered fully occupied; all blocks between \texttt{top}
28 and the last block, not including \texttt{top}, are considered free
29 and \texttt{top} itself is partly ocupied - \texttt{free\_space}
30 contains the number of free bytes left in the end of \texttt{top}.
32 A new memory buffer that may be allocated explicitly by
33 \cvCPyCross{MemStorageAlloc} function or implicitly by higher-level functions,
34 such as \cvCPyCross{SeqPush}, \cvCPyCross{GraphAddEdge}, etc., \texttt{always}
35 starts in the end of the current block if it fits there. After allocation,
36 \texttt{free\_space} is decremented by the size of the allocated buffer
37 plus some padding to keep the proper alignment. When the allocated buffer
38 does not fit into the available portion of \texttt{top}, the next storage
39 block from the list is taken as \texttt{top} and \texttt{free\_space}
40 is reset to the whole block size prior to the allocation.
42 If there are no more free blocks, a new block is allocated (or borrowed
43 from the parent, see \cvCPyCross{CreateChildMemStorage}) and added to the end of
44 list. Thus, the storage behaves as a stack with \texttt{bottom} indicating
45 bottom of the stack and the pair (\texttt{top}, \texttt{free\_space})
46 indicating top of the stack. The stack top may be saved via
47 \cvCPyCross{SaveMemStoragePos}, restored via \cvCPyCross{RestoreMemStoragePos},
48 or reset via \cvCPyCross{ClearStorage}.
50 \cvclass{CvMemBlock}\label{CvMemBlock}
54 typedef struct CvMemBlock
56 struct CvMemBlock* prev;
57 struct CvMemBlock* next;
61 The structure \cross{CvMemBlock} represents a single block of memory
62 storage. The actual data in the memory blocks follows the header, that is,
63 the $i_{th}$ byte of the memory block can be retrieved with the expression
64 \texttt{((char*)(mem\_block\_ptr+1))[i]}. However, there is normally no need
65 to access the storage structure fields directly.
67 \cvclass{CvMemStoragePos}\label{CvMemStoragePos}
68 Memory storage position.
71 typedef struct CvMemStoragePos
78 The structure described above stores the position of the stack top that can be saved via \cvCPyCross{SaveMemStoragePos} and restored via \cvCPyCross{RestoreMemStoragePos}.
82 \cvclass{CvSeq}\label{CvSeq}
83 Growable sequence of elements.
86 Many OpenCV functions return a CvSeq object. The CvSeq obect is a sequence, so these are all legal:
88 seq = cv.FindContours(scribble, storage, cv.CV_RETR_CCOMP, cv.CV_CHAIN_APPROX_SIMPLE)
89 # seq is a sequence of point pairs
91 # FindContours returns a sequence of (x,y) points, so to print them out:
94 print seq[10] # tenth entry in the seqeuence
95 print seq[::-1] # reversed sequence
96 print sorted(list(seq)) # sorted sequence
99 Also, a CvSeq object has methods
102 \texttt{v\_next()} and
104 Some OpenCV functions (for example \cvCPyCross{FindContours}) can return multiple CvSeq objects, connected by these relations.
105 In this case the methods return the other sequences. If no relation between sequences exists, then the methods return \texttt{None}.
112 #define CV_SEQUENCE\_FIELDS() \
113 int flags; /* micsellaneous flags */ \
114 int header_size; /* size of sequence header */ \
115 struct CvSeq* h_prev; /* previous sequence */ \
116 struct CvSeq* h_next; /* next sequence */ \
117 struct CvSeq* v_prev; /* 2nd previous sequence */ \
118 struct CvSeq* v_next; /* 2nd next sequence */ \
119 int total; /* total number of elements */ \
120 int elem_size;/* size of sequence element in bytes */ \
121 char* block_max;/* maximal bound of the last block */ \
122 char* ptr; /* current write pointer */ \
123 int delta_elems; /* how many elements allocated when the sequence grows
124 (sequence granularity) */ \
125 CvMemStorage* storage; /* where the seq is stored */ \
126 CvSeqBlock* free_blocks; /* free blocks list */ \
127 CvSeqBlock* first; /* pointer to the first sequence block */
136 The structure \cross{CvSeq} is a base for all of OpenCV dynamic data structures.
138 Such an unusual definition via a helper macro simplifies the extension
139 of the structure \cross{CvSeq} with additional parameters. To extend
140 \cross{CvSeq} the user may define a new structure and put user-defined
141 fields after all \cross{CvSeq} fields that are included via the macro
142 \texttt{CV\_SEQUENCE\_FIELDS()}.
144 There are two types of sequences - dense and sparse. The base type for dense
145 sequences is \cross{CvSeq} and such sequences are used to represent
146 growable 1d arrays - vectors, stacks, queues, and deques. They have no gaps
147 in the middle - if an element is removed from the middle or inserted
148 into the middle of the sequence, the elements from the closer end are
149 shifted. Sparse sequences have \cross{CvSet} as a base class and they are
150 discussed later in more detail. They are sequences of nodes; each may be either occupied or free as indicated by the node flag. Such
151 sequences are used for unordered data structures such as sets of elements,
152 graphs, hash tables and so forth.
154 The field \texttt{header\_size} contains the actual size of the sequence
155 header and should be greater than or equal to \texttt{sizeof(CvSeq)}.
158 \texttt{h\_prev}, \texttt{h\_next}, \texttt{v\_prev}, \texttt{v\_next}
159 can be used to create hierarchical structures from separate sequences. The
160 fields \texttt{h\_prev} and \texttt{h\_next} point to the previous and
161 the next sequences on the same hierarchical level, while the fields
162 \texttt{v\_prev} and \texttt{v\_next} point to the previous and the
163 next sequences in the vertical direction, that is, the parent and its first
164 child. But these are just names and the pointers can be used in a
167 The field \texttt{first} points to the first sequence block, whose structure is described below.
169 The field \texttt{total} contains the actual number of dense sequence elements and number of allocated nodes in a sparse sequence.
171 The field \texttt{flags} contains the particular dynamic type
172 signature (\texttt{CV\_SEQ\_MAGIC\_VAL} for dense sequences and
173 \texttt{CV\_SET\_MAGIC\_VAL} for sparse sequences) in the highest 16
174 bits and miscellaneous information about the sequence. The lowest
175 \texttt{CV\_SEQ\_ELTYPE\_BITS} bits contain the ID of the element
176 type. Most of sequence processing functions do not use element type but rather
177 element size stored in \texttt{elem\_size}. If a sequence contains the
178 numeric data for one of the \cross{CvMat} type then the element type matches
179 to the corresponding \cross{CvMat} element type, e.g., \texttt{CV\_32SC2} may be
180 used for a sequence of 2D points, \texttt{CV\_32FC1} for sequences of floating-point
181 values, etc. A \texttt{CV\_SEQ\_ELTYPE(seq\_header\_ptr)} macro retrieves the
182 type of sequence elements. Processing functions that work with numerical
183 sequences check that \texttt{elem\_size} is equal to that calculated from
184 the type element size. Besides \cross{CvMat} compatible types, there
185 are few extra element types defined in the \texttt{cvtypes.h} header:
187 Standard Types of Sequence Elements
191 #define CV_SEQ_ELTYPE_POINT CV_32SC2 /* (x,y) */
192 #define CV_SEQ_ELTYPE_CODE CV_8UC1 /* freeman code: 0..7 */
193 #define CV_SEQ_ELTYPE_GENERIC 0 /* unspecified type of
195 #define CV_SEQ_ELTYPE_PTR CV_USRTYPE1 /* =6 */
196 #define CV_SEQ_ELTYPE_PPOINT CV_SEQ_ELTYPE_PTR /* &elem: pointer to
197 element of other sequence */
198 #define CV_SEQ_ELTYPE_INDEX CV_32SC1 /* #elem: index of element of
199 some other sequence */
200 #define CV_SEQ_ELTYPE_GRAPH_EDGE CV_SEQ_ELTYPE_GENERIC /* &next_o,
201 &next_d, &vtx_o, &vtx_d */
202 #define CV_SEQ_ELTYPE_GRAPH_VERTEX CV_SEQ_ELTYPE_GENERIC /* first_edge,
204 #define CV_SEQ_ELTYPE_TRIAN_ATR CV_SEQ_ELTYPE_GENERIC /* vertex of the
206 #define CV_SEQ_ELTYPE_CONNECTED_COMP CV_SEQ_ELTYPE_GENERIC /* connected
208 #define CV_SEQ_ELTYPE_POINT3D CV_32FC3 /* (x,y,z) */
212 The next \texttt{CV\_SEQ\_KIND\_BITS} bits specify the kind of sequence:
214 Standard Kinds of Sequences
218 /* generic (unspecified) kind of sequence */
219 #define CV_SEQ_KIND_GENERIC (0 << CV_SEQ_ELTYPE_BITS)
221 /* dense sequence suntypes */
222 #define CV_SEQ_KIND_CURVE (1 << CV_SEQ_ELTYPE_BITS)
223 #define CV_SEQ_KIND_BIN_TREE (2 << CV_SEQ_ELTYPE_BITS)
225 /* sparse sequence (or set) subtypes */
226 #define CV_SEQ_KIND_GRAPH (3 << CV_SEQ_ELTYPE_BITS)
227 #define CV_SEQ_KIND_SUBDIV2D (4 << CV_SEQ_ELTYPE_BITS)
231 The remaining bits are used to identify different features specific
232 to certain sequence kinds and element types. For example, curves
233 made of points \texttt{(CV\_SEQ\_KIND\_CURVE|CV\_SEQ\_ELTYPE\_POINT)},
234 together with the flag \texttt{CV\_SEQ\_FLAG\_CLOSED}, belong to the
235 type \texttt{CV\_SEQ\_POLYGON} or, if other flags are used, to its
236 subtype. Many contour processing functions check the type of the input
237 sequence and report an error if they do not support this type. The
238 file \texttt{cvtypes.h} stores the complete list of all supported
239 predefined sequence types and helper macros designed to get the sequence
240 type of other properties. The definition of the building
241 blocks of sequences can be found below.
243 \cvclass{CvSeqBlock}\label{CvSeqBlock}
245 Continuous sequence block.
249 typedef struct CvSeqBlock
251 struct CvSeqBlock* prev; /* previous sequence block */
252 struct CvSeqBlock* next; /* next sequence block */
253 int start_index; /* index of the first element in the block +
254 sequence->first->start_index */
255 int count; /* number of elements in the block */
256 char* data; /* pointer to the first element of the block */
261 Sequence blocks make up a circular double-linked list, so the pointers
262 \texttt{prev} and \texttt{next} are never \texttt{NULL} and point to the
263 previous and the next sequence blocks within the sequence. It means that
264 \texttt{next} of the last block is the first block and \texttt{prev} of
265 the first block is the last block. The fields \texttt{startIndex} and
266 \texttt{count} help to track the block location within the sequence. For
267 example, if the sequence consists of 10 elements and splits into three
268 blocks of 3, 5, and 2 elements, and the first block has the parameter
269 \texttt{startIndex = 2}, then pairs \texttt{(startIndex, count)} for the sequence
271 (2,3), (5, 5), and (10, 2)
272 correspondingly. The parameter
273 \texttt{startIndex} of the first block is usually \texttt{0} unless
274 some elements have been inserted at the beginning of the sequence.
276 \cvclass{CvSlice}\label{CvSlice}
280 typedef struct CvSlice
286 inline CvSlice cvSlice( int start, int end );
287 #define CV_WHOLE_SEQ_END_INDEX 0x3fffffff
288 #define CV_WHOLE_SEQ cvSlice(0, CV_WHOLE_SEQ_END_INDEX)
290 /* calculates the sequence slice length */
291 int cvSliceLength( CvSlice slice, const CvSeq* seq );
294 Some of functions that operate on sequences take a \texttt{CvSlice slice}
295 parameter that is often set to the whole sequence (CV\_WHOLE\_SEQ) by
296 default. Either of the \texttt{startIndex} and \texttt{endIndex}
297 may be negative or exceed the sequence length, \texttt{startIndex} is
298 inclusive, and \texttt{endIndex} is an exclusive boundary. If they are equal,
299 the slice is considered empty (i.e., contains no elements). Because
300 sequences are treated as circular structures, the slice may select a
301 few elements in the end of a sequence followed by a few elements at the
302 beginning of the sequence. For example, \texttt{cvSlice(-2, 3)} in the case of
303 a 10-element sequence will select a 5-element slice, containing the pre-last
304 (8th), last (9th), the very first (0th), second (1th) and third (2nd)
305 elements. The functions normalize the slice argument in the following way:
306 first, \cvCPyCross{SliceLength} is called to determine the length of the slice,
307 then, \texttt{startIndex} of the slice is normalized similarly to the
308 argument of \cvCPyCross{GetSeqElem} (i.e., negative indices are allowed). The
309 actual slice to process starts at the normalized \texttt{startIndex}
310 and lasts \cvCPyCross{SliceLength} elements (again, assuming the sequence is
311 a circular structure).
313 If a function does not accept a slice argument, but you want to process
314 only a part of the sequence, the sub-sequence may be extracted
315 using the \cvCPyCross{SeqSlice} function, or stored into a continuous
316 buffer with \cross{CvtSeqToArray} (optionally, followed by
317 \cvCPyCross{MakeSeqHeaderForArray}).
321 \cvclass{CvSet}\label{CvSet}
325 Some OpenCV functions return a CvSet object. The CvSet obect is iterable, for example:
338 typedef struct CvSetElem
340 int flags; /* it is negative if the node is free and zero or positive otherwise */
341 struct CvSetElem* next_free; /* if the node is free, the field is a
342 pointer to next free node */
346 #define CV_SET_FIELDS() \
347 CV_SEQUENCE_FIELDS() /* inherits from [#CvSeq CvSeq] */ \
348 struct CvSetElem* free_elems; /* list of free nodes */
356 The structure \cross{CvSet} is a base for OpenCV sparse data structures.
358 As follows from the above declaration, \cross{CvSet} inherits from
359 \cross{CvSeq} and it adds the \texttt{free\_elems} field, which
360 is a list of free nodes, to it. Every set node, whether free or not, is an
361 element of the underlying sequence. While there are no restrictions on
362 elements of dense sequences, the set (and derived structures) elements
363 must start with an integer field and be able to fit CvSetElem structure,
364 because these two fields (an integer followed by a pointer) are required
365 for the organization of a node set with the list of free nodes. If a node is
366 free, the \texttt{flags} field is negative (the most-significant bit, or
367 MSB, of the field is set), and the \texttt{next\_free} points to the next
368 free node (the first free node is referenced by the \texttt{free\_elems}
369 field of \cross{CvSet}). And if a node is occupied, the \texttt{flags} field
370 is positive and contains the node index that may be retrieved using the
371 (\texttt{set\_elem->flags \& CV\_SET\_ELEM\_IDX\_MASK}) expressions, the rest of
372 the node content is determined by the user. In particular, the occupied
373 nodes are not linked as the free nodes are, so the second field can be
374 used for such a link as well as for some different purpose. The macro
375 \texttt{CV\_IS\_SET\_ELEM(set\_elem\_ptr)} can be used to determined whether
376 the specified node is occupied or not.
378 Initially the set and the list are empty. When a new node is requested
379 from the set, it is taken from the list of free nodes, which is then updated. If the list appears to be empty, a new sequence block is allocated
380 and all the nodes within the block are joined in the list of free
381 nodes. Thus, the \texttt{total} field of the set is the total number of nodes
382 both occupied and free. When an occupied node is released, it is added
383 to the list of free nodes. The node released last will be occupied first.
385 In OpenCV \cross{CvSet} is used for representing graphs (\cross{CvGraph}),
386 sparse multi-dimensional arrays (\cross{CvSparseMat}), and planar subdivisions
390 \cvclass{CvGraph}\label{CvGraph}
391 Oriented or unoriented weighted graph.
394 #define CV_GRAPH_VERTEX_FIELDS() \
395 int flags; /* vertex flags */ \
396 struct CvGraphEdge* first; /* the first incident edge */
398 typedef struct CvGraphVtx
400 CV_GRAPH_VERTEX_FIELDS()
404 #define CV_GRAPH_EDGE_FIELDS() \
405 int flags; /* edge flags */ \
406 float weight; /* edge weight */ \
407 struct CvGraphEdge* next[2]; /* the next edges in the incidence lists for staring (0) */ \
408 /* and ending (1) vertices */ \
409 struct CvGraphVtx* vtx[2]; /* the starting (0) and ending (1) vertices */
411 typedef struct CvGraphEdge
413 CV_GRAPH_EDGE_FIELDS()
417 #define CV_GRAPH_FIELDS() \
418 CV_SET_FIELDS() /* set of vertices */ \
419 CvSet* edges; /* set of edges */
421 typedef struct CvGraph
429 The structure \cross{CvGraph} is a base for graphs used in OpenCV.
431 The graph structure inherits from \cross{CvSet} - which describes common graph properties and the graph vertices, and contains another set as a member - which describes the graph edges.
433 The vertex, edge, and the graph header structures are declared using the
434 same technique as other extendible OpenCV structures - via macros, which
435 simplify extension and customization of the structures. While the vertex
436 and edge structures do not inherit from \cross{CvSetElem} explicitly, they
437 satisfy both conditions of the set elements: having an integer field in
438 the beginning and fitting within the CvSetElem structure. The \texttt{flags} fields are
439 used as for indicating occupied vertices and edges as well as for other
440 purposes, for example, for graph traversal (see \cvCPyCross{CreateGraphScanner}
441 et al.), so it is better not to use them directly.
443 The graph is represented as a set of edges each of which has a list of
444 incident edges. The incidence lists for different vertices are interleaved
445 to avoid information duplication as much as posssible.
447 The graph may be oriented or unoriented. In the latter case there is no
448 distiction between the edge connecting vertex $A$ with vertex $B$ and the edge
449 connecting vertex $B$ with vertex $A$ - only one of them can exist in the
450 graph at the same moment and it represents both $A \rightarrow B$ and
451 $B \rightarrow A$ edges.
453 \cvclass{CvGraphScanner}\label{CvGraphScanner}
454 Graph traversal state.
457 typedef struct CvGraphScanner
459 CvGraphVtx* vtx; /* current graph vertex (or current edge origin) */
460 CvGraphVtx* dst; /* current graph edge destination vertex */
461 CvGraphEdge* edge; /* current edge */
463 CvGraph* graph; /* the graph */
464 CvSeq* stack; /* the graph vertex stack */
465 int index; /* the lower bound of certainly visited vertices */
466 int mask; /* event mask */
472 The structure \cross{CvGraphScanner} is used for depth-first graph traversal. See discussion of the functions below.
474 \cvmacro{CV\_TREE\_NODE\_FIELDS}\label{CV_TREE_NODE_FIELDS}
475 Helper macro for a tree node type declaration.
477 The macro \texttt{CV\_TREE\_NODE\_FIELDS()} is used to declare structures
478 that can be organized into hierarchical strucutures (trees), such as
479 \cross{CvSeq} - the basic type for all dynamic structures. The trees
480 created with nodes declared using this macro can be processed using the
481 functions described below in this section.
483 \cvclass{CvTreeNodeIterator}\label{CvTreeNodeIterator}
484 Opens existing or creates new file storage.
487 typedef struct CvTreeNodeIterator
497 #define CV_TREE_NODE_FIELDS(node_type) \
498 int flags; /* micsellaneous flags */ \
499 int header_size; /* size of sequence header */ \
500 struct node_type* h_prev; /* previous sequence */ \
501 struct node_type* h_next; /* next sequence */ \
502 struct node_type* v_prev; /* 2nd previous sequence */ \
503 struct node_type* v_next; /* 2nd next sequence */
507 The structure \cross{CvTreeNodeIterator} is used to traverse trees. Each tree node should start with the certain fields which are defined by \texttt{CV\_TREE\_NODE\_FIELDS(...)} macro. In C++ terms, each tree node should be a structure "derived" from
512 CV_TREE_NODE_FIELDS(_BaseTreeNode);
516 \texttt{CvSeq}, \texttt{CvSet}, \texttt{CvGraph} and other dynamic structures derived from \texttt{CvSeq} comply with the requirement.
518 \cvCPyFunc{ClearGraph}
522 void cvClearGraph( CvGraph* graph );
529 The function removes all vertices and edges from a graph. The function has O(1) time complexity.
531 \cvCPyFunc{ClearMemStorage}
532 Clears memory storage.
534 \cvdefC{void cvClearMemStorage( CvMemStorage* storage );}
537 \cvarg{storage}{Memory storage}
540 The function resets the top (free space
541 boundary) of the storage to the very beginning. This function does not
542 deallocate any memory. If the storage has a parent, the function returns
543 all blocks to the parent.
548 \cvdefC{void cvClearSeq( CvSeq* seq );}
549 \cvdefPy{ClearSeq(seq)-> None}
552 \cvarg{seq}{Sequence}
555 The function removes all elements from a
556 sequence. The function does not return the memory to the storage block, but this
557 memory is reused later when new elements are added to the sequence. The function has
558 'O(1)' time complexity.
564 \cvdefC{void cvClearSet( CvSet* setHeader );}
567 \cvarg{setHeader}{Cleared set}
571 The function removes all elements from set. It has O(1) time complexity.
574 \cvCPyFunc{CloneGraph}
577 \cvdefC{CvGraph* cvCloneGraph( \par const CvGraph* graph,\par CvMemStorage* storage );}
580 \cvarg{graph}{The graph to copy}
581 \cvarg{storage}{Container for the copy}
585 The function creates a full copy of the specified graph. If the
586 graph vertices or edges have pointers to some external data, it can still be
587 shared between the copies. The vertex and edge indices in the new graph
588 may be different from the original because the function defragments
589 the vertex and edge sets.
594 Creates a copy of a sequence.
596 \cvdefC{CvSeq* cvCloneSeq( \par const CvSeq* seq,\par CvMemStorage* storage=NULL );}
597 \cvdefPy{CloneSeq(seq,storage)-> None}
600 \cvarg{seq}{Sequence}
601 \cvarg{storage}{The destination storage block to hold the new sequence header and the copied data, if any. If it is NULL, the function uses the storage block containing the input sequence.}
604 The function makes a complete copy of the input sequence and returns it.
609 cvCloneSeq( seq, storage )
615 cvSeqSlice( seq, CV_WHOLE_SEQ, storage, 1 )
618 \cvCPyFunc{CreateChildMemStorage}
619 Creates child memory storage.
621 \cvdefC{CvMemStorage* cvCreateChildMemStorage(CvMemStorage* parent);}
624 \cvarg{parent}{Parent memory storage}
627 The function creates a child memory
628 storage that is similar to simple memory storage except for the
629 differences in the memory allocation/deallocation mechanism. When a
630 child storage needs a new block to add to the block list, it tries
631 to get this block from the parent. The first unoccupied parent block
632 available is taken and excluded from the parent block list. If no blocks
633 are available, the parent either allocates a block or borrows one from
634 its own parent, if any. In other words, the chain, or a more complex
635 structure, of memory storages where every storage is a child/parent of
636 another is possible. When a child storage is released or even cleared,
637 it returns all blocks to the parent. In other aspects, child storage
638 is the same as simple storage.
640 Child storage is useful in the following situation. Imagine
641 that the user needs to process dynamic data residing in a given storage area and
642 put the result back to that same storage area. With the simplest approach,
643 when temporary data is resided in the same storage area as the input and
644 output data, the storage area will look as follows after processing:
646 Dynamic data processing without using child storage
648 \includegraphics[width=0.5\textwidth]{pics/memstorage1.png}
650 That is, garbage appears in the middle of the storage. However, if
651 one creates a child memory storage at the beginning of processing,
652 writes temporary data there, and releases the child storage at the end,
653 no garbage will appear in the source/destination storage:
655 Dynamic data processing using a child storage
657 \includegraphics[width=0.5\textwidth]{pics/memstorage2.png}
659 \cvCPyFunc{CreateGraph}
660 Creates an empty graph.
662 \cvdefC{CvGraph* cvCreateGraph( \par int graph\_flags,\par int header\_size,\par int vtx\_size,\par int edge\_size,\par CvMemStorage* storage );}
665 \cvarg{graph\_flags}{Type of the created graph. Usually, it is either \texttt{CV\_SEQ\_KIND\_GRAPH} for generic unoriented graphs and
666 \texttt{CV\_SEQ\_KIND\_GRAPH | CV\_GRAPH\_FLAG\_ORIENTED} for generic oriented graphs.}
667 \cvarg{header\_size}{Graph header size; may not be less than \texttt{sizeof(CvGraph)}}
668 \cvarg{vtx\_size}{Graph vertex size; the custom vertex structure must start with \cross{CvGraphVtx} (use \texttt{CV\_GRAPH\_VERTEX\_FIELDS()})}
669 \cvarg{edge\_size}{Graph edge size; the custom edge structure must start with \cross{CvGraphEdge} (use \texttt{CV\_GRAPH\_EDGE\_FIELDS()})}
670 \cvarg{storage}{The graph container}
673 The function creates an empty graph and returns a pointer to it.
675 \cvCPyFunc{CreateGraphScanner}
676 Creates structure for depth-first graph traversal.
679 CvGraphScanner* cvCreateGraphScanner( \par CvGraph* graph,\par CvGraphVtx* vtx=NULL,\par int mask=CV\_GRAPH\_ALL\_ITEMS );
684 \cvarg{vtx}{Initial vertex to start from. If NULL, the traversal starts from the first vertex (a vertex with the minimal index in the sequence of vertices).}
685 \cvarg{mask}{Event mask indicating which events are of interest to the user (where \cvCPyCross{NextGraphItem} function returns control to the user) It can be \texttt{CV\_GRAPH\_ALL\_ITEMS} (all events are of interest) or a combination of the following flags:
688 \cvarg{CV\_GRAPH\_VERTEX}{stop at the graph vertices visited for the first time}
689 \cvarg{CV\_GRAPH\_TREE\_EDGE}{stop at tree edges (\texttt{tree edge} is the edge connecting the last visited vertex and the vertex to be visited next)}
690 \cvarg{CV\_GRAPH\_BACK\_EDGE}{stop at back edges (\texttt{back edge} is an edge connecting the last visited vertex with some of its ancestors in the search tree)}
691 \cvarg{CV\_GRAPH\_FORWARD\_EDGE}{stop at forward edges (\texttt{forward edge} is an edge conecting the last visited vertex with some of its descendants in the search tree. The forward edges are only possible during oriented graph traversal)}
692 \cvarg{CV\_GRAPH\_CROSS\_EDGE}{stop at cross edges (\texttt{cross edge} is an edge connecting different search trees or branches of the same tree. The \texttt{cross edges} are only possible during oriented graph traversal)}
693 \cvarg{CV\_GRAPH\_ANY\_EDGE}{stop at any edge (\texttt{tree, back, forward}, and \texttt{cross edges})}
694 \cvarg{CV\_GRAPH\_NEW\_TREE}{stop in the beginning of every new search tree. When the traversal procedure visits all vertices and edges reachable from the initial vertex (the visited vertices together with tree edges make up a tree), it searches for some unvisited vertex in the graph and resumes the traversal process from that vertex. Before starting a new tree (including the very first tree when \texttt{cvNextGraphItem} is called for the first time) it generates a \texttt{CV\_GRAPH\_NEW\_TREE} event. For unoriented graphs, each search tree corresponds to a connected component of the graph.}
695 \cvarg{CV\_GRAPH\_BACKTRACKING}{stop at every already visited vertex during backtracking - returning to already visited vertexes of the traversal tree.}
699 The function creates a structure for depth-first graph traversal/search. The initialized structure is used in the \cvCPyCross{NextGraphItem} function - the incremental traversal procedure.
703 \cvCPyFunc{CreateMemStorage}
704 Creates memory storage.
706 \cvdefC{CvMemStorage* cvCreateMemStorage( int blockSize=0 );}
707 \cvdefPy{CreateMemStorage(blockSize = 0) -> memstorage}
710 \cvarg{blockSize}{Size of the storage blocks in bytes. If it is 0, the block size is set to a default value - currently it is about 64K.}
713 The function creates an empty memory storage. See \cross{CvMemStorage} description.
717 \cvCPyFunc{CreateSeq}
720 \cvdefC{CvSeq* cvCreateSeq( \par int seqFlags,\par int headerSize,\par int elemSize,\par CvMemStorage* storage);}
723 \cvarg{seqFlags}{Flags of the created sequence. If the sequence is not passed to any function working with a specific type of sequences, the sequence value may be set to 0, otherwise the appropriate type must be selected from the list of predefined sequence types.}
724 \cvarg{headerSize}{Size of the sequence header; must be greater than or equal to \texttt{sizeof(CvSeq)}. If a specific type or its extension is indicated, this type must fit the base type header.}
725 \cvarg{elemSize}{Size of the sequence elements in bytes. The size must be consistent with the sequence type. For example, for a sequence of points to be created, the element type \newline \texttt{CV\_SEQ\_ELTYPE\_POINT} should be specified and the parameter \texttt{elemSize} must be equal to \texttt{sizeof(CvPoint)}.}
726 \cvarg{storage}{Sequence location}
729 The function creates a sequence and returns
730 the pointer to it. The function allocates the sequence header in
731 the storage block as one continuous chunk and sets the structure
732 fields \texttt{flags}, \texttt{elemSize}, \texttt{headerSize}, and
733 \texttt{storage} to passed values, sets \texttt{delta\_elems} to the
734 default value (that may be reassigned using the \cvCPyCross{SetSeqBlockSize}
735 function), and clears other header fields, including the space following
736 the first \texttt{sizeof(CvSeq)} bytes.
738 \cvCPyFunc{CreateSet}
739 Creates an empty set.
741 \cvdefC{CvSet* cvCreateSet( \par int set\_flags,\par int header\_size,\par int elem\_size,\par CvMemStorage* storage );}
744 \cvarg{set\_flags}{Type of the created set}
745 \cvarg{header\_size}{Set header size; may not be less than \texttt{sizeof(CvSet)}}
746 \cvarg{elem\_size}{Set element size; may not be less than \cross{CvSetElem}}
747 \cvarg{storage}{Container for the set}
750 The function creates an empty set with a specified header size and element size, and returns the pointer to the set. This function is just a thin layer on top of \cvCPyCross{CreateSeq}.
752 \cvCPyFunc{CvtSeqToArray}
753 Copies a sequence to one continuous block of memory.
755 \cvdefC{void* cvCvtSeqToArray( \par const CvSeq* seq,\par void* elements,\par CvSlice slice=CV\_WHOLE\_SEQ );}
758 \cvarg{seq}{Sequence}
759 \cvarg{elements}{Pointer to the destination array that must be large enough. It should be a pointer to data, not a matrix header.}
760 \cvarg{slice}{The sequence portion to copy to the array}
763 The function copies the entire sequence or subsequence to the specified buffer and returns the pointer to the buffer.
765 \cvCPyFunc{EndWriteSeq}
766 Finishes the process of writing a sequence.
768 \cvdefC{CvSeq* cvEndWriteSeq( CvSeqWriter* writer );}
771 \cvarg{writer}{Writer state}
775 The function finishes the writing process and
776 returns the pointer to the written sequence. The function also truncates
777 the last incomplete sequence block to return the remaining part of the
778 block to memory storage. After that, the sequence can be read and
779 modified safely. See \cvCPyCross{cvStartWriteSeq} and \cvCPyCross{cvStartAppendToSeq}
781 \cvCPyFunc{FindGraphEdge}
782 Finds an edge in a graph.
785 CvGraphEdge* cvFindGraphEdge( const CvGraph* graph, int start\_idx, int end\_idx );
790 #define cvGraphFindEdge cvFindGraphEdge
796 \cvarg{start\_idx}{Index of the starting vertex of the edge}
797 \cvarg{end\_idx}{Index of the ending vertex of the edge. For an unoriented graph, the order of the vertex parameters does not matter.}
800 The function finds the graph edge connecting two specified vertices and returns a pointer to it or NULL if the edge does not exist.
802 \cvCPyFunc{FindGraphEdgeByPtr}
803 Finds an edge in a graph by using its pointer.
806 CvGraphEdge* cvFindGraphEdgeByPtr( \par const CvGraph* graph,\par const CvGraphVtx* startVtx,\par const CvGraphVtx* endVtx );
810 #define cvGraphFindEdgeByPtr cvFindGraphEdgeByPtr
815 \cvarg{startVtx}{Pointer to the starting vertex of the edge}
816 \cvarg{endVtx}{Pointer to the ending vertex of the edge. For an unoriented graph, the order of the vertex parameters does not matter.}
819 The function finds the graph edge connecting two specified vertices and returns pointer to it or NULL if the edge does not exists.
821 \cvCPyFunc{FlushSeqWriter}
822 Updates sequence headers from the writer.
824 \cvdefC{void cvFlushSeqWriter( CvSeqWriter* writer );}
827 \cvarg{writer}{Writer state}
830 The function is intended to enable the user to
831 read sequence elements, whenever required, during the writing process,
832 e.g., in order to check specific conditions. The function updates the
833 sequence headers to make reading from the sequence possible. The writer
834 is not closed, however, so that the writing process can be continued at
835 any time. If an algorithm requires frequent flushes, consider using
836 \cvCPyCross{SeqPush} instead.
838 \cvCPyFunc{GetGraphVtx}
839 Finds a graph vertex by using its index.
841 \cvdefC{CvGraphVtx* cvGetGraphVtx( \par CvGraph* graph,\par int vtx\_idx );}
845 \cvarg{vtx\_idx}{Index of the vertex}
849 The function finds the graph vertex by using its index and returns the pointer to it or NULL if the vertex does not belong to the graph.
852 \cvCPyFunc{GetSeqElem}
853 Returns a pointer to a sequence element according to its index.
855 \cvdefC{char* cvGetSeqElem( const CvSeq* seq, int index );}
858 #define CV_GET_SEQ_ELEM( TYPE, seq, index ) (TYPE*)cvGetSeqElem( (CvSeq*)(seq), (index) )
862 \cvarg{seq}{Sequence}
863 \cvarg{index}{Index of element}
866 The function finds the element with the given
867 index in the sequence and returns the pointer to it. If the element
868 is not found, the function returns 0. The function supports negative
869 indices, where -1 stands for the last sequence element, -2 stands for
870 the one before last, etc. If the sequence is most likely to consist of
871 a single sequence block or the desired element is likely to be located
872 in the first block, then the macro
873 \texttt{CV\_GET\_SEQ\_ELEM( elemType, seq, index )}
874 should be used, where the parameter \texttt{elemType} is the
875 type of sequence elements ( \cross{CvPoint} for example), the parameter
876 \texttt{seq} is a sequence, and the parameter \texttt{index} is the index
877 of the desired element. The macro checks first whether the desired element
878 belongs to the first block of the sequence and returns it if it does;
879 otherwise the macro calls the main function \texttt{GetSeqElem}. Negative
880 indices always cause the \cvCPyCross{GetSeqElem} call. The function has O(1)
881 time complexity assuming that the number of blocks is much smaller than the
884 \cvCPyFunc{GetSeqReaderPos}
885 Returns the current reader position.
887 \cvdefC{int cvGetSeqReaderPos( CvSeqReader* reader );}
890 \cvarg{reader}{Reader state}
894 The function returns the current reader position (within 0 ... \texttt{reader->seq->total} - 1).
896 \cvCPyFunc{GetSetElem}
897 Finds a set element by its index.
899 \cvdefC{CvSetElem* cvGetSetElem( \par const CvSet* setHeader,\par int index );}
902 \cvarg{setHeader}{Set}
903 \cvarg{index}{Index of the set element within a sequence}
906 The function finds a set element by its index. The function returns the pointer to it or 0 if the index is invalid or the corresponding node is free. The function supports negative indices as it uses \cvCPyCross{GetSeqElem} to locate the node.
908 \cvCPyFunc{GraphAddEdge}
909 Adds an edge to a graph.
911 \cvdefC{int cvGraphAddEdge( \par CvGraph* graph,\par int start\_idx,\par int end\_idx,\par const CvGraphEdge* edge=NULL,\par CvGraphEdge** inserted\_edge=NULL );
916 \cvarg{start\_idx}{Index of the starting vertex of the edge}
917 \cvarg{end\_idx}{Index of the ending vertex of the edge. For an unoriented graph, the order of the vertex parameters does not matter.}
918 \cvarg{edge}{Optional input parameter, initialization data for the edge}
919 \cvarg{inserted\_edge}{Optional output parameter to contain the address of the inserted edge}
923 The function connects two specified vertices. The function returns 1 if the edge has been added successfully, 0 if the edge connecting the two vertices exists already and -1 if either of the vertices was not found, the starting and the ending vertex are the same, or there is some other critical situation. In the latter case (i.e., when the result is negative), the function also reports an error by default.
925 \cvCPyFunc{GraphAddEdgeByPtr}
926 Adds an edge to a graph by using its pointer.
928 \cvdefC{int cvGraphAddEdgeByPtr( \par CvGraph* graph,\par CvGraphVtx* start\_vtx,\par CvGraphVtx* end\_vtx,\par const CvGraphEdge* edge=NULL,\par CvGraphEdge** inserted\_edge=NULL );}
932 \cvarg{start\_vtx}{Pointer to the starting vertex of the edge}
933 \cvarg{end\_vtx}{Pointer to the ending vertex of the edge. For an unoriented graph, the order of the vertex parameters does not matter.}
934 \cvarg{edge}{Optional input parameter, initialization data for the edge}
935 \cvarg{inserted\_edge}{Optional output parameter to contain the address of the inserted edge within the edge set}
938 The function connects two specified vertices. The
939 function returns 1 if the edge has been added successfully, 0 if the
940 edge connecting the two vertices exists already, and -1 if either of the
941 vertices was not found, the starting and the ending vertex are the same
942 or there is some other critical situation. In the latter case (i.e., when
943 the result is negative), the function also reports an error by default.
945 \cvCPyFunc{GraphAddVtx}
946 Adds a vertex to a graph.
949 int cvGraphAddVtx( \par CvGraph* graph,\par const CvGraphVtx* vtx=NULL,\par CvGraphVtx** inserted\_vtx=NULL );}
953 \cvarg{vtx}{Optional input argument used to initialize the added vertex (only user-defined fields beyond \texttt{sizeof(CvGraphVtx)} are copied)}
954 \cvarg{inserted\_vertex}{Optional output argument. If not \texttt{NULL}, the address of the new vertex is written here.}
957 The function adds a vertex to the graph and returns the vertex index.
959 \cvCPyFunc{GraphEdgeIdx}
960 Returns the index of a graph edge.
963 int cvGraphEdgeIdx( \par CvGraph* graph,\par CvGraphEdge* edge );
968 \cvarg{edge}{Pointer to the graph edge}
971 The function returns the index of a graph edge.
973 \cvCPyFunc{GraphRemoveEdge}
974 Removes an edge from a graph.
976 \cvdefC{void cvGraphRemoveEdge( \par CvGraph* graph,\par int start\_idx,\par int end\_idx );}
980 \cvarg{start\_idx}{Index of the starting vertex of the edge}
981 \cvarg{end\_idx}{Index of the ending vertex of the edge. For an unoriented graph, the order of the vertex parameters does not matter.}
984 The function removes the edge connecting two specified vertices. If the vertices are not connected [in that order], the function does nothing.
986 \cvCPyFunc{GraphRemoveEdgeByPtr}
988 Removes an edge from a graph by using its pointer.
990 \cvdefC{void cvGraphRemoveEdgeByPtr( \par CvGraph* graph,\par CvGraphVtx* start\_vtx,\par CvGraphVtx* end\_vtx );}
994 \cvarg{start\_vtx}{Pointer to the starting vertex of the edge}
995 \cvarg{end\_vtx}{Pointer to the ending vertex of the edge. For an unoriented graph, the order of the vertex parameters does not matter.}
998 The function removes the edge connecting two specified vertices. If the vertices are not connected [in that order], the function does nothing.
1000 \cvCPyFunc{GraphRemoveVtx}
1001 Removes a vertex from a graph.
1003 \cvdefC{int cvGraphRemoveVtx( \par CvGraph* graph,\par int index );}
1006 \cvarg{graph}{Graph}
1007 \cvarg{vtx\_idx}{Index of the removed vertex}
1010 The function removes a vertex from a graph
1011 together with all the edges incident to it. The function reports an error
1012 if the input vertex does not belong to the graph. The return value is the
1013 number of edges deleted, or -1 if the vertex does not belong to the graph.
1015 \cvCPyFunc{GraphRemoveVtxByPtr}
1016 Removes a vertex from a graph by using its pointer.
1018 \cvdefC{int cvGraphRemoveVtxByPtr( \par CvGraph* graph,\par CvGraphVtx* vtx );}
1021 \cvarg{graph}{Graph}
1022 \cvarg{vtx}{Pointer to the removed vertex}
1026 The function removes a vertex from the graph by using its pointer together with all the edges incident to it. The function reports an error if the vertex does not belong to the graph. The return value is the number of edges deleted, or -1 if the vertex does not belong to the graph.
1028 \cvCPyFunc{GraphVtxDegree}
1029 Counts the number of edges indicent to the vertex.
1032 int cvGraphVtxDegree( const CvGraph* graph, int vtxIdx );
1036 \cvarg{graph}{Graph}
1037 \cvarg{vtxIdx}{Index of the graph vertex}
1040 The function returns the number of edges incident to the specified vertex, both incoming and outgoing. To count the edges, the following code is used:
1043 CvGraphEdge* edge = vertex->first; int count = 0;
1046 edge = CV_NEXT_GRAPH_EDGE( edge, vertex );
1051 The macro \texttt{CV\_NEXT\_GRAPH\_EDGE( edge, vertex )} returns the edge incident to \texttt{vertex} that follows after \texttt{edge}.
1053 \cvCPyFunc{GraphVtxDegreeByPtr}
1054 Finds an edge in a graph.
1057 int cvGraphVtxDegreeByPtr( \par const CvGraph* graph,\par const CvGraphVtx* vtx );
1061 \cvarg{graph}{Graph}
1062 \cvarg{vtx}{Pointer to the graph vertex}
1065 The function returns the number of edges incident to the specified vertex, both incoming and outcoming.
1068 \cvCPyFunc{GraphVtxIdx}
1069 Returns the index of a graph vertex.
1071 \cvdefC{int cvGraphVtxIdx( \par CvGraph* graph,\par CvGraphVtx* vtx );}
1074 \cvarg{graph}{Graph}
1075 \cvarg{vtx}{Pointer to the graph vertex}
1078 The function returns the index of a graph vertex.
1080 \cvCPyFunc{InitTreeNodeIterator}
1082 Initializes the tree node iterator.
1086 void cvInitTreeNodeIterator( \par CvTreeNodeIterator* tree\_iterator,\par const void* first,\par int max\_level );
1091 \cvarg{tree\_iterator}{Tree iterator initialized by the function}
1092 \cvarg{first}{The initial node to start traversing from}
1093 \cvarg{max\_level}{The maximal level of the tree (\texttt{first} node assumed to be at the first level) to traverse up to. For example, 1 means that only nodes at the same level as \texttt{first} should be visited, 2 means that the nodes on the same level as \texttt{first} and their direct children should be visited, and so forth.}
1096 The function initializes the tree iterator. The tree is traversed in depth-first order.
1098 \cvCPyFunc{InsertNodeIntoTree}
1100 Adds a new node to a tree.
1102 \cvdefC{void cvInsertNodeIntoTree( \par void* node,\par void* parent,\par void* frame );}
1105 \cvarg{node}{The inserted node}
1106 \cvarg{parent}{The parent node that is already in the tree}
1107 \cvarg{frame}{The top level node. If \texttt{parent} and \texttt{frame} are the same, the \texttt{v\_prev} field of \texttt{node} is set to NULL rather than \texttt{parent}.}
1110 The function adds another node into tree. The function does not allocate any memory, it can only modify links of the tree nodes.
1112 \cvCPyFunc{MakeSeqHeaderForArray}
1113 Constructs a sequence header for an array.
1115 \cvdefC{CvSeq* cvMakeSeqHeaderForArray( \par int seq\_type,\par int header\_size,\par int elem\_size,\par void* elements,\par int total,\par CvSeq* seq,\par CvSeqBlock* block );}
1118 \cvarg{seq\_type}{Type of the created sequence}
1119 \cvarg{header\_size}{Size of the header of the sequence. Parameter sequence must point to the structure of that size or greater}
1120 \cvarg{elem\_size}{Size of the sequence elements}
1121 \cvarg{elements}{Elements that will form a sequence}
1122 \cvarg{total}{Total number of elements in the sequence. The number of array elements must be equal to the value of this parameter.}
1123 \cvarg{seq}{Pointer to the local variable that is used as the sequence header}
1124 \cvarg{block}{Pointer to the local variable that is the header of the single sequence block}
1127 The function initializes a sequence
1128 header for an array. The sequence header as well as the sequence block are
1129 allocated by the user (for example, on stack). No data is copied by the
1130 function. The resultant sequence will consists of a single block and
1131 have NULL storage pointer; thus, it is possible to read its elements,
1132 but the attempts to add elements to the sequence will raise an error in
1135 \cvCPyFunc{MemStorageAlloc}
1136 Allocates a memory buffer in a storage block.
1138 \cvdefC{void* cvMemStorageAlloc( \par CvMemStorage* storage,\par size\_t size );}
1141 \cvarg{storage}{Memory storage}
1142 \cvarg{size}{Buffer size}
1145 The function allocates a memory buffer in
1146 a storage block. The buffer size must not exceed the storage block size,
1147 otherwise a runtime error is raised. The buffer address is aligned by
1148 \texttt{CV\_STRUCT\_ALIGN=sizeof(double)} (for the moment) bytes.
1150 \cvCPyFunc{MemStorageAllocString}
1151 Allocates a text string in a storage block.
1153 \cvdefC{CvString cvMemStorageAllocString(CvMemStorage* storage, const char* ptr, int len=-1);}
1156 typedef struct CvString
1165 \cvarg{storage}{Memory storage}
1166 \cvarg{ptr}{The string}
1167 \cvarg{len}{Length of the string (not counting the ending \texttt{NUL}) . If the parameter is negative, the function computes the length.}
1170 The function creates copy of the string
1171 in memory storage. It returns the structure that contains user-passed
1172 or computed length of the string and pointer to the copied string.
1174 \cvCPyFunc{NextGraphItem}
1175 Executes one or more steps of the graph traversal procedure.
1178 int cvNextGraphItem( CvGraphScanner* scanner );
1182 \cvarg{scanner}{Graph traversal state. It is updated by this function.}
1185 The function traverses through the graph
1186 until an event of interest to the user (that is, an event, specified
1187 in the \texttt{mask} in the \cvCPyCross{CreateGraphScanner} call) is met or the
1188 traversal is completed. In the first case, it returns one of the events
1189 listed in the description of the \texttt{mask} parameter above and with
1190 the next call it resumes the traversal. In the latter case, it returns
1191 \texttt{CV\_GRAPH\_OVER} (-1). When the event is \texttt{CV\_GRAPH\_VERTEX},
1192 \texttt{CV\_GRAPH\_BACKTRACKING}, or \texttt{CV\_GRAPH\_NEW\_TREE},
1193 the currently observed vertex is stored in \texttt{scanner-$>$vtx}. And if the
1194 event is edge-related, the edge itself is stored at \texttt{scanner-$>$edge},
1195 the previously visited vertex - at \texttt{scanner-$>$vtx} and the other ending
1196 vertex of the edge - at \texttt{scanner-$>$dst}.
1198 \cvCPyFunc{NextTreeNode}
1200 Returns the currently observed node and moves the iterator toward the next node.
1204 void* cvNextTreeNode( CvTreeNodeIterator* tree\_iterator );
1209 \cvarg{tree\_iterator}{Tree iterator initialized by the function}
1213 The function returns the currently observed node and then updates the
1214 iterator - moving it toward the next node. In other words, the function
1215 behavior is similar to the \texttt{*p++} expression on a typical C
1216 pointer or C++ collection iterator. The function returns NULL if there
1220 \cvCPyFunc{PrevTreeNode}
1222 Returns the currently observed node and moves the iterator toward the previous node.
1226 void* cvPrevTreeNode( CvTreeNodeIterator* tree\_iterator );
1231 \cvarg{tree\_iterator}{Tree iterator initialized by the function}
1235 The function returns the currently observed node and then updates
1236 the iterator - moving it toward the previous node. In other words,
1237 the function behavior is similar to the \texttt{*p--} expression on a
1238 typical C pointer or C++ collection iterator. The function returns NULL
1239 if there are no more nodes.
1242 \cvCPyFunc{ReleaseGraphScanner}
1243 Completes the graph traversal procedure.
1246 void cvReleaseGraphScanner( CvGraphScanner** scanner );
1250 \cvarg{scanner}{Double pointer to graph traverser}
1254 The function completes the graph traversal procedure and releases the traverser state.
1258 \cvCPyFunc{ReleaseMemStorage}
1259 Releases memory storage.
1261 \cvdefC{void cvReleaseMemStorage( CvMemStorage** storage );}
1264 \cvarg{storage}{Pointer to the released storage}
1267 The function deallocates all storage memory
1268 blocks or returns them to the parent, if any. Then it deallocates the
1269 storage header and clears the pointer to the storage. All child storage
1270 associated with a given parent storage block must be released before the
1271 parent storage block is released.
1273 \cvCPyFunc{RestoreMemStoragePos}
1274 Restores memory storage position.
1276 \cvdefC{void cvRestoreMemStoragePos(\par CvMemStorage* storage,\par CvMemStoragePos* pos);}
1279 \cvarg{storage}{Memory storage}
1280 \cvarg{pos}{New storage top position}
1283 The function restores the position of the storage top from the parameter \texttt{pos}. This function and the function \texttt{cvClearMemStorage} are the only methods to release memory occupied in memory blocks. Note again that there is no way to free memory in the middle of an occupied portion of a storage block.
1286 \cvCPyFunc{SaveMemStoragePos}
1287 Saves memory storage position.
1289 \cvdefC{void cvSaveMemStoragePos(\par const CvMemStorage* storage,\par CvMemStoragePos* pos);}
1292 \cvarg{storage}{Memory storage}
1293 \cvarg{pos}{The output position of the storage top}
1296 The function saves the current position
1297 of the storage top to the parameter \texttt{pos}. The function
1298 \texttt{cvRestoreMemStoragePos} can further retrieve this position.
1300 \cvCPyFunc{SeqElemIdx}
1301 Returns the index of a specific sequence element.
1303 \cvdefC{int cvSeqElemIdx( \par const CvSeq* seq,\par const void* element,\par CvSeqBlock** block=NULL );}
1306 \cvarg{seq}{Sequence}
1307 \cvarg{element}{Pointer to the element within the sequence}
1308 \cvarg{block}{Optional argument. If the pointer is not \texttt{NULL}, the address of the sequence block that contains the element is stored in this location.}
1311 The function returns the index of a sequence element or a negative number if the element is not found.
1313 \cvCPyFunc{SeqInsert}
1314 Inserts an element in the middle of a sequence.
1316 \cvdefC{char* cvSeqInsert( \par CvSeq* seq,\par int beforeIndex,\par void* element=NULL );}
1319 \cvarg{seq}{Sequence}
1320 \cvarg{beforeIndex}{Index before which the element is inserted. Inserting before 0 (the minimal allowed value of the parameter) is equal to \cvCPyCross{SeqPushFront} and inserting before \texttt{seq->total} (the maximal allowed value of the parameter) is equal to \cvCPyCross{SeqPush}.}
1321 \cvarg{element}{Inserted element}
1324 The function shifts the sequence elements from the inserted position to the nearest end of the sequence and copies the \texttt{element} content there if the pointer is not NULL. The function returns a pointer to the inserted element.
1327 \cvCPyFunc{SeqInsertSlice}
1328 Inserts an array in the middle of a sequence.
1330 \cvdefC{void cvSeqInsertSlice( \par CvSeq* seq,\par int beforeIndex,\par const CvArr* fromArr );}
1333 \cvarg{seq}{Sequence}
1334 \cvarg{slice}{The part of the sequence to remove}
1335 \cvarg{fromArr}{The array to take elements from}
1339 The function inserts all \texttt{fromArr}
1340 array elements at the specified position of the sequence. The array
1341 \texttt{fromArr} can be a matrix or another sequence.
1345 \cvCPyFunc{SeqInvert}
1346 Reverses the order of sequence elements.
1348 \cvdefC{void cvSeqInvert( CvSeq* seq );}
1349 \cvdefPy{SeqInvert(seq)-> None}
1352 \cvarg{seq}{Sequence}
1356 The function reverses the sequence in-place - makes the first element go last, the last element go first and so forth.
1361 Removes an element from the end of a sequence.
1363 \cvdefC{void cvSeqPop( \par CvSeq* seq,\par void* element=NULL );}
1366 \cvarg{seq}{Sequence}
1367 \cvarg{element}{Optional parameter . If the pointer is not zero, the function copies the removed element to this location.}
1370 The function removes an element from a sequence. The function reports an error if the sequence is already empty. The function has O(1) complexity.
1372 \cvCPyFunc{SeqPopFront}
1373 Removes an element from the beginning of a sequence.
1375 \cvdefC{void cvSeqPopFront( \par \par CvSeq* seq,\par\par void* element=NULL );}
1378 \cvarg{seq}{Sequence}
1379 \cvarg{element}{Optional parameter. If the pointer is not zero, the function copies the removed element to this location.}
1382 The function removes an element from the beginning of a sequence. The function reports an error if the sequence is already empty. The function has O(1) complexity.
1384 \cvCPyFunc{SeqPopMulti}
1385 Removes several elements from either end of a sequence.
1387 \cvdefC{void cvSeqPopMulti( \par CvSeq* seq,\par void* elements,\par int count,\par int in\_front=0 );}
1390 \cvarg{seq}{Sequence}
1391 \cvarg{elements}{Removed elements}
1392 \cvarg{count}{Number of elements to pop}
1393 \cvarg{in\_front}{The flags specifying which end of the modified sequence.
1395 \cvarg{CV\_BACK}{the elements are added to the end of the sequence}
1396 \cvarg{CV\_FRONT}{the elements are added to the beginning of the sequence}
1400 The function removes several elements from either end of the sequence. If the number of the elements to be removed exceeds the total number of elements in the sequence, the function removes as many elements as possible.
1403 Adds an element to the end of a sequence.
1405 \cvdefC{char* cvSeqPush( \par CvSeq* seq,\par void* element=NULL );}
1408 \cvarg{seq}{Sequence}
1409 \cvarg{element}{Added element}
1412 The function adds an element to the end of a sequence and returns a pointer to the allocated element. If the input \texttt{element} is NULL, the function simply allocates a space for one more element.
1414 The following code demonstrates how to create a new sequence using this function:
1417 CvMemStorage* storage = cvCreateMemStorage(0);
1418 CvSeq* seq = cvCreateSeq( CV_32SC1, /* sequence of integer elements */
1419 sizeof(CvSeq), /* header size - no extra fields */
1420 sizeof(int), /* element size */
1421 storage /* the container storage */ );
1423 for( i = 0; i < 100; i++ )
1425 int* added = (int*)cvSeqPush( seq, &i );
1426 printf( "%d is added\n", *added );
1430 /* release memory storage in the end */
1431 cvReleaseMemStorage( &storage );
1434 The function has O(1) complexity, but there is a faster method for writing large sequences (see \cvCPyCross{StartWriteSeq} and related functions).
1437 \cvCPyFunc{SeqPushFront}
1438 Adds an element to the beginning of a sequence.
1440 \cvdefC{char* cvSeqPushFront( CvSeq* seq, void* element=NULL );}
1443 \cvarg{seq}{Sequence}
1444 \cvarg{element}{Added element}
1447 The function is similar to \cvCPyCross{SeqPush} but it adds the new element to the beginning of the sequence. The function has O(1) complexity.
1449 \cvCPyFunc{SeqPushMulti}
1450 Pushes several elements to either end of a sequence.
1452 \cvdefC{void cvSeqPushMulti( \par CvSeq* seq,\par void* elements,\par int count,\par int in\_front=0 );}
1455 \cvarg{seq}{Sequence}
1456 \cvarg{elements}{Added elements}
1457 \cvarg{count}{Number of elements to push}
1458 \cvarg{in\_front}{The flags specifying which end of the modified sequence.
1460 \cvarg{CV\_BACK}{the elements are added to the end of the sequence}
1461 \cvarg{CV\_FRONT}{the elements are added to the beginning of the sequence}
1465 The function adds several elements to either
1466 end of a sequence. The elements are added to the sequence in the same
1467 order as they are arranged in the input array but they can fall into
1468 different sequence blocks.
1472 \cvCPyFunc{SeqRemove}
1473 Removes an element from the middle of a sequence.
1475 \cvdefC{void cvSeqRemove( \par CvSeq* seq,\par int index );}
1476 \cvdefPy{SeqRemove(seq,index)-> None}
1479 \cvarg{seq}{Sequence}
1480 \cvarg{index}{Index of removed element}
1483 The function removes elements with the given
1484 index. If the index is out of range the function reports an error. An
1485 attempt to remove an element from an empty sequence is a special
1486 case of this situation. The function removes an element by shifting
1487 the sequence elements between the nearest end of the sequence and the
1488 \texttt{index}-th position, not counting the latter.
1491 \cvCPyFunc{SeqRemoveSlice}
1492 Removes a sequence slice.
1494 \cvdefC{void cvSeqRemoveSlice( CvSeq* seq, CvSlice slice );}
1495 \cvdefPy{SeqRemoveSlice(seq,slice)-> None}
1498 \cvarg{seq}{Sequence}
1499 \cvarg{slice}{The part of the sequence to remove}
1502 The function removes a slice from the sequence.
1506 \cvCPyFunc{SeqSearch}
1507 Searches for an element in a sequence.
1510 char* cvSeqSearch( CvSeq* seq, const void* elem, CvCmpFunc func,
1511 int is\_sorted, int* elem\_idx, void* userdata=NULL );
1515 \cvarg{seq}{The sequence}
1516 \cvarg{elem}{The element to look for}
1517 \cvarg{func}{The comparison function that returns negative, zero or positive value depending on the relationships among the elements (see also \cvCPyCross{SeqSort})}
1518 \cvarg{is\_sorted}{Whether the sequence is sorted or not}
1519 \cvarg{elem\_idx}{Output parameter; index of the found element}
1520 \cvarg{userdata}{The user parameter passed to the compasion function; helps to avoid global variables in some cases}
1524 /* a < b ? -1 : a > b ? 1 : 0 */
1525 typedef int (CV_CDECL* CvCmpFunc)(const void* a, const void* b, void* userdata);
1528 The function searches for the element in the sequence. If
1529 the sequence is sorted, a binary O(log(N)) search is used; otherwise, a
1530 simple linear search is used. If the element is not found, the function
1531 returns a NULL pointer and the index is set to the number of sequence
1532 elements if a linear search is used, or to the smallest index
1533 \texttt{i, seq(i)>elem}.
1535 \cvCPyFunc{SeqSlice}
1536 Makes a separate header for a sequence slice.
1538 \cvdefC{CvSeq* cvSeqSlice( \par const CvSeq* seq,\par CvSlice slice,\par CvMemStorage* storage=NULL,\par int copy\_data=0 );}
1541 \cvarg{seq}{Sequence}
1542 \cvarg{slice}{The part of the sequence to be extracted}
1543 \cvarg{storage}{The destination storage block to hold the new sequence header and the copied data, if any. If it is NULL, the function uses the storage block containing the input sequence.}
1544 \cvarg{copy\_data}{The flag that indicates whether to copy the elements of the extracted slice (\texttt{copy\_data!=0}) or not (\texttt{copy\_data=0})}
1547 The function creates a sequence that represents the specified slice of the input sequence. The new sequence either shares the elements with the original sequence or has its own copy of the elements. So if one needs to process a part of sequence but the processing function does not have a slice parameter, the required sub-sequence may be extracted using this function.
1550 Sorts sequence element using the specified comparison function.
1552 \cvdefC{void cvSeqSort( CvSeq* seq, CvCmpFunc func, void* userdata=NULL );}
1555 /* a < b ? -1 : a > b ? 1 : 0 */
1556 typedef int (CV_CDECL* CvCmpFunc)(const void* a, const void* b, void* userdata);
1560 \cvarg{seq}{The sequence to sort}
1561 \cvarg{func}{The comparison function that returns a negative, zero, or positive value depending on the relationships among the elements (see the above declaration and the example below) - a similar function is used by \texttt{qsort} from C runline except that in the latter, \texttt{userdata} is not used}
1562 \cvarg{userdata}{The user parameter passed to the compasion function; helps to avoid global variables in some cases}
1565 The function sorts the sequence in-place using the specified criteria. Below is an example of using this function:
1568 /* Sort 2d points in top-to-bottom left-to-right order */
1569 static int cmp_func( const void* _a, const void* _b, void* userdata )
1571 CvPoint* a = (CvPoint*)_a;
1572 CvPoint* b = (CvPoint*)_b;
1573 int y_diff = a->y - b->y;
1574 int x_diff = a->x - b->x;
1575 return y_diff ? y_diff : x_diff;
1580 CvMemStorage* storage = cvCreateMemStorage(0);
1581 CvSeq* seq = cvCreateSeq( CV_32SC2, sizeof(CvSeq), sizeof(CvPoint), storage );
1584 for( i = 0; i < 10; i++ )
1587 pt.x = rand() % 1000;
1588 pt.y = rand() % 1000;
1589 cvSeqPush( seq, &pt );
1592 cvSeqSort( seq, cmp_func, 0 /* userdata is not used here */ );
1594 /* print out the sorted sequence */
1595 for( i = 0; i < seq->total; i++ )
1597 CvPoint* pt = (CvPoint*)cvSeqElem( seq, i );
1598 printf( "(%d,%d)\n", pt->x, pt->y );
1601 cvReleaseMemStorage( &storage );
1606 Occupies a node in the set.
1608 \cvdefC{int cvSetAdd( \par CvSet* setHeader,\par CvSetElem* elem=NULL,\par CvSetElem** inserted\_elem=NULL );}
1611 \cvarg{setHeader}{Set}
1612 \cvarg{elem}{Optional input argument, an inserted element. If not NULL, the function copies the data to the allocated node (the MSB of the first integer field is cleared after copying).}
1613 \cvarg{inserted\_elem}{Optional output argument; the pointer to the allocated cell}
1616 The function allocates a new node, optionally copies
1617 input element data to it, and returns the pointer and the index to the
1618 node. The index value is taken from the lower bits of the \texttt{flags}
1619 field of the node. The function has O(1) complexity; however, there exists
1620 a faster function for allocating set nodes (see \cvCPyCross{SetNew}).
1623 Adds an element to a set (fast variant).
1625 \cvdefC{CvSetElem* cvSetNew( CvSet* setHeader );}
1628 \cvarg{setHeader}{Set}
1631 The function is an inline lightweight variant of \cvCPyCross{SetAdd}. It occupies a new node and returns a pointer to it rather than an index.
1634 \cvCPyFunc{SetRemove}
1635 Removes an element from a set.
1637 \cvdefC{void cvSetRemove( \par CvSet* setHeader,\par int index );}
1640 \cvarg{setHeader}{Set}
1641 \cvarg{index}{Index of the removed element}
1644 The function removes an element with a specified
1645 index from the set. If the node at the specified location is not occupied,
1646 the function does nothing. The function has O(1) complexity; however,
1647 \cvCPyCross{SetRemoveByPtr} provides a quicker way to remove a set element
1648 if it is located already.
1650 \cvCPyFunc{SetRemoveByPtr}
1651 Removes a set element based on its pointer.
1653 \cvdefC{void cvSetRemoveByPtr( \par CvSet* setHeader,\par void* elem );}
1656 \cvarg{setHeader}{Set}
1657 \cvarg{elem}{Removed element}
1660 The function is an inline lightweight variant of \cvCPyCross{SetRemove} that requires an element pointer. The function does not check whether the node is occupied or not - the user should take care of that.
1663 \cvCPyFunc{SetSeqBlockSize}
1664 Sets up sequence block size.
1666 \cvdefC{void cvSetSeqBlockSize( \par CvSeq* seq,\par int deltaElems );}
1669 \cvarg{seq}{Sequence}
1670 \cvarg{deltaElems}{Desirable sequence block size for elements}
1673 The function affects memory allocation
1674 granularity. When the free space in the sequence buffers has run out,
1675 the function allocates the space for \texttt{deltaElems} sequence
1676 elements. If this block immediately follows the one previously allocated,
1677 the two blocks are concatenated; otherwise, a new sequence block is
1678 created. Therefore, the bigger the parameter is, the lower the possible
1679 sequence fragmentation, but the more space in the storage block is wasted. When
1680 the sequence is created, the parameter \texttt{deltaElems} is set to
1681 the default value of about 1K. The function can be called any time after
1682 the sequence is created and affects future allocations. The function
1683 can modify the passed value of the parameter to meet memory storage
1686 \cvCPyFunc{SetSeqReaderPos}
1687 Moves the reader to the specified position.
1689 \cvdefC{void cvSetSeqReaderPos( \par CvSeqReader* reader,\par int index,\par int is\_relative=0 );}
1692 \cvarg{reader}{Reader state}
1693 \cvarg{index}{The destination position. If the positioning mode is used (see the next parameter), the actual position will be \texttt{index} mod \texttt{reader->seq->total}.}
1694 \cvarg{is\_relative}{If it is not zero, then \texttt{index} is a relative to the current position}
1697 The function moves the read position to an absolute position or relative to the current position.
1700 \cvCPyFunc{StartAppendToSeq}
1701 Initializes the process of writing data to a sequence.
1703 \cvdefC{void cvStartAppendToSeq( \par CvSeq* seq,\par CvSeqWriter* writer );}
1706 \cvarg{seq}{Pointer to the sequence}
1707 \cvarg{writer}{Writer state; initialized by the function}
1710 The function initializes the process of
1711 writing data to a sequence. Written elements are added to the end of the
1712 sequence by using the
1713 \texttt{CV\_WRITE\_SEQ\_ELEM( written\_elem, writer )}
1715 that during the writing process, other operations on the sequence may
1716 yield an incorrect result or even corrupt the sequence (see description of
1717 \cvCPyCross{FlushSeqWriter}, which helps to avoid some of these problems).
1719 \cvCPyFunc{StartReadSeq}
1720 Initializes the process of sequential reading from a sequence.
1722 \cvdefC{void cvStartReadSeq( \par const CvSeq* seq,\par CvSeqReader* reader,\par int reverse=0 );}
1725 \cvarg{seq}{Sequence}
1726 \cvarg{reader}{Reader state; initialized by the function}
1727 \cvarg{reverse}{Determines the direction of the sequence traversal. If \texttt{reverse} is 0, the reader is positioned at the first sequence element; otherwise it is positioned at the last element. }
1730 The function initializes the reader state. After
1731 that, all the sequence elements from the first one down to the last one
1732 can be read by subsequent calls of the macro
1733 \texttt{CV\_READ\_SEQ\_ELEM( read\_elem, reader )}
1734 in the case of forward reading and by using
1735 \texttt{CV\_REV\_READ\_SEQ\_ELEM( read\_elem, reader )}
1736 in the case of reverse
1737 reading. Both macros put the sequence element to \texttt{read\_elem} and
1738 move the reading pointer toward the next element. A circular structure
1739 of sequence blocks is used for the reading process, that is, after the
1740 last element has been read by the macro \texttt{CV\_READ\_SEQ\_ELEM}, the
1741 first element is read when the macro is called again. The same applies to
1742 \texttt{CV\_REV\_READ\_SEQ\_ELEM}. There is no function to finish the reading
1743 process, since it neither changes the sequence nor creates any temporary
1744 buffers. The reader field \texttt{ptr} points to the current element of
1745 the sequence that is to be read next. The code below demonstrates how
1746 to use the sequence writer and reader.
1749 CvMemStorage* storage = cvCreateMemStorage(0);
1750 CvSeq* seq = cvCreateSeq( CV_32SC1, sizeof(CvSeq), sizeof(int), storage );
1755 cvStartAppendToSeq( seq, &writer );
1756 for( i = 0; i < 10; i++ )
1758 int val = rand()%100;
1759 CV_WRITE_SEQ_ELEM( val, writer );
1760 printf("%d is written\n", val );
1762 cvEndWriteSeq( &writer );
1764 cvStartReadSeq( seq, &reader, 0 );
1765 for( i = 0; i < seq->total; i++ )
1769 CV_READ_SEQ_ELEM( val, reader );
1770 printf("%d is read\n", val );
1771 #else /* alternative way, that is prefferable if sequence elements are large,
1772 or their size/type is unknown at compile time */
1773 printf("%d is read\n", *(int*)reader.ptr );
1774 CV_NEXT_SEQ_ELEM( seq->elem_size, reader );
1779 cvReleaseStorage( &storage );
1782 \cvCPyFunc{StartWriteSeq}
1783 Creates a new sequence and initializes a writer for it.
1786 void cvStartWriteSeq( \par int seq\_flags,\par int header\_size,\par int elem\_size,\par CvMemStorage* storage,\par CvSeqWriter* writer );
1790 \cvarg{seq\_flags}{Flags of the created sequence. If the sequence is not passed to any function working with a specific type of sequences, the sequence value may be equal to 0; otherwise the appropriate type must be selected from the list of predefined sequence types.}
1791 \cvarg{header\_size}{Size of the sequence header. The parameter value may not be less than \texttt{sizeof(CvSeq)}. If a certain type or extension is specified, it must fit within the base type header.}
1792 \cvarg{elem\_size}{Size of the sequence elements in bytes; must be consistent with the sequence type. For example, if a sequence of points is created (element type \texttt{CV\_SEQ\_ELTYPE\_POINT} ), then the parameter \texttt{elem\_size} must be equal to \texttt{sizeof(CvPoint)}.}
1793 \cvarg{storage}{Sequence location}
1794 \cvarg{writer}{Writer state; initialized by the function}
1797 The function is a combination of
1798 \cvCPyCross{CreateSeq} and \cvCPyCross{StartAppendToSeq}. The pointer to the
1799 created sequence is stored at
1800 \texttt{writer->seq}
1801 and is also returned by the
1802 \cvCPyCross{EndWriteSeq} function that should be called at the end.
1804 \cvCPyFunc{TreeToNodeSeq}
1805 Gathers all node pointers to a single sequence.
1809 CvSeq* cvTreeToNodeSeq( \par const void* first,\par int header\_size,\par CvMemStorage* storage );
1814 \cvarg{first}{The initial tree node}
1815 \cvarg{header\_size}{Header size of the created sequence (sizeof(CvSeq) is the most frequently used value)}
1816 \cvarg{storage}{Container for the sequence}
1819 The function puts pointers of all nodes reacheable from \texttt{first} into a single sequence. The pointers are written sequentially in the depth-first order.