Целочисленная очередь с двойным окончанием GO

В настоящее время я изучаю Go, и я решил реализовать структуру кругового двусвязного списка (Deque) для обучения. Го — не мой родной язык. Я программирую в основном на Python, поэтому я хотел бы узнать, следует ли код структуре и идиомам Go, и есть ли у вас какие-либо советы по улучшению.

О коде:

Это круговая структура данных двусвязного списка, поэтому идея состоит в том, чтобы иметь O (1) доступ для добавления / удаления / просмотра элементов в начале / конце списка и без доступа к элементам между ними. Я реализовал методы для добавления и удаления элементов, а также для представления списка в виде строки и сравнения двух списков. deque.test также содержит тестовые примеры для каждого из методов.

Здесь я использую связанный список, но я понимаю, что то же самое можно достичь с помощью срезов (возможно, более эффективно), но моей вторичной целью было привыкнуть к указателям и ссылкам — поскольку они не отображаются в Python.

Вопрос по коду:

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

  • Когда deque пуста, и я пытаюсь извлечь элемент, метод вызовет панику, чтобы остановить выполнение программы, вместо того, чтобы возвращать ошибку. Это хорошая практика в Go? Должен ли я вместо этого возвращать значение и ошибку из pop (мне кажется немного неудобным требовать обработки возможной ошибки пустого списка каждый раз, когда элемент выталкивается).

Структура проекта

collections/
- cmd/
- - main.go
- deque/
- - deque.go       
- - deque_test.go  
- - node.go
- - test_cases.go
- some_other_collection/
- - ... 

deque.go

// Package deque implements deque type and common methods to interact with
// deque.
package deque

import (
    "strconv"
    "strings"
)

// Deque is implemented as circular doubly linked list with sentinel node.
// This allows for O(1) non-amortized add/remove operations for both ends
// of the structure. This makes it a perfect implementation of queue data
// structure.
type Deque struct {
    sentinel *IntNode
    length   int
}

// Constructor for new empty deque.
func New() Deque {
    sentinel := &IntNode{0, nil, nil}
    sentinel.prev = sentinel
    sentinel.next = sentinel
    return Deque{sentinel, 0}
}

// Constructor for new empty deque populated with elements from slice.
func FromSlice(slice []int) Deque {
    deq := New()
    for _, val := range slice {
        deq.Append(val)
    }
    return deq
}

// Append adds element to the end of the deque.
func (d *Deque) Append(elem int) {
    newNode := IntNode{value: elem, next: d.sentinel, prev: d.sentinel.prev}
    d.sentinel.prev.next = &newNode
    d.sentinel.prev = &newNode
    d.length += 1
}

// AppendLeft adds element to the front of the deque.
func (d *Deque) AppendLeft(elem int) {
    newNode := IntNode{value: elem, next: d.sentinel.next, prev: d.sentinel}
    d.sentinel.next.prev = &newNode
    d.sentinel.next = &newNode
    d.length += 1
}

// Pop removes and returns last element in deque.
func (d *Deque) Pop() int {
    if d.Empty() {
        panic("popping from empty list")
    }
    value := d.sentinel.prev.value
    d.sentinel.prev.prev.next = d.sentinel
    d.sentinel.prev = d.sentinel.prev.prev
    d.length -= 1
    return value
}

// Pop removes and returns first element in deque.
func (d *Deque) PopLeft() int {
    if d.Empty() {
        panic("popping from empty list")
    }
    value := d.sentinel.next.value
    d.sentinel.next.next.prev = d.sentinel
    d.sentinel.next = d.sentinel.next.next
    d.length -= 1
    return value
}

// Last return value of the first element in deque.
func (d *Deque) First() int {
    return d.sentinel.next.value
}

// Last return value of the last element in deque.
func (d *Deque) Last() int {
    return d.sentinel.prev.value
}

// Length returns number of elements in deque.
func (d *Deque) Length() int {
    return d.length
}

// Empty checks if there are any elements in deque.
func (d *Deque) Empty() bool {
    return d.length == 0
}

// String outputs string representation of deque.
func (d *Deque) String() string {
    var b strings.Builder
    curr := d.sentinel.next
    b.WriteString("Deque{")
    for i := 0; i < d.Length(); i++ {
        b.WriteString(strconv.Itoa(curr.value))
        b.WriteString(",")
        curr = curr.next
    }
    b.WriteString("}")
    return b.String()
}

// Equals checks if both deques contain same elements in the same order.
func (d *Deque) Equals(other *Deque) bool {
    if d.Length() != other.Length() {
        return false
    }
    curr := d.sentinel.next
    otherCurr := other.sentinel.next
    for i := 0; i < d.Length(); i++ {
        if curr.value != otherCurr.value {
            return false
        }
        curr = curr.next
        otherCurr = otherCurr.next
    }
    return true
}

node.go

package deque

type IntNode struct {
    value int
    next  *IntNode
    prev  *IntNode
}

deque_test.go

package deque

import (
    "testing"

    "github.com/stretchr/testify/assert"
)

func TestEquals(t *testing.T) {
    for _, tc := range TestCasesEquals {
        if tc.this.Equals(&tc.other) != tc.expected {
            t.Errorf(tc.msg)
        }
    }
}

func TestAppend(t *testing.T) {
    for _, tc := range TestCasesAppend {
        actual := tc.actual()
        if !actual.Equals(&tc.expected) {
            t.Errorf(tc.msg)
        }
    }
}

func TestAppendLeft(t *testing.T) {
    for _, tc := range TestCasesAppendLeft {
        actual := tc.actual()
        if !actual.Equals(&tc.expected) {
            t.Errorf(tc.msg, actual, tc.expected)
        }
    }
}

func TestPop(t *testing.T) {
    // Main test cases
    for _, tc := range TestCasesPop {
        deque, popped := tc.actual()
        if !deque.Equals(&tc.expectedDeque) || popped != tc.expectedPopped {
            t.Errorf(tc.msg)
        }
    }

    // Popping from empty list
    poppingEmpty := func() {
        d := FromSlice([]int{})
        d.Pop()
    }
    assert.Panics(t, poppingEmpty, "popping from empty deque")
}

func TestPopLeft(t *testing.T) {
    // Main test cases
    for _, tc := range TestCasesPopLeft {
        deque, popped := tc.actual()
        if !deque.Equals(&tc.expectedDeque) || popped != tc.expectedPopped {
            t.Errorf(tc.msg)
        }
    }

    // Popping from empty list
    poppingEmpty := func() {
        d := FromSlice([]int{})
        d.Pop()
    }
    assert.Panics(t, poppingEmpty, "popping from empty deque")
}

func TestString(t *testing.T) {
    d := New()
    if d.String() != "Deque{}" {
        t.Errorf("empty deque; got: %v", d.String())
    }

    d = FromSlice([]int{1, 2, 7, 4})
    if d.String() != "Deque{1,2,7,4,}" {
        t.Errorf("4 element deque; got: %v", d.String())
    }
}

test_cases.go

package deque

type TestCaseEquals struct {
    this     Deque
    other    Deque
    expected bool
    msg      string
}

var TestCasesEquals = []TestCaseEquals{
    {
        this:     New(),
        other:    New(),
        expected: true,
        msg:      "two empty deques",
    },
    {
        this:     FromSlice([]int{1, 2, 3}),
        other:    FromSlice([]int{1, 2, 3}),
        expected: true,
        msg:      "two identical, 3-element deques",
    },
    {
        this:     FromSlice([]int{1, 2, 3}),
        other:    FromSlice([]int{1, 2, 4}),
        expected: false,
        msg:      "same length, last element mismatching",
    },
    {
        this:     FromSlice([]int{1, 2, 3}),
        other:    FromSlice([]int{1, 2}),
        expected: false,
        msg:      "different length, elements matching",
    },
}

type TestCaseAppend struct {
    actual   func() Deque
    expected Deque
    msg      string
}

var TestCasesAppend = []TestCaseAppend{
    {
        actual: func() Deque {
            return New()
        },
        expected: New(),
        msg:      "2 empty deques",
    },
    {
        actual: func() Deque {
            d := New()
            d.Append(1)
            return d
        },
        expected: FromSlice([]int{1}),
        msg:      "adding one element to deque",
    },
    {
        actual: func() Deque {
            d := New()
            d.Append(1)
            d.Append(3)
            d.Append(5)
            d.Append(19)
            return d
        },
        expected: FromSlice([]int{1, 3, 5, 19}),
        msg:      "adding multiple elements to deque",
    },
}

var TestCasesAppendLeft = []TestCaseAppend{
    {
        actual: func() Deque {
            d := New()
            d.AppendLeft(1)
            return d
        },
        expected: FromSlice([]int{1}),
        msg:      "adding one element to deque. Got: %v, Expected: %v",
    },
    {
        actual: func() Deque {
            d := New()
            d.AppendLeft(1)
            d.AppendLeft(3)
            d.AppendLeft(5)
            d.AppendLeft(19)
            return d
        },
        expected: FromSlice([]int{19, 5, 3, 1}),
        msg:      "adding multiple elements to deque. Got: %v, Expected: %v",
    },
}

type TestCasePop struct {
    actual         func() (Deque, int)
    expectedDeque  Deque
    expectedPopped int
    msg            string
}

var TestCasesPop = []TestCasePop{
    {
        actual: func() (Deque, int) {
            d := FromSlice([]int{1})
            val := d.Pop()
            return d, val
        },
        expectedDeque:  New(),
        expectedPopped: 1,
        msg:            "popping from deque with 1 element",
    },
    {
        actual: func() (Deque, int) {
            d := FromSlice([]int{1, 2, 3})
            val := d.Pop()
            return d, val
        },
        expectedDeque:  FromSlice([]int{1, 2}),
        expectedPopped: 3,
        msg:            "popping from deque with 3 elements",
    },
    {
        actual: func() (Deque, int) {
            d := FromSlice([]int{1, 2, 3})
            d.Pop()
            val := d.Pop()
            return d, val
        },
        expectedDeque:  FromSlice([]int{1}),
        expectedPopped: 2,
        msg:            "popping twice from deque with 3 elements",
    },
}

var TestCasesPopLeft = []TestCasePop{
    {
        actual: func() (Deque, int) {
            d := FromSlice([]int{1})
            val := d.PopLeft()
            return d, val
        },
        expectedDeque:  New(),
        expectedPopped: 1,
        msg:            "popping from deque with 1 element",
    },
    {
        actual: func() (Deque, int) {
            d := FromSlice([]int{1, 2, 3})
            val := d.PopLeft()
            return d, val
        },
        expectedDeque:  FromSlice([]int{2, 3}),
        expectedPopped: 1,
        msg:            "popping from deque with 3 elements",
    },
    {
        actual: func() (Deque, int) {
            d := FromSlice([]int{1, 2, 3})
            d.PopLeft()
            val := d.PopLeft()
            return d, val
        },
        expectedDeque:  FromSlice([]int{3}),
        expectedPopped: 2,
        msg:            "popping twice from deque with 3 elements",
    },
}

```

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *