<commit_before>package cuckoo

import (
	"log"
	"math/rand"
	"os"
)

type Comparable interface {
	Compare(other Comparable) int
}

type BucketLocation struct {
	Bucket1 int
	Bucket2 int
}

type Bucket struct {
	// `entries` and `filled` must be the same size
	data      []Comparable     // Stores actual data. Validity of an entry determined by `filled`
	bucketLoc []BucketLocation // Stores the 2 bucket locations for each entry
	filled    []bool           // False if cell is empty. Only read `t.entries[i]` if `t.filled[i]==true`
}

type Table struct {
	log        *log.Logger
	name       string
	numBuckets int // Number of buckets
	depth      int // Capacity of each bucket
	rand       *rand.Rand

	buckets []*Bucket // Data
}

// Creates a brand new cuckoo table
// Two cuckoo tables will have identical state iff,
// 1. the same randSeed is used
// 2. the same operations are applied in the same order
// numBuckets = number of buckets
// depth = the number of entries per bucket
// randSeed = seed for PRNG
func NewTable(name string, numBuckets int, depth int, randSeed int64) *Table {
	t := &Table{}
	t.log = log.New(os.Stdout, "[Cuckoo:"+name+"] ", log.Ldate|log.Ltime|log.Lshortfile)
	t.name = name
	t.numBuckets = numBuckets
	t.depth = depth
	t.rand = rand.New(rand.NewSource(randSeed))

	t.buckets = make([]*Bucket, numBuckets)
	for i := 0; i < numBuckets; i++ {
		t.buckets[i] = &Bucket{}
		t.buckets[i].data = make([]Comparable, depth)
		t.buckets[i].bucketLoc = make([]BucketLocation, depth)
		// We assume this will be filled with `false` as per bool's default value
		t.buckets[i].filled = make([]bool, depth)
	}
	return t
}

/********************
 * PUBLIC METHODS
 ********************/

// Checks if value exists in specified buckets
// Returns true if `value.Equals(...)` returns true
func (t *Table) Contains(bucket1 int, bucket2 int, value Comparable) bool {
	result := false
	if bucket1 < t.numBuckets {
		result = result || t.isInBucket(bucket1, value)
	}
	if bucket2 < t.numBuckets {
		result = result || t.isInBucket(bucket2, value)
	}
	return result
}

/**
// Inserts the value into the cuckoo table
//   fails if either bucket already contains value
// Returns true on success, false if not inserted
// Even if false is returned, the underlying data structure might be different (e.g. rebuilt)
func (t *Table) Insert(bucket1, bucket2, value Comparable) bool {
	coin := rand.Int31()
	ok := t.tryInsertToBucket(e.Bucket1, e)
	if ok {
		return true
	}
	ok = t.tryInsertToBucket(e.Bucket2, e)
	if ok {
		return true
	}
	// @todo Evict

}

// Removes the entry from the cuckoo table
func (t *Table) Remove(bucket1 int, bucket2 int, target Comparable) {
	t.removeFromBucket(target.Bucket1, target)
	t.removeFromBucket(target.Bucket2, target)
}
**/

/********************
 * PRIVATE METHODS
 ********************/

// Checks if the `value` is in a specified bucket
// Returns true if `value.Equals(...)` returns true
func (t *Table) isInBucket(bucketIndex int, value Comparable) bool {
	bucket := t.buckets[bucketIndex]
	for i := 0; i < t.depth; i++ {
		if bucket.filled[i] && value.Compare(bucket.data[i]) == 0 {
			return true
		}
	}
	return false
}

/**
// Tries to inserts `target` into specified bucket
// bucketIndex must be either `target.Bucket1` or `target.Bucket2` or nothing happens
// If the bucket is already full, skip
// Returns true if success, false if bucket already full
func (t *Table) tryInsertToBucket(bucketIndex int, target *Entry) bool {
	// Assert bucketIndex is part of `target`
	if target.Bucket1 != bucketIndex && target.Bucket2 != bucketIndex {
		return false
	}

	// Search for an empty slot
	bucket := t.buckets[bucketIndex]
	for i, filled := range bucket.filled {
		if !filled {
			bucket.filled[i] = true
			bucket.entries[i] = target
			return true
		}
	}

	return false
}

func (t *Table) evictAndInsert(bucketIndex int, target *Entry) *Entry {
}

// Removes all copies of `target` from the specified bucket
// `target` matches against any entry where all fields match<commit_msg>first attempt at eviction loop<commit_after>package cuckoo

import (
	"log"
	"math/rand"
	"os"
)

const MAX_EVICTIONS int = 500

type Comparable interface {
	Compare(other Comparable) int
}

type BucketLocation struct {
	Bucket1 int
	Bucket2 int
}

type Bucket struct {
	// `entries` and `filled` must be the same size
	data      []Comparable     // Stores actual data. Validity of an entry determined by `filled`
	bucketLoc []BucketLocation // Stores the 2 bucket locations for each entry
	filled    []bool           // False if cell is empty. Only read `t.entries[i]` if `t.filled[i]==true`
}

type Table struct {
	log        *log.Logger
	name       string
	numBuckets int // Number of buckets
	depth      int // Capacity of each bucket
	rand       *rand.Rand

	buckets []*Bucket // Data
}

// Creates a brand new cuckoo table
// Two cuckoo tables will have identical state iff,
// 1. the same randSeed is used
// 2. the same operations are applied in the same order
// numBuckets = number of buckets
// depth = the number of entries per bucket
// randSeed = seed for PRNG
func NewTable(name string, numBuckets int, depth int, randSeed int64) *Table {
	t := &Table{}
	t.log = log.New(os.Stdout, "[Cuckoo:"+name+"] ", log.Ldate|log.Ltime|log.Lshortfile)
	t.name = name
	t.numBuckets = numBuckets
	t.depth = depth
	t.rand = rand.New(rand.NewSource(randSeed))

	t.buckets = make([]*Bucket, numBuckets)
	for i := 0; i < numBuckets; i++ {
		t.buckets[i] = &Bucket{}
		t.buckets[i].data = make([]Comparable, depth)
		t.buckets[i].bucketLoc = make([]BucketLocation, depth)
		// We assume this will be filled with `false` as per bool's default value
		t.buckets[i].filled = make([]bool, depth)
	}
	return t
}

/********************
 * PUBLIC METHODS
 ********************/

// Checks if value exists in specified buckets
// Returns true if `value.Equals(...)` returns true
func (t *Table) Contains(bucket1 int, bucket2 int, value Comparable) bool {
	result := false
	if bucket1 < t.numBuckets {
		result = result || t.isInBucket(bucket1, value)
	}
	if bucket2 < t.numBuckets {
		result = result || t.isInBucket(bucket2, value)
	}
	return result
}

// Inserts the value into the cuckoo table
// Returns true on success, false on failure
//   fails if insertion cannot complete because reached MAX_EVICTIONS
//	 failures return an evicted value and must trigger a rebuild by the caller
func (t *Table) Insert(bucket1 int, bucket2 int, value Comparable) (int, int, Comparable, bool) {
	var ok bool
	var nextBucket int
	currBucketLoc := BucketLocation{bucket1, bucket2}
	currVal := value

	// Randomly select 1 bucket first
	coin := t.rand.Int() % 2 // Coin could be -1, 0 or 1
	if coin == 0 {
		ok = t.tryInsertToBucket(bucket1, currBucketLoc, currVal)
		nextBucket = bucket2
	} else {
		ok = t.tryInsertToBucket(bucket2, currBucketLoc, currVal)
		nextBucket = bucket1
	}
	if ok {
		return -1, -1, nil, true
	}

	// Then try the other bucket, starting the eviction loop
	for i := 0; i < MAX_EVICTIONS; i++ {
		nextBucket, currBucketLoc, currVal, ok = t.insertAndEvict(nextBucket, currBucketLoc, currVal)
		if ok {
			return -1, -1, nil, true
		}
	}

	return currBucketLoc.Bucket1, currBucketLoc.Bucket2, currVal, false
}

/**
// Removes the entry from the cuckoo table
func (t *Table) Remove(bucket1 int, bucket2 int, target Comparable) {
	t.removeFromBucket(target.Bucket1, target)
	t.removeFromBucket(target.Bucket2, target)
}
**/

/********************
 * PRIVATE METHODS
 ********************/

// Checks if the `value` is in a specified bucket
// Returns true if `value.Equals(...)` returns true
func (t *Table) isInBucket(bucketIndex int, value Comparable) bool {
	bucket := t.buckets[bucketIndex]
	for i := 0; i < t.depth; i++ {
		if bucket.filled[i] && value.Compare(bucket.data[i]) == 0 {
			return true
		}
	}
	return false
}

// Tries to inserts `bucketLoc, value` into specified bucket
// If the bucket is already full, skip
// Returns true if success, false if bucket already full
func (t *Table) tryInsertToBucket(bucketIndex int, bucketLoc BucketLocation, value Comparable) bool {
	// Search for an empty slot
	bucket := t.buckets[bucketIndex]
	for i := 0; i < t.depth; i++ {
		if !bucket.filled[i] {
			bucket.data[i] = value
			bucket.bucketLoc[i] = bucketLoc
			bucket.filled[i] = true
			return true
		}
	}

	return false
}

// Tries to insert `bucketLoc, value` into specified bucket
// Returns -1, BucketLocation{}, nil, true if there's empty space and succeeds
// Returns false if insertion triggered an eviction
//   other values contain the evicted item's alternate bucket, BucketLocation pair, and value
func (t *Table) insertAndEvict(bucketIndex int, bucketLoc BucketLocation, value Comparable) (int, BucketLocation, Comparable, bool) {
	ok := t.tryInsertToBucket(bucketIndex, bucketLoc, value)
	if ok {
		return -1, BucketLocation{}, nil, true
	}

	// Eviction
	randIndex := t.rand.Int() % t.depth
	if randIndex < 0 {
		randIndex *= -1
	}
	bucket := t.buckets[bucketIndex]
	evictedBucketLoc := bucket.bucketLoc[randIndex]
	evictedValue := bucket.data[randIndex]
	bucket.bucketLoc[randIndex] = bucketLoc
	bucket.data[randIndex] = value
	bucket.filled[randIndex] = true
	if bucketIndex == evictedBucketLoc.Bucket1 {
		return evictedBucketLoc.Bucket2, evictedBucketLoc, evictedValue, false
	} else if bucketIndex == evictedBucketLoc.Bucket2 {
		return evictedBucketLoc.Bucket1, evictedBucketLoc, evictedValue, false
	} else {
		t.log.Fatalf("insertAndEvict: misplaced value! bucketIndex=%v does not match %v", bucketIndex, evictedBucketLoc)
		return -1, BucketLocation{}, nil, false
	}
}

/**
// Removes all copies of `target` from the specified bucket
// `target` matches against any entry where all fields match
{'fraction_non_alphanumeric': 0.1279819801371967, 'fraction_numerical': 0.008600389065219618, 'mean_word_length': 3.7142857142857144, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7610212', 'n_tokens_mistral': 3316, 'n_tokens_neox': 3151, 'n_words': 1086}