Source File
	col.go

Belonging Package
	github.com/freeeve/gochickpeas

// Typed column readers: the key -> column lookup is done once via
// Snapshot.Col / Snapshot.RelCol, then narrowed to a typed reader -- the
// polars column(name).i64() shape. Dense columns read through their raw
// slice fast path; sparse columns binary-search, or read O(1) through a
// lazily built position index (Snapshot.ColIndexed / RelColIndexed).

package chickpeas

import (
	"encoding/binary"

	"github.com/freeeve/gochickpeas/internal/bitset"
)

// posIndex accelerates a sparse column's random reads: a presence bitmap
// with block ranks resolves pos -> pair slot in O(1) -- one rank read plus
// a bounded popcount, no hashing or per-probe branching. A sparse column's
// pair array is position-sorted (its own Get binary-searches it), so the
// rank IS the slot. nil means unindexed (dense and rank layouts are
// already O(1)).
type posIndex = *rankIndex

func buildPosIndex(c Column) posIndex {
	positions := make([]uint32, 0, c.Len())
	span := 0
	for pos := range c.Entries() {
		positions = append(positions, pos)
		if int(pos)+1 > span {
			span = int(pos) + 1
		}
	}
	r := buildRankIndex(positions, span)
	return &r
}

// readIndexed reads a position through the resolved index when present,
// else the column's own lookup.
func readIndexed(c Column, idx posIndex, pos uint32) (Value, bool) {
	if idx == nil {
		return c.Get(pos)
	}
	slot, ok := idx.slot(pos)
	if !ok {
		return Value{}, false
	}
	return valueAtSlot(c, uint32(slot))
}

// Col is a resolved property column, narrowed to a typed reader with I64 /
// F64 / Bool / Str. Build with Snapshot.Col (node columns, indexed by node
// id) or Snapshot.RelCol (rel columns, indexed by outgoing-CSR position).
type Col struct {
	col Column
	idx posIndex
}

// Dtype is the column's logical element type, for picking a typed reader
// without narrowing.
func (c Col) Dtype() Dtype { return c.col.Dtype() }

// Column is the raw generic reader.
func (c Col) Column() Column { return c.col }

// I64 narrows to a typed integer reader; a non-integer column reads back as
// absent, like a mistyped Prop.
func (c Col) I64() I64Col {
	r := I64Col{col: c.col, idx: c.idx}
	switch d := c.col.(type) {
	case denseI64Col:
		r.dense = d
	case denseI64NarrowCol:
		r.nv = &i64NarrowView{narrow: d.b, w: d.w, min: d.min}
	case denseI64BitCol:
		r.nv = &i64NarrowView{bits: d.bits, min: d.min}
	}
	return r
}

// F64 narrows to a typed float reader.
func (c Col) F64() F64Col {
	dense, _ := c.col.(denseF64Col)
	return F64Col{dense: dense, col: c.col, idx: c.idx}
}

// Bool narrows to a typed boolean reader.
func (c Col) Bool() BoolCol {
	var dense *bitset.Bits
	if d, ok := c.col.(denseBoolCol); ok {
		dense = d.bits
	}
	return BoolCol{dense: dense, col: c.col, idx: c.idx}
}

// Str narrows to a typed string reader exposing interned atom ids; resolve
// a comparison string to its atom once and compare ids.
func (c Col) Str() StrCol {
	dense, _ := c.col.(denseStrCol)
	return StrCol{dense: dense, col: c.col, idx: c.idx}
}

// i64NarrowView is the unpacked read state for the narrow and bit
// storage classes, held behind one pointer so I64Col itself stays small:
// Get has a value receiver, so every field added to I64Col is copied on
// every call -- unpacking these six words inline made each read pay a
// duffcopy that cost more than the decode it saved (task 300).
type i64NarrowView struct {
	// narrow is the byte-class delta vector (value = min + delta at
	// width w); bits is the two-valued bit class's vector (value =
	// min + bit).
	narrow []byte
	w      uint8
	min    int64
	bits   *bitset.Bits
}

// I64Col is a resolved integer column reader.
type I64Col struct {
	dense denseI64Col
	// nv is the narrow/bit-class read state (nil for other layouts),
	// one pointer so the value receiver stays cheap to copy.
	nv  *i64NarrowView
	col Column
	idx posIndex
}

// Get returns the value at pos (a node id for node columns, a CSR position
// for rel columns); ok is false when absent.
func (c I64Col) Get(pos uint32) (int64, bool) {
	if c.dense != nil {
		if int(pos) < len(c.dense) {
			return c.dense[pos], true
		}
		return 0, false
	}
	if c.nv != nil {
		return c.nv.get(pos)
	}
	v, ok := readIndexed(c.col, c.idx, pos)
	if !ok {
		return 0, false
	}
	return v.I64()
}

// get decodes pos from the narrow byte classes; the bit class splits out
// so this stays inlinable into Get -- the split plus the u48 single-load
// keeps a narrow read one call level flatter than the fallback path. The
// u48 arm bounds on i+8 against the 2-byte-padded buffer -- exact, since
// a valid slot satisfies i <= len-8 and the first out-of-range slot lands
// at i = len-2; narrower widths divide the unpadded length evenly.
func (v *i64NarrowView) get(pos uint32) (int64, bool) {
	if v.narrow == nil {
		return v.getBits(pos)
	}
	i := int(pos) * int(v.w)
	switch v.w {
	case 1:
		if i < len(v.narrow) {
			return v.min + int64(v.narrow[i]), true
		}
	case 2:
		if i+2 <= len(v.narrow) {
			return v.min + int64(binary.LittleEndian.Uint16(v.narrow[i:])), true
		}
	case 4:
		if i+4 <= len(v.narrow) {
			return v.min + int64(binary.LittleEndian.Uint32(v.narrow[i:])), true
		}
	default:
		if i+8 <= len(v.narrow) {
			return v.min + int64(binary.LittleEndian.Uint64(v.narrow[i:])&narrowU48Mask), true
		}
	}
	return 0, false
}

// getBits decodes pos from the two-valued bit class.
func (v *i64NarrowView) getBits(pos uint32) (int64, bool) {
	if int(pos) >= v.bits.Len() {
		return 0, false
	}
	if v.bits.Get(int(pos)) {
		return v.min + 1, true
	}
	return v.min, true
}

// Slice is the dense value slice indexed directly by position; ok is false
// for a sparse column (fall back to Get).
func (c I64Col) Slice() ([]int64, bool) {
	return c.dense, c.dense != nil
}

// GetMany reads the values at ids into vals with a presence mask -- the
// bulk form of Get for candidate-batch sweeps: the representation switch
// and the receiver hoist out of the loop, so a chunk pays one dispatch
// instead of a call chain per id. vals and present must be at least
// len(ids) long.
func (c I64Col) GetMany(ids []uint32, vals []int64, present []bool) {
	switch {
	case c.dense != nil:
		d := c.dense
		for i, id := range ids {
			if int(id) < len(d) {
				vals[i], present[i] = d[id], true
			} else {
				present[i] = false
			}
		}
	case c.nv != nil && c.nv.narrow != nil:
		v, b, mn := c.nv, c.nv.narrow, c.nv.min
		switch v.w {
		case 1:
			for i, id := range ids {
				if int(id) < len(b) {
					vals[i], present[i] = mn+int64(b[id]), true
				} else {
					present[i] = false
				}
			}
		case 2:
			for i, id := range ids {
				if j := int(id) * 2; j+2 <= len(b) {
					vals[i], present[i] = mn+int64(binary.LittleEndian.Uint16(b[j:])), true
				} else {
					present[i] = false
				}
			}
		case 4:
			for i, id := range ids {
				if j := int(id) * 4; j+4 <= len(b) {
					vals[i], present[i] = mn+int64(binary.LittleEndian.Uint32(b[j:])), true
				} else {
					present[i] = false
				}
			}
		default:
			// u48: the buffer carries a 2-byte pad, so the padded 8-byte
			// masked load bounds exactly like Get's arm.
			for i, id := range ids {
				if j := int(id) * 6; j+8 <= len(b) {
					vals[i], present[i] = mn+int64(binary.LittleEndian.Uint64(b[j:])&narrowU48Mask), true
				} else {
					present[i] = false
				}
			}
		}
	default:
		for i, id := range ids {
			vals[i], present[i] = c.Get(id)
		}
	}
}

// SliceRange is the dense-speed window of a column whose presence is one
// contiguous position run: values read as vals[pos-start], and a
// position outside [start, start+len) is absent. LDBC-shaped loaders
// assign each label a contiguous id block, so a label-scoped column
// stored sparse still reads at hoisted-slice speed through its window
// (the rcp twin's as_i64_slice_range, tasks rcp-265/072; a sparse
// column's pair array is position-sorted, so contiguous presence makes
// the value array itself the window -- the check is O(1) and nothing is
// built). ok=false for gapped presence or a non-integer column.
func (c I64Col) SliceRange() (start uint32, vals []int64, ok bool) {
	if c.dense != nil {
		return 0, c.dense, true
	}
	s, isSparse := c.col.(sparseI64Col)
	n := len(s.ids)
	if !isSparse || n == 0 || int(s.ids[n-1]-s.ids[0])+1 != n {
		return 0, nil, false
	}
	return s.ids[0], s.vals, true
}

// F64Col is a resolved float column reader.
type F64Col struct {
	dense denseF64Col
	col   Column
	idx   posIndex
}

// Get returns the value at pos; ok is false when absent.
func (c F64Col) Get(pos uint32) (float64, bool) {
	if c.dense != nil {
		if int(pos) < len(c.dense) {
			return c.dense[pos], true
		}
		return 0, false
	}
	v, ok := readIndexed(c.col, c.idx, pos)
	if !ok {
		return 0, false
	}
	return v.F64()
}

// Slice is the dense value slice; ok is false for a sparse column.
func (c F64Col) Slice() ([]float64, bool) {
	return c.dense, c.dense != nil
}

// SliceRange is I64Col.SliceRange for float columns.
func (c F64Col) SliceRange() (start uint32, vals []float64, ok bool) {
	if c.dense != nil {
		return 0, c.dense, true
	}
	s, isSparse := c.col.(sparseF64Col)
	n := len(s.ids)
	if !isSparse || n == 0 || int(s.ids[n-1]-s.ids[0])+1 != n {
		return 0, nil, false
	}
	return s.ids[0], s.vals, true
}

// BoolCol is a resolved boolean column reader.
type BoolCol struct {
	dense *bitset.Bits
	col   Column
	idx   posIndex
}

// Get returns the value at pos; ok is false when absent.
func (c BoolCol) Get(pos uint32) (bool, bool) {
	if c.dense != nil {
		if int(pos) < c.dense.Len() {
			return c.dense.Get(int(pos)), true
		}
		return false, false
	}
	v, ok := readIndexed(c.col, c.idx, pos)
	if !ok {
		return false, false
	}
	return v.Bool()
}

// Bits is the dense bit vector indexed directly by position; ok is false
// for a sparse column.
func (c BoolCol) Bits() (*bitset.Bits, bool) {
	return c.dense, c.dense != nil
}

// StrCol is a resolved string column reader exposing interned atom ids.
type StrCol struct {
	dense denseStrCol
	col   Column
	idx   posIndex
}

// ID returns the atom id at pos; ok is false when absent. Note atom 0 ("")
// in a dense column means missing -- Prop.Str folds that in; this raw
// reader does not.
func (c StrCol) ID(pos uint32) (uint32, bool) {
	if c.dense != nil {
		if int(pos) < len(c.dense) {
			return c.dense[pos], true
		}
		return 0, false
	}
	v, ok := readIndexed(c.col, c.idx, pos)
	if !ok {
		return 0, false
	}
	return v.StrID()
}

// IDs is the dense atom-id slice; ok is false for a sparse column.
func (c StrCol) IDs() ([]uint32, bool) {
	return c.dense, c.dense != nil
}

The pages are generated with Golds v0.8.7. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @zigo_101 (reachable from the left QR code) to get the latest news of Golds.