반응형
관련글
A star 최단 경로 알고리즘 (Part 1 원리) (tistory.com)
서론
전 포스트에서 경로 찾기 알고리즘에 대해 알아보았습니다.
A star 알고리즘은 탐색한 위치들의 집합 closeList, 근처에 있으면서 탐색할 수 있는 위치들의 집합 openList이 있었습니다. 또한 F, G, H 값을 기반으로 다음으로 탐색할 위치를 선정했었습니다.
F는 현재 지나온 위치들로 최종 위치로 이동할 때 예측되는 거리 값,
G는 지금까지의 거리 값,
H는 현 위치에서 목적지까지 예측되는 거리 값이었습니다.
여기서 H는 휴리스틱이라고 불립니다.
이번 포스트에서는 제가 만든 헤더파일을 소개하고, 그 헤더파일의 목적, 내부 변수들과 함수들 그리고 위의 개념들이 어떻게 표현되었는지 알아보겠습니다.
type.h
error.h
location.h
maze.h
node.h
nodelist.h
참고 자료
최단 경로 탐색 – A* 알고리즘 – GIS Developer
C 언어 코딩 도장: 74.0 연결 리스트 구현하기 (dojang.io)
반응형
type.h
더보기
/*
(Ko) Copyright 2021. 박광렬 all rights reserved.
(En) Copyright 2021. Kwangryeol Park all rights reserved.
파일 명: type.h
작성자: 박광렬
연락처: pkr7098@gmail.com
생성 날짜: 2021-09-24 (YYYY-MM-DD)
설명:
프로그램에서 사용될 자료형, 데이터 밑 관련 기능
연락 방법: pkr7098@gmail.com으로 메일 보내기
제목: (본인 이름), (목적), (소속), (type.h)
내용: 구체적인 사용 목적, 수정할 계획이 있는지, 어디에서 사용할 프로그램인지(ex ??? 전시회에서 ??? 로봇에 사용될 프로그램입니다.)
*/
#ifndef _type_h
#define _type_h
typedef char int8_t;
typedef unsigned char uint8_t;
typedef short int16_t;
typedef unsigned short uint16_t;
typedef int int32_t;
typedef unsigned int uint32_t;
#define MAX_UINT8 255
#define MIN_UINT8 0
#define MAX_INT8 127
#define MIN_INT8 -128
#define MAX_UINT16 65535
#define MIN_UINT16 0
#define MAX_INT16 32767
#define MIN_INT16 -32768
#define MAX_UINT32 4294967295
#define MIN_UINT32 0
#define MAX_INT32 2147483647
#define MIN_INT32 -2147483648
#endif목적
type.h는 astar를 구현할 때 필요한 자료형을 지정해 놓은 파일입니다. 각각의 자료형의 bit 수를 파악하기 위해 생성되었습니다.
int8_t는 부호 있는 8 비트 자료형
uint8_t는 부호 없는 8 비트 자료형
이런 형식입니다.
MAX_INT8, MIN_INT8 등의 값은 해당 자료형이 최대한으로 표현할 수 있는 최대의 범위를 나타냅니다.
error.h
더보기
/*
(Ko) Copyright 2021. 박광렬 all rights reserved.
(En) Copyright 2021. Kwangryeol Park all rights reserved.
파일 명: error.h
작성자: 박광렬
연락처: pkr7098@gmail.com
생성 날짜: 2021-09-24 (YYYY-MM-DD)
설명:
A star 알고리즘에서 사용될 에러 관련 데이터 및 기능
연락 방법: pkr7098@gmail.com으로 메일 보내기
제목: (본인 이름), (목적), (소속), (error.h)
내용: 구체적인 사용 목적, 수정할 계획이 있는지, 어디에서 사용할 프로그램인지(ex ??? 전시회에서 ??? 로봇에 사용될 프로그램입니다.)
*/
#ifndef _error_h
#define _error_h
#include <stdio.h>
#include <windows.h>
#include "type.h"
#define ERROR_NO 0
#define ERROR_MEMORY_NO (ERROR_NO + 1)
#define ERROR_MEMORY1 (ERROR_NO + 2)
#define ERROR_MEMORY2 (ERROR_NO + 3)
#define ERROR_MEMORY3 (ERROR_NO + 4)
#define ERROR_MEMORY4 (ERROR_NO + 5)
#define ERROR_MEMORY5 (ERROR_NO + 6)
#define ERROR_OBJECT_NO (ERROR_NO + 100 + 1)
#define ERROR_OBJECT_LIST_EXIST (ERROR_NO + 100 + 2)
#define ERROR_OBJECT_SEARCH (ERROR_NO + 100 + 3)
#define ERROR_OBJECT3 (ERROR_NO + 100 + 4)
#define ERROR_OBJECT4 (ERROR_NO + 100 + 5)
#define ERROR_OBJECT5 (ERROR_NO + 100 + 6)
#define ERROR_OBJECT_LIST_EMPTY (ERROR_NO + 100 + 7)
#define ERROR_OVERFLOW_INT8 (ERROR_NO + 200 + 1)
#define ERROR_OVERFLOW_INT16 (ERROR_NO + 200 + 2)
#define ERROR_OVERFLOW_INT32 (ERROR_NO + 200 + 3)
#define ERROR_OVERFLOW_UINT8 (ERROR_NO + 200 + 4)
#define ERROR_OVERFLOW_UINT16 (ERROR_NO + 200 + 5)
#define ERROR_OVERFLOW_UINT32 (ERROR_NO + 200 + 6)
#define ERROR_UNDERFLOW_INT8 (ERROR_NO + 200 + 7)
#define ERROR_UNDERFLOW_INT16 (ERROR_NO + 200 + 8)
#define ERROR_UNDERFLOW_INT32 (ERROR_NO + 200 + 9)
#define ERROR_UNDERFLOW_UINT8 (ERROR_NO + 200 + 10)
#define ERROR_UNDERFLOW_UINT16 (ERROR_NO + 200 + 11)
#define ERROR_UNDERFLOW_UINT32 (ERROR_NO + 200 + 12)
#define ERROR_ROUTE_NO (ERROR_NO + 300 + 1)
#define ERROR_TYPE int16_t
#define ERROR_HIGHLIGHT true
#if ERROR_HIGHLIGHT == true // Do not modify
#define ERROR_HIGHLIGHT_BLACK 0
#define ERROR_HIGHLIGHT_BLUE 1
#define ERROR_HIGHLIGHT_GREEN 2
#define ERROR_HIGHLIGHT_AQUA 3
#define ERROR_HIGHLIGHT_RED 4
#define ERROR_HIGHLIGHT_PURPLE 5
#define ERROR_HIGHLIGHT_YELLOW 6
#define ERROR_HIGHLIGHT_WHITE 7
#define ERROR_HIGHLIGHT_GRAY 8
#define ERROR_HIGHLIGHT_LIGHT_BLUE 9
#define ERROR_HIGHLIGHT_LIGHT_GREEN 0x0A
#define ERROR_HIGHLIGHT_LIGHT_AQUA 0x0B
#define ERROR_HIGHLIGHT_LIGHT_RED 0x0C
#define ERROR_HIGHLIGHT_LIGHT_PURPLE 0x0D
#define ERROR_HIGHLIGHT_LIGHT_YELLOW 0x0E
#define ERROR_HIGHLIGHT_BRIGHT_WHITE 0x0F
#endif
#define ERROR_HIGHLIGHT_COLOR ERROR_HIGHLIGHT_LIGHT_RED
#define ERROR_HIGHLIGHT_CONTENTS_COLOR ERROR_HIGHLIGHT_LIGHT_YELLOW
#define ERROR_HIGHLIGHT_SOLUTION_COLOR ERROR_HIGHLIGHT_LIGHT_AQUA
// ================================================================================
// Print the error
void printError(ERROR_TYPE error, char *location, char *message);
void printError(ERROR_TYPE error, char *location, char *message, char *solution);
void printError(ERROR_TYPE error, const char *location, const char *message);
void printError(ERROR_TYPE error, const char *location, const char *message, const char *solution);
// ================================================================================
#if ERROR_HIGHLIGHT == true
void printError(ERROR_TYPE error, char *location, char *message)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_COLOR);
printf("% 4d ERROR\r\n", error);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_CONTENTS_COLOR);
printf("\tLocation:\t%s\r\n", location);
printf("\tMessage :\t%s\r\n", message);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_WHITE);
}
void printError(ERROR_TYPE error, char *location, char *message, char *solution)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_COLOR);
printf("% 4d ERROR\r\n", error);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_CONTENTS_COLOR);
printf("\tLocation:\t%s\r\n", location);
printf("\tMessage :\t%s\r\n", message);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_SOLUTION_COLOR);
printf("\tSolution:\t%s\r\n", solution);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_WHITE);
}
void printError(ERROR_TYPE error, const char *location, const char *message)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_COLOR);
printf("% 4d ERROR\r\n", error);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_CONTENTS_COLOR);
printf("\tLocation:\t%s\r\n", location);
printf("\tMessage :\t%s\r\n", message);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_WHITE);
}
void printError(ERROR_TYPE error, const char *location, const char *message, const char *solution)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_COLOR);
printf("% 4d ERROR\r\n", error);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_CONTENTS_COLOR);
printf("\tLocation:\t%s\r\n", location);
printf("\tMessage :\t%s\r\n", message);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_SOLUTION_COLOR);
printf("\tSolution:\t%s\r\n", solution);
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), ERROR_HIGHLIGHT_WHITE);
}
#else
void printError(ERROR_TYPE error, char *location, char *message)
{
printf("% 4d ERROR\r\n", error);
printf("\tLocation:\t%s\r\n", location);
printf("\tMessage :\t%s\r\n", message);
}
void printError(ERROR_TYPE error, char *location, char *message, const char *solution)
{
printf("% 4d ERROR\r\n", error);
printf("\tLocation:\t%s\r\n", location);
printf("\tMessage :\t%s\r\n", message);
printf("\tSolution:\t%s\r\n", solution);
}
void printError(ERROR_TYPE error, const char *location, const char *message)
{
printf("% 4d ERROR\r\n", error);
printf("\tLocation:\t%s\r\n", location);
printf("\tMessage :\t%s\r\n", message);
}
void printError(ERROR_TYPE error, const char *location, const char *message, const char *solution)
{
printf("% 4d ERROR\r\n", error);
printf("\tLocation:\t%s\r\n", location);
printf("\tMessage :\t%s\r\n", message);
printf("\tSolution:\t%s\r\n", solution);
}
#endif
#endif
목적
에러와 관련된 처리를 하기 위함입니다.
보다 나은 프로그램을 위해서는 에러가 발생했을 때, 이를 처리하는 코드를 넣는 것이 중요합니다. 가령 0으로 나누는 상황을 미리 감지하여 에러가 발생했다고 알려주는 것이죠. 또 다른 예는 메모리가 부족하는 등의 상황에서 에러를 발생시킬 수 있습니다.
define으로 정의된 것은 흔히 Error code라고 불리우는 것들입니다.
59번째 줄에 있는 ERROR_TYPE은 Error code의 자료형입니다. 여기서는 int16_t로 선언되어 있습니다.
printError는 에러를 출력해주는 함수입니다.
코드를 수행하다 에러가 발생될 수도 있는 지점에서 printError를 호출하고 매개변수로 Error code, 에러가 발생한 위치, 화면에 띄울 메시지, (추가적으로 해결 방법까지)를 전달하여 오류 내용을 보여줍니다.
location.h
더보기
/*
(Ko) Copyright 2021. 박광렬 all rights reserved.
(En) Copyright 2021. Kwangryeol Park all rights reserved.
파일 명: location.h
작성자: 박광렬
연락처: pkr7098@gmail.com
생성 날짜: 2021-09-24 (YYYY-MM-DD)
설명:
A star 알고리즘에서 사용될 좌표 구조체 선언 밑 관련 기능
연락 방법: pkr7098@gmail.com으로 메일 보내기
제목: (본인 이름), (목적), (소속), (location.h)
내용: 구체적인 사용 목적, 수정할 계획이 있는지, 어디에서 사용할 프로그램인지(ex ??? 전시회에서 ??? 로봇에 사용될 프로그램입니다.)
*/
#ifndef _location_h
#define _location_h
#define LOCATION_DEBUG true
#if LOCATION_DEBUG == true
#include <stdio.h>
#endif
#include "error.h"
#include "type.h"
#ifndef EQUAL
#define EQUAL 1
#endif
#ifndef UNEQUAL
#define UNEQUAL 0
#endif
#define DIR_U 0
#define DIR_D 1
#define DIR_L 2
#define DIR_R 3
#define DIR_UR 4
#define DIR_UL 5
#define DIR_DR 6
#define DIR_DL 7
// ================================================================================
typedef struct _Location
{
int8_t x, y;
} Location;
// ================================================================================
// Initiate the location variable by x and y
void init(Location *location, int8_t x, int8_t y, ERROR_TYPE *error);
// Initiate the location variable to x = 0 and y = 0
void init(Location *location, ERROR_TYPE *error);
// Judge the two locations are directing same coordinate
ERROR_TYPE isEqual(Location location1, Location location2);
ERROR_TYPE isEqual(Location *location1, Location *location2);
// Calculate the heuristic
int32_t heuristic(Location location1, Location location2);
int32_t heuristic(Location *location1, Location *location2, ERROR_TYPE *error);
// ================================================================================
void init(Location *location, int8_t x, int8_t y, ERROR_TYPE *error)
{
if (location == (Location *)0)
{
#if LOCATION_DEBUG == true
printError(ERROR_OBJECT_NO, "void init(Location *location, int8_t x, int8_t y, ERROR_TYPE *error)", "location is Null!!");
#endif
*error = ERROR_OBJECT_NO;
return;
}
location->x = x;
location->y = y;
}
void init(Location *location, ERROR_TYPE *error)
{
if (location == (Location *)0)
{
#if LOCATION_DEBUG == true
printError(ERROR_OBJECT_NO, "void init(Location *location)", "location is Null!!");
#endif
*error = ERROR_OBJECT_NO;
return;
}
init(location, 0, 0);
};
ERROR_TYPE isEqual(Location location1, Location location2)
{
if (location1.x == location2.x && location1.y == location2.y)
{
return EQUAL;
}
return UNEQUAL;
}
ERROR_TYPE isEqual(Location *location1, Location *location2)
{
if (location1->x == location2->x && location1->y == location2->y)
{
return EQUAL;
}
return UNEQUAL;
}
int32_t heuristic(Location location1, Location location2)
{
int16_t dx = location1.x - location2.x;
int16_t dy = location1.y - location2.y;
dx = (dx < 0) ? -dx : dx;
dy = (dy < 0) ? -dy : dy;
int32_t dM = (dx < dy) ? dy : dx;
int32_t dm = (dx > dy) ? dy : dx;
dM = dM - dm;
return dm * 3 + dM * 2;
}
int32_t heuristic(Location *location1, Location *location2, ERROR_TYPE *error)
{
if (location1 == (Location *)0 || location2 == (Location *)0)
{
#if LOCATION_DEBUG == true
printError(ERROR_OBJECT_NO, "int32_t heuristic(Location *location1, Location *location2, ERROR_TYPE *error)", "location1 or location2 is Null!!");
#endif
*error = ERROR_OBJECT_NO;
return -1;
}
int16_t dx = location1->x - location2->x;
int16_t dy = location1->y - location2->y;
dx = (dx < 0) ? -dx : dx;
dy = (dy < 0) ? -dy : dy;
int32_t dM = (dx < dy) ? dy : dx;
int32_t dm = (dx > dy) ? dy : dx;
*error = ERROR_NO;
return dm * 3 + dM * 2;
}
#endif
목표
각 지점들을 위치를 지정하고 처리하기 위함입니다.
Location은 구조체의 형태이며 맴버는 x, y가 있습니다.
init 함수는 Location 변수를 포인터 형태로 받아 초기화하는 함수입니다. x, y값을 지정하지 않으면 0으로 초기화합니다. error를 검출하는 코드가 존재합니다.
error 종류:
ERROR_OBJECT_NO: 인수로 받은 location이 Null입니다.
isEqual 함수는 두 개의 Location이 동일한 위치를 가리키고 있나를 확인하기 위한 함수입니다.
Call by value, Call by reference 둘 모두 가능합니다.
heuristic 함수는 앞서 말한 H값 즉, 휴리스틱 값을 계산하기 위함입니다. error를 검출하는 코드가 존재합니다.
maze.h
더보기
/*
(Ko) Copyright 2021. 박광렬 all rights reserved.
(En) Copyright 2021. Kwangryeol Park all rights reserved.
파일 명: maze.h
작성자: 박광렬
연락처: pkr7098@gmail.com
생성 날짜: 2021-09-24 (YYYY-MM-DD)
설명:
A star 알고리즘에서 사용될 Maze 구조체 선언
연락 방법: pkr7098@gmail.com으로 메일 보내기
제목: (본인 이름), (목적), (소속), (maze.h)
내용: 구체적인 사용 목적, 수정할 계획이 있는지, 어디에서 사용할 프로그램인지(ex ??? 전시회에서 ??? 로봇에 사용될 프로그램입니다.)
*/
#ifndef _maze_h
#define _maze_h
#include "type.h"
#define MAP_WIDTH 20
#define MAP_HEIGHT 20
typedef struct
{
char (*field)[MAP_WIDTH];
char obstacle;
char player;
} Maze;
#endif목적
미로를 표현하기 위한 구조체입니다.
MAP_WIDTH, MAP_HEIGHT로 맵의 최대 크기를 지정합니다.
맴버로는
맵의 정보가 저장될 field
장애물의 기호가 저장될 obstacle
현재 위치를 표시하기 위한 기호가 저장될 player가 있습니다.
node.h
더보기
/*
(Ko) Copyright 2021. 박광렬 all rights reserved.
(En) Copyright 2021. Kwangryeol Park all rights reserved.
파일 명: node.h
작성자: 박광렬
연락처: pkr7098@gmail.com
생성 날짜: 2021-09-24 (YYYY-MM-DD)
설명:
A star 알고리즘에서 사용될 Node 구조체 선언 및 관련 기능들
연락 방법: pkr7098@gmail.com으로 메일 보내기
제목: (본인 이름), (목적), (소속), (node.h)
내용: 구체적인 사용 목적, 수정할 계획이 있는지, 어디에서 사용할 프로그램인지(ex ??? 전시회에서 ??? 로봇에 사용될 프로그램입니다.)
*/
#ifndef _node_h
#define _node_h
#define NODE_DEBUG true
#if NODE_DEBUG == true
#include <stdio.h>
#endif
#include "error.h"
#include "location.h"
#include "type.h"
typedef struct _Node
{
Location location;
uint16_t f, g, h;
struct _Node *parent;
struct _Node *next;
char dir;
} Node;
// ================================================================================
// Create a node and initiate it.
Node *createNode(ERROR_TYPE *error);
// Initiate the correspond node.
Node *init(Node *node, ERROR_TYPE *error);
// Delete the current node.
void terminate(Node *node, ERROR_TYPE *error);
// ================================================================================
Node *createNode(ERROR_TYPE *error)
{
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == (Node *)0)
{
#if NODE_DEBUG == true
printError(ERROR_MEMORY_NO, "Node *createNode(ERROR_TYPE *error)", "There is no memory in heap section!!");
#endif
*error = ERROR_MEMORY_NO;
return (Node *)0;
}
*error = ERROR_NO;
return init(newNode, error);
}
Node *init(Node *node, ERROR_TYPE *error)
{
if (node == (Node *)0)
{
#if NODE_DEBUG == true
printError(ERROR_MEMORY_NO, "Node *init(Node *node, ERROR_TYPE *error)", "The node is Null!!");
#endif
*error = ERROR_OBJECT_NO;
return (Node *)0;
}
init(&(node->location));
node->f = 0;
node->g = 0;
node->h = 0;
node->parent = (Node *)0;
node->next = (Node *)0;
node->dir = 'X';
*error = ERROR_NO;
return node;
};
void terminate(Node *node, ERROR_TYPE *error)
{
if (node == (Node *)0)
{
#if NODE_DEBUG == true
printError(ERROR_OBJECT_NO, "void terminate(Node *node, ERROR_TYPE *error)", "The node is Null!!");
#endif
*error = ERROR_OBJECT_NO;
return;
}
*error = ERROR_NO;
free(node);
}
#endif목적
지점의 정보를 담고 있는 구조체 및 관련 함수들을 위함
각각의 지점들은 연결 리스트로 구성될 예정입니다.
Node 구조체는 지점의 정보를 담고 있으며, 맴버로는
위치 정보인 location
경로 정보인 f, g, h
지나온 방향을 저장하기 위한 dir
부모 노드를 저장하기 위한 parent
연결 리스트를 위한 next가 있습니다.
createNode는 노드를 새로 생성하는 함수입니다. malloc을 통해 메모리를 할당하며, 각종 에러를 검출합니다.
검출 가능한 에러:
ERROR_MEMORY_NO: 메모리가 부족합니다.
init은 인수로 받은 노드를 초기화합니다. 각종 에러를 검출합니다.
f = 0;
g = 0;
h = 0;
parent = null;
next = null
dir = 'X'
검출 가능한 에러:
ERROR_OBJECT_NO: 인수로 받은 node가 Null입니다.
terminate는 인수로 받은 노드를 지웁니다. 메모리를 풀어버리며, 각종 에러를 검출합니다.
검출 가능한 에러:
ERROR_OBJECT_NO: 인수로 받은 node가 null입니다.
nodelist.h
더보기
/*
(Ko) Copyright 2021. 박광렬 all rights reserved.
(En) Copyright 2021. Kwangryeol Park all rights reserved.
파일 명: nodelist.h
작성자: 박광렬
연락처: pkr7098@gmail.com
생성 날짜: 2021-09-24 (YYYY-MM-DD)
설명:
Node 구조체를 담을 수 있는 연결 리스트 형태의 List와 관련된 기능들
연락 방법: pkr7098@gmail.com으로 메일 보내기
제목: (본인 이름), (목적), (소속), (nodelist.h)
내용: 구체적인 사용 목적, 수정할 계획이 있는지, 어디에서 사용할 프로그램인지(ex ??? 전시회에서 ??? 로봇에 사용될 프로그램입니다.)
*/
#ifndef _nodelist_h
#define _nodelist_h
#define NODELIST_DEBUG true
#include <stdio.h>
#include <stdlib.h>
#include "error.h"
#include "location.h"
#include "node.h"
#include "type.h"
#ifndef EQUAL
#define EQUAL 1
#endif
#ifndef UNEQUAL
#define UNEQUAL 0
#endif
// ================================================================================
#define ITERATE_STATE_DONE 0
#define ITERATE_STATE_ONGOING 1
// ================================================================================
class NodeList
{
public:
// Identifier
// It create Null Node head and init all factors
NodeList(ERROR_TYPE *error);
// Add a node to link.
void add(Node *node, ERROR_TYPE *error);
// Remove the node from linked list.
// It remove the Node depends on its potiner.
void remove(Node *node, ERROR_TYPE *error);
// Remove the node from linked list.
// It remove the Node depends on its location.
void removeByLocation(Node *node, ERROR_TYPE *error);
// Pick the first node in linked list.
void pickFront(Node **node, ERROR_TYPE *error);
// Make the iterate function done
// It makes iterateState ITERATE_STATE_DONE
void iterateDone();
// Delete all pointers in the list
void terminate();
// Print all Node's information/
void print(ERROR_TYPE *error);
// Notify the current list is empty or not
// Return:
// 1: Empty
// 0: Not empty
int8_t isEmpty();
// For the iteration (while, for etc.)
// Return:
// 1: The iteration is ongoing
// 0: The iteration is done / An error occured
int8_t iterate(Node **node, ERROR_TYPE *error);
// For the iteration (while, for etc.)
// Return:
// 1: The iteration is ongoing
// 0: The iteration is done / An error occured
int8_t iterate(ERROR_TYPE *error);
// Search the node in the list depending on pointer
// Return:
// 1(EQUAL) : The iteration is ongoing
// 0(UNEQUAL) : The iteration is done / An error occured
int8_t search(Node **node, ERROR_TYPE *error);
// Search the node in the list depending on the location
// Return:
// 1(EQUAL) : The iteration is ongoing
// 0(UNEQUAL) : The iteration is done / An error occured
int8_t searchByLocation(Node **node, ERROR_TYPE *error);
private:
// The head of the linked list.
Node *head;
// An element which is used to iterate function
Node *iterateHead;
// The size of the linked list.
// The number of elements in the list.
uint16_t size;
// The state of iteration (ITERATE_STATE_DONE / ITERATE_STATE_ONGOING)
int8_t iterateState;
};
// ================================================================================
NodeList::NodeList(ERROR_TYPE *error)
{
// Allocate memory to head node.
head = createNode(error);
// Error checking.
// If head has no memory
if (*error != ERROR_NO)
{
#if NODELIST_DEBUG == true
printError(*error, "NodeList::NodeList(ERROR_TYPE *error)", "An error occured during create head node!!");
#endif
return;
}
//
// Clear the next of head.
head->next = (Node *)0;
// Reset the size.
size = 0;
// Reset the iterateState variable
iterateState = ITERATE_STATE_DONE;
// No error detection.
*error = ERROR_NO;
}
void NodeList::add(Node *node, ERROR_TYPE *error)
{
// Error checking.
// If head is empty.
if (head == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "void NodeList::add(Node *node, ERROR_TYPE *error)", "The head node is Null", "Please call NodeList() when creating the list");
#endif
*error = ERROR_OBJECT_NO;
return;
}
// If the source node is empty.
if (node == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "void NodeList::add(Node *node, ERROR_TYPE *error)", "The source node is Null");
#endif
*error = ERROR_OBJECT_NO;
return;
}
// If the node has been linked. -> (It should call murge not add)
if (node->next != (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_LIST_EXIST, "void NodeList::add(Node *node, ERROR_TYPE *error)", "The node has already linked to linked list", "Please unlink the node by calling remove() before call add() function");
#endif
*error = ERROR_OBJECT_LIST_EXIST;
return;
}
// If the list exceed the max size
if (size == MAX_UINT16)
{
#if NODELIST_DEBUG == true
printError(ERROR_OVERFLOW_INT16, "void NodeList::add(Node *node, ERROR_TYPE *error)", "The number of nodes in linked list exceeds the max size(int16) of the list");
#endif
*error = ERROR_OVERFLOW_INT16;
return;
}
//
/* Algorithm
node -> null
head -> ... -> node N -> null
head -> node -> ... -> node N -> null
*/
// Link the node.
node->next = head->next;
head->next = node;
// Increase the size.
size++;
// No error detection.
*error = ERROR_NO;
}
void NodeList::remove(Node *node, ERROR_TYPE *error)
{
// Error checking
// If head has not memory allocation.
if (head == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "void NodeList::remove(Node *node, ERROR_TYPE *error)", "The head node is Null", "Please call NodeList() when creating the list");
#endif
*error = ERROR_OBJECT_NO;
return;
}
// If the source node is null.
if (node == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "void NodeList::remove(Node *node, ERROR_TYPE *error)", "The source node is Null");
#endif
*error = ERROR_OBJECT_NO;
return;
}
// The object is empty
if (size == 0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_LIST_EMPTY, "void NodeList::remove(Node *node, ERROR_TYPE *error)", "The list is empty");
#endif
*error = ERROR_OBJECT_LIST_EMPTY;
return;
}
/* Algorithm
node -> node M -> ...
head -> ... -> node -> node M -> ...
head -> ... -> node M -> ...
*/
// Get first node.
Node *preNode = head;
Node *currentNode = head->next;
while (currentNode != (Node *)0)
{
if (currentNode == node)
{
preNode->next = currentNode->next;
currentNode->next = (Node *)0;
size--;
*error == ERROR_NO;
return;
}
preNode = currentNode;
currentNode = currentNode->next;
}
// Error
// The source is not exist in the linked list.
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_SEARCH, "void NodeList::remove(Node *node, ERROR_TYPE *error)", "The node is not in current list");
#endif
*error = ERROR_OBJECT_SEARCH;
return;
}
void NodeList::removeByLocation(Node *node, ERROR_TYPE *error)
{
// Error checking
// If head has not memory allocation.
if (head == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "void NodeList::removeByLocation(Node *node, ERROR_TYPE *error)", "The head node is Null", "Please call NodeList() when creating the list");
#endif
*error = ERROR_OBJECT_NO;
return;
}
// If the source node is null.
if (node == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "void NodeList::removeByLocation(Node *node, ERROR_TYPE *error)", "The source node is Null");
#endif
*error = ERROR_OBJECT_NO;
return;
}
// The object is empty
if (size == 0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_LIST_EMPTY, "void NodeList::removeByLocation(Node *node, ERROR_TYPE *error)", "The list is empty");
#endif
*error = ERROR_OBJECT_LIST_EMPTY;
return;
}
//
/* Algorithm
node -> node M -> ...
head -> ... -> node -> node M -> ...
head -> ... -> node M -> ...
*/
// Get first node.
Node *preNode = head;
Node *currentNode = head->next;
while (currentNode != (Node *)0)
{
if (isEqual(currentNode->location, node->location))
{
preNode->next = currentNode->next;
currentNode->next = (Node *)0;
size--;
*error == ERROR_NO;
return;
}
preNode = currentNode;
currentNode = currentNode->next;
}
// Error
// The source is not exist in the linked list.
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_SEARCH, "void NodeList::removeByLocation(Node *node, ERROR_TYPE *error)", "The node is not in current list");
#endif
*error = ERROR_OBJECT_SEARCH;
return;
}
void NodeList::pickFront(Node **node, ERROR_TYPE *error)
{
// Error checking
// If head has not memory allocation.
if (head == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "void NodeList::removeByLocation(Node *node, ERROR_TYPE *error)", "The head node is Null", "Please call NodeList() when creating the list");
#endif
*error = ERROR_OBJECT_NO;
return;
}
//
/* Algorithm
head -> first node -> ...
The first node could be a null node.
*/
*node = head->next;
*error = ERROR_NO;
}
int8_t NodeList::iterate(Node **node, ERROR_TYPE *error)
{
// Error checking
// If head has not memory allocation.
if (head == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "int NodeList::iterate(Node **node, ERROR_TYPE *error)", "The head node is Null", "Please call NodeList() when creating the list");
#endif
*error = ERROR_OBJECT_NO;
return 0;
}
//
/* Algorithm
head -> node 1 -> node2 -> ....
return node 1
return node 2
...
each time the function be called.
Thanks to the head error checking, iterateHead
*/
if (iterateState == ITERATE_STATE_DONE)
{
iterateState = ITERATE_STATE_ONGOING;
iterateHead = head->next;
}
*node = iterateHead;
if (iterateHead == (Node *)0)
{
iterateState = ITERATE_STATE_DONE;
*error = ERROR_NO;
return 0;
}
iterateHead = iterateHead->next;
*error = ERROR_NO;
return 1;
}
int8_t NodeList::iterate(ERROR_TYPE *error)
{
// Error checking
// If head has not memory allocation.
if (head == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "int NodeList::iterate(ERROR_TYPE *error)", "The head node is Null", "Please call NodeList() when creating the list");
#endif
*error = ERROR_OBJECT_NO;
return 0;
}
//
/* Algorithm
head -> node 1 -> node2 -> ....
return node 1
return node 2
...
each time the function be called.
Thanks to the head error checking, iterateHead
*/
if (iterateState == ITERATE_STATE_DONE)
{
iterateState = ITERATE_STATE_ONGOING;
iterateHead = head->next;
}
if (iterateHead == (Node *)0)
{
iterateState = ITERATE_STATE_DONE;
*error = ERROR_NO;
return 0;
}
iterateHead = iterateHead->next;
*error = ERROR_NO;
return 1;
}
void NodeList::iterateDone()
{
iterateState = ITERATE_STATE_DONE;
}
int8_t NodeList::isEmpty()
{
if (size == 0)
{
return 1;
}
return 0;
}
void NodeList::terminate()
{
if (head == (Node *)0)
{
return;
}
while (head->next != (Node *)0)
{
Node *currentNode = head->next;
head->next = currentNode->next;
free(currentNode);
}
free(head);
}
void NodeList::print(ERROR_TYPE *error)
{
if (head == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "void NodeList::print(ERROR_TYPE *error)", "The head node is Null", "Please call NodeList() when creating the list");
#endif
*error = ERROR_OBJECT_NO;
return;
}
Node *currentNode = head->next;
while (currentNode != (Node *)0)
{
printf("Pointer:(0x%8x), Location(%2d, %2d), Dir:%c, Next:(0x%8x)\n",
currentNode,
currentNode->location.x,
currentNode->location.y,
currentNode->dir,
currentNode->next);
currentNode = currentNode->next;
}
*error = ERROR_NO;
}
int8_t NodeList::search(Node **node, ERROR_TYPE *error)
{
// Error checking
// If head has not memory allocation.
if (head == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "int NodeList::search(Node **node, ERROR_TYPE *error)", "The head node is Null", "Please call NodeList() when creating the list");
#endif
*error = ERROR_OBJECT_NO;
return UNEQUAL;
}
// If the source node is null.
if (*node == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "int NodeList::search(Node **node, ERROR_TYPE *error)", "The source node is Null");
#endif
*error = ERROR_OBJECT_NO;
return UNEQUAL;
}
// The object is empty
if (size == 0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_LIST_EMPTY, "int NodeList::search(Node **node, ERROR_TYPE *error)", "The list is empty");
#endif
*error = ERROR_OBJECT_LIST_EMPTY;
return UNEQUAL;
}
/* Algorithm
node -> node M -> ...
head -> ... -> node -> node M -> ...
head -> ... -> node M -> ...
*/
// Get first node.
Node *currentNode = head->next;
while (currentNode != (Node *)0)
{
if (currentNode == *node)
{
*error = ERROR_NO;
return EQUAL;
}
currentNode = currentNode->next;
}
// Error
// The source is not exist in the linked list.
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_SEARCH, "int NodeList::search(Node **node, ERROR_TYPE *error)", "The node is not in current list");
#endif
*error = ERROR_OBJECT_SEARCH;
return UNEQUAL;
}
int8_t NodeList::searchByLocation(Node **node, ERROR_TYPE *error)
{
// Error checking
// If head has not memory allocation.
if (head == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "int NodeList::searchByLocation(Node **node, ERROR_TYPE *error)", "The head node is Null", "Please call NodeList() when creating the list");
#endif
*error = ERROR_OBJECT_NO;
return UNEQUAL;
}
// If the source node is null.
if (*node == (Node *)0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_NO, "int NodeList::searchByLocation(Node **node, ERROR_TYPE *error)", "The source node is Null");
#endif
*error = ERROR_OBJECT_NO;
return UNEQUAL;
}
// The object is empty
if (size == 0)
{
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_LIST_EMPTY, "int NodeList::searchByLocation(Node **node, ERROR_TYPE *error)", "The list is empty");
#endif
*error = ERROR_OBJECT_LIST_EMPTY;
return UNEQUAL;
}
/* Algorithm
node -> node M -> ...
head -> ... -> node -> node M -> ...
head -> ... -> node M -> ...
*/
// Get first node.
Node *currentNode = head->next;
while (currentNode != (Node *)0)
{
if (isEqual(currentNode->location, (*node)->location))
{
*error = ERROR_NO;
return EQUAL;
}
currentNode = currentNode->next;
}
// Error
// The source is not exist in the linked list.
#if NODELIST_DEBUG == true
printError(ERROR_OBJECT_SEARCH, "int NodeList::searchByLocation(Node **node, ERROR_TYPE *error)", "The node is not in current list");
#endif
*error = ERROR_OBJECT_SEARCH;
return UNEQUAL;
}
#endif목적
Node들을 연결리스트로 만들고, 관리하고, 처리하기 위함
class 형태로 되어 있으며, Node들을 연결리스트에 넣고, 연결리스트를 관리하고, 특별한 기능을 제공하기 위함입니다.
NodeList: 새로운 연결리스트를 생성합니다. 오류를 검출하는 기능이 있습니다.
검출 가능한 오류:
ERROR_MEMORY_NO: 메모리가 부족합니다.
add: 연결리스트에 새로운 노드를 넣습니다. 오류를 검출하는 기능이 있습니다.
검출 가능한 오류:
ERROR_OBJECT_NO: 연결리스트가 생성되지 않았거나, 인수로 받은 node가 null입니다.
ERROR_OBJECT_LIST_EXIST: node가 이미 다른 연결리스트에 들어있습니다.
ERROR_OVERFLOW_INT16: 연결리스트에 더이상 값을 넣을 수 없습니다.
remove: 연결리스트에서 해당 노드를 제거합니다. 오류를 검출하는 기능이 있습니다.
검출 가능한 오류:
ERROR_OBJECT_NO: 연결리스트가 생성되지 않았거나, 인수로 받은 node가 null입니다.
ERROR_OBJECT_LIST_EXIST: node가 이미 다른 연결리스트에 들어있습니다.
ERROR_OBJECT_LIST_EMPTY: 연결리스트가 비어있습니다.
ERROR_OBJECT_SEARCH: 해당 node가 연결리스트에 없습니다.
removeByLocation: 위치를 기반으로 연결리스트에서 해당 노드를 제거합니다. 오류를 검출하는 기능이 있습니다.
검출 가능한 오류:
ERROR_OBJECT_NO: 연결리스트가 생성되지 않았거나, 인수로 받은 node가 null입니다.
ERROR_OBJECT_LIST_EXIST: node가 이미 다른 연결리스트에 들어있습니다.
ERROR_OBJECT_LIST_EMPTY: 연결리스트가 비어있습니다.
ERROR_OBJECT_SEARCH: 해당 node가 연결리스트에 없습니다.
pickFront: 연결리스트에서 첫 번째 노드를 가리킵니다. 오류를 검출하는 기능이 있습니다.
검출 가능한 오류:
ERROR_OBJECT_NO: 연결리스트가 생성되지 않았습니다.
iterate: 호출될 때마다 순차적으로 노드를 가리키며, null이 나올 때까지 가리킵니다. 반복문에서 사용되며, 오류 검출하는 기능이 있습니다.
검출 가능한 오류:
ERROR_OBJECT_NO: 연결리스트가 생성되지 않았습니다.
isEmpty: 연결리스트가 비어있는지를 알려줍니다.
terminate: 연결리스트 내의 모든 요소들을 지우고, 연결리스트 자신도 지웁니다.
print: 연결리스트 내의 모든 노드들의 요소들을 화면에 출력합니다.
search: 연결리스트 내에서 인수로 받은 node가 존재하는지 알려줍니다. 오류를 검출하는 기능이 있습니다.
검출 가능한 오류:
ERROR_OBJECT_NO: 연결리스트가 생성되지 않았거나, 인수로 받은 node가 null입니다.
ERROR_OBJECT_LIST_EXIST: node가 이미 다른 연결리스트에 들어있습니다.
ERROR_OBJECT_LIST_EMPTY: 연결리스트가 비어있습니다.
ERROR_OBJECT_SEARCH: 해당 node가 연결리스트에 없습니다.
searchByLocation: 위치를 기반으로 node를 검색합니다. 오류를 검출하는 기능이 있습니다.
검출 가능한 오류:
ERROR_OBJECT_NO: 연결리스트가 생성되지 않았거나, 인수로 받은 node가 null입니다.
ERROR_OBJECT_LIST_EXIST: node가 이미 다른 연결리스트에 들어있습니다.
ERROR_OBJECT_LIST_EMPTY: 연결리스트가 비어있습니다.
ERROR_OBJECT_SEARCH: 해당 node가 연결리스트에 없습니다.
Continue
반응형
'알고리즘' 카테고리의 다른 글
| A star 경로 알고리즘 (Part 1 원리) (0) | 2021.09.25 |
|---|
