Implementation of Important Data Structures

1KB

sequence.c

Open

800B

sequence.h

Open

2KB

mutable-maps-hashtable.rkt

Open

792B

mutable-sequence-stack.rkt

Open

sequence.h ( where we store all our funct declarations, and struct def) sequence.c ( funct defs)

//
//sequence.h
//contains the structure definition as well as the headers/prototypes/declarations of
// the functions
//

struct Sequence{
	int size; // How many items are in use?
	int *theArray; 
	int cap; // How many items can maximumally hold
};
struct Sequence emptySeq();

int size(struct Sequence s);
void add (struct Sequence *s, int e);
void remove(struct Sequence *s);
int index(struct Sequence s, int i);
void freeSeq(struct Sequence *s);
//they ALL pointers because of the call-by-value property of C.
//WE ARE changing stuff in these sequences, and we want them to stick
//hence we want the pointer to the memory that has the desired sequence 
//and change them with lvalue deferences :O
//we see size and index, don't have it, cause call-by-value doesn't affect
//functionality or not.


c


#include "sequence.h"
struct SeqImpl{
int size, *theArray, cap;
};

const int limit = 10;
Sequence emptySeq(){
Sequence res = malloc(sizeof(struct SeqImpl));
// think that's there since cannot get from .h? as linking step is after compile?
res->size=0;
res->theArray = malloc(limit * sizeof(int));
res->cap = limit;
return res;
}

int size(Sequence s){
return s->size;
}
//...
//
//
//
void add(Sequence s, int e){

//push
if(s->size == cap){
//too big?i
printf("cant it full");
printf("\n jk no we ballin");
s->theArray = realloc(s->theArray, 2*cap*sizeof(int));
s->cap = 2*cap;
}
// access and set in O(1)
// baby

(s->theArray)[s->size++]=e;
}
void remove(Sequence s){
//pop
if((s->size)==0){
print("oi no doing that");
}
(s->size)--;
}





void freeSeq(Sequence s){
free(s->theArray);
//able to do this to clear entire array since contiguous, which
//may not be the case for linked lists.
free(s);
}

int main(){

Sequence s = emptySeq();
s->size = 100; //this errors since we don't know s's structure.
	      
freeSeq(s);
}
// note none of the ADT Operations consume pointers, because type Sequence is 
// already a pointer—PREVENTING clients from accessing the internals.
// but nothings preventing clients from redefining a structure Sequence ( with similar defs,
// doesn't have to be same ), within main.c.
// yea true, but datz all we can do?

Stacks ( mutable sequences)

#lang racket
(struct seq (vec idx) #:mutable)

(define (make-empty)
  (seq (make-vector LENGTH) 0))
(define (first s )
  (vector-ref (seq-vec s)
              (sub1 (seq-idx s)))

  (define (add e s )
    (define i (seq-idx s ))
    (vector-set! (seq-vec s) i e)
    (set-seq-idx! s (add1 i)))
  (define (remove s)

    (set-seq-idx! s (sub1 (seq-idx s)))
    )

 ;; the flaw in this implementation, is that
  ;; the length of vector has to be constant,
  ;; before opeations are performed.
  ;;
  ;; if we live with this, we see all
  ;; implementations are in O(1) time.

;; This data structure has a name, because its so useful:
  ;; a stack.
  ;; add op is called push
  ;; remove op is called pop


 ;; this data-structure plays a key-role in
 ;; implementation of programming languages.

Hashtables (mutable maps)

#lang racket

(define (create-hashtable size)
 (make-vector size empty))

;; we use a hash function to map the keys
;; to the range of vector indices.
;; in this case, just remainder on division by
;; vector length


;; searches key in hashmap
(define (ht-search table key)

  (define index (modulo key(vector-length table)))
  (define hashlist (vector-ref table index))
;;association list with a namechange since in hashmap
  (define lookup (assoc key hashlist))
  (if lookup (second lookup) false))

(define (ht-add table key val)
  (define index (modulo key
                        (vector-length table)))
  ;; if values there we overwrite iggg
;;  (define hashlist (vector-ref table index))
 
  ;(vector-set! table index (list key val))
 ;; why is setting like this a no go? what else
  ;; could this list have bro. ohhhh, it can have
  ;; multiple keys in one index, not just multiple
  (define hashlist (vector-ref table index))
  (define lookup (assoc key hashlist))
  (if lookup
     (when (not (equal? lookup val))
       (vector-set! table index
                    (cons (list key val)
                         (remove lookup hashlist)
                          )))
     ;; returns nuthing
       (vector-set! table index
                    (cons (list key val)
                          (lookup hashlist))
                    )
       ;; returns nuthing
       )
      )
;; see how this is the most optimal and beauty way to do tings.

(define (ht-remove table key)
(define index (modulo key (vector-length table)))
;(define hashlist (vector-ref table index))
(vector-set! table index empty)
  )

;;primitive build-in data types.

(define table (make-hash))
(hash-ref table 42 "not there")
;; checks if in table, if not return success