[ новости /+++ | форум | теги | ]

Каталог документации / Раздел "Программирование, языки" / Оглавление документа

Вперед: 2.2.3 Хэш-таблицы Назад: GTree

GNode

GNode - это N-направленное дерево, реализованное как двусвязный список с родителем и списком детей. Поэтому, большинство операций со списками имеют аналоги в API GNode. Вы также можете проходить дерево различными способами. Вот объявление узла:

typedef struct _GNode GNode;

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

g_node_prev_sibling(node)
g_node_next_sibling(node)
g_node_first_child(node)

Для создания узла предоставляется обычная функция "_new()" (список функций 2..16). "g_node_new()" создает узел без детей и родителей, содержащий data. Обычно, "g_node_new()" используется только для создания корневого узла; есть удобные макросы, которые автоматически создают новые узлы при необходимости.

GNode *g_node_new(gpointer data)

Для построения дерева используются операции, приведенные в списке функций 2..17. Каждая операция возвращает только что добавленный узел, для удобства при написании циклов или прохождении дерева. В отличии от GList, возвращаемое значение можно безопасно проигнорировать.

GNode *g_node_insert(GNode *parent, gint position,
                     GNode *node)
GNode *g_node_insert_before(GNode *parent, GNode *sibling,
                            GNode *node)
GNode *g_node_prepend(GNode *parent, GNode *node)

Удобные макросы, показанные в списке макросов 2..7 реализованы в терминах фундаментальных операций. "g_node_append()" аналогичен "g_node_prepend()"; остальные берут аргумент data, автоматически выделяя для него узел, и вызывают соответствующую базовую операцию.

g_node_append(parent, node)
g_node_insert_data(parent, position, data)
g_node_insert_data_before(parent, sibling, data)
g_node_prepend_data(parent, data)
g_node_append_data(parent, data)

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

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

Есть два макроса для определения вершины и низа дерева GNode, показанные в списке макросов 2..8. Корневой узел определен как узел без родителя и одноуровневых элементов. Листовой узел не имеет детей.

G_NODE_IS_ROOT(node)
G_NODE_IS_LEAF(node)

Вы можете попросить у glib нужную информацию о GNode, включая число узлов, которое оно содержит, его корневой узел, его глубину и узел, содержащий определенный указатель на данные. Эти функции приведены в списке функций 2..19.

GTraverseType был введен ранее, по отношению к GTree; вот возможные значения для GNode:

• "G_NODE_ORDER" сначала обходит левого ребенка, затем сам узел, затем остальных детей узла. Это не очень полезно; в основном это предназначено для использования с GTree.
• "G_PRE_ORDER" обходит текущий узел, затем каждого ребенка.
• "G_POST_ORDER" обходит каждого ребенка, а затем текущий узел.
• "G_LEVEL_ORDER" сначала обходит сам узел; затем каждого ребенка узла; затем детей детей; затем детей детей детей; и так далее. Таким образом, он обходит каждый узел глубины 0, затем каждый узел глубины 1, каждый узел глубины 2 и так далее.

Функции для обхода дерева GNode имеют аргумент GTraverseFlags. Это битовое поле, используемое для изменения природы обхода. В настоящее время существуют только три флага -- вы можете обходить только листовые узлы, только нелистовые узлы, или все узлы:

• "G_TRAVERSE_LEAFS" означает, что обходить надо только листовые узлы.
• "G_TRAVERSE_NON_LEAFS" означает, что обходить надо только нелистовые узлы.
• "G_TRAVERSE_ALL" -- это просто обозначение для "(G_TRAVERSE_LEAFS | G_TRAVERSE_NON_LEAFS)".

guint g_node_n_nodes(GNode *root, GTraverseFlags flags)
GNode *g_node_get_root(GNode *node)
gboolean g_node_is_ancestor(GNode *node, GNode *descendant)
guint g_node_depth(GNode *node)
GNode *g_node_find(GNode *root, GTraverseType order,
                   GTraverseFlags flags, gpointer data)

Остальные функции GNode прямолинейны; большинство из них просто являются операциями над списком детей узла. Они приведены в списке функций 2..20. Есть также два определения функций только для GNode:

typedef gboolean (*GNodeTraverseFunc) (GNode *node, gpointer data);
typedef void (*GNodeForeachFunc) (GNode *node, gpointer data);

void g_node_traverse(GNode *root, GTraverseType order,
                     GTraverseFlags flags, gint max_depth,
                     GNodeTraverseFunc func, gpointer data)
guint g_node_max_height(GNode *root)
void g_node_children_foreach(GNode *node, GTraverseFlags flags,
                             GNodeForeachFunc func, gpointer data)
void g_node_reverse_children(GNode *node)
guint g_node_n_children(GNode *node)
GNode *g_node_nth_child(GNode *node, guint n)
GNode *g_node_last_child(GNode *node)
GNode *g_node_find_child(GNode *node, GTraverseFlags flags,
                         gpointer data)
gint g_node_child_position(GNode *node, GNode *child)
gint g_node_child_index(GNode *node, gpointer data)
GNode *g_node_first_sibling(GNode *node)
GNode *g_node_last_sibling(GNode *node)

---

Партнёры:

Хостинг: