vendor/github.com/aclements/go-gg/table/table.go - perf - Git at Google

 // Copyright 2016 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 // Package table implements ordered, grouped two dimensional relations.
 //
 // There are two related abstractions: Table and Grouping.
 //
 // A Table is an ordered relation of rows and columns. Each column is
 // a Go slice and hence must be homogeneously typed, but different
 // columns may have different types. All columns in a Table have the
 // same number of rows.
 //
 // A Grouping generalizes a Table by grouping the Table's rows into
 // zero or more groups. A Table is itself a Grouping with zero or one
 // groups. Most operations take a Grouping and operate on each group
 // independently, though some operations sub-divide or combine groups.
 //
 // The structures of both Tables and Groupings are immutable. They are
 // constructed using a Builder or a GroupingBuilder, respectively, and
 // then "frozen" into their respective immutable data structures.
 package table

 import (
 	"fmt"
 	"reflect"

 	"github.com/aclements/go-gg/generic"
 	"github.com/aclements/go-gg/generic/slice"
 )

 // TODO
 //
 // Rename Table to T?
 //
 // Make Table an interface? Then columns could be constructed lazily.
 //
 // Do all transformation functions as func(g Grouping) Grouping? That
 // could be a "Transform" type that has easy methods for chaining. In
 // a lot of cases, transformation functions could just return the
 // Transform returned by another function (like MapTables).
 //
 // Make an error type for "unknown column".

 // A Table is an immutable, ordered two dimensional relation. It
 // consists of a set of named columns. Each column is a sequence of
 // values of a consistent type or a constant value. All (non-constant)
 // columns have the same length.
 //
 // The zero value of Table is the "empty table": it has no rows and no
 // columns. Note that a Table may have one or more columns, but no
 // rows; such a Table is *not* considered empty.
 //
 // A Table is also a trivial Grouping. If a Table is empty, it has no
 // groups and hence the zero value of Table is also the "empty group".
 // Otherwise, it consists only of the root group, RootGroupID.
 type Table struct {
 	cols     map[string]Slice
 	consts   map[string]interface{}
 	colNames []string
 	len      int
 }

 // A Builder constructs a Table one column at a time.
 //
 // The zero value of a Builder represents an empty Table.
 type Builder struct {
 	t Table
 }

 // A Grouping is an immutable set of tables with identical sets of
 // columns, each identified by a distinct GroupID.
 //
 // Visually, a Grouping can be thought of as follows:
 //
 //	   Col A  Col B  Col C
 //	------ group /a ------
 //	0   5.4    "x"     90
 //	1   -.2    "y"     30
 //	------ group /b ------
 //	0   9.3    "a"     10
 //
 // Like a Table, a Grouping's structure is immutable. To construct a
 // Grouping, use a GroupingBuilder.
 //
 // Despite the fact that GroupIDs form a hierarchy, a Grouping ignores
 // this hierarchy and simply operates on a flat map of distinct
 // GroupIDs to Tables.
 type Grouping interface {
 	// Columns returns the names of the columns in this Grouping,
 	// or nil if there are no Tables or the group consists solely
 	// of empty Tables. All Tables in this Grouping have the same
 	// set of columns.
 	Columns() []string

 	// Tables returns the group IDs of the tables in this
 	// Grouping.
 	Tables() []GroupID

 	// Table returns the Table in group gid, or nil if there is no
 	// such Table.
 	Table(gid GroupID) *Table
 }

 // A GroupingBuilder constructs a Grouping one table a time.
 //
 // The zero value of a GroupingBuilder represents an empty Grouping
 // with no tables and no columns.
 type GroupingBuilder struct {
 	g        groupedTable
 	colTypes []reflect.Type
 }

 type groupedTable struct {
 	tables   map[GroupID]*Table
 	groups   []GroupID
 	colNames []string
 }

 // A Slice is a Go slice value.
 //
 // This is primarily for documentation. There is no way to statically
 // enforce this in Go; however, functions that expect a Slice will
 // panic with a *generic.TypeError if passed a non-slice value.
 type Slice interface{}

 func reflectSlice(s Slice) reflect.Value {
 	rv := reflect.ValueOf(s)
 	if rv.Kind() != reflect.Slice {
 		panic(&generic.TypeError{rv.Type(), nil, "is not a slice"})
 	}
 	return rv
 }

 // NewBuilder returns a new Builder. If t is non-nil, it populates the
 // new Builder with the columns from t.
 func NewBuilder(t *Table) *Builder {
 	if t == nil {
 		return new(Builder)
 	}
 	b := Builder{Table{
 		cols:     make(map[string]Slice),
 		consts:   make(map[string]interface{}),
 		colNames: append([]string(nil), t.Columns()...),
 		len:      t.len,
 	}}
 	for k, v := range t.cols {
 		b.t.cols[k] = v
 	}
 	for k, v := range t.consts {
 		b.t.consts[k] = v
 	}
 	return &b
 }

 // Add adds a column to b, or removes the named column if data is nil.
 // If b already has a column with the given name, Add replaces it. If
 // data is non-nil, it must have the same length as any existing
 // columns or Add will panic.
 func (b *Builder) Add(name string, data Slice) *Builder {
 	if data == nil {
 		// Remove the column.
 		if _, ok := b.t.cols[name]; !ok {
 			if _, ok := b.t.consts[name]; !ok {
 				// Nothing to remove.
 				return b
 			}
 		}
 		delete(b.t.cols, name)
 		delete(b.t.consts, name)
 		for i, n := range b.t.colNames {
 			if n == name {
 				copy(b.t.colNames[i:], b.t.colNames[i+1:])
 				b.t.colNames = b.t.colNames[:len(b.t.colNames)-1]
 				break
 			}
 		}
 		return b
 	}

 	// Are we replacing an existing column?
 	_, replace := b.t.cols[name]
 	if !replace {
 		_, replace = b.t.consts[name]
 	}

 	// Check the column and add it.
 	rv := reflectSlice(data)
 	dataLen := rv.Len()
 	if len(b.t.cols) == 0 || (replace && len(b.t.cols) == 1) {
 		if b.t.cols == nil {
 			b.t.cols = make(map[string]Slice)
 		}
 		// First non-constant column (possibly replacing the
 		// only non-constant column).
 		b.t.cols[name] = data
 		b.t.len = dataLen
 	} else if b.t.len != dataLen {
 		panic(fmt.Sprintf("cannot add column %q with %d elements to table with %d rows", name, dataLen, b.t.len))
 	} else {
 		b.t.cols[name] = data
 	}

 	if replace {
 		// Make sure it's not in constants.
 		delete(b.t.consts, name)
 	} else {
 		b.t.colNames = append(b.t.colNames, name)
 	}

 	return b
 }

 // AddConst adds a constant column to b whose value is val. If b
 // already has a column with this name, AddConst replaces it.
 //
 // A constant column has the same value in every row of the Table. It
 // does not itself have an inherent length.
 func (b *Builder) AddConst(name string, val interface{}) *Builder {
 	// Are we replacing an existing column?
 	_, replace := b.t.cols[name]
 	if !replace {
 		_, replace = b.t.consts[name]
 	}

 	if b.t.consts == nil {
 		b.t.consts = make(map[string]interface{})
 	}
 	b.t.consts[name] = val

 	if replace {
 		// Make sure it's not in cols.
 		delete(b.t.cols, name)
 	} else {
 		b.t.colNames = append(b.t.colNames, name)
 	}

 	return b
 }

 // Has returns true if b has a column named "name".
 func (b *Builder) Has(name string) bool {
 	if _, ok := b.t.cols[name]; ok {
 		return true
 	}
 	if _, ok := b.t.consts[name]; ok {
 		return true
 	}
 	return false
 }

 // Done returns the constructed Table and resets b.
 func (b *Builder) Done() *Table {
 	if len(b.t.colNames) == 0 {
 		return new(Table)
 	}
 	t := b.t
 	b.t = Table{}
 	return &t
 }

 // Len returns the number of rows in Table t.
 func (t *Table) Len() int {
 	return t.len
 }

 // Columns returns the names of the columns in Table t, or nil if this
 // Table is empty.
 func (t *Table) Columns() []string {
 	return t.colNames
 }

 // Column returns the slice of data in column name of Table t, or nil
 // if there is no such column. If name is a constant column, this
 // returns a slice with the constant value repeated to the length of
 // the Table.
 func (t *Table) Column(name string) Slice {
 	if c, ok := t.cols[name]; ok {
 		// It's a regular column or a constant column with a
 		// cached expansion.
 		return c
 	}

 	if cv, ok := t.consts[name]; ok {
 		// Expand the constant column and cache the result.
 		expanded := slice.Repeat(cv, t.len)
 		t.cols[name] = expanded
 		return expanded
 	}

 	return nil
 }

 // MustColumn is like Column, but panics if there is no such column.
 func (t *Table) MustColumn(name string) Slice {
 	if c := t.Column(name); c != nil {
 		return c
 	}
 	panic(fmt.Sprintf("unknown column %q", name))
 }

 // Const returns the value of constant column name. If this column
 // does not exist or is not a constant column, Const returns nil,
 // false.
 func (t *Table) Const(name string) (val interface{}, ok bool) {
 	cv, ok := t.consts[name]
 	return cv, ok
 }

 // isEmpty returns true if t is an empty Table, meaning it has no rows
 // or columns.
 func (t *Table) isEmpty() bool {
 	return t.colNames == nil
 }

 // Tables returns the groups IDs in this Table. If t is empty, there
 // are no group IDs. Otherwise, there is only RootGroupID.
 func (t *Table) Tables() []GroupID {
 	if t.isEmpty() {
 		return []GroupID{}
 	}
 	return []GroupID{RootGroupID}
 }

 // Table returns t if gid is RootGroupID and t is not empty; otherwise
 // it returns nil.
 func (t *Table) Table(gid GroupID) *Table {
 	if gid == RootGroupID && !t.isEmpty() {
 		return t
 	}
 	return nil
 }

 // NewGroupingBuilder returns a new GroupingBuilder. If g is non-nil,
 // it populates the new GroupingBuilder with the tables from g.
 func NewGroupingBuilder(g Grouping) *GroupingBuilder {
 	if g == nil {
 		return new(GroupingBuilder)
 	}
 	b := GroupingBuilder{groupedTable{
 		tables:   make(map[GroupID]*Table),
 		groups:   append([]GroupID(nil), g.Tables()...),
 		colNames: append([]string(nil), g.Columns()...),
 	}, nil}
 	for _, gid := range g.Tables() {
 		t := g.Table(gid)
 		b.g.tables[gid] = t
 		if b.colTypes == nil {
 			b.colTypes = colTypes(t)
 		}
 	}
 	return &b
 }

 func colTypes(t *Table) []reflect.Type {
 	colTypes := make([]reflect.Type, len(t.colNames))
 	for i, col := range t.colNames {
 		if c, ok := t.cols[col]; ok {
 			colTypes[i] = reflect.TypeOf(c).Elem()
 		} else {
 			colTypes[i] = reflect.TypeOf(t.consts[col])
 		}
 	}
 	return colTypes
 }

 // Add adds a Table to b, or removes a table if t is nil. If t is the
 // empty Table, this is a no-op because the empty Table contains no
 // groups. If gid already exists, Add replaces it. Table t must have
 // the same columns as any existing Tables in this Grouping and they
 // must have identical types; otherwise, Add will panic.
 //
 // TODO This doesn't make it easy to combine two Groupings. It could
 // instead take a Grouping and reparent it.
 func (b *GroupingBuilder) Add(gid GroupID, t *Table) *GroupingBuilder {
 	if t == nil {
 		if _, ok := b.g.tables[gid]; !ok {
 			// Nothing to remove.
 			return b
 		}
 		delete(b.g.tables, gid)
 		for i, g2 := range b.g.groups {
 			if g2 == gid {
 				copy(b.g.groups[i:], b.g.groups[i+1:])
 				b.g.groups = b.g.groups[:len(b.g.groups)-1]
 				break
 			}
 		}
 		return b
 	}

 	if t != nil && t.isEmpty() {
 		// Adding an empty table has no effect.
 		return b
 	}

 	if len(b.g.groups) == 1 && b.g.groups[0] == gid {
 		// We're replacing the only group. This is allowed to
 		// change the shape of the Grouping.
 		b.g.tables[gid] = t
 		b.g.colNames = t.Columns()
 		b.colTypes = colTypes(t)
 		return b
 	} else if len(b.g.groups) == 0 {
 		b.g.tables = map[GroupID]*Table{gid: t}
 		b.g.groups = []GroupID{gid}
 		b.g.colNames = t.Columns()
 		b.colTypes = colTypes(t)
 		return b
 	}

 	// Check that t's column names match.
 	matches := true
 	if len(t.colNames) != len(b.g.colNames) {
 		matches = false
 	} else {
 		for i, n := range t.colNames {
 			if b.g.colNames[i] != n {
 				matches = false
 				break
 			}
 		}
 	}
 	if !matches {
 		panic(fmt.Sprintf("table columns %q do not match group columns %q", t.colNames, b.g.colNames))
 	}

 	// Check that t's column types match.
 	for i, col := range b.g.colNames {
 		t0 := b.colTypes[i]
 		var t1 reflect.Type
 		if c, ok := t.cols[col]; ok {
 			t1 = reflect.TypeOf(c).Elem()
 		} else if cv, ok := t.consts[col]; ok {
 			t1 = reflect.TypeOf(cv)
 		}
 		if t0 != t1 {
 			panic(&generic.TypeError{t0, t1, fmt.Sprintf("for column %q are not the same", col)})
 		}
 	}

 	// Add t.
 	if _, ok := b.g.tables[gid]; !ok {
 		b.g.groups = append(b.g.groups, gid)
 	}
 	b.g.tables[gid] = t

 	return b
 }

 // Done returns the constructed Grouping and resets b.
 func (b *GroupingBuilder) Done() Grouping {
 	if len(b.g.groups) == 0 {
 		return new(groupedTable)
 	}
 	g := b.g
 	b.g = groupedTable{}
 	return &g
 }

 func (g *groupedTable) Columns() []string {
 	return g.colNames
 }

 func (g *groupedTable) Tables() []GroupID {
 	return g.groups
 }

 func (g *groupedTable) Table(gid GroupID) *Table {
 	return g.tables[gid]
 }

 // ColType returns the type of column col in g. This will always be a
 // slice type, even if col is a constant column. ColType panics if col
 // is unknown.
 //
 // TODO: If I introduce a first-class representation for a grouped
 // column, this should probably be in that.
 func ColType(g Grouping, col string) reflect.Type {
 	tables := g.Tables()
 	if len(tables) == 0 {
 		panic(fmt.Sprintf("unknown column %q", col))
 	}
 	t0 := g.Table(tables[0])
 	if cv, ok := t0.Const(col); ok {
 		return reflect.SliceOf(reflect.TypeOf(cv))
 	}
 	return reflect.TypeOf(t0.MustColumn(col))
 }
	// Copyright 2016 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	// Package table implements ordered, grouped two dimensional relations.
	//
	// There are two related abstractions: Table and Grouping.
	//
	// A Table is an ordered relation of rows and columns. Each column is
	// a Go slice and hence must be homogeneously typed, but different
	// columns may have different types. All columns in a Table have the
	// same number of rows.
	//
	// A Grouping generalizes a Table by grouping the Table's rows into
	// zero or more groups. A Table is itself a Grouping with zero or one
	// groups. Most operations take a Grouping and operate on each group
	// independently, though some operations sub-divide or combine groups.
	//
	// The structures of both Tables and Groupings are immutable. They are
	// constructed using a Builder or a GroupingBuilder, respectively, and
	// then "frozen" into their respective immutable data structures.
	package table

	import (
	"fmt"
	"reflect"

	"github.com/aclements/go-gg/generic"
	"github.com/aclements/go-gg/generic/slice"
	)

	// TODO
	//
	// Rename Table to T?
	//
	// Make Table an interface? Then columns could be constructed lazily.
	//
	// Do all transformation functions as func(g Grouping) Grouping? That
	// could be a "Transform" type that has easy methods for chaining. In
	// a lot of cases, transformation functions could just return the
	// Transform returned by another function (like MapTables).
	//
	// Make an error type for "unknown column".

	// A Table is an immutable, ordered two dimensional relation. It
	// consists of a set of named columns. Each column is a sequence of
	// values of a consistent type or a constant value. All (non-constant)
	// columns have the same length.
	//
	// The zero value of Table is the "empty table": it has no rows and no
	// columns. Note that a Table may have one or more columns, but no
	// rows; such a Table is not considered empty.
	//
	// A Table is also a trivial Grouping. If a Table is empty, it has no
	// groups and hence the zero value of Table is also the "empty group".
	// Otherwise, it consists only of the root group, RootGroupID.
	type Table struct {
	cols map[string]Slice
	consts map[string]interface{}
	colNames []string
	len int
	}

	// A Builder constructs a Table one column at a time.
	//
	// The zero value of a Builder represents an empty Table.
	type Builder struct {
	t Table
	}

	// A Grouping is an immutable set of tables with identical sets of
	// columns, each identified by a distinct GroupID.
	//
	// Visually, a Grouping can be thought of as follows:
	//
	// Col A Col B Col C
	// ------ group /a ------
	// 0 5.4 "x" 90
	// 1 -.2 "y" 30
	// ------ group /b ------
	// 0 9.3 "a" 10
	//
	// Like a Table, a Grouping's structure is immutable. To construct a
	// Grouping, use a GroupingBuilder.
	//
	// Despite the fact that GroupIDs form a hierarchy, a Grouping ignores
	// this hierarchy and simply operates on a flat map of distinct
	// GroupIDs to Tables.
	type Grouping interface {
	// Columns returns the names of the columns in this Grouping,
	// or nil if there are no Tables or the group consists solely
	// of empty Tables. All Tables in this Grouping have the same
	// set of columns.
	Columns() []string

	// Tables returns the group IDs of the tables in this
	// Grouping.
	Tables() []GroupID

	// Table returns the Table in group gid, or nil if there is no
	// such Table.
	Table(gid GroupID) *Table
	}

	// A GroupingBuilder constructs a Grouping one table a time.
	//
	// The zero value of a GroupingBuilder represents an empty Grouping
	// with no tables and no columns.
	type GroupingBuilder struct {
	g groupedTable
	colTypes []reflect.Type
	}

	type groupedTable struct {
	tables map[GroupID]*Table
	groups []GroupID
	colNames []string
	}

	// A Slice is a Go slice value.
	//
	// This is primarily for documentation. There is no way to statically
	// enforce this in Go; however, functions that expect a Slice will
	// panic with a *generic.TypeError if passed a non-slice value.
	type Slice interface{}

	func reflectSlice(s Slice) reflect.Value {
	rv := reflect.ValueOf(s)
	if rv.Kind() != reflect.Slice {
	panic(&generic.TypeError{rv.Type(), nil, "is not a slice"})
	}
	return rv
	}

	// NewBuilder returns a new Builder. If t is non-nil, it populates the
	// new Builder with the columns from t.
	func NewBuilder(t Table) Builder {
	if t == nil {
	return new(Builder)
	}
	b := Builder{Table{
	cols: make(map[string]Slice),
	consts: make(map[string]interface{}),
	colNames: append([]string(nil), t.Columns()...),
	len: t.len,
	}}
	for k, v := range t.cols {
	b.t.cols[k] = v
	}
	for k, v := range t.consts {
	b.t.consts[k] = v
	}
	return &b
	}

	// Add adds a column to b, or removes the named column if data is nil.
	// If b already has a column with the given name, Add replaces it. If
	// data is non-nil, it must have the same length as any existing
	// columns or Add will panic.
	func (b Builder) Add(name string, data Slice) Builder {
	if data == nil {
	// Remove the column.
	if _, ok := b.t.cols[name]; !ok {
	if _, ok := b.t.consts[name]; !ok {
	// Nothing to remove.
	return b
	}
	}
	delete(b.t.cols, name)
	delete(b.t.consts, name)
	for i, n := range b.t.colNames {
	if n == name {
	copy(b.t.colNames[i:], b.t.colNames[i+1:])
	b.t.colNames = b.t.colNames[:len(b.t.colNames)-1]
	break
	}
	}
	return b
	}

	// Are we replacing an existing column?
	_, replace := b.t.cols[name]
	if !replace {
	_, replace = b.t.consts[name]
	}

	// Check the column and add it.
	rv := reflectSlice(data)
	dataLen := rv.Len()
	if len(b.t.cols) == 0 \|\| (replace && len(b.t.cols) == 1) {
	if b.t.cols == nil {
	b.t.cols = make(map[string]Slice)
	}
	// First non-constant column (possibly replacing the
	// only non-constant column).
	b.t.cols[name] = data
	b.t.len = dataLen
	} else if b.t.len != dataLen {
	panic(fmt.Sprintf("cannot add column %q with %d elements to table with %d rows", name, dataLen, b.t.len))
	} else {
	b.t.cols[name] = data
	}

	if replace {
	// Make sure it's not in constants.
	delete(b.t.consts, name)
	} else {
	b.t.colNames = append(b.t.colNames, name)
	}

	return b
	}

	// AddConst adds a constant column to b whose value is val. If b
	// already has a column with this name, AddConst replaces it.
	//
	// A constant column has the same value in every row of the Table. It
	// does not itself have an inherent length.
	func (b Builder) AddConst(name string, val interface{}) Builder {
	// Are we replacing an existing column?
	_, replace := b.t.cols[name]
	if !replace {
	_, replace = b.t.consts[name]
	}

	if b.t.consts == nil {
	b.t.consts = make(map[string]interface{})
	}
	b.t.consts[name] = val

	if replace {
	// Make sure it's not in cols.
	delete(b.t.cols, name)
	} else {
	b.t.colNames = append(b.t.colNames, name)
	}

	return b
	}

	// Has returns true if b has a column named "name".
	func (b *Builder) Has(name string) bool {
	if _, ok := b.t.cols[name]; ok {
	return true
	}
	if _, ok := b.t.consts[name]; ok {
	return true
	}
	return false
	}

	// Done returns the constructed Table and resets b.
	func (b Builder) Done() Table {
	if len(b.t.colNames) == 0 {
	return new(Table)
	}
	t := b.t
	b.t = Table{}
	return &t
	}

	// Len returns the number of rows in Table t.
	func (t *Table) Len() int {
	return t.len
	}

	// Columns returns the names of the columns in Table t, or nil if this
	// Table is empty.
	func (t *Table) Columns() []string {
	return t.colNames
	}

	// Column returns the slice of data in column name of Table t, or nil
	// if there is no such column. If name is a constant column, this
	// returns a slice with the constant value repeated to the length of
	// the Table.
	func (t *Table) Column(name string) Slice {
	if c, ok := t.cols[name]; ok {
	// It's a regular column or a constant column with a
	// cached expansion.
	return c
	}

	if cv, ok := t.consts[name]; ok {
	// Expand the constant column and cache the result.
	expanded := slice.Repeat(cv, t.len)
	t.cols[name] = expanded
	return expanded
	}

	return nil
	}

	// MustColumn is like Column, but panics if there is no such column.
	func (t *Table) MustColumn(name string) Slice {
	if c := t.Column(name); c != nil {
	return c
	}
	panic(fmt.Sprintf("unknown column %q", name))
	}

	// Const returns the value of constant column name. If this column
	// does not exist or is not a constant column, Const returns nil,
	// false.
	func (t *Table) Const(name string) (val interface{}, ok bool) {
	cv, ok := t.consts[name]
	return cv, ok
	}

	// isEmpty returns true if t is an empty Table, meaning it has no rows
	// or columns.
	func (t *Table) isEmpty() bool {
	return t.colNames == nil
	}

	// Tables returns the groups IDs in this Table. If t is empty, there
	// are no group IDs. Otherwise, there is only RootGroupID.
	func (t *Table) Tables() []GroupID {
	if t.isEmpty() {
	return []GroupID{}
	}
	return []GroupID{RootGroupID}
	}

	// Table returns t if gid is RootGroupID and t is not empty; otherwise
	// it returns nil.
	func (t Table) Table(gid GroupID) Table {
	if gid == RootGroupID && !t.isEmpty() {
	return t
	}
	return nil
	}

	// NewGroupingBuilder returns a new GroupingBuilder. If g is non-nil,
	// it populates the new GroupingBuilder with the tables from g.
	func NewGroupingBuilder(g Grouping) *GroupingBuilder {
	if g == nil {
	return new(GroupingBuilder)
	}
	b := GroupingBuilder{groupedTable{
	tables: make(map[GroupID]*Table),
	groups: append([]GroupID(nil), g.Tables()...),
	colNames: append([]string(nil), g.Columns()...),
	}, nil}
	for _, gid := range g.Tables() {
	t := g.Table(gid)
	b.g.tables[gid] = t
	if b.colTypes == nil {
	b.colTypes = colTypes(t)
	}
	}
	return &b
	}

	func colTypes(t *Table) []reflect.Type {
	colTypes := make([]reflect.Type, len(t.colNames))
	for i, col := range t.colNames {
	if c, ok := t.cols[col]; ok {
	colTypes[i] = reflect.TypeOf(c).Elem()
	} else {
	colTypes[i] = reflect.TypeOf(t.consts[col])
	}
	}
	return colTypes
	}

	// Add adds a Table to b, or removes a table if t is nil. If t is the
	// empty Table, this is a no-op because the empty Table contains no
	// groups. If gid already exists, Add replaces it. Table t must have
	// the same columns as any existing Tables in this Grouping and they
	// must have identical types; otherwise, Add will panic.
	//
	// TODO This doesn't make it easy to combine two Groupings. It could
	// instead take a Grouping and reparent it.
	func (b GroupingBuilder) Add(gid GroupID, t Table) *GroupingBuilder {
	if t == nil {
	if _, ok := b.g.tables[gid]; !ok {
	// Nothing to remove.
	return b
	}
	delete(b.g.tables, gid)
	for i, g2 := range b.g.groups {
	if g2 == gid {
	copy(b.g.groups[i:], b.g.groups[i+1:])
	b.g.groups = b.g.groups[:len(b.g.groups)-1]
	break
	}
	}
	return b
	}

	if t != nil && t.isEmpty() {
	// Adding an empty table has no effect.
	return b
	}

	if len(b.g.groups) == 1 && b.g.groups[0] == gid {
	// We're replacing the only group. This is allowed to
	// change the shape of the Grouping.
	b.g.tables[gid] = t
	b.g.colNames = t.Columns()
	b.colTypes = colTypes(t)
	return b
	} else if len(b.g.groups) == 0 {
	b.g.tables = map[GroupID]*Table{gid: t}
	b.g.groups = []GroupID{gid}
	b.g.colNames = t.Columns()
	b.colTypes = colTypes(t)
	return b
	}

	// Check that t's column names match.
	matches := true
	if len(t.colNames) != len(b.g.colNames) {
	matches = false
	} else {
	for i, n := range t.colNames {
	if b.g.colNames[i] != n {
	matches = false
	break
	}
	}
	}
	if !matches {
	panic(fmt.Sprintf("table columns %q do not match group columns %q", t.colNames, b.g.colNames))
	}

	// Check that t's column types match.
	for i, col := range b.g.colNames {
	t0 := b.colTypes[i]
	var t1 reflect.Type
	if c, ok := t.cols[col]; ok {
	t1 = reflect.TypeOf(c).Elem()
	} else if cv, ok := t.consts[col]; ok {
	t1 = reflect.TypeOf(cv)
	}
	if t0 != t1 {
	panic(&generic.TypeError{t0, t1, fmt.Sprintf("for column %q are not the same", col)})
	}
	}

	// Add t.
	if _, ok := b.g.tables[gid]; !ok {
	b.g.groups = append(b.g.groups, gid)
	}
	b.g.tables[gid] = t

	return b
	}

	// Done returns the constructed Grouping and resets b.
	func (b *GroupingBuilder) Done() Grouping {
	if len(b.g.groups) == 0 {
	return new(groupedTable)
	}
	g := b.g
	b.g = groupedTable{}
	return &g
	}

	func (g *groupedTable) Columns() []string {
	return g.colNames
	}

	func (g *groupedTable) Tables() []GroupID {
	return g.groups
	}

	func (g groupedTable) Table(gid GroupID) Table {
	return g.tables[gid]
	}

	// ColType returns the type of column col in g. This will always be a
	// slice type, even if col is a constant column. ColType panics if col
	// is unknown.
	//
	// TODO: If I introduce a first-class representation for a grouped
	// column, this should probably be in that.
	func ColType(g Grouping, col string) reflect.Type {
	tables := g.Tables()
	if len(tables) == 0 {
	panic(fmt.Sprintf("unknown column %q", col))
	}
	t0 := g.Table(tables[0])
	if cv, ok := t0.Const(col); ok {
	return reflect.SliceOf(reflect.TypeOf(cv))
	}
	return reflect.TypeOf(t0.MustColumn(col))
	}