Util/TopScores.cs

   1 //
   2 // TopScores.cs
   3 //
   4 // Copyright (C) 2004 Novell, Inc.
   5 //
   6
   7 //
   8 // Permission is hereby granted, free of charge, to any person obtaining a
   9 // copy of this software and associated documentation files (the "Software"),
  10 // to deal in the Software without restriction, including without limitation
  11 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
  12 // and/or sell copies of the Software, and to permit persons to whom the
  13 // Software is furnished to do so, subject to the following conditions:
  14 //
  15 // The above copyright notice and this permission notice shall be included in
  16 // all copies or substantial portions of the Software.
  17 //
  18 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  20 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  21 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  22 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  23 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  24 // DEALINGS IN THE SOFTWARE.
  25 //
  26
  27 using System;
  28 using System.Collections;
  29
  30 namespace Beagle.Util {
  31
  32         public class TopScores {
  33
  34                 private bool Debug = false;
  35
  36                 private struct Node {
  37                         public long Score;
  38                         public object Obj;
  39                         public int LtEq;
  40                         public int Gt;
  41
  42                         public void Clear ()
  43                         {
  44                                 LtEq = -1;
  45                                 Gt = -1;
  46                         }
  47                 }
  48
  49                 int count;
  50                 bool at_capacity = false;
  51                 int free_node = 0;
  52                 int root_node = -1;
  53                 Node [] nodes;
  54                 long cutoff_score;
  55
  56                 public TopScores (int count)
  57                 {
  58                         this.count = count;
  59                         this.nodes = new Node [count];
  60                         for (int i = 0; i < count; ++i)
  61                                 this.nodes [i].Clear ();
  62                 }
  63
  64                 public int Count {
  65                         get { return count; }
  66                 }
  67
  68                 public long MinimumScore {
  69                         get {
  70                                 if (at_capacity)
  71                                         return cutoff_score;
  72
  73                                 long score = 0;
  74                                 int i = root_node;
  75                                 while (i != -1) {
  76                                         score = nodes [i].Score;
  77                                         i = nodes [i].LtEq;
  78                                 }
  79                                 return score;
  80                         }
  81                 }
  82
  83                 public bool WillAccept (long score)
  84                 {
  85                         return (! at_capacity) || score > cutoff_score;
  86                 }
  87
  88                 public void Add (long score, object obj)
  89                 {
  90                         if (at_capacity && score <= cutoff_score) {
  91                                 if (Debug)
  92                                         Console.WriteLine ("Skipping {0} ({1}), since threshold is {2}",
  93                                                            obj, score, cutoff_score);
  94                                 return;
  95                         }
  96
  97                         int node, next_node, prev_node;
  98
  99                         // If this is the first thing we are adding,
 100                         // make it the root node.
 101                         if (root_node == -1) {
 102                                 if (Debug)
 103                                         Console.WriteLine ("Added {0} ({1}) as root node {2}", obj, score, free_node);
 104                                 root_node = free_node;
 105                                 nodes [free_node].Score = score;
 106                                 nodes [free_node].Obj = obj;
 107                                 UpdateAtCapacity ();
 108                                 return;
 109                         }
 110
 111                         // If we are at capacity, find the leftmost node
 112                         // and detatch it.
 113                         if (at_capacity) {
 114                                 prev_node = -1;
 115                                 node = root_node;
 116
 117                                 // Find the leftmost node
 118                                 while (true) {
 119                                         next_node = nodes [node].LtEq;
 120                                         if (next_node == -1)
 121                                                 break;
 122                                         prev_node = node;
 123                                         node = next_node;
 124                                 }
 125
 126                                 // Detatch the node, and store its index
 127                                 // in free_node so we can re-use it immediately.
 128                                 if (prev_node != -1) {
 129                                         // Detatching a non-root node
 130                                         if (Debug)
 131                                                 Console.WriteLine ("Detatching {0} ({1}) from node {2}",
 132                                                                    nodes [node].Obj, nodes [node].Score, node);
 133                                         nodes [prev_node].LtEq = nodes [node].Gt;
 134                                         free_node = node;
 135
 136                                         node = prev_node; // where to start looking for the new cut-off
 137                                 } else {
 138                                         // Detatching the root node
 139                                         if (Debug)
 140                                                 Console.WriteLine ("Detatching {0} ({1}) from root node {2}",
 141                                                                    nodes [root_node].Obj, nodes [root_node].Score, root_node);
 142                                         free_node = root_node;
 143                                         root_node = nodes [root_node].Gt;
 144
 145                                         node = root_node; // where to start looking for the new cut-off
 146                                 }
 147
 148                                 // Find the new cut-off
 149                                 while (node != -1) {
 150                                         cutoff_score = nodes [node].Score;
 151                                         node = nodes [node].LtEq;
 152                                 }
 153
 154                                 nodes [free_node].Clear ();
 155
 156                                 if (Debug)
 157                                         Console.WriteLine ("New cutoff is {0}", cutoff_score);
 158                         }
 159
 160
 161                         // Find where we want to attach this node
 162                         bool is_lteq = false;
 163                         node = -1;
 164                         next_node = root_node;
 165                         while (next_node != -1) {
 166                                 node = next_node;
 167                                 if (score <= nodes [node].Score) {
 168                                         next_node = nodes [node].LtEq;
 169                                         is_lteq = true;
 170                                 } else {
 171                                         next_node = nodes [node].Gt;
 172                                         is_lteq = false;
 173                                 }
 174                         }
 175
 176                         nodes [free_node].Score = score;
 177                         nodes [free_node].Obj = obj;
 178                         if (Debug)
 179                                 Console.WriteLine ("Added {0} ({1}) as node {2}, under and {3} of {4}",
 180                                                    obj, score, free_node, is_lteq ? "left" : "right", node);
 181
 182                         if (at_capacity && score < cutoff_score) {
 183                                 cutoff_score = score;
 184                                 if (Debug)
 185                                         Console.WriteLine ("New cutoff is {0}", cutoff_score);
 186                         }
 187
 188
 189                         if (is_lteq)
 190                                 nodes [node].LtEq = free_node;
 191                         else
 192                                 nodes [node].Gt = free_node;
 193
 194                         UpdateAtCapacity ();
 195                 }
 196
 197                 private void UpdateAtCapacity ()
 198                 {
 199                         if (at_capacity)
 200                                 return;
 201
 202                         ++free_node;
 203                         if (free_node >= count) {
 204                                 cutoff_score = MinimumScore;
 205                                 at_capacity = true;
 206                                 if (Debug)
 207                                         Console.WriteLine ("Hit capacity: set cutoff to {0}", cutoff_score);
 208
 209                         }
 210                 }
 211
 212                 private int ComputeMaxDepth (int i)
 213                 {
 214                         if (i == -1)
 215                                 return 0;
 216                         int a = 1 + ComputeMaxDepth (nodes [i].LtEq);
 217                         int b = 1 + ComputeMaxDepth (nodes [i].Gt);
 218                         return Math.Max (a, b);
 219                 }
 220
 221                 public int MaxDepth {
 222                         get { return ComputeMaxDepth (root_node); }
 223                 }
 224
 225                 private void BuildArray (ArrayList array, int i)
 226                 {
 227                         if (i != -1) {
 228                                 BuildArray (array, nodes [i].Gt);
 229                                 array.Add (nodes [i].Obj);
 230                                 BuildArray (array, nodes [i].LtEq);
 231                         }
 232                 }
 233
 234                 // Returns objects sorted from high to low scores
 235                 public ICollection TopScoringObjects {
 236                         get {
 237                                 ArrayList array = new ArrayList ();
 238                                 BuildArray (array, root_node);
 239                                 return array;
 240                         }
 241                 }
 242
 243 #if false
 244                 static void Main ()
 245                 {
 246                         int trial = 0;
 247                         Random rng = new Random ();
 248
 249                         for (int j = 0; j < 1000; ++j) {
 250                                 ++trial;
 251                                 Console.WriteLine ("Trial #{0}", trial);
 252
 253                                 TopScores top;
 254                                 top = new TopScores (6 + rng.Next (100));
 255
 256                                 ArrayList all = new ArrayList ();
 257                                 int i;
 258                                 int N = 100 + rng.Next (100);
 259                                 for (i = 0; i < N; ++i) {
 260                                         int n = rng.Next (200);
 261                                         all.Add (n);
 262                                         top.Add (n, n);
 263                                 }
 264
 265                                 all.Sort ();
 266                                 i = all.Count - 1;
 267                                 foreach (object obj in top.TopScoringObjects) {
 268                                         if (! obj.Equals (all [i])) {
 269                                                 Console.WriteLine ("Mismatch!");
 270                                                 i = all.Count - 1;
 271                                                 foreach (object x in top.TopScoringObjects) {
 272                                                         Console.WriteLine ("{0} {1} {2}",
 273                                                                            x, all [i],
 274                                                                            x.Equals (all [i]) ? "" : "***");
 275                                                         --i;
 276                                                 }
 277                                                 return;
 278                                         }
 279                                         --i;
 280                                 }
 281                         }
 282                 }
 283 #endif
 284
 285         }
 286 }