From: Mark Wooding Date: Fri, 13 Sep 2024 01:43:07 +0000 (+0100) Subject: Initial commit. X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/wordchain/commitdiff_plain/d26c702eb9253b324a24b1672ca7038c6360f67e?ds=inline Initial commit. --- d26c702eb9253b324a24b1672ca7038c6360f67e diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..33f9090 --- /dev/null +++ b/Makefile @@ -0,0 +1,217 @@ +### -*-makefile-*- + +all: +TARGETS = + +clean:: +CLEAN = + +.PHONY: all clean + +.SECONDEXPANSION: + +SRCEXT = + +V = 0 +v-tag = $(call v-tag.$V,$1) +v-tag.0 = @printf " %-8s %s\n" '$1' '$@'; +V_AT = $(V_AT.$V) +V_AT.0 = @ + +objify = $(addsuffix $1, \ + $(basename \ + $(filter $(addprefix %.,$(SRCEXT)), \ + $2))) +DEPOBJS = +CLEAN += *.o *.d + +SRCEXT += c +CC = gcc +CFLAGS = $(OPTIMIZE) $(WARNINGS) +CCLD = $(CC) +LDFLAGS = +OPTIMIZE = -O2 -g3 -fno-omit-frame-pointer +WARNINGS = -pedantic -Wall + +SRCEXT += cc +CXX = g++ +CXXFLAGS = $(CFLAGS) +CXXLD = $(CXX) + +compile-c = $(call v-tag,CC)$(CC) -c $(CFLAGS) $3 \ + -MD -MF $(1:.o=.d) -o$1 $2 +%.o: %.c + $(call compile-c,$@,$<) + +compile-c++ = $(call v-tag,CXX)$(CXX) -c $(CFLAGS) $3 \ + -MD -MF $(1:.o=.d) -o$1 $2 +%.o: %.cc + $(call compile-c++,$@,$<) + +SRCEXT += rs +RUSTC = rustc +RUSTFLAGS = --edition=2018 -L. $(OPTIMIZE_RUST) +OPTIMIZE_RUST = -O +RUSTLIBS = +CARGODIR = /usr/share/cargo/registry +compile-rust = $(call v-tag,RUSTC)$(RUSTC) $(RUSTFLAGS) $3 \ + -o$1 $2 + +RUSTLIBS += typed_arena +typed_arena_DIR = $(CARGODIR)/typed-arena-2.0.0 +typed_arena_RUSTFLAGS = --cfg 'feature="std"' + +RUSTLIB_OBJS = $(foreach l,$(RUSTLIBS), lib$l.rlib) +CLEAN += $(RUSTLIB_OBJS) +$(RUSTLIB_OBJS): lib%.rlib: $$($*_DEPS) + $(call compile-rust,$@,$($*_DIR)/src/lib.rs, \ + --crate-type=rlib --crate-name=$* $($*_RUSTFLAGS)) + +TREELIBS = +VPATH = + +TREELIBS += xyla +xyla_VARIANTS = avl rb splay treap +XYLADIR = $(HOME)/src/libxyla +xyla_LIBS = $(XYLADIR)/build/.libs/libxyla.a +xyla_CFLAGS = -I$(XYLADIR) +xyla-avl_CFLAGS = -DTREE=XYLA_AVL +xyla-rb_CFLAGS = -DTREE=XYLA_RB +xyla-splay_CFLAGS = -DTREE=XYLA_SPLAY +xyla-treap_CFLAGS = -DTREE=XYLA_TREAP + +TREELIBS += qptrie +qptrie_VARIANTS = qp-fanf qp-mdw fn-fanf fn-mdw +QPDIR = $(HOME)/src/ext/qp +VPATH += $(QPDIR) +CFLAGS += -mpopcnt +qptrie_CFLAGS = -I$(QPDIR) +qptrie_SRCS = Tbl.c +qptrie-qp_SRCS = qp.c +qptrie-fn_SRCS = fn.c +qptrie-qp-fanf_CFLAGS = -DTREE=QPTRIE_QP -DUSE_RECURSIVE_TNEXTL +qptrie-qp-fanf_SRCS = $(qptrie-qp_SRCS) +qptrie-fn-fanf_CFLAGS = -DTREE=QPTRIE_FN -DUSE_RECURSIVE_TNEXTL +qptrie-fn-fanf_SRCS = $(qptrie-fn_SRCS) +qptrie-qp-mdw_CFLAGS = -DTREE=QPTRIE_QP +qptrie-qp-mdw_SRCS = $(qptrie-qp_SRCS) +qptrie-fn-mdw_CFLAGS = -DTREE=QPTRIE_FN +qptrie-fn-mdw_SRCS = $(qptrie-fn_SRCS) + +TREELIBS += sgt +sgt_VARIANTS = tree234 +SGTDIR = $(HOME)/src/sgt/puzzles +VPATH += $(SGTDIR) +sgt_CFLAGS = -I$(SGTDIR) +sgt-tree234_CFLAGS = -DTREE=SGT_TREE234 +sgt-tree234_SRCS = tree234.c malloc.c nullfe.c + +TREELIBS += libavl +libavl_VARIANTS = +LIBAVLDIR = $(HOME)/src/ext/avl +VPATH += $(LIBAVLDIR) +libavl_CFLAGS = -I$(LIBAVLDIR) + +libavl_VARIANTS += avl pavl rtavl tavl +libavl-avl_CFLAGS = -DTREE=LIBAVL_AVL +libavl-avl_SRCS = avl.c +libavl-pavl_CFLAGS = -DTREE=LIBAVL_PAVL +libavl-pavl_SRCS = pavl.c +libavl-rtavl_CFLAGS = -DTREE=LIBAVL_RTAVL +libavl-rtavl_SRCS = rtavl.c +libavl-tavl_CFLAGS = -DTREE=LIBAVL_TAVL +libavl-tavl_SRCS = tavl.c + +libavl_VARIANTS += rb prb rtrb trb +libavl-rb_CFLAGS = -DTREE=LIBAVL_RB +libavl-rb_SRCS = rb.c +libavl-prb_CFLAGS = -DTREE=LIBAVL_PRB +libavl-prb_SRCS = prb.c +libavl-rtrb_CFLAGS = -DTREE=LIBAVL_RTRB +libavl-rtrb_SRCS = rtrb.c +libavl-trb_CFLAGS = -DTREE=LIBAVL_TRB +libavl-trb_SRCS = trb.c + +#libavl_VARIANTS += bst pbst rtbst tbst +libavl-bst_CFLAGS = -DTREE=LIBAVL_BST +libavl-bst_SRCS = bst.c +libavl-pbst_CFLAGS = -DTREE=LIBAVL_PBST +libavl-pbst_SRCS = pbst.c +libavl-rtbst_CFLAGS = -DTREE=LIBAVL_RTBST +libavl-rtbst_SRCS = rtbst.c +libavl-tbst_CFLAGS = -DTREE=LIBAVL_TBST +libavl-tbst_SRCS = tbst.c + +TREELIBS += mLib +mLib_VARIANTS = sym +mLib_LIBS = -lmLib +mLib-sym_CFLAGS = -DTREE=MLIB_SYM + +define def-c-variant +ALL_VARIANTS += $1-$2 +TARGETS += chain.$1-$2 +CLEAN += chain.$1-$2 +$1-$2_OBJS = chain.$1-$2.o \ + $$(call objify,.o,$$($1_SRCS) $$($1-$2_SRCS)) +run-$1-$2 = ./chain.$1-$2 <$$1 +DEPOBJS += $$($1-$2_OBJS) +chain.$1-$2: $$($1-$2_OBJS) + $$(call v-tag,CCLD)$$(CCLD) $$(LDFLAGS) -o$$@ $$+ $$($1_LIBS) +chain.$1-$2.o: chain.c + $$(call compile-c,$$@,$$<,$$($1_CFLAGS) $$($1-$2_CFLAGS)) +endef +$(foreach t,$(TREELIBS), \ + $(foreach v,$($t_VARIANTS), \ + $(eval $(call def-c-variant,$t,$v)))) + +c++_VARIANTS += map +c++-map_CXXFLAGS = -DTREE=CXX_MAP +c++_VARIANTS += uomap +c++-uomap_CXXFLAGS = -DTREE=CXX_UOMAP + +define def-c++-variant +ALL_VARIANTS += c++-$1 +TARGETS += chain.c++-$1 +CLEAN += chain.c++-$1 +c++-$1_OBJS = chain.c++-$1.o +run-c++-$1 = ./chain.c++-$1 <$$1 +DEPOBJS += $$(c++-$1_OBJS) +chain.c++-$1: $$(c++-$1_OBJS) + $$(call v-tag,CXXLD)$$(CXXLD) $$(LDFLAGS) -o$$@ $$+ +chain.c++-$1.o: chain.cc + $$(call compile-c++,$$@,$$<,$$(c++-$1_CXXFLAGS)) +endef +$(foreach v,$(c++_VARIANTS), \ + $(eval $(call def-c++-variant,$v))) + +rust_VARIANTS += btree +rust-btree_RUSTFLAGS = --cfg 'feature="btree"' +rust_VARIANTS += hash +rust-hash_RUSTFLAGS = --cfg 'feature="hash"' + +define def-rust-variant +ALL_VARIANTS += rust-$1 +TARGETS += chain.rust-$1 +CLEAN += chain.rust-$1 +run-rust-$1 = ./chain.rust-$1 <$$1 +chain.rust-$1: chain.rs $$(RUSTLIB_OBJS) + $$(call compile-rust,$$@,$$<, \ + $$(foreach l,$$(RUSTLIBS), \ + $$(rust-$1_RUSTFLAGS) --extern=$$l)) +endef +$(foreach v,$(rust_VARIANTS), \ + $(eval $(call def-rust-variant,$v))) + +DICT = /usr/share/dict/british-english-insane + +MEASURES = $(foreach v,$(ALL_VARIANTS), measure/$v) +measure: $(MEASURES) +$(MEASURES): measure/%: chain.% + $TIME -f%U +.PHONY: measure $(MEASURES) + +all: $(TARGETS) + +clean::; rm -f $(CLEAN) + +-include $(DEPOBJS:.o=.d) diff --git a/chain.c b/chain.c new file mode 100644 index 0000000..8584ef2 --- /dev/null +++ b/chain.c @@ -0,0 +1,554 @@ +#include +#include +#include +#include +#include + +#define XYLA_AVL 1 +#define XYLA_RB 2 +#define XYLA_SPLAY 3 +#define XYLA_TREAP 4 +#define QPTRIE_QP 5 +#define QPTRIE_FN 6 +#define SGT_TREE234 7 +#define LIBAVL_AVL 8 +#define LIBAVL_BST 9 +#define LIBAVL_RB 10 +#define LIBAVL_PAVL 11 +#define LIBAVL_PBST 12 +#define LIBAVL_PRB 13 +#define LIBAVL_RTAVL 14 +#define LIBAVL_RTBST 15 +#define LIBAVL_RTRB 16 +#define LIBAVL_TAVL 17 +#define LIBAVL_TBST 18 +#define LIBAVL_TRB 19 +#define MLIB_SYM 20 + +#if !TREE +# error "`TREE' not defined or bungled constant setting" +#elif TREE == XYLA_AVL +# include "avl.h" +# define USE_XYLA 1 +# define WANT_HEIGHT 1 +# define tree__name(name) xyla_avl_##name +#elif TREE == XYLA_RB +# include "rb.h" +# define USE_XYLA 1 +# define WANT_HEIGHT 1 +# define tree__name(name) xyla_rb_##name +#elif TREE == XYLA_SPLAY +# include "splay.h" +# define USE_XYLA 1 +# define tree__name(name) xyla_splay_##name +#elif TREE == XYLA_TREAP +# include "treap.h" +# define USE_XYLA 1 +# define tree__name(name) xyla_treap_##name +#elif TREE == QPTRIE_QP +# include +# include +# include "Tbl.h" +# include "qp.h" +# define USE_QPTRIE 1 +#elif TREE == QPTRIE_FN +# include +# include +# include "Tbl.h" +# include "fn.h" +# define USE_QPTRIE 1 +#elif TREE == SGT_TREE234 +# include "tree234.h" +#elif TREE == LIBAVL_AVL +# include "avl.h" +# define USE_LIBAVL 1 +# define tree__name(name) avl_##name +#elif TREE == LIBAVL_BST +# include "bst.h" +# define USE_LIBAVL 1 +# define tree__name(name) bst_##name +#elif TREE == LIBAVL_RB +# include "rb.h" +# define USE_LIBAVL 1 +# define tree__name(name) rb_##name +#elif TREE == LIBAVL_PAVL +# include "pavl.h" +# define USE_LIBAVL 1 +# define tree__name(name) pavl_##name +#elif TREE == LIBAVL_PBST +# include "pbst.h" +# define USE_LIBAVL 1 +# define tree__name(name) pbst_##name +#elif TREE == LIBAVL_PRB +# include "prb.h" +# define USE_LIBAVL 1 +# define tree__name(name) prb_##name +#elif TREE == LIBAVL_RTAVL +# include "rtavl.h" +# define USE_LIBAVL 1 +# define tree__name(name) rtavl_##name +#elif TREE == LIBAVL_RTBST +# include "rtbst.h" +# define USE_LIBAVL 1 +# define tree__name(name) rtbst_##name +#elif TREE == LIBAVL_RTRB +# include "rtrb.h" +# define USE_LIBAVL 1 +# define tree__name(name) rtrb_##name +#elif TREE == LIBAVL_TAVL +# include "tavl.h" +# define USE_LIBAVL 1 +# define tree__name(name) tavl_##name +#elif TREE == LIBAVL_BST +# include "tbst.h" +# define USE_LIBAVL 1 +# define tree__name(name) tbst_##name +#elif TREE == LIBAVL_TRB +# include "trb.h" +# define USE_LIBAVL 1 +# define tree__name(name) trb_##name +#elif TREE == MLIB_SYM +# include +#else +# error "unknown `TREE' value" +#endif + +#if USE_XYLA +# define NODE tree__name(node) +# define PATH tree__name(path) +# define ITER tree__name(iter) +# define TREE_CHECK tree__name(check) +# define TREE_LOOKUP tree__name(lookup) +# define TREE_PROBE tree__name(probe) +# define TREE_INITITER tree__name(inititer) +# define TREE_NEXT tree__name(next) +# define TREE_INSERT tree__name(insert) +# if WANT_HEIGHT +# define H(x) x +# define HARG(x) , x +# else +# define H(x) +# define HARG(x) +# endif +#elif USE_LIBAVL +# define TABLE tree__name(table) +# define TRAVERSER tree__name(traverser) +# define TREE_CREATE tree__name(create) +# define TREE_DESTROY tree__name(destroy) +# define TREE_PROBE tree__name(probe) +# define TREE_FIND tree__name(find) +# define TREE_T_INIT tree__name(t_init) +# define TREE_T_NEXT tree__name(t_next) +#endif + +struct word { const char *p; size_t n; } word; + +struct node { +#if USE_XYLA + struct NODE _n; +#elif TREE == MLIB_SYM + struct sym_base _s; +#endif +#if TREE != MLIB_SYM + struct word w; +#endif + struct node *down, *right, *up; + int len; +}; + +#define WORDMAX 64 + +static void bail(const char *msg, ...) +{ + va_list ap; + long pos; + + va_start(ap, msg); vfprintf(stderr, msg, ap); va_end(ap); + pos = ftell(stdin); + if (pos >= 0) fprintf(stderr, " (input pos = %ld)", pos); + fputc('\n', stderr); + exit(2); +} + +#if USE_XYLA || TREE == SGT_TREE234 || USE_LIBAVL + +static int compare_words(const struct word *a, const struct word *b) +{ + size_t alen = a->n, blen = b->n; + int ord; + + ord = memcmp(a->p, b->p, alen <= blen ? alen : blen); + if (!ord) ord = alen < blen ? -1 : alen > blen ? +1 : 0; + return (ord); +} + +#endif + +#if USE_XYLA + +static int word_nav(struct xyla_bst_nodecls *cls, + const struct xyla_bst_node *nn, void *arg) +{ + const struct word *k = arg; + const struct node *node = (struct node *)nn; + + return (compare_words(k, &node->w)); +} + +# define DECLS \ + struct xyla_bst_node *root = 0; \ + struct PATH path; \ + struct ITER it + +# define INIT do ; while (0) + +# if TREE == XYLA_TREAP +# define EXTRA_NODE_SETUP do { node->_n.wt = rand(); } while (0) +# endif +# ifndef EXTRA_NODE_SETUP +# define EXTRA_NODE_SETUP do ; while (0) +# endif +# define INSERT do { \ + if (TREE_PROBE(0, &root, word_nav, &word, &path)) { \ + printf(";; duplicate `%s'\n", buf); \ + free(node); node = 0; \ + } else { \ + EXTRA_NODE_SETUP; \ + TREE_INSERT(0, &path, &node->_n); \ + } \ + } while (0) + +# define ITERATE \ + for (TREE_INITITER(&root, &it); node = TREE_NEXT(&it), node; ) + +# if TREE == XYLA_SPLAY +# define FOCUS do { xyla_splay_splay(0, &path); } while (0) +# else +# define FOCUS do ; while (0) +# endif + +# define LOOKUP TREE_LOOKUP(0, &root, word_nav, &word) + +# define FREE do { \ + while (node = xyla_bst_severfirst(&root), node) free(node); \ + } while (0) + +# ifndef WANT_CHECKS +# define CHECK do ; while (0) +# else + +static const void *word_key(struct xyla_bst_nodecls *cls, + const struct xyla_bst_node *nn) + { struct node *node = (struct node *)nn; return (&node->w); } + +static void word_ident(struct xyla_bst_nodecls *cls, + const struct xyla_bst_node *nn, FILE *fp) + { struct node *node = (struct node *)nn; fprintf(fp, "`%s'", node->w.p); } + +static const struct xyla_bst_ordnodeops word_ops = { + { 0, xyla_bst_chkorder, sizeof(struct xyla_bst_ordinfo), word_ident }, + { word_nav, word_key } +}; +struct xyla_bst_nodecls word_cls = { &word_ops.node }; + +# define CHECK do { \ + if (TREE_CHECK(&word_cls, &root HARG(-1), 0)) \ + bail("check failed"); \ + } while (0) +# endif + +#elif USE_QPTRIE +# ifdef USE_RECURSIVE_TNEXTL +# define my_Tnextl Tnextl +# elif TREE == QPTRIE_QP + +static bool my_Tnextl(Tbl *tbl, const char **k_inout, size_t *sz_inout, + void **val_out) +{ + const char *k = *k_inout; + size_t sz = *sz_inout; + Trie *t, *resume; + unsigned off, max; + Tbitmap b; + + if (!tbl) + return (false); + else { + t = &tbl->root; + if (k) { + resume = 0; + while (isbranch(t)) { + __builtin_prefetch(t->branch.twigs); + b = twigbit(t, k, sz); + TWIGOFFMAX(off, max, t, b); + if (!hastwig(t, b)) return (false); + t = twig(t, off); + if (off + 1 < max) resume = t + 1; + } + if (strcmp(k, t->leaf.key) != 0) return (false); + t = resume; if (!t) return (false); + } + } + while (isbranch(t)) t = twig(t, 0); + *k_inout = k = t->leaf.key; *sz_inout = strlen(k); *val_out = t->leaf.val; + return (true); +} + +# elif TREE == QPTRIE_FN + +static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout, + void **val_out) +{ + const char *k = *k_inout; + size_t sz = *sz_inout; + Trie *resume; + unsigned off, max; + Tbitmap b; + Tindex i; + + if (!t) + return (false); + else if (k) { + resume = 0; + while (isbranch(t)) { + __builtin_prefetch(t->ptr); + i = t->index; b = twigbit(i, k, sz); + TWIGOFFMAX(off, max, i, b); + if (!hastwig(i, b)) return (false); + t = Tbranch_twigs(t) + off; + if (off + 1 < max) resume = t + 1; + } + if (strcmp(k, Tleaf_key(t)) != 0) return (false); + t = resume; if (!t) return (false); + } + while (isbranch(t)) t = Tbranch_twigs(t); + *k_inout = k = Tleaf_key(t); *sz_inout = strlen(k); + *val_out = Tleaf_val(t); + return (true); +} + +# endif + +# define DECLS \ + Tbl *tbl = 0; \ + struct word cur; \ + void *v + +# define INIT do ; while (0) + +# define INSERT do { \ + tbl = Tsetl(tbl, node->w.p, node->w.n, node); \ + } while (0) + +# define ITERATE \ + for (cur.p = 0, cur.n = 0; \ + my_Tnextl(tbl, &cur.p, &cur.n, &v) ? node = v, 1 : 0; ) + +# define FOCUS do ; while (0) + +# define GETPREFIX do { \ + word.n = node->w.n - 1; assert(word.n < WORDMAX); \ + memcpy(buf, node->w.p, word.n); buf[word.n] = 0; \ + } while (0) + +# define LOOKUP Tgetl(tbl, buf, word.n) + +# define FREE do { \ + while (tbl) { \ + cur.p = 0; cur.n = 0; my_Tnextl(tbl, &cur.p, &cur.n, &v); \ + tbl = Tsetl(tbl, cur.p, cur.n, 0); free(v); \ + } \ + } while (0) + +# define CHECK do ; while (0) + +#elif TREE == SGT_TREE234 + +static int node_cmp(void *a, void *b) + { const struct word *wa = a, *wb = b; return (compare_words(wa, wb)); } + +# define DECLS \ + tree234 *root; \ + int i + +# define INIT do { root = newtree234(node_cmp); } while (0) + +# define INSERT do { \ + if (add234(root, node) != node) { \ + printf(";; duplicate `%s'\n", buf); \ + free(node); node = 0; \ + } \ + } while (0) + +# define ITERATE for (i = 0; node = index234(root, i), node; i++) + +# define FOCUS do ; while (0) + +# define LOOKUP find234(root, &word, 0) + +# define FREE do { \ + while (node = delpos234(root, 0), node) free(node); \ + freetree234(root); \ + } while (0) + +# define CHECK do ; while (0) + +#elif USE_LIBAVL + +static int node_cmp(const void *a, const void *b, void *arg) + { const struct word *wa = a, *wb = b; return (compare_words(wa, wb)); } + +static void free_node(void *n, void *arg) { free(n); } + +# define DECLS \ + struct TABLE *tab; \ + struct TRAVERSER it; \ + void **p + +# define INIT do { \ + tab = TREE_CREATE(node_cmp, 0, 0); \ + if (!tab) bail("out of memory"); \ + } while (0) + +# define INSERT do { \ + p = TREE_PROBE(tab, node); if (!p) bail("out of memory"); \ + if (*p != node) { \ + printf(";; duplicate `%s'\n", buf); \ + free(node); node = 0; \ + } \ + } while (0) + +# define ITERATE \ + for (TREE_T_INIT(&it, tab); node = TREE_T_NEXT(&it), node; ) + +# define FOCUS do ; while (0) + +# define LOOKUP TREE_FIND(tab, &word) + +# define FREE do { TREE_DESTROY(tab, free_node); } while (0) + +# define CHECK do ; while (0) + +#elif TREE == MLIB_SYM + +# define DECLS \ + sym_table tab; \ + sym_iter it; \ + unsigned foundp + +# define INIT do { sym_create(&tab); } while (0) + +# define PREPNODE do ; while (0) + +# define INSERT do { \ + node = sym_find(&tab, buf, word.n, sizeof(*node), &foundp); \ + if (foundp) { bail(";; duplicate `%s'\n", buf); node = 0; } \ + } while (0) + +# define ITERATE for (sym_mkiter(&it, &tab); node = sym_next(&it), node; ) + +# define FOCUS do ; while (0) + +# define WORDPTR(node) (SYM_NAME(node)) +# define WORDLEN(node) (SYM_LEN(node)) + +# define LOOKUP sym_find(&tab, word.p, word.n, 0, 0) + +# define FREE do { sym_destroy(&tab); } while (0) + +# define CHECK do ; while (0) + +#endif + +#ifndef PREPNODE +# define PREPNODE do { \ + node = malloc(sizeof(*node) + word.n + 1); \ + if (!node) bail("out of memory"); \ + node->w.p = (char *)(node + 1); \ + memcpy(node + 1, buf, word.n + 1); node->w.n = word.n; \ + } while (0) +#endif + +#ifndef WORDPTR +# define WORDPTR(node) ((node)->w.p) +#endif + +#ifndef WORDLEN +# define WORDLEN(node) ((node)->w.n) +#endif + +#ifndef GETPREFIX +# define GETPREFIX do { \ + word.p = WORDPTR(node); word.n = WORDLEN(node) - 1; \ + } while (0) + +#endif + +static void print_chain(struct node *node) +{ + if (!node->right) { + fputs(WORDPTR(node), stdout); + if (node->down) { putchar(' '); print_chain(node->down); } + } else { + fputs("{ ", stdout); + for (;;) { + fputs(WORDPTR(node), stdout); + if (node->down) { putchar(' '); print_chain(node->down); } + node = node->right; if (!node) break; + fputs(" | ", stdout); + } + fputs(" }", stdout); + } +} + +int main(void) +{ + DECLS; + struct node *node, *parent; + struct word word; + char buf[WORDMAX]; + int ch, max; + + INIT; + word.p = buf; + for (;;) { + if (!fgets(buf, WORDMAX, stdin)) break; + word.n = strlen(buf); assert(word.n); + if (buf[word.n - 1] == '\n') buf[--word.n] = 0; + else if (word.n == WORDMAX - 1) bail("word too long"); + else if (ch = getchar(), ch != EOF) bail("short read, found `%c'", ch); + + PREPNODE; INSERT; + if (node) { node->up = node->down = node->right = 0; node->len = 1; } + } + + CHECK; + + max = 0; + + ITERATE { + FOCUS; +/* fprintf(stderr, ";; ponder `%.*s'\n", WORDLEN(node), WORDPTR(node)); */ + if (WORDLEN(node) <= 1) + parent = 0; + else { + GETPREFIX; +/* fprintf(stderr, ";; search `%.*s'\n", word.n, word.p); */ + parent = LOOKUP; + } + node->up = parent; + while (parent) { + if (parent->len > node->len + 1) break; + if (parent->len < node->len + 1) parent->down = 0; + if (parent->down != node) + { node->right = parent->down; parent->down = node; } + parent->len = node->len + 1; + if (parent->len > max) max = parent->len; + node = parent; parent = node->up; + } + } + + ITERATE if (node->len == max) { print_chain(node); putchar('\n'); } + FREE; + return (0); +} diff --git a/chain.cc b/chain.cc new file mode 100644 index 0000000..0fd7e6e --- /dev/null +++ b/chain.cc @@ -0,0 +1,119 @@ +#include +#include +#include +#include +#include + +#include +#include + +#define CXX_MAP 1 +#define CXX_UOMAP 2 + +struct Node; +typedef std::pair WordNode; +struct Node { + WordNode *down, *right, *up; + int len; +}; + +#if !TREE +# error "`TREE' not defined or bungled constant setting" +#elif TREE == CXX_MAP +# include + typedef std::map Map; +#elif TREE == CXX_UOMAP +# include + typedef std::unordered_map Map; +#else +# error "unknown `TREE' value" +#endif + +#define WORDMAX 64 + +static void bail(const char *msg, ...) +{ + va_list ap; + long pos; + + va_start(ap, msg); std::vfprintf(stderr, msg, ap); va_end(ap); + pos = std::ftell(stdin); + if (pos >= 0) std::fprintf(stderr, " (input pos = %ld)", pos); + std::fputc('\n', stderr); + std::exit(2); +} + +static void print_chain(WordNode *node) +{ + if (!node->second.right) { + std::fputs(node->first.c_str(), stdout); + if (node->second.down) + { std::putchar(' '); print_chain(node->second.down); } + } else { + std::fputs("{ ", stdout); + for (;;) { + std::fputs(node->first.c_str(), stdout); + if (node->second.down) + { std::putchar(' '); print_chain(node->second.down); } + node = node->second.right; if (!node) break; + std::fputs(" | ", stdout); + } + std::fputs(" }", stdout); + } +} + +int main(void) +{ + Map map{}; + char buf[WORDMAX]; size_t n; + int ch, max; + + for (;;) { + if (!std::fgets(buf, WORDMAX, stdin)) break; + n = std::strlen(buf); assert(n); + if (buf[n - 1] == '\n') buf[--n] = 0; + else if (n == WORDMAX - 1) bail("word too long"); + else if (ch = std::getchar(), ch != EOF) + bail("short read, found `%c'", ch); + + auto r = map.insert(WordNode(std::string(buf, n), Node{})); + if (!r.second) printf(";; duplicate `%s'\n", buf); + else { + WordNode *w = &*r.first; + w->second.up = w->second.down = w->second.right = 0; + w->second.len = 1; + } + } + + max = 0; + + for (auto p = map.begin(); p != map.end(); ++p) { +/* std::fprintf(stderr, ";; ponder `%.*s'\n", + p->first.length(), p->first.c_str()); */ + WordNode *w = &*p, *parent; + if (w->first.length() <= 1) + parent = 0; + else { +/* std::fprintf(stderr, ";; search `%.*s'\n", + w->first.length(), w->first.c_str()); */ + std::string prefix{w->first, 0, w->first.length() - 1}; + auto p = map.find(prefix); parent = p == map.end() ? 0 : &*p; + } + w->second.up = parent; + while (parent) { + if (parent->second.len > w->second.len + 1) break; + if (parent->second.len < w->second.len + 1) parent->second.down = 0; + if (parent->second.down != w) { + w->second.right = parent->second.down; + parent->second.down = w; + } + parent->second.len = w->second.len + 1; + if (parent->second.len > max) max = parent->second.len; + w = parent; parent = w->second.up; + } + } + + for (auto p = map.begin(); p != map.end(); ++p) + if (p->second.len == max) { print_chain(&*p); std::putchar('\n'); } + return (0); +} diff --git a/chain.rs b/chain.rs new file mode 100644 index 0000000..9330746 --- /dev/null +++ b/chain.rs @@ -0,0 +1,111 @@ +use std::cell::Cell; +use std::io::{self, BufRead, Write}; +use std::ptr; + +use typed_arena; + +#[cfg(feature = "btree")] +use std::collections::{btree_map::Entry as MapEntry, BTreeMap as Map}; + +#[cfg(feature = "hash")] +use std::collections::{hash_map::Entry as MapEntry, HashMap as Map}; + +#[derive(Debug, Default)] +struct Node<'a> { + word: &'a [u8], + len: Cell, + down: Cell>>, + right: Cell>>, + up: Cell>> +} + +fn print_chain(node: &Node, out: &mut W) -> io::Result<()> { + match node.right.get() { + None => { + out.write_all(node.word)?; + if let Some(down) = node.down.get() + { out.write_all(b" ")?; print_chain(down, out)?; } + } + Some(_) => { + out.write_all(b"{ ")?; + let mut node = node; + loop { + out.write_all(node.word)?; + if let Some(down) = node.down.get() + { out.write_all(b" ")?; print_chain(down, out)?; } + if let Some(right) = node.right.get() + { node = right; out.write_all(b" | ")?; } + else + { break; } + } + out.write_all(b" }")?; + } + } + Ok(()) +} + +fn main() -> io::Result<()> { + let byte_arena = typed_arena::Arena::new(); + let node_arena = typed_arena::Arena::new(); + let mut buf: Vec = Vec::with_capacity(64); + let global_stdin = io::stdin(); let mut stdin = global_stdin.lock(); + let global_stdout = io::stdout(); let mut stdout = global_stdout.lock(); + let global_stderr = io::stderr(); let mut stderr = global_stderr.lock(); + let mut map = Map::new(); + + loop { + buf.clear(); + let n = stdin.read_until(b'\n', &mut buf)?; + let mut line = &buf[0 .. n]; + let n = line.len(); + if n == 0 { break; } + if line[n - 1] == b'\n' { line = &line[0 .. n - 1]; } +//stdout.write_all(b";; read `")?; +//stdout.write_all(line)?; +//stdout.write_all(b"'\n")?; + let word: &[u8] = byte_arena.alloc_extend(line.iter().map(|p| *p)); + if let MapEntry::Vacant(e) = map.entry(word) { + e.insert(node_arena.alloc(Node { word: word, .. Node::default() })); + } else { + stderr.write_all(b";; duplicate `")?; + stderr.write_all(word)?; + stderr.write_all(b"'\n")?; + } + } + + let mut max = 0; + for node in map.values() { +//stdout.write_all(b";; ponder `")?; +//stdout.write_all(node.word)?; +//stdout.write_all(b"'\n")?; + let mut node: &Node = node; + let mut parent; + let n = node.word.len(); + if n <= 1 { parent = None; } + else { parent = map.get(&node.word[0 .. n - 1]).map(|n| &**n); } + node.up.set(parent); + while let Some(parent_node) = parent { + let plen = parent_node.len.get(); + let nlen = node.len.get() + 1; + if plen > nlen { break; } + if plen < nlen { parent_node.down.set(None); } + match parent_node.down.get() { + Some(link) if ptr::eq(link, node) => (), + _ => { + node.right.set(parent_node.down.get()); + parent_node.down.set(Some(node)); + } + } + parent_node.len.set(nlen); + if nlen > max { max = nlen; } + node = parent_node; parent = node.up.get() + } + } + + for node in map.values() { + if node.len.get() == max + { print_chain(node, &mut stdout)?; stdout.write(b"\n")?; } + } + + Ok(()) +}