README
¶
Operations On Streaming Sorted Arrays
MIT Licensed. This package contains function to apply set operations on streams of sorted numbers.
Main motivation of this package is to be used in search engines where big inverted indexes must be used to find matching
documents. Imagine a query find docs where contains "letter" and not contains "message". This operation maps to making
an intersection of the two inverted indexes for "letter" and "message". Now if the indexes are sorted... here comes this
package.
Operations:
- union (returns the stream consisting of elements that are either in stream1 or stream2)
- intersection (returns the stream consisting of elements that are in both stream1 and stream2)
- difference (returns the stream consisting of elements that are in stream1 but not in stream2)
Features:
- generics to support any ordered number type
- asc/desc orders supported
- streaming support is added to reduce memory usage for potentially big data sources
- early stop to consume as few items for streams as possible
Sample
With this tool it is possible to arrange complex pipelines.
// see tests
// expression: (a and b) and not c
func TestComposition(t *testing.T) {
a := NewSliceStream([]int{1, 2, 3})
b := NewSliceStream([]int{2, 3})
c := NewSliceStream([]int{3})
result := Diff[int](Intersect[int](a, b, true), c, true)
require.EqualValues(t, []int{2}, ToSlice(result))
}
Usage
- model your data with
SortedNumbersStreaminterface (seeSliceStreamfor reference) - decide if your sorted data goes asc or desc
- apply operations on your data
Union[<your data type>](stream1, stream2, <isAsc>): SortedNumbersStream - use
ToSliceto dump your iterable to a slice (for testing/debugging)
Documentation
¶
Index ¶
- func ToSlice[T constraints.Ordered](stream SortedNumbersStream[T]) []T
- type ChannelStream
- type SliceStream
- type SortedNumbersStream
- func Diff[T constraints.Ordered](stream1, stream2 SortedNumbersStream[T], asc bool) SortedNumbersStream[T]
- func Intersect[T constraints.Ordered](stream1, stream2 SortedNumbersStream[T], asc bool) SortedNumbersStream[T]
- func Union[T constraints.Ordered](stream1, stream2 SortedNumbersStream[T], asc bool) SortedNumbersStream[T]
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ToSlice ¶
func ToSlice[T constraints.Ordered](stream SortedNumbersStream[T]) []T
Types ¶
type ChannelStream ¶
type ChannelStream[T constraints.Ordered] struct { // contains filtered or unexported fields }
ChannelStream is used as a result of operation on other streams
func NewChannelStream ¶
func NewChannelStream[T constraints.Ordered]() *ChannelStream[T]
func (*ChannelStream[T]) Close ¶
func (s *ChannelStream[T]) Close()
func (*ChannelStream[T]) Next ¶
func (s *ChannelStream[T]) Next() (item T, ok bool)
func (*ChannelStream[T]) Push ¶
func (s *ChannelStream[T]) Push(item T)
type SliceStream ¶
type SliceStream[T constraints.Ordered] struct { // contains filtered or unexported fields }
SliceStream implements SortedNumbersStream for static slices (convenient in tests)
func NewSliceStream ¶
func NewSliceStream[T constraints.Ordered](slice []T) *SliceStream[T]
func (*SliceStream[T]) Next ¶
func (s *SliceStream[T]) Next() (item T, ok bool)
func (*SliceStream[T]) Reset ¶
func (s *SliceStream[T]) Reset()
type SortedNumbersStream ¶
type SortedNumbersStream[T constraints.Ordered] interface { // Next return the next available item from the sorted stream // ok shows if the stream is drained and no further read will give anything (like a closed channel) Next() (item T, ok bool) }
SortedNumbersStream allows to iterate over sorted data Algorithms imply the data behind this interface is sorted
func Diff ¶
func Diff[T constraints.Ordered](stream1, stream2 SortedNumbersStream[T], asc bool) SortedNumbersStream[T]
Diff returns the stream consisting of elements that are in stream1 but not in stream2
func Intersect ¶
func Intersect[T constraints.Ordered](stream1, stream2 SortedNumbersStream[T], asc bool) SortedNumbersStream[T]
Intersect returns the stream consisting of elements that are in both stream1 and stream2
func Union ¶
func Union[T constraints.Ordered](stream1, stream2 SortedNumbersStream[T], asc bool) SortedNumbersStream[T]
Union returns the stream consisting of elements that are either in stream1 or stream2
Source Files