ty: github.com/BurntSushi/ty/data Index | Examples | Files

package data

import "github.com/BurntSushi/ty/data"

Package data tumbles down the rabbit hole into parametric data types.

A parametric data type in this package is a data type that is parameterized by one or more types discovered at run time. For example, an ordered map is parameterized by two types: the type of its keys and the type of its values.

Implementation

While all parametric inputs and outputs of each function have a Go type of `interface{}`, the underlying type is maintained via reflection. In particular, any operation that interacts with a parametric data type does so via reflection so that the type safety found in Go at compile time can be recovered at run time.

For example, consider the case of an ordered map. One might define such a map as a list of its keys in order and a map of `interface{}` to `interface{}`:

type OrdMap struct {
	M map[interface{}]interface{}
	Keys []interface{}
}

And one can interact with this map using standard built-in Go operations:

// Add a key
M["key"] = "value"
Keys = append(Keys, "key")

// Delete a key
delete(M, "key")

// Read a key
M["key"]

But there is no type safety with such a representation, even at run time:

// Both of these operations are legal with
// the aforementioned representation.
M["key"] = "value"
M[5] = true

Thus, the contribution of this library is to maintain type safety at run time by guaranteeing that all operations are consistent with Go typing rules:

type OrdMap struct {
	M reflect.Value
	Keys reflect.Value
}

And one must interact with a map using `reflect`:

key, val := "key", "value"
rkey := reflect.ValueOf(key)
rval := reflect.ValueOf(val)

// Add a key
M.SetMapIndex(rkey, rval)
Keys = reflect.Append(Keys, rkey)

// Delete a key
M.SetMapIndex(rkey, reflect.Value{})

// Read a key
M.MapIndex(rkey)

Which guarantees, at run-time, that the following cannot happen:

key2, val2 := 5, true
rkey2 := reflect.ValueOf(key2)
rval2 := reflect.ValueOf(val2)

// One or the other operation will be disallowed,
// assuming `OrdMap` isn't instantiated with
// `interface{}` as the key and value type.
M.SetMapIndex(rkey, rval)
M.SetMapIndex(rkey2, rval2)

The result is much more painful library code but only slightly more painful client code.

Index

Examples

Package Files

doc.go ordmap.go

type OrdMap Uses

type OrdMap struct {
    // contains filtered or unexported fields
}

OrdMap has a parametric type `OrdMap<K, V>` where `K` is the type of the map's keys and `V` is the type of the map's values.

func OrderedMap Uses

func OrderedMap(ktype, vtype interface{}) *OrdMap

OrderedMap returns a new instance of OrdMap instantiated with the key and value types given. Namely, the types should be provided via nil pointers, e.g., to create a map from strings to integers:

omap := OrderedMap(new(string), new(int))

An ordered map maintains the insertion order of all keys in the map. Namely, `(*OrdMap).Keys()` returns a slice of keys in the order they were inserted. The order of a key can *only* be changed if it is deleted and added again.

All of the operations on an ordered map have the same time complexity as the built-in `map`, except for `Delete` which is O(n) in the number of keys.

Code:

omap := OrderedMap(new(string), new([]string))

omap.Put("Bruce Springsteen",
    []string{"Thunder Road", "Born to Run", "This Hard Land"})
omap.Put("J. Geils Band",
    []string{"Musta Got Lost", "Freeze Frame", "Southside Shuffle"})
omap.Put("Bob Seger",
    []string{"Against the Wind", "Roll Me Away", "Night Moves"})

for _, key := range omap.Keys().([]string) {
    fmt.Println(key)
}

omap.Delete("J. Geils Band")
fmt.Println("\nDeleted 'J. Geils Band'...\n")

for _, key := range omap.Keys().([]string) {
    fmt.Printf("%s: %v\n", key, omap.Get(key))
}

Output:

Bruce Springsteen
J. Geils Band
Bob Seger

Deleted 'J. Geils Band'...

Bruce Springsteen: [Thunder Road Born to Run This Hard Land]
Bob Seger: [Against the Wind Roll Me Away Night Moves]

func (*OrdMap) Delete Uses

func (om *OrdMap) Delete(key interface{})

Delete has a parametric type:

func (om *OrdMap<K, V>) Delete(key K)

Delete removes `key` from the map `om`.

N.B. Delete is O(n) in the number of keys.

func (*OrdMap) Exists Uses

func (om *OrdMap) Exists(key interface{}) bool

Exists has a parametric type:

func (om *OrdMap<K, V>) Exists(key K) bool

Exists returns true if `key` is in the map `om`.

func (*OrdMap) Get Uses

func (om *OrdMap) Get(key interface{}) interface{}

Get has a parametric type:

func (om *OrdMap<K, V>) Get(key K) V

Get retrieves the value in the map `om` corresponding to `key`. If the value does not exist, then the zero value of type `V` is returned.

func (*OrdMap) Keys Uses

func (om *OrdMap) Keys() interface{}

Keys has a parametric type:

func (om *OrdMap<K, V>) Keys() []K

Keys returns a list of keys in `om` in the order they were inserted.

Behavior is undefined if the list is modified by the caller.

func (*OrdMap) Len Uses

func (om *OrdMap) Len() int

Len has a parametric type:

func (om *OrdMap<K, V>) Len() int

Len returns the number of keys in the map `om`.

func (*OrdMap) Put Uses

func (om *OrdMap) Put(key, val interface{})

Put has a parametric type:

func (om *OrdMap<K, V>) Put(key K, val V)

Put adds or overwrites `key` into the map `om` with value `val`. If `key` already exists in the map, then its position in the ordering of the map is not changed.

func (*OrdMap) TryGet Uses

func (om *OrdMap) TryGet(key interface{}) (interface{}, bool)

TryGet has a parametric type:

func (om *OrdMap<K, V>) TryGet(key K) (V, bool)

TryGet retrieves the value in the map `om` corresponding to `key` and reports whether the value exists in the map or not. If the value does not exist, then the zero value of `V` and `false` are returned.

func (*OrdMap) Values Uses

func (om *OrdMap) Values() interface{}

Values has a parametric type:

func (om *OrdMap<K, V>) Values() []V

Values returns a shallow copy of the values in `om` in the order that they were inserted.

Package data imports 2 packages (graph). Updated 2017-07-28. Refresh now. Tools for package owners.