// // TopScores.cs // // Copyright (C) 2004 Novell, Inc. // // // Permission is hereby granted, free of charge, to any person obtaining a // copy of this software and associated documentation files (the "Software"), // to deal in the Software without restriction, including without limitation // the rights to use, copy, modify, merge, publish, distribute, sublicense, // and/or sell copies of the Software, and to permit persons to whom the // Software is furnished to do so, subject to the following conditions: // // The above copyright notice and this permission notice shall be included in // all copies or substantial portions of the Software. // // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER // DEALINGS IN THE SOFTWARE. // using System; using System.Collections; namespace Beagle.Util { public class TopScores { private bool Debug = false; private struct Node { public long Score; public object Obj; public int LtEq; public int Gt; public void Clear () { LtEq = -1; Gt = -1; } } int count; bool at_capacity = false; int free_node = 0; int root_node = -1; Node [] nodes; long cutoff_score; public TopScores (int count) { this.count = count; this.nodes = new Node [count]; for (int i = 0; i < count; ++i) this.nodes [i].Clear (); } public int Count { get { return count; } } public long MinimumScore { get { if (at_capacity) return cutoff_score; long score = 0; int i = root_node; while (i != -1) { score = nodes [i].Score; i = nodes [i].LtEq; } return score; } } public bool WillAccept (long score) { return (! at_capacity) || score > cutoff_score; } public void Add (long score, object obj) { if (at_capacity && score <= cutoff_score) { if (Debug) Console.WriteLine ("Skipping {0} ({1}), since threshold is {2}", obj, score, cutoff_score); return; } int node, next_node, prev_node; // If this is the first thing we are adding, // make it the root node. if (root_node == -1) { if (Debug) Console.WriteLine ("Added {0} ({1}) as root node {2}", obj, score, free_node); root_node = free_node; nodes [free_node].Score = score; nodes [free_node].Obj = obj; ++free_node; return; } // If we are at capacity, find the leftmost node // and detatch it. if (at_capacity) { prev_node = -1; node = root_node; // Find the leftmost node while (true) { next_node = nodes [node].LtEq; if (next_node == -1) break; prev_node = node; node = next_node; } // Detatch the node, and store its index // in free_node so we can re-use it immediately. if (prev_node != -1) { // Detatching a non-root node if (Debug) Console.WriteLine ("Detatching {0} ({1}) from node {2}", nodes [node].Obj, nodes [node].Score, node); nodes [prev_node].LtEq = nodes [node].Gt; free_node = node; node = prev_node; // where to start looking for the new cut-off } else { // Detatching the root node if (Debug) Console.WriteLine ("Detatching {0} ({1}) from root node {2}", nodes [root_node].Obj, nodes [root_node].Score, root_node); free_node = root_node; root_node = nodes [root_node].Gt; node = root_node; // where to start looking for the new cut-off } // Find the new cut-off while (node != -1) { cutoff_score = nodes [node].Score; node = nodes [node].LtEq; } nodes [free_node].Clear (); if (Debug) Console.WriteLine ("New cutoff is {0}", cutoff_score); } // Find where we want to attach this node bool is_lteq = false; node = -1; next_node = root_node; while (next_node != -1) { node = next_node; if (score <= nodes [node].Score) { next_node = nodes [node].LtEq; is_lteq = true; } else { next_node = nodes [node].Gt; is_lteq = false; } } nodes [free_node].Score = score; nodes [free_node].Obj = obj; if (Debug) Console.WriteLine ("Added {0} ({1}) as node {2}, under and {3} of {4}", obj, score, free_node, is_lteq ? "left" : "right", node); if (at_capacity && score < cutoff_score) { cutoff_score = score; if (Debug) Console.WriteLine ("New cutoff is {0}", cutoff_score); } if (is_lteq) nodes [node].LtEq = free_node; else nodes [node].Gt = free_node; if (! at_capacity) { ++free_node; if (free_node >= count) { cutoff_score = MinimumScore; at_capacity = true; if (Debug) Console.WriteLine ("Hit capacity: set cutoff to {0}", cutoff_score); } } } private int ComputeMaxDepth (int i) { if (i == -1) return 0; int a = 1 + ComputeMaxDepth (nodes [i].LtEq); int b = 1 + ComputeMaxDepth (nodes [i].Gt); return Math.Max (a, b); } public int MaxDepth { get { return ComputeMaxDepth (root_node); } } private void BuildArray (ArrayList array, int i) { if (i != -1) { BuildArray (array, nodes [i].Gt); array.Add (nodes [i].Obj); BuildArray (array, nodes [i].LtEq); } } // Returns objects sorted from high to low scores public ICollection TopScoringObjects { get { ArrayList array = new ArrayList (); BuildArray (array, root_node); return array; } } #if false static void Main () { int trial = 0; Random rng = new Random (); for (int j = 0; j < 1000; ++j) { ++trial; Console.WriteLine ("Trial #{0}", trial); TopScores top; top = new TopScores (6 + rng.Next (100)); ArrayList all = new ArrayList (); int i; int N = 100 + rng.Next (100); for (i = 0; i < N; ++i) { int n = rng.Next (200); all.Add (n); top.Add (n, n); } all.Sort (); i = all.Count - 1; foreach (object obj in top.TopScoringObjects) { if (! obj.Equals (all [i])) { Console.WriteLine ("Mismatch!"); i = all.Count - 1; foreach (object x in top.TopScoringObjects) { Console.WriteLine ("{0} {1} {2}", x, all [i], x.Equals (all [i]) ? "" : "***"); --i; } return; } --i; } } } #endif } }