N-ary Trees

N-ary Trees — Деревья данных с любым количеством ответвлений.

Краткое описание



#include <glib.h>


            GNode;
GNode*      g_node_new                      (gpointer data);
GNode*      g_node_copy                     (GNode *node);
gpointer    (*GCopyFunc)                    (gconstpointer src,
                                             gpointer data);
GNode*      g_node_copy_deep                (GNode *node,
                                             GCopyFunc copy_func,
                                             gpointer data);

GNode*      g_node_insert                   (GNode *parent,
                                             gint position,
                                             GNode *node);
GNode*      g_node_insert_before            (GNode *parent,
                                             GNode *sibling,
                                             GNode *node);
GNode*      g_node_insert_after             (GNode *parent,
                                             GNode *sibling,
                                             GNode *node);
#define     g_node_append                   (parent, node)
GNode*      g_node_prepend                  (GNode *parent,
                                             GNode *node);

#define     g_node_insert_data              (parent, position, data)
#define     g_node_insert_data_before       (parent, sibling, data)
#define     g_node_append_data              (parent, data)
#define     g_node_prepend_data             (parent, data)

void        g_node_reverse_children         (GNode *node);
void        g_node_traverse                 (GNode *root,
                                             GTraverseType order,
                                             GTraverseFlags flags,
                                             gint max_depth,
                                             GNodeTraverseFunc func,
                                             gpointer data);
enum        GTraverseFlags;
gboolean    (*GNodeTraverseFunc)            (GNode *node,
                                             gpointer data);
void        g_node_children_foreach         (GNode *node,
                                             GTraverseFlags flags,
                                             GNodeForeachFunc func,
                                             gpointer data);
void        (*GNodeForeachFunc)             (GNode *node,
                                             gpointer data);

GNode*      g_node_get_root                 (GNode *node);
GNode*      g_node_find                     (GNode *root,
                                             GTraverseType order,
                                             GTraverseFlags flags,
                                             gpointer data);
GNode*      g_node_find_child               (GNode *node,
                                             GTraverseFlags flags,
                                             gpointer data);
gint        g_node_child_index              (GNode *node,
                                             gpointer data);
gint        g_node_child_position           (GNode *node,
                                             GNode *child);
#define     g_node_first_child              (node)
GNode*      g_node_last_child               (GNode *node);
GNode*      g_node_nth_child                (GNode *node,
                                             guint n);
GNode*      g_node_first_sibling            (GNode *node);
#define     g_node_next_sibling             (node)
#define     g_node_prev_sibling             (node)
GNode*      g_node_last_sibling             (GNode *node);

#define     G_NODE_IS_LEAF                  (node)
#define     G_NODE_IS_ROOT                  (node)
guint       g_node_depth                    (GNode *node);
guint       g_node_n_nodes                  (GNode *root,
                                             GTraverseFlags flags);
guint       g_node_n_children               (GNode *node);
gboolean    g_node_is_ancestor              (GNode *node,
                                             GNode *descendant);
guint       g_node_max_height               (GNode *root);

void        g_node_unlink                   (GNode *node);
void        g_node_destroy                  (GNode *root);

void        g_node_push_allocator           (gpointer dummy);
void        g_node_pop_allocator            (void);

Описание

Структура GNode и связанные с ней функции обеспечивают N-ary дерево структур данных, где узлы в дереве могут содержать произвольные данные.

Для создания нового дерева используйте g_node_new().

Для вставки узлов в дерево используйте g_node_insert(), g_node_insert_before(), g_node_append() и g_node_prepend().

Для создания нового узла и вставки его в дерево используйте g_node_insert_data(), g_node_insert_data_before(), g_node_append_data() и g_node_prepend_data().

Для реверса дочерних элементов узла используйте g_node_reverse_children().

Для поиска узла используйте g_node_get_root(), g_node_find(), g_node_find_child(), g_node_child_index(), g_node_child_position(), g_node_first_child(), g_node_last_child(), g_node_nth_child(), g_node_first_sibling(), g_node_prev_sibling(), g_node_next_sibling() или g_node_last_sibling().

Для получения информации об узле или дереве используйте G_NODE_IS_LEAF(), G_NODE_IS_ROOT(), g_node_depth(), g_node_n_nodes(), g_node_n_children(), g_node_is_ancestor() or g_node_max_height().

Для обхода дерева, вызывая функцию для каждого посещяемого узла при обходе, используйте g_node_traverse() или g_node_children_foreach().

Для удаления узла или дочернего дерева из дерева используйте g_node_unlink() или g_node_destroy().

Детали

GNode

typedef struct {
  gpointer data;
  GNode	  *next;
  GNode	  *prev;
  GNode	  *parent;
  GNode	  *children;
} GNode;

Структура GNode представляет один узел в N-ary Tree. Поле data содержит фактические данные в узле. Поля next и prev указывают на дочерние узлы (дочерние - это другие GNode с тем же родителем). Поле parent указывает на родителя GNode, или NULL если GNode является корнем дерева. Поле children указывает на первую дочернюю GNode. Другие дочерние узлы связываются используя указатель next каждого дочернего узла.

g_node_new ()

GNode* g_node_new (gpointer data);

Создаёт новую GNode содержащую полученные данные. Используется для создания первого узла в дереве.

`data` :	данные нового узла.
Возвращает :	новый GNode.

g_node_copy ()

GNode* g_node_copy (GNode *node);

Рекурсивно копирует GNode (но не делает глубоких копий данных в узлах, смотрите g_node_copy_deep() если вам это нужно).

`node` :	GNode.
Возвращает :	новый GNode содержащий те же указатели данных.

GCopyFunc ()

gpointer    (*GCopyFunc)                    (gconstpointer src,
                                             gpointer data);

Функция этой сигнатуры используется для копирования узла данных выполняя глубокую копию дерева.

`src` :	указатель на данные которые должны быть скопированны.
`data` :	дополнительные данные.
Возвращает :	указатель на копию.

Начиная с версии 2.4

g_node_copy_deep ()

GNode*      g_node_copy_deep                (GNode *node,
                                             GCopyFunc copy_func,
                                             gpointer data);

Рекурсивно копирует GNode и его данные.

`node` :	GNode
`copy_func` :	функция вызываемая для копирования данных внутри каждого узла, или `NULL` для использования оригинальных данных.
`data` :	данные помещаемые в `copy_func`
Возвращает :	новый GNode содержащий копии данных в `node`.

Начиная с версии 2.4

g_node_insert ()

GNode*      g_node_insert                   (GNode *parent,
                                             gint position,
                                             GNode *node);

Вставляет GNode ниже родителя в указанную позицию.

`parent` :	GNode под которым размещается `node`.
`position` :	позиция для размещения `node`, относительно родственных элементов. Если позиция -1, `node` вставляется как последний дочерний элемент `parent`.
`node` :	GNode для вставки.
Возвращает :	вставляемый GNode.

g_node_insert_before ()

GNode*      g_node_insert_before            (GNode *parent,
                                             GNode *sibling,
                                             GNode *node);

Вставляет GNode ниже родителя перед указанным соседом.

`parent` :	GNode под которым располагается `node`.
`sibling` :	соседний GNode для размещения `node` перед ним. Если соседний это `NULL`, узел вставляется как последний дочерний `parent`.
`node` :	вставляемый GNode.
Возвращает :	вставленный GNode.

g_node_insert_after ()

GNode*      g_node_insert_after             (GNode *parent,
                                             GNode *sibling,
                                             GNode *node);

Вставляет GNode ниже родителя после указанного соседа.

`parent` :	GNode под которым размещается `node`.
`sibling` :	соседний GNode после которого размещается `node`. Если сосед это `NULL`, узел вставляется как первый дочерний `parent`.
`node` :	вставляемый GNode.
Возвращает :	вставленный GNode.

g_node_append()

#define g_node_append(parent, node)

Вставляет GNode как последний дочерний указанного родителя.

`parent` :	GNode под которым размещается новый GNode.
`node` :	вставляемый GNode.
Возвращает :	вставляемый GNode.

g_node_prepend ()

GNode*      g_node_prepend                  (GNode *parent,
                                             GNode *node);

Вставляет GNode как первый дочерний указанного родителя.

`parent` :	GNode под которым размещается новый GNode under.
`node` :	вставляемый GNode.
Возвращает :	вставленный GNode.

g_node_insert_data()

#define g_node_insert_data(parent, position, data)

Вставляет новый GNode в указанную позицию.

`parent` :	GNode под которым размещается новый GNode.
`position` :	позиция для размещения нового GNode. Если позиция равна -1, новый GNode вставляется как последний дочерний `parent`.
`data` :	данные для нового GNode.
Возвращает :	новый GNode.

g_node_insert_data_before()

#define g_node_insert_data_before(parent, sibling, data)

Вставляет новый GNode перед указанным соседом.

`parent` :	GNode под которым размещается новый GNode.
`sibling` :	соседний GNode перед которым размещается новый GNode.
`data` :	данные для нового GNode.
Возвращает :	новый GNode.

g_node_append_data()

#define g_node_append_data(parent, data)

Вставляет новый GNode как последний дочерний указанного родителя.

`parent` :	GNode под которым размещается новый GNode.
`data` :	данные для нового GNode.
Возвращает :	новый GNode.

g_node_prepend_data()

#define g_node_prepend_data(parent, data)

Вставляет новый GNode как первый дочерний указанного родителя.

`parent` :	GNode под которым размещается новый GNode.
`data` :	данные для нового GNode.
Возвращает :	новый GNode.

g_node_reverse_children ()

void g_node_reverse_children (GNode *node);

Переворачивает порядок дочерних GNode. (Она не меняет порядок внуков.)

node : GNode.

g_node_traverse ()

void        g_node_traverse                 (GNode *root,
                                             GTraverseType order,
                                             GTraverseFlags flags,
                                             gint max_depth,
                                             GNodeTraverseFunc func,
                                             gpointer data);

Обходит дерево начиная с указанного корня GNode. Она вызывает указанную функцию для каждого посещяемого узла. Обход может быть прекращён в любой точке когда TRUE вернётся из func.

`root` :	корень GNode дерева для обхода.
`order` :	порядок в котором посещаются узлы - `G_IN_ORDER`, `G_PRE_ORDER`, `G_POST_ORDER`, или `G_LEVEL_ORDER`.
`flags` :	какие типы дочерних узлов будут посещены, один из вариантов - `G_TRAVERSE_ALL`, `G_TRAVERSE_LEAVES` и `G_TRAVERSE_NON_LEAVES`.
`max_depth` :	максимальная глубина обхода. Узлы на этой глубине не будут посещаться. Если max_depth равна -1 посещаются все узлы в дереве. Если глубина 1, посещается только корень. Если глубина 2, посещаются корень и его дочерние узлы. И так далее.
`func` :	функция вызываемая для каждого посещённого элемента GNode.
`data` :	пользовательские данные помещаемые в функцию.

enum GTraverseFlags

typedef enum
{
  G_TRAVERSE_LEAVES     = 1 << 0,
  G_TRAVERSE_NON_LEAVES = 1 << 1,
  G_TRAVERSE_ALL        = G_TRAVERSE_LEAVES | G_TRAVERSE_NON_LEAVES,
  G_TRAVERSE_MASK       = 0x03,
  G_TRAVERSE_LEAFS      = G_TRAVERSE_LEAVES,
  G_TRAVERSE_NON_LEAFS  = G_TRAVERSE_NON_LEAVES
} GTraverseFlags;

Определяет какие узлы посещаются при выполнении некоторых функций дерева, включая g_node_traverse() и g_node_find().

`G_TRAVERSE_LEAVES`	только вершины узлов должны посещаться. Это название было введено в версии 2.6, ранние версии использовали `G_TRAVERSE_LEAFS`.
`G_TRAVERSE_NON_LEAVES`	только не вершины должны посещаться. Это имя введено в версии 2.6, в ранних версиях использовалось `G_TRAVERSE_NON_LEAFS`.
`G_TRAVERSE_ALL`	все узлы должны посещаться.
`G_TRAVERSE_MASK`
`G_TRAVERSE_LEAFS`	идентично `G_TRAVERSE_LEAVES`
`G_TRAVERSE_NON_LEAFS`	идентично `G_TRAVERSE_NON_LEAVES`

GNodeTraverseFunc ()

gboolean    (*GNodeTraverseFunc)            (GNode *node,
                                             gpointer data);

Определяет тип функции помещаемой в g_node_traverse(). Функция вызывается с каждым посещённым узлом, который передают вместе с пользовательскими данными в g_node_traverse(). Если функция возвращает TRUE, то обход прекращается.

`node` :	GNode.
`data` :	пользовательские данные помещаемые в `g_node_traverse()`.
Возвращает :	`TRUE` для остановки обхода.

g_node_children_foreach ()

void        g_node_children_foreach         (GNode *node,
                                             GTraverseFlags flags,
                                             GNodeForeachFunc func,
                                             gpointer data);

Вызывает функцию для каждого дочернего GNode. Помните что она не опускается ниже дочерних узлов.

`node` :	GNode.
`flags` :	какие типы дочерних элементов посещаются, один из `G_TRAVERSE_ALL`, `G_TRAVERSE_LEAVES` и `G_TRAVERSE_NON_LEAVES`.
`func` :	функция вызываемая для каждого посещённого узла.
`data` :	пользовательские данные помещаемые в функцию.

GNodeForeachFunc ()

void        (*GNodeForeachFunc)             (GNode *node,
                                             gpointer data);

Определяет тип функции помещаемой в g_node_children_foreach(). Функция вызываемая для каждого дочернего узла, вместе с пользовательскими данными которые помещаются в g_node_children_foreach().

`node` :	GNode.
`data` :	пользовательские данные помещаемые в `g_node_children_foreach()`.

g_node_get_root ()

GNode* g_node_get_root (GNode *node);

Определяет корень дерева.

`node` :	GNode.
Возвращает :	корень дерева.

g_node_find ()

GNode*      g_node_find                     (GNode *root,
                                             GTraverseType order,
                                             GTraverseFlags flags,
                                             gpointer data);

Находит GNode в дереве.

`root` :	корневой GNode дерева для поиска.
`order` :	порядок в котором посещаются узлы - `G_IN_ORDER`, `G_PRE_ORDER`, `G_POST_ORDER`, или `G_LEVEL_ORDER`.
`flags` :	какой тип дочернего элемента должен быть найден, один из `G_TRAVERSE_ALL`, `G_TRAVERSE_LEAVES` и `G_TRAVERSE_NON_LEAVES`.
`data` :	данные для поиска.
Возвращает :	найденный GNode, или `NULL` если данные не найдены.

g_node_find_child ()

GNode*      g_node_find_child               (GNode *node,
                                             GTraverseFlags flags,
                                             gpointer data);

Находит первый дочерний GNode с указанными данными.

`node` :	GNode.
`flags` :	какой тип дочерних узлов разыскивается, один из `G_TRAVERSE_ALL`, `G_TRAVERSE_LEAVES` и `G_TRAVERSE_NON_LEAVES`.
`data` :	данные для поиска.
Возвращает :	найденный дочерний GNode, или `NULL` если данные не найдены.

g_node_child_index ()

gint        g_node_child_index              (GNode *node,
                                             gpointer data);

Определяет позицию первого дочернего GNode который содержит указанные данные.

`node` :	GNode.
`data` :	данные для поиска.
Возвращает :	номер дочернего `node` который содержит `data`, или -1 если данные не найдены.

g_node_child_position ()

gint        g_node_child_position           (GNode *node,
                                             GNode *child);

Определяет позицию GNode относительно его соседей. child должен быть дочерним по отношению к node. Первый дочерний нумеруется 0, второй 1, и так далее.

`node` :	GNode.
`child` :	дочерний по отношению к `node`.
Возвращает :	позиция `child` относительно его соседей.

g_node_first_child()

#define g_node_first_child(node)

Определяет первый дочерний GNode.

`node` :	GNode.
Возвращает :	первый дочерний `node`, или `NULL` если `node` это `NULL` или нет дочерних элементов.

g_node_last_child ()

GNode* g_node_last_child (GNode *node);

Определяет последний дочерний GNode.

`node` :	GNode (не должен быть `NULL`).
Возвращает :	последний дочерний `node`, или `NULL` если `node` не имеет дочерних элементов.

g_node_nth_child ()

GNode*      g_node_nth_child                (GNode *node,
                                             guint n);

Определяет дочерний GNode, используя указанный номер. Первый это номер 0. Если номер слишком большой, возвращает NULL.

`node` :	GNode.
`n` :	номер желаемого дочернего элемента.
Возвращает :	дочерний `node` с номером `n`.

g_node_first_sibling ()

GNode* g_node_first_sibling (GNode *node);

Определяет первый соседний GNode. Это может быть сам узел.

`node` :	GNode.
Возвращает :	первый соседний `node`.

g_node_next_sibling()

#define g_node_next_sibling(node)

Определяет следующего соседа GNode.

`node` :	GNode.
Возвращает :	следующий сосед `node`, или `NULL` если `node` это `NULL`.

g_node_prev_sibling()

#define g_node_prev_sibling(node)

Определяет предыдущего соседа GNode.

`node` :	GNode.
Возвращает :	предыдущий сосед `node`, или `NULL` если `node` это `NULL`.

g_node_last_sibling ()

GNode* g_node_last_sibling (GNode *node);

Определяет последнего соседа GNode. Это может быть сам узел.

`node` :	GNode.
Возвращает :	последний соседний `node`.

G_NODE_IS_LEAF()

#define	 G_NODE_IS_LEAF(node)	(((GNode*) (node))->children == NULL)

Возвращает TRUE если GNode это вершина узла.

`node` :	GNode.
Возвращает :	`TRUE` если GNode вершина узла (то есть он не имеет дочерних элементов).

G_NODE_IS_ROOT()

#define G_NODE_IS_ROOT(node)

Возвращает TRUE если GNode это корень дерева.

`node` :	GNode.
Возвращает :	`TRUE` если GNode является корнем дерева (то есть он не имеет родительского соседа).

g_node_depth ()

guint g_node_depth (GNode *node);

Определяет глубину GNode.

Если node это NULL глубина равна 0. Корневой узел имеет глубину равную 1. Для дочерних элементов корневого узла глубина равна 2. И так далее.

`node` :	GNode.
Возвращает :	глубина GNode.

g_node_n_nodes ()

guint       g_node_n_nodes                  (GNode *root,
                                             GTraverseFlags flags);

Определяет количество узлов в дереве.

`root` :	GNode.
`flags` :	какие типы дочерних элементов подсчитываются, один из вариантов `G_TRAVERSE_ALL`, `G_TRAVERSE_LEAVES` и `G_TRAVERSE_NON_LEAVES`.
Возвращает :	количество узлов в дереве.

g_node_n_children ()

guint g_node_n_children (GNode *node);

Определяет количество дочерних GNode.

`node` :	GNode.
Возвращает :	количество дочерних `node`.

g_node_is_ancestor ()

gboolean    g_node_is_ancestor              (GNode *node,
                                             GNode *descendant);

Возвращает TRUE если node предок descendant. Это правильно если узел является родителем descendant, или если узел является родителем родителя descendant и так далее.

`node` :	GNode.
`descendant` :	GNode.
Возвращает :	`TRUE` если `node` является родителем `descendant`.

g_node_max_height ()

guint g_node_max_height (GNode *root);

Определяет максимальную высоту всех переходов от GNode. Это максимальное расстояние от GNode до всех вершин.

Если root это NULL, возвращается 0. Если root не имеет дочерних элементов, возвращается 1. Если root имеет дочерние элементы, возвращается 2. И так далее.

`root` :	GNode.
Возвращает :	максимальная высота дерева от `root`.

g_node_unlink ()

void g_node_unlink (GNode *node);

Сбрасывает ссылки GNode из дерева, получая в качестве результата два разделённых дерева.

node : GNode для разлинковки, который становится корнем нового дерева.

g_node_destroy ()

void g_node_destroy (GNode *root);

Удаляет GNode и дочерние элементы из дерева, освобождает любую распределённую память.

root : корень дерева/поддерева для уничтожения.

g_node_push_allocator ()

void g_node_push_allocator (gpointer dummy);

Внимание

g_node_push_allocator устарела начиная с версии 2.10 и не должна использоваться во вновь создаваемом коде. Она ничего не делает, так как GNode конвертируется в slice allocator

Устанавливает распределитель для распределения элементов GNode. Использует g_node_pop_allocator() для восстановления предыдущего распределителя.

Помните что эта функция не доступна если GLib была скомпилирована с опцией --disable-mem-pools

dummy : GAllocator для распределения элементов GNode.

g_node_pop_allocator ()

void g_node_pop_allocator (void);

Внимание

g_node_pop_allocator устарела начиная с версии 2.10 и не должна использоваться во вновь создаваемом коде. Она ничего не делает, так как GNode конвертируется в slice allocator

Восстанавливает предыдущий GAllocator, используется при распределении элементов GNode.

Помните что эта функция не доступна если GLib скомпилирована с опцией --disable-mem-pools

			Справочное описание GLib
Начало \| Описание