Commits

Stephen Tanner committed b4fbdb0

Fixed bitwise and recursive to not use arrarys and handle 0 search case

  • Participants
  • Parent commits 88edce8

Comments (0)

Files changed (17)

+################################################################################
+# Automatically-generated file. Do not edit!
+################################################################################
+
+-include ../makefile.init
+
+RM := rm -rf
+
+# All of the sources participating in the build are defined here
+-include sources.mk
+-include subdir.mk
+-include src/subdir.mk
+-include objects.mk
+
+ifneq ($(MAKECMDGOALS),clean)
+ifneq ($(strip $(C_DEPS)),)
+-include $(C_DEPS)
+endif
+endif
+
+-include ../makefile.defs
+
+# Add inputs and outputs from these tool invocations to the build variables 
+
+# All Target
+all: subc
+
+# Tool invocations
+subc: $(OBJS) $(USER_OBJS)
+	@echo 'Building target: $@'
+	@echo 'Invoking: GCC C Linker'
+	gcc  -o "subc" $(OBJS) $(USER_OBJS) $(LIBS)
+	@echo 'Finished building target: $@'
+	@echo ' '
+
+# Other Targets
+clean:
+	-$(RM) $(OBJS)$(C_DEPS)$(EXECUTABLES) subc
+	-@echo ' '
+
+.PHONY: all clean dependents
+.SECONDARY:
+
+-include ../makefile.targets
+################################################################################
+# Automatically-generated file. Do not edit!
+################################################################################
+
+USER_OBJS :=
+
+LIBS :=
+
+################################################################################
+# Automatically-generated file. Do not edit!
+################################################################################
+
+O_SRCS := 
+C_SRCS := 
+S_UPPER_SRCS := 
+OBJ_SRCS := 
+ASM_SRCS := 
+OBJS := 
+C_DEPS := 
+EXECUTABLES := 
+
+# Every subdirectory with source files must be described here
+SUBDIRS := \
+src \
+

Debug/src/array.d

+src/array.d: ../src/array.c ../src/substring.h
+
+../src/substring.h:

Debug/src/array.o

Binary file added.

Debug/src/bitwise.d

+src/bitwise.d: ../src/bitwise.c ../src/substring.h
+
+../src/substring.h:

Debug/src/bitwise.o

Binary file added.
+src/main.d: ../src/main.c ../src/substring.h
+
+../src/substring.h:

Debug/src/main.o

Binary file added.

Debug/src/recursive.d

+src/recursive.d: ../src/recursive.c ../src/substring.h
+
+../src/substring.h:

Debug/src/recursive.o

Binary file added.

Debug/src/subdir.mk

+################################################################################
+# Automatically-generated file. Do not edit!
+################################################################################
+
+# Add inputs and outputs from these tool invocations to the build variables 
+C_SRCS += \
+../src/array.c \
+../src/bitwise.c \
+../src/main.c \
+../src/recursive.c 
+
+OBJS += \
+./src/array.o \
+./src/bitwise.o \
+./src/main.o \
+./src/recursive.o 
+
+C_DEPS += \
+./src/array.d \
+./src/bitwise.d \
+./src/main.d \
+./src/recursive.d 
+
+
+# Each subdirectory must supply rules for building sources it contributes
+src/%.o: ../src/%.c
+	@echo 'Building file: $<'
+	@echo 'Invoking: GCC C Compiler'
+	gcc -O0 -g3 -Wall -c -fmessage-length=0 -MMD -MP -MF"$(@:%.o=%.d)" -MT"$(@:%.o=%.d)" -o "$@" "$<"
+	@echo 'Finished building: $<'
+	@echo ' '
+
+

Debug/subc

Binary file added.
+import java.io.File;
+import java.io.IOException;
+import java.util.Scanner;
+
+public class Parser 
+{
+	public static void main(String[] args)
+	{
+		// Set up Scanner
+		Scanner in = null;
+		if (args.length == 1) {
+			try {
+				in = new Scanner(new File(args[0]));
+			}
+			catch (IOException e) {
+				System.err.printf("Error: invalid input file\n");
+				System.exit(-1);
+			}
+		}
+		else {
+				in = new Scanner(System.in);
+		}
+	
+		// Get output for bitwise, array, and recursive
+		String type;
+		for (int i = 0; i < 3; i++) {
+			
+			String line = null;
+			try {
+				while ((line = in.nextLine().toLowerCase()).length() == 0);
+			}
+			catch (Exception e) {
+				System.err.println("Error: expected more output");
+				System.exit(-1);
+			}
+			
+			// Check name of function
+			type = line.substring(0, line.indexOf(":"));
+			if (!(type.equals("bitwise") || type.equals("array") || type.equals("recursive"))) {
+				System.err.printf("Error: Unrecognized function: %s\n", type);
+				System.exit(-1);
+			}
+			
+			// Check for no match found case
+			if (line.indexOf("no match found") >= 0) {
+				System.out.printf("Found no %s matches\n", type);
+			}
+			
+			// Check for match found case; print rest of results
+			else if (line.indexOf("match found") >= 0) {
+				get_info(type, in);
+			}
+			
+			// Error if unrecognized
+			else {
+				System.err.printf("Error: Unrecognized line: %s\n", line);
+				System.exit(-1);
+			}
+		}
+	}
+	
+	/** 
+	 * Attempt to get the remaining two lines of input containing information
+	 * about the number of matches and their positions.
+	 */
+	private static void get_info(String type, Scanner in)
+	{
+		for (int i = 0; i < 2; i++) {
+			int match;
+			String line;
+			
+			// Get next line
+			while ((line = in.nextLine()).length() == 0);
+			
+			// Check for expected function type
+			line = line.toLowerCase();
+			if (line.indexOf(type) != 0) {
+				System.err.printf("Error: Expected function type %s\n", type);
+				System.exit(-1);
+			}
+			
+			// Check for line containing the number of matches
+			if ((match = line.indexOf("matches:")) >= 0) {
+				line = line.substring(match + 8).trim();	
+				System.out.printf("Found %s number of matches: %d\n", type, Integer.parseInt(line));
+			}
+			
+			// Check for line containing all of the positions
+			else if ((match = line.indexOf("positions:")) >= 0) {
+				for (String s : line.substring(match + 10).trim().split(",")) {
+					System.out.printf("Found %s match: %d\n", type, Integer.parseInt(s.trim()));
+				}
+			}
+			
+			// Error if unrecognized
+			else {
+				System.err.printf("Error: Unrecognized line: %s\n", line);
+				System.exit(-1);
+			}
+		}
+		
+		System.out.println("");
+	}
+}
 
 bool bitwise_find_substring (int first_int, int second_int) {
 
-    int matches[SIZE];
+    //int matches[SIZE];
     int m_index = 0;
+    bool found = false;
     int i;
+    int firstbit = 0;
     for (i = 0; i < SIZE; i++) {
-        matches[i] = 0;
+        //matches[i] = 0;
     }
     int length = 0;
     int mask = 0;
             break;
         }
     }
+    //handle the 0 search
+    if (!length && !mask) {
+        length = mask = 1;
+    }
+    //Check first int for first bit
+    for (i = SIZE - 1; i >= 0; i--) {
+        int check = first_int & (1 << i);
+        if (check) {
+            //Congrats, you found a bit set to 1
+            firstbit = i + 1;
+            break;
+        }
+    }
     //printf("%d", mask);
-    int shift = SIZE - length;
+    int shift = firstbit - length;
     for (i  = 0; i <= shift; i++) {
 
         int masked = first_int & mask;
             //Ok, so you have found a match of bits,
             //Now you need to save the position of the left most bit
             //aka (length + i)
-            matches[m_index] = length + i;
+            if (!found) {
+                printf("Bitwise: Match Found\n\n");
+                printf("Bitwise: starting bit positions: ");
+                printf("%d", (length+i));
+                found = true;
+            }
+            else {
+                printf(",%d", (length+i));
+
+            }
+            //matches[m_index] = length + i;
             m_index++;
         }
+
         //Shift both mask position, and second integer.
         //This will keep the two sets of bits aligned.
         mask = (mask << 1);
         second_int = (second_int << 1);
     }
-
-    if (!matches[0]) {
+    if (found) {
+                printf("\n\n");
+                printf("Bitwise: number of matches: %d\n\n\n",m_index);
+                return true;
+    }
+    else {
         return false;
     }
-    else {
-        printf("Bitwise: Match Found\n\n");
-        printf("Bitwise: number of matches: %d\n\n",m_index);
-        printf("Bitwise: starting bit positions: ");
-        for (i = 0; i < SIZE; i++) {
-                if (!matches[i]) {
-                    break;
-                }
-                printf("%d", matches[i]);
-                if (matches[i + 1]) {
-                    printf(",");
-                }
-            }
-        printf("\n\n\n");
-        return true;
-    }
+
+//    if (!matches[0]) {
+//        return false;
+//    }
+//    else {
+//        printf("Bitwise: Match Found\n\n");
+//        printf("Bitwise: number of matches: %d\n\n",m_index);
+//        printf("Bitwise: starting bit positions: ");
+//        for (i = 0; i < SIZE; i++) {
+//                if (!matches[i]) {
+//                    break;
+//                }
+//                printf("%d", matches[i]);
+//                if (matches[i + 1]) {
+//                    printf(",");
+//                }
+//            }
+//        printf("\n\n\n");
+//        return true;
+//    }
     //printf("%d", masked);
     //printf("First number is: %d", first_int);
     //Integers can only be 32bits, so the longest binary version is 32
     printf("What is the second integer?: ");
     scanf("%d", &second_int);
     printf("\n");
+    if (first_int < 0 || second_int < 0) {
+        printf("No negative numbers please... \n -_- \n");
+        return 1;
+    }
     bool bitwise = bitwise_find_substring(first_int, second_int);
     if (!bitwise) {
         printf("Bitwise: No Match Found\n\n");
 
 
 
-    return EXIT_SUCCESS;
+    return 0;
 }
 
 
 
 static int SIZE = 32;
 
-bool find_subs(int matches[], int *match_count, int shifts_left, int first_int, int second_int, int mask);
+bool find_subs(bool found, int *match_count, int shifts_left, int first_int, int second_int, int mask, int firstbit);
 
 bool recursive_find_substring (int first_int, int second_int) {
 
-        int matches[SIZE];
+
         int match_count = 0;
+        bool found = false;
+        int firstbit = 0;
         int i;
-        for (i = 0; i < SIZE; i++) {
-            matches[i] = 0;
-        }
+
+
         int length = 0;
         int mask = 0;
         for (i = SIZE - 1; i >= 0; i--) {
                 break;
             }
         }
-        int shifts_left = SIZE - length;
-        bool sub_found = find_subs(matches, &match_count, shifts_left, first_int, second_int, mask);
+        //handle the 0 search
+        if (!length && !mask) {
+            length = mask = 1;
+        }
+        //Check first int for first bit
+        for (i = SIZE - 1; i >= 0; i--) {
+            int check = first_int & (1 << i);
+            if (check) {
+                //Congrats, you found a bit set to 1
+                firstbit = i + 1;
+                break;
+            }
+        }
 
-        if (!sub_found) {
+
+
+
+
+
+
+        int shifts_left = firstbit - length;
+        bool sub_found = find_subs(found, &match_count, shifts_left, first_int, second_int, mask, firstbit);
+
+        if (sub_found) {
+            printf("\n\n");
+            printf("Recursive: number of matches: %d\n\n\n",match_count);
+            return true;
+        }
+        else {
             return false;
         }
-        else {
-            printf("Recursive: Match Found\n\n");
-            printf("Recursive: number of matches: %d\n\n",match_count);
-            printf("Recursive: starting bit positions: ");
-            for (i = 0; i < SIZE; i++) {
-                if (!matches[i]) {
-                    break;
-                }
-                printf("%d", matches[i]);
-                if (matches[i + 1]) {
-                    printf(",");
-                }
-            }
-            printf("\n\n\n");
-            return true;
-        }
+
 }
 
 
-bool find_subs(int matches[], int *match_count, int shifts_left, int first_int, int second_int, int mask) {
+bool find_subs(bool found, int *match_count, int shifts_left, int first_int, int second_int, int mask, int firstbit) {
 
     //Handle the base case
     if (shifts_left == 0) {
     //If shifts_left > 0
     int masked = (first_int & mask);
     if (masked == second_int) {
-        matches[*match_count] = SIZE - shifts_left;
+        //matches[*match_count] = SIZE - shifts_left;
+        if (!found) {
+            printf("Recursive: Match Found\n\n");
+            printf("Recursive: starting bit positions: ");
+            printf("%d", (firstbit - shifts_left));
+            found = true;
+        }
+        else {
+            printf(",%d", (firstbit - shifts_left));
+
+        }
         *match_count = *match_count + 1;
     }
     mask = (mask << 1);
     second_int = (second_int << 1);
     shifts_left--;
-    return find_subs(matches, match_count, shifts_left, first_int, second_int, mask);
+    return find_subs(found, match_count, shifts_left, first_int, second_int, mask, firstbit);
 }