<commit_before># SortedMap

[![Build Status](https://travis-ci.org/umpc/go-sortedmap.svg?branch=master)](https://travis-ci.org/umpc/go-sortedmap) [![Coverage Status](https://codecov.io/github/umpc/go-sortedmap/badge.svg?branch=master)](https://codecov.io/github/umpc/go-sortedmap?branch=master) [![GoDoc](https://godoc.org/github.com/umpc/go-sortedmap?status.svg)](https://godoc.org/github.com/umpc/go-sortedmap)

SortedMap is a simple library that provides a value-sorted ```map[interface{}]interface{}``` type and methods combined from Go 1 map and slice primitives.

This data structure allows for roughly constant-time reads and for efficiently iterating over only a section of stored values.

```sh
go get -u github.com/umpc/go-sortedmap
```

### Complexity
Operation | Average-Case
----------|-----------
Has | ```O(1)```
Get | ```O(1)```
Iter | ```O(n)```
Delete | ```O(n log n)```
Insert | ```O(n^2)```
Replace | ```O(2^n)```

## Example Usage

```go
package main

import (
  "fmt"
  "time"
  mrand "math/rand"

  "github.com/umpc/go-sortedmap"
  "github.com/umpc/go-sortedmap/asc"
)

func main() {
  records := []*sortedmap.Record{
	&sortedmap.Record{
	    Key: "openbsd",
	    Val: time.Date(1995, 10, 18, 8, 37, 1, 0, time.UTC),
    },
    &sortedmap.Record{
	    Key: "unixtime",
	    Val: time.Date(1970, 1, 1, 0, 0, 0, 0, time.UTC),
    },
    &sortedmap.Record{
	    Key: "linux",
	    Val: time.Date(1991, 8, 25, 20, 57, 8, 0, time.UTC),
    },
  }

  // Create a new sorted collection with a size suggestion:
  sm := sortedmap.New(len(records), asc.Time)

  // Insert the example records:
  sm.BatchInsert(records)

  // Loop through records, in order, from the lower bound value,
  // until reaching the upper bound value:
  if ch, ok := sm.BoundedIterCh(false, time.Date(1994, 1, 1, 0, 0, 0, 0, time.UTC), time.Now()); ok {
    for rec := range ch {
      fmt.Printf("%+v\n", rec)
    }
  } else {
	  fmt.Println("No values found that were equal to or within the given bounds.")
  }

  // Check out the examples directory, docs, and test files, for more functionality,
  // and further explainations.
}

func randRecords(n int) []*sortedmap.Record {
  mrand.Seed(time.Now().UTC().UnixNano())
  records := make([]*sortedmap.Record, n)
  for i := range records {
    year := mrand.Intn(2058)
    for year < 2000 {
      year = mrand.Intn(2058)
    }
    mth := time.Month(mrand.Intn(12))
    if mth < 1 {
      mth++
    }
    day := mrand.Intn(28)
    if day < 1 {
      day++
    }
    hour := mrand.Intn(23)
    min  := mrand.Intn(59)
    sec  := mrand.Intn(59)

    t := time.Date(year, mth, day, hour, min, sec, 0, time.UTC)

    records[i] = &sortedmap.Record{
      Key: t.Format(time.UnixDate),
      Val: t,
    }
  }
  return records
}
```

## Benchmarks

```sh
BenchmarkDelete1of1Records-8                 	 5000000	       285 ns/op	       0 B/op	       0 allocs/op

BenchmarkDelete1of10Records-8                	 2000000	       615 ns/op	       0 B/op	       0 allocs/op
BenchmarkDelete1of100Records-8               	 1000000	      1005 ns/op	       0 B/op	       0 allocs/op<commit_msg>Remove unneeded README content. Update with links to examples.<commit_after># SortedMap

[![Build Status](https://travis-ci.org/umpc/go-sortedmap.svg?branch=master)](https://travis-ci.org/umpc/go-sortedmap) [![Coverage Status](https://codecov.io/github/umpc/go-sortedmap/badge.svg?branch=master)](https://codecov.io/github/umpc/go-sortedmap?branch=master) [![GoDoc](https://godoc.org/github.com/umpc/go-sortedmap?status.svg)](https://godoc.org/github.com/umpc/go-sortedmap)

SortedMap is a simple library that provides a value-sorted ```map[interface{}]interface{}``` type and methods combined from Go 1 map and slice primitives.

This data structure allows for roughly constant-time reads and for efficiently iterating over only a section of stored values.

```sh
go get -u github.com/umpc/go-sortedmap
```

### Complexity
Operation | Average-Case
----------|-----------
Has | ```O(1)```
Get | ```O(1)```
Iter | ```O(n)```
Delete | ```O(n log n)```
Insert | ```O(n^2)```
Replace | ```O(2^n)```

## Example Usage

```go
package main

import (
  "fmt"
  "time"

  "github.com/umpc/go-sortedmap"
  "github.com/umpc/go-sortedmap/asc"
)

func main() {
  records := []*sortedmap.Record{
	&sortedmap.Record{
	    Key: "OpenBSD",
	    Val: time.Date(1995, 10, 18, 8, 37, 1, 0, time.UTC),
    },
    &sortedmap.Record{
	    Key: "UnixTime",
	    Val: time.Date(1970, 1, 1, 0, 0, 0, 0, time.UTC),
    },
    &sortedmap.Record{
	    Key: "Linux",
	    Val: time.Date(1991, 8, 25, 20, 57, 8, 0, time.UTC),
    },
  }

  // Create a new sorted collection with a size suggestion:
  sm := sortedmap.New(len(records), asc.Time)

  // Insert the example records:
  sm.BatchInsert(records)

  // Loop through records, in order, from the lower bound value,
  // until reaching the upper bound value:
  if ch, ok := sm.BoundedIterCh(false, time.Date(1994, 1, 1, 0, 0, 0, 0, time.UTC), time.Now()); ok {
    for rec := range ch {
      fmt.Printf("%+v\n", rec)
    }
  } else {
    fmt.Println("No values found that were equal to or within the given bounds.")
  }
}
```

Check out the [examples](https://github.com/umpc/go-sortedmap/tree/master/examples), [documentation](https://godoc.org/github.com/umpc/go-sortedmap), and test files, for more features and further explanations.

## Benchmarks

```sh
BenchmarkDelete1of1Records-8                 	 5000000	       285 ns/op	       0 B/op	       0 allocs/op

BenchmarkDelete1of10Records-8                	 2000000	       615 ns/op	       0 B/op	       0 allocs/op
BenchmarkDelete1of100Records-8               	 1000000	      1005 ns/op	       0 B/op	       0 allocs/op
{'fraction_non_alphanumeric': 0.16590829541477073, 'fraction_numerical': 0.03937696884844242, 'mean_word_length': 2.8562753036437245, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 3, 'https://': 14, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1127975', 'n_tokens_mistral': 2277, 'n_tokens_neox': 2055, 'n_words': 514}