list.h File Reference

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "utils.h"

Include dependency graph for list.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	pack
struct	List
struct	hnode
struct	prodLine
struct	packData
struct	query

Macros
#define	INT_MIN   -2147483647
#define	EMPTY   -23432
#define	PUSH   -232310
#define	MERGE   -2323
#define	MAX_Q   200000
#define	MAX_N   200000
#define	MAX_OP_CHAR   20

Typedefs
typedef struct pack	pack
typedef struct List	List
typedef struct hnode	hnode
typedef struct packData	packData

Functions
int	solve (packData pd, query *qs, int n_query, int *pkOrders)
packData	init_packData (int n, int l)
	Initiate a package management problem. More...
void	kill_packData (packData)
void	PushPack (packData, int iLine, int iPack)
void	MergeLines (packData, int iDst, int iSrc)
int	PopFirstPack (packData, int iLine)
int	PopLastPack (packData, int iLine)
int	PopMaxPack (packData, int iLine)
int	_PopOperation (packData, int, int(*PeekFunc)(packData, int), int(*PopFunc)(packData, int))
int	PeekFirstPack (packData, int i)
int	PeekLastPack (packData, int i)
int	PeekMaxPack (packData, int i)
void	_clearGetMethod (packData, int iLine)
void	_setGetMethod (packData, int iLine)
void	_insertHeap (packData pd, int iLine, int iPack)
int	_popMaxHeap (packData, int iLine)
void	_mergeHeap (packData, int iDst, int iSrc)
hnode *	_mergeHeapLeftist (hnode *A, hnode *B)
	Merge leftist heap. More...
hnode *	_popMaxHeapLeftist (hnode *root, int *val)
hnode *	_insertHeapLeftist (hnode *root, pack *pk, hnode *newnode)
int	_getDistLeftist (hnode *node)
void	swaphNode (hnode **A, hnode **B)
hnode *	createNode (pack *pk, hnode *node)
void	_killHeap (hnode *root)
void	_insertlist (packData pd, int iLine, int iPack)
void	_mergelist (packData, int iDst, int iSrc)
int	_popFirst (packData pd, int iLine)
	Pop first item. Set popped item.avail (pack) to zero. More...
int	_popLast (packData pd, int iLine)
	Similar to _popFirst .
void	_removePack (pack *)
void	_removePackGetMethod (pack *)
pack	getNullPack (void)
prodLine	getNullProdLine (void)
int	_getopID (char *)
void	_getOperation (query *)
void	_printRes (int sol)
void	interface (void)

Detailed Description

Author

your name (you@d.nosp@m.omai.nosp@m.n.com)

Version

0.1

Date

2021-05-08

Copyright

Copyright (c) 2021

Function Documentation

_clearGetMethod()

void _clearGetMethod	(	packData	pd,
		int	iLine
	)

Array of peek functions

_mergeHeapLeftist()

hnode* _mergeHeapLeftist	(	hnode *	A,
		hnode *	B
	)

Merge leftist heap.

Parameters

A	heap root
B	heap root

Note

This algorithm is inspired from CSC 378: Data Structures and Algorithm Analysis

_popFirst()

int _popFirst	(	packData	pd,
		int	iLine
	)

Pop first item. Set popped item.avail (pack) to zero.

Note

this function can be used to pop item. No matter it is availability or not. The item's availablity will be set as 0.

Returns

int popped ID

_PopOperation()

int _PopOperation	(	packData	pd,
		int	iLine,
		int(*)(packData, int)	PeekFunc,
		int(*)(packData, int)	PopFunc
	)

• Use Function pointer to generalize the Pop operation

init_packData()

packData init_packData	(	int	n,
		int	l
	)

Initiate a package management problem.

Parameters

n	number of packages
l	number of lines

Returns

packData

PeekFirstPack()

int PeekFirstPack	(	packData	pd,
		int	i
	)

• Peek first. Return NULL if the line is empty

PeekLastPack()

int PeekLastPack	(	packData	pd,
		int	i
	)

• Peek Last. Return NULL if the line is empty

solve()

int solve	(	packData	pd,
		query *	qs,
		int	n_query,
		int *	pkOrders
	)

Do Operation

Try Pop