1//  Copyright (c) 2017 Couchbase, Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// 		http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15/*
16Package vellum is a library for building, serializing and executing an FST (finite
17state transducer).
18
19There are two distinct phases, building an FST and using it.
20
21When building an FST, you insert keys ([]byte) and their associated value
22(uint64). Insert operations MUST be done in lexicographic order.  While
23building the FST, data is streamed to an underlying Writer. At the conclusion
24of building, you MUST call Close() on the builder.
25
26After completion of the build phase, you can either Open() the FST if you
27serialized it to disk.  Alternatively, if you already have the bytes in
28memory, you can use Load().  By default, Open() will use mmap to avoid loading
29the entire file into memory.
30
31Once the FST is ready, you can use the Contains() method to see if a keys is
32in the FST.  You can use the Get() method to see if a key is in the FST and
33retrieve it's associated value.  And, you can use the Iterator method to
34enumerate key/value pairs within a specified range.
35
36*/
37package vellum
38
39import (
40	"errors"
41	"io"
42)
43
44// ErrOutOfOrder is returned when values are not inserted in
45// lexicographic order.
46var ErrOutOfOrder = errors.New("values not inserted in lexicographic order")
47
48// ErrIteratorDone is returned by Iterator/Next/Seek methods when the
49// Current() value pointed to by the iterator is greater than the last
50// key in this FST, or outside the configured startKeyInclusive/endKeyExclusive
51// range of the Iterator.
52var ErrIteratorDone = errors.New("iterator-done")
53
54// BuilderOpts is a structure to let advanced users customize the behavior
55// of the builder and some aspects of the generated FST.
56type BuilderOpts struct {
57	Encoder           int
58	RegistryTableSize int
59	RegistryMRUSize   int
60}
61
62// New returns a new Builder which will stream out the
63// underlying representation to the provided Writer as the set is built.
64func New(w io.Writer, opts *BuilderOpts) (*Builder, error) {
65	return newBuilder(w, opts)
66}
67
68// Open loads the FST stored in the provided path
69func Open(path string) (*FST, error) {
70	return open(path)
71}
72
73// Load will return the FST represented by the provided byte slice.
74func Load(data []byte) (*FST, error) {
75	return new(data, nil)
76}
77
78// Merge will iterate through the provided Iterators, merge duplicate keys
79// with the provided MergeFunc, and build a new FST to the provided Writer.
80func Merge(w io.Writer, opts *BuilderOpts, itrs []Iterator, f MergeFunc) error {
81	builder, err := New(w, opts)
82	if err != nil {
83		return err
84	}
85
86	itr, err := NewMergeIterator(itrs, f)
87	for err == nil {
88		k, v := itr.Current()
89		err = builder.Insert(k, v)
90		if err != nil {
91			return err
92		}
93		err = itr.Next()
94	}
95
96	if err != nil && err != ErrIteratorDone {
97		return err
98	}
99
100	err = itr.Close()
101	if err != nil {
102		return err
103	}
104
105	err = builder.Close()
106	if err != nil {
107		return err
108	}
109
110	return nil
111}
112