source/gles2rice/src/CSortedList.h

   1 /*
   2 Copyright (C) 2003 Rice1964
   3
   4 This program is free software; you can redistribute it and/or
   5 modify it under the terms of the GNU General Public License
   6 as published by the Free Software Foundation; either version 2
   7 of the License, or (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  17 */
  18
  19 #ifndef _SORTED_LIST_H_
  20 #define _SORTED_LIST_H_
  21
  22 #include <cstring>
  23
  24 template<class Key, class Element>
  25 class CSortedList
  26 {
  27 private:
  28     Key *keys;
  29     Element *elements;
  30     int curSize;
  31     int maxSize;
  32
  33 public:
  34     CSortedList(int size=1000)
  35     {
  36         maxSize = size;
  37         curSize = 0;
  38         keys = new Key[size];
  39         elements = new Element[size];
  40     }
  41
  42     ~CSortedList()
  43     {
  44         delete [] keys;
  45         delete [] elements;
  46     }
  47
  48     int size()
  49     {
  50         return curSize;
  51     }
  52
  53     void clear()
  54     {
  55         curSize = 0;
  56     }
  57
  58     void add(Key key, Element ele)
  59     {
  60         int i = find(key);
  61         if( i >= 0 )
  62         {
  63             elements[i] = ele;
  64             return;
  65         }
  66
  67         if( curSize == maxSize )
  68         {
  69             // Need to increase maxSize
  70             Key *oldkeys = keys;
  71             Element *oldelements = elements;
  72             int oldmaxsize = maxSize;
  73             maxSize *= 2;
  74
  75             keys = new Key[maxSize];
  76             elements = new Element[maxSize];
  77             std::memcpy(keys,oldkeys,oldmaxsize*sizeof(Key));
  78             std::memcpy(elements,oldelements,oldmaxsize*sizeof(Element));
  79         }
  80
  81         for( i=0; i<curSize; i++ )
  82         {
  83             if( keys[i] > key )
  84             {
  85                 // Found the spot
  86                 break;
  87             }
  88         }
  89
  90         for( int j=curSize; j>i; j-- )
  91         {
  92             keys[j] = keys[j-1];
  93             elements[j] = elements[j-1];
  94         }
  95
  96         keys[i] = key;
  97         elements[i] = ele;
  98         curSize++;
  99     }
 100
 101     Element operator[](int index)
 102     {
 103         if( index >= curSize )
 104             index = curSize-1;
 105         else if( index < 0 )
 106             index = 0;
 107
 108         return elements[index];
 109     }
 110
 111     Element get(Key key)
 112     {
 113         int index = Find(key);
 114         return this->operator[](index);
 115     }
 116
 117     // Binary search
 118     int find(Key key)
 119     {
 120         if( curSize <= 0 )
 121             return -1;
 122
 123         int dwMin = 0;
 124         int dwMax = curSize - 1;
 125         int index = -1;
 126
 127         int dwRange;
 128         int dwIndex;
 129
 130         while (true)
 131         {
 132             dwRange = dwMax - dwMin;
 133             dwIndex = dwMin + (dwRange/2);
 134
 135             if( keys[dwIndex] == key )
 136             {
 137                 index = dwIndex;
 138                 break;
 139             }
 140
 141             // If the range is 0, and we didn't match above, then it must be unmatched
 142             if (dwRange == 0)
 143                 break;
 144
 145             // If lower, check from min..index
 146             // If higher, check from index..max
 147             if (key < keys[dwIndex])
 148             {
 149                 // Lower
 150                 dwMax = dwIndex;
 151             }
 152             else
 153             {
 154                 // Higher
 155                 dwMin = dwIndex + 1;
 156             }
 157         }
 158
 159         return index;
 160     }
 161 };
 162
 163 #endif
 164