path: root/src/tre.go

package tre

import (
	"encoding/binary"
	"fmt"
	"strings"
	"sort"
)



type CharBlock struct {
	From []byte
	To   []byte
}

type cpRange struct {
	from rune
	to   rune
}



func (b *CharBlock) String() string {
	var s strings.Builder
	fmt.Fprint(&s, "<")
	fmt.Fprintf(&s, "%X", b.From[0])
	for i := 1; i < len(b.From); i++ {
		fmt.Fprintf(&s, " %X", b.From[i])
	}
	fmt.Fprint(&s, "..")
	fmt.Fprintf(&s, "%X", b.To[0])
	for i := 1; i < len(b.To); i++ {
		fmt.Fprintf(&s, " %X", b.To[i])
	}
	fmt.Fprint(&s, ">")
	return s.String()
}

func GenCharBlocks(from, to rune) ([]*CharBlock, error) {
	rs, err := splitCodePoint(from, to)
	if err != nil {
		return nil, err
	}

	blks := make([]*CharBlock, len(rs))
	for i, r := range rs {
		blks[i] = &CharBlock{
			From: []byte(string(r.from)),
			To:   []byte(string(r.to)),
		}
	}

	return blks, nil
}

/// `splitCodePoint` splits a code point range represented by <from..to> into
/// some blocks.  The code points that the block contains will be a continuous
/// byte sequence when encoded into UTF-8.  For instance, this function splits
/// <U+0000..U+07FF> into <U+0000..U+007F> and <U+0080..U+07FF> because
/// <U+0000..U+07FF> is continuous on the code point but non-continuous in the
/// UTF-8 byte sequence (In UTF-8, <U+0000..U+007F> is encoded <00..7F>, and
/// <U+0080..U+07FF> is encoded <C2 80..DF BF>).
///
/// The blocks don't contain surrogate code points <U+D800..U+DFFF> because byte
/// sequences encoding them are ill-formed in UTF-8.  For instance,
/// <U+D000..U+FFFF> is split into <U+D000..U+D7FF> and <U+E000..U+FFFF>.
/// However, when `from` or `to` itself is the surrogate code point, this
/// function returns an error.
func splitCodePoint(from, to rune) ([]*cpRange, error) {
	if from > to {
		return nil, fmt.Errorf(
			"code point range must be from <= to: U+%X..U+%X",
			from,
			to,
		)
	}
	if from < 0x0000 || from > 0x10ffff || to < 0x0000 || to > 0x10ffff {
		return nil, fmt.Errorf(
			"code point must be >=U+0000 and <=U+10FFFF:" +
				"U+%X..U+%X",
			from,
			to,
		)
	}
	// https://www.unicode.org/versions/Unicode13.0.0/ch03.pdf
	//  > 3.9 Unicode Encoding Forms
	//   > UTF-8 D92
	//    > Because surrogate code points are not Unicode scalar values,
	//    > any UTF-8 byte sequence that would otherwise
	//    > map to code points U+D800..U+DFFF is ill-formed.
	if from >= 0xd800 && from <= 0xdfff || to >= 0xd800 && to <= 0xdfff {
		return nil, fmt.Errorf(
			"surrogate code points U+D800..U+DFFF " +
				"are not allowed in UTF-8: U+%X..U+%X",
			from,
			to,
		)
	}

	in := &cpRange{
		from: from,
		to:   to,
	}
	var rs []*cpRange
	for in.from <= in.to {
		r := &cpRange{
			from: in.from,
			to:   in.to,
		}
		// https://www.unicode.org/versions/Unicode13.0.0/ch03.pdf
		//  > 3.9 Unicode Encoding Forms
		//   > UTF-8 Table 3-7.
		//    > Well-Formed UTF-8 Byte Sequences
		switch {
		case in.from <= 0x007f && in.to > 0x007f:
			r.to = 0x007f
		case in.from <= 0x07ff && in.to > 0x07ff:
			r.to = 0x07ff
		case in.from <= 0x0fff && in.to > 0x0fff:
			r.to = 0x0fff
		case in.from <= 0xcfff && in.to > 0xcfff:
			r.to = 0xcfff
		case in.from <= 0xd7ff && in.to > 0xd7ff:
			r.to = 0xd7ff
		case in.from <= 0xffff && in.to > 0xffff:
			r.to = 0xffff
		case in.from <= 0x3ffff && in.to > 0x3ffff:
			r.to = 0x3ffff
		case in.from <= 0xfffff && in.to > 0xfffff:
			r.to = 0xfffff
		}
		rs = append(rs, r)
		in.from = r.to + 1

		// Skip surrogate code points U+D800..U+DFFF.
		if in.from >= 0xd800 && in.from <= 0xdfff {
			in.from = 0xe000
		}
	}
	return rs, nil
}



type OriginalTable struct {
	entries  []int
	rowCount int
	colCount int
}

func NewOriginalTable(entries []int, colCount int) (*OriginalTable, error) {
	if len(entries) == 0 {
		return nil, fmt.Errorf("enries is empty")
	}
	if colCount <= 0 {
		return nil, fmt.Errorf("colCount must be >=1")
	}
	if len(entries)%colCount != 0 {
		return nil, fmt.Errorf("entries length or column count are incorrect; entries length: %v, column count: %v", len(entries), colCount)
	}

	return &OriginalTable{
		entries:  entries,
		rowCount: len(entries) / colCount,
		colCount: colCount,
	}, nil
}

type Compressor interface {
	Compress(orig *OriginalTable) error
	Lookup(row, col int) (int, error)
	OriginalTableSize() (int, int)
}

var (
	_ Compressor = &UniqueEntriesTable{}
	_ Compressor = &RowDisplacementTable{}
)

type UniqueEntriesTable struct {
	UniqueEntries    []int
	RowNums          []int
	OriginalRowCount int
	OriginalColCount int
}

func NewUniqueEntriesTable() *UniqueEntriesTable {
	return &UniqueEntriesTable{}
}

func (tab *UniqueEntriesTable) Lookup(row, col int) (int, error) {
	if row < 0 || row >= tab.OriginalRowCount || col < 0 || col >= tab.OriginalColCount {
		return 0, fmt.Errorf("indexes are out of range: [%v, %v]", row, col)
	}
	return tab.UniqueEntries[tab.RowNums[row]*tab.OriginalColCount+col], nil
}

func (tab *UniqueEntriesTable) OriginalTableSize() (int, int) {
	return tab.OriginalRowCount, tab.OriginalColCount
}

func (tab *UniqueEntriesTable) Compress(orig *OriginalTable) error {
	var uniqueEntries []int
	rowNums := make([]int, orig.rowCount)
	hash2RowNum := map[string]int{}
	nextRowNum := 0
	for row := 0; row < orig.rowCount; row++ {
		var rowHash string
		{
			buf := make([]byte, 0, orig.colCount*8)
			for col := 0; col < orig.colCount; col++ {
				b := make([]byte, 8)
				binary.PutUvarint(b, uint64(orig.entries[row*orig.colCount+col]))
				buf = append(buf, b...)
			}
			rowHash = string(buf)
		}
		rowNum, ok := hash2RowNum[rowHash]
		if !ok {
			rowNum = nextRowNum
			nextRowNum++
			hash2RowNum[rowHash] = rowNum
			start := row * orig.colCount
			entry := append([]int{}, orig.entries[start:start+orig.colCount]...)
			uniqueEntries = append(uniqueEntries, entry...)
		}
		rowNums[row] = rowNum
	}

	tab.UniqueEntries = uniqueEntries
	tab.RowNums = rowNums
	tab.OriginalRowCount = orig.rowCount
	tab.OriginalColCount = orig.colCount

	return nil
}

const ForbiddenValue = -1

type RowDisplacementTable struct {
	OriginalRowCount int
	OriginalColCount int
	EmptyValue       int
	Entries          []int
	Bounds           []int
	RowDisplacement  []int
}

func NewRowDisplacementTable(emptyValue int) *RowDisplacementTable {
	return &RowDisplacementTable{
		EmptyValue: emptyValue,
	}
}

func (tab *RowDisplacementTable) Lookup(row int, col int) (int, error) {
	if row < 0 || row >= tab.OriginalRowCount || col < 0 || col >= tab.OriginalColCount {
		return tab.EmptyValue, fmt.Errorf("indexes are out of range: [%v, %v]", row, col)
	}
	d := tab.RowDisplacement[row]
	if tab.Bounds[d+col] != row {
		return tab.EmptyValue, nil
	}
	return tab.Entries[d+col], nil
}

func (tab *RowDisplacementTable) OriginalTableSize() (int, int) {
	return tab.OriginalRowCount, tab.OriginalColCount
}

type rowInfo struct {
	rowNum        int
	nonEmptyCount int
	nonEmptyCol   []int
}

func (tab *RowDisplacementTable) Compress(orig *OriginalTable) error {
	rowInfo := make([]rowInfo, orig.rowCount)
	{
		row := 0
		col := 0
		rowInfo[0].rowNum = 0
		for _, v := range orig.entries {
			if col == orig.colCount {
				row++
				col = 0
				rowInfo[row].rowNum = row
			}
			if v != tab.EmptyValue {
				rowInfo[row].nonEmptyCount++
				rowInfo[row].nonEmptyCol = append(rowInfo[row].nonEmptyCol, col)
			}
			col++
		}

		sort.SliceStable(rowInfo, func(i int, j int) bool {
			return rowInfo[i].nonEmptyCount > rowInfo[j].nonEmptyCount
		})
	}

	origEntriesLen := len(orig.entries)
	entries := make([]int, origEntriesLen)
	bounds := make([]int, origEntriesLen)
	resultBottom := orig.colCount
	rowDisplacement := make([]int, orig.rowCount)
	{
		for i := 0; i < origEntriesLen; i++ {
			entries[i] = tab.EmptyValue
			bounds[i] = ForbiddenValue
		}

		nextRowDisplacement := 0
		for _, rInfo := range rowInfo {
			if rInfo.nonEmptyCount <= 0 {
				continue
			}

			for {
				isOverlapped := false
				for _, col := range rInfo.nonEmptyCol {
					if entries[nextRowDisplacement+col] == tab.EmptyValue {
						continue
					}
					nextRowDisplacement++
					isOverlapped = true
					break
				}
				if isOverlapped {
					continue
				}

				rowDisplacement[rInfo.rowNum] = nextRowDisplacement
				for _, col := range rInfo.nonEmptyCol {
					entries[nextRowDisplacement+col] = orig.entries[(rInfo.rowNum*orig.colCount)+col]
					bounds[nextRowDisplacement+col] = rInfo.rowNum
				}
				resultBottom = nextRowDisplacement + orig.colCount
				nextRowDisplacement++
				break
			}
		}
	}

	tab.OriginalRowCount = orig.rowCount
	tab.OriginalColCount = orig.colCount
	tab.Entries = entries[:resultBottom]
	tab.Bounds = bounds[:resultBottom]
	tab.RowDisplacement = rowDisplacement

	return nil
}



func Main() {
}