# 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: 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 += str(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 __iter__(self): cdef int i for i in range(self.len): yield self.arr[i] 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 get_size(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)