Arafatk/DataViz

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

import (
    "fmt"
    "strings"

    "github.com/Arafatk/Dataviz/lists"
    "github.com/Arafatk/Dataviz/utils"
)

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

// List holds the elements in a slice
type List struct {
    elements []interface{}
    size     int
}

const (
    growthFactor = float32(2.0)  // growth by 100%
    shrinkFactor = float32(0.25) // shrink when size is 25% of capacity (0 means never shrink)
)

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

// Add appends a value at the end of the list
func (list *List) Add(values ...interface{}) {
    list.growBy(len(values))
    for _, value := range values {
        list.elements[list.size] = value
        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
    }

    return list.elements[index], 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
    }

    list.elements[index] = nil                                    // cleanup reference
    copy(list.elements[index:], list.elements[index+1:list.size]) // shift to the left by one (slow operation, need ways to optimize this)
    list.size--

    list.shrink()
}

// Contains checks if elements (one or more) are present in the set.
// All elements 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 {

    for _, searchValue := range values {
        found := false
        for _, element := range list.elements {
            if element == searchValue {
                found = true
                break
            }
        }
        if !found {
            return false
        }
    }
    return true
}

// Values returns all elements in the list.
func (list *List) Values() []interface{} {
    newElements := make([]interface{}, list.size, list.size)
    copy(newElements, list.elements[:list.size])
    return newElements
}

//IndexOf returns index of provided element
func (list *List) IndexOf(value interface{}) int {
    if list.size == 0 {
        return -1
    }
    for index, element := range list.elements {
        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.elements = []interface{}{}
}

// Sort sorts values (in-place) using.
func (list *List) Sort(comparator utils.Comparator) {
    if len(list.elements) < 2 {
        return
    }
    utils.Sort(list.elements[:list.size], comparator)
}

// Swap swaps the two values at the specified positions.
func (list *List) Swap(i, j int) {
    if list.withinRange(i) && list.withinRange(j) {
        list.elements[i], list.elements[j] = list.elements[j], list.elements[i]
    }
}

// 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
    }

    l := len(values)
    list.growBy(l)
    list.size += l
    // Shift old to right
    for i := list.size - 1; i >= index+l; i-- {
        list.elements[i] = list.elements[i-l]
    }
    // Insert new
    for i, value := range values {
        list.elements[index+i] = value
    }
}

// String returns a string representation of container
func (list *List) String() string {
    str := "ArrayList\n"
    values := []string{}
    for _, value := range list.elements[:list.size] {
        values = append(values, fmt.Sprintf("%v", 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
}

func (list *List) resize(cap int) {
    newElements := make([]interface{}, cap, cap)
    copy(newElements, list.elements)
    list.elements = newElements
}

// Expand the array if necessary, i.e. capacity will be reached if we add n elements
func (list *List) growBy(n int) {
    // When capacity is reached, grow by a factor of growthFactor and add number of elements
    currentCapacity := cap(list.elements)
    if list.size+n >= currentCapacity {
        newCapacity := int(growthFactor * float32(currentCapacity+n))
        list.resize(newCapacity)
    }
}

// Visualizer makes a visual image demonstrating the list data structure
// using dot language and Graphviz. It first producs a dot string corresponding
// to the list and then runs graphviz to output the resulting image to a file.
func (list *List) Visualizer(fileName string) (ok bool) {
    values := []string{}
    dotString := "digraph graphname{bgcolor=white;subgraph cluster_0 {style=filled;color=lightgrey;node [style=filled,color=white, shape=\"Msquare\"];"
    for _, value := range list.elements[:list.size] {
        values = append(values, fmt.Sprintf("%v", value))
        dotString += values[len(values)-1] + ";"
    }
    dotString += "}}"
    return utils.WriteDotStringToPng(fileName, dotString)
}

// Shrink the array if necessary, i.e. when size is shrinkFactor percent of current capacity
func (list *List) shrink() {
    if shrinkFactor == 0.0 {
        return
    }
    // Shrink when size is at shrinkFactor * capacity
    currentCapacity := cap(list.elements)
    if list.size <= int(float32(currentCapacity)*shrinkFactor) {
        list.resize(list.size)
    }
}