package main

import (
        "github.com/gdamore/tcell/v2"
        "github.com/rivo/tview"
)

type Contact struct {
        firstName   string
        lastName    string
        email       string
        phoneNumber string
        state       string
        business    bool
}

var contacts []Contact

var app = tview.NewApplication()
var text = tview.NewTextView().
        SetTextColor(tcell.ColorGreen).
        SetText("(q) to quit")

func main() {
        if err := app.SetRoot(text, true).EnableMouse(true).Run(); err != nil {
                panic(err)
        }
}

package adt

import (
        "cmp"
        "fmt"
)

// Node represents a single node in linked list representation.
type Node[T any] struct {
        data T
        next *Node[T]
}

// NewNode creates an instance of Node with the data provided.
func NewNode[T any](data T) *Node[T] {
        return &Node[T]{
                data: data,
                next: nil,
        }
}

// Data returns the data from the Node.
func (n *Node[T]) Data() T {
        return n.data
}

// Display displays the node to the console.
func (n *Node[T]) Display() {
        fmt.Printf("%+v\n", n)
}

// TreeNode represents a node in a tree data structure.
type TreeNode[T cmp.Ordered] struct {
        data  T
        left  *TreeNode[T]
        right *TreeNode[T]
}

func NewTreeNode[T cmp.Ordered](data T) *TreeNode[T] {
        return &TreeNode[T]{
                data:  data,
                left:  nil,
                right: nil,
        }
}

package adt

import (
        "errors"
        "fmt"
)

// Queue like Stack, is also an abstract data structure.
// The thing that makes queue different from stack is that a queue is open at both its ends.
// Hence, it follows FIFO (First-In-First-Out) structure, i.e. the data item inserted first will also be accessed first.
// The data is inserted into the queue through one end and deleted from it using the other end.
type Queue[T any] struct {
        front *Node[T]
        rear  *Node[T]
        next  *Node[T]
        size  uint
}

// NewQueue creates an empty queue.
func NewQueue[T any]() *Queue[T] {
        return &Queue[T]{
                front: nil,
                rear:  nil,
                next:  nil,
        }
}

// IsEmpty checks if queue is empty or not.
func (q *Queue[T]) IsEmpty() bool {
        return q.rear == nil && q.front == nil && q.size == 0
}

// Size returns the size of the queue.
func (q *Queue[T]) Size() uint {
        return q.size
}

// Display prints the queue to the console
func (q *Queue[T]) Display() {
        if q.IsEmpty() {
                fmt.Println("queue is empty")
                return
        }

        node := q.front
        for {
                node.Display()
                if node.next == nil {
                        break
                }
                node = node.next
        }
}

// Front returns the front node in the queue, w/o deleting it.
// If Queue is empty, then it will return nil.
func (q *Queue[T]) Front() T {
        if q.IsEmpty() {
                var nothing T
                return nothing
        }
        return q.front.data
}

// Rear returns the rear node in the queue, w/o deleting it.
// If Queue is empty, then it will return nil.
func (q *Queue[T]) Rear() T {
        if q.IsEmpty() {
                var nothing T
                return nothing
        }
        return q.rear.data
}

// EnQueue is a data manipulation operation that inserts an element into the queue.
func (q *Queue[T]) EnQueue(data T) {

        // node to insert
        node := NewNode[T](data)

        // If queue is empty, both front and rear point to same node.
        if q.IsEmpty() {
                q.front = node
                q.rear = node
                q.size++
                return
        }

        node.next = q.front
        q.front = node
        q.size++
}

// DeQueue is a data manipulation operation that removes an element from the queue and returns it.
// If the queue is empty, it sets error.
func (q *Queue[T]) DeQueue() (T, error) {

        if q.IsEmpty() {
                var nothing T
                return nothing, errors.New("queue is empty")
        }

        // traverse to penultimate node
        node := q.front
        count := 1
        for {
                if uint(count) == q.Size()-1 {
                        break
                }
                node = node.next
                count++
        }

        // Grab the last node and unlink it from queue, by pointing rear to
        // penultimate node
        lastNode := node.next
        node.next = nil
        q.rear = node
        q.size--
        return lastNode.Data(), nil
}

package adt

import (
        "errors"
        "fmt"
)

// Stack represents the abstract data structure stack.
// It uses linked list representation to maintain the stack.
type Stack[T any] struct {
        top  *Node[T]
        size uint
}

// NewStack creates an empty stack.
func NewStack[T any]() *Stack[T] {
        return &Stack[T]{top: nil}
}

// Size returns the size of the stack.
func (s *Stack[T]) Size() uint {
        return s.size
}

// IsEmpty checks if the stack is empty or not.
// This is called when performing any of Push, Pop and Display operations.
func (s *Stack[T]) IsEmpty() bool {
        return s.top == nil && s.Size() == 0
}

// Top returns the top element from the stack, w/o deleting it.
func (s *Stack[T]) Top() T {
        return s.top.data
}

// Push pushes new element to top of the stack.
func (s *Stack[T]) Push(data T) {

        node := NewNode[T](data)

        if s.IsEmpty() {
                s.top = node
                s.size++
                return
        }

        currentTop := s.top
        node.next = currentTop
        s.top = node
        s.size++
        return
}

// Pop removes the top node from the stack and returns it.
func (s *Stack[T]) Pop() (T, error) {

        if s.IsEmpty() {
                var nothing T
                return nothing, errors.New("stack is empty")
        }

        poppedNode := s.top
        s.top = poppedNode.next
        poppedNode.next = nil
        s.size--
        return poppedNode.Data(), nil
}

// Display prints the stack to the console.
func (s *Stack[T]) Display() {
        if s.IsEmpty() {
                fmt.Println("stack is empty")
                return
        }

        node := s.top
        for {
                node.Display()
                if node.next == nil {
                        break
                }
                node = node.next
        }

        return
}

package adt

import (
        "cmp"
        "fmt"
)

type Tree[T cmp.Ordered] struct {
        root  *TreeNode[T]
        level int
}

type TraversalType int

const (
        PreOrder TraversalType = iota
        InOrder
        PostOrder
)

// NewBinaryTree creates an empty tree.
func NewBinaryTree[T cmp.Ordered]() *Tree[T] {
        return &Tree[T]{root: nil}
}

func (t *Tree[T]) IsEmpty() bool {
        return t.root == nil
}

// Insert inserts data into the tree.
func (t *Tree[T]) Insert(data T) {

        node := NewTreeNode[T](data)

        // if tree is empty, point root to the node
        if t.IsEmpty() {
                t.root = node
                return
        }

        var (
                current              = t.root
                parent  *TreeNode[T] = nil
        )

        for {
                parent = current
                if node.data < parent.data {
                        current = current.left
                        if current == nil {
                                parent.left = node
                                return
                        }
                } else {
                        current = current.right
                        if current == nil {
                                parent.right = node
                                return
                        }
                }
        }
}

// Traverse prints the tree data based on TraversalType.
func (t *Tree[T]) Traverse(tType TraversalType) {

        if t.IsEmpty() {
                fmt.Println("tree is empty")
                return
        }

        switch tType {
        case InOrder:
                inOrder(t.root)
        case PreOrder:
                preOrder(t.root)
        case PostOrder:
                postOrder(t.root)
        }
}

func inOrder[T cmp.Ordered](root *TreeNode[T]) {
        if root != nil {
                inOrder[T](root.left)
                fmt.Printf("%v ", root.data)
                inOrder[T](root.right)
        }
}

func preOrder[T cmp.Ordered](root *TreeNode[T]) {
        if root != nil {
                fmt.Printf("%v ", root.data)
                preOrder[T](root.left)
                preOrder[T](root.right)
        }
}

func postOrder[T cmp.Ordered](root *TreeNode[T]) {
        if root != nil {
                postOrder[T](root.left)
                postOrder[T](root.right)
                fmt.Printf("%v ", root.data)
        }
}

package applns

import (
        "github.com/codelabs/gobank/lib/v1/adt"
        "strings"
)

type Operator string

const (
        plus             Operator = "+"
        minus            Operator = "-"
        multiplication   Operator = "*"
        division         Operator = "/"
        exponent         Operator = "^"
        openParenthesis  Operator = "("
        closeParenthesis Operator = ")"
        pound            Operator = "#"
)

// operatorPrecedence returns the precedence value for an Operator.
func operatorPrecedence(op string) int {

        var precedence int

        switch Operator(op) {
        case pound:
                precedence = 1
        case plus, minus:
                precedence = 2
        case multiplication, division:
                precedence = 3
        case openParenthesis, closeParenthesis, exponent:
                precedence = 4
        }

        return precedence
}

// isOperator returns true if selected symbol is one of the Operator, otherwise false.
func isOperator(symbol string) bool {
        switch Operator(symbol) {
        case plus, minus, multiplication, division, exponent, openParenthesis, closeParenthesis, pound:
                return true
        }
        return false
}

// ConvertToPostFix converts the infix expression to postfix expression and returns it.
func ConvertToPostFix(infix string) string {

        postfix := make([]string, 0)
        input := strings.Split(infix, "")
        stack := adt.NewStack[string]()

        for _, symbol := range input {

                // Push to stack if symbol is (
                if symbol == string(openParenthesis) {
                        stack.Push(symbol)
                        continue
                }

                // If symbol is ), pop from stack until we encounter (.
                // Append popped symbol to postfix string, ignoring both ( and ).
                if symbol == string(closeParenthesis) {
                        for {
                                if stack.IsEmpty() {
                                        break
                                }
                                operator, _ := stack.Pop()
                                if operator == string(openParenthesis) {
                                        break
                                }
                                postfix = append(postfix, operator)
                        }
                        continue
                }

                // If symbol is not operator, just append to postfix string
                if !isOperator(symbol) {
                        postfix = append(postfix, symbol)
                        continue
                }

                // If stack is empty, just push to stack
                if stack.IsEmpty() {
                        stack.Push(symbol)
                        continue
                }

                // If top of stack has higher precedence than current symbol,
                // pop from stack and append to postfix string.
                // Repeat this until top of stack has lesser precedence or till stack becomes empty.
                for {

                        if stack.IsEmpty() {
                                break
                        }

                        top := stack.Top()

                        if top != "(" && operatorPrecedence(top) > operatorPrecedence(symbol) {
                                operator, _ := stack.Pop()
                                postfix = append(postfix, operator)
                        } else {
                                break
                        }
                }

                // if top of stack has lesser precedence than symbol, push to stack
                stack.Push(symbol)
        }

        // When all the symbols from input are processed, whatever left in
        // the stack pop it and append to postfix string
        for !stack.IsEmpty() {
                operator, _ := stack.Pop()
                postfix = append(postfix, operator)
        }

        return strings.Join(postfix, "")
}

package linkedlist

import "fmt"

// Node represents a node in a single or double linked list.
type Node struct {
        data int
        next *Node
        prev *Node
}

// PrintSingleLL prints a node.
func (n *Node) PrintSingleLL() {
        fmt.Printf("| %d | %+v |\n", n.data, n.next)
}

func (n *Node) PrintDoubleLL() {
        fmt.Printf("| %+v | %d | %+v |\n", n.prev, n.data, n.next)
}

package linkedlist

import (
        "errors"
        "fmt"
)

// Single represents a single linked list.
type Single struct {
        size int
        head *Node
}

// NewSingleLinkedList creates an empty single linked list.
func NewSingleLinkedList() *Single {
        return &Single{head: nil}
}

// Length returns the length of the list.
func (s *Single) Length() int {
        return s.size
}

// IsEmpty checks if the list is empty or not.
func (s *Single) IsEmpty() bool {
        return s.head == nil && s.Length() == 0
}

// incrementLength increases the size of the list by 1.
func (s *Single) incrementLength() {
        s.size++
}

// decrementLength decreases the size of the list by 1.
func (s *Single) decrementLength() {
        s.size--
}

// Insert inserts the data to the end of the list.
// This is opposite to InsertAtBegin, which inserts at beginning.
func (s *Single) Insert(data int) {
        node := &Node{
                data: data,
                next: nil,
        }

        // First element
        if s.IsEmpty() {
                s.head = node
                s.incrementLength()
                return
        }

        // traverse to last element
        lastNode := s.head
        for lastNode.next != nil {
                lastNode = lastNode.next
        }

        // insert
        lastNode.next = node
        s.incrementLength()
}

// Print prints list to the console.
func (s *Single) Print() {
        if s.IsEmpty() {
                fmt.Println("list is empty")
                return
        }

        fmt.Printf("H -> %v\n", s.head)
        node := s.head
        for {
                node.PrintSingleLL()
                if node.next == nil {
                        break
                }
                node = node.next
        }
        fmt.Println("")
}

// InsertAtBeginning inserts the data to the beginning of the list.
// This is opposite to Insert, which inserts at the end.
func (s *Single) InsertAtBeginning(data int) {

        // When list is empty, we can just use Insert.
        if s.IsEmpty() {
                s.Insert(data)
                return
        }

        currentNode := s.head
        newNode := &Node{
                data: data,
                next: currentNode,
        }

        s.head = newNode
        s.incrementLength()
}

// InsertAt inserts the data into a specified position.
// Returns error, if the specified position is invalid. Position 1 is considered as beginning of the list.
func (s *Single) InsertAt(data int, position int) error {

        if position > s.Length() {
                return errors.New("invalid position, exceeded length of the list")
        }

        // Insert at beginning if position is 1
        if position == 1 {
                s.InsertAtBeginning(data)
                return nil
        }

        // To insert at specific position, we have to traverse to that position and insert
        node := s.head
        index := 1

        for {

                if index == position-1 {
                        break
                }

                node = node.next
                index++
        }

        newNode := &Node{
                data: data,
                next: node.next,
        }
        node.next = newNode
        s.incrementLength()
        return nil
}

// Search searches for the specified data in the list.
func (s *Single) Search(data int) bool {
        if s.IsEmpty() {
                return false
        }

        node := s.head
        found := false
        for {

                if node.data == data {
                        found = true
                        break
                }

                if node.next == nil {
                        break
                }

                node = node.next
        }

        return found
}

// DeleteAtEnd removes the last node from the list and returns it.
// Returns nil if list is empty.
func (s *Single) DeleteAtEnd() *Node {

        // If list is empty, there is nothing to delete
        if s.IsEmpty() {
                return nil
        }

        // If there is only one element in the list, then set head to nil
        if s.Length() == 1 {
                node := s.head
                s.head = nil
                s.decrementLength()
                return node
        }

        // If the list has more than 1 node, traverse to the penultimate node in the list.
        node := s.head
        count := 1

        for {
                if count == s.Length()-1 {
                        break
                }
                node = node.next
                count++
        }

        deletedNode := node.next
        node.next = nil
        s.decrementLength()
        return deletedNode
}

// DeleteAtBeginning removes the node that head points to and returns it.
// Returns nil if list is empty.
func (s *Single) DeleteAtBeginning() *Node {
        if s.IsEmpty() {
                return nil
        }

        // If there is only one element in the list, then set head to nil
        if s.Length() == 1 {
                node := s.head
                s.head = nil
                s.decrementLength()
                return node
        }

        // If more than 1 node exists
        node := s.head
        s.head = node.next
        node.next = nil
        s.decrementLength()
        return node
}

// DeleteAtPosition removes the node at a given position and returns the node.
// Sets the error, if invalid position is used or if list is empty.
func (s *Single) DeleteAtPosition(position int) (*Node, error) {

        if position > s.Length() {
                return nil, errors.New("invalid position, exceeded length of the list")
        }

        if position == 1 {
                node := s.DeleteAtBeginning()
                return node, nil
        }

        // traverse to the node that is before to the specified position
        node := s.head
        count := 1
        for {
                if count == position-1 {
                        break
                }
                node = node.next
                count++
        }

        nodeBeforePosition := node
        nodeAtPosition := nodeBeforePosition.next
        nodeAfterPosition := nodeAtPosition.next

        nodeBeforePosition.next = nodeAfterPosition
        nodeAtPosition.next = nil
        s.decrementLength()

        return nodeAtPosition, nil
}

package sorting

import (
        "github.com/codelabs/gobank/lib/v1/utils"
        "log/slog"
)

// BubbleSort is the simplest sorting algorithm that works by repeated swapping the adjacent elements if they are in
// the wrong order.
func BubbleSort[V int | float64](list []V) {

        n := len(list)
        slog.Info("list size", "size", n)

        // swapCounter tracks number of swaps performed.
        swapCounter := 0

        for i := 0; i < n-1; i++ {

                swapped := false
                scanSize := n - 1 - i
                slog.Debug("scan size", "scanSize", scanSize)

                for j := 0; j < scanSize; j++ {

                        if list[j] > list[j+1] {

                                utils.Swap(&list[j], &list[j+1])
                                swapCounter++
                                swapped = true
                        }
                }

                if !swapped {
                        break
                }
        }

        slog.Debug("num swaps", "swapCount", swapCounter)

        if swapCounter == 0 {
                slog.Warn("already sorted")
        }
}

package sorting

import (
        "log/slog"
)

// InsertionSort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands.
// The array is virtually split into a sorted and an unsorted part.
// Values from the unsorted part are picked and placed at the correct position in the sorted part.
func InsertionSort(list []int) {

        n := len(list)
        slog.Debug("", "listSize", n)
        slog.Debug("Before Sort", "list", list)

        for i := 1; i < n; i++ {

                key := list[i]
                slog.Debug("", "i", i, "key", key)

                for j := i - 1; j >= 0; j-- {
                        if list[j] > key {
                                slog.Debug("greater than key found", "j", j)
                                list[j+1] = list[j]
                                list[j] = key
                        }
                }
        }

        slog.Debug("After Sort", "list", list)
}

package sorting

import (
        "fmt"
        "github.com/codelabs/gobank/lib/v1/utils"
        "log/slog"
)

// SelectionSort ...
func SelectionSort(list []int) {

        slog.Info("Before Sort", "list", list)
        n := len(list)

        for i := 0; i < n-1; i++ {

                // Controls the starting point for the sublist
                start := i
                // Assuming the smallest item is at beginning of the sublist
                minItem := list[start]
                // Position or index of the smallest element found.
                position := start

                // Finding the minimum item from the sublist, with its position
                for j := start + 1; j < n; j++ {
                        if minItem > list[j] {
                                minItem = list[j]
                                position = j
                        }
                }

                utils.Swap(&list[start], &list[position])

                iteration := fmt.Sprintf("iteration-%d", i+1)
                slog.Debug(iteration, "min", minItem, "pos", position, "list", list)
        }

        slog.Info("After Sort", "list", list)
}

package utils

// Swap exchanges values between two items.
func Swap[V int | float64 | string](i, j *V) {
        temp := *i
        *i = *j
        *j = temp
}