package art import "core:os" import "core:mem" import "core:math/bits" import "core:fmt" ALPHABET_SIZE :: 26 /* CTrie (104B) uses smallest index possible to reduce size constraints data allocated in array -> easy to free/clear/delete should be the same speed of the default Trie */ // treating 0 as nil as 0 is the root CTrie :: struct { array: [ALPHABET_SIZE]u32, } ctrie_data: [dynamic]CTrie ctrie_init :: proc(cap: int) { ctrie_data = make([dynamic]CTrie, 0, cap) append(&ctrie_data, CTrie {}) } ctrie_destroy :: proc() { delete(ctrie_data) } // push a node to the ctrie array and return its index ctrie_push :: proc() -> u32 { append(&ctrie_data, CTrie {}) return u32(len(ctrie_data) - 1) } // simple helper ctrie_get :: #force_inline proc(index: u32) -> ^CTrie { return &ctrie_data[index] } // get the root of the ctrie tree ctrie_root :: #force_inline proc() -> ^CTrie { return &ctrie_data[0] } // insert a key ctrie_insert :: proc(key: string) { t := ctrie_root() for b in key { idx := b - 'a' if t.array[idx] == 0 { t.array[idx] = ctrie_push() } t = ctrie_get(t.array[idx]) } } // print the ctrie tree ctrie_print :: proc() { depth: int ctrie_print_recursive(ctrie_root(), &depth, 0) } // print the ctrie tree recursively by nodes ctrie_print_recursive :: proc(t: ^CTrie, depth: ^int, b: u8) { if depth^ != 0 { for i in 0.. (res: ^u32) { old := comp_index res = cast(^u32) &comp[old] comp_index += size_of(u32) return } // push trie children nodes as indexes comp_push_data :: proc(count: int) -> (res: []u32) { old := comp_index res = mem.slice_ptr(cast(^u32) &comp[old], count) comp_index += size_of(u32) * count return } // push a ctrie bitfield and its dynamic data comp_push_ctrie :: proc(t: ^CTrie, previous_data: ^u32) { if previous_data != nil { previous_data^ = u32(comp_index) } alphabet_bits := comp_push_bits() for i in 0.. bool { // mask := u32(1 << u32(b - 'a')) // return bits & mask == mask // } // true when the idx exists in the bitfield comp_bits_contains_index :: proc(bits: u32, idx: u32) -> bool { mask := u32(1 << idx) return bits & mask == mask } // print logical size of the compressed trie comp_print_size :: proc() { size := comp_index fmt.eprintf("SIZE in %dB %dKB %dMB for compressed\n", size, size / 1024, size / 1024 / 1024) } // converts alphabetic byte index into the remapped bitfield space comp_bits_index_to_counted_one :: proc(bits: u32, idx: u32) -> (res: u32, ok: bool) { mask: u32 for i in 0.. u8 { if 'A' <= b && b <= 'Z' { return b + 32 } else { return b } } // wether the byte is a letter ascii_is_letter :: #force_inline proc(b: u8) -> bool { return 'a' <= b && b <= 'z' } // searches the compressed trie for the wanted word comp_search :: proc(key: string) -> bool { alphabet_bits := cast(^u32) &comp[0] for i in 0.. bool { return os.write_entire_file(path, comp[:]) } comp_read_from_file :: proc(path: string) { content, ok := os.read_entire_file(path) if ok { comp = content comp_index = len(content) } }