return zettel.Zettel{}, box.NewErrNotAllowed("GetZettel", user, zid)
}

func (pp *polBox) GetAllZettel(ctx context.Context, zid id.ZidO) ([]zettel.Zettel, error) {
	return pp.box.GetAllZettel(ctx, zid)
}

func (pp *polBox) FetchZids(ctx context.Context) (*id.SetO, error) {
	return nil, box.NewErrNotAllowed("fetch-zids", server.GetUser(ctx), id.InvalidO)
}

func (pp *polBox) GetMeta(ctx context.Context, zid id.ZidO) (*meta.Meta, error) {
	m, err := pp.box.GetMeta(ctx, zid)
	if err != nil {
		return nil, err

// Box is to be used outside the box package and its descendants.
type Box interface {
	BaseBox
	WriteBox

	// FetchZids returns the set of all zettel identifer managed by the box.
	FetchZids(ctx context.Context) (*id.SetO, error)

	// GetMeta returns the metadata of the zettel with the given identifier.
	GetMeta(context.Context, id.ZidO) (*meta.Meta, error)

	// SelectMeta returns a list of metadata that comply to the given selection criteria.
	// If `metaSeq` is `nil`, the box assumes metadata of all available zettel.
	SelectMeta(ctx context.Context, metaSeq []*meta.Meta, q *query.Query) ([]*meta.Meta, error)

	arNothing arAction = iota
	arReload
	arZettel
)

type anteroom struct {
	next    *anteroom
	waiting *id.SetO
	curLoad int
	reload  bool
}

type anteroomQueue struct {
	mx      sync.Mutex
	first   *anteroom

		ar.last = ar.first
		return
	}
	for room := ar.first; room != nil; room = room.next {
		if room.reload {
			continue // Do not put zettel in reload room
		}
		if room.waiting.Contains(zid) {
			// Zettel is already waiting. Nothing to do.
			return
		}
	}
	if room := ar.last; !room.reload && (ar.maxLoad == 0 || room.curLoad < ar.maxLoad) {
		room.waiting.Add(zid)
		room.curLoad++

func (ar *anteroomQueue) Reset() {
	ar.mx.Lock()
	defer ar.mx.Unlock()
	ar.first = &anteroom{next: nil, waiting: nil, curLoad: 0, reload: true}
	ar.last = ar.first
}

func (ar *anteroomQueue) Reload(allZids *id.SetO) {
	ar.mx.Lock()
	defer ar.mx.Unlock()
	ar.deleteReloadedRooms()

	if !allZids.IsEmpty() {
		ar.first = &anteroom{next: ar.first, waiting: allZids, curLoad: allZids.Length(), reload: true}
		if ar.first.next == nil {
			ar.last = ar.first
		}
	} else {
		ar.first = nil
		ar.last = nil
	}

	defer ar.mx.Unlock()
	first := ar.first
	if first != nil {
		if first.waiting == nil && first.reload {
			ar.removeFirst()
			return arReload, id.InvalidO, false
		}
		if zid, found := first.waiting.Pop(); found {
			if first.waiting.IsEmpty() {

				ar.removeFirst()
			}
			return arZettel, zid, first.reload
		}
		ar.removeFirst()
	}
	return arNothing, id.InvalidO, false

			result = append(result, z)
		}
	}
	return result, nil
}

// FetchZids returns the set of all zettel identifer managed by the box.
func (mgr *Manager) FetchZids(ctx context.Context) (*id.SetO, error) {
	mgr.mgrLog.Debug().Msg("FetchZids")
	if mgr.State() != box.StartStateStarted {
		return nil, box.ErrStopped
	}
	result := id.NewSetO()
	mgr.mgrMx.RLock()
	defer mgr.mgrMx.RUnlock()
	for _, p := range mgr.boxes {
		err := p.ApplyZid(ctx, func(zid id.ZidO) { result.Add(zid) }, func(id.ZidO) bool { return true })
		if err != nil {
			return nil, err
		}

	compSearch := q.RetrieveAndCompile(ctx, mgr, metaSeq)
	if result := compSearch.Result(); result != nil {
		mgr.mgrLog.Trace().Int("count", int64(len(result))).Msg("found without ApplyMeta")
		return result, nil
	}
	selected := map[id.ZidO]*meta.Meta{}
	for _, term := range compSearch.Terms {
		rejected := id.NewSetO()
		handleMeta := func(m *meta.Meta) {
			zid := m.ZidO
			if rejected.Contains(zid) {
				mgr.mgrLog.Trace().Zid(zid).Msg("SelectMeta/alreadyRejected")
				return
			}
			if _, ok := selected[zid]; ok {
				mgr.mgrLog.Trace().Zid(zid).Msg("SelectMeta/alreadySelected")
				return
			}

	"zettelstore.de/z/ast"
	"zettelstore.de/z/box/manager/store"
	"zettelstore.de/z/strfun"
	"zettelstore.de/z/zettel/id"
)

type collectData struct {
	refs  *id.SetO
	words store.WordSet
	urls  store.WordSet
}

func (data *collectData) initialize() {
	data.refs = id.NewSetO()
	data.words = store.NewWordSet()

	"zettelstore.de/z/zettel"
	"zettelstore.de/z/zettel/id"
	"zettelstore.de/z/zettel/meta"
)

// SearchEqual returns all zettel that contains the given exact word.
// The word must be normalized through Unicode NKFD, trimmed and not empty.
func (mgr *Manager) SearchEqual(word string) *id.SetO {
	found := mgr.idxStore.SearchEqual(word)
	mgr.idxLog.Debug().Str("word", word).Int("found", int64(found.Length())).Msg("SearchEqual")
	if msg := mgr.idxLog.Trace(); msg.Enabled() {
		msg.Str("ids", fmt.Sprint(found)).Msg("IDs")
	}
	return found
}

// SearchPrefix returns all zettel that have a word with the given prefix.
// The prefix must be normalized through Unicode NKFD, trimmed and not empty.
func (mgr *Manager) SearchPrefix(prefix string) *id.SetO {
	found := mgr.idxStore.SearchPrefix(prefix)
	mgr.idxLog.Debug().Str("prefix", prefix).Int("found", int64(found.Length())).Msg("SearchPrefix")
	if msg := mgr.idxLog.Trace(); msg.Enabled() {
		msg.Str("ids", fmt.Sprint(found)).Msg("IDs")
	}
	return found
}

// SearchSuffix returns all zettel that have a word with the given suffix.
// The suffix must be normalized through Unicode NKFD, trimmed and not empty.
func (mgr *Manager) SearchSuffix(suffix string) *id.SetO {
	found := mgr.idxStore.SearchSuffix(suffix)
	mgr.idxLog.Debug().Str("suffix", suffix).Int("found", int64(found.Length())).Msg("SearchSuffix")
	if msg := mgr.idxLog.Trace(); msg.Enabled() {
		msg.Str("ids", fmt.Sprint(found)).Msg("IDs")
	}
	return found
}

// SearchContains returns all zettel that contains the given string.
// The string must be normalized through Unicode NKFD, trimmed and not empty.
func (mgr *Manager) SearchContains(s string) *id.SetO {
	found := mgr.idxStore.SearchContains(s)
	mgr.idxLog.Debug().Str("s", s).Int("found", int64(found.Length())).Msg("SearchContains")
	if msg := mgr.idxLog.Trace(); msg.Enabled() {
		msg.Str("ids", fmt.Sprint(found)).Msg("IDs")
	}
	return found
}

// idxIndexer runs in the background and updates the index data structures.

		if !ok {
			return false
		}
	case _, ok := <-timer.C:
		if !ok {
			return false
		}
		mgr.idxStore.Optimize() // TODO: make it less often, for example once per 10 minutes
		timer.Reset(timerDuration)
	case <-mgr.done:
		if !timer.Stop() {
			<-timer.C
		}
		return false
	}

		}
	} else {
		stWords.Add(value)
	}
}

func (mgr *Manager) idxProcessData(ctx context.Context, zi *store.ZettelIndex, cData *collectData) {
	cData.refs.ForEach(func(ref id.ZidO) {
		if mgr.HasZettel(ctx, ref) {
			zi.AddBackRef(ref)
		} else {
			zi.AddDeadRef(ref)
		}
	})
	zi.SetWords(cData.words)
	zi.SetUrls(cData.urls)
}

func (mgr *Manager) idxUpdateValue(ctx context.Context, inverseKey, value string, zi *store.ZettelIndex) {
	zid, err := id.ParseO(value)
	if err != nil {

}

func (mgr *Manager) idxDeleteZettel(ctx context.Context, zid id.ZidO) {
	toCheck := mgr.idxStore.DeleteZettel(ctx, zid)
	mgr.idxCheckZettel(toCheck)
}

func (mgr *Manager) idxCheckZettel(s *id.SetO) {
	s.ForEach(func(zid id.ZidO) {
		mgr.idxAr.EnqueueZettel(zid)
	})
}

	"zettelstore.de/z/box/manager/store"
	"zettelstore.de/z/zettel/id"
	"zettelstore.de/z/zettel/meta"
)

type zettelData struct {
	meta      *meta.Meta // a local copy of the metadata, without computed keys
	dead      *id.SetO   // set of dead references in this zettel
	forward   *id.SetO   // set of forward references in this zettel
	backward  *id.SetO   // set of zettel that reference with zettel
	otherRefs map[string]bidiRefs
	words     []string // list of words of this zettel
	urls      []string // list of urls of this zettel
}

type bidiRefs struct {
	forward  *id.SetO
	backward *id.SetO
}

func (zd *zettelData) optimize() {
	zd.dead.Optimize()
	zd.forward.Optimize()
	zd.backward.Optimize()
	for _, bidi := range zd.otherRefs {
		bidi.forward.Optimize()
		bidi.backward.Optimize()
	}
}

type mapStore struct {
	mx     sync.RWMutex
	intern map[string]string // map to intern strings
	idx    map[id.ZidO]*zettelData
	dead   map[id.ZidO]*id.SetO // map dead refs where they occur
	words  stringRefs
	urls   stringRefs

	// Stats
	mxStats sync.Mutex
	updates uint64
}
type stringRefs map[string]*id.SetO

// New returns a new memory-based index store.
func New() store.Store {
	return &mapStore{
		intern: make(map[string]string, 1024),
		idx:    make(map[id.ZidO]*zettelData),
		dead:   make(map[id.ZidO]*id.SetO),
		words:  make(stringRefs),
		urls:   make(stringRefs),
	}
}

func (ms *mapStore) GetMeta(_ context.Context, zid id.ZidO) (*meta.Meta, error) {
	ms.mx.RLock()
	defer ms.mx.RUnlock()
	if zi, found := ms.idx[zid]; found && zi.meta != nil {
		// zi.meta is nil, if zettel was referenced, but is not indexed yet.
		return zi.meta.Clone(), nil
	}
	return nil, box.ErrZettelNotFound{Zid: zid}
}

func (ms *mapStore) Enrich(_ context.Context, m *meta.Meta) {
	if ms.doEnrich(m) {
		ms.mxStats.Lock()
		ms.updates++
		ms.mxStats.Unlock()
	}
}

func (ms *mapStore) doEnrich(m *meta.Meta) bool {
	ms.mx.RLock()
	defer ms.mx.RUnlock()
	zi, ok := ms.idx[m.ZidO]
	if !ok {
		return false
	}
	var updated bool
	if !zi.dead.IsEmpty() {
		m.Set(api.KeyDead, zi.dead.MetaString())
		updated = true
	}
	back := removeOtherMetaRefs(m, zi.backward.Clone())
	if !zi.backward.IsEmpty() {
		m.Set(api.KeyBackward, zi.backward.MetaString())
		updated = true
	}
	if !zi.forward.IsEmpty() {
		m.Set(api.KeyForward, zi.forward.MetaString())
		back.ISubstract(zi.forward)
		updated = true
	}
	for k, refs := range zi.otherRefs {
		if !refs.backward.IsEmpty() {
			m.Set(k, refs.backward.MetaString())
			back.ISubstract(refs.backward)
			updated = true
		}
	}
	if !back.IsEmpty() {
		m.Set(api.KeyBack, back.MetaString())
		updated = true
	}
	return updated
}

// SearchEqual returns all zettel that contains the given exact word.
// The word must be normalized through Unicode NKFD, trimmed and not empty.
func (ms *mapStore) SearchEqual(word string) *id.SetO {
	ms.mx.RLock()
	defer ms.mx.RUnlock()
	result := id.NewSetO()
	if refs, ok := ms.words[word]; ok {
		result = result.IUnion(refs)
	}
	if refs, ok := ms.urls[word]; ok {
		result = result.IUnion(refs)
	}
	zid, err := id.ParseO(word)
	if err != nil {
		return result
	}
	zi, ok := ms.idx[zid]
	if !ok {
		return result
	}

	return addBackwardZids(result, zid, zi)

}

// SearchPrefix returns all zettel that have a word with the given prefix.
// The prefix must be normalized through Unicode NKFD, trimmed and not empty.
func (ms *mapStore) SearchPrefix(prefix string) *id.SetO {
	ms.mx.RLock()
	defer ms.mx.RUnlock()
	result := ms.selectWithPred(prefix, strings.HasPrefix)
	l := len(prefix)
	if l > 14 {
		return result
	}

		minZid, err = id.ParseO(prefix + "00000000000000"[:14-l])
		if err != nil {
			return result
		}
	}
	for zid, zi := range ms.idx {
		if minZid <= zid && zid <= maxZid {
			result = addBackwardZids(result, zid, zi)
		}
	}
	return result
}

// SearchSuffix returns all zettel that have a word with the given suffix.
// The suffix must be normalized through Unicode NKFD, trimmed and not empty.
func (ms *mapStore) SearchSuffix(suffix string) *id.SetO {
	ms.mx.RLock()
	defer ms.mx.RUnlock()
	result := ms.selectWithPred(suffix, strings.HasSuffix)
	l := len(suffix)
	if l > 14 {
		return result
	}
	val, err := id.ParseUintO(suffix)
	if err != nil {
		return result
	}
	modulo := uint64(1)
	for range l {
		modulo *= 10
	}
	for zid, zi := range ms.idx {
		if uint64(zid)%modulo == val {
			result = addBackwardZids(result, zid, zi)
		}
	}
	return result
}

// SearchContains returns all zettel that contains the given string.
// The string must be normalized through Unicode NKFD, trimmed and not empty.
func (ms *mapStore) SearchContains(s string) *id.SetO {
	ms.mx.RLock()
	defer ms.mx.RUnlock()
	result := ms.selectWithPred(s, strings.Contains)
	if len(s) > 14 {
		return result
	}
	if _, err := id.ParseUintO(s); err != nil {
		return result
	}
	for zid, zi := range ms.idx {
		if strings.Contains(zid.String(), s) {
			result = addBackwardZids(result, zid, zi)
		}
	}
	return result
}

func (ms *mapStore) selectWithPred(s string, pred func(string, string) bool) *id.SetO {
	// Must only be called if ms.mx is read-locked!
	result := id.NewSetO()
	for word, refs := range ms.words {
		if !pred(word, s) {
			continue
		}
		result.IUnion(refs)
	}
	for u, refs := range ms.urls {
		if !pred(u, s) {
			continue
		}
		result.IUnion(refs)
	}
	return result
}

func addBackwardZids(result *id.SetO, zid id.ZidO, zi *zettelData) *id.SetO {
	// Must only be called if ms.mx is read-locked!
	result = result.Add(zid)
	result = result.IUnion(zi.backward)
	for _, mref := range zi.otherRefs {
		result = result.IUnion(mref.backward)
	}
	return result
}










func removeOtherMetaRefs(m *meta.Meta, back *id.SetO) *id.SetO {
	for _, p := range m.PairsRest() {
		switch meta.Type(p.Key) {
		case meta.TypeID:
			if zid, err := id.ParseO(p.Value); err == nil {
				back = back.Remove(zid)
			}
		case meta.TypeIDSet:
			for _, val := range meta.ListFromValue(p.Value) {
				if zid, err := id.ParseO(val); err == nil {
					back = back.Remove(zid)
				}
			}
		}
	}
	return back
}

func (ms *mapStore) UpdateReferences(_ context.Context, zidx *store.ZettelIndex) *id.SetO {
	ms.mx.Lock()
	defer ms.mx.Unlock()
	m := ms.makeMeta(zidx)
	zi, ziExist := ms.idx[zidx.Zid]
	if !ziExist || zi == nil {
		zi = &zettelData{}
		ziExist = false
	}

	// Is this zettel an old dead reference mentioned in other zettel?
	var toCheck *id.SetO
	if refs, ok := ms.dead[zidx.Zid]; ok {
		// These must be checked later again
		toCheck = refs
		delete(ms.dead, zidx.Zid)
	}

	zi.meta = m
	ms.updateDeadReferences(zidx, zi)
	ids := ms.updateForwardBackwardReferences(zidx, zi)
	toCheck = toCheck.IUnion(ids)
	ids = ms.updateMetadataReferences(zidx, zi)
	toCheck = toCheck.IUnion(ids)
	zi.words = updateStrings(zidx.Zid, ms.words, zi.words, zidx.GetWords())
	zi.urls = updateStrings(zidx.Zid, ms.urls, zi.urls, zidx.GetUrls())

	// Check if zi must be inserted into ms.idx
	if !ziExist {
		ms.idx[zidx.Zid] = zi
	}
	zi.optimize()
	return toCheck
}

var internableKeys = map[string]bool{
	api.KeyRole:      true,
	api.KeySyntax:    true,
	api.KeyFolgeRole: true,
	api.KeyLang:      true,
	api.KeyReadOnly:  true,
}

func isInternableValue(key string) bool {
	if internableKeys[key] {
		return true
	}
	return strings.HasSuffix(key, meta.SuffixKeyRole)
}

func (ms *mapStore) internString(s string) string {
	if is, found := ms.intern[s]; found {
		return is
	}
	ms.intern[s] = s
	return s
}

func (ms *mapStore) makeMeta(zidx *store.ZettelIndex) *meta.Meta {
	origM := zidx.GetMeta()
	copyM := meta.New(origM.ZidO)
	for _, p := range origM.Pairs() {
		key := ms.internString(p.Key)
		if isInternableValue(key) {
			copyM.Set(key, ms.internString(p.Value))
		} else if key == api.KeyBoxNumber || !meta.IsComputed(key) {
			copyM.Set(key, p.Value)
		}
	}
	return copyM
}

func (ms *mapStore) updateDeadReferences(zidx *store.ZettelIndex, zi *zettelData) {
	// Must only be called if ms.mx is write-locked!
	drefs := zidx.GetDeadRefs()
	newRefs, remRefs := zi.dead.Diff(drefs)
	zi.dead = drefs
	remRefs.ForEach(func(ref id.ZidO) {
		ms.dead[ref] = ms.dead[ref].Remove(zidx.Zid)
	})
	newRefs.ForEach(func(ref id.ZidO) {
		ms.dead[ref] = ms.dead[ref].Add(zidx.Zid)
	})
}

func (ms *mapStore) updateForwardBackwardReferences(zidx *store.ZettelIndex, zi *zettelData) *id.SetO {
	// Must only be called if ms.mx is write-locked!
	brefs := zidx.GetBackRefs()
	newRefs, remRefs := zi.forward.Diff(brefs)
	zi.forward = brefs

	var toCheck *id.SetO
	remRefs.ForEach(func(ref id.ZidO) {
		bzi := ms.getOrCreateEntry(ref)
		bzi.backward = bzi.backward.Remove(zidx.Zid)
		if bzi.meta == nil {
			toCheck = toCheck.Add(ref)
		}
	})
	newRefs.ForEach(func(ref id.ZidO) {
		bzi := ms.getOrCreateEntry(ref)
		bzi.backward = bzi.backward.Add(zidx.Zid)
		if bzi.meta == nil {
			toCheck = toCheck.Add(ref)
		}
	})
	return toCheck
}

func (ms *mapStore) updateMetadataReferences(zidx *store.ZettelIndex, zi *zettelData) *id.SetO {
	// Must only be called if ms.mx is write-locked!
	inverseRefs := zidx.GetInverseRefs()
	for key, mr := range zi.otherRefs {
		if _, ok := inverseRefs[key]; ok {
			continue
		}
		ms.removeInverseMeta(zidx.Zid, key, mr.forward)
	}
	if zi.otherRefs == nil {
		zi.otherRefs = make(map[string]bidiRefs)
	}
	var toCheck *id.SetO
	for key, mrefs := range inverseRefs {
		mr := zi.otherRefs[key]
		newRefs, remRefs := mr.forward.Diff(mrefs)
		mr.forward = mrefs
		zi.otherRefs[key] = mr

		newRefs.ForEach(func(ref id.ZidO) {
			bzi := ms.getOrCreateEntry(ref)
			if bzi.otherRefs == nil {
				bzi.otherRefs = make(map[string]bidiRefs)
			}
			bmr := bzi.otherRefs[key]
			bmr.backward = bmr.backward.Add(zidx.Zid)
			bzi.otherRefs[key] = bmr
			if bzi.meta == nil {
				toCheck = toCheck.Add(ref)
			}
		})

		ms.removeInverseMeta(zidx.Zid, key, remRefs)
	}
	return toCheck
}

func updateStrings(zid id.ZidO, srefs stringRefs, prev []string, next store.WordSet) []string {
	newWords, removeWords := next.Diff(prev)
	for _, word := range newWords {




		srefs[word] = srefs[word].Add(zid)
	}
	for _, word := range removeWords {
		refs, ok := srefs[word]
		if !ok {
			continue
		}
		refs = refs.Remove(zid)
		if refs.IsEmpty() {
			delete(srefs, word)
			continue
		}
		srefs[word] = refs
	}
	return next.Words()
}

func (ms *mapStore) getOrCreateEntry(zid id.ZidO) *zettelData {
	// Must only be called if ms.mx is write-locked!
	if zi, ok := ms.idx[zid]; ok {
		return zi
	}
	zi := &zettelData{}
	ms.idx[zid] = zi
	return zi
}

func (ms *mapStore) RenameZettel(_ context.Context, curZid, newZid id.ZidO) *id.SetO {
	ms.mx.Lock()
	defer ms.mx.Unlock()

	curZi, curFound := ms.idx[curZid]
	_, newFound := ms.idx[newZid]
	if !curFound || newFound {
		return nil
	}
	newZi := &zettelData{
		meta:      copyMeta(curZi.meta, newZid),
		dead:      ms.copyDeadReferences(curZi.dead),
		forward:   ms.copyForward(curZi.forward, newZid),
		backward:  nil, // will be done through tocheck
		otherRefs: nil, // TODO: check if this will be done through toCheck
		words:     copyStrings(ms.words, curZi.words, newZid),
		urls:      copyStrings(ms.urls, curZi.urls, newZid),
	}

	ms.idx[newZid] = newZi
	toCheck := ms.doDeleteZettel(curZid)
	toCheck = toCheck.IUnion(ms.dead[newZid])
	delete(ms.dead, newZid)
	toCheck = toCheck.Add(newZid) // should update otherRefs
	return toCheck
}
func copyMeta(m *meta.Meta, newZid id.ZidO) *meta.Meta {
	result := m.Clone()
	result.ZidO = newZid
	return result
}

func (ms *mapStore) copyDeadReferences(curDead *id.SetO) *id.SetO {
	// Must only be called if ms.mx is write-locked!
	curDead.ForEach(func(ref id.ZidO) {



		ms.dead[ref] = ms.dead[ref].Add(ref)
	})


	return curDead.Clone()
}
func (ms *mapStore) copyForward(curForward *id.SetO, newZid id.ZidO) *id.SetO {
	// Must only be called if ms.mx is write-locked!
	curForward.ForEach(func(ref id.ZidO) {



		if fzi, found := ms.idx[ref]; found {
			fzi.backward = fzi.backward.Add(newZid)
		}


	})
	return curForward.Clone()
}

func copyStrings(msStringMap stringRefs, curStrings []string, newZid id.ZidO) []string {
	// Must only be called if ms.mx is write-locked!
	if l := len(curStrings); l > 0 {
		result := make([]string, l)
		for i, s := range curStrings {
			result[i] = s
			msStringMap[s] = msStringMap[s].Add(newZid)
		}
		return result
	}
	return nil
}

func (ms *mapStore) DeleteZettel(_ context.Context, zid id.ZidO) *id.SetO {
	ms.mx.Lock()
	defer ms.mx.Unlock()
	return ms.doDeleteZettel(zid)
}

func (ms *mapStore) doDeleteZettel(zid id.ZidO) *id.SetO {
	// Must only be called if ms.mx is write-locked!
	zi, ok := ms.idx[zid]
	if !ok {
		return nil
	}

	ms.deleteDeadSources(zid, zi)
	toCheck := ms.deleteForwardBackward(zid, zi)
	for key, mrefs := range zi.otherRefs {
		ms.removeInverseMeta(zid, key, mrefs.forward)
	}
	deleteStrings(ms.words, zi.words, zid)
	deleteStrings(ms.urls, zi.urls, zid)
	delete(ms.idx, zid)
	return toCheck
}

func (ms *mapStore) deleteDeadSources(zid id.ZidO, zi *zettelData) {
	// Must only be called if ms.mx is write-locked!
	zi.dead.ForEach(func(ref id.ZidO) {
		if drefs, ok := ms.dead[ref]; ok {
			if drefs = drefs.Remove(zid); drefs.IsEmpty() {

				delete(ms.dead, ref)
			} else {
				ms.dead[ref] = drefs
			}
		}
	})
}

func (ms *mapStore) deleteForwardBackward(zid id.ZidO, zi *zettelData) *id.SetO {
	// Must only be called if ms.mx is write-locked!
	zi.forward.ForEach(func(ref id.ZidO) {
		if fzi, ok := ms.idx[ref]; ok {
			fzi.backward = fzi.backward.Remove(zid)
		}
	})

	var toCheck *id.SetO
	zi.backward.ForEach(func(ref id.ZidO) {
		if bzi, ok := ms.idx[ref]; ok {
			bzi.forward = bzi.forward.Remove(zid)
			toCheck = toCheck.Add(ref)
		}
	})
	return toCheck
}

func (ms *mapStore) removeInverseMeta(zid id.ZidO, key string, forward *id.SetO) {
	// Must only be called if ms.mx is write-locked!
	forward.ForEach(func(ref id.ZidO) {
		bzi, ok := ms.idx[ref]
		if !ok || bzi.otherRefs == nil {
			return
		}
		bmr, ok := bzi.otherRefs[key]
		if !ok {
			return
		}
		bmr.backward = bmr.backward.Remove(zid)
		if !bmr.backward.IsEmpty() || !bmr.forward.IsEmpty() {
			bzi.otherRefs[key] = bmr
		} else {
			delete(bzi.otherRefs, key)
			if len(bzi.otherRefs) == 0 {
				bzi.otherRefs = nil
			}
		}
	})
}

func deleteStrings(msStringMap stringRefs, curStrings []string, zid id.ZidO) {
	// Must only be called if ms.mx is write-locked!
	for _, word := range curStrings {
		refs, ok := msStringMap[word]
		if !ok {
			continue
		}
		refs = refs.Remove(zid)
		if refs.IsEmpty() {
			delete(msStringMap, word)
			continue
		}
		msStringMap[word] = refs
	}
}

func (ms *mapStore) Optimize() {
	ms.mx.Lock()
	defer ms.mx.Unlock()

	// No need to optimize ms.idx: is already done via ms.UpdateReferences
	for _, dead := range ms.dead {
		dead.Optimize()
	}
	for _, s := range ms.words {
		s.Optimize()
	}
	for _, s := range ms.urls {
		s.Optimize()
	}
}

func (ms *mapStore) ReadStats(st *store.Stats) {
	ms.mx.RLock()
	st.Zettel = len(ms.idx)
	st.Words = uint64(len(ms.words))
	st.Urls = uint64(len(ms.urls))
	ms.mx.RUnlock()
	ms.mxStats.Lock()
	st.Updates = ms.updates
	ms.mxStats.Unlock()
}

func (ms *mapStore) Dump(w io.Writer) {
	ms.mx.RLock()
	defer ms.mx.RUnlock()

	io.WriteString(w, "=== Dump\n")
	ms.dumpIndex(w)
	ms.dumpDead(w)
	dumpStringRefs(w, "Words", "", "", ms.words)
	dumpStringRefs(w, "URLs", "[[", "]]", ms.urls)
}

func (ms *mapStore) dumpIndex(w io.Writer) {
	if len(ms.idx) == 0 {
		return
	}
	io.WriteString(w, "==== Zettel Index\n")
	zids := make(id.SliceO, 0, len(ms.idx))
	for id := range ms.idx {
		zids = append(zids, id)
	}
	zids.Sort()
	for _, id := range zids {
		fmt.Fprintln(w, "=====", id)
		zi := ms.idx[id]
		if !zi.dead.IsEmpty() {
			fmt.Fprintln(w, "* Dead:", zi.dead)
		}
		dumpSet(w, "* Forward:", zi.forward)
		dumpSet(w, "* Backward:", zi.backward)

		otherRefs := make([]string, 0, len(zi.otherRefs))
		for k := range zi.otherRefs {
			otherRefs = append(otherRefs, k)
		}
		slices.Sort(otherRefs)
		for _, k := range otherRefs {
			fmt.Fprintln(w, "* Meta", k)
			dumpSet(w, "** Forward:", zi.otherRefs[k].forward)
			dumpSet(w, "** Backward:", zi.otherRefs[k].backward)
		}
		dumpStrings(w, "* Words", "", "", zi.words)
		dumpStrings(w, "* URLs", "[[", "]]", zi.urls)
	}
}

func (ms *mapStore) dumpDead(w io.Writer) {
	if len(ms.dead) == 0 {
		return
	}
	fmt.Fprintf(w, "==== Dead References\n")
	zids := make(id.SliceO, 0, len(ms.dead))
	for id := range ms.dead {
		zids = append(zids, id)
	}
	zids.Sort()
	for _, id := range zids {
		fmt.Fprintln(w, ";", id)
		fmt.Fprintln(w, ":", ms.dead[id])
	}
}

func dumpSet(w io.Writer, prefix string, s *id.SetO) {
	if !s.IsEmpty() {
		io.WriteString(w, prefix)
		s.ForEach(func(zid id.ZidO) {
			io.WriteString(w, " ")
			w.Write(zid.Bytes())
		})
		fmt.Fprintln(w)
	}
}

func dumpStrings(w io.Writer, title, preString, postString string, slice []string) {
	if len(slice) > 0 {
		sl := make([]string, len(slice))
		copy(sl, slice)
		slices.Sort(sl)
		fmt.Fprintln(w, title)
		for _, s := range sl {

	GetMeta(context.Context, id.ZidO) (*meta.Meta, error)

	// Entrich metadata with data from store.
	Enrich(ctx context.Context, m *meta.Meta)

	// UpdateReferences for a specific zettel.
	// Returns set of zettel identifier that must also be checked for changes.
	UpdateReferences(context.Context, *ZettelIndex) *id.SetO

	// RenameZettel changes all references of current zettel identifier to new
	// zettel identifier.
	RenameZettel(_ context.Context, curZid, newZid id.ZidO) *id.SetO

	// DeleteZettel removes index data for given zettel.
	// Returns set of zettel identifier that must also be checked for changes.
	DeleteZettel(context.Context, id.ZidO) *id.SetO

	// Optimize removes unneeded space.
	Optimize()

	// ReadStats populates st with store statistics.
	ReadStats(st *Stats)

	// Dump the content to a Writer.
	Dump(io.Writer)
}

import (
	"zettelstore.de/z/zettel/id"
	"zettelstore.de/z/zettel/meta"
)

// ZettelIndex contains all index data of a zettel.
type ZettelIndex struct {
	Zid         id.ZidO             // zid of the indexed zettel
	meta        *meta.Meta          // full metadata
	backrefs    *id.SetO            // set of back references
	inverseRefs map[string]*id.SetO // references of inverse keys
	deadrefs    *id.SetO            // set of dead references
	words       WordSet
	urls        WordSet
}

// NewZettelIndex creates a new zettel index.
func NewZettelIndex(m *meta.Meta) *ZettelIndex {
	return &ZettelIndex{
		Zid:         m.ZidO,
		meta:        m,
		backrefs:    id.NewSetO(),
		inverseRefs: make(map[string]*id.SetO),
		deadrefs:    id.NewSetO(),
	}
}

// AddBackRef adds a reference to a zettel where the current zettel links to
// without any more information.
func (zi *ZettelIndex) AddBackRef(zid id.ZidO) { zi.backrefs.Add(zid) }



// AddInverseRef adds a named reference to a zettel. On that zettel, the given
// metadata key should point back to the current zettel.
func (zi *ZettelIndex) AddInverseRef(key string, zid id.ZidO) {
	if zids, ok := zi.inverseRefs[key]; ok {
		zids.Add(zid)
		return

// SetWords sets the words to the given value.
func (zi *ZettelIndex) SetWords(words WordSet) { zi.words = words }

// SetUrls sets the words to the given value.
func (zi *ZettelIndex) SetUrls(urls WordSet) { zi.urls = urls }

// GetDeadRefs returns all dead references as a sorted list.
func (zi *ZettelIndex) GetDeadRefs() *id.SetO { return zi.deadrefs }

// GetMeta return just the raw metadata.
func (zi *ZettelIndex) GetMeta() *meta.Meta { return zi.meta }

// GetBackRefs returns all back references as a sorted list.
func (zi *ZettelIndex) GetBackRefs() *id.SetO { return zi.backrefs }

// GetInverseRefs returns all inverse meta references as a map of strings to a sorted list of references
func (zi *ZettelIndex) GetInverseRefs() map[string]*id.SetO {
	if len(zi.inverseRefs) == 0 {
		return nil
	}
	result := make(map[string]*id.SetO, len(zi.inverseRefs))
	for key, refs := range zi.inverseRefs {
		result[key] = refs
	}
	return result
}

// GetWords returns a reference to the set of words. It must not be modified.
func (zi *ZettelIndex) GetWords() WordSet { return zi.words }

// GetUrls returns a reference to the set of URLs. It must not be modified.
func (zi *ZettelIndex) GetUrls() WordSet { return zi.urls }

module zettelstore.de/z

go 1.22

require (
	github.com/fsnotify/fsnotify v1.7.0
	github.com/yuin/goldmark v1.7.3
	golang.org/x/crypto v0.24.0
	golang.org/x/term v0.21.0
	golang.org/x/text v0.16.0
	t73f.de/r/sx v0.0.0-20240513163553-ec4fcc6539ca
	t73f.de/r/sxwebs v0.0.0-20240613142113-66fc5a284245
	t73f.de/r/zsc v0.0.0-20240620163129-e0d62ad54c46
)

github.com/fsnotify/fsnotify v1.7.0 h1:8JEhPFa5W2WU7YfeZzPNqzMP6Lwt7L2715Ggo0nosvA=
github.com/fsnotify/fsnotify v1.7.0/go.mod h1:40Bi/Hjc2AVfZrqy+aj+yEI+/bRxZnMJyTJwOpGvigM=
github.com/yuin/goldmark v1.7.3 h1:fdk0a/y60GsS4NbEd13GSIP+d8OjtTkmluY32Dy1Z/A=
github.com/yuin/goldmark v1.7.3/go.mod h1:uzxRWxtg69N339t3louHJ7+O03ezfj6PlliRlaOzY1E=
golang.org/x/crypto v0.24.0 h1:mnl8DM0o513X8fdIkmyFE/5hTYxbwYOjDS/+rK6qpRI=
golang.org/x/crypto v0.24.0/go.mod h1:Z1PMYSOR5nyMcyAVAIQSKCDwalqy85Aqn1x3Ws4L5DM=
golang.org/x/sys v0.21.0 h1:rF+pYz3DAGSQAxAu1CbC7catZg4ebC4UIeIhKxBZvws=
golang.org/x/sys v0.21.0/go.mod h1:/VUhepiaJMQUp4+oa/7Zr1D23ma6VTLIYjOOTFZPUcA=
golang.org/x/term v0.21.0 h1:WVXCp+/EBEHOj53Rvu+7KiT/iElMrO8ACK16SMZ3jaA=
golang.org/x/term v0.21.0/go.mod h1:ooXLefLobQVslOqselCNF4SxFAaoS6KujMbsGzSDmX0=
golang.org/x/text v0.16.0 h1:a94ExnEXNtEwYLGJSIUxnWoxoRz/ZcCsV63ROupILh4=

	old[n-1].meta = nil // avoid memory leak
	*q = old[0 : n-1]
	return item
}

type contextTask struct {
	port     ContextPort
	seen     *id.SetO
	queue    ztlCtxQueue
	maxCost  float64
	limit    int
	tagMetas map[string][]*meta.Meta
	tagZids  map[string]*id.SetO    // just the zids of tagMetas
	metaZid  map[id.ZidO]*meta.Meta // maps zid to meta for all meta retrieved with tags
}

func newQueue(startSeq []*meta.Meta, maxCost float64, limit int, port ContextPort) *contextTask {
	result := &contextTask{
		port:     port,
		seen:     id.NewSetO(),
		maxCost:  maxCost,
		limit:    limit,
		tagMetas: make(map[string][]*meta.Meta),
		tagZids:  make(map[string]*id.SetO),
		metaZid:  make(map[id.ZidO]*meta.Meta),
	}

	queue := make(ztlCtxQueue, 0, len(startSeq))
	for _, m := range startSeq {
		queue = append(queue, ztlCtxItem{cost: 1, meta: m})
	}

	}
}

func (ct *contextTask) addMeta(m *meta.Meta, newCost float64) {
	// If len(zc.seen) <= 1, the initial zettel is processed. In this case allow all
	// other zettel that are directly reachable, without taking the cost into account.
	// Of course, the limit ist still relevant.
	if !ct.hasLimit() && (ct.seen.Length() <= 1 || ct.maxCost == 0 || newCost <= ct.maxCost) {
		if ct.seen.Contains(m.ZidO) {
			heap.Push(&ct.queue, ztlCtxItem{cost: newCost, meta: m})
		}
	}
}

func (ct *contextTask) addIDSet(ctx context.Context, newCost float64, value string) {
	elems := meta.ListFromValue(value)
	refCost := referenceCost(newCost, len(elems))
	for _, val := range elems {
		ct.addID(ctx, refCost, val)
	}
}

func referenceCost(baseCost float64, numReferences int) float64 {
	nRefs := float64(numReferences)
	return nRefs*math.Log2(nRefs+1) + baseCost
}

func (ct *contextTask) addTags(ctx context.Context, tags []string, baseCost float64) {
	var zidSet *id.SetO
	for _, tag := range tags {
		zs := ct.updateTagData(ctx, tag)
		zidSet = zidSet.IUnion(zs)
	}
	zidSet.ForEach(func(zid id.ZidO) {
		minCost := math.MaxFloat64
		costFactor := 1.1
		for _, tag := range tags {
			tagZids := ct.tagZids[tag]
			if tagZids.Contains(zid) {
				cost := tagCost(baseCost, tagZids.Length())
				if cost < minCost {
					minCost = cost
				}
				costFactor /= 1.1
			}
		}
		ct.addMeta(ct.metaZid[zid], minCost*costFactor)
	})
}

func (ct *contextTask) updateTagData(ctx context.Context, tag string) *id.SetO {
	if _, found := ct.tagMetas[tag]; found {
		return ct.tagZids[tag]
	}
	q := Parse(api.KeyTags + api.SearchOperatorHas + tag + " ORDER REVERSE " + api.KeyID)
	ml, err := ct.port.SelectMeta(ctx, nil, q)
	if err != nil {
		ml = nil

	if ct.hasLimit() {
		return nil, -1
	}
	for len(ct.queue) > 0 {
		item := heap.Pop(&ct.queue).(ztlCtxItem)
		m := item.meta
		zid := m.ZidO
		if ct.seen.Contains(zid) {
			continue
		}
		ct.seen.Add(zid)
		return m, item.cost
	}
	return nil, -1
}

func (ct *contextTask) hasLimit() bool {
	limit := ct.limit
	return limit > 0 && ct.seen.Length() >= limit
}

	for {
		pos := inp.Pos
		zid, found := ps.scanZid()
		if !found {
			inp.SetPos(pos)
			break
		}
		if !zidSet.Contains(zid) {
			zidSet.Add(zid)
			q = createIfNeeded(q)
			q.zids = append(q.zids, zid)
		}
		ps.skipSpace()
		if ps.mustStop() {
			q.zids = nil

	"zettelstore.de/z/zettel/meta"
)

// Searcher is used to select zettel identifier based on search criteria.
type Searcher interface {
	// Select all zettel that contains the given exact word.
	// The word must be normalized through Unicode NKFD, trimmed and not empty.
	SearchEqual(word string) *id.SetO

	// Select all zettel that have a word with the given prefix.
	// The prefix must be normalized through Unicode NKFD, trimmed and not empty.
	SearchPrefix(prefix string) *id.SetO

	// Select all zettel that have a word with the given suffix.
	// The suffix must be normalized through Unicode NKFD, trimmed and not empty.
	SearchSuffix(suffix string) *id.SetO

	// Select all zettel that contains the given string.
	// The string must be normalized through Unicode NKFD, trimmed and not empty.
	SearchContains(s string) *id.SetO
}

// Query specifies a mechanism for querying zettel.
type Query struct {
	// Präfixed zettel identifier.
	zids []id.ZidO

			cTerm.Match = matchAlways
		}
		result.Terms = append(result.Terms, cTerm)
	}
	return result
}

func metaList2idSet(ml []*meta.Meta) *id.SetO {
	if ml == nil {
		return nil
	}
	result := id.NewSetCapO(len(ml))
	for _, m := range ml {
		result = result.Add(m.ZidO)
	}
	return result
}

func (ct *conjTerms) retrieveAndCompileTerm(searcher Searcher, startSet *id.SetO) CompiledTerm {
	match := ct.compileMeta() // Match might add some searches
	var pred RetrievePredicate
	if searcher != nil {
		pred = ct.retrieveIndex(searcher)
		if startSet != nil {
			if pred == nil {
				pred = startSet.ContainsOrNil
			} else {
				predSet := id.NewSetCapO(startSet.Length())
				startSet.ForEach(func(zid id.ZidO) {
					if pred(zid) {
						predSet = predSet.Add(zid)
					}
				})
				pred = predSet.ContainsOrNil
			}
		}
	}
	return CompiledTerm{Match: match, Retrieve: pred}
}

	positives := retrievePositives(normCalls, plainCalls)
	if positives == nil {
		// No positive search for words, must contain only words for a negative search.
		// Otherwise len(search) == 0 (see above)
		negatives := retrieveNegatives(negCalls)
		return func(zid id.ZidO) bool { return !negatives.ContainsOrNil(zid) }
	}
	if positives.IsEmpty() {
		// Positive search didn't found anything. We can omit the negative search.
		return neverIncluded
	}
	if len(negCalls) == 0 {
		// Positive search found something, but there is no negative search.
		return positives.Contains
	}
	negatives := retrieveNegatives(negCalls)
	if negatives == nil {
		return positives.Contains
	}
	return func(zid id.ZidO) bool {
		return positives.Contains(zid) && !negatives.ContainsOrNil(zid)
	}
}

// Limit returns only s.GetLimit() elements of the given list.
func (q *Query) Limit(metaList []*meta.Meta) []*meta.Meta {
	if q == nil {
		return metaList
	}
	return limitElements(metaList, q.limit)
}

	"zettelstore.de/z/zettel/id"
)

type searchOp struct {
	s  string
	op compareOp
}
type searchFunc func(string) *id.SetO
type searchCallMap map[searchOp]searchFunc

var cmpPred = map[compareOp]func(string, string) bool{
	cmpEqual:   stringEqual,
	cmpPrefix:  strings.HasPrefix,
	cmpSuffix:  strings.HasSuffix,
	cmpMatch:   strings.Contains,

		if _, found := plainCalls[val]; found {
			return true
		}
	}
	return false
}

func retrievePositives(normCalls, plainCalls searchCallMap) *id.SetO {
	if isSuperset(normCalls, plainCalls) {
		var normResult *id.SetO
		for c, sf := range normCalls {
			normResult = normResult.IntersectOrSet(sf(c.s))
		}
		return normResult
	}

	type searchResults map[searchOp]*id.SetO
	var cache searchResults
	var plainResult *id.SetO
	for c, sf := range plainCalls {
		result := sf(c.s)
		if _, found := normCalls[c]; found {
			if cache == nil {
				cache = make(searchResults)
			}
			cache[c] = result
		}
		plainResult = plainResult.IntersectOrSet(result)
	}
	var normResult *id.SetO
	for c, sf := range normCalls {
		if cache != nil {
			if result, found := cache[c]; found {
				normResult = normResult.IntersectOrSet(result)
				continue
			}
		}
		normResult = normResult.IntersectOrSet(sf(c.s))
	}
	return normResult.IUnion(plainResult)
}

func isSuperset(normCalls, plainCalls searchCallMap) bool {
	for c := range plainCalls {
		if _, found := normCalls[c]; !found {
			return false
		}
	}
	return true
}

func retrieveNegatives(negCalls searchCallMap) *id.SetO {
	var negatives *id.SetO
	for val, sf := range negCalls {
		negatives = negatives.IUnion(sf(val.s))
	}
	return negatives
}

func getSearchFunc(searcher Searcher, op compareOp) searchFunc {
	switch op {
	case cmpEqual:

			}
		}
	}
	candidates = filterByZid(candidates, refZids)
	return uc.filterCandidates(ctx, candidates, words)
}

func filterByZid(candidates []*meta.Meta, ignoreSeq *id.SetO) []*meta.Meta {
	result := make([]*meta.Meta, 0, len(candidates))
	for _, m := range candidates {
		if !ignoreSeq.ContainsOrNil(m.ZidO) {
			result = append(result, m)
		}
	}
	return result

type getMetaFunc func(context.Context, id.ZidO) (*meta.Meta, error)

func buildSxnCodeDigraph(ctx context.Context, startZid id.ZidO, getMeta getMetaFunc) id.DigraphO {
	m, err := getMeta(ctx, startZid)
	if err != nil {
		return nil
	}
	var marked *id.SetO
	stack := []*meta.Meta{m}
	dg := id.DigraphO(nil).AddVertex(startZid)
	for pos := len(stack) - 1; pos >= 0; pos = len(stack) - 1 {
		curr := stack[pos]
		stack = stack[:pos]
		if marked.Contains(curr.ZidO) {
			continue

import (
	"maps"
	"slices"
)

// DigraphO relates zettel identifier in a directional way.
type DigraphO map[ZidO]*SetO

// AddVertex adds an edge / vertex to the digraph.
func (dg DigraphO) AddVertex(zid ZidO) DigraphO {
	if dg == nil {
		return DigraphO{zid: nil}
	}
	if _, found := dg[zid]; !found {

	}
}

// AddEdge adds a connection from `zid1` to `zid2`.
// Both vertices must be added before. Otherwise the function may panic.
func (dg DigraphO) AddEdge(fromZid, toZid ZidO) DigraphO {
	if dg == nil {
		return DigraphO{fromZid: (*SetO)(nil).Add(toZid), toZid: nil}
	}
	dg[fromZid] = dg[fromZid].Add(toZid)
	return dg
}

// AddEgdes adds all given `Edge`s to the digraph.
//

		dg = dg.AddEdge(edge.From, edge.To)
	}
	return dg
}

// Equal returns true if both digraphs have the same vertices and edges.
func (dg DigraphO) Equal(other DigraphO) bool {
	return maps.EqualFunc(dg, other, func(cg, co *SetO) bool { return cg.Equal(co) })
}

// Clone a digraph.
func (dg DigraphO) Clone() DigraphO {
	if len(dg) == 0 {
		return nil
	}

		return false
	}
	_, found := dg[zid]
	return found
}

// Vertices returns the set of all vertices.
func (dg DigraphO) Vertices() *SetO {
	if len(dg) == 0 {
		return nil
	}
	verts := NewSetCapO(len(dg))
	for vert := range dg {
		verts.Add(vert)
	}
	return verts
}

// Edges returns an unsorted slice of the edges of the digraph.
func (dg DigraphO) Edges() (es EdgeSliceO) {
	for vert, closure := range dg {
		closure.ForEach(func(next ZidO) {
			es = append(es, EdgeO{From: vert, To: next})
		})
	}
	return es
}

// Originators will return the set of all vertices that are not referenced
// a the to-part of an edge.
func (dg DigraphO) Originators() *SetO {
	if len(dg) == 0 {
		return nil
	}
	origs := dg.Vertices()
	for _, closure := range dg {
		origs.ISubstract(closure)
	}
	return origs
}

// Terminators returns the set of all vertices that does not reference
// other vertices.
func (dg DigraphO) Terminators() (terms *SetO) {
	for vert, closure := range dg {
		if closure.IsEmpty() {
			terms = terms.Add(vert)
		}
	}
	return terms
}

// TransitiveClosure calculates the sub-graph that is reachable from `zid`.
func (dg DigraphO) TransitiveClosure(zid ZidO) (tc DigraphO) {
	if len(dg) == 0 {
		return nil
	}
	var marked *SetO
	stack := SliceO{zid}
	for pos := len(stack) - 1; pos >= 0; pos = len(stack) - 1 {
		curr := stack[pos]
		stack = stack[:pos]
		if marked.Contains(curr) {
			continue
		}
		tc = tc.AddVertex(curr)
		dg[curr].ForEach(func(next ZidO) {
			tc = tc.AddVertex(next)
			tc = tc.AddEdge(curr, next)
			stack = append(stack, next)
		})
		marked = marked.Add(curr)
	}
	return tc
}

// ReachableVertices calculates the set of all vertices that are reachable
// from the given `zid`.
func (dg DigraphO) ReachableVertices(zid ZidO) (tc *SetO) {
	if len(dg) == 0 {
		return nil
	}
	stack := dg[zid].SafeSorted()
	for last := len(stack) - 1; last >= 0; last = len(stack) - 1 {
		curr := stack[last]
		stack = stack[:last]
		if tc.Contains(curr) {
			continue
		}
		closure, found := dg[curr]
		if !found {
			continue
		}
		tc = tc.Add(curr)
		closure.ForEach(func(next ZidO) {
			stack = append(stack, next)
		})
	}
	return tc
}

// IsDAG returns a vertex and false, if the graph has a cycle containing the vertex.
func (dg DigraphO) IsDAG() (ZidO, bool) {
	for vertex := range dg {
		if dg.ReachableVertices(vertex).Contains(vertex) {
			return vertex, false
		}
	}
	return InvalidO, true
}

// Reverse returns a graph with reversed edges.
func (dg DigraphO) Reverse() (revDg DigraphO) {
	for vertex, closure := range dg {
		revDg = revDg.AddVertex(vertex)
		closure.ForEach(func(next ZidO) {
			revDg = revDg.AddVertex(next)
			revDg = revDg.AddEdge(next, vertex)
		})
	}
	return revDg
}

// SortReverse returns a deterministic, topological, reverse sort of the
// digraph.
//
// Works only if digraph is a DAG. Otherwise the algorithm will not terminate
// or returns an arbitrary value.
func (dg DigraphO) SortReverse() (sl SliceO) {
	if len(dg) == 0 {
		return nil
	}
	tempDg := dg.Clone()
	for len(tempDg) > 0 {
		terms := tempDg.Terminators()
		if terms.IsEmpty() {
			break
		}
		termSlice := terms.SafeSorted()
		slices.Reverse(termSlice)
		sl = append(sl, termSlice...)
		terms.ForEach(func(t ZidO) {
			tempDg.RemoveVertex(t)
		})
	}
	return sl
}

}

func TestDigraphOriginatorsO(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		name string
		dg   id.EdgeSliceO
		orig *id.SetO
		term *id.SetO
	}{
		{"empty", nil, nil, nil},
		{"single", zps{{0, 1}}, id.NewSetO(0), id.NewSetO(1)},
		{"chain", zps{{0, 1}, {1, 2}, {2, 3}}, id.NewSetO(0), id.NewSetO(3)},
	}
	for _, tc := range testcases {
		t.Run(tc.name, func(t *testing.T) {

func TestDigraphReachableVerticesO(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		name  string
		pairs id.EdgeSliceO
		start id.ZidO
		exp   *id.SetO
	}{
		{"nil", nil, 0, nil},
		{"0-2", zps{{1, 2}, {2, 3}}, 1, id.NewSetO(2, 3)},
		{"1,2", zps{{1, 2}, {2, 3}}, 2, id.NewSetO(3)},
		{"0-2,1-2", zps{{1, 2}, {2, 3}, {1, 3}}, 1, id.NewSetO(2, 3)},
		{"0-2,1-2/1", zps{{1, 2}, {2, 3}, {1, 3}}, 2, id.NewSetO(3)},
		{"0-2,1-2/2", zps{{1, 2}, {2, 3}, {1, 3}}, 3, nil},

// SPDX-License-Identifier: EUPL-1.2
// SPDX-FileCopyrightText: 2021-present Detlef Stern
//-----------------------------------------------------------------------------

package id

import (
	"slices"
	"strings"
)

// SetO is a set of zettel identifier
type SetO struct {
	seq []ZidO
}

// String returns a string representation of the set.
func (s *SetO) String() string {
	return "{" + s.MetaString() + "}"
}

// MetaString returns a string representation of the set to be stored as metadata.
func (s *SetO) MetaString() string {
	if s == nil || len(s.seq) == 0 {
		return ""
	}
	var sb strings.Builder

	for i, zid := range s.seq {
		if i > 0 {
			sb.WriteByte(' ')
		}
		sb.Write(zid.Bytes())
	}

	return sb.String()
}

// NewSetO returns a new set of identifier with the given initial values.
func NewSetO(zids ...ZidO) *SetO {
	switch l := len(zids); l {
	case 0:
		return &SetO{seq: nil}
	case 1:

		return &SetO{seq: []ZidO{zids[0]}}
	default:
		result := SetO{seq: make([]ZidO, 0, l)}
		result.AddSlice(zids)
		return &result
	}
}

// NewSetCapO returns a new set of identifier with the given capacity and initial values.
func NewSetCapO(c int, zids ...ZidO) *SetO {
	result := SetO{seq: make(SliceO, 0, max(c, len(zids)))}
	result.AddSlice(zids)

	return &result
}

// IsEmpty returns true, if the set conains no element.
func (s *SetO) IsEmpty() bool {
	return s == nil || len(s.seq) == 0
}

// Length returns the number of elements in this set.
func (s *SetO) Length() int {
	if s == nil {
		return 0
	}
	return len(s.seq)
}

// Clone returns a copy of the given set.
func (s *SetO) Clone() *SetO {
	if s == nil || len(s.seq) == 0 {
		return nil
	}
	return &SetO{seq: slices.Clone(s.seq)}
}

// Add adds a zid to the set.
func (s *SetO) Add(zid ZidO) *SetO {
	if s == nil {
		return NewSetO(zid)
	}
	s.add(zid)
	return s
}

// Contains return true if the set is non-nil and the set contains the given Zettel identifier.
func (s *SetO) Contains(zid ZidO) bool { return s != nil && s.contains(zid) }







// ContainsOrNil return true if the set is nil or if the set contains the given Zettel identifier.
func (s *SetO) ContainsOrNil(zid ZidO) bool { return s == nil || s.contains(zid) }



















// AddSlice adds all identifier of the given slice to the set.
func (s *SetO) AddSlice(sl SliceO) *SetO {
	if s == nil {
		return NewSetO(sl...)
	}
	s.seq = slices.Grow(s.seq, len(sl))
	for _, zid := range sl {
		s.add(zid)
	}
	return s
}

// SafeSorted returns the set as a new sorted slice of zettel identifier.
func (s *SetO) SafeSorted() SliceO {


	if s == nil {



		return nil
	}
	return slices.Clone(s.seq)
}

// IntersectOrSet removes all zettel identifier that are not in the other set.
// Both sets can be modified by this method. One of them is the set returned.
// It contains the intersection of both, if s is not nil.
//
// If s == nil, then the other set is always returned.
func (s *SetO) IntersectOrSet(other *SetO) *SetO {
	if s == nil || other == nil {
		return other
	}
	topos, spos, opos := 0, 0, 0
	for spos < len(s.seq) && opos < len(other.seq) {
		sz, oz := s.seq[spos], other.seq[opos]
		if sz < oz {
			spos++
			continue
		}
		if sz > oz {
			opos++
			continue
		}
		s.seq[topos] = sz
		topos++
		spos++
		opos++
	}
	s.seq = s.seq[:topos]
	return s
}

// IUnion adds the elements of set other to s.
func (s *SetO) IUnion(other *SetO) *SetO {
	if other == nil || len(other.seq) == 0 {
		return s
	}
	// TODO: if other is large enough (and s is not too small) -> optimize by swapping and/or loop through both
	return s.AddSlice(other.seq)
}

// ISubstract removes all zettel identifier from 's' that are in the set 'other'.
func (s *SetO) ISubstract(other *SetO) {
	if s == nil || len(s.seq) == 0 || other == nil || len(other.seq) == 0 {
		return
	}
	topos, spos, opos := 0, 0, 0
	for spos < len(s.seq) && opos < len(other.seq) {
		sz, oz := s.seq[spos], other.seq[opos]
		if sz < oz {
			s.seq[topos] = sz
			topos++
			spos++
			continue
		}
		if sz == oz {
			spos++
		}
		opos++
	}
	for spos < len(s.seq) {
		s.seq[topos] = s.seq[spos]
		topos++
		spos++
	}
	s.seq = s.seq[:topos]
}

// Diff returns the difference sets between the two sets: the first difference
// set is the set of elements that are in other, but not in s; the second
// difference set is the set of element that are in s but not in other.
//
// in other words: the first result is the set of elements from other that must
// be added to s; the second result is the set of elements that must be removed
// from s, so that s would have the same elemest as other.
func (s *SetO) Diff(other *SetO) (newS, remS *SetO) {
	if s == nil || len(s.seq) == 0 {
		return other.Clone(), nil
	}
	if other == nil || len(other.seq) == 0 {
		return nil, s.Clone()
	}
	seqS, seqO := s.seq, other.seq
	var newRefs, remRefs SliceO
	npos, opos := 0, 0
	for npos < len(seqO) && opos < len(seqS) {
		rn, ro := seqO[npos], seqS[opos]
		if rn == ro {
			npos++
			opos++
			continue
		}
		if rn < ro {
			newRefs = append(newRefs, rn)
			npos++
			continue
		}
		remRefs = append(remRefs, ro)
		opos++
	}
	if npos < len(seqO) {
		newRefs = append(newRefs, seqO[npos:]...)
	}
	if opos < len(seqS) {
		remRefs = append(remRefs, seqS[opos:]...)
	}
	return newFromSlice(newRefs), newFromSlice(remRefs)
}

// Remove the identifier from the set.
func (s *SetO) Remove(zid ZidO) *SetO {
	if s == nil || len(s.seq) == 0 {
		return nil
	}
	if pos, found := s.find(zid); found {
		copy(s.seq[pos:], s.seq[pos+1:])
		s.seq = s.seq[:len(s.seq)-1]
	}
	if len(s.seq) == 0 {
		return nil
	}
	return s
}

// Equal returns true if the other set is equal to the given set.
func (s *SetO) Equal(other *SetO) bool {
	if s == nil {
		return other == nil
	}
	if other == nil {
		return false
	}
	return slices.Equal(s.seq, other.seq)
}

// ForEach calls the given function for each element of the set.
//
// Every element is bigger than the previous one.
func (s *SetO) ForEach(fn func(zid ZidO)) {
	if s != nil {
		for _, zid := range s.seq {
			fn(zid)
		}
	}
}

// Pop return one arbitrary element of the set.
func (s *SetO) Pop() (ZidO, bool) {
	if s != nil {
		if l := len(s.seq); l > 0 {
			zid := s.seq[l-1]
			s.seq = s.seq[:l-1]
			return zid, true
		}
	}
	return InvalidO, false
}

// Optimize the amount of memory to store the set.
func (s *SetO) Optimize() {
	if s != nil {
		s.seq = slices.Clip(s.seq)
	}
}

// ----- unchecked base operations

func newFromSlice(seq SliceO) *SetO {
	if l := len(seq); l == 0 {
		return nil
	} else {
		return &SetO{seq: seq}
	}
}

func (s *SetO) add(zid ZidO) {
	if pos, found := s.find(zid); !found {
		s.seq = slices.Insert(s.seq, pos, zid)
	}
}

func (s *SetO) contains(zid ZidO) bool {
	_, found := s.find(zid)
	return found
}

func (s *SetO) find(zid ZidO) (int, bool) {
	hi := len(s.seq)
	for lo := 0; lo < hi; {
		m := lo + (hi-lo)/2
		if z := s.seq[m]; z == zid {
			return m, true
		} else if z < zid {
			lo = m + 1
		} else {
			hi = m
		}
	}
	return hi, false
}

import (
	"testing"

	"zettelstore.de/z/zettel/id"
)

func TestSetOContainsOrNil(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		s   *id.SetO
		zid id.ZidO
		exp bool
	}{
		{nil, id.InvalidO, true},
		{nil, 14, true},
		{id.NewSetO(), id.InvalidO, false},
		{id.NewSetO(), 1, false},
		{id.NewSetO(), id.InvalidO, false},
		{id.NewSetO(1), 1, true},
	}
	for i, tc := range testcases {
		got := tc.s.ContainsOrNil(tc.zid)
		if got != tc.exp {
			t.Errorf("%d: %v.ContainsOrNil(%v) == %v, but got %v", i, tc.s, tc.zid, tc.exp, got)
		}
	}
}

func TestSetOAdd(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		s1, s2 *id.SetO
		exp    id.SliceO
	}{
		{nil, nil, nil},
		{id.NewSetO(), nil, nil},
		{id.NewSetO(), id.NewSetO(), nil},
		{nil, id.NewSetO(1), id.SliceO{1}},
		{id.NewSetO(1), nil, id.SliceO{1}},
		{id.NewSetO(1), id.NewSetO(), id.SliceO{1}},
		{id.NewSetO(1), id.NewSetO(2), id.SliceO{1, 2}},
		{id.NewSetO(1), id.NewSetO(1), id.SliceO{1}},
	}
	for i, tc := range testcases {
		sl1 := tc.s1.SafeSorted()
		sl2 := tc.s2.SafeSorted()
		got := tc.s1.IUnion(tc.s2).SafeSorted()
		if !got.Equal(tc.exp) {
			t.Errorf("%d: %v.Add(%v) should be %v, but got %v", i, sl1, sl2, tc.exp, got)
		}
	}
}

func TestSetOSafeSorted(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		set *id.SetO
		exp id.SliceO
	}{
		{nil, nil},
		{id.NewSetO(), nil},
		{id.NewSetO(9, 4, 6, 1, 7), id.SliceO{1, 4, 6, 7, 9}},
	}
	for i, tc := range testcases {
		got := tc.set.SafeSorted()
		if !got.Equal(tc.exp) {
			t.Errorf("%d: %v.SafeSorted() should be %v, but got %v", i, tc.set, tc.exp, got)
		}
	}
}

func TestSetOIntersectOrSet(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		s1, s2 *id.SetO
		exp    id.SliceO
	}{
		{nil, nil, nil},
		{id.NewSetO(), nil, nil},
		{nil, id.NewSetO(), nil},
		{id.NewSetO(), id.NewSetO(), nil},
		{id.NewSetO(1), nil, nil},
		{nil, id.NewSetO(1), id.SliceO{1}},
		{id.NewSetO(1), id.NewSetO(), nil},
		{id.NewSetO(), id.NewSetO(1), nil},
		{id.NewSetO(1), id.NewSetO(2), nil},
		{id.NewSetO(2), id.NewSetO(1), nil},
		{id.NewSetO(1), id.NewSetO(1), id.SliceO{1}},
	}
	for i, tc := range testcases {
		sl1 := tc.s1.SafeSorted()
		sl2 := tc.s2.SafeSorted()
		got := tc.s1.IntersectOrSet(tc.s2).SafeSorted()
		if !got.Equal(tc.exp) {
			t.Errorf("%d: %v.IntersectOrSet(%v) should be %v, but got %v", i, sl1, sl2, tc.exp, got)
		}
	}
}

func TestSetOIUnion(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		s1, s2 *id.SetO
		exp    *id.SetO
	}{
		{nil, nil, nil},
		{id.NewSetO(), nil, nil},
		{nil, id.NewSetO(), nil},
		{id.NewSetO(), id.NewSetO(), nil},
		{id.NewSetO(1), nil, id.NewSetO(1)},
		{nil, id.NewSetO(1), id.NewSetO(1)},
		{id.NewSetO(1), id.NewSetO(), id.NewSetO(1)},
		{id.NewSetO(), id.NewSetO(1), id.NewSetO(1)},
		{id.NewSetO(1), id.NewSetO(2), id.NewSetO(1, 2)},
		{id.NewSetO(2), id.NewSetO(1), id.NewSetO(2, 1)},
		{id.NewSetO(1), id.NewSetO(1), id.NewSetO(1)},
		{id.NewSetO(1, 2, 3), id.NewSetO(2, 3, 4), id.NewSetO(1, 2, 3, 4)},
	}
	for i, tc := range testcases {
		s1 := tc.s1.Clone()
		sl1 := s1.SafeSorted()
		sl2 := tc.s2.SafeSorted()
		got := s1.IUnion(tc.s2)
		if !got.Equal(tc.exp) {
			t.Errorf("%d: %v.IUnion(%v) should be %v, but got %v", i, sl1, sl2, tc.exp, got)
		}
	}
}

func TestSetOISubtract(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		s1, s2 *id.SetO
		exp    id.SliceO
	}{
		{nil, nil, nil},
		{id.NewSetO(), nil, nil},
		{nil, id.NewSetO(), nil},
		{id.NewSetO(), id.NewSetO(), nil},
		{id.NewSetO(1), nil, id.SliceO{1}},
		{nil, id.NewSetO(1), nil},
		{id.NewSetO(1), id.NewSetO(), id.SliceO{1}},
		{id.NewSetO(), id.NewSetO(1), nil},
		{id.NewSetO(1), id.NewSetO(2), id.SliceO{1}},
		{id.NewSetO(2), id.NewSetO(1), id.SliceO{2}},
		{id.NewSetO(1), id.NewSetO(1), nil},
		{id.NewSetO(1, 2, 3), id.NewSetO(1), id.SliceO{2, 3}},
		{id.NewSetO(1, 2, 3), id.NewSetO(2), id.SliceO{1, 3}},
		{id.NewSetO(1, 2, 3), id.NewSetO(3), id.SliceO{1, 2}},
		{id.NewSetO(1, 2, 3), id.NewSetO(1, 2), id.SliceO{3}},
		{id.NewSetO(1, 2, 3), id.NewSetO(1, 3), id.SliceO{2}},
		{id.NewSetO(1, 2, 3), id.NewSetO(2, 3), id.SliceO{1}},
	}
	for i, tc := range testcases {
		s1 := tc.s1.Clone()
		sl1 := s1.SafeSorted()
		sl2 := tc.s2.SafeSorted()
		s1.ISubstract(tc.s2)
		got := s1.SafeSorted()
		if !got.Equal(tc.exp) {
			t.Errorf("%d: %v.ISubstract(%v) should be %v, but got %v", i, sl1, sl2, tc.exp, got)
		}
	}
}

func TestSetODiff(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		in1, in2   *id.SetO
		exp1, exp2 *id.SetO
	}{
		{nil, nil, nil, nil},
		{id.NewSetO(1), nil, nil, id.NewSetO(1)},
		{nil, id.NewSetO(1), id.NewSetO(1), nil},
		{id.NewSetO(1), id.NewSetO(1), nil, nil},
		{id.NewSetO(1, 2), id.NewSetO(1), nil, id.NewSetO(2)},
		{id.NewSetO(1), id.NewSetO(1, 2), id.NewSetO(2), nil},
		{id.NewSetO(1, 2), id.NewSetO(1, 3), id.NewSetO(3), id.NewSetO(2)},
		{id.NewSetO(1, 2, 3), id.NewSetO(2, 3, 4), id.NewSetO(4), id.NewSetO(1)},
		{id.NewSetO(2, 3, 4), id.NewSetO(1, 2, 3), id.NewSetO(1), id.NewSetO(4)},
	}
	for i, tc := range testcases {
		gotN, gotO := tc.in1.Diff(tc.in2)
		if !tc.exp1.Equal(gotN) {
			t.Errorf("%d: expected %v, but got: %v", i, tc.exp1, gotN)
		}
		if !tc.exp2.Equal(gotO) {
			t.Errorf("%d: expected %v, but got: %v", i, tc.exp2, gotO)
		}
	}
}

func TestSetORemove(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		s1, s2 *id.SetO
		exp    id.SliceO
	}{
		{nil, nil, nil},
		{id.NewSetO(), nil, nil},
		{id.NewSetO(), id.NewSetO(), nil},
		{id.NewSetO(1), nil, id.SliceO{1}},
		{id.NewSetO(1), id.NewSetO(), id.SliceO{1}},
		{id.NewSetO(1), id.NewSetO(2), id.SliceO{1}},
		{id.NewSetO(1), id.NewSetO(1), id.SliceO{}},
	}
	for i, tc := range testcases {
		sl1 := tc.s1.SafeSorted()
		sl2 := tc.s2.SafeSorted()
		newS1 := id.NewSetO(sl1...)
		newS1.ISubstract(tc.s2)
		got := newS1.SafeSorted()
		if !got.Equal(tc.exp) {
			t.Errorf("%d: %v.Remove(%v) should be %v, but got %v", i, sl1, sl2, tc.exp, got)
		}
	}
}







func BenchmarkSetO(b *testing.B) {
	s := id.NewSetCapO(b.N)
	for i := range b.N {
		s.Add(id.ZidO(i))
	}
}

// Clone a zettel identifier slice
func (zs SliceO) Clone() SliceO { return slices.Clone(zs) }

// Equal reports whether zs and other are the same length and contain the samle zettel
// identifier. A nil argument is equivalent to an empty slice.
func (zs SliceO) Equal(other SliceO) bool { return slices.Equal(zs, other) }

// MetaString returns the slice as a string to be store in metadata.
func (zs SliceO) MetaString() string {
	if len(zs) == 0 {
		return ""
	}
	var sb strings.Builder
	for i, zid := range zs {
		if i > 0 {
			sb.WriteByte(' ')

import (
	"testing"

	"zettelstore.de/z/zettel/id"
)

func TestSliceOSort(t *testing.T) {
	t.Parallel()
	zs := id.SliceO{9, 4, 6, 1, 7}
	zs.Sort()
	exp := id.SliceO{1, 4, 6, 7, 9}
	if !zs.Equal(exp) {
		t.Errorf("Slice.Sort did not work. Expected %v, got %v", exp, zs)
	}
}

func TestSliceOCopy(t *testing.T) {
	t.Parallel()
	var orig id.SliceO
	got := orig.Clone()
	if got != nil {
		t.Errorf("Nil copy resulted in %v", got)
	}
	orig = id.SliceO{9, 4, 6, 1, 7}
	got = orig.Clone()
	if !orig.Equal(got) {
		t.Errorf("Slice.Copy did not work. Expected %v, got %v", orig, got)
	}
}

func TestSliceOEqual(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		s1, s2 id.SliceO
		exp    bool
	}{
		{nil, nil, true},
		{nil, id.SliceO{}, true},

		got = tc.s2.Equal(tc.s1)
		if got != tc.exp {
			t.Errorf("%d/%v.Equal(%v)==%v, but got %v", i, tc.s2, tc.s1, tc.exp, got)
		}
	}
}

func TestSlice0MetaString(t *testing.T) {
	t.Parallel()
	testcases := []struct {
		in  id.SliceO
		exp string
	}{
		{nil, ""},
		{id.SliceO{}, ""},
		{id.SliceO{1}, "00000000000001"},
		{id.SliceO{1, 2}, "00000000000001 00000000000002"},
	}
	for i, tc := range testcases {
		got := tc.in.MetaString()
		if got != tc.exp {
			t.Errorf("%d/%v: expected %q, but got %q", i, tc.in, tc.exp, got)
		}
	}
}