summaryrefslogtreecommitdiff
path: root/python/src/sa/int_list.pxi
diff options
context:
space:
mode:
Diffstat (limited to 'python/src/sa/int_list.pxi')
-rw-r--r--python/src/sa/int_list.pxi177
1 files changed, 177 insertions, 0 deletions
diff --git a/python/src/sa/int_list.pxi b/python/src/sa/int_list.pxi
new file mode 100644
index 00000000..ad14bc9c
--- /dev/null
+++ b/python/src/sa/int_list.pxi
@@ -0,0 +1,177 @@
+# defines int arrays in C, with some convenience methods
+# for reading arrays as globs directly from disk.
+# Adam Lopez <alopez@cs.umd.edu>
+
+from libc.stdio cimport FILE, fopen, fread, fwrite, fclose
+from libc.stdlib cimport malloc, realloc, free
+from libc.string cimport memset, memcpy
+
+cdef class IntList:
+ cdef int size
+ cdef int increment
+ cdef int len
+ cdef int* arr
+
+ def __cinit__(self, int size=0, int increment=1, int initial_len=0):
+ if initial_len > size:
+ size = initial_len
+ self.size = size
+ self.increment = increment
+ self.len = initial_len
+ self.arr = <int*> malloc(size*sizeof(int))
+ memset(self.arr, 0, initial_len*sizeof(int))
+
+ def __str__(self):
+ cdef unsigned i
+ ret = "IntList["
+ for idx in range(self.size):
+ if idx>0:
+ ret += ","
+ ret += str(self.arr[idx])
+ ret += "]"
+ ret += "len="
+ ret += self.len
+ return ret
+
+ def index(self, val):
+ cdef unsigned i
+ for i in range(self.len):
+ if self.arr[i] == val:
+ return i
+ return IndexError
+
+ def partition(self,start,end):
+ pivot = self.arr[end]
+ bottom = start-1
+ top = end
+ done = 0
+ while not done:
+ while not done:
+ bottom += 1
+ if bottom == top:
+ done = 1
+ break
+ if self.arr[bottom] > pivot:
+ self.arr[top] = self.arr[bottom]
+ break
+ while not done:
+ top -= 1
+ if top == bottom:
+ done = 1
+ break
+ if self.arr[top] < pivot:
+ self.arr[bottom] = self.arr[top]
+ break
+ self.arr[top] = pivot
+ return top
+
+ def _doquicksort(self,start,end):
+ if start < end:
+ split = self.partition(start,end)
+ self._doquicksort(start,split-1)
+ self._doquicksort(split+1,end)
+ else:
+ return
+
+ def sort(self):
+ self._doquicksort(0,self.len-1)
+
+ def reset(self):
+ self.len = 0
+
+ def __dealloc__(self):
+ free(self.arr)
+
+ def __getitem__(self, index):
+ cdef int i, j, k
+ if isinstance(index, int):
+ j = index
+ if j < 0:
+ j = self.len + j
+ if j<0 or j>=self.len:
+ raise IndexError("Requested index %d of %d-length IntList" % (index, self.len))
+ return self.arr[j]
+ elif isinstance(index, slice):
+ i = index.start
+ j = index.stop
+ if i < 0:
+ i = self.len + i
+ if j < 0:
+ j = self.len + j
+ if i < 0 or i >= self.len or j < 0 or j > self.len:
+ raise IndexError("Requested index %d:%d of %d-length IntList" % (index.start, index.stop, self.len))
+ result = ()
+ for k from i <= k < j:
+ result = result + (self.arr[k],)
+ return result
+ else:
+ raise TypeError("Illegal key type %s for IntList" % type(index))
+
+ cdef void set(self, int i, int val):
+ j = i
+ if i<0:
+ j = self.len + i
+ if j<0 or j>=self.len:
+ raise IndexError("Requested index %d of %d-length IntList" % (i, self.len))
+ self.arr[j] = val
+
+ def __setitem__(self, i, val):
+ self.set(i, val)
+
+ def __len__(self):
+ return self.len
+
+ def getSize(self):
+ return self.size
+
+ def append(self, int val):
+ self._append(val)
+
+ cdef void _append(self, int val):
+ if self.len == self.size:
+ self.size = self.size + self.increment
+ self.arr = <int*> realloc(self.arr, self.size*sizeof(int))
+ self.arr[self.len] = val
+ self.len = self.len + 1
+
+ def extend(self, other):
+ self._extend(other)
+
+ cdef void _extend(self, IntList other):
+ self._extend_arr(other.arr, other.len)
+
+ cdef void _extend_arr(self, int* other, int other_len):
+ if self.size < self.len + other_len:
+ self.size = self.len + other_len
+ self.arr = <int*> realloc(self.arr, self.size*sizeof(int))
+ memcpy(self.arr+self.len, other, other_len*sizeof(int))
+ self.len = self.len + other_len
+
+ cdef void _clear(self):
+ free(self.arr)
+ self.len = 0
+ self.size = 0
+ self.arr = <int*> malloc(0)
+
+ cdef void write_handle(self, FILE* f):
+ fwrite(&(self.len), sizeof(int), 1, f)
+ fwrite(self.arr, sizeof(int), self.len, f)
+
+ def write(self, char* filename):
+ cdef FILE* f
+ f = fopen(filename, "w")
+ self.write_handle(f)
+ fclose(f)
+
+ cdef void read_handle(self, FILE* f):
+ (self.arr)
+ fread(&(self.len), sizeof(int), 1, f)
+ self.arr = <int*> malloc(self.len * sizeof(int))
+ self.size = self.len
+ fread(self.arr, sizeof(int), self.len, f)
+
+ def read(self, char* filename):
+ cdef FILE* f
+ f = fopen(filename, "r")
+ self.read_handle(f)
+ fclose(f)