5 // Alexander Chebaturkin (chebaturkin@gmail.com)
7 // Copyright (C) 2012 Alexander Chebaturkin
9 // Permission is hereby granted, free of charge, to any person obtaining
10 // a copy of this software and associated documentation files (the
11 // "Software"), to deal in the Software without restriction, including
12 // without limitation the rights to use, copy, modify, merge, publish,
13 // distribute, sublicense, and/or sell copies of the Software, and to
14 // permit persons to whom the Software is furnished to do so, subject to
15 // the following conditions:
17 // The above copyright notice and this permission notice shall be
18 // included in all copies or substantial portions of the Software.
20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
29 using System.Collections.Generic;
31 namespace Mono.CodeContracts.Static.Analysis.Numerical {
32 public abstract class Threshold<T> {
33 protected int NextFree;
34 protected readonly List<T> Values;
36 protected abstract T MinusInfinity { get; }
37 protected abstract T PlusInfinity { get; }
38 protected abstract T Zero { get; }
40 public int Count { get { return Values.Count; } }
42 protected Threshold (int size)
44 Values = new List<T> (size) {MinusInfinity, Zero, PlusInfinity};
48 public bool Add (T value)
50 if (NextFree == Values.Count)
54 while (idx < NextFree && LessThan (Values[idx], value))
57 if (Values[idx].Equals (value))
60 Values.Insert (idx, value);
65 protected abstract bool LessThan (T a, T b);
67 public T GetNext (T value)
69 var index = BinarySearch (value, 0, NextFree - 1);
74 var nextIndex = ~index; //because binary search returns position of next item if not found
75 return Values[nextIndex];
78 public T GetPrevious (T value)
80 var index = BinarySearch (value, 0, NextFree - 1);
85 var nextIndex = ~index;
86 return Values[nextIndex - 1];
89 public int BinarySearch (T value, int low, int hi)
92 var median = low + ((hi - low) >> 1);
93 if (Values[median].Equals (value))
95 if (LessThan (Values[median], value))