Arafatk/DataViz

// Package singlylinkedlist implements the singly-linked list.
//
// Structure is not thread safe.
//
// Reference: https://en.wikipedia.org/wiki/List_%28abstract_data_type%29
package singlylinkedlist

import (
    "fmt"
    "github.com/Arafatk/Dataviz/lists"
    "github.com/Arafatk/Dataviz/utils"
    "strings"
)

func assertListImplementation() {
    var _ lists.List = (*List)(nil)
}

// List holds the elements, where each element points to the next element
type List struct {
    first *element
    last  *element
    size  int
}

type element struct {
    value interface{}
    next  *element
}

// New instantiates a new empty list
func New() *List {
    return &List{}
}

// Add appends a value (one or more) at the end of the list (same as Append())
func (list *List) Add(values ...interface{}) {
    for _, value := range values {
        newElement := &element{value: value}
        if list.size == 0 {
            list.first = newElement
            list.last = newElement
        } else {
            list.last.next = newElement
            list.last = newElement
        }
        list.size++
    }
}

// Append appends a value (one or more) at the end of the list (same as Add())
func (list *List) Append(values ...interface{}) {
    list.Add(values...)
}

// Prepend prepends a values (or more)
func (list *List) Prepend(values ...interface{}) {
    // in reverse to keep passed order i.e. ["c","d"] -> Prepend(["a","b"]) -> ["a","b","c",d"]
    for v := len(values) - 1; v >= 0; v-- {
        newElement := &element{value: values[v], next: list.first}
        list.first = newElement
        if list.size == 0 {
            list.last = newElement
        }
        list.size++
    }
}

// Get returns the element at index.
// Second return parameter is true if index is within bounds of the array and array is not empty, otherwise false.
func (list *List) Get(index int) (interface{}, bool) {

    if !list.withinRange(index) {
        return nil, false
    }

    element := list.first
    for e := 0; e != index; e, element = e+1, element.next {
    }

    return element.value, true
}

// Remove removes one or more elements from the list with the supplied indices.
func (list *List) Remove(index int) {

    if !list.withinRange(index) {
        return
    }

    if list.size == 1 {
        list.Clear()
        return
    }

    var beforeElement *element
    element := list.first
    for e := 0; e != index; e, element = e+1, element.next {
        beforeElement = element
    }

    if element == list.first {
        list.first = element.next
    }
    if element == list.last {
        list.last = beforeElement
    }
    if beforeElement != nil {
        beforeElement.next = element.next
    }

    element = nil

    list.size--
}

// Contains checks if values (one or more) are present in the set.
// All values have to be present in the set for the method to return true.
// Performance time complexity of n^2.
// Returns true if no arguments are passed at all, i.e. set is always super-set of empty set.
func (list *List) Contains(values ...interface{}) bool {

    if len(values) == 0 {
        return true
    }
    if list.size == 0 {
        return false
    }
    for _, value := range values {
        found := false
        for element := list.first; element != nil; element = element.next {
            if element.value == value {
                found = true
                break
            }
        }
        if !found {
            return false
        }
    }
    return true
}

// Values returns all elements in the list.
func (list *List) Values() []interface{} {
    values := make([]interface{}, list.size, list.size)
    for e, element := 0, list.first; element != nil; e, element = e+1, element.next {
        values[e] = element.value
    }
    return values
}

//IndexOf returns index of provided element
func (list *List) IndexOf(value interface{}) int {
    if list.size == 0 {
        return -1
    }
    for index, element := range list.Values() {
        if element == value {
            return index
        }
    }
    return -1
}

// Empty returns true if list does not contain any elements.
func (list *List) Empty() bool {
    return list.size == 0
}

// Size returns number of elements within the list.
func (list *List) Size() int {
    return list.size
}

// Clear removes all elements from the list.
func (list *List) Clear() {
    list.size = 0
    list.first = nil
    list.last = nil
}

// Sort sort values (in-place) using.
func (list *List) Sort(comparator utils.Comparator) {

    if list.size < 2 {
        return
    }

    values := list.Values()
    utils.Sort(values, comparator)

    list.Clear()

    list.Add(values...)

}

// Swap swaps values of two elements at the given indices.
func (list *List) Swap(i, j int) {
    if list.withinRange(i) && list.withinRange(j) && i != j {
        var element1, element2 *element
        for e, currentElement := 0, list.first; element1 == nil || element2 == nil; e, currentElement = e+1, currentElement.next {
            switch e {
            case i:
                element1 = currentElement
            case j:
                element2 = currentElement
            }
        }
        element1.value, element2.value = element2.value, element1.value
    }
}

// Insert inserts values at specified index position shifting the value at that position (if any) and any subsequent elements to the right.
// Does not do anything if position is negative or bigger than list's size
// Note: position equal to list's size is valid, i.e. append.
func (list *List) Insert(index int, values ...interface{}) {

    if !list.withinRange(index) {
        // Append
        if index == list.size {
            list.Add(values...)
        }
        return
    }

    list.size += len(values)

    var beforeElement *element
    foundElement := list.first
    for e := 0; e != index; e, foundElement = e+1, foundElement.next {
        beforeElement = foundElement
    }

    if foundElement == list.first {
        oldNextElement := list.first
        for i, value := range values {
            newElement := &element{value: value}
            if i == 0 {
                list.first = newElement
            } else {
                beforeElement.next = newElement
            }
            beforeElement = newElement
        }
        beforeElement.next = oldNextElement
    } else {
        oldNextElement := beforeElement.next
        for _, value := range values {
            newElement := &element{value: value}
            beforeElement.next = newElement
            beforeElement = newElement
        }
        beforeElement.next = oldNextElement
    }
}

// String returns a string representation of container
func (list *List) String() string {
    str := "SinglyLinkedList\n"
    values := []string{}
    for element := list.first; element != nil; element = element.next {
        values = append(values, fmt.Sprintf("%v", element.value))
    }
    str += strings.Join(values, ", ")
    return str
}

// Check that the index is within bounds of the list
func (list *List) withinRange(index int) bool {
    return index >= 0 && index < list.size
}