15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2012 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "encodings/compact_lang_det/tote.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string.h> // memset 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "encodings/compact_lang_det/win/cld_logging.h" 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Take a set of <key, value> pairs and tote them up. 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// After explicitly sorting, retrieve top key, value pairs 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Tote::Tote() { 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gram_count_ = 0; 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) incr_count_ = 0; 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) byte_count_ = 0; 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(key_, 0, sizeof(key_)); 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // No need to initialize values 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Tote::~Tote() { 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Tote::Reinit() { 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) gram_count_ = 0; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) incr_count_ = 0; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) byte_count_ = 0; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(key_, 0, sizeof(key_)); 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // No need to initialize values 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Increment count of quadgrams/trigrams/unigrams scored 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Tote::AddGram() { 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++gram_count_; 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Three-way associative, guaranteeing that the largest two counts are always 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the data structure. kMaxSize must be a multiple of 3, and is tied to the 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// subscript calculations here, which are for 8 sets of 3-way associative 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// buckets. The subscripts for set N are [N], [N+8], and [N+16] used in a 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// slightly-weird way: The initial probe point is [N] or [N+8], whichever 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// is specified by key mod 16. In most cases (nearly *all* cases except Latin 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// script), this entry matches and we update/return. The second probe is 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the other of [N] and [N+8]. The third probe is only used as a fallback to 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// these two, and is there only for the rare case that there are three or more 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// languages with Language enum values equal mod 8, contending within the same 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// bucket. This can only happen in Latin and (rarely) Cyrillic scripts, because 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the other scripts have fewer than 17 languages total. 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If you change kMaxSize, change the constants 7/8/15/16 below 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Tote::Add(uint8 ikey, int idelta) { 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(ikey != 0); 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++incr_count_; 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Look for existing entry 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int sub0 = ikey & 15; 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub0] == ikey) { 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[sub0] += idelta; 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int sub1 = sub0 ^ 8; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub1] == ikey) { 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[sub1] += idelta; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int sub2 = (ikey & 7) + 16; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub2] == ikey) { 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[sub2] += idelta; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocate new entry 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int alloc = -1; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub0] == 0) { 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc = sub0; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (key_[sub1] == 0) { 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc = sub1; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (key_[sub2] == 0) { 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc = sub2; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // All choices allocated, need to replace smallest one 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc = sub0; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value_[sub1] < value_[alloc]) {alloc = sub1;} 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value_[sub2] < value_[alloc]) {alloc = sub2;} 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key_[alloc] = ikey; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[alloc] = idelta; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Return current top key 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int Tote::CurrentTopKey() { 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int top_key = 0; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int top_value = -1; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int sub = 0; sub < kMaxSize_; ++sub) { 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub] == 0) {continue;} 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (top_value < value_[sub]) { 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) top_value = value_[sub]; 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) top_key = key_[sub]; 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return top_key; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Sort first n entries by decreasing order of value 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If key==0 other fields are not valid, treat value as -1 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Tote::Sort(int n) { 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is n**2, but n is small 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int sub = 0; sub < n; ++sub) { 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub] == 0) {value_[sub] = -1;} 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Bubble sort key[sub] and entry[sub] 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int sub2 = sub + 1; sub2 < kMaxSize_; ++sub2) { 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub2] == 0) {value_[sub2] = -1;} 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value_[sub] < value_[sub2]) { 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // swap 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8 tmpk = key_[sub]; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key_[sub] = key_[sub2]; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key_[sub2] = tmpk; 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int tmpv = value_[sub]; 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[sub] = value_[sub2]; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[sub2] = tmpv; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Tote::Dump(FILE* f) { 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int sub = 0; sub < kMaxSize_; ++sub) { 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub] > 0) { 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(f, "[%2d] %3d %8d\n", sub, key_[sub], value_[sub]); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(f, "%d %d %d\n", gram_count_, incr_count_, byte_count_); 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Take a set of <key, value> pairs and tote them up. 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// After explicitly sorting, retrieve top key, value pairs 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ToteWithReliability::ToteWithReliability() { 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // No need to initialize score_ or value_ 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) incr_count_ = 0; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sorted_ = 0; 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(closepair_, 0, sizeof(closepair_)); 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(key_, 0, sizeof(key_)); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ToteWithReliability::~ToteWithReliability() { 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ToteWithReliability::Reinit() { 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // No need to initialize score_ or value_ 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) incr_count_ = 0; 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sorted_ = 0; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(closepair_, 0, sizeof(closepair_)); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(key_, 0, sizeof(key_)); 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ////ss_.Init(); 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Weight reliability by ibytes 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Also see three-way associative comments above for Tote 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ToteWithReliability::Add(uint8 ikey, int ibytes, 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int score, int ireliability) { 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(ikey != 0); 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(sorted_ == 0); 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++incr_count_; 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Look for existing entry 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int sub0 = ikey & 15; 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub0] == ikey) { 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[sub0] += ibytes; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) score_[sub0] += score; 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reliability_[sub0] += ireliability * ibytes; 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int sub1 = sub0 ^ 8; 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub1] == ikey) { 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[sub1] += ibytes; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) score_[sub1] += score; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reliability_[sub1] += ireliability * ibytes; 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int sub2 = (ikey & 7) + 16; 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub2] == ikey) { 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[sub2] += ibytes; 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) score_[sub2] += score; 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reliability_[sub2] += ireliability * ibytes; 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocate new entry 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int alloc = -1; 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub0] == 0) { 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc = sub0; 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (key_[sub1] == 0) { 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc = sub1; 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (key_[sub2] == 0) { 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc = sub2; 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // All choices allocated, need to replace smallest one 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) alloc = sub0; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value_[sub1] < value_[alloc]) {alloc = sub1;} 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value_[sub2] < value_[alloc]) {alloc = sub2;} 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key_[alloc] = ikey; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[alloc] = ibytes; 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) score_[alloc] = score; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reliability_[alloc] = ireliability * ibytes; 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Find subscript of a given packed language, or -1 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int ToteWithReliability::Find(uint8 ikey) { 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DCHECK(ikey != 0); 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (sorted_) { 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Linear search if sorted 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int sub = 0; sub < kMaxSize_; ++sub) { 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub] == ikey) {return sub;} 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return -1; 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Look for existing entry 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int sub0 = ikey & 15; 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub0] == ikey) { 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return sub0; 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int sub1 = sub0 ^ 8; 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub1] == ikey) { 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return sub1; 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int sub2 = (ikey & 7) + 16; 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub2] == ikey) { 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return sub2; 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return -1; 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Return current top key 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int ToteWithReliability::CurrentTopKey() { 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int top_key = 0; 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int top_value = -1; 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int sub = 0; sub < kMaxSize_; ++sub) { 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub] == 0) {continue;} 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (top_value < value_[sub]) { 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) top_value = value_[sub]; 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) top_key = key_[sub]; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return top_key; 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Sort first n entries by decreasing order of value 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// If key==0 other fields are not valid, treat value as -1 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ToteWithReliability::Sort(int n) { 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is n**2, but n is small 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int sub = 0; sub < n; ++sub) { 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub] == 0) {value_[sub] = -1;} 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Bubble sort key[sub] and entry[sub] 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int sub2 = sub + 1; sub2 < kMaxSize_; ++sub2) { 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub2] == 0) {value_[sub2] = -1;} 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (value_[sub] < value_[sub2]) { 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // swap 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint8 tmpk = key_[sub]; 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key_[sub] = key_[sub2]; 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key_[sub2] = tmpk; 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int tmpv = value_[sub]; 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[sub] = value_[sub2]; 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) value_[sub2] = tmpv; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int tmps = score_[sub]; 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) score_[sub] = score_[sub2]; 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) score_[sub2] = tmps; 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int tmpr = reliability_[sub]; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reliability_[sub] = reliability_[sub2]; 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reliability_[sub2] = tmpr; 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sorted_ = 1; 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ToteWithReliability::Dump(FILE* f) { 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int sub = 0; sub < kMaxSize_; ++sub) { 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (key_[sub] > 0) { 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(f, "[%2d] %3d %6d %5d %4d\n", 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sub, key_[sub], value_[sub], score_[sub], reliability_[sub]); 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(f, " %d#\n", incr_count_); 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 300