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
}
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]) 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]) 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
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 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]) 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.
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")
c, ok := dyn.FirstValue()
if ok {
defer c.Close()
}
for ; ok; ok = c.NextValue() {
fmt.Println(c.Index(), c.GetValue())
}
}
Output: 2 do 5 re 10 mi
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]) NewCursor ¶
NewCursor returns a new cursor pointing at index 1 of this DynArray. It is the same as 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.
Source Files