func joinable(r1, r2 Row, bs map[string]bool) bool {
	for k := range bs {
		if !reflect.DeepEqual(r1[k], r2[k]) {
			return false
		}
	}
	return true
}
joinable return true if the values of the provided bindings are equal
for both provided rows.
package table
import (
	"bytes"
	"errors"
	"fmt"
	"io"
	"log"
	"reflect"
	"sort"
	"strings"
	"sync"
	"time"
	"github.com/google/badwolf/triple/literal"
	"github.com/google/badwolf/triple/node"
	"github.com/google/badwolf/triple/predicate"
)
type Table struct {
	AvailableBindings []string `json:"bindings,omitempty"`
	Data []Row `json:"rows,omitempty"`
	mbs map[string]bool
	mu sync.RWMutex
}
func New(bs []string) (*Table, error) {
	m := make(map[string]bool)
	for _, b := range bs {
		m[b] = true
	}
	if len(m) != len(bs) {
		return nil, fmt.Errorf("table.New does not allow duplicated bindings in %s", bs)
	}
	return &Table{
		AvailableBindings: bs,
		mbs:               m,
	}, nil
}
type Cell struct {
	S *string              `json:"s,omitempty"`
	N *node.Node           `json:"node,omitempty"`
	P *predicate.Predicate `json:"pred,omitempty"`
	L *literal.Literal     `json:"lit,omitempty"`
	T *time.Time           `json:"time,omitempty"`
}
func (c *Cell) String() string {
	if c.S != nil {
		return *c.S
	}
	if c.N != nil {
		return c.N.String()
	}
	if c.P != nil {
		return c.P.String()
	}
	if c.L != nil {
		return c.L.String()
	}
	if c.T != nil {
		return c.T.Format(time.RFC3339Nano)
	}
	return "<NULL>"
}
type Row map[string]*Cell
func (r Row) ToTextLine(res *bytes.Buffer, bs []string, sep string) error {
	cnt := len(bs)
	if sep == "" {
		sep = "\t"
	}
	for _, b := range bs {
		cnt--
		v := "<NULL>"
		if c, ok := r[b]; ok {
			v = c.String()
		}
		if _, err := res.WriteString(v); err != nil {
			return err
		}
		if cnt > 0 {
			res.WriteString(sep)
		}
	}
	return nil
}
func (t *Table) AddRow(r Row) {
	t.mu.Lock()
	if len(r) > 0 {
		delete(r, "")
		t.Data = append(t.Data, r)
	}
	t.mu.Unlock()
}
func (t *Table) NumRows() int {
	t.mu.RLock()
	defer t.mu.RUnlock()
	return len(t.Data)
}
func (t *Table) Row(i int) (Row, bool) {
	t.mu.RLock()
	defer t.mu.RUnlock()
	if i < 0 || i >= len(t.Data) {
		return nil, false
	}
	return t.Data[i], true
}
func (t *Table) Rows() []Row {
	t.mu.RLock()
	defer t.mu.RUnlock()
	return t.Data
}
func (t *Table) unsafeAddBindings(bs []string) {
	for _, b := range bs {
		if !t.mbs[b] {
			t.mbs[b] = true
			t.AvailableBindings = append(t.AvailableBindings, b)
		}
	}
}
func (t *Table) AddBindings(bs []string) {
	t.mu.Lock()
	t.unsafeAddBindings(bs)
	t.mu.Unlock()
}
func (t *Table) ProjectBindings(bs []string) error {
	t.mu.Lock()
	defer t.mu.Unlock()
	if len(t.Data) == 0 || len(t.mbs) == 0 {
		return nil
	}
	for _, b := range bs {
		if !t.mbs[b] {
			return fmt.Errorf("cannot project against unknown binding %s; known bindinds are %v", b, t.AvailableBindings)
		}
	}
	t.AvailableBindings = []string{}
	t.mbs = make(map[string]bool)
	t.unsafeAddBindings(bs)
	return nil
}
func (t *Table) HasBinding(b string) bool {
	t.mu.RLock()
	defer t.mu.RUnlock()
	return t.mbs[b]
}
func (t *Table) Bindings() []string {
	t.mu.RLock()
	defer t.mu.RUnlock()
	return t.AvailableBindings
}
func equalBindings(b1, b2 map[string]bool) bool {
	if len(b1) != len(b2) {
		return false
	}
	for k := range b1 {
		if !b2[k] {
			return false
		}
	}
	return true
}
func (t *Table) AppendTable(t2 *Table) error {
	t.mu.Lock()
	defer t.mu.Unlock()
	if t2 == nil {
		return nil
	}
	if len(t.AvailableBindings) > 0 && !equalBindings(t.mbs, t2.mbs) {
		return fmt.Errorf("AppendTable can only append to an empty table or equally binded table; instead got %v and %v", t.AvailableBindings, t2.AvailableBindings)
	}
	if len(t.AvailableBindings) == 0 {
		t.AvailableBindings, t.mbs = t2.AvailableBindings, t2.mbs
	}
	t.Data = append(t.Data, t2.Data...)
	return nil
}
func disjointBindings(b1, b2 map[string]bool) bool {
	for k := range b1 {
		if b2[k] {
			return false
		}
	}
	return true
}
func MergeRows(ms []Row) Row {
	res := make(map[string]*Cell)
	for _, om := range ms {
		for k, v := range om {
			if _, ok := res[k]; !ok {
				res[k] = v
			}
		}
	}
	return res
}
func (t *Table) DotProduct(t2 *Table) error {
	t.mu.Lock()
	defer t.mu.Unlock()
	if !disjointBindings(t.mbs, t2.mbs) {
		return fmt.Errorf("DotProduct operations requires disjoint bindings; instead got %v and %v", t.mbs, t2.mbs)
	}
	m := make(map[string]bool)
	for k := range t.mbs {
		m[k] = true
	}
	for k := range t2.mbs {
		m[k] = true
	}
	t.mbs = m
	t.AvailableBindings = []string{}
	for k := range t.mbs {
		t.AvailableBindings = append(t.AvailableBindings, k)
	}
	td := t.Data
	cnt, size := 0, len(td)*len(t2.Data)
	t.Data = make([]Row, size, size)  
	for _, r1 := range td {
		for _, r2 := range t2.Data {
			t.Data[cnt] = MergeRows([]Row{r1, r2})
			cnt++
		}
	}
	return nil
}
func (t *Table) LeftOptionalJoin(t2 *Table) error {
	if equalBindings(t.mbs, t2.mbs) || len(t2.mbs) == 0 {
		return nil
	}
	if disjointBindings(t.mbs, t2.mbs) {
		return t.DotProduct(t2)
	}
	joinWithRange(t, t2)
	return nil
}
func joinWithRange(t, t2 *Table) {
	ibs := intersectBindings(t.mbs, t2.mbs)
	ubs := unionBindings(t.mbs, t2.mbs)
	var sbs []string
	for k := range ibs {
		sbs = append(sbs, k)
	}
	sortTablesData(t, t2, sbs)
	var scfg SortConfig
	for _, k := range sbs {
		scfg = append(scfg, sortConfig{Binding: k})
	}
	t.mu.Lock()
	defer t.mu.Unlock()
	t2.mu.Lock()
	defer t2.mu.Unlock()
	var res []Row
	t2d := t2.Data
	lj, j := 0, 0
	for _, t1r := range t.Data {
		extended := false
		for j < len(t2d) && (joinable(t1r, t2d[j], ibs) || rowLess(t2d[j], t1r, scfg)) {
			if joinable(t1r, t2d[j], ibs) {
				res = append(res, extendRowWith(t1r, t2d[j]))
				extended = true
				j++
				continue
			}
			for j < len(t2d) && rowLess(t2d[j], t1r, scfg) {
				j++
				lj = j
			}
		}
		if !extended {
			res = append(res, extendRow(t1r, ubs))
		}
		j = lj
	}
	t.mbs = ubs
	t.AvailableBindings = nil
	for k := range ubs {
		t.AvailableBindings = append(t.AvailableBindings, k)
	}
	t.Data = res
}
func extendRow(r Row, bs map[string]bool) Row {
	nr := make(Row)
	for k, v := range r {
		nr[k] = v
	}
	for k := range bs {
		if _, ok := nr[k]; ok {
			continue
		}
		nr[k] = &Cell{}
	}
	return nr
}
func extendRowWith(r, r2 Row) Row {
	nr := make(Row)
	for k, v := range r {
		nr[k] = v
	}
	for k, v := range r2 {
		if _, ok := nr[k]; ok {
			continue
		}
		nr[k] = v
	}
	return nr
}
func intersectBindings(bs1, bs2 map[string]bool) map[string]bool {
	res := make(map[string]bool)
	for k1 := range bs1 {
		if _, ok := bs2[k1]; ok {
			res[k1] = true
		}
	}
	return res
}
func unionBindings(bs1, bs2 map[string]bool) map[string]bool {
	res := make(map[string]bool)
	for k := range bs1 {
		res[k] = true
	}
	for k := range bs2 {
		res[k] = true
	}
	return res
}
func sortTablesData(t, t2 *Table, bs []string) {
	t.mu.Lock()
	defer t.mu.Unlock()
	t2.mu.Lock()
	defer t2.mu.Unlock()
	d, d2 := t.Data, t2.Data
	var scfg SortConfig
	for _, k := range bs {
		scfg = append(scfg, sortConfig{Binding: k})
	}
	sortIt := func(dt []Row) {
		sort.Slice(dt, func(i, j int) bool {
			return rowLess(dt[i], dt[j], scfg)
		})
	}
	sortIt(d)
	sortIt(d2)
}