Initial code

9 files changed, 402 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..40a1124
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,67 @@
+
+# Created by https://www.gitignore.io/api/vim,linux,osx,cmake
+
+### Vim ###
+# swap
+[._]*.s[a-w][a-z]
+[._]s[a-w][a-z]
+# session
+Session.vim
+# temporary
+.netrwhist
+*~
+# auto-generated tag files
+tags
+
+
+### Linux ###
+*~
+
+# temporary files which can be created if a process still has a handle open of a deleted file
+.fuse_hidden*
+
+# KDE directory preferences
+.directory
+
+# Linux trash folder which might appear on any partition or disk
+.Trash-*
+
+
+### OSX ###
+*.DS_Store
+.AppleDouble
+.LSOverride
+
+# Icon must end with two \r
+Icon


+
+# Thumbnails
+._*
+
+# Files that might appear in the root of a volume
+.DocumentRevisions-V100
+.fseventsd
+.Spotlight-V100
+.TemporaryItems
+.Trashes
+.VolumeIcon.icns
+.com.apple.timemachine.donotpresent
+
+# Directories potentially created on remote AFP share
+.AppleDB
+.AppleDesktop
+Network Trash Folder
+Temporary Items
+.apdisk
+
+
+### CMake ###
+CMakeCache.txt
+CMakeFiles
+CMakeScripts
+Makefile
+cmake_install.cmake
+install_manifest.txt
+CTestTestfile.cmake
+_build
+_install
diff --git a/CMakeLists.txt b/CMakeLists.txt
new file mode 100644
index 0000000..fa1ad6c
--- /dev/null
+++ b/CMakeLists.txt
@@ -0,0 +1,61 @@
+################################################################################
+# Cmake directives
+################################################################################
+cmake_minimum_required(VERSION 2.8)
+
+################################################################################
+# Project information
+################################################################################
+project(libuknapsack)
+
+set(PROJECT_MAJOR_VERSION 1)
+set(PROJECT_MINOR_VERSION 0)
+set(PROJECT_PATCH_VERSION 0)
+set(PROJECT_VERSION ${PROJECT_MAJOR_VERSION}.${PROJECT_MINOR_VERSION}.${PROJECT_PATCH_VERSION})
+
+################################################################################
+# Dependencies
+################################################################################
+
+################################################################################
+# CMake
+################################################################################
+set(C_FLAGS_WARNING "-Wall -pedantic")
+set(C_CXX_FLAGS_DEFAULT "${C_FLAGS_WARNING} -O2")
+
+set(CMAKE_C_FLAGS "${C_CXX_FLAGS_DEFAULT} ${CMAKE_C_FLAGS}")
+set(CMAKE_C_FLAGS_DEBUG   "${CMAKE_C_FLAGS} -O0 -g -DDEBUG=1")
+set(CMAKE_C_FLAGS_RELEASE "${CMAKE_C_FLAGS}")
+set(CMAKE_C_FLAGS_RELWITHDEBINFO "${CMAKE_C_FLAGS_RELEASE} -g -DDEBUG=1")
+
+set(CMAKE_BUILD_TYPE Release CACHE STRING "default to Release")
+
+set(CMAKE_INSTALL_PREFIX ${CMAKE_CURRENT_SOURCE_DIR}/_install)
+
+################################################################################
+# Files and install
+################################################################################
+set(INCLUDE_DIR ${CMAKE_CURRENT_SOURCE_DIR}/include)
+set(INCLUDE_FILES
+  ${INCLUDE_DIR}/nem_ull.h
+  ${INCLUDE_DIR}/structs.h
+  ${INCLUDE_DIR}/common.h
+)
+
+set(SRC_DIR ${CMAKE_CURRENT_SOURCE_DIR}/src)
+set(SRC_FILES
+  ${SRC_DIR}/nem_ull.c
+  ${SRC_DIR}/common.c
+)
+
+set(MAIN_SRC_DIR ${CMAKE_CURRENT_SOURCE_DIR}/src/main)
+
+include_directories (${INCLUDE_DIR})
+
+add_library(nem_ull_lib STATIC ${SRC_FILES})
+add_executable(nem_ull ${MAIN_SRC_DIR}/nem_ull.c)
+target_link_libraries(nem_ull nem_ull_lib)
+
+install(TARGETS nem_ull DESTINATION bin)
+install(TARGETS nem_ull_lib DESTINATION lib)
+install(FILES ${INCLUDE_FILES} DESTINATION include)
diff --git a/README.md b/README.md
index 1e4bbb9..57bdad8 100644
--- a/README.md
+++ b/README.md
@@ -6,3 +6,11 @@ Library with various solutions (optimal and approximations) for the unconstraine
 
 The **unconstrained knapsack problem** is a version of the knapsack problem where there is no constraint on the weight.
 Therefore, at the very least we have a bi-objective problem where we try to minimize the weight and maximize the profit. 
+
+### Building the project
+
+1. Create a `_build` directory: `mkdir _build`
+2. Go to the `_build` directory: `cd _build`
+3. Run cmake: `cmake ..`
+4. Run make install: `make install`
+5. Library will be located on the `_install` folder, to go there: `cd ../_install` if you are still on the `_build` folder
diff --git a/include/common.h b/include/common.h
new file mode 100644
index 0000000..c61ac4d
--- /dev/null
+++ b/include/common.h
@@ -0,0 +1,19 @@
+#ifndef _COMMON_H
+#define _COMMON_H
+
+#include "structs.h"
+
+#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
+#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
+
+struct data * input(char[]);
+void print_data(struct data *);
+void print_front(struct front_item *);
+void free_data(struct data *);
+void free_front(struct front_item *);
+struct front_item * new_front_item(double,  double, struct front_item *, struct front_item *);
+double dist_items(struct item *, struct item *);
+int len_front(struct front_item *);
+int cmp_items_ratio(const void * a, const void * b);
+
+#endif
diff --git a/include/nem_ull.h b/include/nem_ull.h
new file mode 100644
index 0000000..fd1b829
--- /dev/null
+++ b/include/nem_ull.h
@@ -0,0 +1,9 @@
+#ifndef _NEM_ULL_H
+#define _NEM_ULL_H
+
+#include "structs.h"
+
+struct front_item * nem_ull(struct data *);
+struct front_item * nem_ull_step(struct front_item *, struct data *, int);
+
+#endif
diff --git a/include/structs.h b/include/structs.h
new file mode 100644
index 0000000..cb1bca9
--- /dev/null
+++ b/include/structs.h
@@ -0,0 +1,20 @@
+#ifndef _STRUCTS_H
+#define _STRUCTS_H
+struct item {
+	double p;
+	double w;
+};
+
+struct data {
+	long int N;
+	struct item * items;
+	double allp;
+	double allw;
+};
+
+struct front_item {
+	struct item i;
+	struct front_item * next;
+	struct front_item * prev;
+};
+#endif
diff --git a/src/common.c b/src/common.c
new file mode 100644
index 0000000..92bd467
--- /dev/null
+++ b/src/common.c
@@ -0,0 +1,88 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include "structs.h"
+#include "common.h"
+
+struct data * input(char fp[]){
+	int i,j;
+	FILE *f;
+	struct data * d = (struct data *)malloc(sizeof(struct data));
+
+	f = fopen(fp,"r");
+	j = fscanf(f,"%ld",&(d->N));
+	if(j!=1){
+		printf("Error reading data\n");
+		exit(0);
+	}
+	d->items = (struct item *)malloc(d->N*sizeof(struct item));
+	for(i=0;i<d->N;++i){
+		j = fscanf(f,"%lf %lf",&(d->items[i].p),&(d->items[i].w));
+		d->allp += d->items[i].p;
+		d->allw += d->items[i].w;
+	}
+
+	fclose(f);
+	return d;
+}
+
+int cmp_items_ratio(const void * a, const void * b){
+  struct item c = *(struct item *)a;
+  struct item d = *(struct item *)b;
+  if(c.p / c.w < d.p / d.w){
+    return 1;
+  }
+	return -1;
+}
+
+void print_data(struct data * d){
+	int i;
+	printf("### PRINTING DATA - BEGINNING ###\n");
+	printf("N:\t%ld\n\n",d->N);
+	printf("Profit\tWeight\n");
+	for(i=0;i<d->N;++i){
+		printf("%.02f\t%.02f\n",d->items[i].p,d->items[i].w);
+	}
+	printf("### PRINTING DATA - ENDING ###\n");
+}
+
+void print_front(struct front_item * b){
+	while(b!=NULL){
+		printf("%.02f\t%.02f\n",b->i.p,b->i.w);
+		b = b->next;
+	}
+}
+
+void free_data(struct data * d){
+	free(d->items);
+	free(d);
+}
+
+void free_front(struct front_item * b){
+	struct front_item * tmp;
+	for(;b!=NULL;){
+		tmp = b;
+		b = b->next;
+		free(tmp);
+	}
+}
+
+struct front_item * new_front_item(double p, double w, struct front_item * prev, struct front_item * next){
+	struct front_item * f = (struct front_item *)malloc(sizeof(struct front_item));
+	f->i.p = p;
+	f->i.w = w;
+	f->next = next;
+	f->prev = prev;
+
+	return f;
+}
+
+double dist_items(struct item * a, struct item * b){
+	return sqrt((a->p - b->p)*(a->p - b->p) + (a->w - b->w)*(a->w - b->w));
+}
+
+int len_front(struct front_item * f){
+	int N;
+	for(N=0;f!=NULL;f=f->next,N++);
+	return N;
+}
diff --git a/src/main/nem_ull.c b/src/main/nem_ull.c
new file mode 100644
index 0000000..1bf183a
--- /dev/null
+++ b/src/main/nem_ull.c
@@ -0,0 +1,31 @@
+#include <stdio.h>
+#include <time.h>
+#include "common.h"
+#include "structs.h"
+#include "nem_ull.h"
+
+int main(int argc, char * argv[]){
+	struct data * d;
+	struct front_item * b;
+
+	if(argc!=2){
+		printf("Wrong number of arguments!\n");
+		printf("Example usage: %s data_file\n",argv[0]);
+		return 0;
+	}
+
+	d = input(argv[1]);
+	
+  clock_t t = clock();
+	b = nem_ull(d);
+
+	t = clock() - t;
+	printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b));
+
+	//print_front(b);
+
+	free_front(b);
+	free_data(d);
+
+	return 0;
+}
diff --git a/src/nem_ull.c b/src/nem_ull.c
new file mode 100644
index 0000000..9a6b328
--- /dev/null
+++ b/src/nem_ull.c
@@ -0,0 +1,99 @@
+#include <stdlib.h>
+#include "nem_ull.h"
+#include "structs.h"
+#include "common.h"
+
+struct front_item * nem_ull(struct data * d){
+	struct front_item * begin;
+	int i;
+
+	begin = new_front_item(0,0,NULL,NULL);
+
+	for(i=0;i<d->N;++i){
+		begin = nem_ull_step(begin,d,i);
+	}
+
+	return begin;
+}
+
+struct front_item * nem_ull_step(struct front_item * b, struct data * d, int it){
+	unsigned long int i,l0t,l1t,n;
+	double pmax;
+	struct item * l0;
+	struct item * l1;
+	struct front_item * p = b;
+
+	for(n=0;p!=NULL;p=p->next,++n);
+	p = b;
+
+	l0 = (struct item *)malloc(n*sizeof(struct item));
+	l1 = (struct item *)malloc(n*sizeof(struct item));
+
+	for(i=0;i<n;++i){
+		l0[i].p=p->i.p;
+		l0[i].w=p->i.w;
+
+		l1[i].p=p->i.p + d->items[it].p;
+		l1[i].w=p->i.w + d->items[it].w;
+
+		b = p;
+		p = p->next;
+		free(b);
+	}
+
+	pmax = -1;
+	l0t = 0;
+	l1t = 0;
+	p = new_front_item(0,0,NULL,NULL);
+
+	while(1){
+		for(;l0t<n;++l0t){
+			if(l0[l0t].p > pmax){
+				break;
+			}
+		}
+
+		for(;l1t<n;++l1t){
+			if(l1[l1t].p > pmax){
+				break;
+			}
+		}
+
+		if(l0t == n){
+			for(;l1t<n;++l1t){
+				p = new_front_item(l1[l1t].p, l1[l1t].w, p, NULL);
+				p->prev->next = p;
+			}
+			break;
+		}
+
+		if(l1t == n){
+			for(;l0t<n;++l0t){
+				p = new_front_item(l0[l0t].p, l0[l0t].w, p, NULL);
+				p->prev->next = p;
+			}
+			break;
+		}
+
+		if((l0[l0t].w < l1[l1t].w) || ((l0[l0t].w == l1[l1t].w) && (l0[l0t].p > l1[l1t].p))){
+			p = new_front_item(l0[l0t].p, l0[l0t].w , p, NULL);
+			p->prev->next = p;
+			pmax = l0[l0t].p;
+			++l0t;
+		} else {
+			p = new_front_item(l1[l1t].p, l1[l1t].w , p, NULL);
+			p->prev->next = p;
+			pmax = l1[l1t].p;
+			++l1t;
+		}
+	}
+
+	free(l0);
+	free(l1);
+
+	for(;p->prev!=NULL;p=p->prev);
+	p=p->next;
+	free(p->prev);
+	p->prev=NULL;
+	return p;
+}