README
¶
dynarray
Package dynarray contains data structures for Dynamic Arrays.
About
DynArray works like regular arrays except for the following differences:
- Indexing is one based.
- An index can hold no value at all.
- Memory usage depends on count of values stored not the index count.
- When storing values beyond the highest index, length grows automatically instead of seeing index out of bounds.
- Inserting into or deleting from the beginning or middle of the array takes O(log n) time instead of O(n) time.
- Accessing a random array element takes O(log n) time instead of O(1) time.
Cursor instances can speed up array access if reading and writing to the same area of the DynArray. DynArray instances are not safe to use with multiple goroutines.
Examples
package main
import (
"fmt"
"github.com/keep94/dynarray"
)
func main() {
var dyn dynarray.DynArray[string]
dyn.Set(1, "hello")
dyn.Set(3, "goodbye")
for i := 1; i <= dyn.Len(); i++ {
fmt.Println(dyn.GetOrElse(i, "novalue"))
}
// Prints:
//
// hello
// novalue
// goodbye
}
More documentation and examples can be found here.
Documentation
¶
Overview ¶
Package dynarray contains data structures for Dynamic Arrays.
Index ¶
- type Cursor
- func (c *Cursor[T]) Advance(count int) error
- func (c *Cursor[T]) Clear()
- func (c *Cursor[T]) Close()
- func (c *Cursor[T]) Delete(count int) error
- func (c *Cursor[T]) Get() (T, bool)
- func (c *Cursor[T]) GetOrElse(defaultValue T) T
- func (c *Cursor[T]) GetValue() T
- func (c *Cursor[T]) Goto(index int)
- func (c *Cursor[T]) Index() int
- func (c *Cursor[T]) Insert(count int) error
- func (c *Cursor[T]) IsClosed() bool
- func (c *Cursor[T]) Len() int
- func (c *Cursor[T]) NextValue() bool
- func (c *Cursor[T]) Set(value T)
- type DynArray
- func (d *DynArray[T]) All() iter.Seq2[int, T]
- func (d *DynArray[T]) AllFrom(index int) iter.Seq2[int, T]
- func (d *DynArray[T]) Clear(index int)
- func (d *DynArray[T]) Delete(index, count int) error
- func (d *DynArray[T]) FirstValue() (*Cursor[T], bool)
- func (d *DynArray[T]) Get(index int) (T, bool)
- func (d *DynArray[T]) GetOrElse(index int, defaultValue T) T
- func (d *DynArray[T]) GetValue(index int) T
- func (d *DynArray[T]) Insert(index, count int) error
- func (d *DynArray[T]) Len() int
- func (d *DynArray[T]) MakeSnapshot() Snapshot[T]
- func (d *DynArray[T]) NewCursor() *Cursor[T]
- func (d *DynArray[T]) NewCursorAt(index int) *Cursor[T]
- func (d *DynArray[T]) Set(index int, value T)
- func (d *DynArray[T]) Truncate(newLength int) error
- type Snapshot
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cursor ¶
type Cursor[T any] struct { // contains filtered or unexported fields }
Cursor points to a particular index in a DynArray. Accessing elements of the DynArray through a Cursor takes O(1) time. However creating a Cursor instance and using it for the first time takes O(log n) time. Incrementing or decrementing a cursor's index by just one takes O(1) time, but moving a cursor's index by a lot takes closer to O(log n) time. A Cursor instance can point past the end of its DynArray. Calling Set on such a Cursor automatically extends the length of the DynArray to include that new value. Indexes between the old an new length have no value. Cursor instances must be closed when no longer in use to avoid leaks.
Example ¶
package main
import (
"fmt"
"github.com/keep94/dynarray"
)
func main() {
var dyn dynarray.DynArray[string]
c := dyn.NewCursor()
defer c.Close()
c.Set("the")
c.Advance(1)
c.Set("quick")
c.Advance(1)
c.Set("brown")
c.Advance(1)
c.Set("fox")
c.Advance(1)
c.Set("jumps")
c.Advance(1)
c.Set("over")
c.Advance(1)
c.Set("the")
c.Advance(1)
c.Set("lazy")
c.Advance(1)
c.Set("dog")
c.Goto(1)
for c.GetValue() != "fox" {
c.Advance(1)
}
c.Insert(1)
c.Advance(-1)
c.Set("inserted_value")
for i := 1; i <= dyn.Len(); i++ {
fmt.Println(dyn.GetValue(i))
}
}
Output: the quick brown inserted_value fox jumps over the lazy dog
func (*Cursor[T]) Advance ¶
Advance advances this cursor's index forward by count. If count is negative, Advance moves the cursor backwards. Moving the cursor forward or backward by k, takes O(log k) time. Advance returns an error if the cursor's new index would be <= 0 or if it would overflow.
func (*Cursor[T]) Clear ¶
func (c *Cursor[T]) Clear()
Clear clears the value at this cursor's index so that it contains no value. This operation takes O(1) time. If this cursor is pointing past the end of its DynArray, then Clear is a no-op.
func (*Cursor[T]) Close ¶
func (c *Cursor[T]) Close()
Close closes this cursor. Close can be called multiple times on the same Cursor. Calling methods on a closed cursor besides the Close and IsClosed methods panics.
func (*Cursor[T]) Delete ¶
Delete deletes count indexes starting at this cursor's index. This operation takes O(k + log n) time where k is the number of actual values deleted. Other Cursors that point to an index after the ones that got deleted get moved up by count automatically. If a cursor points to an index that got deleted, it is automatically closed. Delete returns an error if there are fewer than count indexes before the end.
func (*Cursor[T]) Get ¶
Get gets the value at this cursor's index. This operation takes O(1) time. If the index has no value, Get returns false. If this cursor is pointing past the end of its DynArray, then Get returns false for no value.
func (*Cursor[T]) GetOrElse ¶
func (c *Cursor[T]) GetOrElse(defaultValue T) T
GetOrElse works like Get, but it returns defaultValue if the index the cursor points to has no value.
func (*Cursor[T]) GetValue ¶
func (c *Cursor[T]) GetValue() T
GetValue works like Get except it returns just the value. GetValue returns the zero value if either the index the cursor points to has no value or it has the zero value.
func (*Cursor[T]) Goto ¶
Goto changes the index of this cursor to be index. Goto delegates to Advance. Goto panics if index <= 0.
func (*Cursor[T]) Insert ¶
Insert inserts count new indexes just before this cursor's index. The new indexes contain no value. This operation takes O(log n) time. Insert moves this cursor forward by count indexes making room for the indexes inserted. Other Cursors that point to an index at or after this cursor get moved forward by count indexes automatically. Insert returns an error if this cursor's index is more than c.Len() + 1 or if count is negative or count so big that it overflows the length of its DynArray.
type DynArray ¶
type DynArray[T any] struct { // contains filtered or unexported fields }
DynArray works like regular arrays except for the following differences:
- Indexing is one based.
- An index can hold no value at all.
- Memory usage depends on count of values stored not the index count.
- When storing values beyond the highest index, length grows automatically instead of seeing index out of bounds.
- Inserting into or deleting from the beginning or middle of the array takes O(log n) time instead of O(n) time.
- Accessing a random array element takes O(log n) time instead of O(1) time.
Cursor instances can speed up array access if reading and writing to the same area of the DynArray. DynArray instances are not safe to use with multiple goroutines.
The zero value of a DynArray[T] has 0 length and is ready to use. DynArray instances do not support copy by value.
func FromSnapshot ¶ added in v0.3.0
FromSnapshot builds a new DynArray from a Snapshot.
func New ¶
New creates a new DynArray of specific length with all the indexes containing no value. The range of indexes of the returned DynArray is between 1 and length inclusive. New panics if length < 0 or if length > math.Maxint - 1.
func (*DynArray[T]) All ¶ added in v0.2.0
All returns the 1 based index and value of each element in this DynArray from beginning to end. It is equivalent to d.AllFrom(1).
Example ¶
package main
import (
"fmt"
"github.com/keep94/dynarray"
)
func main() {
var dyn dynarray.DynArray[string]
dyn.Set(2, "do")
dyn.Set(5, "re")
dyn.Set(10, "mi")
for index, value := range dyn.All() {
fmt.Println(index, value)
}
}
Output: 2 do 5 re 10 mi
func (*DynArray[T]) AllFrom ¶ added in v0.2.0
AllFrom returns the 1 based index and value of each element in this DynArray starting at index.
func (*DynArray[T]) Clear ¶
Clear clears the given index of this DynArray so that it holds no value. The operation takes O(log n) time. Clear panics if index <= 0. If index points past the end of the DynArray then Clear is a no-op.
Example ¶
package main
import (
"fmt"
"github.com/keep94/dynarray"
)
func main() {
var dyn dynarray.DynArray[string]
dyn.Set(7, "do")
dyn.Clear(7)
fmt.Println(dyn.Len())
fmt.Println(dyn.GetOrElse(7, "novalue"))
}
Output: 7 novalue
func (*DynArray[T]) Delete ¶
Delete deletes count indexes from this DynArray starting at index. This operation takes O(log n + k) where k is the number of values deleted. Delete returns an error if index <= 0 or if deleting count indexes would go past the end of the DynArray.
Example ¶
package main
import (
"fmt"
"github.com/keep94/dynarray"
)
func main() {
var dyn dynarray.DynArray[string]
dyn.Set(1, "do")
dyn.Set(4, "re")
dyn.Set(9, "mi")
dyn.Delete(3, 2)
fmt.Println(dyn.Len())
for i := 1; i <= dyn.Len(); i++ {
fmt.Println(dyn.GetOrElse(i, "novalue"))
}
}
Output: 7 do novalue novalue novalue novalue novalue mi
func (*DynArray[T]) FirstValue ¶
FirstValue returns a cursor pointing to the first index of the this DynArray that has a value. If this DynArray has no actual values in it, FirstValue returns false.
func (*DynArray[T]) Get ¶
Get gets the value at the given index of this DynArray. This operation takes O(log n) time. If the index has no value, Get returns false. Get panics if index <= 0. If index points past the end of the DynArray then Get returns false for no value.
func (*DynArray[T]) GetOrElse ¶
GetOrElse works like Get, but it returns defaultValue if index has no value.
Example ¶
package main
import (
"fmt"
"github.com/keep94/dynarray"
)
func main() {
var dyn dynarray.DynArray[string]
dyn.Set(1, "do")
dyn.Set(4, "re")
dyn.Set(9, "mi")
fmt.Println(dyn.Len())
fmt.Println(dyn.GetOrElse(1, "novalue"))
fmt.Println(dyn.GetOrElse(4, "novalue"))
fmt.Println(dyn.GetOrElse(9, "novalue"))
fmt.Println(dyn.GetOrElse(8, "novalue"))
fmt.Println(dyn.GetOrElse(101, "novalue"))
}
Output: 9 do re mi novalue novalue
func (*DynArray[T]) GetValue ¶
GetValue works like Get except it returns just a value. GetValue returns the zero value if the index either has no value or the index has the zero value.
func (*DynArray[T]) Insert ¶
Insert inserts count new indexes into this DynArray right before the given index. The new indexes hold no value. This operation takes O(log n) time. Insert returns an error if index <= 0 or index > d.Len() + 1. index = d.Len() + 1 means insert past the end of the DynArray.
Example ¶
package main
import (
"fmt"
"github.com/keep94/dynarray"
)
func main() {
var dyn dynarray.DynArray[string]
dyn.Set(1, "do")
dyn.Set(4, "re")
dyn.Set(9, "mi")
dyn.Insert(3, 2)
fmt.Println(dyn.Len())
fmt.Println(dyn.GetOrElse(1, "novalue"))
fmt.Println(dyn.GetOrElse(6, "novalue"))
fmt.Println(dyn.GetOrElse(11, "novalue"))
}
Output: 11 do re mi
func (*DynArray[T]) Len ¶
Len returns the length of this DynArray, which is the highest index. Len is not to be confused with the number of values stored in this DynArray.
func (*DynArray[T]) MakeSnapshot ¶ added in v0.3.0
MakeSnapshot makes a snapshot of this DynArray. It takes O(k) time where k is the number of actual values in this DynArray.
func (*DynArray[T]) NewCursor ¶
NewCursor returns a new cursor pointing at index 1 of this DynArray. It is equivalent to d.NewCursorAt(1).
func (*DynArray[T]) NewCursorAt ¶
NewCursorAt returns a new cursor pointing at the given index of this DynArray. NewCursorAt panics if index <= 0.
type Snapshot ¶ added in v0.3.0
type Snapshot[T any] struct { // contains filtered or unexported fields }
Snapshot is an immutable snapshot of a DynArray's data. Unlike a DynArray, a Snapshot is safe to use with multiple goroutines. Index access and iteration are much faster with Snapshots than with DynArrays because Snapshots don't support modification. However, creating a Snapshot takes O(k) time where k is the number of actual values in the DynArray.
The zero value of Snapshot has 0 length and contains no actual values. Programs should pass Snapshot instances as values, not pointers.
func (Snapshot[T]) All ¶ added in v0.3.0
All returns the 1 based index and value of each element in this Snapshot from beginning to end. It is equivalent to s.AllFrom(1).
func (Snapshot[T]) AllFrom ¶ added in v0.3.0
AllFrom returns the 1 based index and value of each element in this Snapshot starting at index.
func (Snapshot[T]) Get ¶ added in v0.3.0
Get returns the value at given index. This operation takes O(log n) time. If index has no value, Get returns false. Get panics if index <= 0.
func (Snapshot[T]) GetOrElse ¶ added in v0.3.0
GetOrElse works like Get, but it returns defaultValue if index has no value.
Source Files