/*
 * Copyright 2003-2010, Axel Dörfler, axeld@pinc-software.de.
 * Distributed under the terms of the MIT License.
 */


#include <parsedate.h>

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include <OS.h>


#define TRACE_PARSEDATE 0
#if TRACE_PARSEDATE
#	define TRACE(x) printf x ;
#else
#	define TRACE(x) ;
#endif


/* The date format is as follows:
 *
 *	a/A		weekday
 *	d		day of month
 *	b/B		month name
 *	m		month
 *	y/Y		year
 *	H/I		hours
 *	M		minute
 *	S		seconds
 *	p		meridian (i.e. am/pm)
 *	T		time unit: last hour, next tuesday, today, ...
 *	z/Z		time zone
 *	-		dash or slash
 *
 *	Any of ",.:" is allowed and will be expected in the input string as is.
 *	You can enclose a single field with "[]" to mark it as being optional.
 *	A space stands for white space.
 *	No other character is allowed.
 */

static const char * const kFormatsTable[] = {
	"[A][,] B d[,] H:M:S [p] Y[,] [Z]",
	"[A][,] B d[,] [Y][,] H:M:S [p] [Z]",
	"[A][,] B d[,] [Y][,] H:M [p][,] [Z]",
	"[A][,] B d[,] [Y][,] H [p][,] [Z]",
	"[A][,] B d[,] H:M [p][,] [Y] [Z]",
	"[A][,] d B[,] [Y][,] H:M [p][,] [Z]",
	"[A][,] d B[,] [Y][,] H:M:S [p][,] [Z]",
	"[A][,] d B[,] H:M:S [Y][,] [p][,] [Z]",
	"[A][,] d B[,] H:M [Y][,] [p][,] [Z]",
	"d.m.y H:M:S [p] [Z]",
	"d.m.y H:M [p] [Z]",
	"d.m.y",
	"[A][,] m-d-y[,] [H][:][M] [p]",
	"[A][,] m-d[,] H:M [p]",
	"[A][,] m-d[,] H[p]",
	"[A][,] m-d",
	"[A][,] B d[,] Y",
	"[A][,] H:M [p]",
	"[A][,] H [p]",
	"H:M [p][,] [A]",
	"H [p][,] [A]",
	"[A][,] B d[,] H:M:S [p] [Z] [Y]",
	"[A][,] B d[,] H:M [p] [Z] [Y]",
	"[A][,] d B [,] H:M:S [p] [Z] [Y]",
	"[A][,] d B [,] H:M [p] [Z] [Y]",
	"[A][,] d-B-Y H:M:S [p] [Z]",
	"[A][,] d-B-Y H:M [p] [Z]",
	"d B Y H:M:S [Z]",
	"d B Y H:M [Z]",
	"y-m-d",
	"y-m-d H:M:S [p] [Z]",
	"m-d-y H[p]",
	"m-d-y H:M[p]",
	"m-d-y H:M:S[p]",
	"H[p] m-d-y",
	"H:M[p] m-d-y",
	"H:M:S[p] m-d-y",
	"A[,] H:M:S [p] [Z]",
	"A[,] H:M [p] [Z]",
	"H:M:S [p] [Z]",
	"H:M [p] [Z]",
	"A[,] [B] [d] [Y]",
	"A[,] [d] [B] [Y]",
	"B d[,][Y] H[p][,] [Z]",
	"B d[,] H[p]",
	"B d [,] H:M [p]",
	"d B [,][Y] H [p] [Z]",
	"d B [,] H:M [p]",
	"B d [,][Y]",
	"B d [,] H:M [p][,] [Y]",
	"B d [,] H [p][,] [Y]",
	"d B [,][Y]",
	"H[p] [,] B d",
	"H:M[p] [,] B d",
	"T [T][T][T][T][T]",
	"T H:M:S [p]",
	"T H:M [p]",
	"T H [p]",
	"H:M [p] T",
	"H [p] T",
	"H [p]",
	NULL
};
static const char* const* sFormatsTable = kFormatsTable;


enum field_type {
	TYPE_UNKNOWN = 0,

	TYPE_DAY,
	TYPE_MONTH,
	TYPE_YEAR,
	TYPE_WEEKDAY,
	TYPE_HOUR,
	TYPE_MINUTE,
	TYPE_SECOND,
	TYPE_TIME_ZONE,
	TYPE_MERIDIAN,

	TYPE_DASH,
	TYPE_DOT,
	TYPE_COMMA,
	TYPE_COLON,

	TYPE_UNIT,
	TYPE_MODIFIER,
	TYPE_END,
};

#define FLAG_NONE				0
#define FLAG_RELATIVE			1
#define FLAG_NOT_MODIFIABLE		2
#define FLAG_NOW				4
#define FLAG_NEXT_LAST_THIS		8
#define FLAG_PLUS_MINUS			16
#define FLAG_HAS_DASH			32

enum units {
	UNIT_NONE,
	UNIT_YEAR,
	UNIT_MONTH,
	UNIT_DAY,
	UNIT_SECOND,
};

enum value_type {
	VALUE_NUMERICAL,
	VALUE_STRING,
	VALUE_CHAR,
};

enum value_modifier {
	MODIFY_MINUS	= -2,
	MODIFY_LAST		= -1,
	MODIFY_NONE		= 0,
	MODIFY_THIS		= MODIFY_NONE,
	MODIFY_NEXT		= 1,
	MODIFY_PLUS		= 2,
};

struct known_identifier {
	const char	*string;
	const char	*alternate_string;
	uint8		type;
	uint8		flags;
	uint8		unit;
	int32		value;
};

static const known_identifier kIdentifiers[] = {
	{"today",		NULL,	TYPE_UNIT, FLAG_RELATIVE | FLAG_NOT_MODIFIABLE,
		UNIT_DAY, 0},
	{"tomorrow",	NULL,	TYPE_UNIT, FLAG_RELATIVE | FLAG_NOT_MODIFIABLE,
		UNIT_DAY, 1},
	{"yesterday",	NULL,	TYPE_UNIT, FLAG_RELATIVE | FLAG_NOT_MODIFIABLE,
		UNIT_DAY, -1},
	{"now",			NULL,	TYPE_UNIT,
		FLAG_RELATIVE | FLAG_NOT_MODIFIABLE | FLAG_NOW, 0},

	{"this",		NULL,	TYPE_MODIFIER, FLAG_NEXT_LAST_THIS, UNIT_NONE,
		MODIFY_THIS},
	{"next",		NULL,	TYPE_MODIFIER, FLAG_NEXT_LAST_THIS, UNIT_NONE,
		MODIFY_NEXT},
	{"last",		NULL,	TYPE_MODIFIER, FLAG_NEXT_LAST_THIS, UNIT_NONE,
		MODIFY_LAST},

	{"years",		"year",	TYPE_UNIT, FLAG_RELATIVE, UNIT_YEAR, 1},
	{"months",		"month",TYPE_UNIT, FLAG_RELATIVE, UNIT_MONTH, 1},
	{"weeks",		"week",	TYPE_UNIT, FLAG_RELATIVE, UNIT_DAY, 7},
	{"days",		"day",	TYPE_UNIT, FLAG_RELATIVE, UNIT_DAY, 1},
	{"hour",		NULL,	TYPE_UNIT, FLAG_RELATIVE, UNIT_SECOND, 1 * 60 * 60},
	{"hours",		"hrs",	TYPE_UNIT, FLAG_RELATIVE, UNIT_SECOND, 1 * 60 * 60},
	{"second",		"sec",	TYPE_UNIT, FLAG_RELATIVE, UNIT_SECOND, 1},
	{"seconds",		"secs",	TYPE_UNIT, FLAG_RELATIVE, UNIT_SECOND, 1},
	{"minute",		"min",	TYPE_UNIT, FLAG_RELATIVE, UNIT_SECOND, 60},
	{"minutes",		"mins",	TYPE_UNIT, FLAG_RELATIVE, UNIT_SECOND, 60},

	{"am",			NULL,	TYPE_MERIDIAN, FLAG_NOT_MODIFIABLE, UNIT_SECOND, 0},
	{"pm",			NULL,	TYPE_MERIDIAN, FLAG_NOT_MODIFIABLE, UNIT_SECOND,
		12 * 60 * 60},

	{"sunday",		"sun",	TYPE_WEEKDAY, FLAG_NONE, UNIT_DAY, 0},
	{"monday",		"mon",	TYPE_WEEKDAY, FLAG_NONE, UNIT_DAY, 1},
	{"tuesday",		"tue",	TYPE_WEEKDAY, FLAG_NONE, UNIT_DAY, 2},
	{"wednesday",	"wed",	TYPE_WEEKDAY, FLAG_NONE, UNIT_DAY, 3},
	{"thursday",	"thu",	TYPE_WEEKDAY, FLAG_NONE, UNIT_DAY, 4},
	{"friday",		"fri",	TYPE_WEEKDAY, FLAG_NONE, UNIT_DAY, 5},
	{"saturday",	"sat",	TYPE_WEEKDAY, FLAG_NONE, UNIT_DAY, 6},

	{"january",		"jan",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 1},
	{"february",	"feb", 	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 2},
	{"march",		"mar",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 3},
	{"april",		"apr",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 4},
	{"may",			"may",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 5},
	{"june",		"jun",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 6},
	{"july",		"jul",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 7},
	{"august",		"aug",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 8},
	{"september",	"sep",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 9},
	{"october",		"oct",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 10},
	{"november",	"nov",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 11},
	{"december",	"dec",	TYPE_MONTH, FLAG_NONE, UNIT_MONTH, 12},

	{"GMT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 0},
	{"UTC",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 0},
	// the following list has been generated from info found at
	// http://www.timegenie.com/timezones
	{"ACDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1050 * 36},
	{"ACIT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"ACST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 950 * 36},
	{"ACT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -500 * 36},
	{"ACWST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 875 * 36},
	{"ADT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"AEDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1100 * 36},
	{"AEST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1000 * 36},
	{"AFT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 450 * 36},
	{"AKDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -800 * 36},
	{"AKST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -900 * 36},
	{"AMDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"AMST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 400 * 36},
	{"ANAST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1300 * 36},
	{"ANAT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"APO",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 825 * 36},
	{"ARDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -200 * 36},
	{"ART",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"AST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -400 * 36},
	{"AWST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"AZODT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 0 * 36},
	{"AZOST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -100 * 36},
	{"AZST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"AZT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 400 * 36},
	{"BIT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -1200 * 36},
	{"BDT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"BEST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -200 * 36},
	{"BIOT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"BNT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"BOT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -400 * 36},
	{"BRST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -200 * 36},
	{"BRT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"BST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 100 * 36},
	{"BTT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"BWDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"BWST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -400 * 36},
	{"CAST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"CAT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 200 * 36},
	{"CCT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 650 * 36},
	{"CDT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -500 * 36},
	{"CEST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 200 * 36},
	{"CET",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 100 * 36},
	{"CGST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -200 * 36},
	{"CGT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"CHADT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1375 * 36},
	{"CHAST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1275 * 36},
	{"CHST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1000 * 36},
	{"CIST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -800 * 36},
	{"CKT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -1000 * 36},
	{"CLDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"CLST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -400 * 36},
	{"COT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -500 * 36},
	{"CST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -600 * 36},
	{"CVT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -100 * 36},
	{"CXT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 700 * 36},
	{"DAVT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 700 * 36},
	{"DTAT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1000 * 36},
	{"EADT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -500 * 36},
	{"EAST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -600 * 36},
	{"EAT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 300 * 36},
	{"ECT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -500 * 36},
	{"EDT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -400 * 36},
	{"EEST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 300 * 36},
	{"EET",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 200 * 36},
	{"EGT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -100 * 36},
	{"EGST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 0 * 36},
	{"EKST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"EST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -500 * 36},
	{"FJT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"FKDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"FKST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -400 * 36},
	{"GALT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -600 * 36},
	{"GET",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 400 * 36},
	{"GFT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"GILT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"GIT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -900 * 36},
	{"GST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 400 * 36},
	{"GYT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -400 * 36},
	{"HADT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -900 * 36},
	{"HAST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -1000 * 36},
	{"HKST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"HMT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"ICT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 700 * 36},
	{"IDT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 300 * 36},
	{"IRDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 450 * 36},
	{"IRKST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 900 * 36},
	{"IRKT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"IRST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 350 * 36},
	{"IST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 200 * 36},
	{"JFDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"JFST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -400 * 36},
	{"JST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 900 * 36},
	{"KGST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"KGT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"KRAST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"KRAT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 700 * 36},
	{"KOST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1100 * 36},
	{"KOVT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 700 * 36},
	{"KOVST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"KST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 900 * 36},
	{"LHDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1100 * 36},
	{"LHST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1050 * 36},
	{"LINT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1400 * 36},
	{"LKT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"MAGST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"MAGT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1100 * 36},
	{"MAWT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"MBT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"MDT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -600 * 36},
	{"MIT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -950 * 36},
	{"MHT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"MMT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 650 * 36},
	{"MNT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"MNST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 900 * 36},
	{"MSD",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 400 * 36},
	{"MSK",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 300 * 36},
	{"MST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -700 * 36},
	{"MUST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"MUT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 400 * 36},
	{"MVT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"MYT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"NCT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1100 * 36},
	{"NDT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -250 * 36},
	{"NFT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1150 * 36},
	{"NPT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 575 * 36},
	{"NRT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"NOVST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 700 * 36},
	{"NOVT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"NST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -350 * 36},
	{"NUT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -1100 * 36},
	{"NZDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1300 * 36},
	{"NZST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"OMSK",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 700 * 36},
	{"OMST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"PDT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -700 * 36},
	{"PETST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1300 * 36},
	{"PET",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -500 * 36},
	{"PETT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"PGT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1000 * 36},
	{"PHOT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1300 * 36},
	{"PHT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"PIT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"PKT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"PKST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"PMDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -200 * 36},
	{"PMST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"PONT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1100 * 36},
	{"PST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -800 * 36},
	{"PWT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 900 * 36},
	{"PYST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"PYT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -400 * 36},
	{"RET",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 400 * 36},
	{"ROTT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"SAMST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"SAMT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 400 * 36},
	{"SAST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 200 * 36},
	{"SBT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1100 * 36},
	{"SCDT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1300 * 36},
	{"SCST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"SCT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 400 * 36},
	{"SGT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"SIT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"SLT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -400 * 36},
	{"SLST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"SRT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"SST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -1100 * 36},
	{"SYST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 300 * 36},
	{"SYT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 200 * 36},
	{"TAHT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -1000 * 36},
	{"TFT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"TJT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"TKT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -1000 * 36},
	{"TMT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"TOT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1300 * 36},
	{"TPT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 900 * 36},
	{"TRUT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1000 * 36},
	{"TVT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"TWT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"UYT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -300 * 36},
	{"UYST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -200 * 36},
	{"UZT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"VLAST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1100 * 36},
	{"VLAT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1000 * 36},
	{"VOST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"VST",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, -450 * 36},
	{"VUT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1100 * 36},
	{"WAST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 200 * 36},
	{"WAT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 100 * 36},
	{"WEST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 100 * 36},
	{"WET",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 0 * 36},
	{"WFT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1200 * 36},
	{"WIB",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 700 * 36},
	{"WIT",		NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 900 * 36},
	{"WITA",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 800 * 36},
	{"WKST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},
	{"YAKST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1000 * 36},
	{"YAKT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 900 * 36},
	{"YAPT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 1000 * 36},
	{"YEKST",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 600 * 36},
	{"YEKT",	NULL,	TYPE_TIME_ZONE,	FLAG_NONE, UNIT_SECOND, 500 * 36},

	{NULL}
};

#define MAX_ELEMENTS	32

class DateMask {
	public:
		DateMask() : fMask(0UL) {}

		void Set(uint8 type) { fMask |= Flag(type); }
		bool IsSet(uint8 type) { return (fMask & Flag(type)) != 0; }

		bool HasTime();
		bool IsComplete();

	private:
		inline uint32 Flag(uint8 type) const { return 1UL << type; }

		uint32	fMask;
};


struct parsed_element {
	uint8		base_type;
	uint8		type;
	uint8		flags;
	uint8		unit;
	uint8		value_type;
	int8		modifier;
	bigtime_t	value;

	void SetCharType(uint8 fieldType, int8 modify = MODIFY_NONE);

	void Adopt(const known_identifier& identifier);
	void AdoptUnit(const known_identifier& identifier);
	bool IsNextLastThis();
};


void
parsed_element::SetCharType(uint8 fieldType, int8 modify)
{
	base_type = type = fieldType;
	value_type = VALUE_CHAR;
	modifier = modify;
}


void
parsed_element::Adopt(const known_identifier& identifier)
{
	base_type = type = identifier.type;
	flags = identifier.flags;
	unit = identifier.unit;

	if (identifier.type == TYPE_MODIFIER)
		modifier = identifier.value;

	value_type = VALUE_STRING;
	value = identifier.value;
}


void
parsed_element::AdoptUnit(const known_identifier& identifier)
{
	base_type = type = TYPE_UNIT;
	flags = identifier.flags;
	unit = identifier.unit;
	value *= identifier.value;
}


inline bool
parsed_element::IsNextLastThis()
{
	return base_type == TYPE_MODIFIER
		&& (modifier == MODIFY_NEXT || modifier == MODIFY_LAST
			|| modifier == MODIFY_THIS);
}


//	#pragma mark -


bool
DateMask::HasTime()
{
	// this will cause
	return IsSet(TYPE_HOUR);
}


/*!	This method checks if the date mask is complete in the
	sense that it doesn't need to have a prefilled "struct tm"
	when its time value is computed.
*/
bool
DateMask::IsComplete()
{
	// mask must be absolute, at last
	if ((fMask & Flag(TYPE_UNIT)) != 0)
		return false;

	// minimal set of flags to have a complete set
	return !(~fMask & (Flag(TYPE_DAY) | Flag(TYPE_MONTH)));
}


//	#pragma mark -


static status_t
preparseDate(const char* dateString, parsed_element* elements)
{
	int32 index = 0, modify = MODIFY_NONE;
	char c;

	if (dateString == NULL)
		return B_ERROR;

	memset(&elements[0], 0, sizeof(parsed_element));

	for (; (c = dateString[0]) != '\0'; dateString++) {
		// we don't care about spaces
		if (isspace(c)) {
			modify = MODIFY_NONE;
			continue;
		}

		// if we're reached our maximum number of elements, bail out
		if (index >= MAX_ELEMENTS)
			return B_ERROR;

		if (c == ',') {
			elements[index].SetCharType(TYPE_COMMA);
		} else if (c == '.') {
			elements[index].SetCharType(TYPE_DOT);
		} else if (c == '/') {
			// "-" is handled differently (as a modifier)
			elements[index].SetCharType(TYPE_DASH);
		} else if (c == ':') {
			elements[index].SetCharType(TYPE_COLON);
		} else if (c == '+') {
			modify = MODIFY_PLUS;

			// this counts for the next element
			continue;
		} else if (c == '-') {
			modify = MODIFY_MINUS;
			elements[index].flags = FLAG_HAS_DASH;

			// this counts for the next element
			continue;
		} else if (isdigit(c)) {
			// fetch whole number

			elements[index].type = TYPE_UNKNOWN;
			elements[index].value_type = VALUE_NUMERICAL;
			elements[index].value = atoll(dateString);
			elements[index].modifier = modify;

			// skip number
			while (isdigit(dateString[1]))
				dateString++;

			// check for "1st", "2nd, "3rd", "4th", ...

			const char* suffixes[] = {"th", "st", "nd", "rd"};
			const char* validSuffix = elements[index].value > 3
				? "th" : suffixes[elements[index].value];
			if (!strncasecmp(dateString + 1, validSuffix, 2)
				&& !isalpha(dateString[3])) {
				// for now, just ignore the suffix - but we might be able
				// to deduce some meaning out of it, since it's not really
				// possible to put it in anywhere
				dateString += 2;
			}
		} else if (isalpha(c)) {
			// fetch whole string

			const char* string = dateString;
			while (isalpha(dateString[1]))
				dateString++;
			int32 length = dateString + 1 - string;

			// compare with known strings
			// ToDo: should understand other languages as well...

			const known_identifier* identifier = kIdentifiers;
			for (; identifier->string; identifier++) {
				if (!strncasecmp(identifier->string, string, length)
					&& !identifier->string[length])
					break;

				if (identifier->alternate_string != NULL
					&& !strncasecmp(identifier->alternate_string, string, length)
					&& !identifier->alternate_string[length])
					break;
			}
			if (identifier->string == NULL) {
				// unknown string, we don't have to parse any further
				return B_ERROR;
			}

			if (index > 0 && identifier->type == TYPE_UNIT) {
				// this is just a unit, so it will give the last value a meaning

				if (elements[--index].value_type != VALUE_NUMERICAL
					&& !elements[index].IsNextLastThis())
					return B_ERROR;

				elements[index].AdoptUnit(*identifier);
			} else if (index > 0 && elements[index - 1].IsNextLastThis()) {
				if (identifier->type == TYPE_MONTH
					|| identifier->type == TYPE_WEEKDAY) {
					index--;

					switch (elements[index].value) {
						case -1:
							elements[index].modifier = MODIFY_LAST;
							break;
						case 0:
							elements[index].modifier = MODIFY_THIS;
							break;
						case 1:
							elements[index].modifier = MODIFY_NEXT;
							break;
					}
					elements[index].Adopt(*identifier);
					elements[index].type = TYPE_UNIT;
				} else
					return B_ERROR;
			} else {
				elements[index].Adopt(*identifier);
			}
		}

		// see if we can join any preceding modifiers

		if (index > 0
			&& elements[index - 1].type == TYPE_MODIFIER
			&& (elements[index].flags & FLAG_NOT_MODIFIABLE) == 0) {
			// copy the current one to the last and go on
			elements[index].modifier = elements[index - 1].modifier;
			elements[index].value *= elements[index - 1].value;
			elements[index].flags |= elements[index - 1].flags;
			elements[index - 1] = elements[index];
		} else {
			// we filled out one parsed_element
			index++;
		}

		if (index < MAX_ELEMENTS)
			memset(&elements[index], 0, sizeof(parsed_element));
	}

	// were there any elements?
	if (index == 0)
		return B_ERROR;

	elements[index].type = TYPE_END;

	return B_OK;
}


static void
computeRelativeUnit(parsed_element& element, struct tm& tm, int* _flags)
{
	// set the relative start depending on unit

	switch (element.unit) {
		case UNIT_YEAR:
			tm.tm_mon = 0;	// supposed to fall through
		case UNIT_MONTH:
			tm.tm_mday = 1;	// supposed to fall through
		case UNIT_DAY:
			tm.tm_hour = 0;
			tm.tm_min = 0;
			tm.tm_sec = 0;
			break;
	}

	// adjust value

	if ((element.flags & FLAG_RELATIVE) != 0) {
		bigtime_t value = element.value;
		if (element.modifier == MODIFY_MINUS)
			value = -element.value;

		if (element.unit == UNIT_MONTH)
			tm.tm_mon += value;
		else if (element.unit == UNIT_DAY)
			tm.tm_mday += value;
		else if (element.unit == UNIT_SECOND) {
			tm.tm_sec += value;
			*_flags |= PARSEDATE_MINUTE_RELATIVE_TIME;
		} else if (element.unit == UNIT_YEAR)
			tm.tm_year += value;
	} else if (element.base_type == TYPE_WEEKDAY) {
		tm.tm_mday += element.value - tm.tm_wday;

		if (element.modifier == MODIFY_NEXT)
			tm.tm_mday += 7;
		else if (element.modifier == MODIFY_LAST)
			tm.tm_mday -= 7;
	} else if (element.base_type == TYPE_MONTH) {
		tm.tm_mon = element.value - 1;

		if (element.modifier == MODIFY_NEXT)
			tm.tm_year++;
		else if (element.modifier == MODIFY_LAST)
			tm.tm_year--;
	}
}


/*!	Uses the format assignment (through "format", and "optional") for the
	parsed elements and calculates the time value with respect to "now".
	Will also set the day/minute relative flags in "_flags".
*/
static time_t
computeDate(const char* format, bool* optional, parsed_element* elements,
	time_t now, DateMask dateMask, int* _flags)
{
	TRACE(("matches: %s\n", format));

	parsed_element* element = elements;
	uint32 position = 0;
	struct tm tm;

	if (now == -1)
		now = time(NULL);

	int nowYear = -1;
	if (dateMask.IsComplete())
		memset(&tm, 0, sizeof(tm));
	else {
		localtime_r(&now, &tm);
		nowYear = tm.tm_year;
		if (dateMask.HasTime()) {
			tm.tm_min = 0;
			tm.tm_sec = 0;
		}

		*_flags = PARSEDATE_RELATIVE_TIME;
	}

	while (element->type != TYPE_END) {
		// skip whitespace
		while (isspace(format[0]))
			format++;

		if (format[0] == '[' && format[2] == ']') {
			// does this optional parameter not match our date string?
			if (!optional[position]) {
				format += 3;
				position++;
				continue;
			}

			format++;
		}

		switch (element->value_type) {
			case VALUE_CHAR:
				// skip the single character
				break;

			case VALUE_NUMERICAL:
				switch (format[0]) {
					case 'd':
						tm.tm_mday = element->value;
						break;
					case 'm':
						tm.tm_mon = element->value - 1;
						break;
					case 'H':
					case 'I':
						tm.tm_hour = element->value;
						break;
					case 'M':
						tm.tm_min = element->value;
						break;
					case 'S':
						tm.tm_sec = element->value;
						break;
					case 'y':
					case 'Y':
					{
						if (nowYear < 0) {
							struct tm tmNow;
							localtime_r(&now, &tmNow);
							nowYear	= tmNow.tm_year;
						}
						int nowYearInCentury = nowYear % 100;
						int nowCentury = 1900 + nowYear - nowYearInCentury;

						tm.tm_year = element->value;
						if (tm.tm_year < 1900) {
							// just a relative year like 11 (2011)

							// interpret something like 50 as 1950 but
							// something like 11 as 2011 (assuming now is 2011)
							if (nowYearInCentury + 10 < tm.tm_year % 100)
								tm.tm_year -= 100;
							
							tm.tm_year += nowCentury - 1900;
						}
						else {
							tm.tm_year -= 1900;
						}
						break;
					}
					case 'z':	// time zone
					case 'Z':
					{
						bigtime_t value
							= (element->value - element->value % 100) * 36
								+ (element->value % 100) * 60;
						if (element->modifier == MODIFY_MINUS)
							value *= -1;
#ifndef HoG_GENODE
						tm.tm_sec -= value + timezone;
#else
///later: what's this timezone thingy ?
						tm.tm_sec -= value;// + timezone;
#endif
						break;
					}
					case 'T':
						computeRelativeUnit(*element, tm, _flags);
						break;
					case '-':
						// there is no TYPE_DASH element for this (just a flag)
						format++;
						continue;
				}
				break;

			case VALUE_STRING:
				switch (format[0]) {
					case 'a':	// weekday
					case 'A':
						// we'll apply this element later, if still necessary
						if (!dateMask.IsComplete())
							computeRelativeUnit(*element, tm, _flags);
						break;
					case 'b':	// month
					case 'B':
						tm.tm_mon = element->value - 1;
						break;
					case 'p':	// meridian
						tm.tm_sec += element->value;
						break;
					case 'z':	// time zone
					case 'Z':
#ifndef HoG_GENODE
						tm.tm_sec -= element->value + timezone;
#else
///later: what's this timezone thingy ?
						tm.tm_sec -= element->value;// + timezone;
#endif
						break;
					case 'T':	// time unit
						if ((element->flags & FLAG_NOW) != 0) {
							*_flags = PARSEDATE_MINUTE_RELATIVE_TIME
								| PARSEDATE_RELATIVE_TIME;
							break;
						}

						computeRelativeUnit(*element, tm, _flags);
						break;
				}
				break;
		}

		// format matched at this point, check next element
		format++;
		if (format[0] == ']')
			format++;

		position++;
		element++;
	}

	return mktime(&tm);
}


// #pragma mark - public API


time_t
parsedate_etc(const char* dateString, time_t now, int* _flags)
{
	// preparse date string so that it can be easily compared to our formats

	parsed_element elements[MAX_ELEMENTS];

	if (preparseDate(dateString, elements) < B_OK) {
		*_flags = PARSEDATE_INVALID_DATE;
		return B_ERROR;
	}

#if TRACE_PARSEDATE
	printf("parsedate(\"%s\", now %ld)\n", dateString, now);
	for (int32 index = 0; elements[index].type != TYPE_END; index++) {
		parsed_element e = elements[index];

		printf("  %ld: type = %u, base_type = %u, unit = %u, flags = %u, "
			"modifier = %u, value = %Ld (%s)\n", index, e.type, e.base_type,
			e.unit, e.flags, e.modifier, e.value,
			e.value_type == VALUE_NUMERICAL ? "numerical"
				: (e.value_type == VALUE_STRING ? "string" : "char"));
	}
#endif

	bool optional[MAX_ELEMENTS];

	for (int32 index = 0; sFormatsTable[index]; index++) {
		// test if this format matches our date string

		const char* format = sFormatsTable[index];
		uint32 position = 0;
		DateMask dateMask;

		parsed_element* element = elements;
		while (element->type != TYPE_END) {
			// skip whitespace
			while (isspace(format[0]))
				format++;

			if (format[0] == '[' && format[2] == ']') {
				optional[position] = true;
				format++;
			} else
				optional[position] = false;

			switch (element->value_type) {
				case VALUE_CHAR:
					// check the allowed single characters

					switch (element->type) {
						case TYPE_DOT:
							if (format[0] != '.')
								goto next_format;
							break;
						case TYPE_DASH:
							if (format[0] != '-')
								goto next_format;
							break;
						case TYPE_COMMA:
							if (format[0] != ',')
								goto next_format;
							break;
						case TYPE_COLON:
							if (format[0] != ':')
								goto next_format;
							break;
						default:
							goto next_format;
					}
					break;

				case VALUE_NUMERICAL:
					// make sure that unit types are respected
					if (element->type == TYPE_UNIT && format[0] != 'T')
						goto next_format;

					switch (format[0]) {
						case 'd':
							if (element->value > 31)
								goto next_format;

							dateMask.Set(TYPE_DAY);
							break;
						case 'm':
							if (element->value > 12)
								goto next_format;

							dateMask.Set(TYPE_MONTH);
							break;
						case 'H':
						case 'I':
							if (element->value > 24)
								goto next_format;

							dateMask.Set(TYPE_HOUR);
							break;
						case 'M':
							if (element->value > 59)
								goto next_format;

							dateMask.Set(TYPE_MINUTE);
							break;
						case 'S':
							if (element->value > 59)
								goto next_format;

							dateMask.Set(TYPE_SECOND);
							break;
						case 'y':
						case 'Y':
							// accept all values
							break;
						case 'z':	// time zone
						case 'Z':
							// a numerical timezone must be introduced by '+'
							// or '-' and it must not exceed 2399
							if ((element->modifier != MODIFY_MINUS
									&& element->modifier != MODIFY_PLUS)
								|| element->value > 2399)
								goto next_format;
							break;
						case 'T':
							dateMask.Set(TYPE_UNIT);
							break;
						case '-':
							if ((element->flags & FLAG_HAS_DASH) != 0) {
								element--;	// consider this element again
								break;
							}
							// supposed to fall through
						default:
							goto next_format;
					}
					break;

				case VALUE_STRING:
					switch (format[0]) {
						case 'a':	// weekday
						case 'A':
							if (element->type != TYPE_WEEKDAY)
								goto next_format;
							break;
						case 'b':	// month
						case 'B':
							if (element->type != TYPE_MONTH)
								goto next_format;

							dateMask.Set(TYPE_MONTH);
							break;
						case 'p':	// meridian
							if (element->type != TYPE_MERIDIAN)
								goto next_format;
							break;
						case 'z':	// time zone
						case 'Z':
							if (element->type != TYPE_TIME_ZONE)
								goto next_format;
							break;
						case 'T':	// time unit
							if (element->type != TYPE_UNIT)
								goto next_format;

							dateMask.Set(TYPE_UNIT);
							break;
						default:
							goto next_format;
					}
					break;
			}

			// format matched at this point, check next element
			if (optional[position])
				format++;
			format++;
			position++;
			element++;
			continue;

		next_format:
			// format didn't match element - let's see if the current
			// one is only optional (in which case we can continue)
			if (!optional[position])
				goto skip_format;

			optional[position] = false;
			format += 2;
			position++;
				// skip the closing ']'
		}

		// check if the format is already empty (since we reached our last
		// element)
		while (format[0]) {
			if (format[0] == '[')
				format += 3;
			else if (isspace(format[0]))
				format++;
			else
				break;
		}
		if (format[0])
			goto skip_format;

		// made it here? then we seem to have found our guy

		return computeDate(sFormatsTable[index], optional, elements, now,
			dateMask, _flags);

	skip_format:
		// check if the next format has the same beginning as the skipped one,
		// and if so, skip that one, too.

		int32 length = format + 1 - sFormatsTable[index];

		while (sFormatsTable[index + 1]
			&& !strncmp(sFormatsTable[index], sFormatsTable[index + 1], length))
			index++;
	}

	// didn't find any matching formats
	return B_ERROR;
}


time_t
parsedate(const char* dateString, time_t now)
{
	int flags = 0;

	return parsedate_etc(dateString, now, &flags);
}


void
set_dateformats(const char** table)
{
	sFormatsTable = table ? table : kFormatsTable;
}


const char**
get_dateformats(void)
{
	return const_cast<const char**>(sFormatsTable);
}

