Content-Length: 623348 | pFad | http://github.com/TheAlgorithms/Go/pull/528/files

49 add generics by crunchypi · Pull Request #528 · TheAlgorithms/Go · GitHub
Skip to content

add generics #528

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Sep 9, 2022
Merged

add generics #528

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
26 changes: 13 additions & 13 deletions structure/linkedlist/cyclic.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3,21 +3,21 @@ package linkedlist
import "fmt"

// Cyclic Struct which cycles the linked list in this implementation.
type Cyclic struct {
type Cyclic[T any] struct {
Size int
Head *Node
Head *Node[T]
}

// Create new list.
func NewCyclic() *Cyclic {
return &Cyclic{0, nil}
func NewCyclic[T any]() *Cyclic[T] {
return &Cyclic[T]{}
}

// Inserting the first node is a special case. It will
// point to itself. For other cases, the node will be added
// to the end of the list. End of the list is Prev field of
// current item. Complexity O(1).
func (cl *Cyclic) Add(val any) {
func (cl *Cyclic[T]) Add(val T) {
n := NewNode(val)
cl.Size++
if cl.Head == nil {
Expand Down Expand Up @@ -46,7 +46,7 @@ func (cl *Cyclic) Add(val any) {
// places is the same as moving N - P places back.
// Therefore, if P > N / 2, you can turn the list by N-P places back.
// Complexity O(n).
func (cl *Cyclic) Rotate(places int) {
func (cl *Cyclic[T]) Rotate(places int) {
if cl.Size > 0 {
if places < 0 {
multiple := cl.Size - 1 - places/cl.Size
Expand All @@ -71,9 +71,9 @@ func (cl *Cyclic) Rotate(places int) {
}

// Delete the current item.
func (cl *Cyclic) Delete() bool {
func (cl *Cyclic[T]) Delete() bool {
var deleted bool
var prevItem, thisItem, nextItem *Node
var prevItem, thisItem, nextItem *Node[T]

if cl.Size == 0 {
return deleted
Expand All @@ -97,15 +97,15 @@ func (cl *Cyclic) Delete() bool {
}

// Destroy all items in the list.
func (cl *Cyclic) Destroy() {
func (cl *Cyclic[T]) Destroy() {
for cl.Delete() {
continue
}
}

// Show list body.
func (cl *Cyclic) Walk() *Node {
var start *Node
func (cl *Cyclic[T]) Walk() *Node[T] {
var start *Node[T]
start = cl.Head

for i := 0; i < cl.Size; i++ {
Expand All @@ -117,13 +117,13 @@ func (cl *Cyclic) Walk() *Node {

// https://en.wikipedia.org/wiki/Josephus_problem
// This is a struct-based solution for Josephus problem.
func JosephusProblem(cl *Cyclic, k int) int {
func JosephusProblem(cl *Cyclic[int], k int) int {
for cl.Size > 1 {
cl.Rotate(k)
cl.Delete()
cl.Rotate(-1)
}
retval := cl.Head.Val.(int)
retval := cl.Head.Val
cl.Destroy()
return retval
}
16 changes: 8 additions & 8 deletions structure/linkedlist/cyclic_test.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -5,19 +5,19 @@ import (
"testing"
)

func fillList(list *Cyclic, n int) {
func fillList(list *Cyclic[int], n int) {
for i := 1; i <= n; i++ {
list.Add(i)
}
}

func TestAdd(t *testing.T) {
list := NewCyclic()
list := NewCyclic[int]()
fillList(list, 3)

want := []any{1, 2, 3}
var got []any
var start *Node
var start *Node[int]
start = list.Head

for i := 0; i < list.Size; i++ {
Expand All @@ -30,7 +30,7 @@ func TestAdd(t *testing.T) {
}

func TestWalk(t *testing.T) {
list := NewCyclic()
list := NewCyclic[int]()
fillList(list, 3)

want := 1
Expand All @@ -46,7 +46,7 @@ func TestRotate(t *testing.T) {
param int
wantToReturn int
}
list := NewCyclic()
list := NewCyclic[int]()
fillList(list, 3)

testCases := []testCase{
Expand All @@ -69,7 +69,7 @@ func TestRotate(t *testing.T) {
}

func TestDelete(t *testing.T) {
list := NewCyclic()
list := NewCyclic[int]()
fillList(list, 3)

want := 2
Expand All @@ -85,7 +85,7 @@ func TestDelete(t *testing.T) {
}

func TestDestroy(t *testing.T) {
list := NewCyclic()
list := NewCyclic[int]()
fillList(list, 3)
wantSize := 0
list.Destroy()
Expand Down Expand Up @@ -119,7 +119,7 @@ func TestJosephusProblem(t *testing.T) {
}

for _, tCase := range testCases {
list := NewCyclic()
list := NewCyclic[int]()
fillList(list, tCase.listCount)
got := JosephusProblem(list, tCase.param)
if got != tCase.wantToReturn {
Expand Down
38 changes: 20 additions & 18 deletions structure/linkedlist/doubly.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -15,16 +15,16 @@ import "fmt"
// `import "github.com/TheAlgorithms/Go/structure/linkedlist"`
//
// and call linkedlist.Doubly to create a new doubly linked list.
type Doubly struct {
Head *Node
type Doubly[T any] struct {
Head *Node[T]
}

func NewDoubly() *Doubly {
return &Doubly{nil}
func NewDoubly[T any]() *Doubly[T] {
return &Doubly[T]{}
}

// AddAtBeg Add a node to the beginning of the linkedlist
func (ll *Doubly) AddAtBeg(val any) {
func (ll *Doubly[T]) AddAtBeg(val T) {
n := NewNode(val)
n.Next = ll.Head

Expand All @@ -37,7 +37,7 @@ func (ll *Doubly) AddAtBeg(val any) {
}

// AddAtEnd Add a node at the end of the linkedlist
func (ll *Doubly) AddAtEnd(val any) {
func (ll *Doubly[T]) AddAtEnd(val T) {
n := NewNode(val)

if ll.Head == nil {
Expand All @@ -53,9 +53,10 @@ func (ll *Doubly) AddAtEnd(val any) {
}

// DelAtBeg Delete the node at the beginning of the linkedlist
func (ll *Doubly) DelAtBeg() any {
func (ll *Doubly[T]) DelAtBeg() (T, bool) {
if ll.Head == nil {
return -1
var r T
return r, false
}

cur := ll.Head
Expand All @@ -64,14 +65,15 @@ func (ll *Doubly) DelAtBeg() any {
if ll.Head != nil {
ll.Head.Prev = nil
}
return cur.Val
return cur.Val, true
}

// DetAtEnd Delete a node at the end of the linkedlist
func (ll *Doubly) DelAtEnd() any {
func (ll *Doubly[T]) DelAtEnd() (T, bool) {
// no item
if ll.Head == nil {
return -1
var r T
return r, false
}

// only one item
Expand All @@ -86,11 +88,11 @@ func (ll *Doubly) DelAtEnd() any {

retval := cur.Next.Val
cur.Next = nil
return retval
return retval, true
}

// Count Number of nodes in the linkedlist
func (ll *Doubly) Count() any {
func (ll *Doubly[T]) Count() int {
var ctr int = 0

for cur := ll.Head; cur != nil; cur = cur.Next {
Expand All @@ -101,8 +103,8 @@ func (ll *Doubly) Count() any {
}

// Reverse Reverse the order of the linkedlist
func (ll *Doubly) Reverse() {
var Prev, Next *Node
func (ll *Doubly[T]) Reverse() {
var Prev, Next *Node[T]
cur := ll.Head

for cur != nil {
Expand All @@ -117,7 +119,7 @@ func (ll *Doubly) Reverse() {
}

// Display display the linked list
func (ll *Doubly) Display() {
func (ll *Doubly[T]) Display() {
for cur := ll.Head; cur != nil; cur = cur.Next {
fmt.Print(cur.Val, " ")
}
Expand All @@ -126,11 +128,11 @@ func (ll *Doubly) Display() {
}

// DisplayReverse Display the linkedlist in reverse order
func (ll *Doubly) DisplayReverse() {
func (ll *Doubly[T]) DisplayReverse() {
if ll.Head == nil {
return
}
var cur *Node
var cur *Node[T]
for cur = ll.Head; cur.Next != nil; cur = cur.Next {
}

Expand Down
30 changes: 18 additions & 12 deletions structure/linkedlist/doubly_test.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -6,7 +6,7 @@ import (
)

func TestDoubly(t *testing.T) {
newList := NewDoubly()
newList := NewDoubly[int]()

newList.AddAtBeg(1)
newList.AddAtBeg(2)
Expand All @@ -20,11 +20,11 @@ func TestDoubly(t *testing.T) {
// check from Next address
current := newList.Head

got = append(got, current.Val.(int))
got = append(got, current.Val)

for current.Next != nil {
current = current.Next
got = append(got, current.Val.(int))
got = append(got, current.Val)
}

if !reflect.DeepEqual(got, wantNext) {
Expand All @@ -33,11 +33,11 @@ func TestDoubly(t *testing.T) {

// check from Prev address
got = []int{}
got = append(got, current.Val.(int))
got = append(got, current.Val)

for current.Prev != nil {
current = current.Prev
got = append(got, current.Val.(int))
got = append(got, current.Val)
}

if !reflect.DeepEqual(got, wantPrev) {
Expand All @@ -51,10 +51,10 @@ func TestDoubly(t *testing.T) {
want := []int{3, 2, 1, 4}
got := []int{}
current := newList.Head
got = append(got, current.Val.(int))
got = append(got, current.Val)
for current.Next != nil {
current = current.Next
got = append(got, current.Val.(int))
got = append(got, current.Val)
}
if !reflect.DeepEqual(got, want) {
t.Errorf("got: %v, want: %v", got, want)
Expand All @@ -63,15 +63,21 @@ func TestDoubly(t *testing.T) {

t.Run("Test DelAtBeg", func(t *testing.T) {
want := 3
got := newList.DelAtBeg()
got, ok := newList.DelAtBeg()
if !ok {
t.Error("unexpected not-ok")
}
if got != want {
t.Errorf("got: %v, want: %v", got, want)
}
})

t.Run("Test DelAtEnd", func(t *testing.T) {
want := 4
got := newList.DelAtEnd()
got, ok := newList.DelAtEnd()
if !ok {
t.Error("unexpected not-ok")
}
if got != want {
t.Errorf("got: %v, want: %v", got, want)
}
Expand All @@ -85,7 +91,7 @@ func TestDoubly(t *testing.T) {
}
})

newList2 := NewDoubly()
newList2 := NewDoubly[int]()
newList2.AddAtBeg(1)
newList2.AddAtBeg(2)
newList2.AddAtBeg(3)
Expand All @@ -94,10 +100,10 @@ func TestDoubly(t *testing.T) {
got := []int{}
newList2.Reverse()
current := newList2.Head
got = append(got, current.Val.(int))
got = append(got, current.Val)
for current.Next != nil {
current = current.Next
got = append(got, current.Val.(int))
got = append(got, current.Val)
}
if !reflect.DeepEqual(got, want) {
t.Errorf("got: %v, want: %v", got, want)
Expand Down
12 changes: 6 additions & 6 deletions structure/linkedlist/shared.go
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -2,13 +2,13 @@ package linkedlist

// Node Structure representing the linkedlist node.
// This node is shared across different implementations.
type Node struct {
Val any
Prev *Node
Next *Node
type Node[T any] struct {
Val T
Prev *Node[T]
Next *Node[T]
}

// Create new node.
func NewNode(val any) *Node {
return &Node{val, nil, nil}
func NewNode[T any](val T) *Node[T] {
return &Node[T]{val, nil, nil}
}
Loading








ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: http://github.com/TheAlgorithms/Go/pull/528/files

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy