Rice Video Plugin for GLES1.1

[mupen64plus-pandora.git] / source / rice_gles / src / CSortedList.h

diff --git a/source/rice_gles/src/CSortedList.h b/source/rice_gles/src/CSortedList.h
new file mode 100644 (file)
index 0000000..91fa9fa
--- /dev/null
+++ b/source/rice_gles/src/CSortedList.h
@@ -0,0 +1,164 @@
+/*
+Copyright (C) 2003 Rice1964
+
+This program is free software; you can redistribute it and/or
+modify it under the terms of the GNU General Public License
+as published by the Free Software Foundation; either version 2
+of the License, or (at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+*/
+
+#ifndef _SORTED_LIST_H_
+#define _SORTED_LIST_H_
+
+#include <cstring>
+
+template<class Key, class Element>
+class CSortedList
+{
+private:
+    Key *keys;
+    Element *elements;
+    int curSize;
+    int maxSize;
+
+public:
+    CSortedList(int size=1000)
+    {
+        maxSize = size;
+        curSize = 0;
+        keys = new Key[size];
+        elements = new Element[size];
+    }
+
+    ~CSortedList()
+    {
+        delete [] keys;
+        delete [] elements;
+    }
+
+    int size()
+    {
+        return curSize;
+    }
+
+    void clear()
+    {
+        curSize = 0;
+    }
+
+    void add(Key key, Element ele)
+    {
+        int i = find(key);
+        if( i >= 0 )
+        {
+            elements[i] = ele;
+            return;
+        }
+
+        if( curSize == maxSize )
+        {
+            // Need to increase maxSize
+            Key *oldkeys = keys;
+            Element *oldelements = elements;
+            int oldmaxsize = maxSize;
+            maxSize *= 2;
+
+            keys = new Key[maxSize];
+            elements = new Element[maxSize];
+            std::memcpy(keys,oldkeys,oldmaxsize*sizeof(Key));
+            std::memcpy(elements,oldelements,oldmaxsize*sizeof(Element));
+        }
+
+        for( i=0; i<curSize; i++ )
+        {
+            if( keys[i] > key )
+            {
+                // Found the spot
+                break;
+            }
+        }
+
+        for( int j=curSize; j>i; j-- )
+        {
+            keys[j] = keys[j-1];
+            elements[j] = elements[j-1];
+        }
+
+        keys[i] = key;
+        elements[i] = ele;
+        curSize++;
+    }
+
+    Element operator[](int index)
+    {
+        if( index >= curSize )
+            index = curSize-1;
+        else if( index < 0 )
+            index = 0;
+
+        return elements[index];
+    }
+
+    Element get(Key key)
+    {
+        int index = Find(key);
+        return this->operator[](index);
+    }
+
+    // Binary search
+    int find(Key key)
+    {
+        if( curSize <= 0 )
+            return -1;
+
+        int dwMin = 0;
+        int dwMax = curSize - 1;
+        int index = -1;
+
+        int dwRange;
+        int dwIndex;
+
+        while (true)
+        {
+            dwRange = dwMax - dwMin;
+            dwIndex = dwMin + (dwRange/2);
+
+            if( keys[dwIndex] == key )
+            {
+                index = dwIndex;
+                break;
+            }
+
+            // If the range is 0, and we didn't match above, then it must be unmatched
+            if (dwRange == 0) 
+                break;
+
+            // If lower, check from min..index
+            // If higher, check from index..max
+            if (key < keys[dwIndex])
+            {
+                // Lower
+                dwMax = dwIndex;
+            }
+            else
+            {
+                // Higher
+                dwMin = dwIndex + 1;
+            }
+        }
+
+        return index;
+    }
+};
+
+#endif
+