2024-04-25 04:52:37 UTC

Поговорим сегодня о новом языковом механизме языка Go, — generics или шаблонах, если говорить в терминах C++, появившемся в языке, начиная с версии 1.18. Речь пойдет не об объяснении этого механизма своими словами (по сути пересказ документации или других статей, но своими словами), а о популярном утверждении о том, что их удобно использовать для реализации обобщенных деревьев (структура данных), не приколоченных гвоздями к какому-то конкретному типу данных.

Спойлер — нет, это не так удобно и очевидно, как кажется, ну а теперь раскроем это подробнее. Сначала о предмете разговора — я буду говорить о реализации некоего двоичного дерева, сбалансированного или нет, не суть важно, но для определенности, давайте рассматривать сбалансированное дерево.

Основная структура, которая представляет узел такого дерева, может выглядеть следующим образом:

type Node struct {
   key Comparable
   color  int
   parent *Node
   left   *Node
   right  *Node
}

Пояснения тут думаю излишни, за исключением поля key — это собственно сами данные (ключи), хранящиеся в дереве. Эти данные имеют в нашем определении тип Comparable. Что же это такое? В нашем случае это интерфейс, который имеет всего два метода:

type Comparable interface {
    Less(y Comparable) bool
    Equal(y Comparable) bool
}

Т.е. для сущностей (ключи) хранящихся в дереве, нам нужно всего 2 вещи — чтобы мы знали как их сравнивать а также, как их упорядочивать (в нашем случае нам надо знать что одно меньше другого). Эти вещи необходимы нам например при поиске в дереве или при его модификации (вставка, удаление). Пример поиска:

func (n *Node) search(value Comparable) (*Node, bool) {
    if value == nil {
        return nil, false
    }
    var x *Node
    x = n
    for x.isNotNil() && !value.Equal(x.key) {
        if value.Less(x.key) {
            x = x.left
        } else {
            x = x.right
        }
    }

    if x.isNil() {
        return nil, false
    }

    return x, true
}

func (n *Node) isNil() bool {
    return n == nil || n.key == nil
}

func (n *Node) isNotNil() bool {
    return n != nil && n.key != nil
}

Вариант с использованием ограничения (constraint), мог бы выглядеть примерно так:

 type Node[T comparable] struct {
    key T
    color  int
    parent *Node
    left   *Node
    right  *Node
}

func (n *Node[T]) search(value T) (*Node[T], bool) {
    if value == nil {
        return nil, false
    }
    var x *Node
    x = n
    for x.isNotNil() && value != x.key {
        if value < x.key {
            x = x.left
        } else {
            x = x.right
        }
    }

    if x.isNil() {
        return nil, false
    }

    return x, true
}

Но в этом случае мы будем ограничены лишь системными типами, удовлетворяющими этому (comparable) ограничению, что ограничивает нас, по сути, только числами и строками, а также структурами, содержащими только comparable члены. Никакой гибкости, например использования только одного члена структуры, для операций упорядочивания и сравнения, в этом случае, получить нельзя. В случае использования интерфейса, мы вольны реализовывать интерфейс как душе угодно. Например, мы хотим хранить в дереве некие папки файловой системы, в этом случае реализация могла бы быть следующей:

import (
    "github.com/akutz/sortfold"
    "strings"
)

// ...

type Folder struct {
    Content *FolderContent
    Path    string
}

func (x *Folder) Less(y Comparable) bool {
    return sortfold.CompareFold(x.Path, y.(*Folder).Path) < 0
}

func (x *Folder) Equal(y Comparable) bool {
    return strings.EqualFold(x.Path, y.(*Folder).Path)
}

// ...

Да, у подхода с интерфейсом тоже есть минусы, — например для системных типов, вместо непосредственного использования в дереве, необходимо делать псевдоним и реализацию интерфейса:

type Int64 int64
type String string

func (x Int64) Less(y Comparable) bool {
    return x < y.(Int64)
}

func (x Int64) Equal(y Comparable) bool {
    return x == y
}

func (x *String) Less(y Comparable) bool {
    return *x < *(y.(*String))
}

func (x *String) Equal(y Comparable) bool {
    return *x == *(y.(*String))
}

func NewString(v string) Comparable {
    s := String(v)
    return &s
}

И это, является необходимым злом (компромиссом) при использовании подхода с интерфейсом, так сказать, плата за гибкость. Что выбрать в конкретном случае — зависит от решаемой задачи и однозначного рецепта конечно нет.

Все описанное выше, можно посмотреть и использовать в своих проектах с помощью моей маленькой библиотеки godatastuct.