func (l *PackageList) PrepareIndex() {
	if l.indexed {
		return
	}
	l.packagesIndex = make([]*Package, l.Len())
	l.providesIndex = make(map[string][]*Package, 128)
	i := 0
	for _, p := range l.packages {
		l.packagesIndex[i] = p
		i++
		for _, provides := range p.Provides {
			l.providesIndex[provides] = append(l.providesIndex[provides], p)
		}
	}
	sort.Sort(l)
	l.indexed = true
}
PrepareIndex prepares list for indexing
package deb
import (
	"fmt"
	"sort"
	"strings"
	"github.com/aptly-dev/aptly/aptly"
	"github.com/aptly-dev/aptly/utils"
)
const (
	DepFollowSource = 1 << iota
	DepFollowSuggests
	DepFollowRecommends
	DepFollowAllVariants
	DepFollowBuild
	DepVerboseResolve
)
type PackageList struct {
	packages map[string]*Package
	packagesIndex []*Package
	providesIndex map[string][]*Package
	keyFunc func(p *Package) string
	duplicatesAllowed bool
	indexed bool
}
type PackageConflictError struct {
	error
}
var (
	_ sort.Interface = &PackageList{}
	_ PackageCatalog = &PackageList{}
)
func packageShortKey(p *Package) string {
	return string(p.ShortKey(""))
}
func packageFullKey(p *Package) string {
	return string(p.Key(""))
}
func NewPackageList() *PackageList {
	return NewPackageListWithDuplicates(false, 1000)
}
func NewPackageListWithDuplicates(duplicates bool, capacity int) *PackageList {
	if capacity == 0 {
		capacity = 1000
	}
	result := &PackageList{
		packages:          make(map[string]*Package, capacity),
		duplicatesAllowed: duplicates,
		keyFunc:           packageShortKey,
	}
	if duplicates {
		result.keyFunc = packageFullKey
	}
	return result
}
func NewPackageListFromRefList(reflist *PackageRefList, collection *PackageCollection, progress aptly.Progress) (*PackageList, error) {
	if reflist == nil {
		return NewPackageList(), nil
	}
	result := NewPackageListWithDuplicates(false, reflist.Len())
	if progress != nil {
		progress.InitBar(int64(reflist.Len()), false)
	}
	err := reflist.ForEach(func(key []byte) error {
		p, err2 := collection.ByKey(key)
		if err2 != nil {
			return fmt.Errorf("unable to load package with key %s: %s", key, err2)
		}
		if progress != nil {
			progress.AddBar(1)
		}
		return result.Add(p)
	})
	if progress != nil {
		progress.ShutdownBar()
	}
	if err != nil {
		return nil, err
	}
	return result, nil
}
func (l *PackageList) Has(p *Package) bool {
	key := l.keyFunc(p)
	_, ok := l.packages[key]
	return ok
}
func (l *PackageList) Add(p *Package) error {
	key := l.keyFunc(p)
	existing, ok := l.packages[key]
	if ok {
		if !existing.Equals(p) {
			return &PackageConflictError{fmt.Errorf("conflict in package %s", p)}
		}
		return nil
	}
	l.packages[key] = p
	if l.indexed {
		for _, provides := range p.Provides {
			l.providesIndex[provides] = append(l.providesIndex[provides], p)
		}
		i := sort.Search(len(l.packagesIndex), func(j int) bool { return l.lessPackages(p, l.packagesIndex[j]) })
		l.packagesIndex = append(l.packagesIndex, nil)
		copy(l.packagesIndex[i+1:], l.packagesIndex[i:])
		l.packagesIndex[i] = p
	}
	return nil
}
func (l *PackageList) ForEach(handler func(*Package) error) error {
	var err error
	for _, p := range l.packages {
		err = handler(p)
		if err != nil {
			return err
		}
	}
	return err
}
func (l *PackageList) ForEachIndexed(handler func(*Package) error) error {
	if !l.indexed {
		panic("list not indexed, can't iterate")
	}
	var err error
	for _, p := range l.packagesIndex {
		err = handler(p)
		if err != nil {
			return err
		}
	}
	return err
}
func (l *PackageList) Len() int {
	return len(l.packages)
}
func (l *PackageList) Append(pl *PackageList) error {
	if l.indexed {
		panic("Append not supported when indexed")
	}
	for k, p := range pl.packages {
		existing, ok := l.packages[k]
		if ok {
			if !existing.Equals(p) {
				return fmt.Errorf("conflict in package %s", p)
			}
		} else {
			l.packages[k] = p
		}
	}
	return nil
}
func (l *PackageList) Remove(p *Package) {
	delete(l.packages, l.keyFunc(p))
	if l.indexed {
		for _, provides := range p.Provides {
			for i, pkg := range l.providesIndex[provides] {
				if pkg.Equals(p) {
					l.providesIndex[provides][len(l.providesIndex[provides])-1], l.providesIndex[provides][i], l.providesIndex[provides] =
						nil, l.providesIndex[provides][len(l.providesIndex[provides])-1], l.providesIndex[provides][:len(l.providesIndex[provides])-1]
					break
				}
			}
		}
		i := sort.Search(len(l.packagesIndex), func(j int) bool { return l.packagesIndex[j].Name >= p.Name })
		for i < len(l.packagesIndex) && l.packagesIndex[i].Name == p.Name {
			if l.packagesIndex[i].Equals(p) {
				copy(l.packagesIndex[i:], l.packagesIndex[i+1:])
				l.packagesIndex[len(l.packagesIndex)-1] = nil
				l.packagesIndex = l.packagesIndex[:len(l.packagesIndex)-1]
				break
			}
			i++
		}
	}
}
func (l *PackageList) Architectures(includeSource bool) (result []string) {
	result = make([]string, 0, 10)
	for _, pkg := range l.packages {
		if pkg.Architecture != ArchitectureAll && (pkg.Architecture != ArchitectureSource || includeSource) && !utils.StrSliceHasItem(result, pkg.Architecture) {
			result = append(result, pkg.Architecture)
		}
	}
	return
}
func (l *PackageList) Strings() []string {
	result := make([]string, l.Len())
	i := 0
	for _, p := range l.packages {
		result[i] = string(p.Key(""))
		i++
	}
	return result
}
func (l *PackageList) FullNames() []string {
	result := make([]string, l.Len())
	i := 0
	for _, p := range l.packages {
		result[i] = p.GetFullName()
		i++
	}
	return result
}
func depSliceDeduplicate(s []Dependency) []Dependency {
	l := len(s)
	if l < 2 {
		return s
	}
	if l == 2 {
		if s[0] == s[1] {
			return s[0:1]
		}
		return s
	}
	found := make(map[string]bool, l)
	j := 0
	for i, x := range s {
		h := x.Hash()
		if !found[h] {
			found[h] = true
			s[j] = s[i]
			j++
		}
	}
	return s[:j]
}
func (l *PackageList) VerifyDependencies(options int, architectures []string, sources *PackageList, progress aptly.Progress) ([]Dependency, error) {
	l.PrepareIndex()
	missing := make([]Dependency, 0, 128)
	if progress != nil {
		progress.InitBar(int64(l.Len())*int64(len(architectures)), false)
	}
	for _, arch := range architectures {
		cache := make(map[string]bool, 2048)
		for _, p := range l.packagesIndex {
			if progress != nil {
				progress.AddBar(1)
			}
			if !p.MatchesArchitecture(arch) {
				continue
			}
			for _, dep := range p.GetDependencies(options) {
				variants, err := ParseDependencyVariants(dep)
				if err != nil {
					return nil, fmt.Errorf("unable to process package %s: %s", p, err)
				}
				variants = depSliceDeduplicate(variants)
				variantsMissing := make([]Dependency, 0, len(variants))
				for _, dep := range variants {
					if dep.Architecture == "" {
						dep.Architecture = arch
					}
					hash := dep.Hash()
					satisfied, ok := cache[hash]
					if !ok {
						satisfied = sources.Search(dep, false) != nil
						cache[hash] = satisfied
					}
					if !satisfied && !ok {
						variantsMissing = append(variantsMissing, dep)
					}
					if satisfied && options&DepFollowAllVariants == 0 {
						variantsMissing = nil
						break
					}
				}
				missing = append(missing, variantsMissing...)
			}
		}
	}
	if progress != nil {
		progress.ShutdownBar()
	}
	if options&DepVerboseResolve == DepVerboseResolve && progress != nil {
		missingStr := make([]string, len(missing))
		for i := range missing {
			missingStr[i] = missing[i].String()
		}
		progress.ColoredPrintf("@{y}Missing dependencies:@| %s", strings.Join(missingStr, ", "))
	}
	return missing, nil
}
func (l *PackageList) Swap(i, j int) {
	l.packagesIndex[i], l.packagesIndex[j] = l.packagesIndex[j], l.packagesIndex[i]
}
func (l *PackageList) lessPackages(iPkg, jPkg *Package) bool {
	if iPkg.Name == jPkg.Name {
		cmp := CompareVersions(iPkg.Version, jPkg.Version)
		if cmp == 0 {
			return iPkg.Architecture < jPkg.Architecture
		}
		return cmp == 1
	}
	return iPkg.Name < jPkg.Name
}
func (l *PackageList) Less(i, j int) bool {
	return l.lessPackages(l.packagesIndex[i], l.packagesIndex[j])
}