Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/heap.h @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
27 #ifndef LEPTONICA_HEAP_H
28 #define LEPTONICA_HEAP_H
29
30 /*!
31 * \file heap.h
32 *
33 * <pre>
34 * Expandable priority queue configured as a heap for arbitrary void* data
35 *
36 * The L_Heap is used to implement a priority queue. The elements
37 * in the heap are ordered in either increasing or decreasing key value.
38 * The key is a float field 'keyval' that is required to be
39 * contained in the elements of the queue.
40 *
41 * The heap is a simple binary tree with the following constraints:
42 * - the key of each node is >= the keys of the two children
43 * - the tree is complete, meaning that each level (1, 2, 4, ...)
44 * is filled and the last level is filled from left to right
45 *
46 * The tree structure is implicit in the queue array, with the
47 * array elements numbered as a breadth-first search of the tree
48 * from left to right. It is thus guaranteed that the largest
49 * (or smallest) key belongs to the first element in the array.
50 *
51 * Heap sort is used to sort the array. Once an array has been
52 * sorted as a heap, it is convenient to use it as a priority queue,
53 * because the min (or max) elements are always at the root of
54 * the tree (element 0), and once removed, the heap can be
55 * resorted in not more than log[n] steps, where n is the number
56 * of elements on the heap. Likewise, if an arbitrary element is
57 * added to the end of the array A, the sorted heap can be restored
58 * in not more than log[n] steps.
59 *
60 * A L_Heap differs from a L_Queue in that the elements in the former
61 * are sorted by a key. Internally, the array is maintained
62 * as a queue, with a pointer to the end of the array. The
63 * head of the array always remains at array[0]. The array is
64 * maintained (sorted) as a heap. When an item is removed from
65 * the head, the last item takes its place (thus reducing the
66 * array length by 1), and this is followed by array element
67 * swaps to restore the heap property. When an item is added,
68 * it goes at the end of the array, and is swapped up to restore
69 * the heap. If the ptr array is full, adding another item causes
70 * the ptr array size to double.
71 *
72 * For further implementation details, see heap.c.
73 * </pre>
74 */
75
76 /*! Heap of arbitrary void* data */
77 struct L_Heap
78 {
79 l_int32 nalloc; /*!< size of allocated ptr array */
80 l_int32 n; /*!< number of elements stored in the heap */
81 void **array; /*!< ptr array */
82 l_int32 direction; /*!< L_SORT_INCREASING or L_SORT_DECREASING */
83 };
84 typedef struct L_Heap L_HEAP;
85
86
87 #endif /* LEPTONICA_HEAP_H */